文本聚類集成關(guān)鍵技術(shù)研究.pdf

1、聚類分析是數(shù)據(jù)挖掘、模式識別等方向的重要研究內(nèi)容之一,已被廣泛用于數(shù)據(jù)壓縮、信息檢索、語音識別、字符識別、圖像分割和文本聚類等。另外,在生物學(xué)、地質(zhì)學(xué)、地理學(xué)、市場營銷和異常數(shù)據(jù)檢測等方面也受到越來越多的關(guān)注。目前,已有上千種聚類算法,然而沒有一種算法可以成功識別出具有不同大小、不同形狀、不同密度甚至可能包含噪聲的簇。文本數(shù)據(jù)具有高維、稀疏等特點,這使得許多聚類算法并不適用于文本聚類;另外,文本集規(guī)模的海量性對聚類算法的運行效率也提出了

2、很高的要求。作為傳統(tǒng)聚類算法的重要擴展,聚類集成技術(shù)具備了傳統(tǒng)聚類算法所不具備的諸多優(yōu)點。目前,聚類集成已經(jīng)發(fā)展成為機器學(xué)習(xí)領(lǐng)域的研究熱點之一。本文以文本聚類為應(yīng)用背景,針對文本聚類集成中的關(guān)鍵問題進行了研究,取得的創(chuàng)新性研究成果包括:
　　 (1)鑒于譜聚類方法的諸多優(yōu)點,本文將基于矩陣擾動理論和譜圖理論的譜聚類算法引入到文本聚類集成問題中。針對譜聚類算法計算復(fù)雜度高的問題,本文基于代數(shù)變換,首先將大規(guī)模矩陣的特征值分解問題轉(zhuǎn)

3、化為等價的奇異值分解問題,并進一步轉(zhuǎn)化為小規(guī)模矩陣的特征值分解問題。由此設(shè)計了兩個不同的文本聚類集成譜算法SMSA和TMSA。實驗結(jié)果表明:本文的代數(shù)變換方法是切實可行的,代數(shù)變換前后算法的運行時間大幅度減少,而且獲得的結(jié)果非常接近:SMSA和TMSA比基于圖劃分的聚類集成算法更優(yōu)越,是解決文本聚類集成問題行之有效的方法。
　　 (2)本文研究了譜聚類算法的關(guān)鍵思想,從求解“最佳”子空間出發(fā),同時推導(dǎo)出文本和超邊的低維嵌入,由此

4、設(shè)計了兩個基于子空間相似度的聚類集成算法SSICA和SSDCA,實驗結(jié)果表明:SSICA和SSDCA都獲得了比基于圖劃分的聚類集成算法更優(yōu)越的結(jié)果;SSICA的聚類質(zhì)量略高于SSDCA。本文進一步泛化SSICA,設(shè)計出基于低維嵌入的文本聚類集成方法。該方法首先通過不同的譜聚類算法獲得了超邊的低維嵌入;隨后通過映射的復(fù)合間接獲得了文本的低維嵌入;最后根據(jù)文本在低維空間下的坐標使用簡單K均值算法聚類。實驗結(jié)果表明,該方法比其它常見的基于圖劃

5、分的聚類集成方法優(yōu)越,可以有效解決文本聚類集成問題。
　　 (3)本文將非負矩陣分解(NMF)引入到文本聚類集成問題中,設(shè)計了BNMF算法;由于NMF算法收斂速度較慢、易于收斂到較差的局部最優(yōu)解,本文使用K均值初始化NMF,設(shè)計出NMFK算法;另外,針對K均值算法隨機初始化所帶來的聚類結(jié)果不穩(wěn)定問題,本文使用最小最大原則確定K均值算法的初值,設(shè)計出NMFKMMP算法。實驗結(jié)果表明:使用K均值算法初始化NMF是有效的,NMFK獲得

6、了比BNMF算法更加優(yōu)越、穩(wěn)定的結(jié)果,且運行效率也比BNMF高出許多;NMFKMMP算法可以有效解決文本聚類集成問題,NMFKMMP算法運行高效,并且獲得了比其它常見的聚類集成算法更加優(yōu)越的結(jié)果。
　　 (4)超球K均值算法不能有效識別非超球狀的簇,因此易于產(chǎn)生精度較低的文本聚類集成成員。為了進一步提高文本聚類集成算法的聚類質(zhì)量,本文在集成成員生成階段引入了CHAMELEON算法的關(guān)鍵思想--“分裂-合并”(DM)策略。首先在聚

7、類成員生成階段運行使用DM策略的SKM算法r次,每次生成較多的文本子簇,并根據(jù)子簇的相似性使用Ward算法合并這些子簇,得到r個聚類成員,隨后在聚類集成階段采用本文設(shè)計的聚類集成算法進行集成。實驗結(jié)果顯示,除了基于圖劃分的聚類集成算法外,基于層次聚類方法的4個聚類集成算法以及本文設(shè)計的基于譜聚類方法、基于低維嵌入方法和基于非負矩陣分解方法的多個文本聚類集成算法在使用DM策略后獲得的平均規(guī)范化互信息(NMI)都有不同程度的提高,這表明DM