基于側(cè)重點(diǎn)聚類的數(shù)學(xué)表達(dá)式相似度計(jì)算方法

楊 芳，尹 曦，司建輝，劉宏媛，汪 雪

河北大學(xué) 網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院，河北 保定 071002

數(shù)學(xué)表達(dá)式是科技文檔中不可缺少的表現(xiàn)形式，對科技文檔的檢索有著重要的參考價(jià)值。隨著科技文檔數(shù)量的指數(shù)級增長和對科技文檔檢索要求的提高，對數(shù)學(xué)表達(dá)式的相似度計(jì)算也提出了更高的要求[1-2]。數(shù)學(xué)表達(dá)式具有豐富的語義和復(fù)雜的結(jié)構(gòu)，目前對數(shù)學(xué)表達(dá)式相似度計(jì)算的方法主要從表達(dá)式的內(nèi)容和結(jié)構(gòu)匹配兩個(gè)方面展開。

基于內(nèi)容的相似度計(jì)算是較早提出的方法，MathDex[3]、ZHANG 等[4]、XU 等[5]均是根據(jù)數(shù)學(xué)表達(dá)式的內(nèi)容為表達(dá)式分配權(quán)重，計(jì)算相似度。同時(shí)表達(dá)式的結(jié)構(gòu)相似度計(jì)算也受到了重視，樹形結(jié)構(gòu)是常用的結(jié)構(gòu)表示方法。文獻(xiàn)[6-8]在樹形結(jié)構(gòu)的基礎(chǔ)上利用關(guān)鍵詞、關(guān)鍵字?jǐn)?shù)目比例、運(yùn)算符等信息構(gòu)建索引得到查詢表達(dá)式的相似表達(dá)式集合。ZHONG等[9]使用倒排索引和秩的動(dòng)態(tài)剪枝算法來提高表達(dá)式匹配效率，實(shí)現(xiàn)更快的表達(dá)式子結(jié)構(gòu)匹配。

數(shù)學(xué)表達(dá)式的內(nèi)容與結(jié)構(gòu)相結(jié)合的相似度計(jì)算方法也受到了廣泛關(guān)注[10-11]。SHUNSUKE 等人[12]提出了一種基于散列的近似計(jì)算算法，采用Subtree Hash、Modular Trick、SIGURE Hash 三種哈希算法分別對應(yīng)表達(dá)式的變量名稱、功能結(jié)構(gòu)和α-等價(jià)三種測度來計(jì)算表達(dá)式的相似度，在考慮到表達(dá)式結(jié)構(gòu)的同時(shí)可以捕捉到數(shù)學(xué)表達(dá)式不同特征的語義相似性，該方法所用的計(jì)算時(shí)間較短，且對表達(dá)式中各個(gè)元素考慮周全，得到的相似度計(jì)算結(jié)果準(zhǔn)確度較高。

側(cè)重點(diǎn)是一個(gè)較為主觀的概念且數(shù)學(xué)表達(dá)式數(shù)目龐大，很難人為地對其進(jìn)行歸納，本文使用K-means++算法[14]對表達(dá)式的側(cè)重點(diǎn)進(jìn)行聚類歸納。K-means++聚類算法是K-means聚類算法[15]改進(jìn)算法之一，該算法在計(jì)算機(jī)領(lǐng)域應(yīng)用廣泛，在算法模型的改進(jìn)、文本分類等[16-17]方面都起到重要的作用。其原理簡單，容易實(shí)現(xiàn)，收斂速度快，簇與簇之間區(qū)別明顯，將K-means++聚類算法用于數(shù)學(xué)表達(dá)式相似度計(jì)算中，可以很好地將側(cè)重點(diǎn)不同的表達(dá)式分為不同的簇，為調(diào)節(jié)相似度計(jì)算中參數(shù)提供依據(jù)。再使用遺傳算法對參數(shù)進(jìn)行優(yōu)化，使得相似度計(jì)算結(jié)果更加準(zhǔn)確。

本文使用K-means++聚類算法，將數(shù)學(xué)表達(dá)式聚類到不同的側(cè)重點(diǎn)簇中，充分體現(xiàn)數(shù)學(xué)表達(dá)式主要框架結(jié)構(gòu)對相似度計(jì)算的影響，以獲得更加準(zhǔn)確的匹配結(jié)果。將表達(dá)式所屬側(cè)重點(diǎn)簇作為依據(jù)，使用遺傳算法對相似度計(jì)算中相關(guān)參數(shù)進(jìn)行調(diào)節(jié)，提高了方法的靈活性，使其更好地適用于不同側(cè)重點(diǎn)表達(dá)式的相似度計(jì)算。該方法提高了數(shù)學(xué)表達(dá)式相似度計(jì)算的準(zhǔn)確性，使其更好地服務(wù)于信息檢索，使用戶得到的檢索結(jié)果更加理想。

