Kmeans聚類分析

1、K-means聚類分析主要的聚類算法可以分為以下幾種：劃分聚類、層次聚類、密度型聚類、網(wǎng)格型聚類和基于模型的聚類。劃分聚類算法把數(shù)據(jù)點(diǎn)集分為k個(gè)劃分，每個(gè)劃分作為一個(gè)聚類。它一般從一個(gè)初始劃分開始，然后通過(guò)重復(fù)的控制策略，使某個(gè)準(zhǔn)則函數(shù)最優(yōu)化，而每個(gè)聚類由其質(zhì)心來(lái)代表(k-means算法)，或者由該聚類中最靠近中心的一個(gè)對(duì)象來(lái)代表(k-medoids算法)。劃分聚類算法收斂速度快，缺點(diǎn)在于它傾向于識(shí)別凸形分布大小相近、密度相近的聚類，不能發(fā)現(xiàn)分布形狀比較復(fù)雜的聚類，它要求類別數(shù)目k可以合理地估計(jì)，并且初始中心的選擇和噪聲會(huì)對(duì)聚類結(jié)果產(chǎn)生很大影響。主要的劃分聚類算法有k-means,EM,k-m

2、edoids,CLARA,CLARANS等。下面主要介紹K-means聚類方法。k-means算法首先隨機(jī)選擇k個(gè)對(duì)象，每個(gè)對(duì)象代表一個(gè)聚類的質(zhì)心。對(duì)于其余的每一個(gè)對(duì)象，根據(jù)該對(duì)象與各聚類質(zhì)心之間的距離，把它分配到與之最相似的聚類中。然后，計(jì)算每個(gè)聚類的新質(zhì)心。重復(fù)上述過(guò)程，直到準(zhǔn)則函數(shù)會(huì)聚。通常采用的準(zhǔn)則函數(shù)是平方誤差準(zhǔn)則函S(squared-errorcriterion),即E是一個(gè)數(shù)據(jù)集中所有對(duì)象的誤差平方和，P是一個(gè)對(duì)象，mi是聚類Ci的質(zhì)心,即曲k-means聚類算法的具體步驟如下：從數(shù)據(jù)集中選擇k個(gè)質(zhì)心Cl,C2,，Ck作為初始的聚類中心；把每個(gè)對(duì)象分配到與之最相似的聚合。每個(gè)聚合

3、用其中所有對(duì)象的均值來(lái)代表，“最相似”就是指距離最小。對(duì)于每個(gè)點(diǎn)Vi,找出一個(gè)質(zhì)心Cj,使它與其間的距離d(Vi,Cj)最小，并把Vi分配到第j組；把所有的點(diǎn)都分配到相應(yīng)的組之后重新計(jì)算每個(gè)組的質(zhì)心Cj；循環(huán)執(zhí)行第步和第步，直到數(shù)據(jù)的劃分不再發(fā)生變化。該算法具有很好的可伸縮性，其計(jì)算復(fù)雜度為O(nkt),其中，t是循環(huán)的次數(shù)。K-means聚類算法的不足之處在于它要多次掃描數(shù)據(jù)庫(kù)，此外，它只能找出球形的類，而不能發(fā)現(xiàn)任意形狀的類。還有，初始質(zhì)心的選擇對(duì)聚類結(jié)果有較大的影響,該算法對(duì)噪聲很敏感。問(wèn)題探究近年來(lái)，數(shù)據(jù)挖掘成為越來(lái)越熱的一個(gè)研究方向，而聚類(clustering)作為數(shù)據(jù)挖掘的主要方

4、法之一，也越來(lái)越引起人們的關(guān)注。所謂聚類，就是把大量的d維數(shù)據(jù)對(duì)象(n個(gè))聚集成k個(gè)聚類(kvn),使同一聚類內(nèi)對(duì)象的相似性盡可能最大,而不同聚類內(nèi)對(duì)象的相似性盡量達(dá)到最小。也就是說(shuō)，形成聚類之后，同一個(gè)聚類內(nèi)對(duì)象具有很高的相似性，而與不屬于該聚類的對(duì)象有迥然的差異（即不相似）。聚類與分類相比，分類算法分析的是類別已知的數(shù)據(jù)集，而聚類算法分析的是類別未知的數(shù)據(jù)。聚類的輸入是一組未分類的記錄，而且事先也不知道要分成幾類，它通過(guò)分析數(shù)據(jù)，根據(jù)一定的分類準(zhǔn)則，合理劃分記錄集合，從而確定每個(gè)記錄所屬的類別。不同的聚類算法中，用于描述相似性的函數(shù)也有所不同，有的釆用歐氏距離或馬氏距離，有的采用向量夾角的

5、余弦，也有的釆用其他的度量方法。當(dāng)預(yù)先不知道類型數(shù)目，或者用參數(shù)估計(jì)和非參數(shù)估計(jì)難以分辨不同類型的類概率密度函數(shù)時(shí)，就需要釆用聚類分析。有些聚類分析算法可以自動(dòng)地確定類型的數(shù)目k,而不必以預(yù)知k為前提條件，也可以給定k作為算法的終止條件若沒(méi)有給定k,那么如何在聚類過(guò)程中自動(dòng)地確定k,這是聚類分析中的一個(gè)關(guān)鍵問(wèn)題。確定k值的方法很多，具體哪種較好還有待探究。基于自組織特征神經(jīng)網(wǎng)絡(luò)（SOM）的聚類分析是其中的一種解決方案。自組織特征神經(jīng)網(wǎng)絡(luò)簡(jiǎn)介在人類的神經(jīng)系統(tǒng)及腦的研究中，人們發(fā)現(xiàn):人腦的某些區(qū)域?qū)δ撤N信息或感覺(jué)敏感，如人腦的某一部分進(jìn)行機(jī)械記憶特別有效;而某一部分進(jìn)行抽象思維特別有效。這種情況使

