KMEANS算法K均值算法

1、k-means算法一算法簡介k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類算法。 它是將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點，算法的主要思想是通過迭代過程把數(shù)據(jù)集劃分為不同的類別，使得評價聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的每個聚類內(nèi)緊湊，類間獨立。這一算法不適合處理離散型屬性，但是對于連續(xù)型具有較好的聚類效果。二劃分聚類方法對數(shù)據(jù)集進(jìn)行聚類時包括如下三個要點：（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量k-means聚類算法不適合處理離散型屬性，對連續(xù)型屬性比較適合。因此在計算數(shù)據(jù)樣本之間的距離時，可以根據(jù)實際需要選擇歐式距離、曼哈頓距離或者明

2、考斯距離中的一種來作為算法的相似性度量，其中最常用的是歐式距離。下面我給大家具體介紹一下歐式距離。假設(shè)給定的數(shù)據(jù)集 ，X中的樣本用d個描述屬性A1,A2Ad來表示，并且d個描述屬性都是連續(xù)型屬性。數(shù)據(jù)樣本xi=(xi1,xi2,xid), xj=(xj1,xj2,xjd)其中，xi1,xi2,xid和xj1,xj2,xjd分別是樣本xi和xj對應(yīng)d個描述屬性A1,A2,Ad的具體取值。樣本xi和xj之間的相似度通常用它們之間的距離d(xi,xj)來表示，距離越小，樣本xi和xj越相似，差異度越??；距離越大，樣本xi和xj越不相似，差異度越大。歐式距離公式如下：（2）選擇評價聚類性能的準(zhǔn)則函數(shù)k

3、-means聚類算法使用誤差平方和準(zhǔn)則函數(shù)來評價聚類性能。給定數(shù)據(jù)集X，其中只包含描述屬性，不包含類別屬性。假設(shè)X包含k個聚類子集X1,X2,XK；各個聚類子集中的樣本數(shù)量分別為n1，n2,nk;各個聚類子集的均值代表點（也稱聚類中心）分別為m1，m2,mk。則誤差平方和準(zhǔn)則函數(shù)公式為：（3）相似度的計算根據(jù)一個簇中對象的平均值來進(jìn)行。1) 將所有對象隨機(jī)分配到k個非空的簇中。2) 計算每個簇的平均值，并用該平均值代表相應(yīng)的簇。3) 根據(jù)每個對象與各個簇中心的距離，分配給最近的簇。4) 然后轉(zhuǎn)2），重新計算每個簇的平均值。這個過程不斷重復(fù)直到滿足某個準(zhǔn)則函數(shù)才停止。三算法描述 1. 為中心向量

4、c1, c2, , ck初始化k個種子 2. 分組:a) 將樣本分配給距離其最近的中心向量 b) 由這些樣本構(gòu)造不相交（ non-overlapping ）的聚類 3. 確定中心:a) 用各個聚類的中心向量作為新的中心 4. 重復(fù)分組和確定中心的步驟，直至算法收斂四算法流程輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫。輸出：k個簇，使平方誤差準(zhǔn)則最小。 算法步驟： 1.為每個聚類確定一個初始聚類中心，這樣就有K 個初始聚類中心。 2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類 3.使用每個聚類中的樣本均值作為新的聚類中心。4.重復(fù)步驟2.3步直到聚類中心不再變化。5.結(jié)束，得到K個聚類 OXY

5、10220031.50450552五算法舉例數(shù)據(jù)對象集合S見表1，作為一個聚類分析的二維樣本，要求的簇的數(shù)量k=2。(1)選擇 ， 為初始的簇中心，即 ，(2)對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇。 對 ：顯然 ，故將 分配給對于 ： 因為 ，所以將 分配給對于 ：因為 ，所以將 分配給 更新，得到新簇 和 計算平方誤差準(zhǔn)則，單個方差為總體平均方差是：（3）計算新的簇的中心。 重復(fù)（2）和（3），得到O1分配給C1；O2分配給C2，O3分配給C2 ，O4分配給C2，O5分配給C1。更新，得到新簇 和 。 中心為 ， 。 單個方差分別為總體平均誤差是：由上可以看出，第一次