1 數(shù)學(xué)表達(dá)式相似度計(jì)算方法

1.1 數(shù)學(xué)表達(dá)式相似度計(jì)算總體思路

基于側(cè)重點(diǎn)聚類的數(shù)學(xué)表達(dá)式相似度計(jì)算方法總體流程分兩部分，如圖1所示。聚類部分使用K-means++聚類算法對數(shù)據(jù)集進(jìn)行聚類，根據(jù)表達(dá)式側(cè)重點(diǎn)不同將其分為不同的側(cè)重點(diǎn)簇，并且確定各個(gè)側(cè)重點(diǎn)簇的聚類中心。參數(shù)調(diào)節(jié)部分，首先使用Jaccard 相似度計(jì)算方法[18]，計(jì)算表達(dá)式間相似度，獲取初始結(jié)果列表。接著根據(jù)聚類結(jié)果對查詢表達(dá)式和結(jié)果列表中表達(dá)式的所屬簇進(jìn)行判定，并計(jì)算結(jié)果列表中與查詢表達(dá)式所屬簇相同的表達(dá)式所占比例值。最后以該比例值作為適應(yīng)度函數(shù)，使用遺傳算法[19-20]調(diào)節(jié)相似度計(jì)算的參數(shù)，得到最優(yōu)相似度結(jié)果列表。

1.2 相似度計(jì)算方法

本文以數(shù)學(xué)表達(dá)式的MathML 格式為基礎(chǔ)，使用XML 解析器將表達(dá)式處理為表達(dá)式樹用于相似度計(jì)算。表達(dá)式樹的每一個(gè)節(jié)點(diǎn)都存儲(chǔ)了表達(dá)式的一個(gè)運(yùn)算數(shù)或運(yùn)算符元素，同時(shí)對節(jié)點(diǎn)中的元素的類別和每個(gè)節(jié)點(diǎn)的所在層次、所在層次中的排序等位置信息都有所標(biāo)記。

圖1 數(shù)學(xué)表達(dá)式相似度計(jì)算總體流程圖

使用Subtree Hash、Modular Trick、SIGURE Hash三種哈希算法分別對表達(dá)式樹進(jìn)行初步處理，計(jì)算公式如（1）～（4）所示：

Subtree Hash：

Modular Trick：

其中p、b、s滿足：

SIGURE Hash：

其中，l表示公式樹的層數(shù)，祖先節(jié)點(diǎn)為0 層，葉子節(jié)點(diǎn)為第l-1 層；n為該節(jié)點(diǎn)孩子節(jié)點(diǎn)個(gè)數(shù)，i為節(jié)點(diǎn)所在層次的節(jié)點(diǎn)個(gè)數(shù)；s表示子樹可以散列到期望的深度，1 ＜s≤l；xli表示第l層的第i個(gè)節(jié)點(diǎn)。hash(xli)、hash()分別表示第l層的第i個(gè)節(jié)點(diǎn)在數(shù)據(jù)字典中對應(yīng)的哈希值和其經(jīng)過計(jì)算后得到的哈希值。hash()表示計(jì)算后根節(jié)點(diǎn)的哈希值，即為該哈希算法對表達(dá)式處理的最終值，該值由葉子節(jié)點(diǎn)自底向上計(jì)算而來，葉子節(jié)點(diǎn)的hash(x)值和hash(x′)值相同。

p、b為預(yù)設(shè)置參數(shù)，二者對哈希計(jì)算結(jié)果都有著直接影響。其中，參數(shù)b用于捕捉數(shù)學(xué)表達(dá)式中結(jié)構(gòu)或者模式的語義，僅對于Modular Trick有影響，根據(jù)公式（3）可知其值可由p決定；參數(shù)p涉及到的運(yùn)算主要為求余運(yùn)算，其取值范圍為1 ＜p≤H,H為公式（1）與公式（2）中被除數(shù)的較小值，參數(shù)p的確定是表達(dá)式相似度計(jì)算的關(guān)鍵。

