matlab實(shí)現(xiàn)Kmeans聚類(lèi)算法

1、題目：matlab實(shí)現(xiàn)Kmeans聚類(lèi)算法姓名背景知識(shí)1.簡(jiǎn)介：Kmeans算法是一種經(jīng)典的聚類(lèi)算法，在模式識(shí)別中得到了廣泛的應(yīng)用，基于Kmeans的變種算法也有很多，模糊Kmeans分層Kmeans等。Kmean/口應(yīng)用于混合高斯模型的受限EM算法是一致的。高斯混合模型廣泛用于數(shù)據(jù)挖掘、模式識(shí)別、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)分析。Kmeans的迭代步驟可以看成E步和M步，E:固定參數(shù)類(lèi)別中心向量重新標(biāo)記樣本，M固定標(biāo)記樣本調(diào)整類(lèi)別中心向量。K均值只考慮（估計(jì)）了均值，而沒(méi)有估計(jì)類(lèi)別的方差，所以聚類(lèi)的結(jié)構(gòu)比較適合于特征協(xié)方差相等的類(lèi)別。Kmean碓某種程度也可以看成MeansMtf的特殊版本，Meanshi

2、ft是一種概率密度梯度估計(jì)方法（優(yōu)點(diǎn)：無(wú)需求解出具體的概率密度，直接求解概率密度梯度。），所以Meanshift可以用于尋找數(shù)據(jù)的多個(gè)模態(tài)（類(lèi)別），利用的是梯度上升法。在06年的一篇CVP就章上，證明了Meanshift方法是牛頓拉夫遜算法的變種。Kmeans和EM算法相似是指混合密度的形式已知（參數(shù)形式已知）情況下，利用迭代方法，在參數(shù)空間中搜索解。而Kmeans和Meanshift相似是指都是一種概率密度梯度估計(jì)的方法，不過(guò)是Kmea砒用的是特殊的核函數(shù)（uniformkernel）,而與混合概率密度形式是否已知無(wú)關(guān)，是一種梯度求解方式。k-means是一種聚類(lèi)算法，這種算法是依賴于點(diǎn)的鄰

3、域來(lái)決定哪些點(diǎn)應(yīng)該分在一個(gè)組中。當(dāng)一堆點(diǎn)都靠的比較近，那這堆點(diǎn)應(yīng)該是分到同一組。使用k-means,可以找到每一組的中心點(diǎn)。當(dāng)然，聚類(lèi)算法并不局限于2維的點(diǎn)，也可以對(duì)高維的空間（3維,4維，等等）的點(diǎn)進(jìn)行聚類(lèi)，任意高維的空間都可以。上圖中的彩色部分是一些二維空間點(diǎn)。上圖中已經(jīng)把這些點(diǎn)分組了，并使用了不同的顏色對(duì)各組進(jìn)行了標(biāo)記。這就是聚類(lèi)算法要做的事情。這個(gè)算法的輸入是：1：點(diǎn)的數(shù)據(jù)（這里并不一定指的是坐標(biāo)，其實(shí)可以說(shuō)是向量）2:K,聚類(lèi)中心的個(gè)數(shù)（即要把這一堆數(shù)據(jù)分成幾組）所以，在處理之前，你先要決定將要把這一堆數(shù)據(jù)分成幾組，即聚成幾類(lèi)。但并不是在所有情況下，你都事先就能知道需要把數(shù)據(jù)聚成幾類(lèi)

