Introduction

最近在做数据分析相关研究时需要用到K-Medoids算法对数据进行聚类，然后在平时常用的Python的sklearn.cluster库模块中没有找到这个算法函数，于是想着找一下别的库。首先是发现了一位研究数据分析的博主的一份笔记：K-medoids聚类算法原理简介&Python与R的实现，在文末评论里他提到博文中用的pyclust模块不维护了，然后推荐了pyclustering模块和其参考文档。为加深自己的理解，特此对文档做一份学习笔记。

K-Medoids文档渣翻与应用

pyclustering.cluster.kmedoids.kmedoids：一个用于表征K-Medoids算法的类

公共类成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def __init__ (self, data, initial_index_medoids, tolerance=0.001, ccore=True, kwargs)
# K-Medoids聚类算法的构造初始化

def process (self)
# 根据K-Medoids算法的规则进行聚类分析

def predict (self, points)
# 对于每个点计算离它距离最近的簇

def get_clusters (self)
# 返回已分配好群集的列表,每个群集包含数据列表中对象的索引

def get_medoids (self)
# 返回由输入数据中的索引表示的已分配群集的medoid列表

def get_cluster_encoding (self)
# 返回指示如何对群集进行编码的群集结果表示类型

这里对每个函数的注释仅是简单翻译了一下官方文档里的那句话，对函数的详细使用和分析可结合下面详细说明中代码样例里我注释的笔记来理解。

详细说明

该算法与K-Means相比对异常值的敏感性较低。K-Medoids与K-Medians的主要区别在于，K-Medoids使用输入数据空间中的已有点作为每个簇的中心点，但K-Medians中的中心点可以是不真实的对象（而不是从输入数据空间中选取已有点）。

下面是官方给出的一个聚类样例，在代码中加入了一些本人做的笔记注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from pyclustering.cluster.kmedoids import kmedoids
from pyclustering.cluster import cluster_visualizer
from pyclustering.utils import read_sample
from pyclustering.samples.definitions import FCPS_SAMPLES

# 导入待聚类的样本点。
# 这里我打印了一下这些数据，整个sample就是一个二维的列表（甚至没有用到numpy包），共有800行（也就是800个数据点），每一行是一个长度为2的列表（就是TWO_DIAMONDS二维数据），列表中的两个数的数据类型为float。导入自己数据进行聚类时可参考这个格式。
sample = read_sample(FCPS_SAMPLES.SAMPLE_TWO_DIAMONDS)

# 设定随机的初始中心点索引。
# 这里中心点的数据类型是一个int类型的列表，列表中每个值代表每一类中心点的索引。注意该列表的长度已经代表了你要聚类的类别个数，也就是说len(initial_medoids)=k。
initial_medoids = [1, 500]

# 创建K-Medoids算法的实例。
# 这里就创建了kmedoids类的一个对象，__init__函数被调用，这里传入了前两个参数，后面的参数保持默认状态。
kmedoids_instance = kmedoids(sample, initial_medoids)

# 进行聚类分析并获取聚类结果。
kmedoids_instance.process()
clusters = kmedoids_instance.get_clusters()

# 打印分配好的聚类结果。
# 这里的clusters为一个k（本示例k=2）行列表，每一行列表里嵌套一个索引列表，列表里是对应簇中所有点的索引值（int型）。
print(clusters)

# 打印各簇中心点。
# 此段代码官方示例中没有，是我自己为了看一下get_medoids()函数而加的，得到的结果是medoids为一个长度为k的列表，每个元素对应每个簇的中心点的索引值（int型）。
medoids = kmedoids_instance.get_medoids()
print(medoids)

#聚类的可视化，用了模块里的自带功能。
visualizer = cluster_visualizer()
visualizer.append_clusters(clusters, sample)
visualizer.show()

各点之间距离的计算方法可以由kmedoids类对象初始化里的参数“Metric”指定。需要注意的是kmedoids(metric=metric)传入的metric是一个distance_metric类对象，而这个类对象是pyclustering模块里的另一个定义的类（详细文档），调用的时候需要import一下。可选择的距离类型参考type_metric的文档，官方选用了MINKOWSKI距离作为示例：

1
2
3
4
5
6
7
8
9
10
11
12
# 导入相关模块
from pyclustering.utils.metric import distance_metric, type_metric

# 创建Minkowski距离度量方法，并设置相关的degree参数为'2'
metric = distance_metric(type_metric.MINKOWSKI, degree=2)