6、迭代后，總體平均誤差值52.2525.65，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。 六k-means算法的性能分析6.1 k-means算法的優(yōu)缺點主要優(yōu)點：1. 是解決聚類問題的一種經(jīng)典算法，簡單、快速。2. 對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。因為它的復(fù)雜度是0 (n k t ) , 其中, n 是所有對象的數(shù)目, k 是簇的數(shù)目, t 是迭代的次數(shù)。通常k < <n 且t < <n 。3. 當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時, 它的效果較好。主要缺點1. 在簇的平均值被定義的情況下才能使用，這對于處理符號屬性的數(shù)據(jù)不適

7、用。2. 必須事先給出k（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導(dǎo)致不同結(jié)果。 3. 它對于“躁聲”和孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。針對K-Means算法對于不同的初始值，可能會導(dǎo)致不同結(jié)果。解決方法： 1.多設(shè)置一些不同的初值，對比最后的運算結(jié)果）一直到結(jié)果趨于穩(wěn)定結(jié)束，比較耗時和浪費資源 2.很多時候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個類別才最合適。這也是 K-means 算法的一個不足。有的算法是通過類的自動合并和分裂，得到較為合理的類型數(shù)目 K，例如 ISODATA 算法。 3. 所謂的gapstatistics（ Gap統(tǒng)計模

8、型） 6.2 ISODATA算法6.2.1 ISODATA算法與K-均值算法的比較：1. K-均值算法通常適合于分類數(shù)目已知的聚類，而ISODATA算法則更加靈活；2. 從算法角度看， ISODATA算法與K-均值算法相似，聚類中心都是通過樣本均值的迭代運算來決定的；3. ISODATA算法加入了一些試探步驟，并且可以結(jié)合成人機(jī)交互的結(jié)構(gòu)，使其能利用中間結(jié)果所取得的經(jīng)驗更好地進(jìn)行分類。主要是在選代過程中可將一類一分為二，亦可能二類合二為一，即“自組織”，這種算法具有啟發(fā)式的特點。6.2.2 ISODATA算法與K-means相比在下列幾方面有改進(jìn)： 1.考慮了類別的合并與分裂，因而有了自我調(diào)整

9、類別數(shù)的能力。合并主要發(fā)生在某一類內(nèi)樣本個數(shù)太少的情況，或兩類聚類中心之間距離太小的情況。為此設(shè)有最小類內(nèi)樣本數(shù)限制 ，以及類間中心距離參數(shù) 。若出現(xiàn)兩類聚類中心距離小于的情況，可考慮將此兩類合并。分裂則主要發(fā)生在某一類別的某分量出現(xiàn)類內(nèi)方差過大的現(xiàn)象，因而宜分裂成兩個類別，以維持合理的類內(nèi)方差。給出一個對類內(nèi)分量方差的限制參數(shù) ，用以決定是否需要將某一類分裂成兩類。2.由于算法有自我調(diào)整的能力，因而需要設(shè)置若干個控制用參數(shù)，如聚類數(shù)期望值K、每次迭代允許合并的最大聚類對數(shù)L、及允許迭代次數(shù)I等。6.2.3 ISODATA算法基本步驟和思路ü 選擇某些初始值?？蛇x不同的參數(shù)指標(biāo)，也可

10、在迭代過程中人為修改，以將N個模式樣本按指標(biāo)分配到各個聚類中心中去。ü 計算各類中諸樣本的距離指標(biāo)函數(shù)。ü （3）（5）按給定的要求，將前一次獲得的聚類集進(jìn)行分裂和合并處理（4）為分裂處理，（5）為合并處理），從而獲得新的聚類中心。ü 重新進(jìn)行迭代運算，計算各項指標(biāo)，判斷聚類結(jié)果是否符合要求。經(jīng)過多次迭代后，若結(jié)果收斂，則運算結(jié)束。6.3 k-means算法初始中心的選取對算法的影響棋盤格數(shù)據(jù)集(Checkerboard data set)僅使用其中486個正類數(shù)據(jù)，并將數(shù)據(jù)變換到-1,1之間，分布情況如下圖所示：原始數(shù)據(jù) 初始聚類中心均在中心附近初始聚類中心在平

