引入IVHFS的數(shù)學表達式檢索結(jié)果排序方法

韓 蘋，田學東

(河北大學 網(wǎng)絡空間安全與計算機學院，河北 保定 071002)

1 引 言

傳統(tǒng)面向一維文本的檢索方法很難對數(shù)學表達式這種特殊的信息表現(xiàn)形式進行檢索和處理，且數(shù)學表達式檢索的查詢式和檢索結(jié)果會因為數(shù)學表達式豐富的語法語義變換特性而存在需求偏離的情況，導致檢索性能降低.因此，有必要針對以數(shù)學表達式為查詢關(guān)鍵詞的數(shù)學表達式檢索結(jié)果排序.

國內(nèi)外針對數(shù)學表達式檢索的研究取得了一定的進展.在公式檢索結(jié)果排序方面，Mansouri等人[1]為使排序更為準確、有效，引入了一種新的外觀符號布局樹(Symbol Layout Trees，SLTs)、運算符樹(Operator Trees，OPTs)兩個分層的公式嵌入模型，提高公式間相似性的精確度.Math-aware[2]是一種能夠結(jié)合數(shù)學公式布局和語義特征的三層公式搜索模型，結(jié)合并行索引和相似度評價方法，在公式的檢索結(jié)果排名中能夠提高檢索的排序效果和質(zhì)量.Dallas等人[3]融合數(shù)學表達式符號布局樹的特征作為關(guān)鍵搜索詞，并使用BM25文本排序方法，實現(xiàn)基于數(shù)學和文本之間的搜索.DLMF(Digital Library of Mathematical Functions)Search[4]主要是針對數(shù)學圖書館而建立的數(shù)學表達式檢索系統(tǒng)在檢索結(jié)果排序方面先后改進了TF-IDF[5]算法，從而實現(xiàn)對數(shù)學檢索內(nèi)容的檢索.

宰新宇等人[6]在對科技文檔檢索時融入了一種詞嵌入語言模型，彌補了單一的公式對文檔檢索造成絕對性的影響，結(jié)合上下文語義特征構(gòu)建了一種融合公式和語義特征的科技文檔檢索模型，從而實現(xiàn)檢索結(jié)果更為有效、合理的排序.孟祥福等人[7]提出一種空間關(guān)鍵字個性化語義查詢方法，該方法能夠完整顯示原有信息的個性化查詢，提高個性化查詢程度和準確率.黃鶯等人[8]利用用戶的個性化信息，融合擴展檢索技術(shù)，優(yōu)化了檢索結(jié)果排序，減少用戶獲取資源的時間.崔曉娟等人[9]在提取數(shù)學表達式的檢索特征上構(gòu)建了分層結(jié)構(gòu)索引表，采用TF-IDF對文檔向量賦予權(quán)值，利用余弦相似度來計算檢索向量和文檔之間的相似度，最終實現(xiàn)有關(guān)數(shù)學表達式的科技文檔檢索結(jié)果的有序輸出.

由于數(shù)學表達式屬于多種符號構(gòu)成的復雜二維模式，如何將其在符號、語法、語義等方面的屬性合理融合，獲取符合用戶需求的數(shù)學表達式檢索結(jié)果，成為一項關(guān)鍵問題.本文將數(shù)學表達式檢索結(jié)果排序問題轉(zhuǎn)化成模糊信息決策問題，利用IVHFS理論在多屬性決策上的優(yōu)勢，求得數(shù)學表達式間的相似性距離，從而得到排序結(jié)果.其中，該理論的優(yōu)勢主要概括為3個方面：

1)保留信息的猶豫性和模糊性，貼合人類描述信息形式，確保了數(shù)學表達式屬性信息的有效性和完整性；

2)將屬性信息映射為多個區(qū)間值的評價指標，擴展了決策信息的不定性描述，從而削弱數(shù)學表達式屬性評價指標的不確定因素，提高描述信息的靈活性，使得檢索結(jié)果更加合理化；

