极客笔记机器学习 K-Medoids聚类算法及解决示例
K-Medoids是一种使用聚类的分区方法的无监督聚类算法。它是K-Means聚类算法的改进版本，专门用于处理异常数据。它需要使用无标签数据进行工作。
在本文中，让我们用一个例子来了解K-Medoids算法。
K-Medoids算法
在K-Medoids算法中，每个数据点称为一个中心点。中心点作为聚类的中心。中心点是一个点，使得它到同一聚类中所有其他点的距离之和最小。可以使用任何适合的度量标准，如欧氏距离或曼哈顿距离来计算距离。
算法应用后，完整的数据分为K个聚类。
K-Medoids有三种类型-PAM、CLARA和CLARANS。PAM是最流行的方法。它有一个缺点就是它需要很长时间。
K-Medoid的应用方式是：
- 一个点只能属于一个聚类
-
每个聚类至少有一个点
让我们通过一个例子来看K-Medoids的工作过程。
工作过程
首先，我们有K个聚类和D个无标签的数据。
- 首先，我们从数据集中选择K个点，并将它们分配给K个聚类。这些K个点作为初始中心点。每个对象被分配到一个聚类中。
-
接下来，计算初始中心点（点）与其他点（非中心点）之间的距离，使用欧氏距离或曼哈顿距离等距离度量标准。
-
非中心点被分配到与其到中心点距离最小的聚类中。
-
现在计算总成本，即在一个聚类内从其他点到中心点的距离之和。
-
接下来，选择一个随机的新的非中心对象s，并与初始中心对象r交换，并重新计算成本。
-
如果成本小于costr，则交换变为永久交换。
-
最后，重复步骤2到6，直到成本没有变化。
示例
让我们考虑以下一组数据。我们取k=2，距离公式为
\mathrm{D=\mid x_{2}-x_{1}\mid+\mid y_{2}-y_{1}\mid}
| Sl. no | x | y |
|---|---|---|
| 1 | 9 | 6 |
| 2 | 10 | 4 |
| 3 | 4 | 4 |
| 4 | 5 | 8 |
| 5 | 3 | 8 |
| 6 | 2 | 5 |
| 7 | 8 | 5 |
| 8 | 4 | 6 |
| 9 | 8 | 4 |
| 10 | 9 | 3 |
数据看起来类似于绘图中的下图。
对于 k = 2，我们选取了两个随机点 P1(8,4) 和 P2(4,6) 并计算与其他点的距离。
| Sl. no | x | y | Dist from P1 (8,4) | Dist from P2 (4,6) |
|---|---|---|---|---|
| 1 | 9 | 6 | 3 | 5 |
| 2 | 10 | 4 | 2 | 8 |
| 3 | 4 | 4 | 4 | 2 |
| 4 | 5 | 8 | 7 | 3 |
| 5 | 3 | 8 | 9 | 3 |
| 6 | 2 | 5 | 7 | 3 |
| 7 | 8 | 5 | 1 | 5 |
| 8 | 4 | 6 | - | - |
| 9 | 8 | 4 | - | - |
| 10 | 9 | 3 | 2 | 8 |
1,2,7,10 – 分配给P1(8,4)
3,4,5,6 – 分配给P2(4,6)
总花费 C1 = (3+2+1+2) +(2+3+3+3) = 19
现在让我们随机选择任意其他两个点作为中点 P1(8,5) 和 P2(4,6)，并计算距离。
| Sl. no | x | y | Dist from P1(8,5) | Dist from P2(4,6) |
|---|---|---|---|---|
| 1 | 9 | 6 | 2 | 5 |
| 2 | 10 | 4 | 3 | 8 |
| 3 | 4 | 4 | 5 | 2 |
| 4 | 5 | 8 | 6 | 3 |
| 5 | 3 | 8 | 6 | 3 |
| 6 | 2 | 5 | 6 | 3 |
| 7 | 8 | 5 | - | - |
| 8 | 4 | 6 | - | - |
| 9 | 8 | 4 | 1 | - |
| 10 | 9 | 3 | 3 | 8 |
新成本参与C_{2}=[2+3+1+3]+[2+3+3+3]=20
交换所涉及的总成本C=C_{2}-C_{1}=20-19=1
由于交换所涉及的总成本大于0，我们将撤销交换。
点P1（8,4）和P2（4,6）被视为最终中心点，并且只使用这些点形成2个簇。
代码实现
import numpy as np
from sklearn_extra.cluster import KMedoids
data = {'x' : [9,10,4,5,3,2,8,4,8,9],
'y' : [6,4,4,8,8,5,5,6,4,3]}
x = [[i,j] for i,j in zip(data['x'],data['y'])]
data_x = np.asarray(x)
model_km = KMedoids(n_clusters=2)
km = model_km.fit(data_x)
print("Labels :",km.labels_)
print("Cluster centers :",km.cluster_centers_)
输出
Labels : [1 1 0 0 0 0 1 0 1 1]
Cluster centers : [[4. 6.]
[8. 4.]]
结论
K-Medoids是对M-Means算法的改进方法。它是无监督的，需要无标签的数据。K-Mediods是一种基于距离的方法，依赖于聚类距离和聚类内的距离，其中medoids充当聚类中心，并作为参考点来计算距离。它非常有用，因为它可以有效处理异常值。