基于特征詞袋的雙聚類算法研究

摘 要：傳統(tǒng)聚類方法分析數(shù)據(jù)時，僅僅從單一角度進行分析，無法利用數(shù)據(jù)對象和其特征之間存在的協(xié)作關(guān)系，針對該問題，本文提出了基于特征詞袋的雙路聚類算法。該算法可以同時從數(shù)據(jù)對象和特征兩個方向進行數(shù)據(jù)壓縮，將特征詞壓縮袋一個詞袋里，充分的利用二者之間存在的寫作關(guān)系，對每一路數(shù)據(jù)進行分析。實驗結(jié)果表明，該雙聚類算法不僅提高了數(shù)據(jù)分析的精度，而且在動態(tài)減少的過程的數(shù)據(jù)分析，易于理解的數(shù)據(jù)分析結(jié)果。

關(guān)鍵詞：聚類；特征詞；數(shù)據(jù)分析；數(shù)據(jù)挖掘

中圖分類號：TP311.13

傳統(tǒng)聚類方法在進行數(shù)據(jù)分析時，尤其是在分析文本類數(shù)據(jù)時，僅僅從單一角度進行分析，往往忽略了能夠提高聚類精度的關(guān)鍵內(nèi)容，從而無法利用數(shù)據(jù)對象和特征之間存在的關(guān)系。為此，本文在已有的經(jīng)典聚類算法基礎(chǔ)上，提出了雙路聚類算法。該算法進行聚類分析時，分為兩個關(guān)鍵步驟：（1）使用某種聚類算法對特征進行聚類分析，尋找特征之間存在的潛在模式；（2）根據(jù)第一步尋找的特征模式，對數(shù)據(jù)對象進行聚類，尋找數(shù)據(jù)對象間存在的數(shù)據(jù)模式。

雙路聚類算法對數(shù)據(jù)以及特征進行分析，其能夠同時對數(shù)據(jù)以及特征進行分析，可以充分利用二者之間的協(xié)作關(guān)系。為了驗證本文算法的效果，使用了經(jīng)典的以互信息為度量的模擬退火的聚類算法[1]，該算法的實驗數(shù)據(jù)來源于Lang收集的20-Newsgroup數(shù)據(jù)集[2]。實驗結(jié)果表明，雙聚類算法不僅可以獲得更為準(zhǔn)確的數(shù)據(jù)對象的潛在模式，提高數(shù)據(jù)分析結(jié)果的準(zhǔn)確性，同時還存在動態(tài)降維的作用，加快了數(shù)據(jù)分析的時間精度。

本文提出了一種合理的數(shù)據(jù)分析機制，能夠發(fā)現(xiàn)數(shù)據(jù)和特征存在的協(xié)作關(guān)系，該協(xié)作關(guān)系對數(shù)據(jù)分析結(jié)果具有很大的影響。

1 背景知識

1.1 雙路聚類模型。傳統(tǒng)聚類算法分析海量數(shù)據(jù)時，其原變量、目標(biāo)變量和相關(guān)變量均是單一的。為此本文在前人研究的基礎(chǔ)上，提出了一種雙聚類思想，該思想可以將特征詞壓縮到特征詞袋中[3]，然后對數(shù)據(jù)對象進行聚類分析，這樣既可以降低數(shù)據(jù)分析時間，又可以提高其精度。具體雙聚類模型進行聚類分析的過程可以描述如下：在壓縮的過程中，給定的變量X和變量Y作為源變量和相關(guān)變量同時存在，變量X壓縮到變量TX中盡可能保存變量Y（TY）的信息，變量Y壓縮到變量TY中盡可能保存變量X（TX）的信息。該模型存在兩個優(yōu)點：一是高維數(shù)據(jù)分析時，不是全部特征對數(shù)據(jù)分析都有作用，數(shù)據(jù)中存在很多不相關(guān)或者是相關(guān)度較低的特征，維數(shù)過高造成維度災(zāi)難，雙路聚類模型提供特征選擇機制，將特征縮小到高度相關(guān)的范圍內(nèi)，該機制可稱為動態(tài)降維。二是該模型使用數(shù)據(jù)和特征之間的協(xié)作關(guān)系，同時進行數(shù)據(jù)分析，不但提高數(shù)據(jù)分析結(jié)果的精度，還使數(shù)據(jù)分析結(jié)果變的更加容易解釋。

