SPMF源码学习与总结——k-means算法

• 算法源代码下载地址
  Algorithm.rar
  是用Eclipse调试过的，直接用Eclipse打开工程文件即可运行。主方法在ca.pfv.spmf.test包内的MainTestKMeans_saveTiFile.java中，工程文件内还包括所有Spmf实现的聚类、分类、关联规则等相关算法。

• 算法步骤
  (1)选择聚类的数量k，及决定生成类别的数量k
  (2)随机产生k个类，并指定每个类的中心center
  (3)分别计算每个点到这k个类的center的距离，把该点分配到离它最近的类
  (4)重新计算每个类的的中心点
  (5)重复(3)、(4)步，直到没有点被重新分类

• 算法分析
  (1) spmf实现的kmeans算法，关键在与实现数据的存储上。输入数据格式如下：

1 2 3 4
1 6 8 8
1 2 3 3
2 4 5 5
4 7 8 7
7 6 8 9
4 4 3 3
2 2 5 5
7 5 5 5
5 6 8 9

即每一行数据代表一个点，每一个点含有4个值，是一个典型的高维数据。算法实现的目标是将这10个4维点分成3（k=3）个类型，每一个类型定义变量cluster存储，类集合用定义的clusters变量存储。每个点用vector代表，而所有的点存储在List中，用私有变量vectors代表。而vector是spmf自定义的doubleAllary数据结构，该结构实质是一个double型的4维数组。

• 源码解读：

List<ClusterWithMean> applyKMeans(int k, DistanceFunction distanceFunction,
            List<DoubleArray> vectors, double minValue, double maxValue,
            int vectorsSize) {
        List<ClusterWithMean> newClusters = new ArrayList<ClusterWithMean>();

        // 如果只有一个点
        if (vectors.size() == 1) {
            // 创建一个类型，并把该点分到该类中，返回类 
            DoubleArray vector = vectors.get(0);
            ClusterWithMean cluster = new ClusterWithMean(vectorsSize);
            cluster.addVector(vector);
            newClusters.add(cluster);
            return newClusters;
        }

        //产生k个空类，为每个类随机产生一个中心，该循环结束后，newClusters会含有3(k=3)个空类，每个类都有一个中心点
        for(int i=0; i< k; i++){
        //因为数据是4维数据，所以产生的中心点meanVector也是四维数据
            DoubleArray meanVector = generateRandomVector(minValue, maxValue, vectorsSize);
        //产生类
            ClusterWithMean cluster = new ClusterWithMean(vectorsSize);
        //设置类的中心点   
            cluster.setMean(meanVector);
            newClusters.add(cluster);
        }

        // 以下是步骤(5)
        boolean changed;
        while(true) {
            iterationCount++;
            changed = false;
            // 对于数据中的每一个点vector，计算与每一个类型中心点的距离。
            for (DoubleArray vector : vectors) {
                // 定义两个引用，分别用来表示离当前点最近的类、包含该点的类
                ClusterWithMean nearestCluster = null;
                ClusterWithMean containingCluster = null;
                double distanceToNearestCluster = Double.MAX_VALUE;
                for (ClusterWithMean cluster : newClusters) {
                    // 计算每个点vector与当前类cluster的距离
                    double distance = distanceFunction.calculateDistance(cluster.getmean(), vector);
                    //如果点vector离当前cluster的距离比上一个cluster的短
                    //则记录该距离以便与下一个比较。同时，让引用指向这个类，
                    //即相对于上一个cluster来说，距点Vector最近的类是当前的cluster
                    if (distance < distanceToNearestCluster) {
                        nearestCluster = cluster;
                        distanceToNearestCluster = distance; 
                    }
                    // 这一步比较关键：标记包含改点的类containingCluster
                    //有两种情况。举例：第一，假设点vector1离cluster类近，且cluster1包含该类，
                    //则，点vector1分到类cluster1中是正确的。第二，假设vector1离cluster1近，
                    //但是vector1在点却在cluster2类中，所以把vector1分配到cluster1的同时，
                    //也要把vector1从cluster2中删除，containingCluster就是标记cluster2的作用
                    if (cluster.contains(vector)) {
                        containingCluster = cluster;
                    }
                }
                // 判断距点vector最近的类nearestCluster是不是包含该点，处理情况见上
                //当所有的点分类正确后containingCluster== nearestCluster会一直成立
                //即离vector点最近的类肯定已经包含vector了，所以change会为false
                if (containingCluster != nearestCluster) {
                    if (containingCluster != null) {
                        containingCluster.remove(vector);
                    }
                    nearestCluster.addVector(vector);
                    changed = true;
                }
            }
            MemoryLogger.getInstance().checkMemory();

            if(!changed){  
                break;
            }

            // 重新计算每个类newClusters的中心点
            for (ClusterWithMean cluster : newClusters) {
                cluster.recomputeClusterMean();
            }
        }
        //返回分好的类别
        return newClusters;
    }