# 在创建K-Medoids类对象时附上metric参数
kmedoids_instance = kmedoids(sample, initial_medoids, metric=metric)

# 下面的活就跟之前的一样了
kmedoids_instance.process()
clusters = kmedoids_instance.get_clusters()

下面这个就体现了K-Medoids算法相比于K-Means的一个优越性所在：可适用类别（categorical）类型的特征。因为K-Means每次计算质心取的均值可能不是一个真实的点，所以对原始数据有要求为数据点类型，能够映射到对应维度的一个空间里的具体位置中，即要求数据点处在一个欧氏空间之中。然而并不是所有的数据都能满足这样的要求，这里K-Medoids就解决了这个问题（参考文章），在算法里重新计算中心点时只需要点与点之间的距离即可，因此其适用范围可扩散到各种各样的数据，前提是只要你可以正确计算出每个元素之间的距离即可。pyclustering.cluster.kmedoids里即可使用距离矩阵代替点序列来提高性能。为此，在创建K-Medoids类对象时要使用data_type这个参数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 若用pyclustering自带的计算距离功能，这里需要先导入相关模块。
from pyclustering.utils import calculate_distance_matrix

# 计算样本数据的距离矩阵。
# 这里read_sample里传入的参数其实可以是本地数据文件地址或上面示例里的模块自带样本数据，暂时先改一下跟上面示例一样用自带数据。
# sample = read_sample(path_to_sample)
sample = read_sample(FCPS_SAMPLES.SAMPLE_TWO_DIAMONDS)

# 这里calculate_distance_matrix返回的matrix是一个800×800的二维列表（模拟数据点为800个），每个元素类型为float，是一个对称型矩阵，自行计算距离矩阵时记得注意一下数据格式。然后数值越大代表两点距离越大，也即代表两点差异性越大，注意不要和相似度矩阵搞反了。
matrix = calculate_distance_matrix(sample)

# 创建K-Medoids类对象时把data_type这个参数设为'distance_matrix'。
kmedoids_instance = kmedoids(matrix, initial_medoids, data_type='distance_matrix')

# 下面的活也跟之前的一样了。
kmedoids_instance.process()
clusters = kmedoids_instance.get_clusters()
medoids = kmedoids_instance.get_medoids()

构造和析构函数文档

1
2
3
4
5
6
7
8
def pyclustering.cluster.kmedoids.kmedoids.__init__	(	 	
    self,
 	data,
 	initial_index_medoids,
 	tolerance = 0.001,
 	ccore = True,
 	kwargs 
)

参数：

参数名 含义
data （list型）输入数据，表征点（对象）的列表，每个点的表征格式都应为列表或元组。
initial_index_medoids （list型）初始中心点的索引（输入数据中点的索引）。
tolerance （double型）算法停止条件：如果在重新计算簇的中心点中，新旧中心点的距离变化的最大值小于这个tolerance，则算法停止运算。默认值为0.001。
ccore （bool型）如果指定CCORE库（C++的pyclustering库）的话，则用于代替Python代码进行聚类。
**kwargs 任意关键字参数（可用参数：’metric’, ‘data_type’, ‘itermax’）。

关键字参数：

  • metric (distance_metric型): 用于计算两点之间距离的计算方法，默认为EUCLIDEAN_SQUARE。
  • data_type (string型): 输入样本数据的数据类型，有两种：’points’, ‘distance_matrix’，默认为’points’。
  • itermax (uint型): 聚类分析的最大迭代次数，默认为200。

成员函数文档

成员函数中get_cluster_encoding(),get_clusters(),get_medoids(),process()都在前面示例代码里提到了，而且原文档中这里的介绍也比较简单就不再重复。在这里重点介绍一下predict()函数：

1
2
3
4
def pyclustering.cluster.kmedoids.kmedoids.predict (
    self,
 	points 
)

用于计算对于每个点的最近聚类簇。

参数

[in]points(array_like型): 已计算好最近邻聚类簇的点集。

返回值

(list型) 对于每个点的最近邻聚类簇的列表形式。每个聚类簇用索引来表示。如果process()方法在此之前未被调用的话会返回一个空集。

一个样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from pyclustering.cluster.kmedoids import kmedoids
from pyclustering.samples.definitions import SIMPLE_SAMPLES
from pyclustering.utils import read_sample

