基于距離的聚類算法詳解

　　確定k個(gè)劃分達(dá)到平方誤差最小。適用于發(fā)現(xiàn)凸面形狀的簇，簇與簇之間區(qū)別較明顯，且簇大小相近。

　　優(yōu)點(diǎn)

　　算法快速，簡(jiǎn)單；對(duì)大數(shù)據(jù)集有較高的效率并且可伸縮；時(shí)間復(fù)雜度為O（n*k*t）， 其中t是迭代次數(shù)，接近于線性，并且適合挖掘大規(guī)模數(shù)據(jù)集。

　　缺點(diǎn)

　　k值的選定難以估計(jì)，初始類聚類中心點(diǎn)的選取對(duì)聚類結(jié)果有較大的影響。經(jīng)常以局部最優(yōu)結(jié)束，對(duì)噪聲和孤立點(diǎn)敏感。

　　算法過(guò)程

　　輸入：k，data

　　1） 選取k個(gè)點(diǎn)作為質(zhì)心；

　　2） 計(jì)算剩余的點(diǎn)到質(zhì)心的距離并將點(diǎn)歸到最近的質(zhì)心所在的類；

　　3） 重新計(jì)算各類的質(zhì)心；

　　4） 重復(fù)進(jìn)行2~3步直至新質(zhì)心與原質(zhì)心的距離小于指定閾值或達(dá)到迭代上限

　　優(yōu)化目標(biāo)

　　聚類的基本假設(shè)：對(duì)于每一個(gè)簇，可以選出一個(gè)中心點(diǎn)，使得該簇中的所有的點(diǎn)到該中心點(diǎn)的距離小于到其他簇的中心的距離。雖然實(shí)際情況中得到的數(shù)據(jù)并不能保證總是滿足這樣的約束，但這通常已經(jīng)是我們所能達(dá)到的最好的結(jié)果，而那些誤差通常是固有存在的或者問(wèn)題本身的不可分性造成的。

　　基于以上假設(shè)，N個(gè)數(shù)據(jù)點(diǎn)需要分為K個(gè)簇時(shí)，k-means要優(yōu)化的目標(biāo)函數(shù)：

　　其中，在數(shù)據(jù)點(diǎn)n被歸類到簇k的時(shí)候?yàn)?，否則為0。

　　為第k個(gè)簇的中心。

　　直接尋找和來(lái)最小化J并不容易，不過(guò)可以采取迭代的辦法：先固定 ，選擇最優(yōu)的 ，很容易看出，只要將數(shù)據(jù)點(diǎn)歸類到離他最近的那個(gè)中心就能保證 J最小。下一步則固定，再求最優(yōu)的。將 J對(duì)求導(dǎo)并令導(dǎo)數(shù)等于零，很容易得到J 最小的時(shí)候 應(yīng)該滿足：

　　即 的值應(yīng)當(dāng)是所有簇k中的數(shù)據(jù)點(diǎn)的平均值。由于每一次迭代都是取到 J的最小值，因此J 只會(huì)不斷地減?。ɑ蛘卟蛔儯?，而不會(huì)增加，這保證了k-means最終會(huì)到達(dá)一個(gè)極小值。雖然k-means并不能保證總是能得到全局最優(yōu)解，但是對(duì)于這樣的問(wèn)題，像k-means這種復(fù)雜度的算法，這樣的結(jié)果已經(jīng)是很不錯(cuò)的了。

　　kmeans方法應(yīng)用舉例

　?。踦lain］ view plain copy#顯示數(shù)據(jù)的基本特征

　　#檢查數(shù)據(jù)的維度

　　dim（iris）

　　#顯示列名

　　names（iris）

　　#查看數(shù)據(jù)內(nèi)部結(jié)構(gòu)

　　str（iris）

　　#顯示數(shù)據(jù)集屬性

　　attributes（iris）

　　#查看前十行記錄

　　head（iris，10）

　　iris［1:10，］

　　#查看屬性Petal.Width的前五行數(shù)據(jù)

　　iris［1:5，“Petal.Width”］

　　iris$Petal.Width［1:5］

　　#顯示每個(gè)變量的分布情況

　　summary（iris）

　　#顯示iris數(shù)據(jù)集列Species中各個(gè)值出現(xiàn)的頻次

　　table（iris$Species）

　　#根據(jù)列Species畫出餅圖

　　pie（table（iris$Species））

　　#畫出Sepal.Length的分布柱狀圖

　　hist（iris$Sepal.Length）

　　#畫出Sepal.Length的密度函數(shù)圖

　　plot（density（iris$Sepal.Length））

　　#畫出Sepal.Length列和Petal.Length列的散點(diǎn)圖

　　plot（iris$Sepal.Length，iris$Petal.Length）

　　#計(jì)算Sepal.Length列所有值的方差

　　var（iris$Sepal.Length）

　　#計(jì)算Sepal.Length列和Petal.Length列的協(xié)方差

