65.9K
CodeProject 正在变化。 阅读更多。
Home

比较 K-Means 和其他数据聚类算法

Nicolas DESCARTES
starIconstarIconstarIconstarIconstarIcon

5.00/5 (6投票s)

2024 年 1 月 8 日

CPOL

13分钟阅读

viewsIcon

8273

downloadIcon

234

应为聚类任务选择哪种聚类算法？

引言

聚类是机器学习和数据分析中的一种技术，它根据某些特征或特性将相似的数据点分组。聚类的目标是识别数据集中自然存在的模式或结构，并将其组织成子集或簇。同一簇内的数据点应比其他簇中的数据点更相似。

本质上，聚类能够发现数据中固有的结构或关系，从而深入了解其底层组织。这项技术广泛应用于各种领域，包括模式识别、图像分析、客户细分和异常检测。常见的聚类算法包括 K-Means、层次聚类、CURE 和 DBSCAN。

在本系列文章中，我们将用 C# 实现主要的聚类技术，并努力比较每种技术，评估它们的优缺点。这项探索将有助于深入了解每种算法更适合的场景和数据类型。

本文最初发布于 此处。

什么是聚类？

聚类是机器学习和数据分析中的一种技术，它根据一组数据点固有的相似性将它们分组到子集或簇中。聚类的主要目标是组织和揭示数据中的模式，从而识别有意义的结构或关系。

该过程涉及将数据划分为组，使得同一簇内的数据点比其他簇中的数据点更相似。相似性通常使用距离度量来衡量，并且采用各种算法（如 K-Means、层次聚类和 DBSCAN）来执行聚类任务。例如，在上图中，识别三个明显分离的簇似乎很自然。

然而，聚类有时会变得更具挑战性，如下面的示例所示，其中簇呈现出更不规则的形状，并且不易被线性边界分开。

聚类算法应具备哪些特征？

通常的回答是，一如既往：这取决于具体情况。它确实取决于所考虑的具体应用。在实践中，某些算法在某些情况下表现出色，而在其他情况下则表现不佳。有些算法可能表现出对挑战性场景的适应性，但计算成本很高。在本节中，我们的目标是强调这些通常至关重要的特征。

为确保最大程度的简洁性，我们的研究将仅专注于连续输入变量，只考虑可以定义距离和角度的欧几里得空间。此限制是由于某些算法涉及计算点平均值，而在欧几里得空间中这项任务更为直接。

我们将如何比较算法？

我们在此系列中的目标是评估各种最先进的算法，我们将通过使用由两个特征 X 和 Y 组成的简单预定义数据集来实现这一目标。

  • 第一个数据集是最基础的，它将使我们能够观察算法在简单场景中的表现。

  • 第二个数据集几乎相同，但包含两个离群点，从而可以了解算法在存在离群点时的行为。

  • 最后，第三个数据集探索了当数据不是线性可分的或呈现不规则形状时的算法性能。

目标是评估我们分析的每种算法在这些数据集上的表现，并确定所得簇的相关性。具体来说，我们将详细深入探讨以下问题。

是否需要预先定义簇的数量？

确定合适的簇数量一直是一个挑战，导致某些算法（如成熟的 K-Means）需要将此数量作为输入。这需要我们事先了解数据集中潜在的组数。

重要

需要注意的是，此要求不一定是一个缺点，因为指定簇的数量可能与特定的业务需求相符。

相反，其他算法不强制要求预定的簇数量；相反，它们在内在过程中将其自动确定。

对离群点的敏感性意味着什么？

离群点是与数据集中其余部分显著不同的数据点，通常位于分布的中心趋势的异常距离处。这些数据点被认为与数据集中大多数其他观测值相比非同寻常或非典型。离群点会影响统计分析和机器学习算法，可能导致结果失真或模型偏差。识别和处理离群点在数据预处理中至关重要，以确保分析过程的鲁棒性和准确性。

The two points highlighted in red are evidently anomalous, as they do not align with the other points.

红色标记的两个点明显是异常的，因为它们与其他点不一致。

第二个数据集将使我们能够观察算法对离群点的敏感程度。

