K-means聚类

K-means聚类算法的一般步骤：

    * 初始化。输入基因表达矩阵作为对象集X，输入指定聚类类数N，并在X中随机选取N个对象作为初始聚类中心。设定迭代中止条件，比如最大循环次数或者聚类中心收敛误差容限。
    * 进行迭代。根据相似度准则将数据对象分配到最接近的聚类中心，从而形成一类。初始化隶属度矩阵。
    * 更新聚类中心。然后以每一类的平均向量作为新的聚类中心，重新分配数据对象。
    * 反复执行第二步和第三步直至满足中止条件。
具体实现代码如下：
public class BasicKMeans implements Serializable{

/**
*
*/
private static final long serialVersionUID = 1L;

private int numClusters=2;//想要聚类的个数

private int coordCount;//数据的个数

private double[][] datas;//原始数据

private KCluster[] _clusters;//聚类

/*
     * 定义一个变量用于记录和跟踪每个资料点属于哪个群聚类
     *_clusterAssignments[j]=i;// 表示第 j 个资料点对象属于第 i 个群聚类
     */
     final int[] _clusterAssignments;
    
     // 定义一个变量用于记录和跟踪每个资料点离聚类最近
     private final int[] _nearestCluster;
    
     /*定义一个变量，来表示资料点到中心点的距离,
      *其中_distanceCache[i][j]表示第i个资料点到第j个群聚对象中心点的距离；
      */
     private final double[][] _distanceCache;
    
     private static final Random _rnd = new Random(1);
    
     public BasicKMeans(double[][]datas,int num){
    this.datas=datas;
    this.numClusters=num;
    this.coordCount=datas.length;
    this._clusters=new KCluster[num];
    _clusterAssignments=new int[coordCount];
    _nearestCluster=new int[coordCount];
    _distanceCache=new double[coordCount][numClusters];
    InitRandom();
     }
    
     //
     public void start(){
    while(true){
    //1、重新计算每个聚类的均值
    for(int i=0;i<numClusters;i++){
    _clusters[i].updateCenter(datas);
    }
    //2 计算每个数据与聚类中心的距离
    for(int i=0;i<coordCount;i++){
    for(int j=0;j<numClusters;j++){
    double dist=getDistance(datas[i],_clusters[j].center);
    _distanceCache[i][j]=dist;
    }
    }
    //3、计算每个数据离哪个聚类最近
     //4、比较每个数据最近的聚类是否就是它所属的聚类
     //如果全相等表示所有的点已经是最佳距离了，直接返回；
    int k=0;
    for(int i=0;i<coordCount;i++){
    _nearestCluster[i]=nearestCluster(i);
    if(_clusterAssignments[i]==_nearestCluster[i])
    k++;
    }
    if(k==coordCount)
    break;
    //5、否则需要重新调整资料点和群聚类的关系，调整完毕后再重新开始循环；
             //需要修改每个聚类的成员和表示某个数据属于哪个聚类的变量
    for(int i=0;i<numClusters;i++){
    _clusters[i].currentMembership.clear();
    }
    for(int i=0;i<coordCount;i++){
    _clusters[_nearestCluster[i]].currentMembership.add(i);
    _clusterAssignments[i]=_nearestCluster[i];
    }
    }
     }
    
   //计算某个资料点最近的聚类
     public int nearestCluster(int index){
    int indexCluster=-1;
    double min=Double.MAX_VALUE;
    for(int i=0;i<numClusters;i++){
    double dis=_distanceCache[index][i];
    if(dis<min){
    min=dis;
    indexCluster=i;
    }
    }
    if(indexCluster==-1)
    ;
    return indexCluster;
     }
   //计算某数据离某聚类中心的距离时
     public double getDistance(double[] data,double[] center){
    //1 采用距离的算法计算
    int len=data.length;
    double sum=0;
    for(int i=0;i<len;i++){
    double v=data[i]-center[i];
    sum+=v*v;
    }
    return Math.sqrt(sum);
   
    }
    
  // 随机初始化k个聚类
     private void InitRandom(){
         for (int i = 0; i < numClusters; i++)
         {
             int temp = _rnd.nextInt(coordCount);
             _clusterAssignments[temp] = i; // 记录第temp个资料属于第i个聚类
             _clusters[i] = new KCluster(temp,datas[temp]);
         }
     }


public class KCluster {

public List<Integer> currentMembership = new ArrayList<Integer>();// 用于表示每个群聚包含的数据资料点集合
double[] center;// 用于表示每个聚类对象的均值，也就是中心对象

public KCluster(int dataIndex,double[] data){
currentMembership.add(dataIndex);
this.center=data;
}
// 根据 mCurrentMembership 取得原始资料点对象 coord ，该对象是 coordinates 的一个子集；
    //然后取出该子集的均值；取均值的算法很简单，可以把 coordinates 想象成一个 m*n 的距阵 ,
    //每个均值就是每个纵向列的取和平均值 , //该值保存在 mCenter 中
public void updateCenter(double[][] coordinates){
for(int i=0;i<currentMembership.size();i++){
double[] coord=coordinates[currentMembership.get(i)];
for(int j=0;j<coord.length;j++)
center[j]+=coord[j];// 得到每个纵向列的和；
}
for(int k=0;k<center.length;k++)
center[k]/=currentMembership.size();// 对每个纵向列取平均值
}

}