K均值聚類分析

1、1案例題目：選取一組點（三維或二維），在空間內繪制出來，之后根據K均值聚類，把這組點分為n類。此例中選取的三維空間內的點由均值分別為（0,0,0）,（4,4,4）,（-4,4,-4）,300000300協(xié)方差分別為030,030，030的150個由mvnrnd函數(shù)隨機生003003003成。2原理運用與解析：2.1聚類分析的基本思想聚類分析是根據“物以類聚”的道理，對樣本或指標進行分類的一種多元統(tǒng)計分析方法，它們討論的對象是大量的樣本，要求能合理地按各自的特性進行合理的分類。對于所選定的屆性或特征，每組內的模式都是相似的，而與其他組的模式差別大。一類主要方法是根據各個待分類模式的屆性或特征相似

2、程度進行分類，相似的歸為一類，由此將待分類的模式集分成若十個互不重疊的子集，另一類主要方法是定義適當?shù)臏蕜t函數(shù)運用有關的數(shù)學工具進行分類。由于在分類中不需要用訓練樣本進行學習和訓練，故此類方法稱為無監(jiān)督分類。聚類的目的是使得不同類別的個體之間的差別盡可能的大，而同類別的個體之間的差別盡可能的小。聚類乂被稱為非監(jiān)督分類，因為和分類學習相比，分類學習的對象或例子有類別標記，而要聚類的例子沒有標記，需要由聚類分析算法來自動確定，即把所有樣本作為未知樣本進行聚類。因此，分類問題和聚類問題根本不同點為：在分類問題中，知道訓練樣本例的分類屆性值，而在聚類問題中，需要在訓練樣例中找到這個分類屆性值。聚類分析

3、的基本思想是認為研究的樣本或變量之間存在著程度不同的相似性（親疏關系）。研究樣本或變量的親疏程度的數(shù)量指標有兩種：一種叫相似系數(shù)，性質越接近的樣本或變量，它們的相似系數(shù)越接近1或-1,而彼此無關的變量或樣本它們的相似系數(shù)越接近0,相似的為一類，不相似的為不同類。另一種叫距離，它是將每一個樣本看做p維空間的一個點，并用某種度量測量點與點之間的距離，距離較近的歸為一類，距離較遠的點應屆丁不同的類。2.2動態(tài)聚類法思想動態(tài)聚類方法、亦稱逐步聚類法.一類聚類法.屆丁大樣本聚類法。具體作法是：先粗略地進行預分類，然后再逐步調整，直到把類分得比較合理為止。這種分類方法較之系統(tǒng)聚類法，具有計算量較小、占用計

4、算機存貯單元少、方法簡單等優(yōu)點，所以更適用丁大樣本的聚類分析，是一種普遍被采用的方法。這種方法具有以下三個要素：(1) 選定某種距離度量作為樣本間的相似性度量；確定某種可以評價聚類結果質量的準則函數(shù)；給定某個初始分類，然后用迭代算法找出使得準則函數(shù)取極值的最好聚類結果。動態(tài)聚類法在計算迭代過程中，類心會隨著迭代次數(shù)進行修正和改變。動態(tài)聚類法的基本步驟：(1) 選取初始聚類中心及有關參數(shù)，進行初始聚類。(2) 計算模式和聚類的距離，調整模式的類別。(3) 計算各聚類的參數(shù)，刪除，合并或分裂一些聚類。(4) 從初始聚類開始，運用迭代算法動態(tài)地改變模式的類別和聚類的中心，使準則函數(shù)取極值或設定的參數(shù)

5、達到設計要求時停止。2.3K-均值聚類算法的思想K-均值算法是一種基丁劃分的聚類算法，它通過不斷的迭代過程來進行聚類，當算法收斂到一個結束條件時就終止迭代過程，輸出聚類結果。由丁其算法思想簡便,乂容易實現(xiàn)，因此K一均值算法己成為一種目前最常用的聚類算法之一。K-均值算法解決的是將含有n個數(shù)據點(實體)的集合Xx1,x2,.,xn)戈U分為k個類Cj的問題，其中j1,2,.,k，算法首先隨機選取k個數(shù)據點作為k個類的初始類中心，集合中每個數(shù)據點被劃分到與其距離最近的類中心所在的類中，形成了k個聚類的初始分布。對分配完的每一個類計算新的類中心，然后繼續(xù)進行數(shù)據分配的過程，這樣迭代若干次之后，若類中

6、心不再發(fā)生變化，則說明數(shù)據對象全部分配到自己所在的類中，證明函數(shù)收斂。在每一次的迭代過程中都要對全體數(shù)據點的分配進行調整，然后重新計算類中心，進入下一次迭代過程，若在某一次迭代過程中，所有數(shù)據點的位置沒有變化，相應的類中心也沒有變化，此時標志著聚類準則函數(shù)已經收斂，算法結束。通常采用的目標函數(shù)形式為平方誤差準則函數(shù)：Ci其中，xi為數(shù)據對象，Ci表示類Ci的質心,E則表示數(shù)據集中所有對象的誤差平方和。該目標函數(shù)采用歐氏距離。K-均值聚類算法的過程描述如下:(1)任選k個模式特征欠量作為初始聚類中心:Zi(0),z20),.,zC0)，令k=0.(2)將待分類的模式識別特征欠量集x：中的模式逐個

