線性代數式檢索結果的相似度排序方法

(河北大學 計算機科學與技術學院,河北 保定 071002)

0 概述

作為現代數學的一個重要研究課題,線性代數式廣泛應用于各種科技文獻,相對于普通公式和文本,線性代數式的結構更復雜。目前主流的搜索引擎多數是針對文本而設計,且部分針對數學公式設計的檢索系統也不能十分合理地完成線性代數式的搜索,因此,研究并設計具有線性代數式檢索功能的數學公式檢索系統具有重要意義。

目前,國內外針對線性代數式檢索的研究并不多,而針對普通表達式的研究已取得一些成果,包括MathDex[1]、DLMF Search[2]、LeActiveMath[3-4]、EgoMath[5-7]、MathWebSearch[8-9]、Wikimirs[10-11]等。按照實現方法,可將上述成果分為改進文本搜索的數學檢索系統和為數學公式建立專門索引的數學檢索系統,前者不支持數學公式內容識別,而后者支持。隨著網絡數學資源的日漸豐富,用戶進行檢索時往往會返回大量的檢索結果,如何按檢索結果與查詢公式的相似度由高到低將其進行排序,以縮短查詢時間、提升工作效率,是實際應用中面臨的挑戰。

文獻[12]將數學公式用五元組(s,n,r,p,b)表示,利用距離公式計算待查詢式和結果式的五元組距離,得出相似度進而完成排序。文獻[13]提出一種基于結構相似度的數學檢索方法,其將不同形式的數學公式統一成Presentation MathML格式,采用“樹編輯距離”方法計算公式之間的相似度。文獻[14-15]定義“數據類型層級”“查詢覆蓋度”“匹配深度”等特征,利用對查詢表達式和獲取目標表達式的解析樹進行遞歸的相似距離分析,計算其之間的相似度。文獻[16-17]設計并實現數學公式檢索系統MASE和Lattice-based Math Search,前者采用被動攻擊的在線學習分類模型對檢索結果進行排序,后者建立數學概念格,在格中完成數學公式的相關排序。文獻[10]改進TF-IDF(Term Frequency-Inverse Document Frequency)算法,引入節點所處層次評價指標,計算每個節點的頻率和倒排公式頻率,完成相似度排序。文獻[11]改進文獻[10]方法,引入結果表達式中包含的與待查詢式相同的節點數目占待查詢式節點總數的比例,用其作為評價指標,優化排序結果。文獻[18]采用加權算法形成權值分配矩陣,利用快速排序和優化排序對數學公式進行相似度計算。

上述方法為線性代數式檢索結果排序提供了思路。由于線性代數式的結構、語法和語義的復雜性,只有選擇合理的理論及模型,從多視角研究線性代數式的特征,才能完成線性代數式檢索結果的相似度排序。本文將猶豫模糊集理論應用于線性代數式的相似度評價中,提出一種線性代數式檢索結果相似度排序方法。在線性代數式的局部屬性和整體屬性2個方面建立隸屬度函數,應用距離相似度公式計算猶豫模糊集之間的距離,完成待查詢線性代數式與檢索結果式的相似度計算,并最終得到排序結果。

1 線性代數式相似度評價特征

1.1 線性代數式檢索模式

線性代數式種類較多,其變形和計算十分豐富,在設計檢索系統時,應根據用戶的實際需求設計不同的匹配模式。

定義1線性代數式中按照行列規則排列,既相互獨立又互有聯系的子表達式稱為子公式。

定義2Eq為一個m行n列的線性代數查詢式,Eq(i,j)(i=1,2,…,m;j=1,2,…,n)為其子公式,Erqt(t=1,2,…,h)為檢索結果集合中的h個c行d列線性代數式,Erqt(k,l)(k=1,2,…,c;l=1,2,…,d)為其子公式。

線性代數式的檢索功能覆蓋了矩陣、行列式和方程組匹配3種模式,它們均是在子式匹配的基礎上做了相應的改進。由于在匹配算法的設計時考慮到線性代數式的語法和語義變換問題,因此矩陣匹配結果中除包含與待查詢矩陣精確一致,或部分子式包含待查詢矩陣子式的矩陣外,還會包含查詢式的轉置、逆矩陣、增廣矩陣和伴隨矩陣等變換結果。因此,在矩陣檢索結果的相似度評價中,也將查詢式的轉置、逆矩陣、增廣矩陣和伴隨矩陣作為相似度評價的因素。類似地,在行列式匹配中涉及轉置變換和求值運算,而方程組匹配僅限于子式匹配。