最后通過Jaccard算法初步計(jì)算出兩個(gè)公式間的相似度J(M1,M2)：

其中M1、M2分別為參與相似度計(jì)算表達(dá)式的Subtree Hash、Modular Trick、SIGURE Hash三種哈希計(jì)算得到的最終哈希值集合。

1.3 基于K-means++聚類算法的側(cè)重點(diǎn)簇判定

表達(dá)式側(cè)重點(diǎn)簇的判定是參數(shù)調(diào)節(jié)的依據(jù)，為了解決側(cè)重點(diǎn)概念主觀性強(qiáng)、難以人為歸納的問題，對表達(dá)式元素的映射規(guī)則進(jìn)行定義，使用K-means++聚類算法對表達(dá)式的側(cè)重點(diǎn)簇進(jìn)行判定。

本文在K-means++聚類計(jì)算時(shí)舍棄了存儲(chǔ)運(yùn)算數(shù)的葉子節(jié)點(diǎn)，層次遍歷標(biāo)記樹中的非葉子節(jié)點(diǎn)。表達(dá)式之間距離D(X,Y)如公式（6）所示：

其中，xi、yi分別為X、Y兩棵表達(dá)式樹的非葉子節(jié)點(diǎn)的映射值，i為表達(dá)式樹非葉子節(jié)點(diǎn)個(gè)數(shù)，取兩棵表達(dá)式樹中的非葉子節(jié)點(diǎn)個(gè)數(shù)較大的值。

表達(dá)式樹中節(jié)點(diǎn)元素的映射規(guī)則為：

（1）子節(jié)點(diǎn)數(shù)目不同的節(jié)點(diǎn)映射為不同值。

（2）若子節(jié)點(diǎn)數(shù)目相同，根據(jù)子節(jié)點(diǎn)順序是否可調(diào)換映射為不同值。

以圖2中（a）、（b）、（c）、（d）四棵表達(dá)式樹為例：表達(dá)式樹（d）根節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目與前三個(gè)表達(dá)式樹根節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目不同；表達(dá)式樹（c）與前兩個(gè)表達(dá)式樹的子節(jié)點(diǎn)數(shù)目相同，但其兩個(gè)子節(jié)點(diǎn)順序不可調(diào)換而（a）、（b）的子節(jié)點(diǎn)順序是可以調(diào)換的。則在聚類計(jì)算中將+、×都映射為α，÷、∑分別映射為β、γ。

圖2 表達(dá)式樹

對一個(gè)數(shù)學(xué)表達(dá)式樹節(jié)點(diǎn)映射后，數(shù)學(xué)表達(dá)式的側(cè)重點(diǎn)使用K-means++聚類計(jì)算進(jìn)行歸納。聚類過程如下所示：

（1）從數(shù)據(jù)集中隨機(jī)選擇一個(gè)樣本表達(dá)式作為第一個(gè)聚類中心A1。

（2）計(jì)算數(shù)據(jù)集中每一個(gè)樣本表達(dá)式與當(dāng)前已有聚類中心之間的最短距離，用minD(X)表示。

（4）重復(fù)步驟（3）直至選擇出所有的初始聚類中心。

（5）計(jì)算每個(gè)樣本點(diǎn)到各個(gè)初始聚類中心的距離，將其歸納為與其距離最近的聚類中心簇中，進(jìn)行迭代。

（6）迭代過程中，使用均值法更新各個(gè)簇的聚類中心，當(dāng)聚類中心變化趨近于穩(wěn)定狀態(tài)時(shí)，迭代結(jié)束，聚類完成。

通過計(jì)算表達(dá)式到每個(gè)聚類中心的距離，以距離最近的聚類中心的所屬簇作為表達(dá)式的側(cè)重點(diǎn)簇，完成對表達(dá)式側(cè)重點(diǎn)簇的判定。

1.4 基于遺傳算法的參數(shù)調(diào)節(jié)

不同的參數(shù)p進(jìn)行相似度計(jì)算得到不同的結(jié)果列表，參數(shù)p的值決定了結(jié)果列表中與查詢表達(dá)式所屬簇相同的表達(dá)式的比例，而該比例決定了此時(shí)的參數(shù)p是否為最優(yōu)解。

本文使用遺傳算法對表達(dá)式相似度計(jì)算方法中的參數(shù)p進(jìn)行調(diào)節(jié)，確定其范圍內(nèi)的最優(yōu)取值，使得到的計(jì)算結(jié)果中表達(dá)式與查詢表達(dá)式所屬簇一致性最高。