　　cov（iris$Sepal.Length， iris$Petal.Length）

　　#計(jì)算Sepal.Length列和Petal.Length列的相關(guān)系數(shù)

　　cor（iris$Sepal.Length， iris$Petal.Length）

　　#使用Kmeans聚類

　　#刪去類別列，即第五列，然后對(duì)數(shù)據(jù)做聚類

　　#1

　　newiris = iris［，-5］

　　#2

　　newiris = iris

　　newiris$Species = NULL

　　#將數(shù)據(jù)分為三類

　　class = kmeans（newiris， 3）

　　#統(tǒng)計(jì)每種花中屬于每一類的數(shù)量

　　table（iris$Species，class$cluster）

　　#以Sepal.Length為橫坐標(biāo)，Sepal.width為縱坐標(biāo)，畫散點(diǎn)圖，顏色用1，2，3表示缺省顏色

　　plot（newiris［c（“Sepal.Length”， “Sepal.Width”）］， col=class$cluster）

　　#在散點(diǎn)圖中標(biāo)出每個(gè)類的中心

　　points（class$centers［，c（“Sepal.Length”， “Sepal.Width”）］， col=1:3， pch=8， cex=2）

　　【R語(yǔ)言實(shí)現(xiàn)K-means】

　　原始代碼來(lái)自：

　　http://weibo.com/p/23041875063b660102vi10

　?。踦lain］ view plain copyMy_kmeans = function（data， k， max.iter=10）{

　　#獲取行，列數(shù)

　　rows = nrow（data）

　　cols = ncol（data）

　　#迭代次數(shù)

　　iter = 0

　　#定義indexMatrix矩陣，第一列為每個(gè)數(shù)據(jù)所在的類，第二列為每個(gè)數(shù)據(jù)到其類中心的距離，初始化為無(wú)窮大

　　indexMatrix = matrix（0， nrow=rows， ncol=2）

　　indexMatrix［，2］ = Inf

　　#centers矩陣存儲(chǔ)類中心

　　centers = matrix（0， nrow=k， ncol=cols）

　　#從樣本中選k個(gè)隨機(jī)正整數(shù)作為初始聚類中心

　　randSeveralInteger = as.vector（sample（1:rows，size=k））

　　for（i in 1:k）{

　　indexMatrix［randSeveralInteger［i］，1］ = i

　　indexMatrix［randSeveralInteger［i］，2］ = 0

　　centers［i，］ = as.numeric（data［randSeveralInteger［i］，］）

　　}

　　#changed標(biāo)記數(shù)據(jù)所在類是否發(fā)生變化

　　changed=TRUE

　　while（changed）{

　　if（iter 》= max.iter）

　　break

　　changed=FALSE

　　#對(duì)每一個(gè)數(shù)據(jù)，計(jì)算其到各個(gè)類中心的距離，并將其劃分到距離最近的類

　　for（i in 1:rows）{

　　#previousCluster表示該數(shù)據(jù)之前所在類

　　previousCluster = indexMatrix［i，1］

　　#遍歷所有的類，將該數(shù)據(jù)劃分到距離最近的類

　　for（j in 1:k）{

　　#計(jì)算該數(shù)據(jù)到類j的距離

　　currentDistance = （sum（（data［i，］-centers［j，］）^2））^0.5

　　#如果該數(shù)據(jù)到類j的距離更近

　　if（currentDistance 《 indexMatrix［i，2］） {

　　#認(rèn)為該數(shù)據(jù)屬于類j

　　indexMatrix［i，1］ = j

　　#更新該數(shù)據(jù)到類中心的距離

　　indexMatrix［i，2］ = currentDistance

　　}

　　}

　　#如果該數(shù)據(jù)所屬的類發(fā)生了變化，則將changed設(shè)為TRUE，算法繼續(xù)

　　if（previousCluster ！= indexMatrix［i，1］）

　　changed=TRUE

　　}

　　#重新計(jì)算類中心

　　for（m in 1:k）{

　　clusterMatrix = as.matrix（data［indexMatrix［，1］==m，］） #得到屬于第m個(gè)類的所有數(shù)據(jù)

　　#如果屬于第m類的數(shù)據(jù)的數(shù)目大于0

　　if（nrow（clusterMatrix） 》 0）{

　　#更新第m類的類中心

　　centers［m，］ = colMeans（clusterMatrix）

　　#centers［m，］ = apply（clusterMatrix， 2， mean） #兩句效果相同

　　}

　　}

　　iter=（iter+1）#迭代次數(shù)＋1

　　}

　　#計(jì)算函數(shù)返回值

　　#cluster返回每個(gè)樣本屬于那一類

　　cluster = indexMatrix［，1］

　　#center為聚類中心

　　centers = data.frame（centers）

　　names（centers） = names（data）

　　#withinss存儲(chǔ)類內(nèi)距離平方和

　　withinss = matrix（0，nrow=k，ncol=1）

　　ss《-function（x） sum（scale（x，scale=FALSE）^2）

　　#按照類標(biāo)號(hào)劃分?jǐn)?shù)據(jù)集，并對(duì)每部分求方差

　　withinss《-sapply（split（as.data.frame（data），indexMatrix［，1］），ss）

　　#tot.withinss為類內(nèi)距離和

　　tot.withinss《-sum（withinss）

　　#類間距離

　　between = ss（centers［indexMatrix［，1］，］）

　　size = as.numeric（table（cluster））

　　#生成返回值列表cluster，tot.withinss，betweenss，iteration

　　result《-list（cluster=cluster，centers = centers， tot.withinss=withinss，betweenss=between，iter=iter）

　　return（result）

　　}