# 导入模拟数据，这里用了SAMPLE_SIMPLE3这种生成方式。
sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3)

# 设k=4，设了４个初始中心点。
initial_medoids = [4, 12, 25, 37]

# 构建kmedoids聚类对象。
kmedoids_instance = kmedoids(sample, initial_medoids)

# 进行聚类分析。
kmedoids_instance.process()

# 对以下两个点计算出最近邻的聚类簇
# 这里可以看到points就是用了与sample格式相同的数据点，然后输入predict()方法中，返回的是一个长度等于points中数据点个数的列表，列表中的每个值是聚类簇的索引，比如这里的取值范围就是0-3，代表对应points中位置的那个点应该属于哪个已聚好的类，其实就是相当于一个分类器。
points = [[0.35, 0.5], [2.5, 2.0]]
closest_clusters = kmedoids_instance.predict(points)
print(closest_clusters)

Elbow法则的应用

对k值的取值一直是K-Means、K-Medoids等划分类聚类算法的一个关键问题，而Elbow法则是最常用的一种方法。在研究pyclustering文档时无意中发现里面还有pyclustering.cluster.elbow这个模块，于是打算尝试一下把这个封装好的Elbow法则结合到上面的K-Medoids算法中。

pyclustering.cluster.elbow文档解析

具体的分析内容均写在下面的代码注释里了：

公共类成员函数

1
2
3
4
5
6
7
8
9
10
11
def __init__ (self, data, kmin, kmax, kwargs)
# 构造Elbow方法。
 
def process (self)
# 执行分析以找出适当数量的群集。
 
def get_amount (self)
# 返回由Elbow法则得出的k值。
 
def get_wce (self)
# 返回一个列表，每个元素是(kmin, kmin + 1, ..., kmax - 1)这个范围里不同的k取值所对应的误差函数的值。也就是可以绘制那条肘部法则折线图的取值。

详细说明与代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from pyclustering.cluster.kmeans import kmeans, kmeans_visualizer
from pyclustering.cluster.center_initializer import kmeans_plusplus_initializer
from pyclustering.cluster.elbow import elbow #导入elbow模块
from pyclustering.utils import read_sample
from pyclustering.samples.definitions import SIMPLE_SAMPLES

# 采样数据和前面一样。
sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3)

# 创建Elbow方法实例，设K从1取到9（kmax-1）。
kmin, kmax = 1, 10
elbow_instance = elbow(sample, kmin, kmax)
# 这里需要提一下elbow初始化函数里的一个任意关键字参数：initializer，是初始质心的取值方法，有kmeans_plusplus_initializer和random_center_initializer两种，前者是K-Means++里的方法，后者是经典的随机取点，默认取值是kmeans_plusplus_initializer，若要改为随机取点参照下面这行代码。
#elbow_instance = elbow(sample, kmin, kmax, initializer=random_center_initializer)

# 运行输入的数据并获得分析的结果。
elbow_instance.process()
# 返回的是一个int型数据，代表在Elbow法则的判别下得出的最有可能的k取值。
amount_clusters = elbow_instance.get_amount()
# 返回的是一个列表，保存了每个k值对应的误差函数的值。
wce = elbow_instance.get_wce()

# 下面是利用K-Means算法依据前面得出的K值进行的聚类。
# 初始化质心调用了center_initializer模块中的K-Means++式的初始化方式。
centers = kmeans_plusplus_initializer(sample, amount_clusters, amount_candidates=kmeans_plusplus_initializer.FARTHEST_CENTER_CANDIDATE).initialize()
# 后面的步骤就跟K-Medoids差不多，同一个库里的接口设置得还比较相似。
kmeans_instance = kmeans(sample, centers)
kmeans_instance.process()
clusters = kmeans_instance.get_clusters()
centers = kmeans_instance.get_centers()
kmeans_visualizer.show_clusters(sample, clusters, centers)

把elbow模块应用到K-Medoids中

研究过elbow模块里的源代码可以发现elbow里的误差函数是由K-Means算法里的结果计算出来的，因此由此得出的K值应该是适用于K-Means里的K值，而并不一定适用于K-Medoids里。不过为了探索一下这个难得封装好的elbow法则在K-Medoids里的应用，我尝试了一下利用K-Means确定的K值来做K-Medoids聚类，代码及注释放在下面。

