K-means算法及在圖像分割中的簡單應(yīng)用

1、1主要內(nèi)容算法簡介算法簡介算法要點算法要點實例實例性能分析性能分析算法改進算法改進在圖像分割中的簡單應(yīng)用在圖像分割中的簡單應(yīng)用2算法簡介k-means算法：一種得到最廣泛使用的聚類算法算法：一種得到最廣泛使用的聚類算法 算法的主要思想：算法的主要思想：u將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點聚類的代表點u通過迭代過程把數(shù)據(jù)集劃分為不同的類別通過迭代過程把數(shù)據(jù)集劃分為不同的類別u使得評價聚類性能的準則函數(shù)達到最優(yōu)，從而使使得評價聚類性能的準則函數(shù)達到最優(yōu)，從而使生成的每個聚類內(nèi)緊湊，類間獨立。生成的每個聚類內(nèi)緊湊，類間獨立。使用范圍：不適

2、合處理離散型屬性，但是對于使用范圍：不適合處理離散型屬性，但是對于連連續(xù)型續(xù)型具有較好的聚類效果。具有較好的聚類效果。3 k-means算法算法輸入：簇的數(shù)目輸入：簇的數(shù)目k和包含和包含n個對象的數(shù)據(jù)庫。個對象的數(shù)據(jù)庫。輸出：輸出：k個簇，使平方誤差準則最小。個簇，使平方誤差準則最小。算法步驟：算法步驟： 1.為每個聚類確定一個初始聚類中心，這樣就有為每個聚類確定一個初始聚類中心，這樣就有K 個初始聚類中心。個初始聚類中心。 2.將樣本集中的樣本按照最小距離原則分配到最將樣本集中的樣本按照最小距離原則分配到最鄰近聚類鄰近聚類 3.使用每個聚類中的樣本均值作為新的聚類中心。使用每個聚類中的樣本均

3、值作為新的聚類中心。 4.重復(fù)步驟重復(fù)步驟2.3直到聚類中心不再變化。直到聚類中心不再變化。 5.結(jié)束，得到結(jié)束，得到K個聚類個聚類4 將樣本分配給距離它們最近的中心向量，并使將樣本分配給距離它們最近的中心向量，并使目標函數(shù)值減小目標函數(shù)值減小21,.,2,1|min jniikjpxiCxiixCx1更新簇平均值更新簇平均值21 kiCxiixxE計算準則函數(shù)計算準則函數(shù)E5算法要點1 1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量）選定某種距離作為數(shù)據(jù)樣本間的相似性度量 在計算數(shù)據(jù)樣本之間的距離時，可以根據(jù)實際在計算數(shù)據(jù)樣本之間的距離時，可以根據(jù)實際需要選擇歐式距離、曼哈頓距離或者明考斯距離需

4、要選擇歐式距離、曼哈頓距離或者明考斯距離中的一種來作為算法的相似性度量，其中最常用中的一種來作為算法的相似性度量，其中最常用的是的是歐式距離歐式距離。6dkjkikjixxxxd12,距離越小，樣本距離越小，樣本x xi i和和x xj j越相似，差異度越??；越相似，差異度越??；距離越大，樣本距離越大，樣本x xi i和和x xj j越不相似，差異度越大。越不相似，差異度越大。（2 2）選擇評價聚類性能的準則函數(shù)）選擇評價聚類性能的準則函數(shù): :誤差平方和準則函數(shù)誤差平方和準則函數(shù) 給定數(shù)據(jù)集給定數(shù)據(jù)集X X，假設(shè)，假設(shè)X X包含包含k k個聚類子集個聚類子集X X1 1,X,X2 2,X,X

