K-均值聚類分析

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

2、分成若干個互不重疊的子集，另一類主要方法是定義適當(dāng)?shù)臏?zhǔn)則函數(shù)運用有關(guān)的數(shù)學(xué)工具進(jìn)行分類。由于在分類中不需要用訓(xùn)練樣本進(jìn)行學(xué)習(xí)和訓(xùn)練，故此類方法稱為無監(jiān)督分類。聚類的目的是使得不同類別的個體之間的差別盡可能的大，而同類別的個體之間的差別盡可能的小。聚類又被稱為非監(jiān)督分類，因為和分類學(xué)習(xí)相比，分類學(xué)習(xí)的對象或例子有類別標(biāo)記，而要聚類的例子沒有標(biāo)記，需要由聚類分析算法來自動確定，即把所有樣本作為未知樣本進(jìn)行聚類。因此，分類問題和聚類問題根本不同點為：在分類問題中，知道訓(xùn)練樣本例的分類屬性值，而在聚類問題中，需要在訓(xùn)練樣例中找到這個分類屬性值。聚類分析的基本思想是認(rèn)為研究的樣本或變量之間存在著程度不同

3、的相似性（親疏關(guān)系）。研究樣本或變量的親疏程度的數(shù)量指標(biāo)有兩種：一種叫相似系數(shù)，性質(zhì)越接近的樣本或變量，它們的相似系數(shù)越接近1或-1，而彼此無關(guān)的變量或樣本它們的相似系數(shù)越接近0，相似的為一類，不相似的為不同類。另一種叫距離，它是將每一個樣本看做p維空間的一個點，并用某種度量測量點與點之間的距離，距離較近的歸為一類，距離較遠(yuǎn)的點應(yīng)屬于不同的類。2.2動態(tài)聚類法思想動態(tài)聚類方法、亦稱逐步聚類法.一類聚類法.屬于大樣本聚類法。具體作法是:先粗略地進(jìn)行預(yù)分類，然后再逐步調(diào)整，直到把類分得比較合理為止。這種分類方法較之系統(tǒng)聚類法，具有計算量較小、占用計算機(jī)存貯單元少、方法簡單等優(yōu)點，所以更適用于大樣本

4、的聚類分析，是一種普遍被采用的方法。這種方法具有以下三個要素：(1) 選定某種距離度量作為樣本間的相似性度量；(2) 確定某種可以評價聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)；(3) 給定某個初始分類，然后用迭代算法找出使得準(zhǔn)則函數(shù)取極值的最好聚類結(jié)果。動態(tài)聚類法在計算迭代過程中，類心會隨著迭代次數(shù)進(jìn)行修正和改變。動態(tài)聚類法的基本步驟：(1) 選取初始聚類中心及有關(guān)參數(shù)，進(jìn)行初始聚類。(2) 計算模式和聚類的距離，調(diào)整模式的類別。(3) 計算各聚類的參數(shù)，刪除，合并或分裂一些聚類。(4) 從初始聚類開始，運用迭代算法動態(tài)地改變模式的類別和聚類的中心，使準(zhǔn)則函數(shù)取極值或設(shè)定的參數(shù)達(dá)到設(shè)計要求時停止。2.3K-均值

5、聚類算法的思想K-均值算法是一種基于劃分的聚類算法，它通過不斷的迭代過程來進(jìn)行聚類，當(dāng)算法收斂到一個結(jié)束條件時就終止迭代過程，輸出聚類結(jié)果。由于其算法思想簡便，又容易實現(xiàn)，因此K一均值算法己成為一種目前最常用的聚類算法之一。K-均值算法解決的是將含有n個數(shù)據(jù)點(實體)的集合 劃分為k個類 的問題，其中 ，算法首先隨機(jī)選取k個數(shù)據(jù)點作為k個類的初始類中心，集合中每個數(shù)據(jù)點被劃分到與其距離最近的類中心所在的類中，形成了k個聚類的初始分布。對分配完的每一個類計算新的類中心，然后繼續(xù)進(jìn)行數(shù)據(jù)分配的過程，這樣迭代若干次之后，若類中心不再發(fā)生變化，則說明數(shù)據(jù)對象全部分配到自己所在的類中，證明函數(shù)收斂。在每

6、一次的迭代過程中都要對全體數(shù)據(jù)點的分配進(jìn)行調(diào)整，然后重新計算類中心，進(jìn)入下一次迭代過程，若在某一次迭代過程中，所有數(shù)據(jù)點的位置沒有變化，相應(yīng)的類中心也沒有變化，此時標(biāo)志著聚類準(zhǔn)則函數(shù)已經(jīng)收斂，算法結(jié)束。通常采用的目標(biāo)函數(shù)形式為平方誤差準(zhǔn)則函數(shù)： 其中， 為數(shù)據(jù)對象， 表示類 的質(zhì)心，E則表示數(shù)據(jù)集中所有對象的誤差平方和。該目標(biāo)函數(shù)采用歐氏距離。K-均值聚類算法的過程描述如下：(1) 任選k個模式特征矢量作為初始聚類中心： ，令k=0.(2) 將待分類的模式識別特征矢量集 中的模式逐個按最小距離原則分劃給k類中的某一類，即 如果 ， ，則判 式中， 表示 和 的中心 的距離，上標(biāo)表示迭代次數(shù)，于