需要注意的一点是初始化中心点时，调用了pyclustering.cluster.center_initializer模块中的K-Means++式初始化方法，而该模块中的initialize()函数有一个bool型的参数return_index，若为True则返回初始化中心点的索引（可用于pyclustering模块的K-Medoids算法中），否则默认为False，返回初始化中心点的数值数组（用于pyclustering模块的K-Means算法中）。在下面的代码中我分别用centers_data和centers_index两个变量接收两个不同格式的返回值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from pyclustering.cluster.kmeans import kmeans, kmeans_visualizer
from pyclustering.cluster.kmedoids import kmedoids
from pyclustering.cluster.center_initializer import kmeans_plusplus_initializer
from pyclustering.cluster.elbow import elbow
from pyclustering.utils import read_sample
from pyclustering.samples.definitions import SIMPLE_SAMPLES
import matplotlib.pyplot as plt

sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3)

kmin, kmax = 1, 10
elbow_instance = elbow(sample, kmin, kmax)
elbow_instance.process()

amount_clusters = elbow_instance.get_amount()  # 得到K值
wce = elbow_instance.get_wce()  # 得到误差函数


# 初始化质心返回数值
centers_data = kmeans_plusplus_initializer(sample, amount_clusters,
                                      amount_candidates=kmeans_plusplus_initializer.FARTHEST_CENTER_CANDIDATE).initialize()
# 初始化质心返回质心索引
centers_index = kmeans_plusplus_initializer(sample, amount_clusters,
                                      amount_candidates=kmeans_plusplus_initializer.FARTHEST_CENTER_CANDIDATE).initialize(return_index=True)

# 下面分别进行K-Means和K-Medoids算法，并打印聚类结果进行对比
# K-Means
kmeans_instance = kmeans(sample, centers_data)
kmeans_instance.process()
kmeans_clusters = kmeans_instance.get_clusters()
kmeans_centers = kmeans_instance.get_centers()
for row in kmeans_centers:
	print(row)
print('*********K-Means结果*********')
i=1
for cluster in kmeans_clusters:
	print("第%d类个数：%d"%(i,len(cluster)))
	i+=1
    
# K-Medoids
kmedoids_instance = kmedoids(sample, centers_index, itermax=10000)
kmedoids_instance.process()
kmedoids_clusters = kmedoids_instance.get_clusters()
kmedoids_medoids = kmedoids_instance.get_medoids()
for item in kmedoids_medoids:
	print(sample[item])
print('*********K-Medoids结果*********')
i=1
for cluster in kmedoids_clusters:
	print("第%d类个数：%d"%(i,len(cluster)))
	i+=1

# 绘出K值与误差函数值的折线图
x=list(range(1,10))
plt.plot(x,wce)
plt.xlabel('K')
plt.ylabel('error')
plt.xticks(x)
plt.grid()
plt.show()

代码中的sample变量可更改为任意符合格式的数据。我用我自己的一些研究数据尝试了一下，总的来说从聚类后各类别的数量上来看，K-Means和K-Medoids聚类的结果相差并不大。因此从我自己数据的角度来看，把elbow模块用在K-Medoids算法之前帮忙确定K值这个做法不会产生太大问题，但毕竟这种做法在逻辑上严谨来说是说不通，需要具体数据具体分析。在反复运行程序时出现变化的因素有：

  • 在elbow_instance.process()过程中由于K-Means算法本身的随机性，重复运行程序有可能会得出不同的K值。
  • 在kmeans_plusplus_initializer().initialize()初始化中心点时，由于K-Means++算法本身在概率上的随机性，重复运行程序有可能会得出不同的初始化中心点。
  • 在kmeans_instance.process()和kmedoids_instance.process()过程中，由于算法本身的随机性，重复运行程序可能会出现每一类的数目有稍微变化的情况。然后针对前面“K-Means和K-Medoids聚类的结果相差并不大”，出现的特例在于有可能对于一个K值，K-Means（K-Medoids）的聚类结果是每个类别数目较为平均可观，但是K-Medoids（K-Means）的聚类结果中有某一类或数类里只有1个或几个元素（就是明显的无意义分类）。这种情况在反复运行程序过程中不会经常出现，但本人也碰到有出现过的情况，这个取决于数据本身的分布特征以及前面确定K值和初始化质心等工作的质量。

After

有意向进一步研究一下elbow模块的源代码，仿照一下写一个用K-Medoids算法得出误差函数的elbow模块，把elbow法则真正结合到K-Medoids模块算法中。