1.基本Kmeans算法
選擇K個點作為初始質(zhì)心
repeat
將每個點指派到最近的質(zhì)心，形成K個簇
重新計算每個簇的質(zhì)心
until?簇不發(fā)生變化或達到最大迭代次數(shù)
時間復雜度：O(tKmn)，其中，t為迭代次數(shù)，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)
空間復雜度：O((m+K)n)，其中，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)
kmenas算法首先選擇K個初始質(zhì)心，其中K是用戶指定的參數(shù)，即所期望的簇的個數(shù)。這樣做的前提是我們已經(jīng)知道數(shù)據(jù)集中包含多少個簇，但很多情況下，我們并不知道數(shù)據(jù)的分布情況，實際上聚類就是我們發(fā)現(xiàn)數(shù)據(jù)分布的一種手段，這就陷入了雞和蛋的矛盾。如何有效的確定K值，這里大致提供幾種方法，若各位有更好的方法，歡迎探討。
1.與層次聚類結(jié)合[2]
經(jīng)常會產(chǎn)生較好的聚類結(jié)果的一個有趣策略是，首先采用層次凝聚算法決定結(jié)果粗的數(shù)目，并找到一個初始聚類，然后用迭代重定位來改進該聚類。
2.穩(wěn)定性方法[3]
穩(wěn)定性方法對一個數(shù)據(jù)集進行2次重采樣產(chǎn)生2個數(shù)據(jù)子集，再用相同的聚類算法對2個數(shù)據(jù)子集進行聚類，產(chǎn)生2個具有k個聚類的聚類結(jié)果，計算2個聚類結(jié)果的相似度的分布情況。2個聚類結(jié)果具有高的相似度說明k個聚類反映了穩(wěn)定的聚類結(jié)構(gòu)，其相似度可以用來估計聚類個數(shù)。采用次方法試探多個k，找到合適的k值。
3.系統(tǒng)演化方法[3]
系統(tǒng)演化方法將一個數(shù)據(jù)集視為偽熱力學系統(tǒng)，當數(shù)據(jù)集被劃分為K個聚類時稱系統(tǒng)處于狀態(tài)K。系統(tǒng)由初始狀態(tài)K=1出發(fā)，經(jīng)過分裂過程和合并過程，系統(tǒng)將演化到它的穩(wěn)定平衡狀態(tài)Ki，其所對應的聚類結(jié)構(gòu)決定了最優(yōu)類數(shù)Ki。系統(tǒng)演化方法能提供關于所有聚類之間的相對邊界距離或可分程度，它適用于明顯分離的聚類結(jié)構(gòu)和輕微重疊的聚類結(jié)構(gòu)。
4.使用canopy算法進行初始劃分[4]
基于Canopy Method的聚類算法將聚類過程分為兩個階段
Stage1、聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy ，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬于任何Canopy的情況，可以把這一階段看做數(shù)據(jù)預處理；
Stage2、在各個Canopy 內(nèi)使用傳統(tǒng)的聚類方法(如K-means)，不屬于同一Canopy 的對象之間不進行相似性計算。
從這個方法起碼可以看出兩點好處：首先，Canopy 不要太大且Canopy 之間重疊的不要太多的話會大大減少后續(xù)需要計算相似性的對象的個數(shù)；其次，類似于K-means這樣的聚類方法是需要人為指出K的值的，通過Stage1得到的Canopy 個數(shù)完全可以作為這個K值，一定程度上減少了選擇K的盲目性。
其他方法如貝葉斯信息準則方法（BIC）可參看文獻[5]。
選擇適當?shù)某跏假|(zhì)心是基本kmeans算法的關鍵步驟。常見的方法是隨機的選取初始質(zhì)心，但是這樣簇的質(zhì)量常常很差。處理選取初始質(zhì)心問題的一種常用技術(shù)是：多次運行，每次使用一組不同的隨機初始質(zhì)心，然后選取具有最小SSE（誤差的平方和）的簇集。這種策略簡單，但是效果可能不好，這取決于數(shù)據(jù)集和尋找的簇的個數(shù)。
第二種有效的方法是，取一個樣本，并使用層次聚類技術(shù)對它聚類。從層次聚類中提取K個簇，并用這些簇的質(zhì)心作為初始質(zhì)心。該方法通常很有效，但僅對下列情況有效：（1）樣本相對較小，例如數(shù)百到數(shù)千（層次聚類開銷較大）；（2）K相對于樣本大小較小
第三種選擇初始質(zhì)心的方法，隨機地選擇第一個點，或取所有點的質(zhì)心作為第一個點。然后，對于每個后繼初始質(zhì)心，選擇離已經(jīng)選取過的初始質(zhì)心最遠的點。使用這種方法，確保了選擇的初始質(zhì)心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質(zhì)心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用于點樣本。由于離群點很少（多了就不是離群點了），它們多半不會在隨機樣本中出現(xiàn)。計算量也大幅減少。
第四種方法就是上面提到的canopy算法。
常用的距離度量方法包括：歐幾里得距離和余弦相似度。兩者都是評定個體間差異的大小的。歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需要先進行標準化，同時距離越大，個體間差異越大；空間向量余弦夾角的相似度度量不會受指標刻度的影響，余弦值落于區(qū)間[-1,1]，值越大，差異越小。但是針對具體應用，什么情況下使用歐氏距離，什么情況下使用余弦相似度？
從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形，其頂角大小是不確定的。也就是說對于兩條空間向量，即使兩點距離一定，他們的夾角余弦值也可以隨意變化。感性的認識，當兩用戶評分趨勢一致時，但是評分值差距很大，余弦相似度傾向給出更優(yōu)解。舉個極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認知其實是一樣的，但是歐式距離給出的解顯然沒有余弦值合理。[6]
對于距離度量不管是采用歐式距離還是采用余弦相似度，簇的質(zhì)心都是其均值，即向量各維取平均即可。對于距離對量采用其它方式時，這個還沒研究過。
一般是目標函數(shù)達到最優(yōu)或者達到最大的迭代次數(shù)即可終止。對于不同的距離度量，目標函數(shù)往往不同。當采用歐式距離時，目標函數(shù)一般為最小化對象到其簇質(zhì)心的距離的平方和，如下：
當采用余弦相似度時，目標函數(shù)一般為最大化對象到其簇質(zhì)心的余弦相似度和，如下：
如果所有的點在指派步驟都未分配到某個簇，就會得到空簇。如果這種情況發(fā)生，則需要某種策略來選擇一個替補質(zhì)心，否則的話，平方誤差將會偏大。一種方法是選擇一個距離當前任何質(zhì)心最遠的點。這將消除當前對總平方誤差影響最大的點。另一種方法是從具有最大SSE的簇中選擇一個替補的質(zhì)心。這將分裂簇并降低聚類的總SSE。如果有多個空簇，則該過程重復多次。另外，編程實現(xiàn)時，要注意空簇可能導致的程序bug。
Kmenas算法試圖找到使平凡誤差準則函數(shù)最小的簇。當潛在的簇形狀是凸面的，簇與簇之間區(qū)別較明顯，且簇大小相近時，其聚類結(jié)果較理想。前面提到，該算法時間復雜度為O(tKmn)，與樣本數(shù)量線性相關，所以，對于處理大數(shù)據(jù)集合，該算法非常高效，且伸縮性較好。但該算法除了要事先確定簇數(shù)K和對初始聚類中心敏感外，經(jīng)常以局部最優(yōu)結(jié)束，同時對“噪聲”和孤立點敏感，并且該方法不適于發(fā)現(xiàn)非凸面形狀的簇或大小差別很大的簇。