子式匹配是將用戶輸入的待查詢式Eq的子式Eq(i,j)和檢索結果集Erqt的子式Erqt(k,l)看作一個獨立的數學公式,按行優先原則遞歸地將Eq(i,j)和Erqt(k,l)進行包含匹配,即要求Eq(i,j)是Erqt(k,l)的一部分或兩者完全相同,當包含匹配成功時,將該Erqt(k,l)所對應的Erqt返回給用戶。子式匹配原理如圖1所示。

圖1 子式匹配原理

1.2 評價流程

對線性代數式進行相似度評價的流程分為3個步驟:特征提取,隸屬度計算,相似度計算。

圖2 線性代數式評價原理

在圖2中,一級屬性為局部屬性{A1,A2,…,Am},二級屬性為整體屬性{Am+1,Am+2,…,An},每個屬性包含一組評價標準,按每個屬性所對應的評價標準進行特征提取,首先提取局部屬性特征,并代入相應的隸屬度函數進行計算,再按相同的原理提取整體屬性特征,形成如圖2所示的局部猶豫模糊集和整體猶豫模糊集,最后根據針對線性代數式變型的廣義猶豫標準距離公式完成公式之間的相似度計算,該公式將在后文中給出詳細定義。基于猶豫模糊集的線性代數式評價流程如圖3所示。

圖3 線性代數式評價流程

1.3 評價屬性

本文從局部和整體2個部分進行線性代數式的相似度評價。綜合考慮多種因素,定義線性代數式的評價屬性如表1所示,其中針對不同的匹配模式,將個別屬性設置為1來表示該屬性值對該匹配模式的屬性評價無影響。

表1 線性代數式評價屬性

定義3calla[a,b]表示a與b的相似度。其中a,b表示代數式。

1.3.1 局部屬性

線性代數式是多個子公式的組合,子公式的結構、數量、位置和相對位置等都影響著線性代數式之間的相似程度。因此,進行線性代數式相似度評價時需考慮如下屬性:

1)結構屬性AF

(1)長度標準indlen

按行優先原則考察Eq(i,j)與每一個以其為子式的Erqt(k,l)所包含的運算數和運算符的數目,兩者的數目越接近,其相似度就越大。

calla[Eq(1,1),Erq1(1,1)]

(1)

(2)層次標準indlev

圖4 線性代數式層次與相似度關系

(3)位置標準indloc

calla[Eq(1,1),Erq1(1,1)]>calla[Eq(1,1),Erq2(2,1)]

(2)

(4)起始位標準indsta

圖5 線性代數式起始位與相似度關系

(5)標志位標準indfla

圖6 線性代數式標志位與相似度關系

2)運算數屬性AO

按行優先原則考察Eq(i,j)與以其為子式的Erqt(k,l)的運算數信息,設Eq(i,j)中包含若干運算數{O1,O2,…,Os1},其中,s1表示Eq(i,j)所包含的運算數個數,考察Om(m=1,2,…,s1)在Erqt(k,l)中出現的次數及重要程度,將其作為一個評價標準indopd。

3)運算符屬性AR

按行優先原則考察Eq(i,j)與以其為子式的Erqt(k,l)的運算符信息,設Eq(i,j)中包含若干運算符{R1,R2,…,Rs2},其中,s2表示Eq(i,j)所包含的運算符個數,考察Rn(n=1,2,…,s2)在Erqt(k,l)中出現的次數及重要程度,將其作為一個評價標準indopr。

1.3.2 整體屬性

線性代數式在整體角度有其獨特的特征,因此,在考察線性代數式間的相似度時應考慮其整體屬性,從而得出更準確的測評結果。

1)矩陣變換屬性AJ

