数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究机器学习中K-Medoids聚类及其解题示例
简介
K-Medoids 是一种使用分区聚类方法的无监督聚类算法。它是 K-Means 聚类算法的改进版本，特别用于处理异常值数据。它需要无标签数据才能工作。
在本文中，让我们通过一个例子来了解 k-Medoids 算法。
K-Medoids 算法
在 K-Medoids 算法中，每个数据点都被称为类中心点(medoid)。类中心点充当聚类中心。类中心点是指其与同一聚类中所有其他点的距离之和最小的点。对于距离，可以使用任何合适的度量，如欧几里得距离或曼哈顿距离。
应用算法后，完整的数据将被分成 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}$$
序号 |
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)，并计算它们到其他点的距离。
序号 |
x |
y |
P1 (8,4) 的距离 |
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)，并计算距离。
序号 |
x |
y |
P1(8,5) 的距离 |
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 |
$$\mathrm{新的成本 C_{2}=[2+3+1+3]+[2+3+3+3]=20}$$
$$\mathrm{交换涉及的总成本 C=C_{2}-C_{1}=20-19=1}$$
由于交换涉及的总成本 C 大于 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 是一种基于距离的方法，它依赖于聚类之间的距离和聚类内的距离，其中类中心点充当聚类中心，并被用作计算距离的参考点。它非常有用，因为它可以非常有效地处理异常值。
2K+ 阅读量
