每日算法 — 使用java实现K-means聚类：无监督学习与中心点迭代优化

K-means是最经典、应用最广泛的无监督聚类算法之一，由Stuart Lloyd于1957年提出，后经James MacQueen于1967年正式命名。K-means通过迭代优化将n个样本划分为k个簇，使得簇内样本之间的相似度最大化、簇间差异最大化。该算法被广泛应用于客户分群、图像分割、文档聚类、异常检测等数据挖掘场景。

核心思想

K-means的核心目标是最小化簇内平方和（Within-Cluster Sum of Squares, WCSS）：

$$J = \sum_{i=1}^{k} \sum_{x \in C_i} ||x – \mu_i||^2$$

其中$C_i$为第i个簇，$\mu_i$为该簇的中心点（质心）。算法通过交替执行”分配”和”更新”两个步骤，逐步降低目标函数值直至收敛。

算法步骤

初始化：随机选择k个样本作为初始质心
分配步骤（E步）：将每个样本分配到距离最近的质心所属簇
更新步骤（M步）：重新计算每个簇的质心（簇内所有样本的均值）
收敛判断：若质心不再变化或变化小于阈值，算法终止；否则返回步骤2

距离度量

K-means通常使用欧几里得距离衡量样本与质心的相似度：

$$d(x, \mu) = \sqrt{\sum_{j=1}^{m}(x_j – \mu_j)^2}$$

在实现中，为减少计算量通常比较距离的平方而省略开方操作。

完整可运行代码

import java.util.*;

/**
 * K-means聚类算法实现
 * 时间复杂度: O(iterations * k * n * d)
 * 空间复杂度: O(k * d + n)
 */
public class KMeans {

    private final int k; // 簇的数量
    private final int maxIterations; // 最大迭代次数
    private final double epsilon; // 收敛阈值
    private double[][] centroids; // 质心
    private int[] labels; // 每个样本的簇标签

    public KMeans(int k, int maxIterations, double epsilon) {
        this.k = k;
        this.maxIterations = maxIterations;
        this.epsilon = epsilon;
    }

    /**
     * 执行聚类
     * @param data 输入数据，每行一个样本
     * @return 每个样本的簇标签
     */
    public int[] fit(double[][] data) {
        int n = data.length;
        int d = data[0].length;

        labels = new int[n];
        centroids = new double[k][d];

        // 随机初始化质心
        initializeCentroids(data);

        for (int iter = 0; iter < maxIterations; iter++) {
            // 分配步骤：将每个样本分配到最近的质心
            boolean changed = assignClusters(data);

            if (!changed) {
                System.out.println("收敛于第 " + (iter + 1) + " 次迭代");
                break;
            }

            // 更新步骤：重新计算质心
            double maxShift = updateCentroids(data);

            if (maxShift < epsilon) {
                System.out.println("质心变化小于阈值，收敛于第 " + (iter + 1) + " 次迭代");
                break;
            }
        }

        return labels;
    }

    /**
     * 随机选择k个样本作为初始质心
     */
    private void initializeCentroids(double[][] data) {
        int n = data.length;
        Random random = new Random(42); // 固定种子确保可复现
        Set<Integer> selected = new HashSet<>();

        for (int i = 0; i < k; ) {
            int idx = random.nextInt(n);
            if (selected.add(idx)) {
                centroids[i] = data[idx].clone();
                i++;
            }
        }
    }

    /**
     * 分配步骤：将样本分配到最近质心
     * @return 是否有样本改变了所属簇
     */
    private boolean assignClusters(double[][] data) {
        boolean changed = false;

        for (int i = 0; i < data.length; i++) {
            int nearestCluster = findNearestCentroid(data[i]);
            if (labels[i] != nearestCluster) {
                labels[i] = nearestCluster;
                changed = true;
            }
        }

        return changed;
    }

    /**
     * 找到距离样本最近的质心索引
     */
    private int findNearestCentroid(double[] point) {
        int nearest = 0;
        double minDist = squaredDistance(point, centroids[0]);

        for (int i = 1; i < k; i++) {
            double dist = squaredDistance(point, centroids[i]);
            if (dist < minDist) {
                minDist = dist;
                nearest = i;
            }
        }

        return nearest;
    }

    /**
     * 计算欧几里得距离的平方
     */
    private double squaredDistance(double[] a, double[] b) {
        double sum = 0.0;
        for (int i = 0; i < a.length; i++) {
            double diff = a[i] - b[i];
            sum += diff * diff;
        }
        return sum;
    }

    /**
     * 更新步骤：重新计算质心位置
     * @return 最大质心移动距离
     */
    private double updateCentroids(double[][] data) {
        int d = data[0].length;
        double[][] newCentroids = new double[k][d];
        int[] counts = new int[k];

        // 累加每个簇的样本坐标
        for (int i = 0; i < data.length; i++) {
            int cluster = labels[i];
            counts[cluster]++;
            for (int j = 0; j < d; j++) {
                newCentroids[cluster][j] += data[i][j];
            }
        }

        // 计算均值
        for (int i = 0; i < k; i++) {
            if (counts[i] > 0) {
                for (int j = 0; j < d; j++) {
                    newCentroids[i][j] /= counts[i];
                }
            }
        }

        // 计算最大移动距离
        double maxShift = 0.0;
        for (int i = 0; i < k; i++) {
            double shift = Math.sqrt(squaredDistance(centroids[i], newCentroids[i]));
            if (shift > maxShift) {
                maxShift = shift;
            }
            centroids[i] = newCentroids[i];
        }

        return maxShift;
    }