基于以上描述可知雙路聚類模型的目標(biāo)函數(shù)為：

F（p（Tx|X），p（TY|Y））=I（X；Y）+I（TX；X）+I（TY；Y）-β（I（Tx；Y）+I（TY；X）+I（TX；TY）） （1）

其中I（X；Y）是常量，可以省略不寫，β是平衡因子。從雙路聚類模型的目標(biāo)函數(shù)可以得知，一方面要盡可能的壓縮變量X和變量Y，另一方面也要盡可能的使TX和TY相互提供信息。

1.2 雙路聚類算法。為了驗證本文算法的效果，本文引入經(jīng)典的以互信息為度量的模擬退火的聚類算法[4]為對比，提出了基于雙聚類模型的雙聚類算法，其分析機制可以描述如下：初始變量X，Y中的數(shù)據(jù)為一個劃分，使用自底向上凝聚原則，生成一棵層次樹，每一次合并當(dāng)前層的兩個劃分，使本層互信息損失最小，直到把全部數(shù)據(jù)合并到一個劃分中。雙路聚類算法對數(shù)據(jù)以及特征同時進行數(shù)據(jù)分析，與傳統(tǒng)的數(shù)據(jù)分析算法相比，該算法具有很強的可視化性和可理解性。

本文使用文本數(shù)據(jù)驗證雙路聚類算法的有效性，具體地，X、Y、TX和TY分別指文本X、特征詞Y、文本模式TX和特征詞袋TY。假設(shè)tm和tn是即將壓縮到一個變量的任意兩個變量，壓縮過程中損失的信息稱為合并代價，其被定義為：

d（tm，tn）=I（Tbefore；Y）-I（Tafter；Y） （2）

其中，I（Tbefore；Y）和I（Tafter；Y）分別代表tm和tn合并前和合并后的T和Y之間的互信息。在傳統(tǒng)聚類算法中， ，雙路聚類算法為實現(xiàn)動態(tài)的降維機制， ，JSП（PPQ）是概率分布p（·）和q（·）之間的Jensen-Shannon距離， ?；谏鲜鏊枷?，雙路聚類算法如表1所示。

表1 雙路聚類算法

輸入：聯(lián)合概率分布P（X，Y），平衡參數(shù)β（調(diào)節(jié)壓縮和保存之間的平衡），平衡參數(shù)α（調(diào)節(jié)合并X或者Y的次序）

輸出：把X和Y分別劃分到一個層次樹中，其中| |和| |是期望得到的層（| |=| |，假設(shè)他們之間是一一對應(yīng)的關(guān)系，為什么這么說呢，為了便于使用得到的 解釋得到的 ）

初始化：

←X， ←Y，β=∞，

根據(jù)公式（2）計算所有模式對之間的合并代價 _Merge_Cost[i，j]，1

根據(jù)公式（2）計算所有模式對之間的合并代價 _Merge_Cost[m，n]，1

While （| |>1）

{

←Min _Merge_Cost[]；

←Min _Merge_Cost[]；

if （ ）

{

；

根據(jù)公式（2）更新 _Merge_Cost[]；

}

else

{

；

根據(jù)公式（2）更新 _Merge_Cost[]；

}

}

End

2 實驗結(jié)果與分析

2.1 實驗評估方法。在本文中，數(shù)據(jù)采用Lang收集的20-Newsgroup數(shù)據(jù)集，并基于BoW工具進行預(yù)處理，從中取出九個子數(shù)據(jù)集，分別為B_1、B_2、B_3、M5_1、M5_2、M5_3、M10_1、M10_2、M10_3，每個數(shù)據(jù)集都包含500篇文章，計算每篇文章中的特征詞對聚類的貢獻，選取前2000個單詞作為特征詞。

