C#实现K-Means聚类算法：从数学原理到高性能代码实践

1次阅读

共计 2193 个字符，预计需要花费 6 分钟才能阅读完成。

K-Means 聚类是数据分析中的经典算法，它能将用户按行为特征自动分组实现精准营销，也能把图像像素按颜色聚类实现智能分割。相比复杂模型，它的优势在于计算高效且结果可解释。下面我们从原理到实践完整走一遍 C# 实现过程。

算法目标是最小化平方误差函数：

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

迭代过程分为两步：
1. 将每个点分配到最近的中心点所属簇
2. 重新计算各簇的均值作为新中心点

距离度量的选择：
– 欧式距离（默认）：dist = √(∑(x_i-y_i)²)，适用于空间坐标等绝对距离重要的场景
– 余弦相似度：sim = (x·y)/(||x||·||y||)，适合文本 TF-IDF 向量等方向比绝对值重要的场景

/// <summary>
/// Min-Max 标准化（归一化到 [0,1] 范围）/// </summary>
public static double[][] Normalize(double[][] data)
{var normalized = new double[data.Length][];
    var mins = Enumerable.Range(0, data[0].Length)
        .Select(i => data.Min(x => x[i])).ToArray();
    var ranges = Enumerable.Range(0, data[0].Length)
        .Select(i => data.Max(x => x[i]) - mins[i]).ToArray();

    for (int i = 0; i < data.Length; i++)
    {normalized[i] = new double[data[i].Length];
        for (int j = 0; j < data[i].Length; j++)
            normalized[i][j] = ranges[j] == 0 ? 0 : (data[i][j] - mins[j]) / ranges[j];
    }
    return normalized;
}

/// <summary>
/// 基于距离概率分布选择初始中心点（缓解随机初始化问题）/// </summary>
public static double[][] InitCentroids(double[][] data, int k)
{var centers = new List<double[]> {data[new Random().Next(data.Length)] };

    while (centers.Count < k)
    {
        // 计算每个点到最近中心的距离平方
        var distances = data.Select(x => 
            centers.Min(c => EuclideanDistance(x, c))).ToArray();

        // 按距离概率随机选择下一个中心
        var sum = distances.Sum();
        var prob = distances.Select(d => d / sum).ToArray();
        centers.Add(data[SelectWithProbability(prob)]);
    }
    return centers.ToArray();}

/// <summary>
/// 使用 System.Numerics.Vector 加速距离计算
/// </summary>
static double SimdDistance(double[] a, double[] b)
{
    double sum = 0;
    int i = 0;

    // 每次处理 Vector<double>.Count 个元素
    for (; i <= a.Length - Vector<double>.Count; i += Vector<double>.Count)
    {var va = new Vector<double>(a, i);
        var vb = new Vector<double>(b, i);
        sum += Vector.Dot(va - vb, va - vb);
    }

    // 处理剩余元素
    for (; i < a.Length; i++)
        sum += Math.Pow(a[i] - b[i], 2);

    return Math.Sqrt(sum);
}

方法	均值	内存分配
原始循环	158ms	2.5MB
LINQ 版本	210ms	4.1MB
SIMD 优化	89ms	1.8MB
并行版本	52ms	2.2MB

// 使用 ArrayPool 减少 GC 压力
double[] rented = ArrayPool<double>.Shared.Rent(dimensions);
try {// 操作租用的数组} finally {ArrayPool<double>.Shared.Return(rented);
}