当数据呈现不规则形状时会发生什么？

大多数算法在线性可分数据（即可通过直线或平面分割的数据）上运行良好。但是，有时会出现数据显示出不规则或退化形状的情况，如下图所示。在这种情况下，算法是否能够准确地聚类数据集？

算法的实现是否简单，并且是否显示出效率？

最后但同样重要的是，评估算法在特定编程语言中是否易于实现和理解至关重要。一个过于复杂、需要非凡数学技能或难以表述的算法可能无法广泛使用。

其效率同样重要。再次出现问题：一个能够处理离群点或区分不规则形状的高效方法，如果其计算复杂度是指数级的，那么它的价值有多大？

在本系列中，我们将努力审查所研究算法的每一个特征。这种方法将为每种算法的优缺点提供更清晰的见解。

我们将分析哪些算法？

存在大量的聚类算法以及每种算法的各种版本。在这种情况下，我们将重点关注三种：首先是广泛使用的 K-Means，然后是层次方法，最后是经常被低估的 DBSCAN 技术。

在深入研究这三种算法的 C# 实现之前，我们将在本文中简要概述 Visual Studio 项目的逻辑结构。

正如在前一篇文章中所解释的，我们将仅使用一个具有两个特征 X 和 Y 的数据集。因此，我们将有一个非常简单的 `DataPoint` 类来建模一个记录。

public class DataPoint : IEquatable<DataPoint>
{
    public double X { get; set; }

    public double Y { get; set; }

    public double ComputeDistance(DataPoint other)
    {
        var X0 = other.X; var Y0 = other.Y;
        return Math.Sqrt((X-X0)*(X-X0) + (Y-Y0) * (Y-Y0));
    }

    public bool Equals(DataPoint? other)
    {
        return other != null && X == other.X && Y == other.Y;
    }

    public override int GetHashCode()
    {
        return X.GetHashCode() ^ Y.GetHashCode();
    }
}

重要

请注意，我们实现了一个 `ComputeDistance` 方法来评估点之间的相似性或不相似性。选择的距离度量是欧几里得距离。在实际场景中，距离应通过依赖注入作为构造函数中的参数提供。

数据集就是 `DataPoint` 对象的一个列表。

public class Dataset
{
    public List<DataPoint> Points { get; set; }

    private Dataset() { Points = new List<DataPoint>(); }

    public static Dataset Load(string path)
    {
        var set = new Dataset();

        var contents = File.ReadAllLines(path);
        foreach (var content in contents.Skip(1))
        {
            var d = content.Split(';');
            var point = new DataPoint() 
                        { X = Convert.ToDouble(d[0]), Y = Convert.ToDouble(d[1]) };
            set.Points.Add(point);
        }

        return set;
    }
}

重要

数据通过文件提供，并使用 `Load` 方法加载。

由于目标是定义簇，我们需要在 C# 中对该实体进行建模。因此，`DataCluster` 就是一个带有簇编号标签的 `DataPoint` 对象列表。

public class DataCluster : IEquatable<DataCluster>
{
    public List<DataPoint> Points { get; set; }

    public string Cluster { get; set; }        

    public DataPoint GetCentroid()
    {
        var avgx = Points.Average(t => t.X);
        var avgy = Points.Average(t => t.Y);

        return new DataPoint() { X = avgx, Y = avgy };
    }

    public bool Equals(DataCluster? other)
    {
        return other != null && Cluster == other.Cluster;
    }

    public override int GetHashCode()
    {
        return Cluster.GetHashCode();
    }
}

有了这些基础代码，就可以定义所有算法都需要实现的接口。

public interface IClusteringStragtegy
{
    List<DataCluster> Cluster(Dataset set, int clusters);
}

该接口仅包含一个方法，其目标是从数据集和预定的簇数量中获取 `DataCluster` 对象。

为了全面起见，包含数据的文件的格式与我们前面介绍的第一个数据集的格式相似。

