【正文】 聚類的初始分布。對分配完的每一 個類簇計算新的簇中心，然后繼續(xù)進(jìn)行數(shù)據(jù)分配過程，這樣迭代若干次后，若簇中心不再發(fā)生變化，則說明數(shù)據(jù)對象全部分配到自己所在的類簇中，聚類準(zhǔn)則函數(shù)收斂，否則繼續(xù)進(jìn)行迭代過程，直至收斂。這里的聚類準(zhǔn)則函數(shù)一般采用聚類誤差平方和準(zhǔn)則函數(shù)。本算法的一個特點就是在每一次的迭代過程中都要對全體數(shù)據(jù)點的分配進(jìn)行調(diào)整，然后重新計算簇中心，進(jìn)入下一次的迭代過程，若在某一次迭代過程中，所有數(shù)據(jù)點的位置沒有變化，相應(yīng)的簇中心也沒有變化，此時標(biāo)志著聚類準(zhǔn)則函數(shù)已經(jīng)收斂，算法結(jié)束。 K均值聚類算法的算法流程 原始的 K均 值聚類算法 : 輸入 :數(shù)據(jù)集 x={x1， x2， ?? xn}，聚類數(shù)目 k。 輸出 : k個類簇 cj， j=1， 2， ?? ， k [stepl]令 I=1，隨機(jī)選取 k個數(shù)據(jù)點作為 k 個類簇的初始簇中心， mj(I) j=1，2，?， 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 個新的聚類 中心 基于文本的聚類算法研究 13 [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īng)收斂，結(jié)束算法，否則轉(zhuǎn)入 step2 繼續(xù)執(zhí)行。具體流程如下 : [Stepl][初始化 l隨機(jī)指定 k 個聚類中心 (ml， m2， ?? mk)。 [Step2][分配 xi]對每一個樣本 xi，找到離它最近的聚類中心，并將其分配到該類 : [Step3][修正簇中心 ]重新計算各簇中心 [Step4][計算偏差 ] [Step5][收斂判斷 ]如果 J值收斂，則 return(m1， m2， ? ? ， mk)，算法終止 。否則，轉(zhuǎn) Step2。 從上面的算法思想及流程中可以看出， k個類簇的初始簇中心點的選取對聚類的最終結(jié)果至關(guān)重要，算法中，每一次迭代都把數(shù)據(jù)點劃分到與其距離最近的簇中心所在的類簇中去，然后重新計算簇中心，進(jìn)而反復(fù)迭代，直到每一個數(shù)據(jù)點都不再重新劃分為止。 K均值算法的優(yōu)缺點分析 K均值算法是一種基于劃分的聚類算法，它通過不斷的迭代過程來進(jìn)行聚類，當(dāng)算法收斂到一個結(jié)束條件時就終止迭代過程，輸出聚類結(jié)果。由于其算法思想基于文本的聚類算法研究 14 簡便，又容易實現(xiàn)，因此 K均值算法己成為一種目前最常用的聚 類算法之一。然而 Kmeans 過分依賴于初始中心點的選取，且容易受噪音點的影響。為解決這一問題，出現(xiàn)了各種基于全局最優(yōu)化思想的 K均值聚類方法，比如模擬退火算法、遺傳算法等。然而這些技術(shù)并沒有得到廣泛認(rèn)可，在許多實際應(yīng)用中還是反復(fù)利用 K均值聚類算法來解決問題。 K均值聚類算法采用迭代式的過程對樣本點進(jìn)行分配來尋求最終的聚類結(jié)果，其終止條件是所有樣本的位置不再變化，其迭代過程可以概括如下 :(l)分配樣本點，即對每個樣本點，將其分配到與其距離最近的簇中心所在的類簇中 。(2)重新計算簇中心，對于每一個重新分配 后的類簇，重新計算其簇中心。和大多數(shù)的聚類算法一樣， K均值聚類算法也有其自身的局限，主要局限如下 : (1)K均值聚類算法中的聚類數(shù)目即 K值需要由用戶預(yù)先給出。從 K均值聚類算法的算法流程中可以看出， K 值作為一個需要預(yù)先確定的參數(shù)，在已知的前提下才能執(zhí)行 K均值聚類算法，而在實際應(yīng)用中，需要聚類的數(shù)據(jù)究竟要分成多少個類別，往往不是被用戶所知的。當(dāng)聚類數(shù)目不被人所知的情況下，人們往往需要結(jié)合其它算法來獲取聚類數(shù)目，即 K值。往往獲取 K值的代價要比 K均值聚類算法的代價大得多，因此 K 值的不確定性是 K均值聚類算 法的一個很大的不足之處。 (2)K均值聚類算法嚴(yán)重依賴于初始簇中心點的選取。 K均值聚類算法隨機(jī)的選取 K個初始簇中心點，并針對這 K個簇中心點進(jìn)行迭代運算，即重新分配數(shù)據(jù)點和重新計算簇中心的運算，直到所有的數(shù)據(jù)點位置不再變化或聚類誤差準(zhǔn)則函數(shù)不再變化。這樣就導(dǎo)致了 K均值聚類算法對初始簇中心點的嚴(yán)重依賴性。初始簇中心點選取不當(dāng)很容易造成聚類結(jié)果陷入局部最優(yōu)解甚至或?qū)е洛e誤的聚類結(jié)果。 (3)K均值聚類算法的聚類結(jié)果容易受噪音點數(shù)據(jù)的影響。在 K均值聚類算法中，每次對于簇中心的重新計算，都是通過對每一個類簇 中所有數(shù)據(jù)點求均值，這樣，當(dāng)數(shù)據(jù)集中存在噪音點數(shù)據(jù)時，均值點的計算將導(dǎo)致聚類中心 (即簇中心偏離數(shù)據(jù)真正密集的區(qū)域，而趨向噪音點數(shù)據(jù)歹這樣導(dǎo)致聚類結(jié)果的不準(zhǔn)確。因此，當(dāng)數(shù)據(jù)集中存在遠(yuǎn)離所有數(shù)據(jù)點的噪音點時，聚類結(jié)果將很大程度上受這些噪音點的影響，導(dǎo)致聚類結(jié)果的錯誤，所以 K均值聚類算法對噪聲點和孤立點非常敏感。 基于文本的聚類算法研究 15 (4)K均值聚類算法無法發(fā)現(xiàn)任意形狀的簇。 K均值聚類算法采用距離函數(shù)作為度量數(shù)據(jù)點間相似度的方法，這里的距離函數(shù)多采用歐氏距離，同時采用聚類誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)，對于基于歐式距離的聚 類算法而言，其只能發(fā)現(xiàn)數(shù)據(jù)點分布較均勻的類球狀簇，對于聚類誤差平方和準(zhǔn)則函數(shù)而言，當(dāng)類簇大小差別較大，形狀較不規(guī)則時，容易造成對較大的類簇進(jìn)行分割來達(dá)到目標(biāo)函數(shù)取極小值的目的，因此容易造成錯誤的聚類結(jié)果。 (5)K均值聚類算法不適用于大數(shù)據(jù)量的聚類問題。 K均值聚類算法每次迭代過程都要調(diào)整簇中心及重新分配數(shù)據(jù)點，因此，當(dāng)數(shù)據(jù)量比較大的時候，這些迭代過程的計算量是相當(dāng)大的，算法的時間開銷也是巨大的，因此，由于需要大量的計算時間，因此 K均值聚類算法在待聚類數(shù)據(jù)量較大的時候并不適用。 現(xiàn)有的對于 K均值聚類算法的改進(jìn) 目前，對于 K均值聚類算法的改進(jìn)主要集中在以下兩個方面 : (1)初始聚類中心的選擇 K均值聚類算法是一個迭代的求解最優(yōu)解的問題，這里的最優(yōu)解一般指的是目標(biāo)函數(shù) (即聚類誤差和準(zhǔn)則函數(shù) )的最優(yōu)解，是一個優(yōu)化問題。然而，作為聚類誤差和準(zhǔn)則函數(shù)，通常存在一些局部最小點，目標(biāo)函數(shù)的搜索方向總是沿著聚類誤差和準(zhǔn)則函數(shù)的遞減方向進(jìn)行，當(dāng)初始簇中心不同時，搜索路徑也會不同，而目標(biāo)函數(shù)具有很多局部最優(yōu)解，這樣就存在著，當(dāng)初始簇中心選取不當(dāng)時，目標(biāo)函數(shù)容易陷入局部最優(yōu)解。而 K均值聚類算法采取隨機(jī)選取初始簇 中心點，這樣，初始中心點的不同或數(shù)據(jù)輸入順序的不同都有可能導(dǎo)致聚類結(jié)果的不穩(wěn)定性，且無法得到全局最優(yōu)解而陷入局部最優(yōu)解。 (2)K 值的確定問題 K均值聚類算法中， K值是由用戶預(yù)先確定的，而在實際應(yīng)用中，這個 K值很難直接確定，尤其是當(dāng)數(shù)據(jù)量較大時， K值的確定問題將成為 K 一均值聚類算法的一個很大的困難，因為在多數(shù)情況下人們并不能提前預(yù)知數(shù)據(jù)的分布情況及分類情況。而 K均值聚類算法的聚類結(jié)果受 K值的影響， K 值不同時，聚類結(jié)果往往也隨著不同，很多方法是通過試探 K值來達(dá)到獲取 K值的目的，而在數(shù)據(jù)量較大時，這種方法并不 行得通，需要大量的時間代價，因此，為了得到確定的聚類結(jié)果， K 值的確定顯得尤為重要。因此，在無監(jiān)督情況下，通過某種學(xué)習(xí)方法得到合適的 K值是很有必要的。 基于 K均值聚類算法的改進(jìn)，國內(nèi)外的專家學(xué)者做了大量的研究工作，主要 基于文本的聚類算法研究 16 總結(jié)如下。 現(xiàn)有基于初始中心點改進(jìn)的 K均值聚類算法 目前的 K均值聚類算法中，對于初始聚類中心點的選取方法主要總結(jié)如下 : (1)隨機(jī)選取 k 個樣本作為初始聚類中心，由于是最早提出的這種選擇初始聚類中心點的方法，因此在后來的很多文獻(xiàn)中把這種隨機(jī)選擇初始聚類中心的方法稱為 FA(FyAPProach)。 (2)按最大最小距離聚類法中尋找聚類中心的方法來確定 K均值聚類算法 中的初始聚類中心。 (3)將全部樣本以某種規(guī)則直觀的分成 k類，分別計算每一類的均值點作為 K均值聚類算法的初始聚類中心。 (4)采用基于數(shù)據(jù)采樣的方法。分別選取 K組采樣數(shù)據(jù)分別執(zhí)行 K均值聚 類算法，然后選擇聚類結(jié)果最好的一組聚類中心作為算法的初始聚類中心點。 (5)通過“密度法”選擇代表點作為初始聚類中心。這里所指的密度是指樣本點分布的密集情況，描述為，對于所有的樣本，、將每個樣本點假設(shè)為中心，設(shè)定一個半徑， 則落入這個半徑所在圓內(nèi)的所有樣本點的數(shù)目即為該樣本點的密度值，在計算完所有樣本點的密度值后，選取最大密度值的樣本點作為第一個初始聚類中心，然后將該樣本點及其半徑所在圓內(nèi)的數(shù)據(jù)點去除后，重新設(shè)定半徑選取下一個初始中心點，以此類推，直到得到 K 個初始中心點。 (6)聚類問題解出 k 類問題的中心。算法思路如下 :先將全部樣本點看成是一個類簇的聚類問題，執(zhí)行 K均值聚類算法后得到的簇中心即為一個類簇的聚類問題的最佳解，然后選取與現(xiàn)有簇中心距離最遠(yuǎn)的點作為下一個類簇的初始簇中心，以此類推，確定出 K個類簇的初始聚類中心。 (7)進(jìn)行多次初始值的選擇、聚類、找出一組最優(yōu)的聚類結(jié)果。 (8)采用遺傳算法或者免疫規(guī)劃方法 lv1 進(jìn)行混合聚類。除了以上列出的初始中心點的選取方法以外，還有很多對 K均值聚類算法的初始中心點的改進(jìn)算法，在這里由于篇幅的關(guān)系我們沒有一一列出。 基于文本的聚類算法研究 17 本章小結(jié) 本章詳細(xì)的闡述了 k均值聚類算法的算法思想及算法流程，并且詳細(xì)的提出了該算法的優(yōu)點以及存在的問題。同時也 對 kmeans 算法的改進(jìn)有兩種方法一是：現(xiàn)有的對于 K均值聚類算法的改進(jìn)，二是：現(xiàn)有基于初始中心點改進(jìn)的 K均值聚類算法。 基于文本的聚類算法研究 18 第四章 SOM 聚類算法 SOM 聚類算法的網(wǎng)絡(luò)特性與基本流程 SOM 網(wǎng)絡(luò)的特性 神經(jīng)細(xì)胞模型中還存在著一種細(xì)胞聚類的功能柱。它是由多個細(xì)胞聚合而成的，在接受外界刺激后，它們會自動形成。一個功能柱中的細(xì)胞完成同一種功能。生物細(xì)胞中的這種現(xiàn)象在 SOM網(wǎng)絡(luò)模型中有所反應(yīng)。當(dāng)外界輸入不同的樣本到 SOM網(wǎng)絡(luò)中，一開始輸入樣本引起輸出興奮的位置各不相同，但通過網(wǎng)絡(luò)自組織后會形成一些輸出群，它們分別代表了輸入樣本的分布，反映了輸入樣本的圖形分布特征，所以 SOM 網(wǎng)絡(luò)常常被稱為特性圖。 SOM 網(wǎng)絡(luò)是輸入樣本通過競爭學(xué)習(xí)后，功能相同的輸入靠得比較近，不同的分得比較開，以此將一些無規(guī)則的輸入自動排開，在連接權(quán)的調(diào)整過程中，使權(quán)的分布與輸入域可逐步縮小，使區(qū)域的劃分越來越明顯。在這種情況下，不論輸入樣本是多少維的，都可投影到低維的數(shù)據(jù)空間的某個區(qū)域上。這種形式也成為數(shù)據(jù)壓縮。同時，如果高維空間比較相近的樣本，則在低維空間中的投影也比較接近，這樣就可以從中取出樣本空間中較多的信息。遺憾的是，網(wǎng)絡(luò)在高維映射到低維時會發(fā)生畸變，而且壓縮比越大，畸變越大 。另外網(wǎng)絡(luò)要求的輸入神 經(jīng)元數(shù)很大，因而 SOM 網(wǎng)絡(luò)比其他人工神經(jīng)網(wǎng)絡(luò) (比如 BP 網(wǎng)絡(luò) )的規(guī)模要大。樣本的概率密度分布相似。所以 SOM 網(wǎng)絡(luò)可以作為一種樣本特征檢測器，在樣本排序、樣本分類以及樣本檢測方面有廣泛的應(yīng)用。一般可以這樣說， SOM網(wǎng)絡(luò)的權(quán)矢量收斂到所代表的輸入矢量的平均值，它反映了輸入數(shù)據(jù)的統(tǒng)計特性。再擴(kuò)大一點，如果說一般的競爭學(xué)習(xí)網(wǎng)絡(luò)能夠訓(xùn)練識別出輸入矢量的點特征，那么 SOM網(wǎng)絡(luò)能夠表現(xiàn)輸入矢量在線上或平面上的分布特征。當(dāng)隨機(jī)樣本輸入到 SOM網(wǎng)絡(luò)時，如果樣本足夠多，那么在權(quán)值分布上可近似于輸入隨機(jī)樣本的概率密度分布，在輸出神 經(jīng)元上也反映了這種分布，即概率大的樣本集中在輸出空間的某一個區(qū)域，如果輸入的樣本有幾種分布類型，則它們各自會根據(jù)其概率分布集中到輸出空間的各個不同的區(qū)域。每一個區(qū)域代表同一類的樣本 . 基于文本的聚類算法研究 19 SOM 網(wǎng)絡(luò)聚類的基本流程 步驟 1:初始化連接權(quán)值 ? ，學(xué)習(xí)率 a。，鄰域半徑 Nbo. 步驟 2:取樣對所有輸入樣本執(zhí)行步驟 3 一步驟 6. 步驟 3:確定獲勝神經(jīng)元。如果采用歐氏距離，計算連接權(quán)向量與輸入樣本之間的距離，選擇值最小的神經(jīng)元是獲勝神經(jīng)元。 步驟 4:更新獲勝神經(jīng)元及其鄰域 內(nèi)所有神經(jīng)元的連接權(quán)值，而鄰域外的神經(jīng)元的連接權(quán)值保持不變。 步驟 5:參數(shù)調(diào)整。調(diào)整學(xué)習(xí)率和鄰域半徑，為了保證算法的收斂，學(xué)習(xí)率的取值一般在 O到 1之間，且隨著學(xué)習(xí)代數(shù)的增加而遞減 。鄰域半徑也隨著學(xué)習(xí)代數(shù)的增加而遞減，最后只有獲勝結(jié)點在學(xué)習(xí) 步驟 6:返回步驟 2，直至算法收斂或達(dá)到最大迭代次數(shù)為為止。 SOM 網(wǎng)絡(luò)聚類的優(yōu)點及存在的問題 (l) SOM神經(jīng)網(wǎng)絡(luò)在聚類方面有如下優(yōu)點 : ①無須用戶指定聚類