6、人們對(duì)大腦的作用的整體性與局部性特征有所認(rèn)識(shí)。對(duì)大腦的研究說(shuō)明，大腦是由大量協(xié)同作用的神經(jīng)元群體組成的。大腦的神經(jīng)網(wǎng)絡(luò)是一個(gè)十分復(fù)雜的反饋系統(tǒng);在這個(gè)系統(tǒng)中含有各種反饋?zhàn)饔茫姓w反饋，局部反饋:另外，還有化學(xué)交互作用。在大腦處理信息的過(guò)程中，聚類是極其重要的功能。大腦通過(guò)聚類過(guò)程從而識(shí)別外界的信號(hào)，并產(chǎn)生自組織過(guò)程。根據(jù)大腦對(duì)信號(hào)的處理特點(diǎn)，在1981年，TKohonen提出了一種神經(jīng)網(wǎng)絡(luò)模型，也就是自組織特征映射SOM（Self一orzanizingFeatureMap）oSOM網(wǎng)絡(luò)算法是一種聚類算法，它能根據(jù)其學(xué)習(xí)規(guī)則對(duì)輸入的模式進(jìn)行自動(dòng)分類，即再在無(wú)監(jiān)督的情況下，對(duì)輸入模式進(jìn)行自組織學(xué)

7、習(xí)，通過(guò)反復(fù)地調(diào)整連接權(quán)重系數(shù)，最終使得這些系數(shù)反映出輸入樣本之間地相互關(guān)系，并在競(jìng)爭(zhēng)層將分類結(jié)果表示出來(lái)。因此，SOM神經(jīng)網(wǎng)絡(luò)在結(jié)構(gòu)上模擬了大腦皮層中神經(jīng)元旱二維空間點(diǎn)陣的結(jié)構(gòu)，并在功能上通過(guò)網(wǎng)絡(luò)中神經(jīng)元間的相互作用和相互競(jìng)爭(zhēng)，模擬了大腦信息處理的聚類功能、自組織和學(xué)習(xí)功能。該算法被廣泛應(yīng)用于各種模式識(shí)別和分類問(wèn)題中。SOM網(wǎng)絡(luò)的結(jié)梅如圖1所示，它由輸入層和槍出層糾成。其中輸入層的神經(jīng)元個(gè)數(shù)的選取視繩入陽(yáng)路的向量個(gè)數(shù)而定-輸入神經(jīng)元接收網(wǎng)絡(luò)的輸入信號(hào)輸出層則是由紳經(jīng)兀按一定的方式井刃成一個(gè)半1紙輸入層的袒經(jīng)元與輸出層的紳經(jīng)元通過(guò)權(quán)備相互連接在一起。在每個(gè)輸入樣本學(xué)習(xí)過(guò)甩中.SOM網(wǎng)絡(luò)找岀與之

8、距離吊短的絢出層單元，即獲世節(jié)點(diǎn)(BMUh然后更新BMU及其相鄰區(qū)域的權(quán)值，使得輸出節(jié)點(diǎn)保持輸入時(shí)広的拓?fù)涮卣?SOM網(wǎng)絡(luò)的具俅訓(xùn)練方法如卜圖ISOMW絡(luò)給構(gòu)兇初始化對(duì)輸出足的毎個(gè)神經(jīng)元筋點(diǎn)的奴值說(shuō)樋機(jī)賦予較小的初值，定義訓(xùn)練結(jié)朿條件.從輸入樣本中隨機(jī)選取一個(gè)輸入樓式X,.尋找獲胖伙點(diǎn)(BMU處義*為狀勝節(jié)點(diǎn)，其應(yīng)該滿足卞式：dt=min(jp=minIIX,-W.II(1)/式巾：III表示跖離國(guó)數(shù).對(duì)于連續(xù)址值H性的數(shù)據(jù)集，通常釆用歐氏距離。確定獲勝單元的相郃區(qū)域心幾區(qū)域NQ隨若時(shí)間的增長(zhǎng)而不斷縮水。對(duì)區(qū)域耳(0內(nèi)的節(jié)點(diǎn)的權(quán)tn按E式進(jìn)行調(diào)整使其向X,罪龍：wf(t+!)=眄+T(t)hfj(t)Xt(t)-(2)式中:f表不時(shí)間,加)為學(xué)習(xí)率,人“)為g的鄰域歯數(shù):選取騎的輸入模式，垂復(fù)步驟3)4),直到所有輸入樣本筋巳經(jīng)龍成譏練。按一定嫌則收縮相第區(qū)域N/),域小學(xué)習(xí)率加)，重復(fù)步驟2)到5),當(dāng)達(dá)到訓(xùn)練絡(luò)束條件后停止訓(xùn)練輸出聚類結(jié)果。山于輸出層#節(jié)點(diǎn)互松渤勵(lì)學(xué)習(xí)，訓(xùn)練后的鄰近節(jié)點(diǎn)具有相似的權(quán)值，因ftSOM網(wǎng)絡(luò)輸出廿點(diǎn)的空間位賈體現(xiàn)了輸入洋本的內(nèi)在底兔即具有性的輸入會(huì)映射在鄰近的SON1輸出節(jié)點(diǎn)上。利用人眼對(duì)低維數(shù)據(jù)的快速把喔能力，實(shí)現(xiàn)聚類的可祕(mì)化，通過(guò)計(jì)算結(jié)果作圖分析可以確定k值。再結(jié)