X;Y
0.2;0.22
0.22;0.2
0.18;0.205
0.188;0.18
0.205;0.185
0.8;0.792
0.82;0.8
0.78;0.82
0.795;0.825
0.815;0.78
0.34;0.84
0.32;0.86
0.335;0.88
0.345;0.82
0.35;0.855

现在我们可以开始我们的探索，从古老的 K-Means 开始。

什么是 K-Means？

K-Means 是一种流行的机器学习和数据分析聚类算法。它属于划分方法的范畴，旨在将数据集划分为特定数量的簇 (K)，其中每个数据点都属于最近均值的簇。该算法通过将数据点分配给最近的质心所在的簇，并根据分配点均值来更新质心，从而迭代地优化其簇。

K-Means 算法的基本步骤如下。请注意，我们使用了维基百科的图片。

  • 初始化

    We randomly select K data points from the dataset as initial cluster centroids.

    我们从数据集中随机选择 K 个数据点作为初始簇质心。
  • Assign

    We assign each data point to the cluster whose centroid is the closest (usually based on Euclidean distance).

    我们将每个数据点分配给其质心最近的簇（通常基于欧几里得距离）。
  • 更新

    We recalculate the centroids of each cluster based on the mean of the data points assigned to that cluster.

    我们根据分配给该簇的数据点均值重新计算每个簇的质心。
  • Repeat

    We repeat the assignment and update steps until convergence, where the centroids no longer change significantly or a predefined number of iterations is reached.

    我们重复分配和更新步骤，直到收敛，即质心不再发生显著变化，或者达到预定的迭代次数。

重要提示 1

簇的质心是该簇中所有数据点的算术平均值。

重要提示 2

K-Means 中的点初始化并非完全随机；而是旨在以一种可能将 KK 点分布在不同簇的方式进行选择。为此存在各种技术，但我们在此不深入探讨这些技术的细节。有兴趣的读者可以参考已实现的 कोड。

重要提示 3

在实际场景中，在处理数据之前对其进行标准化是很常见的做法。

C# 实现

正如在前一篇文章中所提到的，我们需要实现 `IClusteringStrategy` 接口。

public class KMeansClusteringStrategy : IClusteringStragtegy
{
    public KMeansClusteringStrategy()
    {
        // DI: Inject distance in a real-world scenario
    }

    public List<DataCluster> Cluster(Dataset set, int clusters)
    {
        var groups = Initialize(set, clusters);            
        while (true)
        {
            var changed = false;
            foreach (var point in set.Points)
            {
                var currentCluster = groups.FirstOrDefault
                                     (t => t.Points.Any(x => x == point));
                if (currentCluster == null) changed = true;

                var d = double.MaxValue; DataCluster selectedCluster = null;
                foreach (var group in groups)
                {
                    var distance = point.ComputeDistance(group.GetCentroid());
                    if (d > distance)
                    {
                        selectedCluster = group;
                        d = distance;
                    }
                }

                if (selectedCluster != currentCluster)
                {
                    selectedCluster?.Points.Add(point);
                    currentCluster?.Points.Remove(point);
                    changed = true;
                }                    
            }

            if (!changed) break;
        }

        return groups;            
    }

    #region Private Methods

    private List<DataCluster> Initialize(Dataset set, int clusters)
    {
        var results = new List<DataCluster>();

        var selectedPoints = new List<DataPoint>();

        var r = new Random(); var k = r.Next(set.Points.Count); 
        var p = set.Points.ElementAt(k); selectedPoints.Add(p);

        var c = 1;
        var cluster = new DataCluster() 
            { Cluster = c.ToString(), Points = new List<DataPoint>() { p } };
        results.Add(cluster);

        while (c < clusters) 
        {                
            var remainingPoints = set.Points.Except(selectedPoints).ToList();
            var maximum = double.MinValue; DataPoint other = null;
            foreach (var point in remainingPoints)
            {
                var distance = selectedPoints.Select(x => x.ComputeDistance(point)).Min();
                if (distance > maximum)
                {
                    maximum = distance;
                    other = point;
                }
            }

            selectedPoints.Add(other);

            c++;
            var newCluster = new DataCluster() 
                { Cluster = c.ToString(), Points = new List<DataPoint>() { other } };
            results.Add(newCluster);
        }

        return results;
    }

