使用 .NET 集合的聚类算法

• 下载源代码 - 78.4 KB

引言

本文展示了一种算法，它利用诸如泛型集合、LINQ、分部类和 Lambda 表达式等 .NET 功能，将一组点根据其相对位置分类成组（簇）。

背景

聚类算法是一个被充分研究的主题，在互联网上很容易找到相关的文章。

每个算法的核心总是有一个或一系列循环，遍历这组点，并根据一定的标准将它们分类成组（簇）。在本文中，我将展示如何通过利用 .NET 集合类、LINQ 和 Lambda 表达式来简化算法。

首先，一些定义以建立通用的说法

• 该算法的输入数据将是一组点 {P}，设 N 为 {P} 中点的总数；以及一个数字（距离）D。
• 如果 {P} 中的两个点之间的相对（欧几里得）距离小于或等于 D，则称这两个点直接连接。
• 如果可以在它们之间建立一条直接连接的点的路径，则称 {P} 中的两个点间接连接。
• 簇是 {P} 中相互（直接或间接）连接的点的子集。
• 一个点只能属于一个簇。
• 如果一个点没有与其他任何点直接连接，那么它本身就形成一个簇。该簇只包含一个点。
• 该算法的结果将是一组簇 {C}。这组簇描述了在遵循上述规则的情况下，{P} 中的点是如何分组的。
• {C} 的每个单独成员都列出了 {P} 的一个子集。

抱歉，最后两个句子听起来比实际问题更复杂。OOP 在代码中阐明了这些问题。

使用代码

类 Point 描述了上述集合 {P} 的一个点。{P} 本身在代码中由 .NET 泛型集合 l_ListPoints 表示。类 Cluster 具有一个属性，描述簇内的 List<Point> 类型的点。{C} 在代码中由 l_ListClusters 表示。这些点的实际数据是使用 C# 的伪随机生成器生成的，并设置到一个 .NET 分部类 BasicLibrary.AuxListPoint 中（分布在文件 AuxListPoint.cs 和 points.cs 中）。最重要的是，为了示例的缘故，这些点的位置被硬编码。

图 1 显示了算法的核心

通过使用 .NET 功能提供的简化可以在步骤 6、7 和 8 的编码中看到（参见图 1）。如果我们不使用 .NET，那么我们将不得不将步骤 6、7 和 8 编码成详细的子算法来处理集合。

在代码中，这些步骤的实现看起来像

#region Main Loop
// the algorithm is inside this loop
List<Cluster> l_ListAttainableClusters;
Cluster l_c;
foreach (BasicLibrary.Point p in l_ListPoints)
{
    l_ListAttainableClusters = new List<Cluster>();
    l_ListAttainableClusters = l_ListClusters.FindAll(x => x.IsPointReachable(p));
    l_ListClusters.RemoveAll(x => x.IsPointReachable(p));
    l_c = new Cluster(l_Dist, p);
    // merge point's "reachable" clusters
    if (l_ListAttainableClusters.Count > 0)
        l_c.AnnexCluster(l_ListAttainableClusters.Aggregate((c, x) => 
          c = Cluster.MergeClusters(x, c)));
    l_ListClusters.Add(l_c);
    l_ListAttainableClusters = null;
    l_c = null;
}  // of loop over candidate points
#endregion

关注点

值得一提的是，现实生活中的聚类应用通常处理大量的点，在这种情况下，算法的性能至关重要。这里提出的算法还没有在大于五万个点的情况下进行测试；对于更大的数据集，它的性能可能是一个问题。

解决方案中有一个 WPF 应用程序和一个控制台应用程序（参见源代码）。两者都使用相同的算法。WPF 项目带有一个聚类图形显示，它色彩鲜艳，但尚未证明具有意义（图 2 和图 3 是使用两个不同的 D 值运行 WPF 应用程序的示例）。在图形中，我使用了 https://codeproject.org.cn/KB/graphics/WpfCoordExample.aspx 中描述的辅助类。