[發明專利]一種適合于中文網頁文檔的后綴樹聚類方法

在審

• 申請號: 201210490899.0
• 申請日: 2012-11-27
• 公開（公告）號: CN103838783A
• 公開（公告）日: 2014-06-04
• 發明（設計）人: 汲業
• 申請（專利權）人: 大連靈動科技發展有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 大連東方專利代理有限責任公司 21212
• 代理人: 曲永祚

1.一種適合于中文網頁文檔的后綴樹聚類方法，其特征在于：包括以下步驟：

A、文檔預處理

搜索引擎返回的結果列表包含文檔的URL、標題和摘要信息，其中URL是用來定位文檔的，因此將文檔的標題和摘要作為聚類算法的輸入；數據預處理階段主要分為兩個部分，HTML標簽及特殊符號的過濾和停用詞的去除；

A1、過濾HTML標簽及特殊符號

HTML標簽以及特殊符號的過濾是預處理的第一個步驟，主要負責將文檔中沒有用的或者干擾文檔信息的非漢語元素去除掉，包括HTML標簽，如<br>、<p>、<td>等、特殊字符，如@、#、%等、標點符號，去除包括“，”、“？”、“！”、“；”等符號、數字等字符；

A2、去除停用詞

消除停用詞需要定義并維護一個中文停用詞表，使在后綴樹構建過程中出現在停用詞表中的詞語全部被剔除，用以改善聚類結果的質量；

B、后綴樹構建

假設為長度為m的字符串S生成一棵后綴樹，首先要為樹添加一條表示后綴S[1,m]的邊，然后連續遞歸地為樹添加表示后綴S[i,m]的邊，其中i從2到m；

設Ni為中間后綴樹，對S[i,m]進行后綴樹表示；樹N1包含有一條單一的邊和一個葉子結點，葉子結點用1標識，邊用S[1,m]標識；樹Ni+1的構造基于樹Ni：

在Ni中，找到從根結點開始的、并且標識能夠匹配S[i+1,m]的前綴的最長路經；這條路徑的查找方法如下：不斷的將S[i+1,m]與從根結點開始的路徑上的標識比較和匹配，直到沒有更多的匹配時就得到了最長的路徑；

如果沒有找到與S[i+1,m]的前綴相匹配的路徑，則創建一條從根節點到新葉節點i+1的邊，用來標識后綴S[i+1,m]；

否則，當找到最長的路徑時，存在兩種狀態：有可能匹配的位置在一個結點上，設為x，也可能匹配的位置在一條邊的中間，設這條邊為(u,v)；

如果是在一條邊的中間，此時需要先將邊(u,v)折為兩段，在折斷位置插入新的結點x，折斷的位置就是和S[i+1,m]的前綴比較時，匹配的最后一個詞的下一個位置；

在兩種狀態下，都需要創建一條新邊(x,i+1)，其中結點i+1是一個新的標識為i+1的葉子，并且用S[i+1,m]的不匹配部分來表示這條邊；

C、短語類識別

為每個短語類分配一個分值，然后選擇分值高的作進一步分析；包含短語Bp的短語類B的分值Score(B)可以由下面的公式得到：

Score(B)=|B|f(|B_p|)∑TF-IDF(w_i)

其中，|B|是短語類B中的文檔數目，|Bp|是Bp的長度；當短語中的字數小于7時f函數是線性的，而大于7時則是個常數，w_i是Bp中的詞，TF-IDF(w_i)是Bp中每個詞的權值；TF-IDF是IR領域一個常用的為詞賦權重的方法，其基本原理是：在一篇文檔中出現頻率越高的詞越能代表這篇文檔的主題，而出現頻率越低的詞越能區分不同的文檔，其計算公式如下：

TF-IDF(wi)=(1+log(TF(wi))).log(1+NDF(wi))]]>

其中，TF(w_i)表示短語類代表的文檔子集中詞w_i的出現次數，N是文檔子集中的文檔數目，DF(w_i)是出現詞w_i的文檔數目；

D、短語類合并

文檔集中有可能包含一個以上的相同短語，因此，不同短語類代表的文檔集合可能大部分重疊甚至完全相同，需要從文檔集重合度方面進行短語類合并；另外，還從短語類本身的語義層面考慮合并具有相同語義的短語類，目的是避免在最后的聚類結果中出現語義相同的類別，提高聚類結果的質量；

D1、考慮文檔集重疊度

使用二進制的方法計算兩個短語類之間的相似度，按分值由高到低的順序，依次計算每個短語類和其它所有短語類之間的相似度；計算方法如下：給定兩個短語類Am和An，如果|Am∩An|/|Am|>k并且|Am∩An|/|An|>k，則Am和An的相似度為1，否則為0，其中k是一個在0和1之間的常數，通常取0.5，|Am∩An|表示Am和An所代表的文檔集中的相同文檔數，|Am|表示Am所代表的文檔集中的文檔數；然后，將相似度值為1的短語類合并；合并后的類包含所有短語類對應的文檔集合，合并類的分值等于其所包含的短語類的分值總和；計算出短語類的相似度后，對于值為1的短語類還應判斷它們之間是否存在依附關系，然后再決定合并與否；

D2、考慮短語類語義

借助詞典對同義短語進行判斷，計算兩個短語類Am和An語義相似度的公式如下：

Similarity(Am,An)=KN(Am,An)+SN(Am,An)Max(kn(Am),kn(An))]]>

其中，kn(.)表示對應的短語類的字數，KN(Am,An)表示短語類Am和An中相同詞的長度，SN(Am,An)表示Am和An中同義詞的長度；同樣需要為相似度值定義一個閾值k，計算結果大于k的兩個短語類被認為是具有相同語義的短語類，將被合并成一個類別。