考慮矩陣A的4種變形:轉置變換AT,逆矩陣變換A-1,增廣矩陣變換和伴隨矩陣變換A*。將Eq和Erqt的矩陣變換信息作為評價標準indjuz。考慮到待查詢矩陣與經過上述4種變換后矩陣的相似性,規定相似度排序為:原矩陣>轉置矩陣>增廣矩陣>逆矩陣>伴隨矩陣>普通矩陣。

2)行列式變換屬性AD

根據行列式的性質可知:D=DT,即行列式與其轉置行列式相等,將行列式是否與原查詢式互為轉置作為評價標準indhal。

3)行列式的值屬性AK

行列式可以進行求值運算,依據行列式的性質進行求值運算時,原行列式可能會發生變化,但其值不變,將行列式的值作為評價標準indkey。

4)規模屬性AS

calla(Eq,Erq1)>calla(Eq,Erq2)

(3)

5)相同子表達式數量屬性AN

設Eq中包含若干子表達式{N1,N2,…,Ns3},其中,s3為Eq所包含的子表達式個數,將Erqt中每個子表達式Nd(d=1,2,…,s3)出現的個數及其所占的比例作為一個評價標準indnsu。

1.4 猶豫模糊隸屬度定義及參數設置

1.4.1 猶豫模糊隸屬度定義

定義4長度標準indlen的隸屬度函數為:

findlen[Eq(i,j),Erqt(k,l)]=lb(1+indlen)

(4)

定義5層次標準indlev的隸屬度函數為:

findlev[Eq(i,j),Erqt(k,l)]=eη·indlev

(5)

其中,indlev為子式Eq(i,j)在Erqt(k,l)中所處的層次,η為層次屬性權重系數。

定義6位置標準indloc的隸屬度函數為:

(6)

其中,rmin=min(i,k)表示Eq(i,j)和Erqt(k,l)所處行號中較小值,rmax=max(i,k),表示Eq(i,j)和Erqt(k,l)所處行號中較大值,cmin=min(j,l),表示Eq(i,j)和Erqt(k,l)所處列號中較小值,cmax=max(j,l),表示Eq(i,j)和Erqt(k,l)所處列號中較大值。

定義7起始位標準indsta的隸屬度函數為:

findsta[Eq(i,j),Erqt(k,l)]=e-μindsta

(7)

其中,indsta為子式Eq(i,j)在Erqt(k,l)中所處的水平位置(規定初始位置為0),μ為起始位屬性權重系數。

定義8標志位標準indfla的隸屬度函數如表2所示。本文將標志位信息內部做了特殊處理,為區分各行,規定每行第1個子式的主基線標志位為6i,其中,i=1,2,…,表示行號。每行非第1個子式的主基線標志位為0。

表2 標志位g隸屬度值

定義9運算數標準indopd的隸屬度函數為:

(8)

定義10運算符標準indopr的隸屬度函數為:

(9)

定義11矩陣變換標準indjuz的隸屬度函數如表3所示。

表3 矩陣不同變換形式的隸屬度值

定義12行列式變換標準indhal的隸屬度函數為:

(10)

定義13行列式的值標準indkey的隸屬度函數為:

(11)

定義14規模標準indsiz的隸屬度函數為:

(12)

其中,Rmin=min(m,c)表示Eq和Erqt的行數中較小值,Rmax=max(m,c)表示Eq和Erqt的行數中較大值,Cmin=min(n,d)表示Eq和Erqt的列數中較小值,Cmax=max(n,d)表示Eq和Erqt的列數中較大值。

定義15相同子表達式個數標準indnsu的隸屬度函數為:

findnsu[Eq(i,j),Erqt(k,l)]=

(13)

其中,D=m×n表示Eq包含的子式總數,cntq(i,j)表示Eq(i,j)與Erqt(k,l)完全相同的次數,cntrqt(k,l)表示Erqt的子公式總數。

1.4.2 參數設定

隸屬度函數參數設定說明如下。

層次屬性權重系數η:通過統計數據庫中6 352個表達式的節點總數、層次信息以及處于該層的節點個數,并將處于某層的節點個數歸一化,利用polyfit函數借助MATLAB軟件繪制圖像,最終確定η值為-0.113。