7、按最小距離原則分劃給k類中的某一類，即(k)(k)(k1)如果diimindj,i1,2,.,N，則判xii式中，dj(k)表示為和jk)的中心z(k)的距離，上標表示迭代次數(shù)，丁是產生新的聚類(k1),j1,2,.,k計算重新分類后的各類心zjk1)41)X，j1,2,.,knjx(k1)(k1)(kD式中，n()為j類中所含模式的個數(shù)。(3) (k1)-,(k)/如木ZjZj(j1,2,.,k)，貝形口界，白貝LkkI,持土少糠(2)。3. 結果分析在二維和三維空間里，原樣本點為藍色，隨機選取樣本點中的四個點作為中心，用*表示，其他對象根據與這四個聚類中心(對象)的距離，根據最近距離原則，

8、逐個分別聚類到這四個聚類中心所代表的聚類中，每完成一輪聚類，聚類的中心會發(fā)生相應的改變，之后更新這四個聚類的聚類中心，根據所獲得的四個新聚類中心，以及各對象與這四個聚類中心的距離，根據最近距離原則，對所有對象進行重新歸類。再次重復上述過程就可獲得聚類結果，當各聚類中的對象(歸屆)已不再變化，整個聚類操作結束。經過K均值聚類計算，樣本點分為紅，藍，綠，黑四個聚類，計算出新的四個聚類中心，用*表示。該算法中，一次迭代中把每個數(shù)據對象分到離它最近的聚類中心所在類，這個過程的時間復雜度O(nkd)，這里的n指的是總的數(shù)據對象個數(shù)，k是指定的聚類數(shù)，d是數(shù)據對象的位數(shù)：新的分類產生后需要計算新的聚類中心

9、，這個過程的時間復雜度為O(nd)。因此，這個算法一次迭代后所需要的總的時間復雜度為O(nkd).通過實驗可以看出，k個初始聚類中心點的選取對聚類結果有較大的影響，因為在該算法中是隨機地任意選取k個點作為初始聚類中心，分類結果受到取定的類別數(shù)目和聚類中心初始位置的影響，所以結果只是局部最優(yōu)。K-均值算法常采用誤差平方和準則函數(shù)作為聚類準則函數(shù)(目標函數(shù)).目標函數(shù)在空間狀態(tài)是一個非凸函數(shù)，非凸函數(shù)往往存在很多個局部極小值，只有一個是全局最小。所以通過迭代計算，目標函數(shù)常常達到局部最小而難以得到全局最小。聚類個數(shù)k的選定是很難估計的，很多時候我們事先并不知道給定的數(shù)據集應該分成多少類才合適。關丁

10、K-均值聚類算法中聚類數(shù)據k值得確定，有些根據方差分析理論，應用混合F統(tǒng)計量來確定最佳分類樹，并應用了模糊劃分嫡來驗證最佳分類的準確性。將類的質心（均值點）作為聚類中心進行新一輪聚類計算，將導致遠離數(shù)據密集區(qū)的孤立點和噪聲點會導致聚類中心偏離真正的數(shù)據密集區(qū)，所以K-均值算法對噪聲點和孤立點非常敏感。圖1為未聚類前初始樣本及中心，圖2為聚類后的樣本及中心。磯結聚晃中與-1C圖1未聚類前初始樣本及中心湘，聚奧，心6也圖1聚類后的樣本及中心4. 程序：clear;clc;TH=0.001;N=20;n=0;th=1;嘟一類數(shù)據mu1=000;%均值S1=300;030;003;%協(xié)方差矩陣X1=m

11、vnrnd(mu1,S1,50);%T生多維正態(tài)隨機數(shù)，mul為期望向量，s1為協(xié)方差矩陣,50為規(guī)模嘟一類數(shù)據mu2=444;%均值S2=000;030;003;%協(xié)方差矩陣X2=mvnrnd(mu2,S2,50);%第一類數(shù)據mu3=-44-4;%均值S3=300;030;003;%協(xié)方差矩陣X3=mvnrnd(mu3,S3,50);X=X1;X2;X3;%三類數(shù)據合成一個不帶標號的數(shù)據類plot3(X(:,1),X(:,2),X(:,3),'+');咖示holdongridontitle('初始聚類中心);k=4;count,d=size(X);centers=X

12、(round(rand(k,1)*count),:);id=zeros(count,1);%會出聚類中心plot3(centers(:,1),centers(:,2),centers(:,3),'kx''MarkerSize',10,'LineWidth',2)plot3(centers(:,1),centers(:,2),centers(:,3),'ko'MarkerSize',10,'LineWidth',2)dist=zeros(k,1);newcenters=zeros(k,d);while(n&l

13、t;N&&th>TH)%whilen<Nforix=1:countforik=1:kdist(ik)=sum(X(ix,:)-centers(ik,:).A2);end,tmp=sort(dist);%離哪個類最近則屆于那個類id(ix)=tmp(1);endth=0;forik=1:kidtmp=find(id=ik);iflength(idtmp)=0returnendnewcenters(ik,:)=sum(X(idtmp,:),1)./length(idtmp);th=th+sum(newcenters(ik,:)-centers(ik,:).A2);end

14、centers=newcenters;n=n+1;endfigure(2)plot3(X(find(id=1),1),X(find(id=1),2),X(find(id=1),3),'r*'),holdonplot3(X(find(id=2),1),X(find(id=2),2),X(find(id=2),3),'g*'),holdonplot3(X(find(id=3),1),X(find(id=3),2),X(find(id=3),3),'b*'),holdonplot3(X(find(id=4),1),X(find(id=4),2),X(find(id=4),3),'k*'),holdontitle(&#