Kmeans算法学习笔记

Scroll Down

Kmeans 算法

计算方法

  1. 从n个向量中选择k个向量作为初始的聚类中心
  2. 根据在步骤(1)中设置的k个向量,计算每个向量与这k个中心的距离
  3. 对于(2)中的计算,将距离这个向量最近的中心向量归在一个类簇里
  4. 重新计算每个类簇的位置
  5. 重复(3)(4)步骤,直到类簇变化量极少为止

K-means算法的演示

  1. 生成数据
    dataset.png
    可见,数据分4簇,有两簇比较集中,两簇比较分散
  2. 随机分配中心
    /**
     * 初始化聚簇中心
     * @param dataset
     * @return
     */
    public ArrayList<ArrayList<Double>> initializeCenter(ArrayList<ArrayList<Double>> dataset)
    {
        Random random = new Random();
        Integer k = this.getK();
        HashSet<Integer> set = new HashSet<>(k);
        ArrayList<ArrayList<Double>> centres = new ArrayList<ArrayList<Double>>(k);
        for (int i=0;i<k;i++)
        {
            int index=-1;
            do{
                index = random.nextInt(dataset.size());
            }while (set.contains(index));
            set.add(index);
            centres.add(dataset.get(index));
        }
        return centres;
    }
  1. 计算距离
  2. 分配类簇
  3. 重新定位中心
    为了算法的效率,我把上述三步写到了一起
public ClusterResult changeCentre(ArrayList<ArrayList<Double>> dataset,ArrayList<ArrayList<Double>> centres)
    {
        ArrayList<Integer> labels = new ArrayList<>(dataset.size());
        Integer k = this.getK();
        DistanceContext distanceContext = this.getDistanceContext();
        ArrayList<HashSet<Integer>> inverted = new ArrayList<>(k);
        ArrayList<ArrayList<Double>> newCentre = new ArrayList<>(k);
        double[][] sum = new double[k][dataset.get(0).size()];
        for (int i=0;i<k;i++)   //初始化倒排表
            inverted.add(new HashSet<Integer>());
        for (int i=0;i<dataset.size();i++)
        {
            int min=-1;
            double minValue = 9999999;
            //计算出距离
            for (int j=0;j<k;j++) {
                double distance = distanceContext.getDistance(dataset.get(i), centres.get(j));
                if (minValue > distance){
                    minValue = distance;
                    min = j;
                }
            }
            labels.add(min);
            inverted.get(min).add(i);
            //重定位累加
            for (int j=0;j<dataset.get(i).size();j++)
                sum[min][j]+=dataset.get(i).get(j);
        }
        //计算平均距离
        for (int i=0;i<k;i++)
        {
            ArrayList<Double> list = new ArrayList<>(sum[i].length);
            for (int j=0;j<sum[i].length;j++)
                 list.add(sum[i][j] / inverted.get(i).size());
            newCentre.add(list);
        }
        return new ClusterResult(inverted,labels,newCentre);
    }
  1. 不断重复,直到变化很少
 private final int MAX_ITERATE_NUM=100;  //最大迭代次数
    @Override
    public ClusterResult getClusterResult(ArrayList<ArrayList<Double>> dataset) {
        ArrayList<ArrayList<Double>> centers = initializeCenter(dataset);
        ClusterResult result=new ClusterResult();
        double costLast = 99999999;
        result = changeCentre(dataset, centers);
        for (int i=0;i<this.MAX_ITERATE_NUM;i++) {
            double cost = this.getCost(dataset, result.getClusterCenter(), result.getClusterIndexSet());
            if (Math.abs((cost-costLast))<0.00000000000001)
                break;
            else
                costLast = cost;
            result = changeCentre(dataset, result.getClusterCenter());
        }
        System.out.println(costLast);
        return result;
    }

算法结果

result.png
可见分配还是较为合适的。

算法分析

因为Kmeans算法的初始化的不确定性,我们提出了算法的改进。

改进,K-means++算法

主要思想:初始的聚类中心之间的相互距离要尽可能的远。
  1. 随机选取一个样本作为第一个聚类中心 c1;
  2. 计算每个样本与当前已有类聚中心最短距离(即与最近一个聚类中心的距离)
  3. 用轮盘法选出下一个聚类中心;
  4. 重复步骤二,知道选出 k 个聚类中心
private ArrayList<ArrayList<Double>> initializeCentres(ArrayList<ArrayList<Double>> dataset)
    {
        Integer k = super.getK();
        ArrayList<ArrayList<Double>> centres = new ArrayList<>(k);
        Random random = new Random();
        centres.add(dataset.get(random.nextInt(dataset.size())));       //初始化第一个聚类中心
        for (int i=0;i<k-1;i++)
        {
            ArrayList<Double> list = new ArrayList<>();     //暂时存放概率
            double sum = 0.0;       //计算距离的和
            for (int j=0;j<dataset.size();j++)
            {
                double closestDistance = getClosestDistance(dataset.get(j), centres);
                //double closestDis_pow = Math.pow(closestDistance, 2);
                list.add(closestDistance);
                sum += closestDistance;
            }
            double pointer = Math.random();     //轮盘的指标
            sum*=pointer;
            for (int j=0;j<list.size();j++)
            {
                //double possibility=list.get(j)/sum;     //概率
                sum-=list.get(j);
                if (sum<0)      //轮盘命中
                {
                    centres.add(dataset.get(j));
                    break;
                }
            }
        }
        return centres;
    }

在k值比较大的情况下这个算法是比较慢的,但是在K值较小数据较多的时候,这个算法是比较快速的,它牺牲了一部分时间来进行初始化计算,但减少了后续聚类的时间和次数,在同时增加了准确性。