11、面內(nèi)隨機(jī)選取七k-means算法的改進(jìn)方法7.1 k-means算法的改進(jìn)方法k-mode 算法u k-modes 算法：實現(xiàn)對離散數(shù)據(jù)的快速聚類，保留了k-means算法的效率同時將k-means的應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)。u K-modes算法是按照k-means算法的核心內(nèi)容進(jìn)行修改，針對分類屬性的度量和更新質(zhì)心的問題而改進(jìn)。具體如下:1.度量記錄之間的相關(guān)性D的計算公式是比較兩記錄之間，屬性相同為0，不同為1.并所有相加。因此D越大，即他的不相關(guān)程度越強(qiáng)（與歐式距離代表的意義是一樣的）；2.更新modes，使用一個簇的每個屬性出現(xiàn)頻率最大的那個屬性值作為代表簇的屬性值。7.2 k-mea

12、ns算法的改進(jìn)方法k-prototype算法u k-Prototype算法：可以對離散與數(shù)值屬性兩種混合的數(shù)據(jù)進(jìn)行聚類，在k-prototype中定義了一個對數(shù)值與離散屬性都計算的相異性度量標(biāo)準(zhǔn)。u K-Prototype算法是結(jié)合K-Means與K-modes算法，針對混合屬性的，解決2個核心問題如下：1.度量具有混合屬性的方法是，數(shù)值屬性采用K-means方法得到P1，分類屬性采用K-modes方法P2，那么D=P1+a*P2，a是權(quán)重，如果覺得分類屬性重要，則增加a，否則減少a，a=0時即只有數(shù)值屬性2.更新一個簇的中心的方法，方法是結(jié)合K-Means與K-modes的更新方法。7.3

13、k-means算法的改進(jìn)方法k-中心點算法k-中心點算法：k -means算法對于孤立點是敏感的。為了解決這個問題，不采用簇中的平均值作為參照點，可以選用簇中位置最中心的對象，即中心點作為參照點。這樣劃分方法仍然是基于最小化所有對象與其參照點之間的相異度之和的原則來執(zhí)行的。 八K-means算法在圖像分割上的簡單應(yīng)用例1：圖片：一只遙望大海的小狗；此圖為100 x 100像素的JPG圖片，每個像素可以表示為三維向量（分別對應(yīng)JPEG圖像中的紅色、綠色和藍(lán)色通道）；將圖片分割為合適的背景區(qū)域（三個）和前景區(qū)域（小狗）； 1. 使用K-means算法對圖像進(jìn)行分割。 分割后的效果（注：最大迭代次數(shù)

14、為20次，需運行多次才有可能得到較好的效果。）例2：注：聚類中心個數(shù)為5，最大迭代次數(shù)為10。聚類中心個數(shù)為3（程序如下）clcclearticRGB= imread ('test5.jpg'); %讀入像img=rgb2gray(RGB);m,n=size(img);subplot(2,2,1),imshow(img);title(' 圖一 原圖像')subplot(2,2,2),imhist(img);title(' 圖二 原圖像的灰度直方圖')hold off;img=double(img);for i=1:200 c1(1)=25; c2

15、(1)=125; c3(1)=200;%選擇三個初始聚類中心 r=abs(img-c1(i); g=abs(img-c2(i); b=abs(img-c3(i);%計算各像素灰度與聚類中心的距離 r_g=r-g; g_b=g-b; r_b=r-b; n_r=find(r_g<=0&r_b<=0);%尋找最小的聚類中心 n_g=find(r_g>0&g_b<=0);%尋找中間的一個聚類中心 n_b=find(g_b>0&r_b>0);%尋找最大的聚類中心 i=i+1; c1(i)=sum(img(n_r)/length(n_r);%將所有低灰度求和取平均，作為下一個低灰度中心 c2(i)=sum(img(n_g)/length(n_g);%將所有低灰度求和取平均，作為下一個中間灰度中心 c3(i)=sum(img(n_b)/length(n_b);%將所有低灰度求和取平均，作為下一個高灰度中心 d1(i)=abs(c1(i)-c1(i-1); d2(i)=abs(c2(i)-c2(i-1); d3(i)=abs(c3(i)-c3(i-1); if d1(i)<=0.001&&d2(i)<=0.001&&d3(i)<=0.001 R=c1(i);