K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評價(jià)指標(biāo)，即認(rèn)為兩個(gè)對象的距離越近，其相似度就越大。該算法認(rèn)為簇是由距離靠近的對象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。

k個(gè)初始類聚類中心點(diǎn)的選取對聚類結(jié)果具有較大的影響，因?yàn)樵谠撍惴ǖ谝徊街惺请S機(jī)的選取任意k個(gè)對象作為初始聚類的中心，初始地代表一個(gè)簇。該算法在每次迭代中對數(shù)據(jù)集中剩余的每個(gè)對象，根據(jù)其與各個(gè)簇中心的距離將每個(gè)對象重新賦給最近的簇。當(dāng)考察完所有數(shù)據(jù)對象后，一次迭代運(yùn)算完成，新的聚類中心被計(jì)算出來。如果在一次迭代前后，J的值沒有發(fā)生變化，說明算法已經(jīng)收斂。

算法過程如下：

1）從N個(gè)文檔隨機(jī)選取K個(gè)文檔作為質(zhì)心

2）對剩余的每個(gè)文檔測量其到每個(gè)質(zhì)心的距離，并把它歸到最近的質(zhì)心的類

3）重新計(jì)算已經(jīng)得到的各個(gè)類的質(zhì)心

4）迭代2～3步直至新的質(zhì)心與原質(zhì)心相等或小于指定閾值，算法結(jié)束

具體如下：

輸入：k， data［n］;

（1） 選擇k個(gè)初始中心點(diǎn)，例如c［0］=data［0］，…c［k-1］=data［k-1］；

（2） 對于data［0］….data［n］，分別與c［0］…c［k-1］比較，假定與c［i］差值最少，就標(biāo)記為i；

（3） 對于所有標(biāo)記為i點(diǎn)，重新計(jì)算c［i］={ 所有標(biāo)記為i的data［j］之和}/標(biāo)記為i的個(gè)數(shù)；

（4） 重復(fù)（2）（3），直到所有c［i］值的變化小于給定閾值。

Kmeans算法的優(yōu)缺點(diǎn)

K-means算法的優(yōu)點(diǎn)是：首先，算法能根據(jù)較少的已知聚類樣本的類別對樹進(jìn)行剪枝確定部分樣本的分類；其次，為克服少量樣本聚類的不準(zhǔn)確性，該算法本身具有優(yōu)化迭代功能，在已經(jīng)求得的聚類上再次進(jìn)行迭代修正剪枝確定部分樣本的聚類，優(yōu)化了初始監(jiān)督學(xué)習(xí)樣本分類不合理的地方；第三，由于只是針對部分小樣本可以降低總的聚類時(shí)間復(fù)雜度。

K-means算法的缺點(diǎn)是：首先，在 K-means 算法中 K 是事先給定的，這個(gè) K 值的選定是非常難以估計(jì)的。很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適；其次，在 K-means 算法中，首先需要根據(jù)初始聚類中心來確定一個(gè)初始劃分，然后對初始劃分進(jìn)行優(yōu)化。這個(gè)初始聚類中心的選擇對聚類結(jié)果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結(jié)果；最后，該算法需要不斷地進(jìn)行樣本分類調(diào)整，不斷地計(jì)算調(diào)整后的新的聚類中心，因此當(dāng)數(shù)據(jù)量非常大時(shí)，算法的時(shí)間開銷是非常大的。

K-means算法對于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。解決方法：

1.多設(shè)置一些不同的初值，對比最后的運(yùn)算結(jié)果，一直到結(jié)果趨于穩(wěn)定結(jié)束

2.很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適。通過類的自動(dòng)合并和分裂，得到較為合理的類型數(shù)目 K，例如 ISODATA 算法。

K-means算法的其他改進(jìn)算法如下：

1. k-modes 算法：實(shí)現(xiàn)對離散數(shù)據(jù)的快速聚類，保留了k-means算法的效率同時(shí)將k-means的應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)。

2. k-Prototype算法：可以對離散與數(shù)值屬性兩種混合的數(shù)據(jù)進(jìn)行聚類，在k-prototype中定義了一個(gè)對數(shù)值與離散屬性都計(jì)算的相異性度量標(biāo)準(zhǔn)。

