原文寫于個人博客肖油，歡迎關注www.xiaolewei.com
簡介
聚類分析最簡單的方法即输钩，將所處理的對象按照相異性劃分為多個互斥的簇反镇。對于含有n個數(shù)據(jù)的數(shù)據(jù)集D奋蔚，以及簇數(shù)k势腮，本文所講的劃分算法將基于距離函數(shù)联贩，將對象組劃分成k個分區(qū)，每個分區(qū)代表一個簇捎拯，并盡量使簇中對象相似泪幌，不同簇中對象相異。
基本概念
令數(shù)據(jù)集D包含n個歐氏空間中的對象署照，令ci為簇Ci的形心祸泪，即為該簇的代表，定義dist(p,ci)為對象p與該簇的代表ci的度量建芙，其中dist(x,y)表示x與y的歐式距離没隘。使用簇內(nèi)變差來衡量Ci的質量，它是Ci中所有對象和形心直接的誤差的平方和：
定義E為數(shù)據(jù)集中所有對象的誤差平方和：
算法原理
為了得到k個簇禁荸，k-均值算法首先在D中隨機的選取k個對象右蒲，作為k個簇的中心。對于剩下的每個對象屡限，根據(jù)其與各個簇中心的歐式距離品嚣，將其分配到最近的一個簇中。待所有對象分配完成后钧大，對于每個簇翰撑，計算其新的形心，并將其作為該簇的代表啊央，重復分配每個對象眶诈，重復上述步驟，直到不再發(fā)生變化瓜饥。
實例詳解
選取二維的歐式空間逝撬，令D：
A1(2,10), A2(2,5), A3(8,4), B1(5,8), B2(7,5), B3(6,4), C1(1,2), C2(4,9)
距離函數(shù)為歐式距離。假設初始時選擇A1,B1,C2作為每個簇的中心（該步為隨機選扰彝痢）宪潮，進行第一輪迭代（為方便比較溯警，未開根號）：
dist(A1,A2) = √25
dist(A1,A3) = √37
dist(A1,B2) = √50
dist(A1,B3) = √52
dist(A1,C2) = √5
dist(B1,A2) = √18
dist(B1,A3) = √25
dist(B1,B2) = √13
dist(B1,B3) = √17
dist(B1,C2) = √34
dist(C1,A2) = √10
dist(C1,A3) = √53
dist(C1,B2) = √45
dist(C1,B3) = √29
dist(C1,C2) = √58
所以可以得到如下簇：
{A1,C2}
{B1,A3,B2,B3}
{C1,A2}
重新計算各個簇的形心：
A'(3，9.5)狡相、B'(6.5,5.25)梯轻、C'(1.5,3.5)
重復上述步驟重新分配D中所有對象，直到形心不再變化尽棕。
算法不足
該算法時間復雜度為O(nkt)喳挑，但是k-均值是無法保證結果收斂于全局最優(yōu)解，且常常終止于一個局部最優(yōu)解滔悉，其常常依賴于初始值的選取伊诵，更通常的做法是選取不同的初始值，多次運行該算法回官。
另外該算法對利群點是敏感的曹宴，當離群點被分配到某一簇時，會嚴重扭曲簇的平均值