起始位屬性權重系數μ:通過統計數據庫中6 352個表達式的長度信息,找出最小長度、中間長度、最大長度和分布中心長度,統計在[LEN,LEN+10](LEN=最小長度,或中間長度,或最大長度,或分布中心長度)范圍內的表達式個數并進行歸一化處理,將這4類長度與其加10后的長度進行取平均值處理,利用polyfit函數借助MATLAB軟件繪制圖像,最終確定μ值為0.56。

根據統計數據庫中不同g值所對應的表達式個數占表達式總數的比例,以及不同標志位所代表的典型運算的常見程度,進行g隸屬度的取值設定。

綜合考慮用戶的檢索需求及幾種不同矩陣的常見性,進行矩陣不同變換形式的隸屬度取值設定。

1.5 猶豫模糊集及線性代數式相似度計算

文獻[19]提出模糊集概念,之后一些學者又對其進行擴展,相繼提出直覺模糊集、Type2型模糊集、模糊多重集等,但在處理決策問題時其模糊不確定性方面存在缺陷,特別是在專家對某對象的某個屬性進行評價時出現猶豫的情況。對此文獻[20]提出猶豫模糊集的概念,用一個集合的形式給出某一對象屬于模糊集的程度,該方法不再需要專家對屬性值給定一個誤差范圍或幾個可能值的分布,就可以對決策中的不確定性進行有效刻畫,為數學公式檢索結果排序提供理論支撐。此后,區間值猶豫模糊集[21]及其相應的一些關聯度、距離及相似性測度、算子和相應的決策方法相繼被提出[22]。

1.5.1 猶豫模糊集相關概念

定義16設X是一個非空集合,則稱式(14)為猶豫模糊集。

E={|x∈X}

(14)

其中,hE(x)稱為猶豫模糊元素,是元素x對于集合E的幾個可能隸屬度的集合,該元素值在[0,1]區間內分布[20]。

定義17設P和Q分別為非空集合X={x1,x2,…,xn}中的2個猶豫模糊集合,則P和Q的廣義猶豫標準距離表示為:

(15)

定義18P和Q的相似度表示為:

s(P,Q)=1-dghn(P,Q)

(16)

1.5.2 線性代數式相似度計算

線性代數式相似度計算分為3步:局部特征相似度計算,整體特征相似度計算和公式相似度計算。各步驟具體內容如下:

步驟1設Eq(i,j)和Erqt(k,l)分別對應猶豫模糊集合Hfq(i,j)和Hfrqt(k,l),這2個集合所對應的猶豫模糊元素為Pq(i,j)(Aa)和Prqt(k,l)(Aa),其中Aa表示局部評價屬性,且a=1,2,3。根據式(15)得到局部特征猶豫模糊集合的廣義猶豫標準距離,再根據式(16)得出2個猶豫模糊集合的相似度。

s(Hfq(i,j),Hfrqt(k,l))=1-dghn(Hfq(i,j),Hfrqt(k,l))=

(17)

設srqt表示最終局部相似度,若同一個Erqt(k,l)有多個相似度值,就取最大值作為其相似度值。對同一個Erqt的每一個子式的最大相似度求平均值,即為Erqt的最終局部相似度。

(18)

步驟2設Eq和Erqt的整體評價屬性分別對應的猶豫模糊集合為Hfq和Hfrqt,這2個集合所對應的猶豫模糊元素為Pqw(Aw)和Prqwt(Aw),其中,Aw表示整體評價屬性,且w=1,2,3,4,5?？紤]到用戶的實際需求,每個整體評價標準對檢索結果相似度排序的影響程度不同,將式(15)適當變形,得出2個猶豫模糊集的相似度為:

s(Hfq,Hfrqt)=1-dghn(Hfq,Hfrqt)=

(19)

其中,在考慮大量用戶檢索需求的基礎上,經過統計不同整體屬性所代表的典型線性代數式與待查詢式的邏輯相似性,進而進行θi值的設定(對不同匹配模式的相似度評價沒有影響的整體屬性對應的θi值設置為0)。例如:當用戶檢索式為某一矩陣時,用戶更想查詢出原矩陣及其轉置矩陣、增廣矩陣、逆矩陣等?；诖?每種匹配模式的整體評價屬性所對應的θi值如表4所示。

表4 各類匹配模式整體屬性所對應θi值

步驟3將上述2部分相似度取平均值,即得到2個公式的相似度。

(20)

