[發明專利]一種搜索引擎中基于類中心壓縮變換的文本聚類方法

有效

• 申請號: 201210447277.X
• 申請日: 2012-11-09
• 公開（公告）號: CN102955857A
• 公開（公告）日: 2013-03-06
• 發明（設計）人: 歐陽元新;謝舒翼;劉文琦;熊璋
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 楊學明;顧煒

1.一種搜索引擎中基于類中心壓縮變換的文本聚類方法，其特征在于：該方法包括以下步驟：

步驟1、對聚類文本集中的每一個文本進行分詞；

步驟2、去除停用詞，過濾影響因子較小的詞；

步驟3、計算每個文本中每個詞出現的次數tf；

步驟4、計算詞語的反文本頻率idf；

步驟5、挖掘同義詞組；

步驟6、挖掘共現高頻詞組，即同時出現在多個不同文本中的詞組對；

步驟7、根據同義詞組和高頻共現詞組，產生原始的類中心，每個類中心由一系列高頻詞匯組成，統計高頻詞匯的tf和idf，標記高頻詞匯所屬的類中心；

步驟8、計算每個文本的內容長度，提取文章的標題，對標題進行分詞；如果沒有標題，則標題title設為空；提取段首詞語與段尾詞匯并加以標記以便后面的加權計算；

步驟9、計算任意兩個文本之間的相似度，標題或內容中有相同或同義的詞語時增加權重，段首詞語與段尾詞匯分別賦予不同的權重，計算公式如下：pureFileSim_(i，j)＝(contentSimilarity_(i，j)+titleSimilarity_(i，j))/(log(fileLength_i*fileLength_j))；

contentSimilarity(i,j)=Σx,y(log(fileKeywodTf(i,x))+1)*fileKeywodIdf(i,x)*∂+(log(fileKeywodTf(j,y))+1)*fileKeywodIdf(j,y)*∂;]]>

titleSimilarity(i,j)=Σx,y(fileTitleWordTf(i,x)*fileTitleWordIdf(i,x))*∂+(fileTitleWordTf(j,y)*fileTitleWordIdf(j,y))*∂;]]>

式中：pureFileSim_(i,j)：文本i與文本j的純相似度；

contentSimilarity_(i,j)：文本i與文本j的內容相似度；

titleSimilarity_(i,j)：文本i與文本j的標題相似度；

fileKeywordTf_(x，i)：文本i中關鍵字x的tf；

fileKeywordIdf_(x，i)：文本i中關鍵字x的idf；

fileTitleWordTf_(j,y)：類中心j關鍵詞y的tf；

fileTitleWordIdf_(j,y)：類中心j關鍵詞y的idf；

fileLength_i：文本i的內容長度；

步驟10、隨機化文本的輸入順序：根據原始聚類中心對聚類文本集進行初始聚類，其算法如下：對每一篇文本，計算它與所有聚類中心的相似度，選擇相似度最大的一個聚類中心id作為這個文本所屬的類；文本i與類中心j的相似度計算公式如下：

fileSim(i,j)=(ΣfileKeyword(i,x)∈centerj(log(fileKeywordIf(x,i))+1)*fileKeywordIdf(x,i)]]>

+ΣfileTitleWord(i,x)∈centerj(log(centerKeywordTf(j,y))+1)*(centerKeywordIdf(j,y))/fileContentLengthi;]]>

式中：

fileKeywordTf_(x，i)：文本i中關鍵字x的tf；

fileKeywordIdf_(x，i)：文本i中關鍵字x的idf；

centerKeywordTf_(j，y)：類中心j關鍵詞y的tf；

centerKeywordIdf_(j，y)：類中心j關鍵詞y的idf；

fileContentLength_i：文本i的內容長度；

同時計算與每個詞匯最接近的類中心，記錄下詞匯的wordid；

計算最相似的類中心比第二相似的類中心多出的百分比，記錄到文本的diffRatio中；

步驟11、剔除diffRatio小于10%的文本，在剩下的文本中對屬于同一個類的文本集進行關鍵詞提取和統計，利用這些詞匯重新生成該類的中心；被選的詞匯要求tf和idf都不小于某個閾值；更新詞匯的中心id，對類中心進行壓縮，讓同一個詞匯只出現在與其相似高的一些類中心里，合并相似度較高的類中心；

步驟12、根據新的聚類中心重新計算每個文本所屬的聚類中心，相似度計算同步驟9；

步驟13、計算每個類的核心相似度，嘗試對最大的類進行分裂以產生新的類，其分裂算法如下：計算該類中最活躍的文本fx，即其它文本最相似文本中文本fx出現的次數最高，且相似值較大，在類中計算與文本fx相似度最低的文本fy，以fx及與fx最相似的文本集建立新的類中心ctx，以fy及與fy最相似的文本集建立新的類中心cty，對該類中剩下的文本計算其與ctx，cty的相似度，將它們分別并入兩者之一；

步驟14、在步驟11的基礎上對與類中心相似度較小的文本，根據其大多數詞匯的中心id并入屬于該id的類；

步驟15.重復步驟10-14，直到類的個數收斂，且同一個類中的文本與類中心相似度到達一定閾值，則終止。