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

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

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

中圖分類號：TP311.13

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

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

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

1背景知識

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

基于以上描述可知雙路聚類模型的目標函數(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）是常量，可以省略不寫，β是平衡因子。從雙路聚類模型的目標函數(shù)可以得知，一方面要盡可能的壓縮變量X和變量Y，另一方面也要盡可能的使TX和TY相互提供信息。

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

本文使用文本數(shù)據(jù)驗證雙路聚類算法的有效性，具體地，X、Y、TX和TY分別指文本X、特征詞Y、文本模式TX和特征詞袋TY。假設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分別劃分到一個層次樹中，其中||和||是期望得到的層（||=||，假設他們之間是一一對應的關系，為什么這么說呢，為了便于使用得到的解釋得到的）

初始化：

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實驗結果與分析

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

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

（3）

召回率定義為：

（4）

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

2.2實驗結果分析。傳統(tǒng)聚類算法和雙路聚類算法的實驗結果如圖1所示，經(jīng)過分析，本文可以得到如下結果：（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上精確度表明了對于同構數(shù)據(jù)，其運行結果的精確度不夠穩(wěn)定，魯棒性較低，而雙聚類算法則表現(xiàn)很穩(wěn)定，魯棒性高。同時，該現(xiàn)象在其他6個數(shù)據(jù)集上也可以體現(xiàn)出來。

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

3結論及下一步工作

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

參考文獻：

[1]N.Slonim，N.Friedman，N.Tishby.Unsuperviseddocumentclassificationusingsequentialinformationmaximization[C].In：Proceedingsofthe25thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval，2002：129-136.

[2]R.Bekkerman，R.El-Yaniv，N.Tishby，etal.Distributionalwordclustersvs.wordsfortextcategorization[J].JournalofMachineLearningResearch，2003：1183-1208.

[3]C.Galleguillos，A.Rabinovich，S.Belongie.Objectcategorizationusingco-occurrence，locationandappearance[C].IEEEConferenceonComputerVisionandPatternRecognition，2008：1-8.

[4]N.Slonim，N.Tishby.Agglomerativeinformat