一、引言
在精准营销、用户画像和推荐系统中，将客户按照行为特征划分为不同群体是核心需求。K均值聚类（K-Means Clustering）因其简单高效、易于实现，成为最广泛使用的无监督聚类算法。它通过迭代优化将n个样本划分到k个簇中，使得簇内样本之间的相似度最大化、簇间差异最大化。然而，K值的选择一直是个难题——肘部法则（Elbow Method）为此提供了直观且有效的解决方案。本文将用Java从零实现K均值聚类与肘部法则自动选K，并结合客户消费数据展示完整的分群流程。
二、算法原理
2.1 K均值核心步骤
- 初始化：随机选择k个样本作为初始质心（Centroid）；
- 分配步（E-Step）：将每个样本分配到距离最近的质心所在簇；
- 更新步（M-Step）：重新计算每个簇的质心（簇内样本均值）；
- 迭代：重复步骤2~3，直到质心不再变化或达到最大迭代次数。
该过程本质上是期望最大化（EM）算法在硬分配场景下的特例，目标是最小化平方误差和（SSE）：
$$SSE = \sum_{i=1}^{k} \sum_{x \in C_i} ||x – \mu_i||^2$$
2.2 肘部法则选K
随着k增大，SSE单调递减。当k小于真实簇数时，SSE下降很快；当k超过真实簇数后，SSE下降趋于平缓。肘部法则通过绘制”K-SSE”曲线，选择拐点（肘部）对应的k值作为最优簇数。
2.3 K-Means++初始化优化
随机初始化可能导致收敛到局部最优。K-Means++改进策略：
- 随机选第一个质心；
- 对每个样本，计算它到已选质心的最短距离D(x)；
- 以概率D(x)²/ΣD(x)²选择下一个质心；
- 重复直至选出k个质心。
该策略使初始质心相互远离，显著提升聚类质量。
三、完整Java实现
import java.util.*;
/**
* K-Means聚类算法Java实现
* 支持K-Means++初始化与肘部法则自动选K
*/
public class KMeansClustering {
private final int k; // 簇数量
private final int maxIterations; // 最大迭代次数
private final double epsilon; // 质心变化阈值（收敛判定）
private final boolean useKMeansPlusPlus; // 是否使用K-Means++初始化
private final Random random;
private double[][] centroids; // 质心 [k][features]
private int[] labels; // 每个样本的簇标签
private double finalSSE; // 最终平方误差和
public KMeansClustering(int k, int maxIterations, double epsilon,
boolean useKMeansPlusPlus, long seed) {
this.k = k;
this.maxIterations = maxIterations;
this.epsilon = epsilon;
this.useKMeansPlusPlus = useKMeansPlusPlus;
this.random = new Random(seed);
}
/**
* 训练聚类模型
* @param data 样本数据 [nSamples][nFeatures]
* @return 每个样本的簇标签
*/
public int[] fit(double[][] data) {
int n = data.length;
int m = data[0].length;
labels = new int[n];
centroids = new double[k][m];
// 初始化质心
if (useKMeansPlusPlus) {
initKMeansPlusPlus(data);
} else {
initRandom(data);
}
// EM迭代
for (int iter = 0; iter < maxIterations; iter++) {
// E-Step: 分配样本到最近质心
boolean changed = assignClusters(data);
// M-Step: 更新质心
double maxShift = updateCentroids(data);
// 收敛判定：无样本改变归属 或 质心移动极小
if (!changed || maxShift < epsilon) {
System.out.println("K-Means在第" + (iter + 1) + "轮收敛");
break;
}
}
finalSSE = computeSSE(data);
return labels;
}
/**
* 随机初始化质心
*/
private void initRandom(double[][] data) {
int n = data.length;
Set<Integer> chosen = new HashSet<>();
for (int i = 0; i < k; i++) {
int idx;
do { idx = random.nextInt(n); } while (chosen.contains(idx));
chosen.add(idx);
centroids[i] = data[idx].clone();
}
}
/**
* K-Means++初始化
*/
private void initKMeansPlusPlus(double[][] data) {
int n = data.length;
int m = data[0].length;
// 第一个质心随机选
centroids[0] = data[random.nextInt(n)].clone();
double[] minDistSq = new double[n];
for (int c = 1; c < k; c++) {
double totalDist = 0;
for (int i = 0; i < n; i++) {
double d = distanceSq(data[i], centroids, c);
minDistSq[i] = d;
totalDist += d;
}
// 按距离平方概率选择下一个质心
double threshold = random.nextDouble() * totalDist;
double sum = 0;
int chosen = 0;
for (int i = 0; i < n; i++) {
sum += minDistSq[i];
if (sum >= threshold) {
chosen = i;
break;
}
}
centroids[c] = data[chosen].clone();
}
}
/**
* 计算样本到已选质心的最短距离平方
*/
private double distanceSq(double[] point, double[][] centroids, int numCentroids) {
double min = Double.MAX_VALUE;
for (int i = 0; i < numCentroids; i++) {
double d = euclideanSq(point, centroids[i]);
if (d < min) min = d;
}
return min;
}
/**
* 分配样本到最近质心
* @return true表示有样本改变了簇归属
*/
private boolean assignClusters(double[][] data) {
boolean changed = false;
for (int i = 0; i < data.length; i++) {
int bestCluster = -1;
double minDist = Double.MAX_VALUE;
for (int c = 0; c < k; c++) {
double d = euclideanSq(data[i], centroids[c]);
if (d < minDist) {
minDist = d;
bestCluster = c;
}
}
if (labels[i] != bestCluster) {
labels[i] = bestCluster;
changed = true;
}
}
return changed;
}
/**
* 更新质心为簇内样本均值
* @return 最大质心移动距离
*/
private double updateCentroids(double[][] data) {
int m = data[0].length;
double[][] newCentroids = new double[k][m];
int[] counts = new int[k];
for (int i = 0; i < data.length; i++) {
int c = labels[i];
for (int j = 0; j < m; j++) {
newCentroids[c][j] += data[i][j];
}
counts[c]++;
}
double maxShift = 0;
for (int c = 0; c < k; c++) {
if (counts[c] == 0) continue; // 空簇保持原质心
for (int j = 0; j < m; j++) {
newCentroids[c][j] /= counts[c];
}
double shift = Math.sqrt(euclideanSq(centroids[c], newCentroids[c]));
if (shift > maxShift) maxShift = shift;
centroids[c] = newCentroids[c];
}
return maxShift;
}
/**
* 计算欧氏距离平方（避免开方，提升速度）
*/
private double euclideanSq(double[] a, double[] b) {
double sum = 0;
for (int i = 0; i < a.length; i++) {
double diff = a[i] - b[i];
sum += diff * diff;
}
return sum;
}
/**
* 计算平方误差和（SSE）
*/
public double computeSSE(double[][] data) {
double sse = 0;
for (int i = 0; i < data.length; i++) {
sse += euclideanSq(data[i], centroids[labels[i]]);
}
return sse;
}
/**
* 预测新样本所属簇
*/
public int predict(double[] point) {
int best = 0;
double minDist = euclideanSq(point, centroids[0]);
for (int c = 1; c < k; c++) {
double d = euclideanSq(point, centroids[c]);
if (d < minDist) {
minDist = d;
best = c;
}
}
return best;
}
public double[][] getCentroids() { return centroids; }
public double getFinalSSE() { return finalSSE; }
// ==================== 肘部法则 ====================
/**
* 肘部法则：尝试k从1到maxK，返回推荐的最优k值与SSE列表
* @param data 样本数据
* @param maxK 最大尝试k值
* @return [推荐k值, SSE数组(k=1~maxK)]
*/
public static Object[] elbowMethod(double[][] data, int maxK, long seed) {
double[] sseValues = new double[maxK];
for (int k = 1; k <= maxK; k++) {
KMeansClustering km = new KMeansClustering(k, 100, 1e-4, true, seed);
km.fit(data);
sseValues[k - 1] = km.getFinalSSE();
System.out.printf("k=%d, SSE=%.4f%n", k, sseValues[k - 1]);
}
// 自动选择肘部：计算二阶导数最大的点
int bestK = 1;
double maxCurvature = -1;
for (int i = 1; i < maxK - 1; i++) {
// 简化：计算相邻斜率变化
double slope1 = sseValues[i] - sseValues[i - 1];
double slope2 = sseValues[i + 1] - sseValues[i];
double curvature = Math.abs(slope1 - slope2);
if (curvature > maxCurvature) {
maxCurvature = curvature;
bestK = i + 1; // 索引+1对应k值
}
}
return new Object[]{bestK, sseValues};
}
// ==================== 客户分群场景 ====================
static class Customer {
String id;
double annualSpend; // 年消费金额（万元）
double visitFreq; // 月均访问次数
double avgOrderValue; // 平均订单金额
double loyaltyScore; // 忠诚度评分（0~100）
Customer(String id, double s, double f, double v, double l) {
this.id = id;
this.annualSpend = s;
this.visitFreq = f;
this.avgOrderValue = v;
this.loyaltyScore = l;
}
double[] toVector() {
return new double[]{annualSpend, visitFreq, avgOrderValue, loyaltyScore};
}
@Override
public String toString() {
return String.format("%s[消费%.1f, 访问%.1f次, 客单%.1f, 忠诚%.1f]",
id, annualSpend, visitFreq, avgOrderValue, loyaltyScore);
}
}
public static void main(String[] args) {
Random rand = new Random(42);
int n = 500;
// 构造模拟客户数据：分为4类隐群体
Customer[] customers = new Customer[n];
double[][] data = new double[n][4];
for (int i = 0; i < n; i++) {
// 4个隐群体，各125人
int group = i / 125;
double spend, freq, order, loyal;
switch (group) {
case 0: // 高价值忠诚客户
spend = 8 + rand.nextGaussian() * 2;
freq = 15 + rand.nextGaussian() * 3;
order = 0.5 + rand.nextGaussian() * 0.1;
loyal = 85 + rand.nextGaussian() * 10;
break;
case 1: // 高频低额客户
spend = 3 + rand.nextGaussian() * 1;
freq = 25 + rand.nextGaussian() * 5;
order = 0.1 + rand.nextGaussian() * 0.03;
loyal = 60 + rand.nextGaussian() * 15;
break;
case 2: // 大额低频客户
spend = 10 + rand.nextGaussian() * 3;
freq = 3 + rand.nextGaussian() * 1;
order = 3.0 + rand.nextGaussian() * 0.8;
loyal = 45 + rand.nextGaussian() * 10;
break;
default: // 低价值流失风险客户
spend = 1 + rand.nextGaussian() * 0.5;
freq = 2 + rand.nextGaussian() * 1;
order = 0.4 + rand.nextGaussian() * 0.2;
loyal = 20 + rand.nextGaussian() * 10;
break;
}
customers[i] = new Customer("C" + String.format("%03d", i), spend, freq, order, loyal);
data[i] = customers[i].toVector();
}
// 特征标准化（Z-Score）
standardize(data);
// 肘部法则选K
System.out.println("=== 肘部法则自动选K ===");
Object[] elbowResult = elbowMethod(data, 8, 42);
int bestK = (Integer) elbowResult[0];
double[] sseValues = (double[]) elbowResult[1];
System.out.println("\n推荐K值: " + bestK);
System.out.println("各K对应SSE: " + Arrays.toString(sseValues));
// 使用最优K训练最终模型
System.out.println("\n=== K=" + bestK + " 聚类结果 ===");
KMeansClustering model = new KMeansClustering(bestK, 200, 1e-6, true, 42);
int[] labels = model.fit(data);
// 输出每簇特征
System.out.println("\n各簇质心（标准化后）:");
double[][] centroids = model.getCentroids();
String[] featureNames = {"年消费", "访问频次", "客单价", "忠诚度"};
for (int c = 0; c < bestK; c++) {
System.out.printf("簇%d: ", c);
for (int j = 0; j < 4; j++) {
System.out.printf("%s=%.3f ", featureNames[j], centroids[c][j]);
}
System.out.println();
}
// 每簇随机展示3个客户
System.out.println("\n各簇客户样例:");
for (int c = 0; c < bestK; c++) {
System.out.println("\n--- 簇" + c + " ---");
int shown = 0;
for (int i = 0; i < n && shown < 3; i++) {
if (labels[i] == c) {
System.out.println(" " + customers[i]);
shown++;
}
}
}
// 与随机初始化的对比
System.out.println("\n=== K-Means++ vs 随机初始化 ===");
KMeansClustering kmPP = new KMeansClustering(4, 100, 1e-6, true, 42);
kmPP.fit(data);
KMeansClustering kmRand = new KMeansClustering(4, 100, 1e-6, false, 42);
kmRand.fit(data);
System.out.printf("K-Means++ SSE: %.4f%n", kmPP.getFinalSSE());
System.out.printf("随机初始化 SSE: %.4f%n", kmRand.getFinalSSE());
System.out.printf("SSE改善: %.2f%%%n",
(1 - kmPP.getFinalSSE() / kmRand.getFinalSSE()) * 100);
}
/**
* Z-Score标准化：均值为0，标准差为1
*/
static void standardize(double[][] data) {
int n = data.length;
int m = data[0].length;
for (int j = 0; j < m; j++) {
double sum = 0, sqSum = 0;
for (int i = 0; i < n; i++) {
sum += data[i][j];
sqSum += data[i][j] * data[i][j];
}
double mean = sum / n;
double std = Math.sqrt(sqSum / n - mean * mean);
if (std < 1e-10) std = 1; // 避免除零
for (int i = 0; i < n; i++) {
data[i][j] = (data[i][j] - mean) / std;
}
}
}
}
四、复杂度分析
- 时间复杂度：每轮迭代需计算n个样本到k个质心的距离，O(n × k × d)，d为特征维度。T轮迭代总复杂度O(T × n × k × d)。K-Means++初始化额外增加O(k × n × d)。
- 空间复杂度：O(n + k × d)，需存储样本标签和k个质心。
- 肘部法则：需运行maxK次完整K-Means，总复杂度O(maxK × T × n × k_avg × d)。
五、总结
本文围绕客户分群场景，用Java完整实现了K均值聚类体系：
- K-Means++初始化通过距离平方概率采样，使初始质心相互远离，SSE相比随机初始化改善显著；
- 肘部法则自动识别最优簇数，避免了人工试探的低效；
- Z-Score标准化消除了量纲差异对距离度量的影响，是聚类前的必要步骤；
- 模拟实验成功从500名客户中识别出4个特征鲜明的群体，验证了算法有效性。
读者可进一步探索：轮廓系数（Silhouette Score）作为补充选K指标、Mini-Batch K-Means加速大规模数据、或结合PCA降维后可视化聚类效果。
