黑毛到白毛的攻城獅之路: WEKA：K-Means 分群演算法

2010年8月6日星期五

WEKA：K-Means 分群演算法

K-Means 分群演算法：
輸入一群資料，以及設定為需要分成 c 群
演算法會先隨便找出 c 個點當作中心點
然後對剩下的每個點都去計算跟這 c 個中心點的距離，來決定要把他們分在哪一群
遞迴是先找出這 c 群中下一個中心點
也就是對每一個點都去計算群內其他點到這個點的距離平方
找出全體的距離平方最短的那個點，就是下一個中心點～
而如果每一群找出來中心點都跟原本一樣，就表示已經找到局部最小值了～

不過 K-Means 比較明顯的問題是，因為只能找出局部最小值，並不一定就是整體最佳解
因此一開始第一個設定的中心點是如何選取的，就顯得非常重要～

K-Means 觀念：http://neural.cs.nthu.edu.tw/jang/books/dcpr/kMeans.asp

K-Means 參考的 Java code：http://mx19841031.javaeye.com/blog/224443

另外註記，WEKA 也有包含 K-Means 的演算法可以使用。
WEKA 的資料格式是 ARFF：http://weka.wikispaces.com/ARFF+(stable+version)
使用 ARFF 檔案的範例：http://weka.wikispaces.com/Use+WEKA+in+your+Java+code#Instances

範例程式碼

        
          
          
              
              File f = new File("G:\\cluster\\bank.arff");
Instances train = new Instances(new BufferedReader(new FileReader(f))); 
AddCluster ac = new AddCluster(); 
SimpleKMeans skm = new SimpleKMeans();
skm.setNumClusters(3); // 設定用 K-Means 要分成 3 群
ac.setClusterer(skm); 
ac.setInputFormat(train);  // 指定輸入資料
System.out.println("Clustered instances:"); 
Instances CI = Filter.useFilter(train, ac); // 執行分群演算法
 
//System.out.println(clusteredI); // 印出分群結果（同下行的迴圈效果）
for(int i=0 ; i<CI.numInstances() ; i++) {
 System.out.println((i+1)+": "+CI.instance(i)+"\t");
 System.out.println("cluster #:"+CI.instance(i).value(CI.instance(i).numAttributes()-1));
}
 
System.out.println("Centroids:"); 
Instances centroids = skm.getClusterCentroids(); 
System.out.println(centroids); // 印出每群的中心點

            

        
      