    /**
     * 计算轮廓系数（Silhouette Score）评估聚类质量
     */
    public double silhouetteScore(double[][] data) {
        int n = data.length;
        double totalScore = 0.0;

        for (int i = 0; i < n; i++) {
            double a = averageIntraClusterDistance(data, i);
            double b = averageNearestClusterDistance(data, i);
            totalScore += (b - a) / Math.max(a, b);
        }

        return totalScore / n;
    }

    private double averageIntraClusterDistance(double[][] data, int idx) {
        int cluster = labels[idx];
        double sum = 0.0;
        int count = 0;

        for (int i = 0; i < data.length; i++) {
            if (labels[i] == cluster && i != idx) {
                sum += Math.sqrt(squaredDistance(data[idx], data[i]));
                count++;
            }
        }

        return count == 0 ? 0 : sum / count;
    }

    private double averageNearestClusterDistance(double[][] data, int idx) {
        int cluster = labels[idx];
        double minAvg = Double.MAX_VALUE;

        for (int c = 0; c < k; c++) {
            if (c == cluster) continue;

            double sum = 0.0;
            int count = 0;
            for (int i = 0; i < data.length; i++) {
                if (labels[i] == c) {
                    sum += Math.sqrt(squaredDistance(data[idx], data[i]));
                    count++;
                }
            }

            if (count > 0) {
                double avg = sum / count;
                if (avg < minAvg) {
                    minAvg = avg;
                }
            }
        }

        return minAvg == Double.MAX_VALUE ? 0 : minAvg;
    }

    public double[][] getCentroids() {
        return centroids;
    }

    public static void main(String[] args) {
        // 生成示例数据：三个二维高斯分布
        double[][] data = new double[300][2];
        Random rand = new Random(42);

        // 簇1: 中心(2, 2)
        for (int i = 0; i < 100; i++) {
            data[i][0] = 2 + rand.nextGaussian();
            data[i][1] = 2 + rand.nextGaussian();
        }

        // 簇2: 中心(8, 8)
        for (int i = 100; i < 200; i++) {
            data[i][0] = 8 + rand.nextGaussian();
            data[i][1] = 8 + rand.nextGaussian();
        }

        // 簇3: 中心(2, 8)
        for (int i = 200; i < 300; i++) {
            data[i][0] = 2 + rand.nextGaussian();
            data[i][1] = 8 + rand.nextGaussian();
        }

        KMeans kmeans = new KMeans(3, 100, 1e-4);
        int[] labels = kmeans.fit(data);

        // 统计每个簇的样本数
        int[] counts = new int[3];
        for (int label : labels) {
            counts[label]++;
        }
        System.out.println("各簇样本数: " + Arrays.toString(counts));

        // 输出质心
        double[][] centroids = kmeans.getCentroids();
        System.out.println("质心坐标:");
        for (int i = 0; i < centroids.length; i++) {
            System.out.printf("  簇%d: (%.3f, %.3f)%n", i, centroids[i][0], centroids[i][1]);
        }

        // 计算轮廓系数
        double score = kmeans.silhouetteScore(data);
        System.out.printf("轮廓系数: %.4f%n", score);
    }
}

K-means++改进初始化

K-means对初始质心敏感，可能陷入局部最优。K-means++通过概率化初始质心选择显著提升聚类质量：第一个质心随机选，后续质心以与最近已有质心距离成正比的的概率选取。

private void kmeansPlusPlusInit(double[][] data) {
    int n = data.length;
    Random random = new Random(42);
    centroids[0] = data[random.nextInt(n)].clone();

    double[] minDistances = new double[n];
    for (int c = 1; c < k; c++) {
        double totalDist = 0.0;
        for (int i = 0; i < n; i++) {
            double d = squaredDistance(data[i], centroids[findNearestCentroid(data[i])]);
            minDistances[i] = d;
            totalDist += d;
        }

        // 轮盘赌选择
        double threshold = random.nextDouble() * totalDist;
        double sum = 0.0;
        for (int i = 0; i < n; i++) {
            sum += minDistances[i];
            if (sum >= threshold) {
                centroids[c] = data[i].clone();
                break;
            }
        }
    }
}

优缺点分析

优点	缺点
实现简单，计算高效	需要预先指定k值
收敛速度快	对初始质心敏感
可扩展性好	对异常值敏感
适用于大规模数据	假设簇为球形分布

应用场景

客户分群：根据消费行为将用户分为不同价值群体
图像压缩：通过聚类减少颜色数量实现矢量量化
文档聚类：将相似主题的新闻或论文自动归类
异常检测：远离所有质心的样本视为异常点
地理位置分析：基于位置数据识别热点区域

Tagged with: K-means 数据挖掘无监督学习机器学习聚类算法轮廓系数