3)區(qū)間的左右端點，分別代表屬性指標的最小和最大值，避免評估信息的主觀性，很好地解決了不完全信息中的決策問題.

2 相關(guān)工作

區(qū)間值猶豫模糊集

在多屬性決策問題中，為了描述信息中的不確定性，表達人們對事物的刻畫，1965年Zadeh[10]提出了模糊集的概念，來描述人們對于事物的評判.2010年Torra[11]提出了猶豫模糊集，拓展了描述隸屬度函數(shù)方面的局限.2013年陳樹偉等人[12]提出了區(qū)間值猶豫模糊集理論，進一步完善了隸屬度函數(shù)的取值范圍.因此，引入?yún)^(qū)間值來增強決策信息的猶豫偏好程度，可以使決策結(jié)果更加合理并貼合實際.

定義 1[12，13].設非空集合為X={x1，x2，…，xn}，則關(guān)于X的區(qū)間值猶豫模糊集為：

(1)

(2)

偏差函數(shù)為：

(3)

根據(jù)得分函數(shù)和偏差函數(shù)可以比較兩個區(qū)間值猶豫模糊元素的大小，它們之間的比較法則[12，14]為：

3 數(shù)學表達式相似度評價方法

(4)

4 基于IVHFS的數(shù)學表達式檢索結(jié)果排序方法

在對數(shù)學表達式屬性特征信息描述中，一般的描述方法是將屬性評價信息用某一精確的數(shù)值來描述.但是，當某一對象的屬性評價值有多個時，精確值則無法完全概括，導致部分信息丟失，影響排序效果.因此，采用IVHFS理論對數(shù)學表達式進行綜合評價，將某一對象屬性以多個可能的區(qū)間值集合的形式表示出來，可以更好描述評估屬性信息，解決數(shù)學表達式評價中的不確定性問題，從而判斷數(shù)學表達式之間的相似度，實現(xiàn)以數(shù)學表達式為查詢關(guān)鍵字的數(shù)學表達式檢索結(jié)果排序.故將其引入數(shù)學表達式檢索結(jié)果排序問題.本文主要對包含式查詢，且主要分為兩個部分：確定數(shù)學表達式區(qū)間值屬性以及對IVHFS集合進行相似度評價.

4.1 數(shù)學表達式的多屬性評價指標

IVHFS對數(shù)學表達式進行多屬性描述，其優(yōu)勢主要體現(xiàn)在兩個方面：1)利用IVHFS的模糊性和猶豫特性，貼近人類語言表述形式，諸如“好”，“壞”等態(tài)度詞匯，能更加靈活地描述屬性信息；2)利用區(qū)間值可以減少重復出現(xiàn)的子式以及符號屬性的描述，從而形成基于數(shù)學表達式的綜合評價屬性的IVHFS集合.數(shù)學表達式屬性評價指標如圖1所示.

圖1中評價指標的設計主要圍繞查詢式、運算符和運算數(shù)3方面屬性.其中，屬性提取規(guī)則是根據(jù)FDS(Formula Description Structure)[15-17]做了改進，可簡單描述為：提取查詢子式、運算符和運算數(shù)中的FDS屬性特征.

圖1 數(shù)學表達式屬性評價指標結(jié)構(gòu)圖Fig.1 Structure diagram of formula attribute evaluation index

4.1.1 子式空間結(jié)構(gòu)屬性

將Q作為一個整體，將其看成單獨的“運算符”或“運算數(shù)”，利用改進的FDS方法提取子式屬性特征.

1)長度指標

定義 4.子式長度指標隸屬函數(shù)為：

(5)

lenQ、lenRQt分別為Q和RQt的符號總數(shù)；Q在RQt中所占比例越大，相似度越高，兩個公式越相似.

2)位置指標