5、K K；各個聚類子集中的樣本數(shù)量分別為各個聚類子集中的樣本數(shù)量分別為n n1 1，n n2 2,n,nk k; ;各個聚類子集的均值代表點（也稱聚類中心）分各個聚類子集的均值代表點（也稱聚類中心）分別為別為m m1 1，m m2 2,m,mk k。則誤差平方和準則函數(shù)公式為：。則誤差平方和準則函數(shù)公式為：721 kiXpiimpE（3）相似度的計算根據(jù)一個類中對象的平均值相似度的計算根據(jù)一個類中對象的平均值 來進行。來進行。將所有對象隨機分配到將所有對象隨機分配到k k個非空的類中。個非空的類中。計算每個類的平均值，并用該平均值代表相應(yīng)計算每個類的平均值，并用該平均值代表相應(yīng)的類。的類。根據(jù)每

6、個對象與各個類中心的距離，分配給最根據(jù)每個對象與各個類中心的距離，分配給最近的類。近的類。然后轉(zhuǎn)（然后轉(zhuǎn)（2 2），重新計算每個類的平均值。這個），重新計算每個類的平均值。這個過程不斷重復(fù)直到滿足某個準則函數(shù)才停止。過程不斷重復(fù)直到滿足某個準則函數(shù)才停止。8Oxy10220031.50450552 數(shù)據(jù)數(shù)據(jù)對象集合對象集合S如表所示，如表所示，作為一個聚類分析作為一個聚類分析的二維的二維樣本，樣本，要求聚類的要求聚類的數(shù)量數(shù)量k=2。(1)選擇選擇 ， 為為初始初始的類中心的類中心，即即 ， 。(2)對剩余的每個對象，根據(jù)其與對剩余的每個對象，根據(jù)其與各個類中心各個類中心的距的距離，將它賦給最

7、近離，將它賦給最近的類。的類。 對對 ： 顯然顯然 ，故將故將 分配給分配給3132,OMdOMd2 , 01O0 , 02O2 , 011OM0 , 022 OM5 . 2025 . 10,2231OMd5 . 1005 . 10,2232OMd3O3O2C例子例子9 對于對于 ： 因為因為 ，所以將，所以將 分配給分配給 對于對于 ：因為因為 ，所以將，所以將 分配給分配給更新，得到新類更新，得到新類 和和計算平方誤差準則，單個方差為計算平方誤差準則，單個方差為4O2214,052029d MO2224,05005dMO2414,d MOd MO4O2c5O2215,05225dMO222

8、5,050229dMO1525,d M Od MO5O1C511,OOC 252250220022221E25.272E2234,CO O OOxy10220031.504505522 , 011OM0 , 022OM10，?？傮w平均方差是：總體平均方差是：（3）計算新）計算新的聚類的的聚類的中心。中心。 25.5225.272521EEE 2 , 5 . 2222, 2501M0 ,17. 23000, 355 . 102M重復(fù)（重復(fù)（2）和（）和（3），得到），得到O1分配給分配給C1；O2分配給分配給C2，O3分配給分配給C2 ，O4分配給分配給C2，O5分配給分配給C1。更新，得到。更

9、新，得到新類新類和和 。 中心為中心為 ， 。單個方差分別為單個方差分別為511,OOC 4322,OOOC 2 , 5 . 21M0 ,17. 22M5 .122255 . 2225 . 2022221E15.132E總體平均誤差是：總體平均誤差是： 65.2515.135 .1221EEE由上可以看出，第一次迭代后，總體平均誤差值由上可以看出，第一次迭代后，總體平均誤差值52.2552.25降到降到25.6525.65，顯著減小。由于顯著減小。由于在這次在這次迭代中迭代中，類中心，類中心不變，所以停止迭代過程不變，所以停止迭代過程，算法停止算法停止。 Oxy10220031.5045055

10、211性能分析性能分析n主要優(yōu)點：主要優(yōu)點：u是解決聚類問題的一種經(jīng)典算法，簡單、快速。是解決聚類問題的一種經(jīng)典算法，簡單、快速。u對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。u當結(jié)果類是密集的，而類與類之間區(qū)別明顯時當結(jié)果類是密集的，而類與類之間區(qū)別明顯時, , 它的它的效果較好。效果較好。n主要缺點主要缺點u在類的平均值被定義的情況下才能使用，在類的平均值被定義的情況下才能使用，這對于處理這對于處理符號屬性的數(shù)據(jù)不適用。符號屬性的數(shù)據(jù)不適用。u必須事先給出必須事先給出k k（要生成的類的數(shù)目），而且對初值（要生成的類的數(shù)目），而且對初值敏感，

