K-MEANS算法 



輸入：聚類個數k，以及包含 n個數據對象的數據庫。

輸出：滿足方差最小標準的k個聚類。

處理流程：        

（1）  從 n個數據對象任意選擇 k 個對象作為初始聚類中心；

（2）  循環（3）到（4）直到每個聚類不再發生變化為止

（3）  根據每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據最小距離重新對相應對象進行劃分；

（4）  重新計算每個（有變化）聚類的均值（中心對象）

k-means 算法接受輸入量 k ；然后將n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進行計算的。

k-means 算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心；而對于所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然 后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標準測度函數開始收斂為止。一般都采用均方差作為標準測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。


     k-means算法是一種基于樣本間相似性度量的間接聚類方法，屬于非監督學習方法。此算法以k為參數，把n 個對象分為k個簇，以使簇內具有較高的相似度，而且簇間的相似度較低。相似度的計算根據一個簇中對象的平均值（被看作簇的重心）來進行。此算法首先隨機選擇k個對象，每個對象代表一個聚類的質心。對于其余的每一個對象，根據該對象與各聚類質心之間的距離，把它分配到與之最相似的聚類中。然后，計算每個聚類的新質心。重復上述過程，直到準則函數會聚。k-means算法是一種較典型的逐點修改迭代的動態聚類算法，其要點是以誤差平方和為準則函數。逐點修改類中心：一個象元樣本按某一原則，歸屬于某一組類后，就要重新計算這個組類的均值，并且以新的均值作為凝聚中心點進行下一次象元素聚類；逐批修改類中心：在全部象元樣本按某一組的類中心分類之后，再計算修改各類的均值，作為下一次分類的凝聚中心點。
 
發表于 @ 2006年11月29日 10:04:00|評論(0)|編輯

 | 舊一篇: Nagle's algorithm(轉）