K-MEANS(K均值聚類(lèi)算法-C均值算法)ppt課件

1、主講內(nèi)容,算法性能分析,算法改進(jìn),算法簡(jiǎn)介,算法應(yīng)用,算法要點(diǎn),算法描述,算法實(shí)例,ISODATA算法,gapstatistics,算法簡(jiǎn)介,k-means算法，也被稱(chēng)為k-平均或k-均值，是一種得到最廣泛使用的聚類(lèi)算法。 它是將各個(gè)聚類(lèi)子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類(lèi)的代表點(diǎn)，算法的主要思想是通過(guò)迭代過(guò)程把數(shù)據(jù)集劃分為不同的類(lèi)別，使得評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的每個(gè)聚類(lèi)內(nèi)緊湊，類(lèi)間獨(dú)立。這一算法不適合處理離散型屬性，但是對(duì)于連續(xù)型具有較好的聚類(lèi)效果,算法描述 為中心向量c1, c2, , ck初始化k個(gè)種子 分組: 將樣本分配給距離其最近的中心向量 由這些樣本構(gòu)造不相交（

2、 non-overlapping ）的聚類(lèi) 確定中心: 用各個(gè)聚類(lèi)的中心向量作為新的中心 重復(fù)分組和確定中心的步驟，直至算法收斂,算法 k-means算法 輸入：簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。 輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小。 算法步驟： 1.為每個(gè)聚類(lèi)確定一個(gè)初始聚類(lèi)中心，這樣就有K 個(gè)初始聚類(lèi)中心。 2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類(lèi) 3.使用每個(gè)聚類(lèi)中的樣本均值作為新的聚類(lèi)中心。 4.重復(fù)步驟2.3直到聚類(lèi)中心不再變化。 5.結(jié)束，得到K個(gè)聚類(lèi),2021/1/28,將樣本分配給距離它們最近的中心向量，并使目標(biāo)函數(shù)值減小,更新簇平均值,計(jì)算準(zhǔn)則函數(shù)E,K-means

3、聚類(lèi)算法,劃分聚類(lèi)方法對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)時(shí)包括如下 三個(gè)要點(diǎn)： （1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量 上面講到，k-means聚類(lèi)算法不適合處理離散型 屬性，對(duì)連續(xù)型屬性比較適合。因此在計(jì)算數(shù)據(jù)樣本之間的距離時(shí)，可以根據(jù)實(shí)際需要選擇歐式距離、曼哈頓距離或者明考斯距離中的一種來(lái)作為算法的相似性度量，其中最常用的是歐式距離。下面我給大家具體介紹一下歐式距離,假設(shè)給定的數(shù)據(jù)集 ，X中的樣本用d個(gè)描述屬性A1,A2Ad來(lái)表示，并且d個(gè)描述屬性都是連續(xù)型屬性。數(shù)據(jù)樣本xi=(xi1,xi2,xid), xj=(xj1,xj2,xjd)其中， xi1,xi2,xid和xj1,xj2,xjd分別是樣本

4、xi和xj對(duì)應(yīng)d個(gè)描述屬性A1,A2,Ad的具體取值。樣本xi和xj之間的相似度通常用它們之間的距離d(xi,xj)來(lái)表示，距離越小，樣本xi和xj越相似，差異度越?。痪嚯x越大，樣本xi和xj越不相似，差異度越大。 歐式距離公式如下,2）選擇評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù) k-means聚類(lèi)算法使用誤差平方和準(zhǔn)則函數(shù)來(lái) 評(píng)價(jià)聚類(lèi)性能。給定數(shù)據(jù)集X，其中只包含描述屬性，不包含類(lèi)別屬性。假設(shè)X包含k個(gè)聚類(lèi)子集X1,X2,XK；各個(gè)聚類(lèi)子集中的樣本數(shù)量分別為n1，n2,nk;各個(gè)聚類(lèi)子集的均值代表點(diǎn)（也稱(chēng)聚類(lèi)中心）分別為m1，m2,mk。則誤差平方和準(zhǔn)則函數(shù)公式為,3）相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值