將參數(shù)p在其范圍內(nèi)的可選值作為染色體，這些染色體隨機(jī)組成的M個(gè)種群P(0)作為初始化種群。使用結(jié)果列表中表達(dá)式與查詢表達(dá)式側(cè)重點(diǎn)簇一致的比例作為適應(yīng)度函數(shù)，評價(jià)染色體的適應(yīng)度高低，適應(yīng)度函數(shù)設(shè)置為公式（7）：

其中，f為染色體適應(yīng)度值，y為結(jié)果列表中與查詢表達(dá)式類型一致的表達(dá)式個(gè)數(shù)，Y為結(jié)果列表中表達(dá)式個(gè)數(shù)（本文取前100），二者比例越高染色體適應(yīng)度越高。在對染色體適應(yīng)度進(jìn)行評價(jià)后，對其進(jìn)行選擇、交叉、變異處理。選擇的目的是將適應(yīng)度高的個(gè)體直接遺傳到下一代，使用比例選擇方法對個(gè)體進(jìn)行選擇，即個(gè)體被選中的概率Pi與其適應(yīng)度成正比，如公式（8）所示。N為群體中個(gè)體數(shù)量，fi為個(gè)體的適應(yīng)度。

表1 提取表達(dá)式及其相關(guān)信息示例

采用自適應(yīng)方法對交叉概率Pc和變異概率Pm進(jìn)行計(jì)算，計(jì)算公式分別如公式（9）和公式（10）所示：

其中，fmax為種群中的最大適應(yīng)值；favg為種群平均適應(yīng)值；f′、f″表示將要交叉或變異的兩個(gè)染色體中較大的適應(yīng)度值；k1、k2、k3、k4為常數(shù)，本文中k1、k3取值設(shè)置為0.5，k2、k4取值設(shè)置為0.97[21]。

本文設(shè)置算法最大迭代次數(shù)為500，當(dāng)在迭代次數(shù)內(nèi)最優(yōu)個(gè)體適應(yīng)度達(dá)到70%時(shí)或到達(dá)最大迭代次數(shù)時(shí)，算法終止。得到最優(yōu)的參數(shù)p，從而輸出該參數(shù)下的相似度計(jì)算結(jié)果列表。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)設(shè)備與數(shù)據(jù)集

實(shí)驗(yàn)主要開發(fā)工具為Visual Studio 2017，編程語言為 C#。實(shí)驗(yàn)環(huán)境為：CPU Intel?CoreTMi5-4570，3.20 GHz，內(nèi)存8 GB，系統(tǒng)環(huán)境為Microsoft Windows10。

本文實(shí)驗(yàn)數(shù)據(jù)集為NTCIR-12-MathIR-Wikipedia-Corpus，共采集31 401篇文檔。對數(shù)據(jù)集文檔進(jìn)行預(yù)處理，數(shù)據(jù)集中表達(dá)式的表現(xiàn)形式有兩種分別為：MathMLPresentation、MathML-Content，提取其中Content部分用于本實(shí)驗(yàn)，共提取373 615個(gè)數(shù)學(xué)表達(dá)式，提取表達(dá)式示例如表1所示。

2.2 數(shù)學(xué)表達(dá)式聚類結(jié)果

在基于K-means++聚類算法對表達(dá)式側(cè)重點(diǎn)簇的歸納中，通過不斷進(jìn)行實(shí)驗(yàn)和對結(jié)果的分析，當(dāng)K值為9時(shí)，簇間距離適中，各個(gè)側(cè)重點(diǎn)簇間區(qū)別較為明顯，聚類效果最佳，表達(dá)式聚類結(jié)果數(shù)據(jù)如表2所示。

表2 聚類結(jié)果數(shù)據(jù)表

2.3 對比實(shí)驗(yàn)及數(shù)據(jù)分析

本文與文獻(xiàn)[12]的方法進(jìn)行對比實(shí)驗(yàn)，以公式（11）為例，從相似度計(jì)算結(jié)果、相似度計(jì)算性能、響應(yīng)時(shí)間三個(gè)方面進(jìn)行對比分析。

2.3.1 相似度評價(jià)指標(biāo)

