基于向量空間模型的層次聚類算法在文本挖掘中的應(yīng)用

張 浩

（溫州職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系，浙江 溫州 325035）

0 引 言

文本數(shù)據(jù)挖掘是指抽取有效、新穎、有用、可理解的、散布在文本文件中的有價(jià)值的知識(shí)，并且利用這些知識(shí)更好地組織信息的過程[1]。相較于數(shù)據(jù)庫中的結(jié)構(gòu)化數(shù)據(jù)，諸如新聞數(shù)據(jù)、郵件數(shù)據(jù)、文檔數(shù)據(jù)、Web數(shù)據(jù)等文本數(shù)據(jù)的結(jié)構(gòu)表達(dá)非常有限；文本數(shù)據(jù)中的內(nèi)容是人類的自然語言，現(xiàn)有的數(shù)據(jù)挖掘技術(shù)仍無法解決利用計(jì)算機(jī)來處理語義的難題，這就需要對文本進(jìn)行預(yù)處理，抽取其特征的元數(shù)據(jù)，作為文本的中間表達(dá)形式。常用的文本信息特征表示有布爾邏輯模型、向量空間模型（VSM）、概率模型及混合模型，其中向量空間模型最大的優(yōu)點(diǎn)在于將非結(jié)構(gòu)化和半結(jié)構(gòu)化的文本表示為向量形式，使得各種數(shù)學(xué)處理成為可能。

隨著文本數(shù)據(jù)挖掘技術(shù)的不斷深入，文本數(shù)據(jù)挖掘技術(shù)中的聚類分析得到了較快的發(fā)展。文本聚類是基于“聚類假設(shè)”，其關(guān)鍵是將預(yù)先給定的若干無標(biāo)記的文本數(shù)據(jù)對象聚集起來使之成為有意義的類。文本聚類中常用的層次聚類算法是對指定的文本數(shù)據(jù)集進(jìn)行層次分解，直到滿足某種條件為止。層次聚類的優(yōu)點(diǎn)是距離和規(guī)則的相似度容易定義，不需要事先確定聚類個(gè)數(shù)，容易發(fā)現(xiàn)類的層次關(guān)系，聚類成其它形狀。本文基于向量空間模型，采用文本聚類中的層次聚類算法，實(shí)現(xiàn)文本數(shù)據(jù)的挖掘。

1 文本聚類工作原理

基于文本聚類的過濾思想[2-3]是：在預(yù)定的層次目錄下，獲取特征詞的關(guān)聯(lián)矩陣，作為特征詞擴(kuò)充的依據(jù)。關(guān)聯(lián)矩陣反映了在該目錄下的文本中詞的關(guān)聯(lián)，利用它進(jìn)行擴(kuò)充，可以有效防止因用戶興趣擴(kuò)充而出現(xiàn)的“漂移”情況。對用戶模板進(jìn)行聚類，將具有相同和相似興趣的用戶模板分為一類，通過與類重心向量的匹配，將符合要求的文本推送給相應(yīng)的一類用戶，以提高文本過濾的準(zhǔn)確度。

文本聚類主要依據(jù)相似度假設(shè)，即同類型的文檔相似度較高，不同類型的文檔相似度較低，把一個(gè)文本集分成若干稱為簇（cluster）的子集，每個(gè)簇中的文本之間具有較大的相似性，而簇之間的文本具有較小的相似性[4]。因?yàn)槭菬o監(jiān)督的學(xué)習(xí)方式，聚類既無需訓(xùn)練也無需預(yù)先手工標(biāo)識(shí)類別，只需對原始文檔集進(jìn)行相應(yīng)的預(yù)處理，建立索引并抽取特征詞，計(jì)算文檔間相似度，再根據(jù)一定的算法進(jìn)行聚類，算出每一類文檔的質(zhì)心。當(dāng)加入新文檔時(shí)，將此文檔按相似度歸類并重新對該類計(jì)算質(zhì)心。文本聚類系統(tǒng)的工作流程如圖1所示。

圖1 文本聚類系統(tǒng)的工作流程

2 基于向量空間模型的層次聚類算法及實(shí)現(xiàn)

向量空間模型是將文檔空間看作是由一組正交詞條矢量組成的矢量空間，且每個(gè)文檔表示為一個(gè)規(guī)范化矢量V(d)=(t1,ω1(d)；…；ti,ωi(d)；…；tn,ωn(d)；…；)，其中，ti(i=1,2,…,n)為詞條項(xiàng)，ωi(d)為ti在d中的權(quán)值，這樣一篇文章就表示成為高維空間中的一個(gè)向量[5]。一般還需要構(gòu)造一個(gè)評(píng)價(jià)函數(shù)用以表示詞條權(quán)重，其計(jì)算的唯一準(zhǔn)則就是最大限度地區(qū)分不同文檔。

基于向量空間模型的層次聚類算法的步驟如下：

（1）對于給定的文檔集D={d1,d2,…,di,…,dn}，將D中每個(gè)文檔di當(dāng)作一個(gè)簇，即ci={di}，所有的簇構(gòu)成一個(gè)聚類C={c1,c2,…,ci}。

（2）計(jì)算聚類C中兩兩簇之間的相似度。

