趙 鳴，吳 磊 (長江大學計算機科學學院，湖北 荊州 434023)

改進性的文本聚類算法研究

趙 鳴，吳 磊 (長江大學計算機科學學院，湖北 荊州 434023)

在互聯(lián)網(wǎng)技術(shù)日益發(fā)展的今天，如何快速對海量的文本進行歸類是數(shù)據(jù)挖掘的一項重要課題。 提出了一種改進型的文本聚類算法，計算句子相似度時綜合考慮基于詞頻統(tǒng)計的特征向量表示法和關(guān)鍵詞之間的關(guān)系，減少了相似度對于輸入次序和頻數(shù)的敏感度，有效地提高了計算小文檔和簡單句子相似度的準確度和文本聚類結(jié)果的準確率、召回率。

文本聚類；特征向量；相似度

經(jīng)典的文本聚類算法很多,K均值聚類算法是目前比較流行的一種基于劃分的算法。該算法中文檔相似度計算通常采用向量空間模型，它們在假設(shè)術(shù)語間相互獨立的基礎(chǔ)上，通過邏輯表達式或向量間的內(nèi)積反映用戶查詢和文檔的相似度，將查詢結(jié)果按相似度的降序排列后提供給用戶[1]。它們對用戶的查詢項進行精確匹配，因此只能反映用戶所要檢索內(nèi)容的某一方面，無法保證語義概念上的匹配。而且算法效果與樣本輸入的次序和詞頻相關(guān)，只有當句子包含的詞數(shù)足夠多時，相關(guān)的詞才會重復出現(xiàn)，其效果才能體現(xiàn)出來，因此該算法只適合于詞頻較大的大文檔[2]。對于小文本文檔，K均值聚類算法很難反映出其語義特征，檢索效果較差。為此，筆者提出了一種改進型的K均值聚類算法，解決中小文檔聚類問題。

1 改進型的K均值聚類算法

圖1 傳統(tǒng)K均值聚類算法流程圖 圖2 改進型的K均值聚類算法流程圖

改進型的K均值聚類算法是在原有算法的基礎(chǔ)上作如下改進：通過改進權(quán)重和特征向量表示來改進相似度的計算方法，即計算句子相似度時不僅考慮基于詞頻統(tǒng)計的特征向量表示法，而且結(jié)合詞語間的關(guān)聯(lián)度值，考慮了關(guān)鍵詞之間的關(guān)系，減少了相似度對于輸入次序和頻數(shù)的敏感度，在某種程度上考慮了語義理解，有效的提高了計算小文檔和簡單句子相似度的準確度和文本聚類結(jié)果的準確率、召回率。其傳統(tǒng)算法和改進算法流程如圖1和圖2所示。

由圖2可知，改進型的K均值聚類算法對文檔集進行切詞預處理后，再作如下處理：①對文檔中每個詞進行權(quán)重計算，根據(jù)權(quán)重進行文本特征向量表示；②每個文檔視為一個事務(wù)，文檔中的關(guān)鍵詞組視為事務(wù)中的一組事務(wù)項，執(zhí)行關(guān)聯(lián)規(guī)則算法，得出基于詞與詞的關(guān)聯(lián)規(guī)則，并按照文中給出的算法求出詞語間的關(guān)聯(lián)度矩陣。然后由改進的相似度算法計算出句子間相似度值，執(zhí)行K均值聚類算法得到幾個簇的子集。

1.1特征向量表示和權(quán)重計算

關(guān)鍵詞是組成文本的基本元素。關(guān)鍵詞權(quán)重反映了該詞對標識文本內(nèi)容的貢獻程度和文本之間的區(qū)分能力。各個關(guān)鍵詞在不同文本中的出現(xiàn)頻率滿足一定的統(tǒng)計規(guī)律，因此可根據(jù)關(guān)鍵詞的頻率特性來分配關(guān)鍵詞權(quán)重。文本空間被看作是由一組正交詞條向量所組成的向量空間。每個文本表示為其中一個范化特征向量V(d) = {t1,w1(d)；…；ti,wi(d)；…；tn,wn(d)}，其中，ti為詞條項；wi(d)為ti在文檔d中的權(quán)值。

1.2相似度算法改進

聚類分析按照樣本在性質(zhì)上的親疏遠近的程度進行分類。為了使類分得合理，必須描述樣本之間的親疏遠近的程度[3]?？坍嫎颖军c之間的相似度[4]主要用相似系數(shù)。

(1)

2)相似度算法改進的具體實現(xiàn) 雖然夾角余弦函數(shù)可以衡量2個文檔之間的相似性[7]，但它忽略各個向量的絕對長度，一個問題用一個句子還是用多個句子來表述時，其絕對長度相差很大，用式(1)計算不準確。為此，筆者提出了一種基于關(guān)鍵詞相關(guān)性(關(guān)聯(lián)度)的相似度計算方法。計算關(guān)鍵詞的關(guān)聯(lián)度時，依據(jù)是基于關(guān)鍵詞的關(guān)聯(lián)規(guī)則，將執(zhí)行關(guān)聯(lián)規(guī)則算法后得到的前件后件同時寫入到關(guān)聯(lián)表中，同時出現(xiàn)在一條記錄中的關(guān)鍵詞具有較大的相關(guān)性，其出現(xiàn)同一條關(guān)聯(lián)規(guī)則的記錄數(shù)越多，說明其相關(guān)度越大。若同現(xiàn)記錄數(shù)為 0，其相關(guān)性設(shè)一較小默認值；若2個詞相同，其相關(guān)度為1。