本文使用F1-Score 對相似度計(jì)算效果進(jìn)行評估。F1-Score是精確率和召回率的調(diào)和平均數(shù)，如公式（12）～（14）所示，其中pr為平均精確率，re為平均召回率，T(i)為相似度結(jié)果列表中表達(dá)式，R(i)為專家標(biāo)記認(rèn)證符合查詢表達(dá)式相似度的表達(dá)式。F1 的取值范圍為[0，1]，其值越接近1說明形似度計(jì)算效果越好。

表3 相似度計(jì)算Top-5結(jié)果列表

2.3.2 相似度計(jì)算結(jié)果

本實(shí)驗(yàn)與文獻(xiàn)[12]的相似度計(jì)算結(jié)果TOP-5列表如表3所示，本文方法中Top-2表達(dá)式與查詢表達(dá)式相同，表現(xiàn)形式不同，排名靠前，但并未出現(xiàn)在文獻(xiàn)[12]的前5個(gè)結(jié)果表達(dá)式中。可以看出本文方法可以使得表現(xiàn)形式不同的相同表達(dá)式排名靠前，得到更加精確的相似度計(jì)算結(jié)果。

2.3.3 相似度計(jì)算性能分析

表4為兩種實(shí)驗(yàn)方法對5組表達(dá)式進(jìn)行計(jì)算得到的相似度結(jié)果列表的F1-Score的數(shù)據(jù)對比。文獻(xiàn)[12]的平均F1-Score為0.76，而本文的平均F1-Score為0.84，相比于對比實(shí)驗(yàn)提高了0.08，說明本文方法通過對表達(dá)式側(cè)重點(diǎn)的聚類，判定表達(dá)式的側(cè)重點(diǎn)簇有效地改善了相似度計(jì)算結(jié)果。

表4 F1-Score對比表

2.3.4 相似度計(jì)算響應(yīng)時(shí)間

本文與文獻(xiàn)[12]響應(yīng)時(shí)間對比如圖3所示。

圖3 響應(yīng)時(shí)間對比

經(jīng)過對比可以看出，雖然本文的響應(yīng)時(shí)間較慢，但二者的響應(yīng)時(shí)間差別并不大，可以在合理的時(shí)間內(nèi)得到所需表達(dá)式相似度計(jì)算結(jié)果。本文犧牲可接受范圍內(nèi)的時(shí)間，對表達(dá)式側(cè)重點(diǎn)聚類以及對側(cè)重點(diǎn)簇判定，對相似度計(jì)算中參數(shù)進(jìn)行調(diào)節(jié)，使得與查詢表達(dá)式一致性更高的結(jié)果表達(dá)式排名靠前，方便用戶得到更加理想的結(jié)果表達(dá)式。

3 結(jié)語

本文從表達(dá)式的側(cè)重點(diǎn)出發(fā)，提出了一種基于側(cè)重點(diǎn)聚類的數(shù)學(xué)表達(dá)式相似度計(jì)算方法。對數(shù)據(jù)集中表達(dá)式進(jìn)行側(cè)重點(diǎn)聚類，通過計(jì)算相似度結(jié)果列表與查詢表達(dá)式所屬相同簇的比例，得到參數(shù)調(diào)節(jié)的依據(jù)，優(yōu)化調(diào)節(jié)參數(shù)，得到最終的相似度結(jié)果列表。該方法體現(xiàn)了表達(dá)式結(jié)構(gòu)框架對相似度計(jì)算的影響，增加了數(shù)學(xué)表達(dá)式相似度計(jì)算的靈活性。通過多次實(shí)驗(yàn)以及對實(shí)驗(yàn)結(jié)果的分析，確定合適的K值和遺傳算法中的相關(guān)參數(shù)值，從實(shí)驗(yàn)結(jié)果分析可以得到，平均F1-Score 達(dá)到了0.84，較對比實(shí)驗(yàn)提高了0.08，表明本文的相似度計(jì)算方法相似度計(jì)算性能好，提高了信息檢索的準(zhǔn)確性。但本文只針對于數(shù)學(xué)表達(dá)式的MathML格式，并未考慮到其他格式下表達(dá)式的相關(guān)計(jì)算情況；且本文進(jìn)行聚類的數(shù)據(jù)集與相似度計(jì)算使用數(shù)據(jù)集為同一數(shù)據(jù)集，較為單一。進(jìn)一步會(huì)嘗試對不同格式數(shù)學(xué)表達(dá)式進(jìn)行應(yīng)用，考慮不同數(shù)據(jù)集中的實(shí)驗(yàn)效果，對算法進(jìn)行改進(jìn)。