在 C#.NET 中实现 K-Means 聚类算法
4.90/5 (10投票s)
如何在 C#.NET 中实现 K-Means 聚类算法
引言
正如文章标题所示，我们将要在 C# 中实现 K-Means 聚类算法。我为了一个项目研究这个算法已经有一段时间了。它是一种优秀、简单且高效的算法，可以将一些数据分类到不同的组中。几天前，我决定用 C# 实现这个算法，现在我想带大家一步一步地完成这个过程。但首先，我们要了解 K-Means 聚类算法本身。
K-Means 聚类算法
有很多页面和网站解释 K-Means 聚类算法，但往往让你更加困惑。说实话，也有很多非常有用的、简单明了的解释。我会尽我最大的努力以最简单的方式向你展示这个算法。正如我之前所说，这个算法用于将一些数据分类到不同的组，或者，我们以后会称之为“簇”。你可能也遇到过需要将相似的项分组的情况，使得同一组的成员有很多共同点，而不同组的成员差异很大。这就是这个算法要做的。
为了更清楚地说明，让我们看看我从维基百科上找到的以下四张图片。
我将从左到右依次引用这四张图片。所以，让我们先看看左边的图片。在这张图片中，你看到了一组我们要聚类的灰色方块。你还可以看到三个红色、绿色和蓝色的圆圈。它们被称为质心。简单来说，这些小东西将帮助我们将灰色方块分组。很简单，是吧？好吧。请继续跟着我。
现在，看看第二张图片。在这里，灰色方块不再是灰色的了。实际上，它们已经变成了圆圈的颜色，这表示它们属于那个簇。整个区域也被分成了三个较小的彩色区域，以显示三个簇的边界。所以，现在我们有了三个簇，每个簇都包含一些方块。
下一张图片显示了一些计算。这是算法的一部分，在这个阶段，方块可能会从一个簇移动到另一个簇。但我们如何决定呢？我现在先跳过这个问题，稍后会再回来讨论。
最后，最后一张图片显示了算法的最终结果，其中所有方块都被分成了三个簇。算法的最后一步将方块聚类，使得同一簇的成员有很多共同点，而不同组的成员差异很大。
现在，你可能会问自己为什么我们称之为“K”和“Means”？简单来说，“K”是你决定的质心的数量，“Means”（均值）是决定一个数据点应该属于哪个簇的标准。我稍后会详细解释这一点。此外，请访问此页面了解更多关于 K-Means 聚类算法的信息。
C# 中的 K-Means 聚类算法
数据点数据模型
现在我们对算法的总体目标有了一点了解，让我们尝试用 C# 来实现它。我做的第一件事是创建一个数据模型来存储我要聚类的数据。你想聚类的数据可以是任何东西。在我这里，我需要聚类一个名为“Data Point”类型的对象。这个类有两个属性：Height（身高）和 Weight（体重），它们可能对应于一个人（或事物）的两个物理属性。还有一个名为“Cluster”的属性。这个属性存储了 Data Point 所属的簇的索引。
public class DataPoint
{
public double Height { get; set; }
public double Weight { get; set; }
public int Cluster { get; set; }
public DataPoint(double height, double weight)
{
Height = height;
Weight = weight;
Cluster = 0;
}
public DataPoint()
{
}
public override string ToString()
{
return string.Format("{{{0},{1}}}", Height.ToString("f" + 1), Weight.ToString("f" + 1));
}
}
还有一个 ToString 方法，用于将数据点插入到主窗体上的 listbox 中。以下是执行此操作的事件处理程序。
private void txtWeight_KeyDown(object sender, KeyEventArgs e)
{
if (e.KeyCode==Keys.Enter)
{
if (string.IsNullOrEmpty(txtHeight.Text) || string.IsNullOrEmpty(txtWeight.Text))
{
MessageBox.Show("Please enter the values for both Height and Weight.");
return;
}
DataPoint dp = new DataPoint();
dp.Height = double.Parse(txtHeight.Text);
dp.Weight = double.Parse(txtWeight.Text);
lstRawData.Items.Add(dp.ToString());
}
}
类级别对象
我还为应用程序的主窗体声明了一些类级别的对象。
List<DataPoint> _rawDataToCluster = new List<DataPoint>();
List<DataPoint> _normalizedDataToCluster = new List<DataPoint>();
List<DataPoint> _clusters = new List<DataPoint>();
private int _numberOfClusters = 0;
我认为上面的代码足够清楚了，但我们还是来解释一下这些对象将负责什么。
· _rawDataToCluster：存储用户输入的数据。· _normalizedDataToCluster：存储 _rawDataToCluster 的归一化版本。什么是归一化？我稍后会讲。· _clusters：存储每个簇的均值。均值？那是什么？别担心。同样，我稍后会解释。但目前，我应该说，存储在这个集合中的数据决定了一个数据点是否应该在两个簇之间移动，或者保持在它已经存在的簇中。· _numberOfClusters：我们想要分组数据的簇的数量。在上面的图片中，簇的数量是三个。
InitializeRawData 方法
首先要做的就是使用用户输入的数据填充 _rawDataToCluster 集合。我应该提到，用户应该在两个文本框中输入“Height”和“Weight”属性的数据。按下 Enter 键后，数据将以以下格式添加到 listbox 中：{32.0,230.0}。
现在，是时候使用 listbox 中的数据来填充 _rawDataToCluster 集合了。当然，有很多方法可以做到这一点。我试图坚持最简单的一种。
private void InitilizeRawData()
{
if (__rawDataToCluster .Count == 0)
{
string lstRawDataItem = string.Empty;
for (int i = 0; i < lstRawData.Items.Count; i++)
{
DataPoint dp = new DataPoint();
lstRawDataItem = lstRawData.Items[i].ToString();
lstRawDataItem = lstRawDataItem.Replace("{", "");
lstRawDataItem = lstRawDataItem.Replace("}", "");
string[] data = lstRawDataItem.Split(',');
dp.Height = double.Parse(data[0]);
dp.Weight = double.Parse(data[1]);
__rawDataToCluster .Add(dp);
}
}
}
上面的方法只是遍历 listbox 中的项，使用 String 类型的 Split 方法提取每一行中的两个数据，实例化一个类型为 Data Point 的新对象，设置属性，然后将对象添加到 _rawDataToCluster 中。
NormalizeData 方法
到目前为止获得的数据还不能使用。首先，我们需要对其进行归一化。为什么？很简单。你看，我们处理的是两种不同类型的数据：Height（身高）和 Weight（体重）。它们在某种程度上是关于不同测量的。再举个例子，如果我们处理的是关于天数、年龄、客户购买次数等数据，我们就需要对数据进行归一化。我们进行归一化是为了确保一个数据（例如 Height）不会压倒另一个（例如 Weight）。同样，我们也可以跳过归一化步骤，但最佳实践是这样做。所以，这是代码。
private void NormalizeData()
{
double heightSum = 0.0;
double weightSum = 0.0;
foreach (DataPoint dataPoint in _rawDataToCluster)
{
heightSum += dataPoint.Height;
weightSum += dataPoint.Weight;
}
double heightMean = heightSum / _rawDataToCluster.Count;
double weightMean = weightSum / _rawDataToCluster.Count;
double sumHeight = 0.0;
double sumWeight = 0.0;
foreach (DataPoint dataPoint in _rawDataToCluster)
{
sumHeight += Math.Pow(dataPoint.Height - heightMean, 2);
sumWeight += Math.Pow(dataPoint.Weight - weightMean, 2);
}
double heightSD = sumHeight / _rawDataToCluster.Count;
double weightSD = sumWeight / _rawDataToCluster.Count;
foreach (DataPoint dataPoint in _rawDataToCluster)
{
_normalizedDataToCluster.Add(new DataPoint()
{
Height = (dataPoint.Height - heightMean)/heightSD,
Weight = (dataPoint.Weight - weightMean) / weightSD
}
);
}
}
有不同的方法可以归一化我们到目前为止获得的数据。这里使用的方法是高斯（也称为正态）归一化。它是如何工作的？非常简单。第一个循环和接下来的两行计算数据点Height和Weight的平均值。如何计算？只需将Height和Weight的值加起来，然后除以集合中的项数。下一步是为集合中的所有项做一些事情，即用前面计算出的平均值（heightMean，weightMean）减去Height和Weight，然后平方。下一步是将这两个值除以集合中的项数。最后，最后一个循环通过向其中添加类型为 DataPoint 的新对象来填充 _normalizedDataToCluster 集合。用于这两个属性的值是 _rawDataToCluster 集合中值的归一化版本。现在，大多数归一化值将在 -3 和 +3 之间。请随意访问此页面了解有关此归一化方法的更多信息。
ShowData 方法
既然我们已经有了归一化数据，为什么不将其显示给用户呢？好吧，下面的方法就是这样做的。
private void ShowData(List<DataPoint> data, int decimals, TextBox outPut)
{
foreach (DataPoint dp in data)
{
outPut.Text += dp.ToString() + Environment.NewLine;
}
}
此方法接受一个类型为 DataPoint 的泛型列表、小数点位数以及要打印输出的 textbox 的引用。表单上实际上有三个 textbox。一个用于显示归一化数据，一个用于显示聚类历史，另一个用于显示算法的最后结果。同样，代码足够简单：只需遍历列表中的所有成员，调用 ToString 方法，就这样。我们以 {Height,Weight} 的格式获得集合中的所有项。还记得 ToString 方法吗？
InitializeCentroids 方法
好吧，K-Means 聚类算法的核心部分在这里开始。你还记得质心吗？那些帮助我们分组灰色方块的小彩色圆圈。K-Means 聚类算法的一个特点是首先为每个数据项设置初始质心。我们如何做到这一点？最基本的方法是随机设置质心。还有其他方法，我们暂时跳过。这就是我们要做的。所以，对于我们到目前为止获得的每个 DataPoint，我们需要使用随机机制设置 Cluster 属性。
private void InitializeCentroids()
{
Random random = new Random(_numberOfClusters);
for (int i = 0; i < _numberOfClusters; ++i)
{
_normalizedDataToCluster[i].Cluster = _rawDataToCluster[i].Cluster = i;
}
for (int i = _numberOfClusters; i < _normalizedDataToCluster.Count; i++)
{
_normalizedDataToCluster[i].Cluster = _rawDataToCluster[i].Cluster = random.Next(0, _numberOfClusters);
}
}
关于这个聚类算法要记住的一点是，一个簇**必须**始终至少有一个成员（这里是 DataPoint）。这就是第一个循环的目的。第一个循环通过设置 _normalizedDataToCluster 和 _rawDataToCluster 集合中的项的 Cluster 属性，任意地将一个数据点添加到每个簇。然后，第二个循环为剩余的数据点将 Cluster 属性设置为零到用户输入的簇数量之间的随机数。为什么我们要为 _normalizedDataToCluster 和 _rawDataToCluster 集合中的项都设置 Cluster 属性？那是因为最后，我们将使用 _rawDataToCluster 来显示算法的结果。换句话说，我们使用 _normalizedDataToCluster 中的 Cluster 属性来实际进行聚类，而使用 _rawDataToCluster 中的 Cluster 属性向用户显示结果。这是我决定这样做的一个选择。如果你愿意，可以省略这一部分，而使用 _rawDataToCluster 来打印最终结果。
UpdateDataPointMeans 方法
你还记得我告诉过你，算法名称中的“Means”（均值）一词负责决定哪个簇应该包含一个数据点吗？如果你不记得了，请回过头来再读一遍。现在，这个过程有点复杂，但我会尽量用最简单的方式解释。你看，我们已经设置了数据点的质心。也就是说，我们已经将数据点分到了一些任意的簇中。现在，是时候为每个数据点找到最合适的簇了。我们如何决定呢？同样，非常简单。首先，我们需要计算一个簇中所有项的均值（针对 Height 和 Weight）。例如，如果一个簇包含三个数据点，如 {32,65}、{16,87} 和 {17,60}，那么这个簇的均值是 (32+16+17)/3 和 (65+87+60)/3。我们将这两个值存储在 _cluster 集合中。只是提醒一下，_cluster 集合是一个类型为 DataPoint 的泛型列表，在类级别声明。然而，这个集合中项的 Height 和 Weight 属性不再代表 DataPoint 的实际值，而是代表簇中所有数据点的相应属性的均值。_normalizedDataToCluster 和 _rawDataToCluster 中的 DataPoint 对象的 Cluster 属性表示包含该 DataPoint 的簇的索引。让我们用这个例子来进一步说明，让事情更简单。假设 _cluster 集合中有一个 DataPoint 对象，其属性如下。
DataPoint{21.6,70.6,1}
_rawDataToCluster 或 _normalizedDataToCluster 集合中也有三个项，其属性如下。
DataPoint{32,65,1}, DataPoint{16,87,1}, DataPoint{17,60,1}
所有这些都意味着 _rawDataToCluster 集合中的三个数据点是一个索引为 1 的簇的成员，该簇的 Height 和 Weight 属性是其成员的两个属性的均值：21.6 和 70.6。
现在，废话少说，让我们看看代码。
private bool UpdateDataPointMeans()
{
if (EmptyCluster(_normalizedDataToCluster)) return false;
var groupToComputeMeans = _normalizedDataToCluster.GroupBy(s => s.Cluster).OrderBy(s => s.Key);
int clusterIndex = 0;
double height = 0.0;
double weight = 0.0;
foreach (var item in groupToComputeMeans)
{
foreach (var value in item)
{
height += value.Height;
weight += value.Weight;
}
_clusters[clusterIndex].Height = height / item.Count();
_clusters[clusterIndex].Weight = weight / item.Count();
clusterIndex++;
height = 0.0;
weight = 0.0;
}
return true;
}
此方法利用 LINQ 根据 Cluster 属性对 _normalizedDataToCluster 进行分组。然后，它遍历每个组中的每个项，计算均值并更新簇集合。但是，首先，它确保没有任何一个簇是空的。如果即使有一个簇是空的，它就会返回 false 而不继续。这正是我之前所说的：任何时候，每个簇**必须**至少有一个成员。
EmptyCluster 方法
这是测试簇以确保每个簇至少有一个成员的方法。
private bool EmptyCluster(List<DataPoint> data)
{
var emptyCluster =
data.GroupBy(s => s.Cluster).OrderBy(s => s.Key).Select(g => new {Cluster = g.Key, Count = g.Count()});
foreach (var item in emptyCluster)
{
if (item.Count == 0)
{
return true;
}
}
return false;
}
EuclideanDistance 方法
现在到我们算法最重要的部分了。K-Means 聚类算法的思想是将相似的项放在一起，对吗？没错。但这种相似性是什么意思呢？好吧，它是项与当前簇成员均值之间的差异。如何计算这种差异？嗯，有很多方法可以做到这一点。最简单的方法是我在这里使用的欧几里得距离法。
private double ElucidanDistance(DataPoint dataPoint, DataPoint mean)
{
double _diffs = 0.0;
_diffs = Math.Pow(dataPoint.Height - mean.Height, 2);
_diffs += Math.Pow(dataPoint.Weight - mean.Weight, 2);
return Math.Sqrt(_diffs);
}
此方法相当直接。它接受两个 DataPoint 类型的参数：一个是我们要移动到更合适簇的 DataPoint，另一个是存储目标簇中项的均值的 DataPoint。欧几里得方法背后的思想也很简单。在这种情况下，我们只需要将要处理的数据点的 Height 和 Weight 减去目标簇中这两个属性的均值，然后将值平方，将它们相加，然后返回该值的平方根，这就是这两个数据点之间的欧几里得距离。有关此方法的更多信息，您可以参考此页面。现在我们已经获得了数据点与目标簇均值之间的距离，我们可以决定是否将该数据点移动到新簇。我们如何决定呢？请继续阅读。
UpdateClusterMembership 方法
要将一个数据点从一个簇移动到另一个簇，我们只需要更新其 Cluster 属性中存储的值。但是，问题是如何决定这一点。嗯，我们需要将数据点的 Height 和 Weight 属性与所有簇中这些属性的均值进行比较。然后，我们需要选择差异最小的簇，并将数据点移动到该簇。为什么？因为那个簇是最合适的，因为它的均值与数据点之间的差异最小。请记住，算法的最终目标是将相似的项分组在一起；那些值之间的差异最小的项。以下代码负责完成所有这些工作。
private bool UpdateClusterMembership()
{
bool changed = false;
double[] distances = new double[_numberOfClusters];
StringBuilder sb = new StringBuilder();
for (int i = 0; i < _normalizedDataToCluster.Count; ++i)
{
for (int k = 0; k < _numberOfClusters; ++k)
distances[k] = ElucidanDistance(_normalizedDataToCluster[i], _clusters[k]);
int newClusterId = MinIndex(distances);
if (newClusterId != _normalizedDataToCluster[i].Cluster)
{
changed = true;
_normalizedDataToCluster[i].Cluster = _rawDataToCluster[i].Cluster = newClusterId;
sb.AppendLine("Data Point >> Height: " + _rawDataToCluster[i].Height + ", Weight: " +
_rawDataToCluster[i].Weight + " moved to Cluster # " + newClusterId);
}
else
{
sb.AppendLine("No change.");
}
sb.AppendLine("------------------------------");
txtIterations.Text += sb.ToString();
}
if (changed == false)
return false;
if (EmptyCluster(_normalizedDataToCluster)) return false;
return true;
}
让我们稍微谈谈这个方法。最外层的循环遍历 _normalizedDataToCluster 集合的项。下一个内部循环计算 _normalizedDataToCluster 集合中的每个项与 _clusters 集合中存储的簇均值之间的欧几里得距离，然后将每个比较的结果存储在一个名为 distances 的数组中。之后，代码调用一个名为 MinIndex 的方法，该方法返回数组中最小值的索引。这非常简单，我很快就会给出代码。现在我们有了最小差异簇的索引，我们必须检查这个数据点是否已经在那个簇中。这就是代码的条件部分所做的。如果数据点不在最小距离簇中，我们应该将其移动到那里。如何移动？只需更新该数据点的 Cluster 属性中的值。我们将 changed 标志设置为 true ，以表明簇成员关系发生了变化。然后，我们还在 StringBuilder 对象中放入一小段 string ，以通知用户一个数据点更换了簇。如果数据点已经在最小距离簇中，我们只输出“No Change”（无变化）。很简单吧？在此方法结束时，我们检查 changed 标志不为 false，并且我们还检查没有任何一个簇是空的。如果任何一个条件不满足，该方法就会返回 false。为什么？非常简单。K-Means 聚类算法的理念是，我们应该尝试将项移动到更合适的簇，直到没有发生簇成员关系的变化，或者，如前所述，至少有一个簇是空的。
MinIndex 方法
此方法在 UpdateClusterMembership 方法中使用，它简单地接受一个数组并返回其中存储的最小值的索引。它用于找到数据点要移动到的最小差异簇。
private int MinIndex(double[] distances)
{
int _indexOfMin = 0;
double _smallDist = distances[0];
for (int k = 0; k < distances.Length; ++k)
{
if (distances[k] < _smallDist)
{
_smallDist = distances[k];
_indexOfMin = k;
}
}
return _indexOfMin;
}
Cluster 方法
在这里，我们放上了我们代码的最后一块来聚类数据。它是一个非常简单的方法，使用了我们已经讨论过的大部分代码。
public void Cluster(List<DataPoint> data, int numClusters)
{
bool _changed = true;
bool _success = true;
InitializeCentroids();
int maxIteration = data.Count * 10;
int _threshold = 0;
while (_success == true && _changed == true && _threshold < maxIteration)
{
++_threshold;
_success = UpdateDataPointMeans();
_changed = UpdateClusterMembership();
}
}
此方法接受一个类型为 DataPoint 的集合和一个期望的簇数量。它调用 InitializeCentroids 方法为数据点设置一些随机质心。最后，它在循环中调用 UpdateDataPointMeans 和 UpdateClusterMembership 方法。我使用了 while 循环。停止循环的三个条件也很重要。首先，_success 标志必须为 true；它由 UpdateDataPointMeans 设置，并且除非有一个簇为空，否则始终为 true。下一个条件是 _changed 标志必须为 true；它也由 UpdateClusterMembership 方法设置，并且除非有一个簇为空或数据点的簇成员关系没有发生变化，否则始终为 true。还为执行聚类操作的次数设置了一个阈值。这个阈值设置为需要聚类的数据点数量的十倍。
聚类并打印结果
最后一件事是使用所有这些来聚类一些数据。这是按钮的事件处理程序，该按钮调用 Cluster 方法。
private void btnCluster_Click(object sender, EventArgs e)
{
InitilizeRawData();
_numberOfClusters = int.Parse(txtNumberOfClusters.Text);
for (int i = 0; i < _numberOfClusters; i++)
{
_clusters.Add(new DataPoint(){Cluster = i});
}
Cluster(_normalizedDataToCluster, _numberOfClusters);
StringBuilder sb = new StringBuilder();
var group = _rawDataToCluster.GroupBy(s => s.Cluster).OrderBy(s => s.Key);
foreach (var g in group)
{
sb.AppendLine("Cluster # " + g.Key + ":");
foreach (var value in g)
{
sb.Append(value.ToString());
sb.AppendLine();
}
sb.AppendLine("------------------------------");
}
txtOutput.Text = sb.ToString();
}
此方法非常直接。它读取用户指定的簇数量，并将正确数量的数据点添加到 _clusters 集合中。然后，它将 _normalizedDataToCluster 集合和簇数量传递给 Cluster 方法。聚类操作完成后，它根据 Cluster 属性对 _ rawDataToCluster 集合中的项进行分组，然后打印出每个簇中的成员。
结论
就这样！在 C# 中实现了 K-Means 聚类算法。这是一种非常优美且高效的聚类算法。我试图用最简单的语言解释这个过程。希望你喜欢它。