4、的。但這也并不意味著使用k-means就不能處理這種情況，下文中會(huì)有講解。把相應(yīng)的輸入數(shù)據(jù)，傳入k-means算法后，當(dāng)k-means算法運(yùn)行完后，該算法的輸出是：1：標(biāo)簽（每一個(gè)點(diǎn)都有一個(gè)標(biāo)簽，因?yàn)樽罱K任何一個(gè)點(diǎn)，總會(huì)被分到某個(gè)類(lèi)，類(lèi)的id號(hào)就是標(biāo)簽）2:每個(gè)類(lèi)的中心點(diǎn)。標(biāo)簽，是表示某個(gè)點(diǎn)是被分到哪個(gè)類(lèi)了。例如，在上圖中，實(shí)際上有4中“標(biāo)簽”，每個(gè)“標(biāo)簽”使用不同的顏色來(lái)表示。所有黃色點(diǎn)我們可以用標(biāo)簽0表示，所有橘色點(diǎn)可以用標(biāo)簽1來(lái)表示，等等。在本文中，使用上圖的二維坐標(biāo)(x,y)向量為數(shù)據(jù)集。假設(shè)我們要將這些點(diǎn)聚成5類(lèi)，即k=5。我們可以看出，有3個(gè)類(lèi)離的比較遠(yuǎn)，有兩個(gè)類(lèi)離得比較近，幾乎要

5、混合在一起了。當(dāng)然，數(shù)據(jù)集不一定是坐標(biāo)，假如你要對(duì)彩色圖像進(jìn)行聚類(lèi)，那么你的向量就可以是(b,g,r),如果使用的是hsv顏色空間，那還可以使用(h,s,v),當(dāng)然肯定可以有不同的組合例如(b*b,g*r,r*b),(h*b,s*g,v*v)等等。在本文中，初始的類(lèi)的中心點(diǎn)是隨機(jī)產(chǎn)生的。如上圖的紅色點(diǎn)所示，是本文隨機(jī)產(chǎn)生的初始點(diǎn)。注意觀察那兩個(gè)離得比較近的類(lèi)，它們幾乎要混合在一起，看看算法是如何將它們分開(kāi)的。類(lèi)的初始中心點(diǎn)是隨機(jī)產(chǎn)生的。算法會(huì)不斷迭代來(lái)矯正這些中心點(diǎn)，并最終得到比較靠近真實(shí)中心點(diǎn)的一組中心點(diǎn)。當(dāng)然，最終的結(jié)果不一定就是真實(shí)的那一組中心點(diǎn)，算法會(huì)盡量向真實(shí)的靠近。每個(gè)點(diǎn)(除了中心

6、點(diǎn)的其他點(diǎn))都計(jì)算與5個(gè)中心點(diǎn)的距離,選出一個(gè)距離最小的(例如該點(diǎn)與第2個(gè)中心點(diǎn)的距離是5個(gè)距離中最小的)，那么該點(diǎn)就歸屬于該類(lèi).上圖是點(diǎn)的歸類(lèi)結(jié)果示意圖.經(jīng)過(guò)步驟3后，每一個(gè)中心center(i)點(diǎn)都有它的“管轄范圍”,由于這個(gè)中心點(diǎn)不一定是這個(gè)管轄范圍的真正中心點(diǎn),所以要重新計(jì)算中心點(diǎn),計(jì)算的方法有很多種,最簡(jiǎn)單的一種是,直接計(jì)算該管轄范圍內(nèi)所有點(diǎn)的均值，做為心的中心點(diǎn)new_center(i).如果重新計(jì)算的中心點(diǎn)new_center(i)與原來(lái)的中心點(diǎn)centei)的距離大于一定的閾值(該閾值可以設(shè)定)，那么認(rèn)為算法尚未收斂，使用new_center(i)代替centei)(如圖，中心

7、點(diǎn)從紅色點(diǎn)轉(zhuǎn)移到綠色點(diǎn))，轉(zhuǎn)步驟3;否則，認(rèn)為算法已經(jīng)收斂，則new_center(i)就是最終的中心點(diǎn)?，F(xiàn)在，所有的中心都不再移動(dòng)，即算法已經(jīng)收斂。當(dāng)然，也許這些中心點(diǎn)還沒(méi)有達(dá)到你要的精度，由于計(jì)算這些中心點(diǎn)的準(zhǔn)確性，會(huì)受初始中心點(diǎn)設(shè)置的影響。所以，如果初始中心設(shè)置的很糟糕，那么得出來(lái)的結(jié)果也會(huì)不理想?？梢詮腒=1開(kāi)始，并且k值不斷的增加，通常，隨著k的增加，類(lèi)中的方差會(huì)急劇的下降，當(dāng)k達(dá)到一定大的時(shí)候，方差的下降會(huì)明顯減慢(至于慢道何種程度，可以設(shè)閾值)，此時(shí)，就選取到了最佳的k值。如果初始值沒(méi)設(shè)置好，肯定也不能獲得理想的聚類(lèi)效果。針對(duì)這種情況，這里提供兩種方法：隨機(jī)的選取多組中心點(diǎn)，在每

