【文章內(nèi)容簡(jiǎn)介】 間的距離進(jìn)行聚類，這類方法只能發(fā)現(xiàn)圓形或球狀的簇，較難發(fā)現(xiàn)任意形狀的簇。為此，提出了基于密度的聚類算法（DensityBased Clustering Method），其主要思想是：只要鄰近區(qū)域的對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目超過某個(gè)閾值，就繼續(xù)聚類。即對(duì)給定類中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域中至少包含某個(gè)數(shù)目的點(diǎn)，這樣就能很好的過濾掉“噪聲”數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。其基本出發(fā)點(diǎn)是，尋找低密度區(qū)域分離的高密度區(qū)域。具有代表性的方法是DBSCAN（Density Based Spatial Clustering of Applications withNoise），它是將密度足夠大的那部分記錄組成類，可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類，但它需要用戶主觀來選擇參數(shù)，從而影響了最終的聚類結(jié)果?；诿芏鹊木垲愃惴ㄔ诋?dāng)前的文獻(xiàn)中較少被用于文本聚類中。這是由于文本間的相似度不穩(wěn)定，同屬一簇的文本，有些文本間的相似度較高，所以密度高；有些相似度較低，所以密度低。如果根據(jù)全局的密度參數(shù)進(jìn)行判斷，顯然是不適合的。并且密度單元的計(jì)算復(fù)雜度大，需要建立空間索引來降低計(jì)算量，且對(duì)數(shù)據(jù)維數(shù)的伸縮性較差?；诰W(wǎng)格的算法（GridBased Clustering Method）把對(duì)象空間量化為有限數(shù)目的單元，形成了一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)。所用的聚類操作都在整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)即量化的空間上進(jìn)行。這種方法的一個(gè)突出的優(yōu)點(diǎn)就是處理速度很快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目，只與量化空間中的每一維的單元數(shù)目有關(guān)。此外，它還可以處理高維數(shù)據(jù)。代表算法有統(tǒng)計(jì)信息網(wǎng)格法STING算法、聚類高維空間法CLIQUE算法、基于小波變換的聚類法WAVECLUSTER算法。STING（Statistical Information Grid），利用了存儲(chǔ)在網(wǎng)格中的統(tǒng)計(jì)信息，它不但能并行處理且能增量更新，因而效率很高，缺點(diǎn)是簇的質(zhì)量和精確性欠佳。WaveCluster（Clustering Using Wavelet Transformation）是一種多分辨率的聚類算法。其主要優(yōu)點(diǎn)是能有效地處理大規(guī)模數(shù)據(jù)集；能發(fā)現(xiàn)任意形狀的簇；能成功地處理孤立點(diǎn)；對(duì)于輸入的順序不敏感；不要求指定任何參數(shù)；且效率和聚類質(zhì)量都比較高。CLIQUE（Clustering in Quest）是一種將基于密度的方法與基于網(wǎng)格的方法相結(jié)合的算法，能有效處理大型數(shù)據(jù)庫的高維數(shù)據(jù)。它對(duì)輸入順序不敏感，無需假設(shè)任何規(guī)范的數(shù)據(jù)分布。另外，它還具有良好的可伸縮性。但由于方法大大簡(jiǎn)化，聚類結(jié)果的精確可能降低。基于模型的算法（ModelBased Clustering Method）試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性。這樣的算法經(jīng)常是基于這樣的假設(shè)，數(shù)據(jù)是根據(jù)潛在的概率分布生成的。它通過為每個(gè)聚類假設(shè)一個(gè)模型來發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對(duì)象。根據(jù)標(biāo)準(zhǔn)統(tǒng)計(jì)方法并綜合考慮“噪聲”或異常數(shù)據(jù)，該方法可以自動(dòng)確定聚類個(gè)數(shù)，從而得到魯棒性較好的聚類方法。基于模型的算法主要有兩類，分別為統(tǒng)計(jì)學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法。大多數(shù)的概念聚類采用的是統(tǒng)計(jì)的方法，即在決定一個(gè)類時(shí)，用可能性的描述語句，典型的代表就是COBWEB，它是一個(gè)通用且簡(jiǎn)單的聚類方法?；谏窠?jīng)網(wǎng)絡(luò)的聚類方法是將每一個(gè)類看作一個(gè)標(biāo)本，它是這個(gè)類型的“典型”，但不需要和某個(gè)具體的對(duì)象或例子相對(duì)應(yīng)。根據(jù)新對(duì)象和這個(gè)標(biāo)本之間的距離，就可以將這個(gè)對(duì)象進(jìn)行分類了。如基于SOM的文檔聚類方法在數(shù)字圖書館等領(lǐng)域得到了較好的應(yīng)用。聚類分析算法眾多，應(yīng)用于文檔的聚類分析算法也種類繁多，如何評(píng)價(jià)文檔聚類分析的效果，目前還沒有一個(gè)確定的說法。在實(shí)際的應(yīng)用中一般都是實(shí)現(xiàn)幾種算法，然后用人工判斷的方法去選擇合適的算法以及算法相對(duì)應(yīng)的參數(shù)。這么多的算法雖然帶來了更多的選擇，但同時(shí)也帶來了應(yīng)用上的困難，因此有必要在一個(gè)統(tǒng)一的尺度上來衡量一些算法并對(duì)他們做出評(píng)價(jià)。本章主要介紹了影響文本聚類結(jié)果的三方面主要因素：文本表示模型、相似度計(jì)算方法及聚類算法。文本聚類過程中每個(gè)步驟都有可能影響最終的聚類效果，各方面因素變化情形眾多，在實(shí)際研究和工程應(yīng)用中，聚類評(píng)價(jià)工作困難重重。為了更好地評(píng)價(jià)聚類結(jié)果，我們?cè)谙乱徽聦⒃敿?xì)介紹已有的文本聚類評(píng)價(jià)方法，比較各自的優(yōu)缺點(diǎn)。第三章 k均值聚類算法 K均值聚類算法的思想 K均值聚類算法的基本思想一九六七年，麥克奎因[B. Mac Queen]提出了K均值聚類算法，用來處理數(shù)據(jù)聚類的問題，該種算法由于其算法簡(jiǎn)便，又很早提出，因此在科學(xué)和工業(yè)領(lǐng)域的應(yīng)用中影響力極為廣泛。該算法首先隨機(jī)選取k個(gè)數(shù)據(jù)點(diǎn)作為n個(gè)簇的初始簇中心，集合中每個(gè)數(shù)據(jù)點(diǎn)被劃分到與其距離最近的簇中心所在的類簇之中，形成了k個(gè)聚類的初始分布。對(duì)分配完的每一個(gè)類簇計(jì)算新的簇中心，然后繼續(xù)進(jìn)行數(shù)據(jù)分配過程，這樣迭代若干次后，若簇中心不再發(fā)生變化，則說明數(shù)據(jù)對(duì)象全部分配到自己所在的類簇中，聚類準(zhǔn)則函數(shù)收斂，否則繼續(xù)進(jìn)行迭代過程，直至收斂。這里的聚類準(zhǔn)則函數(shù)一般采用聚類誤差平方和準(zhǔn)則函數(shù)。本算法的一個(gè)特點(diǎn)就是在每一次的迭代過程中都要對(duì)全體數(shù)據(jù)點(diǎn)的分配進(jìn)行調(diào)整，然后重新計(jì)算簇中心，進(jìn)入下一次的迭代過程，若在某一次迭代過程中，所有數(shù)據(jù)點(diǎn)的位置沒有變化，相應(yīng)的簇中心也沒有變化，此時(shí)標(biāo)志著聚類準(zhǔn)則函數(shù)已經(jīng)收斂，算法結(jié)束。 K均值聚類算法的算法流程原始的K均值聚類算法:輸入:數(shù)據(jù)集x={x1，x2，……xn}，聚類數(shù)目k。輸出: k個(gè)類簇cj，j=1，2，……，k[stepl]令I(lǐng)=1，隨機(jī)選取k個(gè)數(shù)據(jù)點(diǎn)作為k個(gè)類簇的初始簇中心，mj(I) j=1，2，…，k。[step2]計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)與這k個(gè)簇中心的距離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]計(jì)算k個(gè)新的聚類中心[step4]判斷:若mj(i+1) mj(I)，j=1，2，…，k，則I=i+1，返回step2:否則，算法結(jié)束。K均值聚類算法在執(zhí)行過程中還可以加入聚類準(zhǔn)則函數(shù)來終止迭代過程，一般采用聚類誤差平方和準(zhǔn)則函數(shù)，即在上面算法流程中的step4中計(jì)算聚類誤差平方和J，然后加入判斷，若兩次的J值沒有明顯變化，則說明J值已經(jīng)收斂，結(jié)束算法，否則轉(zhuǎn)入step2繼續(xù)執(zhí)行。具體流程如下:[Stepl][初始化l隨機(jī)指定k個(gè)聚類中心(ml，m2，……mk)。[Step2][分配xi]對(duì)每一個(gè)樣本xi，找到離它最近的聚類中心，并將其分配到該類: [Step3][修正簇中心]重新計(jì)算各簇中心[Step4][計(jì)算偏差] [Step5][收斂判斷]如果J值收斂，則return(m1， m2，……，mk)，算法終止。否則，轉(zhuǎn)Step2。從上面的算法思想及流程中可以看出，k個(gè)類簇的初始簇中心點(diǎn)的選取對(duì)聚類的最終結(jié)果至關(guān)重要，算法中，每一次迭代都把數(shù)據(jù)點(diǎn)劃分到與其距離最近的簇中心所在的類簇中去，然后重新計(jì)算簇中心，進(jìn)而反復(fù)迭代，直到每一個(gè)數(shù)據(jù)點(diǎn)都不再重新劃分為止。 K均值算法的優(yōu)缺點(diǎn)分析K均值算法是一種基于劃分的聚類算法，它通過不斷的迭代過程來進(jìn)行聚類，當(dāng)算法收斂到一個(gè)結(jié)束條件時(shí)就終止迭代過程，輸出聚類結(jié)果。由于其算法思想簡(jiǎn)便，又容易實(shí)現(xiàn)，因此K均值算法己成為一種目前最常用的聚類算法之一。然而Kmeans過分依賴于初始中心點(diǎn)的選取，且容易受噪音點(diǎn)的影響。為解決這一問題，出現(xiàn)了各種基于全局最優(yōu)化思想的K均值聚類方法，比如模擬退火算法、遺傳算法等。然而這些技術(shù)并沒有得到廣泛認(rèn)可，在許多實(shí)際應(yīng)用中還是反復(fù)利用K均值聚類算法來解決問題。K均值聚類算法采用迭代式的過程對(duì)樣本點(diǎn)進(jìn)行分配來尋求最終的聚類結(jié)果，其終止條件是所有樣本的位置不再變化，其迭代過程可以概括如下:(l)分配樣本點(diǎn)，即對(duì)每個(gè)樣本點(diǎn)，將其分配到與其距離最近的簇中心所在的類簇中。(2)重新計(jì)算簇中心，對(duì)于每一個(gè)重新分配后的類簇，重新計(jì)算其簇中心。和大多數(shù)的聚類算法一樣，K均值聚類算法也有其自身的局限，主要局限如下:(1)K均值聚類算法中的聚類數(shù)目即K值需要由用戶預(yù)先給出。從K均值聚類算法的算法流程中可以看出，K值作為一個(gè)需要預(yù)先確定的參數(shù)，在已知的前提下才能執(zhí)行K均值聚類算法，而在實(shí)際應(yīng)用中，需要聚類的數(shù)據(jù)究竟要分成多少個(gè)類別，往往不是被用戶所知的。當(dāng)聚類數(shù)目不被人所知的情況下，人們往往需要結(jié)合其它算法來獲取聚類數(shù)目，即K值。往往獲取K值的代價(jià)要比K均值聚類算法的代價(jià)大得多，因此K值的不確定性是K均值聚類算法的一個(gè)很大的不足之處。(2)K均值聚類算法嚴(yán)重依賴于初始簇中心點(diǎn)的選取。K均值聚類算法隨機(jī)的選取K個(gè)初始簇中心點(diǎn)，并針對(duì)這K個(gè)簇中心點(diǎn)進(jìn)行迭代運(yùn)算，即重新分配數(shù)據(jù)點(diǎn)和重新計(jì)算簇中心的運(yùn)算，直到所有的數(shù)據(jù)點(diǎn)位置不再變化或聚類誤差準(zhǔn)則函數(shù)不再變化。這樣就導(dǎo)致了K均值聚類算法對(duì)初始簇中心點(diǎn)的嚴(yán)重依賴性。初始簇中心點(diǎn)選取不當(dāng)很容易造成聚類結(jié)果陷入局部最優(yōu)解甚至或?qū)е洛e(cuò)誤的聚類結(jié)果。(3)K均值聚類算法的聚類結(jié)果容易受噪音點(diǎn)數(shù)據(jù)的影響。在K均值聚類算法中，每次對(duì)于簇中心的重新計(jì)算，都是通過對(duì)每一個(gè)類簇中所有數(shù)據(jù)點(diǎn)求均值，這樣，當(dāng)數(shù)據(jù)集中存在噪音點(diǎn)數(shù)據(jù)時(shí)，均值點(diǎn)的計(jì)算將導(dǎo)致聚類中心(即簇中心偏離數(shù)據(jù)真正密集的區(qū)域，而趨向噪音點(diǎn)數(shù)據(jù)歹這樣導(dǎo)致聚類結(jié)果的不準(zhǔn)確。因此，當(dāng)數(shù)據(jù)集中存在遠(yuǎn)離所有數(shù)據(jù)點(diǎn)的噪音點(diǎn)時(shí)，聚類結(jié)果將很大程度上受這些噪音點(diǎn)的影響，導(dǎo)致聚類結(jié)果的錯(cuò)誤，所以K均值聚類算法對(duì)噪聲點(diǎn)和孤立點(diǎn)非常敏感。(4)K均值聚類算法無法發(fā)現(xiàn)任意形狀的簇。K均值聚類算法采用距離函數(shù)作為度量數(shù)據(jù)點(diǎn)間相似度的方法，這里的距離函數(shù)多采用歐氏距離，同時(shí)采用聚類誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)，對(duì)于基于歐式距離的聚類算法而言，其只能發(fā)現(xiàn)數(shù)據(jù)點(diǎn)分布較均勻的類球狀簇，對(duì)于聚類誤差平方和準(zhǔn)則函數(shù)而言，當(dāng)類簇大小差別較大，形狀較不規(guī)則時(shí)，容易造成對(duì)較大的類簇進(jìn)行分割來達(dá)到目標(biāo)函數(shù)取極小值的目的，因此容易造成錯(cuò)誤的聚類結(jié)果。(5)K均值聚類算法不適用于大數(shù)據(jù)量的聚類問題。K均值聚類算法每次迭代過程都要調(diào)整簇中心及重新分配數(shù)據(jù)點(diǎn)，因此，當(dāng)數(shù)據(jù)量比較大的時(shí)候，這些迭代過程的計(jì)算量是相當(dāng)大的，算法的時(shí)間開銷也是巨大的，因此，由于需要大量的計(jì)算時(shí)間，因此K均值聚類算法在待聚類數(shù)據(jù)量較大的時(shí)候并不適用。目前，對(duì)于K均值聚類算法的改進(jìn)主要集中在以下兩個(gè)方面:(1)初始聚類中心的選擇K均值聚類算法是一個(gè)迭代的求解最優(yōu)解的問題，這里的最優(yōu)解一般指的是目標(biāo)函數(shù)(即聚類誤差和準(zhǔn)則函數(shù))的最優(yōu)解，是一個(gè)優(yōu)化問題。然而，作為聚類誤差和準(zhǔn)則函數(shù)，通常存在一些局部最小點(diǎn)，目標(biāo)函數(shù)的搜索方向總是沿著聚類誤差和準(zhǔn)則函數(shù)的遞減方向進(jìn)行，當(dāng)初始簇中心不同時(shí)，搜索路徑也會(huì)不同，而目標(biāo)函數(shù)具有很多局部最優(yōu)解，這樣就存在著，當(dāng)初始簇中心選取不當(dāng)時(shí)，目標(biāo)函數(shù)容易陷入局部最優(yōu)解。而K均值聚類算法采取隨機(jī)選取初始簇中心點(diǎn)，這樣，初始中心點(diǎn)的不同或數(shù)據(jù)輸入順序的不同都有可能導(dǎo)致聚類結(jié)果的不穩(wěn)定性，且無法得到全局最優(yōu)解而陷入局部最優(yōu)解。(2)K值的確定問題K均值聚類算法中，K值是由用戶預(yù)先確定的，而在實(shí)際應(yīng)用中，這個(gè)K值很難直接確定，尤其是當(dāng)數(shù)據(jù)量較大時(shí)，K值的確定問題將成為K一均值聚類算法的一個(gè)很大的困難，因?yàn)樵诙鄶?shù)情況下人們并不能提前預(yù)知數(shù)據(jù)的分布情況及分類情況。而K均值聚類算法的聚類結(jié)果受K值的影響，K值不同時(shí)，聚類結(jié)果往往也隨著不同，很多方法是通過試探K值來達(dá)到獲取K值的目的，而在數(shù)據(jù)量較大時(shí)，這種方法并不行得通，需要大量的時(shí)間代價(jià)，因此，為了得到確定的聚類結(jié)果，K值的確定顯得尤為重要。因此，在無監(jiān)督情況下，通過某種學(xué)習(xí)方法得到合適的K值是很有必要的?；贙均值聚類算法的改進(jìn)，國內(nèi)外的專家學(xué)者做了大量的研究工作，主要總結(jié)如下。目前的K均值聚類算法中，對(duì)于初始聚類中心點(diǎn)的選取方法主要總結(jié)如下:(1)隨機(jī)選取k個(gè)樣本作為初始聚類中心，由于是最早提出的這種選擇初始聚類中心點(diǎn)的方法，因此在后來的很多文獻(xiàn)中把這種隨機(jī)選擇初始聚類中心的方法稱為FA(ForgyAPProach)。(2)按最大最小距離聚類法中尋找聚類中心的方法來確定K均值聚類算法中的初始聚類中心。(3)將全部樣本以某種規(guī)則直觀的分成k類，分別計(jì)算每一類的均值點(diǎn)作為K均值聚類算法的初始聚類中心。(4)采用基于數(shù)據(jù)采樣的方法。分別選取K組采樣數(shù)