使用人工智能 K-Means 聚类算法对数据进行分类
5.00/5 (3投票s)
K-Means 聚类用于数据分析的简单介绍。
“聚类的主要目的不仅仅是创建聚类，而是创建良好且有意义的聚类” – Analytics Vidhya (https://www.analyticsvidhya.com/)。
引言
最优多目标聚类是最流行、同时也是最奇特的监督机器学习问题之一，它出现在计算机科学的许多领域，例如数据和知识挖掘、数据压缩、向量量化、模式检测和分类、Voronoi 图、推荐引擎 (RE) 等。聚类分析过程本身允许我们揭示输入数据集上表现出的各种趋势和见解。
聚类分析 (CA) 过程允许我们确定特定数据之间的相似性和差异，以一种方式对数据进行分区，使得相似数据通常属于特定的组或聚类。例如，我们可以对信用卡客户的数据进行聚类分析，以根据余额和贷款金额标准，揭示应该向特定客户提供哪些特殊优惠。在这种情况下，我们所要做的就是将所有客户数据划分为多个聚类，然后向相似的客户提供相同的优惠。这通常通过对多变量数值数据进行多变量数值数据聚类分析来完成。
执行实际聚类的主要目标是将一组具有相关数值 n 维特征向量的数据项排列成多个同质组，称为“聚类”。通常，整个聚类问题可以被表述为某个目标相似度函数最小化问题。作为相似度目标函数，使用了各种代数概念。n 维欧几里得空间中向量之间的欧几里得距离是现有聚类分析技术和算法中广泛使用的一种最流行的概念。下图说明了数据聚类的示例
从上图可以看出，各种数据被划分成三个聚类，每个聚类都包含最相似的数据。
在已知基于最小化相似度目标函数的聚类算法中，K-means 算法使用最广泛。给定实数 n 维空间中的一组 t 个数据点和一个整数 k，问题是确定欧几里得空间中的 k 个点，称为中心点，并最小化每个数据点到其最近中心点的均方距离。该度量通常称为平方误差失真，此类聚类属于基于方差的聚类类别。
基于 K-means 的聚类与许多其他聚类和位置问题密切相关。其中包括欧几里得 k-中位数（或多源 Weber 问题），其目标是最小化到最近中心的距离之和；以及几何 k-中心问题，其目标是最小化从每个点到其最近中心的最大距离。
解决基于 K-means 算法的聚类问题最流行的启发式方法之一，基本上依赖于一种简单的迭代方法来查找一组聚类。K-means 算法有多种变体。具体来说，在本文中，我们将重点讨论 Lloyd 提出的算法。
此外，我们将讨论经典 K-means 算法优化的多个方面，旨在提高聚类的实际质量，并为以下算法提供高效的性能。
此外，我们将介绍各种度量标准，例如惯性或 Dunn 指数，以评估聚类过程的质量。
最后，我们将讨论 C#.NET 中优化 K-means 算法的高效实现。
背景
在本章中，我们将介绍并阐述 K-means 聚类算法，包括许多算法级别的优化，这些优化可以显著提高聚类质量，并提高聚类过程本身的性能。
聚类分析 (CA) 基础
聚类分析 (CA) 是将一组数据项排列成一定数量的组的过程，每个组包含最相似的项。这些组称为“簇”。“聚类”本身通常用于更好地理解正在分析的数据、数据压缩或异常检测。
聚类分析是数据挖掘和统计学中不可或缺的一部分，它基本上依赖于使用监督机器学习算法来执行实际聚类。这些算法通常提供各种方法来解决整个聚类问题。至少有三种流行的聚类算法，例如 K-means 或模糊 C-means 聚类，以及处理部分或不完整数据聚类问题的期望最大化 (EM) 算法等。
此外，关于如何确定特定数据的相似性并将这些数据排列成聚类，存在大量的想法和观点。一种流行的确定数据相似性的方法是测量特定数据之间的实际欧几里得距离，并根据最小距离标准将其分组到聚类中。以下方法主要用于确定可以轻松表示为 n 维欧几里得空间中向量数量的数据的相似性。这些向量中的每一个都由数量的数值特征组成 $\bar{u}=\{u_1,u_2,u_3,…,u_{n-1},u_n\}$两个向量 $\bar{u}$ 和 $\bar{v}$ 之间的实际距离可以通过以下欧几里得距离公式测量
，其中 ${D}$ - 向量 $\bar{u}$ 和 $\bar{v}$ 之间的距离， $u_i$ 和 $v_i$ - 向量 $\bar{u}$ 和 $\bar{v}$ 的第 $i$ 个分量， $n$ - 特征的数量（即欧几里得空间的维度）；
下图展示了两个数据向量欧几里得距离的计算
根据这个公式，两个向量最相似当且仅当每个分量之间的实际差异，以及因此平方距离 D 的总值最小。
为了执行多维数据聚类，我们将使用快速且鲁棒的 K-means 算法，而不是其他算法，它相对高效，为不同的或分离良好的合成数据提供最佳聚类结果。以下算法完全基于上面列出的欧几里得距离公式的距离度量。
K-means 是一种基于质心的聚类算法，能够生成聚类，每个聚类都由一个特定的质心表示。“质心”是一个中心数据向量（即点），它可能包含也可能不包含在每个新构建聚类的数据结果集中。根据聚类的主要思想，如果两个数据向量与其最近的质心相似，基于最小距离标准，则这两个向量也相似（例如，彼此之间具有最小距离）。对于每个新构建的聚类，我们基本上选择一个代表给定数据向量集的“质量中心”的向量，然后找到所有与其最近质心距离最小的点。
在我们深入讨论 K-means 聚类算法之前，让我们讨论一下使用所讨论的算法生成聚类的一些主要考虑因素
- 单个簇内的所有数据点必须彼此相似；
- 来自不同簇的特定数据点必须尽可能不同；
根据第一个考虑因素，分配给单个聚类的所有数据点必须基于簇内距离标准相似。簇内距离是单个聚类内数据点之间的距离，两个相似数据点之间的距离不得超过簇内距离。
反过来，簇间距离（即特定簇之间的距离，例如簇中心）必须远大于最大簇内距离，以提供高质量的聚类。绝对不同数据点之间的距离必须大于或等于簇间距离。簇内和簇间距离之间的差异如下图所示
以下考虑因素是最佳聚类过程的基本原则。
导入和准备数据集
在这里，我们将深入讨论我们即将使用 K-means 算法聚类的合成数据的性质，以及如何使用 Python 的 Sklearn 库生成合成输入数据集合。
首先，让我们在实际聚类之前看一下合成数据。“合成”一词基本上是指满足特定需求或某些条件的数据，而这些需求或条件无法在原始真实数据上揭示。一个数据集，其中所有项目都排列成几个组，就是上述合成数据的一个例子。
正如我们已经讨论过的，K-means 算法可以用于聚类多维数据，其中每个项目由 n 维欧几里得空间中的一个向量表示，其分量是一组数值特征。此外，集合中的每个向量都与其组、类别或类别的特定标签相关联
从上图可以看出，数据集中的每个项都是一个 5 维特征向量及其所属的特定类别标签的对。每个向量的数值特征基本上表示特定的浮点参数值。例如，这可能是信用卡余额、金融领域的贷款金额、生物学中植物的各种特征等等。每个特定项的标签是一个数值或字符串值，用于标识该项所属的组。接下来，我们将为每个项组使用整数标签 [0;N]。
为了生成以下数据集，我们将实现一个 Python 脚本，如下所示
import numpy as np
import pandas as pd
from sklearn.datasets.samples_generator import make_blobs
X, labels = make_blobs(n_samples=1000, n_features=5, centers=6, cluster_std=0.60, random_state=0)
df = pd.DataFrame({'X': X[:,0], 'Y': X[:,1], 'Z': X[:,2], 'C': X[:,3], 'T': X[:,4], 'Label': labels}, columns=['X','Y','Z','C','T','Label'])
df.to_csv(r'd:\dataset.csv', index = None, header=None)
在此代码中，我们将从 sklearn.datasets.samples_generator 模块导入 make_blobs 函数，并使用它生成一组数据项及其标签。以下函数接受多个参数，例如要生成的项目数 n_samples = 600、每个项目向量的特征数 n_features=5、聚类中心数 centers = 6、聚类的标准差 cluster_std = 0.60 和随机数生成器状态 random_state=0。以下函数返回一个由生成向量或其标签组成的数组元组。
生成数据集后，现在将其导出为 .csv 文件格式。为此，我们将使用 Python 的 Pandas 数据框。Pandas 数据框通常使用通用模板实例化，将两个参数传递给数据框构造函数 df = pd.DataFrame(…)。第一个参数是包含先前生成的数据集中每列数据的列表：{'X': X[:,0], 'Y': X[:,1], 'Z': X[:,2], 'C': X[:,3], 'T': X[:,4], 'Label': labels}，第二个参数是列标签名称列表：columns=['X','Y','Z','C','T','Label']。创建数据框后，现在可以将数据导出为 .csv 文件。这通常通过调用 df.to_csv(r'dataset.csv', index = None, header=None) 方法来完成。
最后，以下数据集可以由 C#.NET 中的代码使用，以执行实际的聚类。
K-Means 聚类算法
初始化
K-means 算法的初始化阶段相当直观简单。在初始化阶段，我们通常在执行实际聚类之前，在欧几里得空间中选择 k 个随机点作为一组初始质心。
然而，以下方法存在许多缺点，导致出现次优聚类问题。具体来说，随机选择的质心之间的距离在大多数情况下不是最优的（例如，特定质心之间的距离非常小）。以下通常会导致两种主要结果：聚类质量差或性能显著下降。
显然，为了执行最优聚类，我们需要一种略有不同的方法来寻找一组最优初始质心，如下所述。
K-Means++ 初始化
作为次优聚类问题的解决方案，我们将阐述 k-means++ 初始化算法，该算法能够显著提高经典 k-means 过程提供的聚类质量，并提高其性能并降低计算复杂性。通常，我们使用 k-means++ 替代方案来实现两个主要目标
- 在已知缺陷和局限性方面，改进经典 K-means 算法提供的聚类收敛性和质量；
- 通过优化迭代，为 NP-hard K-means 聚类过程提供更好的性能，从而将其计算复杂度降低到仅 $p = O(log(k))$，其中 $k$ 是初始质心的数量，而无需重新设计整个算法本身；
整个初始化过程基本上依赖于执行几个步骤，例如欧几里得、Lloyd's 或原生 k-means++。欧几里得步骤是一个初步步骤，在此期间我们执行搜索以找到第一和第二初始质心对，基于最大欧几里得距离大小。反过来，Lloyd's 步骤对于 k-means++ 和 k-means 聚类过程本身都非常常见。在此步骤中，我们实际上预先构建了一组初始聚类，将每个点映射到特定的现有质心，从而构建一个初始聚类。这通常是为了找到具有最佳距离的点和质心。k-means++ 是最后一步，在此期间我们调查点与每个现有质心之间的距离，基于最大距离测量选择新的最佳质心。
根据 k-means++ 过程，我们不再需要随机地在欧几里得空间中播种任意点 $\forall p\in \mathbb{R}^{n}$，并在实际聚类之前将它们用作初始质心集。尽管如此，初始质心的数量 $k$ 仍然必须指定。
在 K-means++ 初始化阶段，我们将在所有现有数据点 $\forall {t_k}\in {T}$ 中随机选择第一个质心，然后使用一种略有不同的算法来最优地选择其他质心。让我们回顾一下，在这种情况下，使用 K-means++ 过程选择的每个质心都是现有数据点集 $T$ 中的一个点，而不是 n 维欧几里得空间中的任意点。
K-means++ 算法的主要思想是，质心计算的整个过程基本上依赖于所选质心之间的最优距离度量。强烈建议质心之间的实际距离应尽可能大。
在执行初始化时，我们始终都在寻找具有最佳距离的质心。随机选择第一个质心 ${c_1}$ 后，我们可以计算一个点作为第二个质心 ${c_2}$，该点与质心 ${c_1}$ 之间的距离最大，这是第一个最大距离。然后，我们计算一个特定点及其最近的质心 ${c_1}$ 或 ${c_2}$，使得该点与其中一个质心之间的距离是第二个最大距离。以下点被视为第三个质心 ${c_3}$。为了找到第四个质心 ${c_4}$，我们做同样的事情，计算一个点与质心 ${c_1}$、${c_2}$ 或 ${c_3}$ 之间的第三个最大距离，依此类推。
K-means++ 算法可以表述如下
- 给定一组数据点 $T=\{t_1,t_2,t_3,...,t_{n-1},t_n\}$ 和初始聚类的数量 $k$；
- 随机选择一个点 $\forall{t}$ 作为第一个质心 $c_1 = RND\{\overline{T}\}$；从输入点集中。在这种情况下，我们可以不受任何限制地选取集合中的任何现有定点 $\forall{t}$；
- 计算集合中每个点到第一个质心 $c_1$ 的距离 $d(t_k)$，并选择距离最大的点 $t_j$ 作为下一个质心 $c_2 = \forall{t_j}|max_j\{d(t_j)\}$；
- 计算集合中每个点到其最近质心（例如 $C = \{c_1,c_2,c_3,...,_c{n-1},c_n\}$）的距离 $d(t_k)$；
- 选择距离最大的点 $t_s$ 作为下一个质心 $c_m = \forall{t_s}|max_s\{d(t_s)\}$，并将其添加到质心集合 ($C\leftarrow c_m$)；
- 继续步骤 3 和 4，直到选择了所需数量的 $k$ 个质心；
根据 K-means++ 过程，我们必须确保在计算其他质心之前至少已选择两个质心。在此阶段，所生成的质心集必须用随机选择的单个点作为第一个质心 $c_1$ 进行初始化。第二个质心 $c_2$ 是通过计算每个点到第一个质心 $c_1$ 的距离 $d(t_k)$，并选择与该质心距离最大的点 $\forall{t_j}$ 来选择的。这通常是为了在执行实际聚类之前改善簇间距离。之后，第二个质心 $c_2$ 成功选择后，我们将该点 $c_m = t_j$ 添加到质心集 $C \leftarrow c_m$。以下这个微不足道的操作基本上是指所讨论算法的欧几里得步骤。图 5 说明了选择第一个和第二个初始质心 $c_1$ 和 $c_2$ 的过程，
由于质心 $c_1$ 和 $c_2$ 都已被选中，现在，我们可以计算其余的质心（例如 $c_3,c_4,c_5,...$）。为此，对于每个点，我们必须迭代计算到集合 $C$ 中所有现有质心的距离 $d(t_k)$，并将当前点 $t_k$ 与距离最小的质心 $c_n$ 关联起来，直到每个点都属于一个特定的质心。这一步对于 k-means++ 和经典 k-means 算法都非常常见，称为“Lloyd 步”。然后，根据原生 k-means++ 算法，选择与最近质心 $c_n$ 距离最大的点 $t_s$ 作为下一个质心 $c_m\leftarrow t_s$，并添加到质心集合 $C$ 中。通常，我们重复以下计算，直到找到所需数量的质心。在下方的图 6 中显示了在集合中找到其余质心的整个过程。
正如您可能已经注意到的，我们通常会继续 K-means++ 初始化过程，直到我们最终选定了一组质心，并在算法的 Lloyd 步骤中构建了许多初始簇。此外，这些初始簇的数量被添加到现有簇的输出集中，并且通过重新计算每个正在处理的特定现有簇的质量中心大小（即“质心”）来生成新的簇。这反过来又允许在算法层面提高 K-means 聚类的性能。以下主题将在本文的后续章节中详细讨论。
在前面的段落中，我们已经讨论了 K-means++ 初始化过程主要基于寻找具有最大最优距离的质心。然而，正如我们可能认为的那样，寻找一组最优初始质心的算法可能有所不同。具体来说，我们可以计算点对之间的距离，然后选择距离最大的点。显然，以下算法是失败的，因为两个或多个任意点作为质心之间的距离可能不是最优的。例如，我们找到了一组三个质心 $c_1$、$c_2$ 和 $c_3$。质心对 $c_1$ 和 $c_2$ 之间以及 $c_2$ 和 $c_3$ 之间的距离是最优的，但 $c_1$ 和 $c_3$ 之间的距离不是。以下原因证明我们仍然需要遵循 K-means++ 初始化过程。
事实上，K-means++ 初始化过程是解决最优初始质心选择的唯一可能算法。以下过程完全基于选择质心之间具有优化距离的技术，从而确保 K-means 算法本身将在聚类过程的最初几个步骤中成功收敛，显著减少执行的操作数量。此外，K-means++ 算法有多种变体，例如基于距离或基于概率的。然而，基于概率分布的 K-means++ 过程，类似于通用 K-means 初始化，有时由于一些随机化问题，往往会提供糟糕的初始质心选择结果。
最后，在下面的图表中，我们将比较使用 K-means++ 过程或通用 K-means 随机初始化选择初始质心的结果。
执行 K-Means 聚类
在详细讨论了初始化阶段之后，现在让我们花一点时间简要地了解一下 K-means 聚类过程。根据 K-means 算法的主要思想，我们需要将距离最小的点排列成多个称为“簇”的组，并且由于已经生成了新构建的簇，因此需要根据在接下来段落中讨论的查找“质量中心”大小的过程，为每个簇重新计算一个质心。
简要介绍之后，我们来阐述一下经典的 K-means 算法，它非常简单
- 给定一组 $k$ 个质心 $C=\{c_1,c_2,c_3,...,c_{k-1},c_k\}$ 和一组数据点 $T=\{t_1,t_2,t_3,...,t_{n-1},t_n\}$；
- 对于每个质心 $\forall{c_i}$，找到一组与当前质心 $c_i$ 距离最近的点 $\hat{T}$，并将这些点与该质心关联，从而创建一个新构建的簇；
- 根据“质量中心”大小重新计算每个新构建的簇的质心，并将每个新计算的质心添加到质心集合 $C$ 中；
- 检查每个已存在簇的质心是否未改变，并且所选点是否不在同一簇内（例如，我们没有生成包含先前已构建簇中已出现重复点的相似簇）；
- 如果不是，则继续执行步骤 1、2 和 3，否则终止 K-means 聚类过程；
由于我们已经给定了一组初始质心 $C$，对于每个特定的质心 $c_i$，我们可以计算一个包含 $T$ 中数据点的簇，其中到当前质心 $c_i$ 的距离最小。为此，对于每个特定点 $t_k \in T$，我们必须计算到 $C$ 中每个质心 $c_i \in C$ 的距离，确定到当前点 $t_k$ 距离最小的质心 $c_j$，并将点子集 $\hat{T}$ 分配给一个以质心 $c_j$ 为中心的新构建簇。以下操作基本上是指前面讨论的算法的 Lloyd 步骤。
在我们计算出新簇之后，是时候重新计算质心，以便能够在聚类过程的下一阶段生成新簇了。这通常通过使用“质量中心”方程来完成，该方程产生以下计算。为了找到质量中心，对于 $\hat{T}$ 中的所有点，我们必须计算 n 维欧几里得空间 $t_k\in\mathbb{R}^n$ 中每个坐标的平均值/均值。这里有一个方程说明了这种计算
其中 $v_i$ 是第 $i$ 个簇的新质心， $c_i$ - 第 $i$ 个簇中的点数， $x_j$ - 属于第 $i$ 个簇的点 $\forall x_j \in \hat{T}$；
执行这些计算的结果是，我们得到一个点，代表一个新的聚类质心。我们通常会继续执行以下计算，直到为每个已存在的聚类找到一个新的质心。
此外，我们将使用这些质心来寻找新的聚类，继续执行 K-means 算法的 Lloyd 步骤，该步骤已在前面的段落中讨论过。
最后，我们将讨论聚类过程的另一个方面，即 K-means 算法的停止准则。至少有三个准则可以用来确定 K-means 聚类过程何时必须终止
- 重新计算的新质心不变，且与已存在簇的质心相等；
- 新簇由已在先前构建的簇中出现过的相同数据点组成；
- 迭代次数已达到上限；
在这些条件之一满足时，我们可以终止 K-means 聚类过程，认为该过程已成功收敛，并且我们最终得到了所需数量的 $k$ 个簇，每个簇都包含最相似的数据点。
评估 K-Means 聚类算法
有许多评估指标，例如惯性大小或 Dunn 指数，可以让我们衡量聚类质量。通过评估惯性，我们实际上计算所有点到每个簇质心的距离之和，然后将这些和相加。实际上，通过计算惯性，我们评估簇内距离之和。最后，我们认为惯性值越小，聚类质量越高。以下公式说明了惯性指标的计算
，其中 $I$ – 惯性值， $k$ – 簇的数量， $c_i$ – 第 $i$ 个簇的质心， $x_j$ - 第 $i$ 个簇中的第 $j$ 个点。
此外，惯性值可用于确定初始聚类数量，以执行最优聚类。在这种情况下，我们顺序增加初始聚类数量 $k$，然后计算惯性，直到惯性值不再变化并保持恒定。之后，取惯性值未改变的初始聚类数量 $k$。
Dunn 指数是另一种可以有效评估聚类质量的指标。该指标基本上表示簇间最小距离与簇内最大距离之比。与惯性值不同，Dunn 指数的大小很大程度上取决于簇之间的距离。在大多数情况下，为了提供高质量的聚类，我们希望最大化 Dunn 指数的值。下面的公式说明了 Dunn 指数的计算
从上面的公式可以看出，当且仅当最小簇间距离最高时，才能获得 Dunn 指数的最大值。同样，当最大簇内距离最小化时，我们也会得到 Dunn 指数的相同最大值。而这正是聚类本身最理想的情况，因为我们构建了一组最合适的簇，每个簇都包含最相似的项，同时来自不同簇的特定项之间的差异非常大。
使用代码
在这里，我们将讨论如何实现一些函数来执行 K-means 聚类。我实现的第一个函数是 LoadDataFromFile(...) 函数，它从 .csv 文件加载多维聚类数据集。
static List<tuple<list<double>, string>> LoadDataFromFile(string filename)
{
// Instantiate a list of items
List<tuple<list<double>, string>> Items =
new List<tuple<list<double>, string>>();
// Open .csv-file for reading
using (System.IO.StreamReader file =
new System.IO.StreamReader(filename))
{
string buf = "\0";
// Read .csv-file line-by-line
while ((buf = file.ReadLine()) != null)
{
List<double> features = new List<double>();
// Split each line into a list of values
foreach (string param in buf.Split(',').ToArray())
// For each value perform a check if it's a floating-point value
// using regular expressions parser
if (Regex.Match(param, @"[.]", RegexOptions.IgnoreCase).Success)
// If so, add the current value to the list of item's features
features.Add(Double.Parse(param, CultureInfo.InvariantCulture));
// Add each pair of a vector of features and its label to the list of items
Items.Add(new Tuple<list<double>, string>(features,
buf.Split(',').ElementAt(buf.Split(',').Length - 1)));
}
// Close the file
file.Close();
}
// Return the list of items
return Items;
}
</list<double></double></double></tuple<list<double></tuple<list<double></tuple<list<double>
上面列出的代码打开一个 .csv 文件并逐行读取文件，迭代地将其拆分为一个值列表。对于每个值，它会检查是否为浮点值。如果是，则将该值附加到特征列表，构建一个多维向量，然后将其及其标签（例如，当前行中最后一个逗号分隔的值）添加到项目列表中。执行结束时，该函数返回一个由特征向量及其标签组成的项元组列表。
EuclDist(...) - 我之前实现的另一个函数。以下函数执行多变量欧几里得距离值的计算，并接受两个主要参数，分别是特征的第一个和第二个向量，用于计算这两个向量之间的距离（即“相似度”）
static double EuclDist(List<double><double> params1,
List<double><double> params2, bool squared = false)
{
double distance = .0f;
// For each dimension, compute the squared difference
// between two features and accumulate the result in
// the distance variable
for (int Index = 0; Index < params1.Count(); Index++)
distance += Math.Pow((params1[Index] - params2[Index]), 2);
// Return a squared or regular distance value
return !squared ? Math.Sqrt(distance) : distance;
}
</double></double>
此函数有两种专门用途，分别用于常规或平方欧几里得距离计算。此函数执行的结果是获得两个 n 维特征向量之间欧几里得距离的浮点值。此函数主要由 Euclidean_Step(...) 和 Lloyd_Step(...) 函数使用，以计算特定的距离值。
static int Euclidean_Step(List<tuple<list<double>,
string>> items, int centroid)
{
List<tuple<int, double="">> dists = new List<tuple<int, double="">>();
// For each item compute the distance two an already existing centroid
for (int Index = 0; Index < items.Count(); Index++)
// Add each distance to the list of distances
dists.Add(new Tuple<int, double="">(Index,
EuclDist(items[centroid].Item1, items[Index].Item1, true)));
// Find an item with the maxima distance to the centroid specified
return dists.Find(obj => obj.Item2 ==
dists.Max(dist => dist.Item2)).Item1;
}
</int,></tuple<int,></tuple<int,></tuple<list<double>
上面列出的函数接受两个主要参数：项目列表以及选作第一个质心的项目的索引。
Lloyd_Step(...) 是通过调用它来执行实际聚类的主要函数。该函数由 k-means++ 和 k-means 例程都使用，根据与质心列表中每个质心的最近距离来划分数据集。这是 Lloyd_Step(...) 函数的实现
static List<Tuple<int, List<int>>> Lloyd_Step(
List<Tuple<List<double>, string>> items,
List<int> centroids, List<List<double>> c_mass = null)<tuple<int, list=""><tuple<list<double><int><list<double>
{
List<tuple<int, list="">>> clusters =
new List<tuple<int, list="">>>();
// Pre-build a set of new clusters based on the centroids index values
if (centroids != null)
{
for (int Index = 0; Index < centroids.Count(); Index++)
clusters.Add(new Tuple<int, list="">>(
centroids[Index], new List<int>()));
}
else
{
for (int Index = 0; Index < c_mass.Count(); Index++)
clusters.Add(new Tuple<int, list="">>(Index, new List<int>()));
}
for (int Index = 0; Index < items.Count(); Index++)
{
double dist_min = .0f; int cluster = -1;
if (centroids != null)
{
// For each item compute the distance to each centroid
// finding an item with the smallest distance to a current centroid
for (int cnt = 0; cnt < centroids.Count(); cnt++)
{
double distance = EuclDist(items[Index].Item1,
items[centroids[cnt]].Item1, true);
if ((distance <= dist_min) || (cluster == -1))
{
dist_min = distance; cluster = cnt;
}
}
// Assign the following item to a cluster with centroid
// having the smallest distance
var cluster_target = clusters.Find(
obj => obj.Item1 == centroids[cluster]);
if (cluster_target != null)
cluster_target.Item2.Add(Index);
}
else
{
for (int cnt = 0; cnt < c_mass.Count(); cnt++)
{
// For each item compute the distance to each centroid
// finding an item with the smallest distance to a current centroid
double distance = EuclDist(items[Index].Item1, c_mass[cnt], true);
if ((distance <= dist_min) || (cluster == -1))
{
dist_min = distance; cluster = cnt;
}
}
// Assign the following item to a cluster with centroid
// having the smallest distance
var cluster_target = clusters.Find(
obj => obj.Item1 == cluster);
if (cluster_target != null)
cluster_target.Item2.Add(Index);
}
}
// Return a list of clusters
return clusters;
}
</int></int,></int></int,></tuple<int,></tuple<int,></list<double></int></tuple<list<double></tuple<int,>
上面列出的函数接受三个参数：输入项目列表、质心索引列表或表示新聚类中心的点列表。对于每个项目，它计算到列表中每个质心或点的欧几里得距离，执行搜索以找到距离最小的质心。然后将该项目分配给具有最小距离的质心的聚类。该函数实际上执行整个数据集分区。最后，该函数返回一个元组列表，每个元组由一个质心索引和一个项目索引列表组成。
要执行 k-means++ 初始化，我们将实现以下函数，该函数基本上依赖于使用 Euclidean_Step(...) 和 Lloyd_Step(...) 函数。
static Tuple<List<int>, List<Tuple<int, List<int>>>> KmeansPlusPlus(
List<Tuple<List<double>, string>> items, int k)
{
// Initialize a list of centroids with a single centroid
// randomly selected
List<int> centroids = new List<int>() {
new Random().Next(items.Count())
};
if (centroids.Count() == 1)
// Compute the second centroid by invoking the Euclidean_Step(...)
// function and append it to the list of centroids
centroids.Add(Euclidean_Step(items, centroids[0]));
List<Tuple<int, List<int>>> targets = null;
// Compute the other initial centroids
for (int count = k - 2; count >= 0; count--)
{
// Perform a Lloyd's step to obtain a list of initial clusters
List<Tuple<int, List<int>>> clusters =
Lloyd_Step(items, centroids);
double dist_max = .0f; int cmax_index = -1, dmax_index = -1;
// For each cluster compute an item with the largest distance
// to its centroid
for (int Index = 0; Index < clusters.Count(); Index++)
{
int centroid = clusters[Index].Item1;
for (int pt = 0; pt < clusters[Index].Item2.Count(); pt++)
{
double distance = EuclDist(items[centroid].Item1,
items[clusters[Index].Item2[pt]].Item1);
if ((distance > dist_max) ||
(cmax_index == -1) || (dmax_index == -1))
{
dist_max = distance;
cmax_index = Index; dmax_index = pt;
}
}
}
if (count > 0)
// Add the following item index to the list of centroids
centroids.Add(clusters[cmax_index].Item2[dmax_index]);
targets = (clusters.Count() > 0) && (count == 0) ? clusters : null;
}
// Return a tuple of a list of centroids and a list of pre-built clusters
return new Tuple<List<int>, List<Tuple<int, List<int>>>>(centroids, targets);
}
为了执行实际的 K-means 聚类，我们将实现以下函数
static List<Tuple<int, List<int>>> KMeans(
List<Tuple<List<double>, string>> Items, int k)
{
// Find k - initial centroids using k-means++ procedure
Tuple<List<int>, List<Tuple<int,
List<int>>>> result = KmeansPlusPlus(Items, k);
// Instantiate the list of target clusters
List<Tuple<int, List<int>>> clusters_target =
new List<Tuple<int, List<int>>>();
List<int> centroids = result.Item1;
List<Tuple<int, List<int>>> clusters = result.Item2;
while (clusters.Count() > 1)
{
// Re-compute the centroids of the pre-built clusters
List<List<double>> centroids_new =
RecomputeCentroids(clusters, Items);
// Perform a Lloyd step to partition the dataset
List<Tuple<int, List<int>>> clusters_new =
Lloyd_Step(Items, null, centroids_new);
// Perform a check if we're not producing the same clusters
// and the k-means procedure has not converged.
// If not, proceed with the next clustering phase
for (int clu = 0; clu < clusters.Count(); clu++)
{
if ((Compare(clusters[clu].Item2, clusters_new[clu].Item2)))
{
clusters_target.Add(clusters[clu]);
clusters.RemoveAt(clu); clusters_new.RemoveAt(clu); clu--;
}
}
if (clusters_new.Count() > 1)
clusters = clusters_new;
}
return clusters_target;
}
上面列出的函数执行实际的 K-means 聚类。首先，它调用 KmeansPlusPlus(...) 函数以获取初始质心和预构建聚类的列表。之后，它执行一个简单的迭代，在此期间重新计算已存在聚类的质心。然后，这些新质心被 Lloyd_Step(...) 函数用于将整个数据集划分为一组新聚类。然后，它执行一个检查，以查看 K-means 过程是否已收敛，并且我们没有生成相同的聚类。如果不是，它会继续执行 K-means 聚类过程的下一次迭代。否则，该函数返回一个新构建聚类的列表。为了重新计算新质心，我实现了以下函数
static List<List<double>> RecomputeCentroids(
List<Tuple<int, List<int>>> clusters,
List<Tuple<List<double>, string>> Items)
{
List<List<double>> centroids_new =
new List<List<double>>();
// For each cluster re-compute the new centroids
for (int clu = 0; clu < clusters.Count(); clu++)
{
List<int> c_items = clusters[clu].Item2;
List<double> centroid = new List<double>();
// For a list of items, compute the average of each coordinate
for (int i = 0; i < Items[c_items[0]].Item1.Count(); i++)
{
if (Items[c_items[0]].Item1.Count() > 0)
{
double avg = .0f;
for (int Index = 0; Index < c_items.Count(); Index++)
avg += Items[c_items[Index]].Item1[i] / c_items.Count();
centroid.Add(avg);
}
}
// Add a new centroid to the list of centroids
centroids_new.Add(centroid);
}
// Return a list of new centroids
return centroids_new;
}
为了获得新的质心，我们通常计算单个簇内每个项目的每个坐标的平均值（即“质量中心”），以获得一个点，该点是特定簇的质心。
此外，还有另一个函数用于检查旧簇和新簇是否不相交。具体来说，如果新构建的簇未包含在旧簇中。
static bool Compare(List<int> list1, List<int> list2)
{
return list2.Intersect(list1).Count() == list2.Count();
}
最后，让我们讨论一下使用上面介绍的函数执行实际 K-means 聚类的主要代码
static void Main(string[] args)
{
Console.WriteLine("K-Means Clustering Algorithm v.1.0 by Arthur V. Ratz @ CodeProject.Com");
Console.WriteLine("======================================================================");
string filename = "\0";
Console.Write("Enter a filename: ");
filename = Console.ReadLine();
int k = 0;
Console.Write("Enter a number of clusters: ");
k = Int32.Parse(Console.ReadLine()); Console.WriteLine();
List<Tuple<List<double>, string>> Items =
LoadDataFromFile(filename);
List<Tuple<int, List<int>>> clusters_target =
KMeans(Items, k);
for (int clu = 0; clu < clusters_target.Count(); clu++)
{
Console.WriteLine("Cluster = {0}", clu + 1);
for (int Index = 0; Index < clusters_target[clu].Item2.Count(); Index++)
{
for (int Item = 0; Item < Items[clusters_target[clu].Item2[Index]].Item1.Count(); Item++)
Console.Write("{0} ", Items[clusters_target[clu].Item2[Index]].Item1[Item]);
Console.WriteLine("{0}", Items[clusters_target[clu].Item2[Index]].Item2);
}
Console.WriteLine("\n");
}
Console.ReadKey();
}
以下代码通过调用 LoadDataFromFile(...) 函数从 .csv 文件加载数据集，然后执行 KMeans(...) 函数以执行实际的聚类。最后，它输出聚类结果。
关注点
正如我们已经讨论过的，通过使用 K-means++ 初始化过程，可以显著优化整个 K-means 聚类过程。在这种情况下，使用 K-means++ 初始化在聚类过程的质量和性能方面都具有优势，能够将经典 NP-hard K-means 算法的整体计算复杂度降低到仅 $p = O(log(k))$，其中 $k$ 是结果集中的簇数。除了最优初始质心集之外，K-means++ 初始化还可以用于生成一组初始簇，K-means 聚类过程将从这些簇开始。此外，使用 K-means++ 初始化可确保 K-means 聚类过程将在最少的迭代次数下完成并成功收敛，从而提供最合适的实际聚类结果。具体来说，每个簇将包含最相似的数据点，尤其是在执行排他性聚类操作时，在此期间，每个点都被分配到一个特定的簇，并且不能同时包含在多个簇中。
此外，执行实际 K-means 聚类的顺序代码片段的性能可以很容易地通过使用各种现有的高性能计算 (HPC) 库和框架转换为并行，从而进一步提高聚类过程本身的性能。
历史
- 2020 年 1 月 11 日 - 本文第一版发布