7、是產(chǎn)生新的聚類 (3) 計算重新分類后的各類心 式中，為類中所含模式的個數(shù)。(4) 如果 ，則結(jié)束；否則， ，轉(zhuǎn)至步驟（2）。3.結(jié)果分析在二維和三維空間里，原樣本點為藍(lán)色，隨機(jī)選取樣本點中的四個點作為中心，用*表示，其他對象根據(jù)與這四個聚類中心（對象）的距離，根據(jù)最近距離原則，逐個分別聚類到這四個聚類中心所代表的聚類中，每完成一輪聚類，聚類的中心會發(fā)生相應(yīng)的改變，之后更新這四個聚類的聚類中心，根據(jù)所獲得的四個新聚類中心，以及各對象與這四個聚類中心的距離，根據(jù)最近距離原則，對所有對象進(jìn)行重新歸類。再次重復(fù)上述過程就可獲得聚類結(jié)果，當(dāng)各聚類中的對象（歸屬）已不再變化，整個聚類操作結(jié)束。經(jīng)過K均值

8、聚類計算，樣本點分為紅，藍(lán)，綠，黑四個聚類，計算出新的四個聚類中心，用*表示。該算法中，一次迭代中把每個數(shù)據(jù)對象分到離它最近的聚類中心所在類，這個過程的時間復(fù)雜度O(nkd)，這里的n指的是總的數(shù)據(jù)對象個數(shù)，k是指定的聚類數(shù)，d是數(shù)據(jù)對象的位數(shù)：新的分類產(chǎn)生后需要計算新的聚類中心，這個過程的時間復(fù)雜度為O(nd)。因此，這個算法一次迭代后所需要的總的時間復(fù)雜度為O(nkd). 通過實驗可以看出，k個初始聚類中心點的選取對聚類結(jié)果有較大的影響，因為在該算法中是隨機(jī)地任意選取k個點作為初始聚類中心，分類結(jié)果受到取定的類別數(shù)目和聚類中心初始位置的影響，所以結(jié)果只是局部最優(yōu)。K-均值算法常采用誤差平方

9、和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)(目標(biāo)函數(shù)).目標(biāo)函數(shù)在空間狀態(tài)是一個非凸函數(shù)，非凸函數(shù)往往存在很多個局部極小值，只有一個是全局最小。所以通過迭代計算，目標(biāo)函數(shù)常常達(dá)到局部最小而難以得到全局最小。 聚類個數(shù)k的選定是很難估計的，很多時候我們事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少類才合適。關(guān)于K-均值聚類算法中聚類數(shù)據(jù)k值得確定，有些根據(jù)方差分析理論，應(yīng)用混合F統(tǒng)計量來確定最佳分類樹，并應(yīng)用了模糊劃分熵來驗證最佳分類的準(zhǔn)確性。將類的質(zhì)心（均值點）作為聚類中心進(jìn)行新一輪聚類計算，將導(dǎo)致遠(yuǎn)離數(shù)據(jù)密集區(qū)的孤立點和噪聲點會導(dǎo)致聚類中心偏離真正的數(shù)據(jù)密集區(qū)，所以K-均值算法對噪聲點和孤立點非常敏感。圖1為未聚類前

10、初始樣本及中心，圖2為聚類后的樣本及中心。圖1 未聚類前初始樣本及中心圖1 聚類后的樣本及中心4程序：clear;clc; TH = 0.001;N = 20; n = 0;th = 1;%第一類數(shù)據(jù)mu1=0 0 0; % 均值S1=3 0 0;0 3 0;0 0 3;% 協(xié)方差矩陣X1=mvnrnd(mu1,S1,50); %產(chǎn)生多維正態(tài)隨機(jī)數(shù)，mul為期望向量，s1為協(xié)方差矩陣，50為規(guī)模%第一類數(shù)據(jù)mu2=4 4 4;% 均值S2=0 0 0;0 3 0;0 0 3;% 協(xié)方差矩陣X2=mvnrnd(mu2,S2,50);%第一類數(shù)據(jù)mu3=-4 4 -4;% 均值S3=3 0 0;0

11、 3 0;0 0 3;% 協(xié)方差矩陣X3=mvnrnd(mu3,S3,50); X=X1;X2;X3; %三類數(shù)據(jù)合成一個不帶標(biāo)號的數(shù)據(jù)類 plot3(X(:,1),X(:,2),X(:,3),'+');%顯示hold ongrid ontitle('初始聚類中心');k=4;count,d = size(X); centers=X(round(rand(k,1)*count),:); id = zeros(count,1); %會出聚類中心plot3(centers(:,1),centers(:,2),centers(:,3),'kx',. &

12、#39;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 < N && th > TH) %while n<N for ix = 1:count for ik = 1:k dist(ik) = sum(X(ix,:

13、)-centers(ik,:).2); end ,tmp=sort(dist); %離哪個類最近則屬于那個類 id(ix) =tmp(1); endth = 0;for ik = 1:k idtmp = find(id = ik); if length(idtmp) = 0 return; end newcenters(ik,:)= sum(X(idtmp,:),1)./length(idtmp); th = th + sum(newcenters(ik,:) - centers(ik,:).2);endcenters = newcenters;n = n+1;end figure(2)plo

14、t3(X(find(id=1),1),X(find(id=1),2),X(find(id=1),3),'r*'),hold onplot3(X(find(id=2),1),X(find(id=2),2),X(find(id=2),3),'g*'),hold onplot3(X(find(id=3),1),X(find(id=3),2),X(find(id=3),3),'b*'),hold onplot3(X(find(id=4),1),X(find(id=4),2),X(find(id=4),3),'k*'),hold ontitle('最終聚類中心')