    #endregion
}

K-Means 以其简单性而闻名，正如前面的代码所示，只有几行代码。毫无疑问，这种简单性有助于其广泛使用。就我们而言，我们将探索该算法在我们三个数据集上的表现。

第一个数据集的结果

请记住，第一个数据集纯粹是学术性的，它是一个简单的测试，用于确保算法在简单情况下有效。

我们可以看到，正如预期的那样，簇被完美地识别出来，而且在这个特定情况下没有其他需要注意的地方。

第二个数据集的结果

第二个数据集用于说明离群点的影响。

这个结果值得进一步评论。尽管只有两个离群点（尽管有些夸张），但算法似乎陷入困境。这突显了本系列文章的一个关键见解：K-Means 对离群点高度敏感，在盲目应用此方法之前，应实施专门针对离群点检测的鲁棒预处理步骤。

第三个数据集的结果

第三个数据集用于演示算法在更具挑战性或病态情况下的表现。

注意

在这种情况下，有两个簇（而不是之前的三个）。

再次，这个结果值得进一步评论：K-Means 在处理不规则形状或非线性可分数据时面临巨大挑战。这种特性可能带来挑战。在我们的图中，相对容易看出数据是病态的，但在非常高维的实际场景中，可视化这一点变得更具挑战性。我们需要信任我们对当前问题的理解，以确保我们能够应用 K-Means 并获得准确的结果。

需要牢记

K-Means 易于理解和实现，在处理简单和球状簇时表现高效。但是，它有一些局限性：

  • 它对离群点高度敏感。
  • 它需要预定义的簇数量作为输入。
  • 它不适合形状不规则的数据集。

我们能否改进并解决其中提到的一些局限性？这是下一篇关于层次聚类的文章的主题。

什么是层次聚类？

层次聚类是一种创建簇层次结构的聚类算法。该算法根据簇之间的相似性或不相似性迭代地合并或分割簇，直到达到预定的停止标准。

有两种主要的层次聚类类型：聚集式或分裂式。

  • 聚集式层次聚类从每个数据点作为一个独立的簇开始，然后 successive 地合并最接近的簇对，直到只剩下一个簇。合并过程通常基于欧几里得距离等距离度量。

  • 分裂式层次聚类从所有数据点位于一个簇开始，然后递归地将簇分割成更小的簇，直到每个数据点位于自己的簇中。与聚集式聚类类似，分裂式聚类使用距离度量或链接标准来进行分割过程。

重要

在本篇文章中，我们将只实现聚集式层次聚类。

理论上，层次聚类的优点在于它不需要预先指定簇的数量。但是，这需要一个不容易有机确定的停止标准。因此，在本篇文章中，我们将预先定义要识别的簇的数量。

如何实现层次聚类？

想象一下我们需要聚类以下数据集的情况。

我们从每个点都在自己的簇开始（在我们的例子中，我们因此从 11 个簇开始）。随着时间的推移，通过合并两个较小的簇来形成较大的簇。但是我们如何决定合并哪两个簇呢？我们将在下一节中对此进行探讨，但现在，算法可以描述为：

WHILE we have the right number of clusters DO
   pick the best two clusters to merge
   combine those clusters into one cluster
END

我们如何决定合并哪两个簇？

实际上，有几种规则可以用来选择要合并的最佳簇。在本篇文章中，我们将使用任意两个点之间的最小距离，其中一个点从每个簇中选择。也可以使用其他规则；例如，我们可以识别质心之间距离最小的对。

  • 根据我们的规则，最接近的两个簇是 9 和 11，因此我们合并这两个簇。

  • 现在，我们将点 8 与之前的两个点（9 和 11）的簇合并，因为点 8 和 9 非常接近，而且没有其他未聚类的点对如此接近。

  • 然后，我们选择合并点 5 和 7。

  • 依此类推，直到达到所需的簇数量。

C# 实现

我们需要实现 `IClusteringStrategy` 接口。