Q在RQt中的位置越靠前，Q對于RQt越重要，公式的相似度越高.當RQt中有多個Q時，pos的指標函數(shù)可以用區(qū)間值的形式來表示，取位于RQt中靠前的Q所在位置函數(shù)值為區(qū)間值的左端點，RQt中最后一個Q的位置函數(shù)值為區(qū)間的右端點.

定義 5.位置指標隸屬函數(shù)可以表示為：

(6)

其中，e-β(pos-1)是位置屬性權(quán)重函數(shù)，pos(1，2，3，…)表示解析公式Q在RQt中的位置，β是位置屬性權(quán)重系數(shù)，該區(qū)間越接近[1，1]，RQt和Q的相似度越高.

所以，相似度大小為：sim(Q1，RQ1)>sim(Q1，RQ2)

3)標志位指標

數(shù)學表達式特殊的二維結(jié)構(gòu)關(guān)系可以用標志位表示其所

圖2 公式標志位示意圖Fig.2 Schematic diagram of formula flag

在空間位置關(guān)系情況，圖2為標志位示意圖，0-8數(shù)字依次代表8種位置狀態(tài)關(guān)系.其中，每個標志位所在的重要程度不同，標志位權(quán)重越高，說明公式在該標志位的可能性越大，公式間相似度越高.

定義 6.標志位隸屬函數(shù)為：

(7)

4)層次指標

RQt中Q層次越接近主基線位置，相似度越高，排序越靠前.

定義 7.層次隸屬函數(shù)為：

(8)

圖3 RQ3改進的FDS示意圖Fig.3 Improved FDS diagram of RQ3

表1 RQ3的子式空間結(jié)構(gòu)屬性區(qū)間值Table 1 Interval values of subspace structure attribute of RQ3

4.1.2 符號關(guān)聯(lián)評價指標

符號關(guān)聯(lián)度評價指標反映了符號在數(shù)據(jù)集中出現(xiàn)的頻度以及符號所在層次和標志位特征分布權(quán)重的關(guān)聯(lián)屬性信息.該指標利用TF-IDF-ICD[18]特征提取算法，構(gòu)造了屬性隸屬函數(shù).

定義 8.符號關(guān)聯(lián)指標隸屬函數(shù)為：

(9)

μsk是符號s的關(guān)聯(lián)度隸屬函數(shù)；TFs為s的頻度公式，描述Q中s個數(shù)nQs和RQt中s個數(shù)nRQts之比；IDFs是公式逆頻率，N為數(shù)據(jù)庫中公式總數(shù)，NsRQt為Q中出現(xiàn)任意符號的公式總數(shù)；ICDsk是符號頻度和符號類別分布公式，當符號處于不同層次或標志位時，其權(quán)重不同；α是IDF與ICD之間的調(diào)和因子，α越大符號屬性權(quán)重分布越高，ICD值越大，說明IDF對該函數(shù)影響越小.

圖4 RQ4的運算符關(guān)聯(lián)屬性示意圖Fig.4 Schematic diagram of operator association properties for RQ4

4.2 數(shù)學表達式檢索結(jié)果排序方法

對數(shù)學表達式檢索結(jié)果進行排序的算法如算法1所示.

算法1.IVHFS的數(shù)學表達式檢索結(jié)果排序算法

輸入：LaTeX數(shù)學表達式Q

輸出：結(jié)果表達式的排序集合rank

1.doublef[j][3]

//存放待查詢式的關(guān)鍵字j的屬性指標特征flag(f[j][0])、level(f[j][1])、len(f[j][2])、pos(f[j][3])

2.IVHFSR

//待查詢式的區(qū)間值猶豫模糊集合

3.ifQ?RQtthen//RQt中存在子式Q

4. 按FDS解析公式

5.whilelength(Q)≠0do

6.key(i)//將Q、Q中所包含符號填入到關(guān)鍵詞字典

7.forj=1∶4

8.f[j][i]//關(guān)鍵字i的屬性特征矩陣

9.ifi=keythen