8、一組中心點(diǎn)上，都把kmeans算法運(yùn)行一次。最后，在選取類(lèi)間方差最小的一組。通過(guò)設(shè)定的選初始值方法(這里提供一種，當(dāng)然自己也可以去構(gòu)想其他的方法).在數(shù)據(jù)集上隨機(jī)選擇一個(gè)點(diǎn)，做為第一個(gè)中心點(diǎn)；2:在數(shù)據(jù)集上，選取離第一個(gè)中心點(diǎn)最遠(yuǎn)的一個(gè)點(diǎn)做為第二個(gè)中心點(diǎn)。3:在數(shù)據(jù)集上，選取離第一個(gè)和第二個(gè)中心最遠(yuǎn)的點(diǎn)，做為第三個(gè)中心。1 4:依此計(jì)算后續(xù)的中心點(diǎn).數(shù)據(jù)來(lái)源描述本次數(shù)據(jù)挖掘?qū)嶒?yàn)的數(shù)據(jù)源來(lái)自加州大學(xué)計(jì)算機(jī)與信息院，是用于合成控制圖時(shí)間序列聚類(lèi)分析的一組數(shù)據(jù)。數(shù)據(jù)集中一共包含600組數(shù)據(jù)，每一組數(shù)據(jù)都有60個(gè)分量，也就是數(shù)據(jù)是60維的。數(shù)據(jù)一共可以分成6個(gè)聚類(lèi)，分別是：1-100Normal（正常

9、）101-200Cyclic（循環(huán)）201-300Increasingtrend（增加趨勢(shì)）301-400Decreasingtrend（減少趨勢(shì)）401-500Upwardshift（上升變化）2 501-600Downwardshift（下降變化）.數(shù)據(jù)預(yù)處理由于本數(shù)據(jù)集的數(shù)據(jù)維數(shù)較多，所以本實(shí)驗(yàn)采用了結(jié)構(gòu)體來(lái)存儲(chǔ)60維的數(shù)據(jù)，并使用指針來(lái)進(jìn)行對(duì)數(shù)據(jù)的操作，以提高速度。在數(shù)據(jù)預(yù)處理過(guò)程中，首先將數(shù)據(jù)從data文件中讀出，后依次存入結(jié)構(gòu)體數(shù)組dataset600中。3 .k-means聚類(lèi)算法k-means算法接受參數(shù)k；然后將事先輸入的n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類(lèi)以便使得所獲得的聚類(lèi)滿足：同

10、一聚類(lèi)中的對(duì)象相似度較高；而不同聚類(lèi)中的對(duì)象相似度較小。聚類(lèi)相似度是利用各聚類(lèi)中對(duì)象的均值所獲得一個(gè)“中心對(duì)象”（引力中心）來(lái)進(jìn)行計(jì)算的。K-means算法是最為經(jīng)典的基于劃分的聚類(lèi)方法，是十大經(jīng)典數(shù)據(jù)挖掘算法之一。K-means算法的基本思想是：以空間中k個(gè)點(diǎn)為中心進(jìn)行聚類(lèi)，對(duì)最靠近他們的對(duì)象歸類(lèi)。通過(guò)迭代的方法，逐次更新各聚類(lèi)中心的值，直至得到最好的聚類(lèi)結(jié)果。（1）算法思路：首先從n個(gè)數(shù)據(jù)對(duì)象任意選擇k個(gè)對(duì)象作為初始聚類(lèi)中心；而對(duì)于所剩下其它對(duì)象，則根據(jù)它們與這些聚類(lèi)中心的相似度（距離），分別將它們分配給與其最相似的（聚類(lèi)中心所代表的）聚類(lèi)；然后再計(jì)算每個(gè)所獲新聚類(lèi)的聚類(lèi)中心（該聚類(lèi)中所有