整個相似度改進分為2步，首先計算文檔中關(guān)鍵詞的關(guān)聯(lián)度，形成基于關(guān)鍵詞的關(guān)聯(lián)矩陣；隨后計算句子的相似度。

R=(Rij)n×m

圖3 關(guān)聯(lián)度算法流程圖 圖4 相似度算法流程圖

其中，Rij表示關(guān)鍵詞Wn和關(guān)鍵詞Wm的關(guān)聯(lián)度。具體算法流程如圖3所示。

圖3的算法流程中，首先根據(jù)詞頻賦予其權(quán)重，并用特征向量表示，然后判斷2個句子的權(quán)重是否相等，若相等，則令Rnm為1；否則判斷Wn與Wm是否已經(jīng)存在記錄庫中。若存在，令Rnm為(i-a)(i-b)；不存在，則Rnm=b，直到記錄庫未為止。其中a與b的取值需要多次試驗進行訓練，它們的值與事務(wù)數(shù)是密切相關(guān)的，因此需要根據(jù)不同的事務(wù)數(shù)，確定適當?shù)腶與b取值。

相似度算法如圖4所示。

由于詞語的出現(xiàn)頻繁，使得權(quán)重值較大或者句子長度相差較大，經(jīng)過試驗得出的相似度值可能相差很大，這就造成這些數(shù)據(jù)對象出現(xiàn)孤立點問題，因此需要對這個孤立點進行處理。筆者采用將相似度歸一化的方法來消除孤立點對聚類結(jié)果的負面影響[8]，即句子之間的相似度可以轉(zhuǎn)化成句子之間的隸屬度問題，既不會去除這些點，又不會使之過多影響聚類效果。

2 試驗結(jié)果與結(jié)論

圖5 系統(tǒng)聚類精度結(jié)果比較

試驗分別采用傳統(tǒng)聚類算法和改進型聚類算法進行，以k為參數(shù)，把n個對象分為k個聚類，使聚類內(nèi)具有較高的相似度，聚類間的相似度較低。其中改進型的相似度的計算根據(jù)一個聚類中對象的平均值(k看作聚類的中心)來進行。試驗選用智能答疑平臺中計算機基礎(chǔ)課程相關(guān)問題共300條，執(zhí)行k-means 文本聚類算法。隨機選擇 6 個中心點，經(jīng)過 6 遍中心點變化循環(huán)后停止，根據(jù)精確度和召回率，2種算法得出聚類結(jié)果如圖5所示。

其中1、2、3、4、5、6 分別代表圖像數(shù)據(jù)，網(wǎng)絡(luò)數(shù)據(jù)，打印數(shù)據(jù)，文件數(shù)據(jù)流，數(shù)據(jù)庫，智能信息幾個方面的文檔。由表5可看出，除了簇 5 之外，其他簇的改進型聚類算法精確度和召回率都比傳統(tǒng)聚類算法的高，而簇 5即數(shù)據(jù)庫方面的精確率比較低，可能的原因是數(shù)據(jù)庫方面的文檔較短，詞頻較少，因此權(quán)重值較?。换蛘吲c數(shù)據(jù)庫方面相關(guān)的關(guān)聯(lián)規(guī)則較少，求出的詞語關(guān)聯(lián)度較低或者不準確，以至于相似度計算不準確而造成聚類準確率較低。

3 結(jié) 語

筆者通過改進權(quán)重和特征向量表示，結(jié)合關(guān)聯(lián)規(guī)則算法來改進相似度的計算方法，從而達到改進K均值聚類算法的關(guān)聯(lián)矩陣來影響聚類的結(jié)果。試驗結(jié)果表明，該改進方法對智能信息小文本的聚類有顯著的效果。由于技術(shù)和科研條件不足，該系統(tǒng)還存在很多的問題，更大的適應(yīng)范圍和更有效的聚類結(jié)果始終是該系統(tǒng)不斷努力的方向。

[1]王欽.基于數(shù)據(jù)挖掘的智能答疑系統(tǒng)的設(shè)計與實現(xiàn)[D].濟南：濟南大學，2007.

[2] 張正蘭,李珊.一個支持自然語言提問的智能答疑系統(tǒng)的實現(xiàn)[J].微機發(fā)展,2009，30(8)：1966～1968.

[3] 張同珍,申瑞民.基于 Web 的自動答疑系統(tǒng)問題匹配算法研究與實現(xiàn)[J].計算機工程與應(yīng)用，2003，39(29)：103～104.

[4] 田俊華.基于自然語言提問的自動答疑系統(tǒng)設(shè)計[J].應(yīng)用資訊,2005，(1)：48～51.

[5] 胡佳妮.文本挖掘中若干關(guān)鍵問題的研究[D].北京.北京郵電大學，2008.

[6] 薛德軍.中文文本自動分類中的關(guān)鍵問題研究[D].北京：清華大學, 2006 .

[7] 郭慶琳,樊孝忠,柳長安. 基于文本聚類的自動文摘系統(tǒng)的研究與實現(xiàn)[J].計算機工程, 2006，(4)：30～32.

[8] 尚文倩,黃厚寬,劉玉玲,等.文本分類中基于基尼指數(shù)的特征選擇算法研究[J].計算機研究與發(fā)展, 2006，43(10)：1688～1694 .

[編輯] 易國華

TP311

A

1673-1409(2009)02-N073-03

2009-02-27

趙鳴(1975-)，男，1995年大學畢業(yè)，副教授，現(xiàn)主要從事人工智能技術(shù)、智能數(shù)據(jù)挖掘與知識發(fā)現(xiàn)方面的教學與研究工作。