（3）選取最大相似度的簇對max sim(ci,cj)，將ci和cj合并為一個(gè)新簇ck=ciUcj。

（4）重復(fù)上述步驟，最后剩下的簇?cái)?shù)達(dá)到預(yù)先設(shè)定的聚類數(shù)為止。

可見，層次聚類算法相當(dāng)于將每篇文檔作為一篇文檔節(jié)點(diǎn)生成m_nMaxClasses棵聚類樹的過程，每次合并相似度最大的兩棵樹，并相應(yīng)調(diào)整權(quán)重、相似度等信息，繼續(xù)合并直至聚類樹的棵數(shù)等于預(yù)先設(shè)定的聚類數(shù)為止。

值得注意的是，層次聚類算法的具體步驟中，關(guān)鍵在于如何合并相似度最大的樹，聚類后如何輸出結(jié)果，這需要在程序中做好以下幾項(xiàng)工作：一是將布爾型成員m_bClusted改為整型數(shù)據(jù)成員m_nParent。整型數(shù)據(jù)成員的意義是將一篇未被聚類的文檔設(shè)為0，否則設(shè)為它的父節(jié)點(diǎn)文檔號(hào)。二是每次要比較文檔的兩兩相似度，因此相似度數(shù)組要由一維變?yōu)槎S。三是每次合并兩棵相似度最大的樹時(shí)，將權(quán)重大的樹的根作為根，權(quán)重小的作為子樹。四是每次合并兩棵樹后要?jiǎng)討B(tài)調(diào)整相似度數(shù)組的值。對于將要合并的兩棵樹的根節(jié)點(diǎn)的文檔號(hào)，選權(quán)值大的作為根節(jié)點(diǎn)，設(shè)節(jié)點(diǎn)號(hào)為r,調(diào)整相似度數(shù)組中行號(hào)和列號(hào)為r的元素。五是聚類完成后，每棵樹的根節(jié)點(diǎn)對應(yīng)的文檔即為該類的質(zhì)心。結(jié)果輸出時(shí)，需要對聚類樹進(jìn)行遍歷。

層次聚類算法的形式化過程描述為：

void CCluster::Run()

{

將每篇文檔初始化為一棵樹，父節(jié)點(diǎn)號(hào)為0；

while（當(dāng)前聚類樹的棵數(shù)>設(shè)定的聚類數(shù)）

{

計(jì)算文檔兩兩相似度存入相似度數(shù)組；

選取相似度最大的兩篇文檔對應(yīng)節(jié)點(diǎn)；

將權(quán)值較小節(jié)點(diǎn)的m_nParent置成權(quán)

值較大的節(jié)點(diǎn)號(hào)；

調(diào)整新生成樹的權(quán)值和相似度數(shù)組；

當(dāng)前聚類樹棵數(shù)減1；

}

輸出聚類結(jié)果；

}

3 實(shí) 驗(yàn)

根據(jù)預(yù)設(shè)的聚類體系，從各大門戶網(wǎng)站上收集300篇文本，首先選取其中20篇作為測試樣本，然后對基于向量空間模型的層次聚類算法進(jìn)行分析調(diào)試，再隨機(jī)抽取剩余中的100篇和200篇作為實(shí)驗(yàn)樣本進(jìn)行測試，最后采用準(zhǔn)確率評(píng)價(jià)聚類效果。這里的準(zhǔn)確率是指所有判斷的文本中與人工聚類結(jié)果吻合的文本所占的比率。測試結(jié)果表明，采用基于向量空間模型的層次聚類算法對文本進(jìn)行聚類，在20篇測試樣本的情況下準(zhǔn)確率可以達(dá)到81%，在其余兩種樣本容量的環(huán)境下，整體準(zhǔn)確率也都有不同程度的改善，如圖2所示。

4 結(jié)束語

通過基于向量空間模型的層次聚類算法從網(wǎng)上采集的樣本在特征空間中的分布情況與待分樣本非常相近，說明采用該算法從網(wǎng)上獲取相似樣本的方法是可行的，且從挖掘的準(zhǔn)確率上更具有性能優(yōu)勢。但隨著樣本容量的增加，準(zhǔn)確率會(huì)有所降低，其中主要的原因是實(shí)驗(yàn)數(shù)據(jù)類別本身比較相似，屬于一個(gè)大類別，或者由于同一個(gè)子類別下的文本文件關(guān)聯(lián)不是很緊密。這可以通過去除無特征詞和合并同義詞來提高準(zhǔn)確率。

圖2 基于向量空間模型的層次聚類算法與指定闕值算法、最大權(quán)重算法的比較

[1]常青.文本挖掘 挖掘知識(shí)[J].中國計(jì)算機(jī)用戶，2004(24):49-50.

[2]胡可.基于人工免疫系統(tǒng)的信息過濾技術(shù)研究[D].成都:西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，2006.

[3]林鴻飛，馬雅彬.基于聚類的文本過濾模型[J].大連理工大學(xué)學(xué)報(bào)，2002(2):249-252.

[4]馬軍紅.文本聚類算法初探[J].電子世界，2012(6):71-72.

[5]劉泉鳳，陸蓓，王小華.文本挖掘中聚類算法的比較研究[J].計(jì)算機(jī)時(shí)代，2005(6):7-8，22.