k-中心聚类算法（k-medoids）算法是一种分区聚类方法，用于将数据集划分为 k 个簇，其中 k 是由用户指定的簇的数量。

与K-means算法不同，K-medoids算法选择实际的数据点作为簇的中心（称为medoids），而不是计算簇内数据点的均值。

这样，K-medoids算法对异常值更加鲁棒，因为它不会受到极端值的影响。

K-medoids算法的主要步骤如下：

1. 初始化：随机选择 k 个数据点作为初始的 medoids。

2. 分配：将每个数据点分配给最近的 medoids，形成 k 个簇。

3. 更新：对于每个簇，计算所有 非medoids 点与 当前medoids 交换后的总成本变化。如果更换medoids能减少总成本，则进行更换。

4. 重复步骤2和3，直到没有更好的medoids可选或达到最大迭代次数。

涉及到的公式：

目标函数（准则函数）

假设我们有 n 个数据点和 k 个簇，目标是最小化以下函数：

$$\sum _{i=1}^k\sum _{j\in C_i}d(o_j,m_i)$$

这里：

• $o_j$ 表示数据集中的任意一个数据点。
• $m_i$ 是簇 $C_i$ 的 medoids。
• $C_i$ 是由medoids $m_i$ 代表的所有数据点组成的簇。
• $d(o_j,m_i)$ 是数据点 $o_j$ 和medoids $m_i$ 之间的距离。

距离度量

最常见的距离度量是欧几里得距离，定义为：

$$d(o_j,m_i)=\sqrt{\sum _{l=1}^p(o_{jl}-m_{il}{)}^2}$$

这里：

• $p$ 是数据点的维度。
• $o_{jl}$ 和 $m_{il}$ 分别是数据点 $o_j$ 和medoids $m_i$ 在第 $l$ 维上的值。

解释每个字符：

• $\sum$：求和符号，表示对一系列数值进行累加。
• $i$：簇的索引。
• $j$：数据点的索引。
• $o_j$：数据点 $j$。
• $m_i$：簇 $i$ 的medoids。
• $C_i$：簇 $i$ 中的所有数据点集合。
• $d$：距离函数。
• $p$：数据点的维度。
• $l$：维度的索引。
• $o_{jl}$：数据点 $j$ 在第 $l$ 维的值。
• $m_{il}$：medoids $m_i$ 在第 $l$ 维的值。

K-medoids算法的目标是通过上述公式最小化簇内的总距离，从而获得更紧凑、更一致的簇。