public class HierarchicalClusteringStrategy : IClusteringStragtegy
{
    public List<DataCluster> Cluster(Dataset set, int clusters)
    {
        var results = new List<DataCluster>(); var c = 1;
        foreach (var point in set.Points)
        {
            var cluster = new DataCluster()
            {
                Cluster = c.ToString(),
                Points = new List<DataPoint> { point }
            };
            results.Add(cluster);

            c++;
        }

        var currentNumber = results.Count;
        while (currentNumber > clusters)
        {
            var minimum = double.MaxValue; var clustersToMerge = new List<DataCluster>();
            foreach (var cluster in results)
            {
                var remainingClusters = results.Where(x => x != cluster).ToList();
                foreach (var remainingCluster in remainingClusters)
                {
                    //var distance = cluster.GetCentroid().ComputeDistance
                    //(remainingCluster.GetCentroid());
                    var distance = ComputeDistanceBetweenClusters
                                   (cluster, remainingCluster);
                    if (distance < minimum)
                    {
                        minimum = distance;
                        clustersToMerge = new List<DataCluster>() 
                                          { cluster, remainingCluster };
                    }
                }
            }

            // Merge clusters
            var newCluster = new DataCluster()
            {
                Cluster = clustersToMerge.Select
                          (x => Convert.ToInt32(x.Cluster)).Min().ToString(),
                Points = clustersToMerge.SelectMany(x => x.Points).ToList()
            };

            foreach (var delete in clustersToMerge)
                results.Remove(delete);

            results.Add(newCluster);
            currentNumber = results.Count;
        }

        return results;
    }

    private double ComputeDistanceBetweenClusters
            (DataCluster dataCluster1, DataCluster dataCluster2)
    {
        var minimum = double.MaxValue;
        foreach (var point1 in dataCluster1.Points)
        {
            foreach (var point2 in dataCluster2.Points)
            {
                var distance = point1.ComputeDistance(point2);
                if (distance < minimum)
                {
                    minimum = distance;
                }
            }
        }

        return minimum;
    }
}

第一个数据集的结果

请记住，第一个数据集纯粹是学术性的，它是一个简单的测试，用于确保算法在简单情况下有效。

我们可以看到，正如预期的那样，簇被完美地识别出来，而且在这个特定情况下没有其他需要注意的地方。

第二个数据集的结果

第二个数据集用于说明离群点的影响。

尽管存在离群点，但显然层次聚类响应得当，并有效地识别出精确的簇。因此，与 K-Means 相比，层次聚类对离群点的抵抗力更强。

第三个数据集的结果

第三个数据集用于演示算法在更具挑战性或病态情况下的表现。

注意

在这种情况下，有两个簇（而不是之前的三个）。

因此，层次聚类似乎能够很好地处理不规则形状，并且不受非线性可分数据的阻碍。

需要牢记

层次聚类易于理解和实现，并且对离群点非常鲁棒。此外，它似乎非常适合不规则形状的数据集。

此外，层次聚类易于理解和实现，并且对离群点非常鲁棒。此外，它似乎非常适合不规则形状的数据集。层次聚类似乎是一种神奇的方法，这引起了为什么它不被更广泛使用的疑问。然而，一个关键点在前面的例子中并不明显：层次聚类在计算上可能很密集，并且与 K-Means 等方法相比，对于大型数据集不太适合。

层次聚类算法的效率不高。在每一步，我们都必须计算每对簇之间的距离，以便找到最佳的合并。初始步骤需要 O(n2) 时间 [nn 是数据集中记录的数量]，但后续步骤需要与 (n−1)2, (n−2)2, ... 成比例的时间。前 n 个数的平方和是 O(n3)，因此该算法是立方级的。因此，它只能用于相当少量的点。
Leskovec, Rajaraman, Ullman (海量数据挖掘)

尽管存在更优化的算法版本（特别是那些包含优先队列的算法），但执行时间仍然相对较高。因此，这种方法只能用于小型数据集。

我们能否改进并解决其中提到的一些局限性？为避免使本文过于冗长，有兴趣的读者可以在 此处 找到答案。

历史

  • 2024 年 1 月 8 日：初始版本
© . All rights reserved.