机器学习中的K-Medoids聚类算法详解

什么是中心点？

中心点是聚类内位于最中心位置的数据点。它最小化了与该聚类内所有其他点的差异性（dissimilarity）。我们定义中心点 $Ci$ 与对象 $Pi$ 之间的差异性为：$E =

$

K-Medoids 的总成本（或目标函数）定义为：

> $c = \sum{Ci} \sum{Pi \in Ci}

$

K-Medoids 算法步骤

1. 初始化： 从数据集中随机选择 $k$ 个数据点作为初始中心点。
2. 分配点： 使用距离度量（例如曼哈顿距离或欧几里得距离），将每个数据点分配给最近的中心点。
3. 更新步骤（交换）： 对于每个中心点 $m$，尝试将其与非中心点 $o$ 进行交换：

• 重新计算这种新配置下的成本。
• 如果总成本减少，则接受该交换；否则，恢复原状。

4. 重复： 继续上述过程，直到无法进一步降低成本为止。

实例解析

让我们来看下面的例子。

!K-Medoids-clustering

如果使用上述数据点绘制图表，我们将得到下图：

!K-Medoids-clustering

步骤 1：初始化

假设随机选择的 2 个中心点为：$k=2$，令 $C1 = (4, 5)$ 且 $C2 = (8, 5)$。

步骤 2：计算成本

接下来，我们计算每个非中心点与中心点之间的差异性，并制成表格：

!K-Medoids-clustering

我们使用曼哈顿距离公式来计算中心点和非中心点之间的距离：

$$\text{Distance} =

+

$$

我们将每个点分配给差异性较小的中心点所在的聚类。

• 点 1, 2 和 5 -> 聚类 C1
• 点 0, 3, 6, 7 和 8 -> 聚类 C2

成本 = $( 3+ 4+ 4) +( 3+ 1+ 1+ 2+ 2) = 20$

步骤 3：交换并重新计算

现在，我们随机选择一个非中心点并重新计算成本。假设随机选择的点是 (8, 4)。

!K-Medoids-clustering

同样，将每个点分配给差异性较小的聚类。

• 点 1, 2 和 5 -> 聚类 C1
• 点 0, 3, 6, 7 和 8 -> 聚类 C2

新成本 = $( 3+ 4+ 4) +( 2+ 2+ 1+ 3+ 3) = 22$

交换成本 = 新成本 – 旧成本 = $22 – 20 = 2$

因为 $2 > 0$，即交换成本并未小于零，所以我们撤销这次交换。

因此，(4, 5) 和 (8, 5) 成为最终的中心点。

!K-Medoids-clustering

最终结果

最终的聚类结果如下：

• 聚类 1：(4, 5) -> 包含点 1, 2, 5
• 聚类 2：(8, 5) -> 包含点 0, 3, 6, 7, 8

> K-Medoids 算法的时间复杂度为：$O(k \times (n – k)^2)$

优点

• 算法原理简单，易于理解和实现。
• K-Medoids 可以在固定的步骤内收敛。
• 与其他划分算法相比，它对异常值不太敏感。

缺点

• 不适合用于非球形或任意形状的聚类。
• 由于中心点的初始化是随机的，多次运行的结果可能会有所不同。