/*key為Q中關(guān)鍵字子式Q、運算符o和運算數(shù)n*/

//關(guān)鍵字隸屬度區(qū)間值

/*子式空間結(jié)構(gòu)屬性隸屬度區(qū)間值集合，將特征帶入式(5)-式(8)所得*/

/*運算符屬性隸屬度區(qū)間值集合，將特征帶入式(9)所得*/

/*運算數(shù)屬性隸屬度區(qū)間值集合，將特征帶入式(9)所得*/

15.dis(Q，RQ)=dis(IVHFSQ，IVHFSRQ)

//Q和RQ之間的距離測度值

16.sim(Q，RQ)=1-dis(Q，RQ)

//Q和RQ的相似度，根據(jù)公式(4)所得

17.endif

18.endfor

19.endwhile

20.endif

21.RQ={RQ1，RQ2，RQ3，…}

//按相似度對結(jié)果式進行排序

22.if(sim(Q，RQt)=sim(Q，RQg))

23.e(RQ)、h(RQ)

/*待查詢式的得分函數(shù)值和偏差函數(shù)值，

將IVHFSR代入公式(2)和公式(3)所得*/

24. 確定RQt、RQg的排序順序

//按照得分和偏差值的比較法則排序

//結(jié)果表達式排序集合

26.endif

27.returnrank

在算法1中，子式屬性關(guān)鍵字只有一個，當待查詢式中存在多個Q時，僅取屬性指標的最大值和最小值構(gòu)成子式屬性集合；但是，對于某些公式運算符和運算數(shù)的關(guān)鍵字不止一個，選取公式中運算符或運算數(shù)屬性評價指標的最大值和最小值作為屬性隸屬度區(qū)間值集合即可.

5 實驗分析

5.1 實驗環(huán)境

在visual studio 2017和SQL2012環(huán)境下，采用C#編程語言實現(xiàn)數(shù)學表達式檢索模型.以公共數(shù)據(jù)集NTCIR-12_MathIR_Wikipedia_Corpus[19]的31742個LaTeX格式的HTML科技文獻集合中獲取的528188個數(shù)學表達式作為實驗數(shù)據(jù)集.

5.2 實驗參數(shù)設定

1)黃駿等人[18]通過實驗表明，當調(diào)和因子α=2時，可以有效增加分類屬性的準確率；

2)通過對數(shù)據(jù)庫中的數(shù)學表達式分析、統(tǒng)計、歸納屬性信息，確定了位置權(quán)重系數(shù)β=0.66；數(shù)學表達式標志位和層次指標值分別如表2、表3所示，其中，x可以代表查詢公式Q、運算符o以及運算數(shù)n；

表2 數(shù)學表達式標志位指標Table 2 Mathematical expressions of flag indicators

表3 數(shù)學表達式層次指標Table 3 Mathematical expressions of level indicators

所以，對μslevel和μsflag分別除以7.3、7.7方便排序.

5.3 實驗結(jié)果分析

本實驗主要對528188個數(shù)學公式進行分析和檢索實驗，以查詢公式“Q2=x+y”為例，得到一個有序的有限結(jié)果表達式集合RQ2={RQ21，RQ22，RQ23，…}.其中，RQ21是集合RQ2中與Q2相似度最高的公式，且集合內(nèi)相似度依次降低.表4為檢索Q2時部分表達式的區(qū)間值猶豫模糊集合以及相似度.

表4 部分表達式的區(qū)間值猶豫模糊集以及相似度Table 4 Partial interval valued hesitation fuzzy sets and similarity of expression

ID是公式序號，其中，查詢式的ID=1；根據(jù)公式(4)，選擇不同的相似測度對表4中數(shù)據(jù)處理，當λ=1、2、3時，對應的排序結(jié)果序列分別為：

E1=(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18)

E2=(1，2，3，4，5，6，7，8，9，10，11，12，13，15，14，16，17，18)

