【正文】 層出不窮，各說各的好處，在我們的工程實踐中具體該采用哪種算法，如何設(shè)計文本聚類算法并對其進行評價都是難以解決的問題。因此，需要對文本聚類分析結(jié)果的質(zhì)量進行評價，利用這種評價機制來指導算法設(shè)計、算法選擇、算法效能分析、參數(shù)優(yōu)化等。 28 第二章 文本聚類效果影響因素影響文本聚類分析效果的因素是多方面的，文本聚類分析全過程中的每個步驟都有可能對聚類結(jié)果造成影響。聚類流程三個步驟的實際處理內(nèi)容為：(1)文本聚類分析首先將文本表示成機器可計算的形式。文本表示過程顯然需要領(lǐng)域知識參與，文本中哪些因素可以構(gòu)成特征，特征中哪些在聚類中可用以及如何使用是文本聚類第一步驟文本表示考察的內(nèi)容；(2)文本聚類分析的第二個步驟是算法。聚類分析算法可以從不同的角度進行比較，比如是否產(chǎn)生層次聚類結(jié)構(gòu)、是否需要參數(shù)、是否能夠產(chǎn)生模糊聚類、能否識別出不規(guī)則形狀的簇等等。這個步驟中算法的時空效率、聚類結(jié)果質(zhì)量是研發(fā)中選擇算法的主要標準。不同的算法對參數(shù)的敏感性不同，但是基本上參數(shù)的好壞對結(jié)果的影響都比較顯著。參數(shù)的設(shè)定主觀性比較強，如何設(shè)定才是一個好的參數(shù)缺乏有效的方法，利用本文中實現(xiàn)的聚類算法包和聚類評價方法可以通過指標的變化曲線圖尋找算法的最佳參數(shù)。在經(jīng)典的研究中通常利用特征(Term，包括字、詞、詞組等)的詞頻信息建立文本向量，通過文本向量與文本向量之間的相似度來進行聚類分析。表示特指特征的提取，計算指權(quán)重的定義和語義相似度的定義。特征的權(quán)重定義及特征結(jié)構(gòu)上的相似度度量可以選取不同的模型，如向量空間模型、概率模型、語言模型等。文本表示本質(zhì)上是對原始文本進行轉(zhuǎn)換，使之在機器上可形式化描述、可計算。關(guān)于特征定義與篩選可以參考自然語言處理領(lǐng)域中的相關(guān)研究，這里不詳細介紹。布爾模型是基于集合論與布爾代數(shù)之上的一種簡單模型，主要應(yīng)用于信息檢索中。經(jīng)典布爾模型中查詢與文檔的相關(guān)性只能是0或者1，滿足查詢query中的所有邏輯表達式的文檔被判定相關(guān)，不滿足的被判定為不相關(guān)。在經(jīng)典布爾模型基礎(chǔ)上，研究人員又提出了擴展布爾模型(Extended Boolean Approach)，重新定義了And與Or操作符成為多元操作符，使相關(guān)性可以成為[0,1]之間的數(shù)。向量空間模型將文檔表示成一個向量，向量的每一維表示一個特征，這個特征可以是一個字、一個詞、一個ngram或某個復雜的結(jié)構(gòu)。通常情況下用向量空間模型中的向量表示文檔時，需要對文檔進行切分(中文分詞、英文通過詞的分界符識別單詞)、停用詞處理、英文詞的詞形還原或者提取詞干(Stemming)，經(jīng)過若干個處理步驟后，基本上就可以得到一系列詞，將這些詞作為文檔的特征。每個文檔可以用文檔中的詞來表示，這些詞及其對應(yīng)的權(quán)重構(gòu)成一個向量。 說明VSM模型中文檔與向量空間之間的映射關(guān)系。一個文本聚類分析過程的質(zhì)量取決于對度量標準的選擇。文本相似度是用來衡量文本之間相似程度大小的一個統(tǒng)計量。如果兩文本之間相似度為1，則說明這兩個文本對象完全相同；反之，則說明兩文本沒有相似之處。通常在文本向量中，最常使用的相似度計算公式就是兩個文本向量之間的“內(nèi)積”運算，其定義為：上述各公式中，Sim(di,dj)表示文本di和dj之間的相似程度，分Wki,Wkj分別表示文本di和dj的第k個特征項的權(quán)重，n為文本特征項數(shù)。在文本相似度計算中，我們也可以用兩個文本之間的距離來度量文本之間的相似程度。(1) 當p=1時(2) 當p=2時這就是歐式距離，也就是向量空間中的直線距離。為了衡量文本集合之間的相似度，常見的方法有：最小距離、最大距離、平均距離、質(zhì)心法、離差平方和等。每種算法都有各自的優(yōu)缺點，都有其適用的領(lǐng)域，并不是每一類算法都適合于文本聚類，我們必須根據(jù)文本數(shù)據(jù)的特點對聚類算法進行分析選擇。方法將數(shù)據(jù)集合分成若干個子集，它根據(jù)設(shè)定的劃分數(shù)目k選出k個初始聚類中心，得到一個初始劃分，然后采用迭代重定位技術(shù)，反復在k個簇之間重新計算每個簇的聚類中心，并重新分配每個簇中的對象，以改進劃分的質(zhì)量。典型的劃分聚類方法有kmeans算法[36]和kmedoids算法，兩者的區(qū)別在于簇代表點的計算方法不同。為了對大規(guī)模的數(shù)據(jù)集進行聚類，以及處理復雜形狀的聚類，各類改進的劃分算法逐漸增多。算法容易局部收斂，且不同的初始聚類中心選取對聚類結(jié)果影響較大?；趯哟蔚木垲愃惴ǎ℉ierarchical Method）又叫“分級聚類算法”或“樹聚類”，它通過分解給定的數(shù)據(jù)對象集來創(chuàng)建一個層次。前者稱為自下而上的凝聚式聚類，后者稱為自上而下的分裂式聚類。使用該算法可以得到較好的聚類結(jié)果，而且該方法無需用戶輸入?yún)?shù)；但是層次聚類算法的時間復雜度比較高，達到了O(n2)，對于大規(guī)模的文本集合，有其不適用性。如果某一步?jīng)]有很好的選擇要凝聚或者分裂的簇，將會導致低質(zhì)量的聚類結(jié)果。為此，提出了基于密度的聚類算法（DensityBased Clustering Method），其主要思想是：只要鄰近區(qū)域的對象或數(shù)據(jù)點的數(shù)目超過某個閾值，就繼續(xù)聚類。其基本出發(fā)點是，尋找低密度區(qū)域分離的高密度區(qū)域?；诿芏鹊木垲愃惴ㄔ诋斍暗奈墨I中較少被用于文本聚類中。如果根據(jù)全局的密度參數(shù)進行判斷，顯然是不適合的?；诰W(wǎng)格的算法（GridBased Clustering Method）把對象空間量化為有限數(shù)目的單元，形成了一個網(wǎng)絡(luò)結(jié)構(gòu)。這種方法的一個突出的優(yōu)點就是處理速度很快，其處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與量化空間中的每一維的單元數(shù)目有關(guān)。代表算法有統(tǒng)計信息網(wǎng)格法STING算法、聚類高維空間法CLIQUE算法、基于小波變換的聚類法WAVECLUSTER算法。WaveCluster（Clustering Using Wavelet Transformation）是一種多分辨率的聚類算法。CLIQUE（Clustering in Quest）是一種將基于密度的方法與基于網(wǎng)格的方法相結(jié)合的算法，能有效處理大型數(shù)據(jù)庫的高維數(shù)據(jù)。另外，它還具有良好的可伸縮性。基于模型的算法（ModelBased Clustering Method）試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學模型之間的適應(yīng)性。它通過為每個聚類假設(shè)一個模型來發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對象?；谀Ｐ偷乃惴ㄖ饕袃深?，分別為統(tǒng)計學方法和神經(jīng)網(wǎng)絡(luò)方法?；谏窠?jīng)網(wǎng)絡(luò)的聚類方法是將每一個類看作一個標本，它是這個類型的“典型”，但不需要和某個具體的對象或例子相對應(yīng)。如基于SOM的文檔聚類方法在數(shù)字圖書館等領(lǐng)域得到了較好的應(yīng)用。在實際的應(yīng)用中一般都是實現(xiàn)幾種算法，然后用人工判斷的方法去選擇合適的算法以及算法相對應(yīng)的參數(shù)。本章主要介紹了影響文本聚類結(jié)果的三方面主要因素：文本表示模型、相似度計算方法及聚類算法。為了更好地評價聚類結(jié)果，我們在下一章將詳細介紹已有的文本聚類評價方法，比較各自的優(yōu)缺點。該算法首先隨機選取k個數(shù)據(jù)點作為n個簇的初始簇中心，集合中每個數(shù)據(jù)點被劃分到與其距離最近的簇中心所在的類簇之中，形成了k個聚類的初始分布。這里的聚類準則函數(shù)一般采用聚類誤差平方和準則函數(shù)。 K均值聚類算法的算法流程原始的K均值聚類算法:輸入:數(shù)據(jù)集x={x1，x2，……xn}，聚類數(shù)目k。[step2]計算每一個數(shù)據(jù)點與這k個簇中心的距離d(xi，mj，(i)), i=1，2，…n，j=1，2，…，k，,如果滿足d(xi，mj(I))=min{d(xi， mj(I))，j=1，2，…，k}則xi cj.[steP3]計算k個新的聚類中心[step4]判斷:若mj(i+1) mj(I)，j=1，2，…，k，則I=i+1，返回step2:否則，算法結(jié)束。具體流程如下:[Stepl][初始化l隨機指定k個聚類中心(ml，m2，……mk)。否則，轉(zhuǎn)Step2。 K均值算法的優(yōu)缺點分析K均值算法是一種基于劃分的聚類算法，它通過不斷的迭代過程來進行聚類，當算法收斂到一個結(jié)束條件時就終止迭代過程，輸出聚類結(jié)果。然而Kmeans過分依賴于初始中心點的選取，且容易受噪音點的影響。然而這些技術(shù)并沒有得到廣泛認可，在許多實際應(yīng)用中還是反復利用K均值聚類算法來解決問題。(2)重新計算簇中心，對于每一個重新分配后的類簇，重新計算其簇中心。從K均值聚類算法的算法流程中可以看出，K值作為一個需要預先確定的參數(shù)，在已知的前提下才能執(zhí)行K均值聚類算法，而在實際應(yīng)用中，需要聚類的數(shù)據(jù)究竟要分成多少個類別，往往不是被用戶所知的。往往獲取K值的代價要比K均值聚類算法的代價大得多，因此K值的不確定性是K均值聚類算法的一個很大的不足之處。K均值聚類算法隨機的選取K個初始簇中心點，并針對這K個簇中心點進行迭代運算，即重新分配數(shù)據(jù)點和重新計算簇中心的運算，直到所有的數(shù)據(jù)點位置不再變化或聚類誤差準則函數(shù)不再變化。初始簇中心點選取不當很容易造成聚類結(jié)果陷入局部最優(yōu)解甚至或?qū)е洛e誤的聚類結(jié)果。在K均值聚類算法中，每次對于簇中心的重新計算，都是通過對每一個類簇中所有數(shù)據(jù)點求均值，這樣，當數(shù)據(jù)集中存在噪音點數(shù)據(jù)時，均值點的計算將導致聚類中心(即簇中心偏離數(shù)據(jù)真正密集的區(qū)域，而趨向噪音點數(shù)據(jù)歹這樣導致聚類結(jié)果的不準確。(4)K均值聚類算法無法發(fā)現(xiàn)任意形狀的簇。(5)K均值聚類算法不適用于大數(shù)據(jù)量的聚類問題。目前，對于K均值聚類算法的改進主要集中在以下兩個方面:(1)初始聚類中心的選擇K均值聚類算法是一個迭代的求解最優(yōu)解的問題，這里的最優(yōu)解一般指的是目標函數(shù)(即聚類誤差和準則函數(shù))的最優(yōu)解，是一個優(yōu)化問題。而K均值聚類算法采取隨機選取初始簇中心點，這樣，初始中心點的不同或數(shù)據(jù)輸入順序的不同都有可能導致聚類結(jié)果的不穩(wěn)定性，且無法得到全局最優(yōu)解而陷入局部最優(yōu)解。而K均值聚類算法的聚類結(jié)果受K值的影響，K值不同時，聚類結(jié)果往往也隨著不同，很多方法是通過試探K值來達到獲取K值的目的，而在數(shù)據(jù)量較大時，這種方法并不行得通，需要大量的時間代價，因此，為了得到確定的聚類結(jié)果，K值的確定顯得尤為重要?；贙均值聚類算法的改進，國內(nèi)外的專家學者做了大量的研究工作，主要總結(jié)如下。(2)按最大最小距離聚類法中尋找聚類中心的方法來確定K均值聚類算法中的初始聚類中心。(4)采用基于數(shù)據(jù)采樣的方法。 (5)通過“密度法”選擇代表點作為初始聚類中心。(6)聚類問題解出k類問題的中心。(7)進行多次初始值的選擇、聚類、找出一組最優(yōu)的聚類結(jié)果。除了以上列出的初始中心點的選取方法以外，還有很多對K均值聚類算法的初始中心點的改進算法，在這里由于篇幅的關(guān)系我們沒有一一列出。同時也對kmeans算法的改進有兩種方法一是：現(xiàn)有的對于K均值聚類算法的改進，二是：現(xiàn)有基于初始中心點改進的K均值聚類算法。它是由多個細胞聚合而成的，在接受外界刺激后，它們會自動形成。生物細胞中的這種現(xiàn)象在SOM網(wǎng)絡(luò)模型中有所反應(yīng)。SOM網(wǎng)絡(luò)是輸入樣本通過競爭學習后，功能相同的輸入靠得比較近，不同的分得比較開，以此將一些無規(guī)則的輸入自動排開，在連接權(quán)的調(diào)整過程中，使權(quán)的分布與輸入域可逐步縮小，使區(qū)域的劃分越來越明顯。這種形式也成為數(shù)據(jù)壓縮。遺憾的是，網(wǎng)絡(luò)在高維映射到低維時會發(fā)生畸變，而且壓縮比越大，畸變越大。樣本的概率密度分布相似。一般可以這樣說，SOM網(wǎng)絡(luò)的權(quán)矢量收斂到所代表的輸入矢量的平均值，它反映了輸入數(shù)據(jù)的統(tǒng)計特性。當隨機樣本輸入到SOM網(wǎng)絡(luò)時，如果樣本足夠多，那么在權(quán)值分布上可近似于輸入隨機樣本的概率密度分布，在輸出神經(jīng)元上也反映了這種分布，即概率大的樣本集中在輸出空間的某一個區(qū)域，如果輸入的樣本有幾種分布類型，則它們各自會根據(jù)其概率分布集中到輸出空間的各個不同的區(qū)域。鄰域半徑Nbo.步驟2:取樣對所有輸入樣本執(zhí)行步驟3一步驟6.步驟3:確定獲勝神經(jīng)元。步驟4:更新獲勝神經(jīng)元及其鄰域內(nèi)所有神經(jīng)元的連接權(quán)值，而鄰域外的神經(jīng)元的連接權(quán)值保持不變。調(diào)整學習率和鄰域半徑，為了保證算法的收斂，學習率的取值一般在O到1之間，且隨著學習代數(shù)的增加而遞減。 SOM網(wǎng)絡(luò)聚類的優(yōu)點及存在的問題(l) SOM神經(jīng)網(wǎng)絡(luò)在聚類方面有如下優(yōu)點:①無須用戶指定聚類數(shù)目，網(wǎng)絡(luò)通過學習過程自適應(yīng)地確定聚類數(shù)目。③具有可視化的優(yōu)點。因此，SOM網(wǎng)絡(luò)不但能學習到輸入模式的類別特征，而且能夠?qū)W習到輸入模式在原始空間中的拓撲結(jié)構(gòu)特征和概率分布，從而具備可視化的優(yōu)點。輸出層結(jié)點的初始拓撲結(jié)構(gòu)與輸入模式在在原始數(shù)據(jù)空間中的拓撲結(jié)構(gòu)一致時，網(wǎng)絡(luò)才會達到好的學習效果。②網(wǎng)絡(luò)訓練時，有些輸出層神經(jīng)元的連接權(quán)值與輸入模式相差很大