11、對(duì)象的均值）；不斷重復(fù)這一過(guò)程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開(kāi)始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù).k個(gè)聚類(lèi)具有以下特點(diǎn)：各聚類(lèi)本身盡可能的緊湊，而各聚類(lèi)之間盡可能的分開(kāi)。該算法的最大優(yōu)勢(shì)在于簡(jiǎn)潔和快速。算法的關(guān)鍵在于初始中心的選擇和距離公式。（2）算法步驟：step.1-初始化距離K個(gè)聚類(lèi)的質(zhì)心（隨機(jī)產(chǎn)生）step.2-計(jì)算所有數(shù)據(jù)樣本與每個(gè)質(zhì)心的歐氏距離，將數(shù)據(jù)樣本加入與其歐氏距離最短的那個(gè)質(zhì)心的簇中（記錄其數(shù)據(jù)樣本的編號(hào)）step.3-計(jì)算現(xiàn)在每個(gè)簇的質(zhì)心，進(jìn)行更新，判斷新質(zhì)心是否與原質(zhì)心相等，若相等，則迭代結(jié)束，若不相等，回到step2繼續(xù)迭代。Matlab代碼:functionkm(k,A

12、)%函數(shù)名里不要出現(xiàn)"-"X=randn(100,2).*100;.randn(100,2)*200;randn(100,2).*300;.randn(100,2)*400;randn(100,2).*500;randn(100,2).*600;opts=statset('Display','final');idx,ctrs=kmeans(X,6,Distance'Replicates''Optionsplot(X(idx=1,1),X(idx=1,2),holdonplot(X(idx=2,1),X(idx=2,2)

13、,holdonplot(X(idx=3,1),X(idx=3,2),holdonplot(X(idx=4,1),X(idx=4,2),holdonplot(X(idx=5,1),X(idx=5,2),holdonplot(X(idx=6,1),X(idx=6,2),title('bfKmeanscity',.,5,.,opts);'r.','MarkerSize',12)'b.','MarkerSize',12)'m.','MarkerSize',12)'g.',&#

14、39;MarkerSize',12)'k.','MarkerSize',12)'c.','MarkerSize',12)聚類(lèi)算法圖像')plot(ctrs(:,1),ctrs(:,2),plot(ctrs(:,1),ctrs(:,2),plot(ctrs(:,1),ctrs(:,2),plot(ctrs(:,1),ctrs(:,2),plot(ctrs(:,1),ctrs(:,2),plot(ctrs(:,1),ctrs(:,2),'kx','MarkerSize',12,'

15、LineWidth',2)'ko','MarkerSize',12,'LineWidth',2)'kx','MarkerSize',12,'LineWidth',2)'kx','MarkerSize',12,'LineWidth',2)'kx','MarkerSize',12,'LineWidth',2)'kx','MarkerSize',12,'LineW

16、idth',2)plot(ctrs(:,1),ctrs(:,2),'kx','MarkerSize',12,'LineWidth',2)legend('Cluster1','Cluster2','Cluster3','Cluster4','Cluster5''Cluster6','Centroids','Location','NW)15iterations,totalsumofdistances=1889

17、4728iterations,totalsumofdistances=17870912iterations,totalsumofdistances=18405514iterations,totalsumofdistances=18264212iterations,totalsumofdistances=1783571500WOO5C00-SCO-10CO-15C0-1500-WOO-5000500100015302000K陽(yáng)4M聚類(lèi)算法圖像*Cluster1*Clcster2*Cluster3Cluster4*Clusler5ClusterBXCentroidsPublishedwithMATLAB?7.7.分析方法點(diǎn)估計(jì)、區(qū)間估計(jì)、回歸分析、假設(shè)檢驗(yàn)、聚類(lèi)分析、判別分析、因素分析和主成分