5、來(lái)進(jìn)行。 （1）將所有對(duì)象隨機(jī)分配到k個(gè)非空的簇中。 （2）計(jì)算每個(gè)簇的平均值，并用該平均值代表相應(yīng)的簇。 （3）根據(jù)每個(gè)對(duì)象與各個(gè)簇中心的距離，分配給最近的簇。 （4）然后轉(zhuǎn)（2），重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)直到滿(mǎn)足某個(gè)準(zhǔn)則函數(shù)才停止,數(shù)據(jù)對(duì)象集合S見(jiàn)表1，作為一個(gè)聚類(lèi)分析的二維樣本，要求的簇的數(shù)量k=2。 (1)選擇 ， 為初始的簇中心，即 ， 。 (2)對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。 對(duì),顯然 ，故將 分配給,例子,對(duì)于 ： 因?yàn)?所以將 分配給 對(duì)于 ： 因?yàn)?所以將 分配給 更新，得到新簇 和 計(jì)算平方誤差準(zhǔn)則，單個(gè)方差為,總體平均方差是

6、： （3）計(jì)算新的簇的中心,重復(fù)（2）和（3），得到O1分配給C1；O2分配給C2，O3分配給C2 ，O4分配給C2，O5分配給C1。更新，得到新簇 和 。 中心為 ， 。 單個(gè)方差分別為,總體平均誤差是,由上可以看出，第一次迭代后，總體平均誤差值52.2525.65，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過(guò)程，算法停止,k-means算法的性能分析,主要優(yōu)點(diǎn)： 是解決聚類(lèi)問(wèn)題的一種經(jīng)典算法，簡(jiǎn)單、快速。 對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。因?yàn)樗膹?fù)雜度是0 (n k t ) , 其中, n 是所有對(duì)象的數(shù)目, k 是簇的數(shù)目, t 是迭代的次數(shù)。通常k n 且t n

7、 。 當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí), 它的效果較好。 主要缺點(diǎn) 在簇的平均值被定義的情況下才能使用，這對(duì)于處理符號(hào)屬性的數(shù)據(jù)不適用。 必須事先給出k（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果,K-Means算法對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。解決方法： 1.多設(shè)置一些不同的初值，對(duì)比最后的運(yùn)算結(jié)果）一直到結(jié)果趨于穩(wěn)定結(jié)束，比較耗時(shí)和浪費(fèi)資源 2.很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類(lèi)別才最合適。這也是 K-means 算法的一個(gè)不足。有的算法是通過(guò)類(lèi)的自動(dòng)合并和分裂，得到較為合理的類(lèi)型數(shù)目 K，例如 ISODATA 算法。 3. 所

8、謂的gapstatistics（ Gap統(tǒng)計(jì)模型,它對(duì)于“躁聲”和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類(lèi)數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響,ISODATA算法,與K-均值算法的比較 K-均值算法通常適合于分類(lèi)數(shù)目已知的聚類(lèi)，而ISODATA算法則更加靈活； 從算法角度看， ISODATA算法與K-均值算法相似，聚類(lèi)中心都是通過(guò)樣本均值的迭代運(yùn)算來(lái)決定的； ISODATA算法加入了一些試探步驟，并且可以結(jié)合成人機(jī)交互的結(jié)構(gòu)，使其能利用中間結(jié)果所取得的經(jīng)驗(yàn)更好地進(jìn)行分類(lèi)。 主要是在選代過(guò)程中可將一類(lèi)一分為二，亦可能二類(lèi)合二為一，即“自組織”，這種算法具有啟發(fā)式的特點(diǎn),與K-means相比在下列幾方面有改進(jìn)：

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

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

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

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

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

14、進(jìn)行分割,2021/1/28,在圖像分割上的簡(jiǎn)單應(yīng)用,分割后的效果,注：最大迭代次數(shù)為20次，需運(yùn)行多次才有可能得到較好的效果,2021/1/28,在圖像分割上的簡(jiǎn)單應(yīng)用,例2,注：聚類(lèi)中心個(gè)數(shù)為5，最大迭代次數(shù)為10,2021/1/28,Matlab程序?qū)崿F(xiàn),clc clear tic RGB= imread (test5.jpg); %讀入像 img=rgb2gray(RGB); m,n=size(img); subplot(2,2,1),imshow(img);title( 圖一 原圖像) subplot(2,2,2),imhist(img);title( 圖二 原圖像的灰度直方圖) h