均值聚類分析

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

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

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

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

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

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

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

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

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