11、對于不同的初始值，可能會導(dǎo)致不同結(jié)果。敏感，對于不同的初始值，可能會導(dǎo)致不同結(jié)果。u它對于它對于“躁聲躁聲”和孤立點數(shù)據(jù)是敏感的，和孤立點數(shù)據(jù)是敏感的，少量的該類少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。12針對K-means算法缺點的改進方法1.1.對于不同的初始值，可能會導(dǎo)致不同結(jié)果：多設(shè)置對于不同的初始值，可能會導(dǎo)致不同結(jié)果：多設(shè)置一些不同的初值，但比較耗時和浪費資源。一些不同的初值，但比較耗時和浪費資源。2.分類數(shù)目分類數(shù)目K不確定：通過類的自動合并和分裂，得不確定：通過類的自動合并和分裂，得到較為合理的類型數(shù)目到較為合理的類型數(shù)目K，例如，例如ISOD

12、ATA算法。相同算法。相同點：聚類中心都是通過樣本均值的迭代運算來決定的；點：聚類中心都是通過樣本均值的迭代運算來決定的；不同點：主要是在選代過程中可將一類一分為二，亦不同點：主要是在選代過程中可將一類一分為二，亦可能二類合二為一，即可能二類合二為一，即“自組織自組織”，這種算法具有啟，這種算法具有啟發(fā)式的特點。發(fā)式的特點。由于算法有自我調(diào)整的能力，因而需要設(shè)置若干個控由于算法有自我調(diào)整的能力，因而需要設(shè)置若干個控制用參數(shù)，如聚類數(shù)期望值制用參數(shù)，如聚類數(shù)期望值K、最小類內(nèi)樣本數(shù)、類、最小類內(nèi)樣本數(shù)、類間中心距離參數(shù)、每次迭代允許合并的最大聚類對數(shù)間中心距離參數(shù)、每次迭代允許合并的最大聚類對數(shù)

13、L及允許迭代次數(shù)及允許迭代次數(shù)I等。等。13k-k- center center算法：解決算法：解決k -means算法對于孤立點是算法對于孤立點是敏感敏感的問題的問題l 不不采用簇中的平均值作為參照點，可以采用簇中的平均值作為參照點，可以選用類選用類中中位置最中心的對象，即中心點作為參照點位置最中心的對象，即中心點作為參照點。l劃分劃分方法仍然是基于方法仍然是基于最小化最小化所有對象與其參照所有對象與其參照點之間的相異度之和的原則來執(zhí)行的。點之間的相異度之和的原則來執(zhí)行的。 k-meansk-means算法的改進方法算法的改進方法k-k- center center算法算法14uk-mode

14、s 算法：實現(xiàn)對算法：實現(xiàn)對離散數(shù)據(jù)離散數(shù)據(jù)的快速的快速聚類，處理聚類，處理分類屬性型數(shù)據(jù)，例如：姓名、性別、年齡等。分類屬性型數(shù)據(jù)，例如：姓名、性別、年齡等。u采用差異度采用差異度D來代替來代替k-means算法中的距離，差異算法中的距離，差異度越小，則表示距離越小。一個樣本和一個聚類中心度越小，則表示距離越小。一個樣本和一個聚類中心的差異度就是它們各個屬性不相同的個數(shù)，的差異度就是它們各個屬性不相同的個數(shù)，屬性屬性相同相同為為0，不同為不同為1，并計算，并計算1的總和。的總和。因此因此D越大，即他的越大，即他的不相關(guān)程度越不相關(guān)程度越強。強。k-meansk-means算法的改進方法算法的改進方法k-mode k-mode s s算法算法1516K-meansK-mea