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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、進行分割,2021/1/28,在圖像分割上的簡單應用,分割后的效果,注：最大迭代次數(shù)為20次，需運行多次才有可能得到較好的效果,2021/1/28,在圖像分割上的簡單應用,例2,注：聚類中心個數(shù)為5，最大迭代次數(shù)為10,2021/1/28,Matlab程序實現(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