大家接觸的第一個(gè)聚類方法，十有八九都是K-means聚類啦。該算法十分容易理解，也很容易實(shí)現(xiàn)。其實(shí)幾乎所有的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法都有其優(yōu)點(diǎn)和缺點(diǎn)。

（1）對于離群點(diǎn)和孤立點(diǎn)敏感；

（2）k值選擇;

（3）初始聚類中心的選擇；

（4）只能發(fā)現(xiàn)球狀簇。

對于這4點(diǎn)呢的原因，讀者可以自行思考下，不難理解。針對上述四個(gè)缺點(diǎn)，依次介紹改進(jìn)措施。

改進(jìn)1

首先針對（1），對于離群點(diǎn)和孤立點(diǎn)敏感，如何解決？提到過離群點(diǎn)檢測的LOF算法，通過去除離群點(diǎn)后再聚類，可以減少離群點(diǎn)和孤立點(diǎn)對于聚類效果的影響。

改進(jìn)2

k值的選擇問題，在安徽大學(xué)李芳的碩士論文中提到了k-Means算法的k值自適應(yīng)優(yōu)化方法。下面將針對該方法進(jìn)行總結(jié)。

首先該算法針對K-means算法的以下主要缺點(diǎn)進(jìn)行了改進(jìn)：

1）必須首先給出k（要生成的簇的數(shù)目），k值很難選擇。事先并不知道給定的數(shù)據(jù)應(yīng)該被分成什么類別才是最優(yōu)的。

2）初始聚類中心的選擇是K-means的一個(gè)問題。

李芳設(shè)計(jì)的算法思路是這樣的：可以通過在一開始給定一個(gè)適合的數(shù)值給k，通過一次K-means算法得到一次聚類中心。對于得到的聚類中心，根據(jù)得到的k個(gè)聚類的距離情況，合并距離最近的類，因此聚類中心數(shù)減小，當(dāng)將其用于下次聚類時(shí)，相應(yīng)的聚類數(shù)目也減小了，最終得到合適數(shù)目的聚類數(shù)?？梢酝ㄟ^一個(gè)評判值E來確定聚類數(shù)得到一個(gè)合適的位置停下來，而不繼續(xù)合并聚類中心。重復(fù)上述循環(huán)，直至評判函數(shù)收斂為止，最終得到較優(yōu)聚類數(shù)的聚類結(jié)果。

改進(jìn)3

對初始聚類中心的選擇的優(yōu)化。一句話概括為：選擇批次距離盡可能遠(yuǎn)的K個(gè)點(diǎn)。具體選擇步驟如下。

首先隨機(jī)選擇一個(gè)點(diǎn)作為第一個(gè)初始類簇中心點(diǎn)，然后選擇距離該點(diǎn)最遠(yuǎn)的那個(gè)點(diǎn)作為第二個(gè)初始類簇中心點(diǎn)，然后再選擇距離前兩個(gè)點(diǎn)的最近距離最大的點(diǎn)作為第三個(gè)初始類簇的中心點(diǎn)，以此類推，直至選出K個(gè)初始類簇中心點(diǎn)。

對于該問題還有個(gè)解決方案。之前我也使用過。熟悉weka的同學(xué)應(yīng)該知道weka中的聚類有一個(gè)算法叫Canopy算法。

選用層次聚類或者Canopy算法進(jìn)行初始聚類，然后利用這些類簇的中心點(diǎn)作為KMeans算法初始類簇中心點(diǎn)。該方法對于k值的選擇也是十分有效的。

改進(jìn)4

只能獲取球狀簇的根本原因在于，距離度量的方式。在李薈嬈的碩士論文K_means聚類方法的改進(jìn)及其應(yīng)用中提到了基于2種測度的改進(jìn)，改進(jìn)后，可以去發(fā)現(xiàn)非負(fù)、類橢圓形的數(shù)據(jù)。但是對于這一改進(jìn)，個(gè)人認(rèn)為，并沒有很好的解決K-means在這一缺點(diǎn)的問題，如果數(shù)據(jù)集中有不規(guī)則的數(shù)據(jù)，往往通過基于密度的聚類算法更加適合，比如DESCAN算法。