2 線性代數式排序算法

不同匹配模式的排序算法,其原理大致相同,算法步驟如下:

輸入LaTeX形式的線性代數查詢式

輸出LaTeX形式的線性代數結果式排序結果

1)初始化數據表LaForm、SubForm、Whole、NodeInf、OpInf、Rt_end。

2)將待查詢式子式的subid、文件名subnam和字符串substr存入表SubForm中,對其進行解析,將特征存入表NodeInf、OpInf。

3)i=i+1,若i>待查詢線性代數式的子式總數,執行步驟5),否則執行步驟4)。

4)查詢數據庫中SubForm表,若數據庫中表達式子式的字符串含有該查詢式的子式,則對其進行解析,存入表NodeInf、OpInf、Whole,計算局部相似度,存入表NodeInf;否則,算法結束。

5)將待查詢式的Eqid、文件名Eqfnam和字符串Eqstr存入表LaForm,對其進行解析,將特征存入表NodeInf、OpInf、Whole。

6)j=j+1,若j>數據庫中表達式總數,執行步驟8);否則,執行步驟7)。

7)查詢數據庫中NodeInf表,并根據Formid在表達式表FORMULA中找到對應表達式,對其進行解析,并將特征存入表LaForm、SubForm、NodeInf、OpInf,計算整體屬性相似度,存入表Whole。

8)計算線性代數式的相似度并將最終結果寫入表Result_end,并把該表按s_end降序返回給用戶。

假設待查詢線性代數式的子公式總數為m1,數據庫中線性代數公式的總數為n,則數據庫中線性代數公式的子公式總數為m2×n,其中m2為數據庫中線性代數公式子公式個數的平均值。根據實驗數據可知:1≤m1<

表5 檢索結果所對應猶豫模糊集合

表6 結果表達式相似度計算結果

3 實驗結果與分析

采用C#進行編程,結合SQL2013,應用猶豫模糊集理論進行線性代數式檢索及結果排序。由于目前國內外對此方面的研究并不多,相關數據集較少,因此本文選取線性代數課本和網絡上相關文獻的電子文檔,從中提取MathType格式的線性代數表達式并轉換成LaTeX形式,再通過解析程序將其存儲于數據庫中,最終共得到6 352條用于實驗的線性代數式數據集。因為本文系統主要針對線性代數式,所以選擇與數學檢索系統SearchOnMath(http://searchonmath.com/,一個直接查詢數學內容的搜索引擎,查詢結果包含給定數學公式的網頁,并給出其不同的相似性)進行對比,并引入斯皮爾曼秩次相關系數概念用以檢驗檢索結果的合理性,斯皮爾曼秩次相關系數定義如下:

定義19斯皮爾曼秩次相關系數[24]是反映2組變量之間聯系密切程度的統計分析指標,適用于2組無序數列相關性大小的計算,其值越大,表示相關性越高。斯皮爾曼秩次相關系數計算公式為:

(21)

其中,di表示2組無序序列按遞增或遞減排序后,每個數列元素位置變化的差值,n表示2個序列的長度。

表7 待查詢線性代數式

表8 排序結果對比

讓一組專家對表7中每個查詢表達式的檢索結果集合進行人工排序,將該排序結果作為評價標準,利用斯皮爾曼秩次相關系數,分別計算本文方法和SearchOnMath方法的排序結果與人工排序結果的相關性,得到如圖7所示的相關性比較結果,其中,斯皮爾曼秩次相關系數越高,說明排序結果越符合用戶需求。

圖7 2種方法與人工排序結果的相關性比較

由圖7可以看出,本文方法的排序結果與人工排序結果更接近,因此,本文方法更能滿足用戶的查詢需求。

4 結束語

針對線性代數式的檢索及結果排序,本文從多角度分析并歸納線性代數式的特征,利用猶豫模糊集的相關理論建立相應的隸屬度函數,對抽象的公式特征進行數量化,從而實現線性代數式的相似度評價,完成線性代數式檢索結果的合理排序。對比實驗驗證了該方法在線性代數式相似度評價上的合理性和有效性。但本文實驗在線性代數式的特征選取上還不夠全面,評價函數涉及的參數選擇還需優化,下一步將對此進行研究。

