kmodies.java

k中心点 编制和调试一个程序

/*
 * KModies.java
 *
 * Created on 2007年7月27日, 下午3:05
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

/**
 *
 * @author Administrator
 */
import java.util.*;

class Data{
    double[] record=new double[5];
    static boolean choosen;
    int clusterID;
    Data()  {
        Random rand= new Random();
        for(int i=0;i<5;i++)
           record[i]= 50.0 * rand.nextDouble();
        choosen=false;
        clusterID=-1;    //还没有被分配到任何簇中
    }
    
    Data(Data e)
    {
         for(int i=0;i<5;i++)
             this.record[i]=e.record[i];
         this.choosen=e.choosen;
         this.clusterID=e.clusterID;
    }
    
    
}



public class KModies {   
       
    static double countDistance(Data e1,Data e2)   {
        double tmp=0.0;
        for(int i=0;i<5;i++)            
            tmp+=Math.abs(e1.record[i]-e2.record[i]);
        return tmp;   
    } 
    
    static double computeCost(Data [] db , ArrayList <Data> cenlist)   {
        double tmpcost=0.0;
        for(int i=0;i<db.length;i++)    
            tmpcost+=countDistance(db[i] , cenlist.get(db[i].clusterID));
        
        return tmpcost;
        
    }
    
    static boolean existLeftElement(Data [] db)
    {
        for(int i=0;i<db.length;i++)
        {
            if(db[i].choosen==false)
                return true;
        }
        return false;
    }
    
   
   
    public static void main(String[] args) {
        Data [] database=new Data[30];  //30是数据记录条数
        for(int i=0;i<30;i++)
            database[i]=new Data();
      
        
       int k=4;   //k是簇的个数
       Random randtmp= new Random();
       ArrayList <Data> centerlist=new ArrayList <Data> (k);
       for(int i=0;i<k;i++) {
           int j=randtmp.nextInt(database.length); 
           database[j].choosen=true;
           database[j].clusterID=i;
           
           centerlist.add(database[j]);           
       }    //初始的k个中心点
       
     
       double distance=1000.0;
       for(int i=0;i<30;i++) {
         if(database[i].choosen!=true)  
            continue;
        //跳过中心点
         for(int j=0;j<centerlist.size();j++) {                     
            if( countDistance(database[i],centerlist.get(j)) < distance ) {
                distance =countDistance(database[i],centerlist.get(j)) ;
                database[i].clusterID=(centerlist.get(j)).clusterID;
            }
         }
         distance=1000.0;      //恢复distance
          //将所有的记录进行分配   
      }
       
       double currentcost=0.0;
       Data tmpCenter;
       while(true)
       {
          if(!existLeftElement(database))
              break; 
               
           
           currentcost=computeCost(database,centerlist);
           int tmpIndex=randtmp.nextInt(k);
           tmpCenter=new Data(centerlist.get(tmpIndex));
           int tmpRecord=randtmp.nextInt(database.length);
           while(database[tmpRecord].choosen==true)
                tmpRecord=randtmp.nextInt(database.length);
           
           database[tmpRecord].choosen=true;
           centerlist.set(tmpIndex,database[tmpRecord]);
           
           if(currentcost<=computeCost(database,centerlist))
                centerlist.set(tmpIndex,tmpCenter);
           else
               centerlist.get(tmpIndex).clusterID=tmpCenter.clusterID;
       }
             
       
       for(int i=0;i<30;i++)
            System.out.println(database[i].clusterID);
       
    } 
    
}