為了有效的評估本文提出的雙聚類算法的有效性，采用的評價標(biāo)準(zhǔn)包括精確度和召回率，精確度定義為：

（3）

召回率定義為：

（4）

其中，T表示聚類算法分析結(jié)果的類標(biāo)號，C表示文本正確的類標(biāo)號，因此，本文定義A1（c，T）表示正確分配到類C中的文本數(shù)，A2（c，T）表示錯誤的將文檔分配到C中的文本數(shù)量，A3（c，T）表示錯誤的將文本分配到C中的文本數(shù)量。在聚類算法中，規(guī)定數(shù)據(jù)集和算法都是單類標(biāo)記時，召回率和精確度是相同的，因此，本文的實驗數(shù)據(jù)集和算法都是單類標(biāo)，其算法運行結(jié)果僅用精確度進行度量即可。

2.2 實驗結(jié)果分析。傳統(tǒng)聚類算法和雙路聚類算法的實驗結(jié)果如圖1所示，經(jīng)過分析，本文可以得到如下結(jié)果：（1）與傳統(tǒng)聚類算法相比，雙路聚類算法精確度更高。其中在數(shù)據(jù)集B_2上精確度提高最大，達到30.4%，在9個數(shù)據(jù)集上得到的平均精確度為73.7%，相比于傳統(tǒng)聚類算法提高達14.0%。（2）與傳統(tǒng)聚類算法相比，雙聚類算法具有較好的魯棒性。傳統(tǒng)聚類算法在B_1、B_2、B_3上精確度表明了對于同構(gòu)數(shù)據(jù)，其運行結(jié)果的精確度不夠穩(wěn)定，魯棒性較低，而雙聚類算法則表現(xiàn)很穩(wěn)定，魯棒性高。同時，該現(xiàn)象在其他6個數(shù)據(jù)集上也可以體現(xiàn)出來。

圖1 在九個數(shù)據(jù)集上，傳統(tǒng)聚類算法和雙路聚類算法運行結(jié)果精確度比較

3 結(jié)論及下一步工作

傳統(tǒng)聚類方法作為一種數(shù)據(jù)分析方法，已經(jīng)得到廣泛的應(yīng)用，為了更好的適應(yīng)問題需要，本文提出雙路聚類模型。該模型可以從多視角對數(shù)據(jù)進行分析，然后利用每一路數(shù)據(jù)之間的協(xié)作關(guān)系，來更好地發(fā)現(xiàn)數(shù)據(jù)中隱含的數(shù)據(jù)模式，并利用得到的數(shù)據(jù)模式解釋另一路數(shù)據(jù)模式。下一步工作是近一步完善雙路聚類算法，利用無監(jiān)督學(xué)習(xí)思想發(fā)現(xiàn)特征模式和數(shù)據(jù)模式之間的協(xié)作關(guān)系。

參考文獻：

[1]N.Slonim，N.Friedman，N.Tishby.Unsupervised document classification using sequential information maximization [C].In：Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，2002：129-136.

[2]R.Bekkerman，R.El-Yaniv，N.Tishby，et al.Distributional word clusters vs.words for text categorization [J].Journal of Machine Learning Research，2003：1183-1208.

[3]C.Galleguillos，A.Rabinovich，S.Belongie.Object categorization using co-occurrence，location and appearance [C].IEEE Conference on Computer Vision and Pattern Recognition，2008：1-8.

[4]N.Slonim，N.Tishby.Agglomerative information bottleneck [C].In：Proceedings of 13th Annual Conference on Neural Information Processing Systems，Colorado，USA，1999：617-623.

作者簡介：黃志艷（1977.10-），女，山東泰安人，講師，主要研究方向：軟件工程、教師教育。

作者單位：泰山職業(yè)技術(shù)學(xué)院，山東泰安 271000