[1] MINER R,MUNAVALLI R.An approach to mathematical search through query formulation and data normaliza-tion[C]//Proceedings of the 14th Symposium on Towards Mechanized Mathematical Assistants.Berlin,Germany:Springer,2007:342-355.

[2] MILLER B,YOUSSEF A.Technical aspects of the digital library of mathematical functions[J].Annals of Mathematics and Artificial Intelligence,2003,38(1):121-136.

[3] LIBBRECHT P,MELIS E.Semantic search in leactive-math[EB/OL].[2017-09-05].http://www.hoplahup.net/copy_left/Libbrecht-etal-Semant ic-Search-WebALT-06.pdf.

[4] LIBBRECHT P,MELIS E.Methods to access and retrieve mathematical content in active math[C]//Proceedings of 2006 Mathematical Software-ICMS.Berlin,Germany:Springer,2006:331-342.

[5] MISUTKA J,GALAMBOS L.Mathematical extension of full text search engine indexer[C]//Proceedings of the 3rd International Conference on Information and Communication Technologies.Washington D.C.,USA:IEEE Press,2008:1-6.

[7] MISUTKA J,GALAMBOS L.System description:EgoMath2 as a tool for mathematical searching on Wikipedia.org[C]//Proceedings of the 18th Calculemus and 10th International Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2011:307-309.

[8] KOHLHASE M,SUCAN I.A search engine for mathematical formulae[C]//Proceedings of the 8th International Conference on Artificial Intelligence and Symbolic Computation.Berlin,Germany:Springer,2006:241-253.

[9] KOHLHASE M,ANCA S,JUCOVSCHI C,et al.MathWebSearch 0.4,a semantic search engine for mathematics[EB/OL].[2017-09-15].https://www.researchgate.net/publication/216797208_MathWebSearch_04_A_Semantic_Search_Engine_for_Mathematics.

[10] HU X,GAO L C,LIN X Y,et al.WikiMirs:a mathe-matical information retrieval system for Wikipedia[C]//Proceedings of the 13th ACM/IEEE-CS Joint Conference on Digital Libraries.New York,USA:ACM Press,2013:11-20.

[11] LIN X Y,GAO L C,HU X,et al.A mathematics retrieval system for formulae in layout presentations[C]//Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,USA:ACM Press,2014:697-706.

[12] SCHELLENBERG T,YUAN B,ZANIBBI R.Layout-based substitution tree indexing and retrieval for mathematical expressions[J].Document Recognition and Retrieval XIX,2012,8297(2):263-271.

[13] KAMALI S,TOMPA F W.Structural similarity search for mathematics retrieval[C]//Proceedings of 2013 Inter-national Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2013:246-262.

[14] ZHANG Q,YOUSSEF A.An approach to math-similarity search[C]//Proceedings of 2014 International Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2014:404-418.

[15] 田學東,張凱歌,周 南,等.一種數學表達式檢索結果相關排序算法[J].計算機工程,2017,43(3):204-212.

[16] NGUYEN T T,CHANG K,HUI S C.A math-aware search engine for math question answering system[C]//Proceedings of the 21st ACM International Conference on Information and knowledge Management.New York,USA:ACM Press,2012:724-733.

[17] NGUYEN T T,HUI S C,CHANG K.A lattice-based approach for mathematical search using formal concept analysis[J].Expert Systems with Applications,2012,39(5):5820-5828.

[18] 馬惠娟.數學搜索中索引模型研究[D].蘭州:蘭州大學,2013.

[19] ZADEH L A.Fuzzy sets[J].Information and Control,1965,8(3):338-353.

[20] TORRA V.Hesitant fuzzy sets[J].International Journal of Intelligent Systems,2010,25(6):529-539.

[21] 陳樹偉,蔡麗娜.區間值猶豫模糊集[J].模糊系統與數學,2013,27(6):38-44.

[22] 蔡麗娜.區間值猶豫模糊集及其在決策中的應用研究[D].鄭州:鄭州大學,2013.

[23] XU Z S,XIA M M.Distant and similarity measures for hesitant fuzzy sets[J].Information Sciences,2011,181(11):2128-2138.

[24] KENDALL M,GIBBONS J D.Rank correlation methods[M].New York,USA:Oxford University Press,1990.