K-means Clustering

k-means算法源于信号处理中的一种向量量化方法，现作为一种聚类分析方法。它的目的是把每个数据点划分到k个聚类中心范围里，使得每个点都属于离它最近的聚类中心对应的类别。

算法描述

已知数据集$(x_1,x_2,…,x_n)$，其中每个数据都是一个$p$维特征向量，k-means 算法就是要把这些输入数据划分到 k 个类别集合$S_i$中，目标函数为：

$$\underset{S}{\mathrm{argmin}}\sum^k_{i=1}\sum_{x\in S_i}\Arrowvert x-\mu_i\Arrowvert^2$$

其中$\mu_i$是$S_i$中所有点的均值。

聚类中心的更新函数为：

$$k_i=\frac{1}{\mid S_i\mid}\sum_{x\in S_i}x$$

由于上述最小化问题是一个 NP 困难)问题，因此只能采用启发式迭代方法来进行求解。

算法步骤

选择 k 个数据点作为初始聚类中心
Repeat
		计算每个数据点到聚类中心的距离，并将其划分为离它最近的类别中，形成 k 个簇
		根据目标函数重新计算每个类别的聚类中心
Until 聚类中心不发生变化或达到最大迭代此数

优点：原理简单，易于实现，可解释度较高，参数仅有聚类中心个数 k

缺点：初始化聚类中心的选取不好把握，可能收敛于局部极值，且在大规模数据中收敛速度较慢，对异常点比较敏感

距离度量

欧式距离

$$d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$

曼哈顿距离

$$d=\mid x_1-x_2\mid+\mid y_1-y_2\mid$$

切比雪夫距离

$$d=\max(\mid x_1-x_2\mid,\mid y_1-y_2\mid)$$

余弦距离

$$d=\frac{x_1x_2+y_1y_2}{\sqrt{(x_1+y_1)^2}\sqrt{(x_2+y_2)^2}}$$

代码实现

public class KMeans {

    public double[][][] kmeans(double[][] data, int k, int epoch, double error) {
        int n = data.length;//数据个数
        int p = data[0].length;//每个数据的特征个数

        //初始化聚类中心
        double[][] kCenter = new double[k][p];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < p; j++) {
                kCenter[i][j] = data[i][j];
            }
        }

        double[][][] temp = new double[k][n][p];

        //聚类之后的结果，三维数组，第一维度为类别个数，第二维度为数据个数，第三维度为特征个数
//        double[][][] resData = new double[k][n][p];

        //定义每种类别的样本个数
//        int[] numOfCi = new int[k];

        //迭代epoch次
        for (int iter = 0; iter < epoch; iter++) {

            double[][][] resData = new double[k][n][p];
            int[] numOfCi = new int[k];

            //将数据聚类到离它最近的聚类中心类别中
            for (int i = 0; i < n; i++) {
                double minDistance = Double.MAX_VALUE;
                int minDisIndex = 0;
                for (int j = 0; j < k; j++) {
                    double curDistance = distance(kCenter[j], data[i]);
                    if (curDistance < minDistance) {
                        minDistance = curDistance;
                        minDisIndex = j;
                    }
                }
                resData[minDisIndex][numOfCi[minDisIndex]++] = data[i];
            }

            //重新计算聚类中心
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < p; j++) {
                    double eachDataP = 0;
                    for (int d = 0; d < numOfCi[i]; d++) {
                        eachDataP += resData[i][d][j];
                    }
                    kCenter[i][j] = eachDataP / numOfCi[i];
                }
            }

            //计算目标函数，若小于设定值则退出迭代
            double curError = 0.0;
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < numOfCi[i]; j++) {
                    curError += distance(resData[i][j], kCenter[i]);
                }
            }
            if (curError < error) {
                return resData;
            }

            if (iter+1 == epoch) {
                return resData;
            }
        }

        return temp;
    }

    public double distance(double[] x, double[] y) {
        int feaLen = x.length;
        double dis = 0;
        for (int i = 0; i < feaLen; i++) {
            dis += Math.pow(x[i] - y[i], 2);
        }
        dis = Math.sqrt(dis);
        return dis;
    }

    public static void main(String[] args) {
        KMeans kMeans = new KMeans();
        double[][] data = {
                {1.0, 2.0},
                {2.0, 7.0},
                {3.0, 1.0}
        };
        int k = 2;
        int epoch = 3;
        double error = 0.0;
        double[][][] res = kMeans.kmeans(data, k, epoch, error);
        for (int i = 0; i < k; i++) {
            System.out.println("Category "+i+" :");
            for (int j = 0; j < res[i].length; j++) {
                for (int f = 0; f < res[i][j].length; f++) {
                    if (res[i][j][f] != 0.0) {
                        System.out.print(res[i][j][f]);
                        System.out.print(" ");
                    }
                }
                System.out.println();
            }
        }
    }
}

优化算法

k-means++

动机：初始化聚类中心对之后的聚类结果和运行速度都有着很大的影响，因此初始化合适的聚类中心就很有必要。

策略：

1. 从输入数据集合中随机选择一个点作为第一个聚类中心$c_1$
2. 计算每一个数据与已选择聚类中心的距离，并找到最短距离，代表了当前样本与当前已有聚类中心之间最短的距离，即$d(x_i)={\mathrm{argmin}}||x_i-c_s||^2_2$ $s=1,2,…,c_{selected}$
3. 每个数据被选择为聚类中心的可能性为$\frac{d(x)^2}{\sum_{x_i\in X}d(x)^2}$，选择其中具有最大概率的数据点作为下一个聚类中心
4. 重复2、3步选择出 k 个聚类中心，并使用这些点作为初始话的聚类中心执行 k-means 算法

mini batch k-means

动机：若输入数据量特别大，那么每次都要计算所有数据点到聚类中心的距离，导致算法非常耗时。

策略：

1. 从数据集中选择一部分数据执行 k-means 算法，批样本大小为 batch size
2. 批样本大小一般通过无放回的随机抽样得到的
3. 为了提升算法的准确性，一般选择多个 batch size 执行多次 k-means 算法，选择其中最优的聚类中心

赞赏