E3=(1，2，3，4，5，6，7，8，9，10，11，13，12，15，14，16，17，18)

專家的排序結(jié)果序列為：

EV=(1，3，2，4，5，6，7，9，8，10，11，12，14，13，15，16，17，18)

采用皮爾遜相關(guān)系數(shù)計算專家評價和本方法的排序結(jié)果序列間的相關(guān)度，兩個排序結(jié)果序列之間的相關(guān)度越高，說明該評判方法越接近專家的判斷.其中，皮爾遜相關(guān)系數(shù)計算公式為：

(10)

其中，ρ的取值范圍為[-1，1]；

NV代表實驗算法排序結(jié)果序列；

EV代表專家排序結(jié)果序列.

當λ取不同值時，部分數(shù)學表達式相似度取值如圖5所示，皮爾遜相關(guān)系數(shù)分別為：

ρE1，EV=0.9938、ρE2，EV=0.9897、ρE3，EV=0.9856

通過皮爾遜相關(guān)系數(shù)和圖5折線圖中決策結(jié)果進行對比分析觀察可以得出，當λ取不同的值時，相似度的相對大小趨勢不變，因此該方法在一定程度上具有較高的普適性和可靠性.

圖5 部分表達式的相似度Fig.5 Partial similarity of expression

5.4 對比實驗

表5 Top-5檢索結(jié)果Table 5 Top-5 search results

于查詢式中的符號時，兩個公式相似度相同，無法確定兩個公式的先后關(guān)系.比如，本文系統(tǒng)中第3個和第4個檢索結(jié)果為并列關(guān)系，這是本實驗未考慮到的地方，未來會增加包含查詢公式以外符號屬性的指標函數(shù)，不斷完善排序效果.

5.5 檢索分析

選取表4中ID值為前10的公式作為查詢關(guān)鍵字檢索，利用公式(11)得到如圖6所示的查全率(Recall)和查準率(Precision).

查全率=(檢索出的相關(guān)公式個數(shù)/ 系統(tǒng)中相關(guān)公式總數(shù))*100%

查準率=(檢索出的相關(guān)公式個數(shù)/ 檢索出的公式總數(shù))*100%

(11)

本文的平均查全率為75.8%，平均查準率為66.4%.當查詢公式越簡單時，系統(tǒng)中相關(guān)公式的數(shù)量就越多，公式的查全率就越高；而當查詢公式越復雜，其系統(tǒng)中的相關(guān)公式數(shù)量

圖6 系統(tǒng)檢索查全率和查準率Fig.6 Retrieval recall and precision

就越少，所以，公式查詢結(jié)果越容易產(chǎn)生錯誤，其查準率越低.

6 結(jié)論與展望

本文利用數(shù)學表達式的符號、語法和語義特征信息，引入一種IVHFS的數(shù)學表達式檢索結(jié)果排序方法.該方法融合決策分析領(lǐng)域技術(shù)，對表達式進行多屬性描述.提取表達式的子式空間結(jié)構(gòu)屬性、運算符關(guān)聯(lián)屬性以及運算數(shù)關(guān)聯(lián)屬性作為表達式的屬性特征，并且在每個屬性下都又各自增添了不同指標，從而增強屬性描述的多面性和靈活性.最終為滿足使用需求，獲取了全面和詳細的數(shù)學表達式評估信息.

本實驗方法也存在一些不足:1)該實驗主要針對包含式查詢，所以，導致系統(tǒng)無法對其它比如在結(jié)構(gòu)、語義等方面相似的公式進行查詢，因此，具有一定的局限性;2)為了靈活滿足用戶查詢公式的需求，在實驗中可以增設其它文字信息的關(guān)鍵字進行以文字和公式相互融合的查詢，當用戶對公式認識不清時，增加文字信息來引導公式的查詢，增強公式描述的準確性，使得排序結(jié)果更加合理有效.除此之外，還有其它的缺陷，在以后會不斷完善實驗，提高實驗的排序效果.