目錄

• 歷史淵源
• 算法原理
• 優(yōu)缺點(diǎn)
• 改進(jìn)算法
  • K-Modes
  • K-Medoids
  • Mini-Batch K-Means
  • 二分K-Means
• 相關(guān)算法

K-Means算法的功能是將空間中m個(gè)點(diǎn)按相似性劃分為k個(gè)不同部分，每個(gè)部分都有一個(gè)中心點(diǎn)。舉個(gè)例子來說，這里有6本書，書名是：瘋狂的投資、深夜加油站遇見蘇格拉底、與神對(duì)話、巴菲特之道、理念的力量、股票作手回憶錄。那么按相似性可以把瘋狂的投資、巴菲特之道以及股票作手回憶錄劃分到同一個(gè)類別當(dāng)中，因?yàn)樗鼈兌际顷P(guān)于股票投資的；而另外三本書可以劃分到另一個(gè)類別；類別的中心點(diǎn)那你就可以認(rèn)為是最能代表這個(gè)類別中的某一本書。（*** 這個(gè)例子舉得不是很恰當(dāng)啊。***）

1. 歷史淵源

K-Means算法來源于信號(hào)處理中的矢量量化技術(shù)。所謂的矢量量化指的是：將一個(gè)向量空間中的點(diǎn)用其子集代替。而子集的尋找就可以使用K-Means算法。

2. 算法原理

K-Means算法偽碼如下：

1. 隨機(jī)產(chǎn)生k個(gè)中心點(diǎn)，一個(gè)中心點(diǎn)代表一個(gè)類別
2. 計(jì)算每個(gè)點(diǎn)與k個(gè)中心點(diǎn)的歐式距離，并將該點(diǎn)劃分到與之距離最短的中心點(diǎn)所屬的類別當(dāng)中
3. 對(duì)每一個(gè)類別，使用該類中所有點(diǎn)的均值更新中心點(diǎn)
4. 重復(fù)2/3兩個(gè)步驟直到前后兩次劃分的類別不再改變?yōu)橹?/li>

3. 優(yōu)缺點(diǎn)

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

• 簡(jiǎn)單
• 復(fù)雜度較低，為O(tmk)，其中t為迭代次數(shù)，m為數(shù)據(jù)集大小，k為中心點(diǎn)個(gè)數(shù)。

缺點(diǎn)：

• 由于使用均值更新中心點(diǎn)，因此對(duì)數(shù)據(jù)集中的極值較為敏感。
• 預(yù)先需要給定k的值，在用戶不能明確k值得情況下只能猜測(cè)了。
• 在數(shù)據(jù)分布存在較大傾斜的情況下，聚類效果不好。
• 聚類效果依賴于初始中心點(diǎn)，可能由于中心點(diǎn)選取不當(dāng)而收斂到局部最優(yōu)解。

4. 改進(jìn)算法

4.1 K-Modes算法

在均值沒有意義的情況下使用眾數(shù)，比如說對(duì)于標(biāo)稱屬性，均值顯然沒有意義。

4.2 K-Medoids算法

聽說該算法可以降低極值所產(chǎn)生的影響，不過不大明白原理。

4.3 Mini-Batch K-Means算法

該算法是為了解決傳統(tǒng)的K-Means算法在大數(shù)據(jù)集下耗時(shí)較長(zhǎng)的問題。算法原理和K-Means算法在數(shù)據(jù)集的選取上有所不同，普通的K-Means算法每次迭代都是使用原始數(shù)據(jù)集中的所有數(shù)據(jù)進(jìn)行迭代，而Mini-Batch算法則是在每次迭代時(shí)都從原始數(shù)據(jù)集中采取固定數(shù)量的樣本作為本次迭代的數(shù)據(jù)集。

4.4 二分K-Means算法

該算法主要是解決K-Means算法陷入局部最優(yōu)解的問題。該算法通過將原始數(shù)據(jù)集一分為二，之后再對(duì)每個(gè)類進(jìn)行劃分，以找到一個(gè)劃分可以最大化的降低誤差。（參考：機(jī)器學(xué)習(xí)實(shí)戰(zhàn)P190）

未完待續(xù)