原文引用：
http://flylijian.spaces.live.com/
1.
什么是
k-means
聚類算法？
?
從網上找到了很多定義，這里選取比較典型的幾個；
? K-Mean
分群法是一種分割式分群方法，其主要目標是要在大量高緯的資料點中找出
??????
具有代表性的資料點；這些資料點可以稱為群中心，代表點；然后再根據這些
???????
群中心，進行后續的處理，這些處理可以包含
?? 1
）資料壓縮：以少數的資料點來代表大量的資料，達到資料壓縮的功能；
?? 2
）資料分類：以少數代表點來代表特點類別的資料，可以降低資料量及計算量；
?
??????
分割式分群法的目的是希望盡量減小每個群聚中，每一點與群中心的距離平方差（square error）。?
?假設我們現在有一組包含c個群聚的資料，其中第 k 個群聚可以用集合 Gk來表示，假設 Gk包含nk筆
?資料 {x1, x2, …, xnk），此群聚中心為yk，則該群聚的平方差 ek可以定義為：
????????????
ek =
S
i
|xi-yk|2
，其中 xi是屬於第 k 群的資料點。
?而這c個群聚的總和平方差E便是每個群聚的平方差總和：
E =
S
k=1~c
ek
?我們分群的方法，就變成是一個最佳化的問題，換句話說，我們要如何選取 c 個群聚以及相關的群中心，
?使得 E 的值為最小。
?
2
．處理流程
（
1
）
?
從
c
個數據對象任意選擇
k
個對象作為初始聚類中心；
（
2
）
?
循環（
3
）到（
4
）直到每個聚類不再發生變化為止；
（
3
）
?
根據每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據最小距離重新對相應對象進行劃分；
（
4
）
?
重新計算每個（有變化）聚類的均值（中心對象）
?
?
3. java
算法的實現說明
?
1)
假設給點一組
c
點資料
X = {x1, ..., xc}
，每一點都有
d
維；給定一個群聚的數目
k,
求其
????
最好的聚類結果。
? 2
）
BasicKMeans.java
主類
??????? int coordCount = 250;//
原始的資料個樹
??????? int dimensions = 100;//
每個資料的緯度數目
??????? double[][] coordinates = new double[coordCount][dimensions];
? 這里假設
c
點資料為
coordinates
對象，其中
c
為
coordCount,d
為
dimensions
相應值。
??????? int mk = 30; //
想要群聚的數目
?? 根據群聚數目定義
mk
個群聚類對象
????? mProtoClusters = new ProtoCluster[mK];//
見
ProtoCluster
類說明
?? //
首先隨機選取
mk
個原始資料點作為群聚類
???? mProtoClusters[i]= new ProtoCluster (coordinates[j] );//i
依此為
0
到
mk
的值；
j
為
0
到
coordCount
的值
? 定義一個變量用于記錄和跟蹤每個資料點屬于哪個群聚類
??? mClusterAssignments = new int[coordCount];
??? mClusterAssignments[j]=i;//
表示第
j
個資料點對象屬于第
i
個群聚類
?? //
開始循環
?? mProtoClusters[i].updateCenter(mCoordinates);//
計算第
i
個聚類對象的均值
?
-
?? //
依次計算每個資料點到中心點的距離，然后根據最小值劃分到相應的群集類中；
? 采用距離平方差來表示資料點到中心點的距離；
?? //定義一個變量，來表示資料點到中心點的距離
?? mDistanceCache = new double[coordCount ][mk];
??? //其中mDistanceCache[i][j]表示第i個資料點到第j個群聚對象中心點的距離；
??? //距離算法描述():
???? a)依次取出每個資料點對象double[] coord = coordinates[i];
????????b)再依次取出每個群聚類中的中心點對象double[] center = mProtoClusters[j].mCenter;
??????? c)計算coord對象與center對象之間的距離?
???? double distance(double[] coord, double[] center) {
??????? int len = coord.length;
??????? double sumSquared = 0.0;
??????? for (int i=0; i<len; i++) {
??????????? double v = coord[i] - center[i];
??????????? sumSquared += v*v;?//平方差
??????? }
??????? return Math.sqrt(sumSquared);
????? }?
???? d)循環執行上面的流程，把結果記錄在mDistanceCache[i][j]中；
-
????? //比較出最小距離，然后根據最小距離重新對相應對象進行劃分
???? 依次比較每個資料點的 最短中心距離，
????? int nearestCluster(int ndx) {
??????? int nearest = -1;
??????? double min = Double.MAX_VALUE;??
??????? for (int c = 0; c < mK; c++) {
??????????????? double d = mDistanceCache[ndx][c];
??????????????? if (d < min) {
??????????????????? min = d;
??????????????????? nearest = c;
??????????????? }??????????
????????? ?}
??????? return nearest;
?????? }
? 該方法返回該資料點對應的最短中心距離的群聚類的索引值；
? 比較每個 nearestCluster[coordCount] 的值和mClusterAssignments[coordCount]
? 的值是否相等，如果全相等表示所有的點已經是最佳距離了，直接返回；
? 否則需要重新調整資料點和群聚類的關系，調整完畢后再重新開始循環；
??調整時需要更新下列數據：
??? a)更新mProtoClusters[i]中的mCurrentMembership集合；
?????? b)更新mClusterAssignments[i]中對應的值；
?? 然后重行開始循環
?? 3
）
ProtoCluster.java
是一個包含代表點的群聚類，該類有兩個最主要的屬性"代表點"和"群中心"；
??????
? int[] mCurrentMembership;//
用于表示每個群聚包含的數據資料點集合
??????? double[] mCenter;//
用于表示每個聚類對象的均值，也就是中心對象
??????
? void updateCenter(double[][] coordinates) {
?????? //
該方法計算
聚類對象的均值
;
??????? //
根據
mCurrentMembership
取得原始資料點對象
coord
，該對象是
coordinates
的一個子集；然后取出該子集的均值；
??? 取均值的算法很簡單，可以把
coordinates
想象成一個
m*n
的距陣
,
每個均值就是每個縱向列的取和平均值
,
該值保
??? 存在
mCenter
中
?????
?for (int i=0; i< mCurrentMembership.length; i++) {
?????????????? double[] coord = coordinates[mCurrentMembership[i]];
?????????????? for (int j=0; j<coord.length; j++) {
??????????????????????? mCenter[j] += coord[j];//
得到每個縱向列的和；
?????????????
?}
???????????????f
or (int i=0; i<mCenter.length; i++) {
??????????????????
?mCenter[i] /= mCurrentSize; //
對每個縱向列取平均值
???????
??????? }
???????????}?
????? 參考文檔：http://www.javaworld.com/javaworld/jw-11-2006/jw-1121-thread.html
?