　　【改進(jìn)】

　　1） 選定K的方法

　　a） 與層次聚類結(jié)合。首先采用層次凝聚算法決定結(jié)果簇的數(shù)目。

　　b） 設(shè)定一些類別分裂和合并的條件，在聚類的過(guò)程中自動(dòng)增減類別的數(shù)目，得到較為 合理的類型數(shù)目k（ISODATA）

　　c） 根據(jù)方差分析理論（ANOVA），應(yīng)用混合F統(tǒng)計(jì)量確定最佳分類數(shù)，應(yīng)用模糊劃分熵 驗(yàn)證最佳分類數(shù)的正確性；

　　d） 次勝者受罰的競(jìng)爭(zhēng)學(xué)習(xí)規(guī)則（RPCL），對(duì)每個(gè)輸入而言，不僅競(jìng)爭(zhēng)獲勝單元的權(quán)值被 修正以適應(yīng)輸入值，而且對(duì)次勝單元采用懲罰的方法使之遠(yuǎn)離輸入值。

　　2） 選定初始聚類中心

　　a） 采用遺傳算法初始化

　　b） 在層次聚類的結(jié)果中選取k個(gè)類，將這k個(gè)類的質(zhì)心作為初始質(zhì)心

　　3） K-means++算法

　　k-means++算法選擇初始質(zhì)心的基本思想就是：初始的聚類中心之間的相互距離要盡可能的遠(yuǎn)。

　　a） 從輸入的數(shù)據(jù)點(diǎn)集合中隨機(jī)選擇一個(gè)點(diǎn)作為第一個(gè)聚類中心

　　b） 對(duì)于數(shù)據(jù)集中的每一個(gè)點(diǎn)x，計(jì)算它與最近聚類中心（指已選擇的聚類中心）的 距離D（x）

　　c） 選擇一個(gè)新的數(shù)據(jù)點(diǎn)作為新的聚類中心，選擇的原則是：D（x）較大的點(diǎn)，被選 取作為聚類中心的概率較大

　　d） 重復(fù)b和c直到k個(gè)聚類中心被選出來(lái)

　　e） 利用這k個(gè)初始的聚類中心來(lái)運(yùn)行標(biāo)準(zhǔn)的k-means算法

　　算法的關(guān)鍵是第3步，如何將D（x）反映到點(diǎn)被選擇的概率上，一種算法如下：

　　a） 先從我們的數(shù)據(jù)庫(kù)隨機(jī)挑個(gè)隨機(jī)點(diǎn)當(dāng)“種子點(diǎn)”

　　b） 對(duì)于每個(gè)點(diǎn)，我們都計(jì)算其和最近的一個(gè)“種子點(diǎn)”的距離D（x）并保存在一個(gè)數(shù)組 里，然后把這些距離加起來(lái)得到Sum（D（x））。

　　c） 再取一個(gè)隨機(jī)值，用權(quán)重的方式來(lái)取計(jì)算下一個(gè)“種子點(diǎn)”。這個(gè)算法的實(shí)現(xiàn) 是，先取一個(gè)能落在Sum（D（x））中的隨機(jī)值Random，然后用Random -= D（x）， 直到其《=0，此時(shí)的點(diǎn)就是下一個(gè)“種子點(diǎn)”。

　　d） 重復(fù)b和c直到k個(gè)聚類中心被選出來(lái)

　　e） 利用這k個(gè)初始的聚類中心來(lái)運(yùn)行標(biāo)準(zhǔn)的k-means算法

　　4） 空簇處理

　　如果所有的點(diǎn)在指派步驟都未分配到某個(gè)簇，就會(huì)得到空簇。如果這種情況發(fā)生，則需要某種策略來(lái)選擇一個(gè)替補(bǔ)質(zhì)心，否則的話，平方誤差將會(huì)偏大。

　　a） 一種方法是選擇一個(gè)距離當(dāng)前任何質(zhì)心最遠(yuǎn)的點(diǎn)。這將消除當(dāng)前對(duì)總平方誤差影響最大的點(diǎn)。

　　b） 另一種方法是從具有最大SSE的簇中選擇一個(gè)替補(bǔ)的質(zhì)心。這將分裂簇并降低聚類的總SSE。如果有多個(gè)空簇，則該過(guò)程重復(fù)多次。