KMeans聚类算法介绍

聚类算法是一种非监督算法,当你拥有大量的无标签数据的时候,最方便的做法就是对这些数据用聚类算法进行分类,打上标签。

一、KMeans算法的应用

  • 图像分割
  • 基因片段分类
  • 文章标签归类
  • 物种种群分类
  • 异常数据检测

二、KMeans算法步骤

  • 第一步 - 随机选择 K 个点作为点的聚类中心,这表示我们要将数据分为 K 类。
  • 第二步 - 遍历所有的点 P, 算出 P 到每个聚类中心的距离,将 P 放到最近的聚类中心的点集中。遍历结束后我们将得到 K 个点集。
  • 第三步 - 遍历每一个点集,算出每一个点集的中心位置,将其作为新的聚类中心。
  • 第四步 - 重复步骤 2 和步骤 3,直到聚类中心位置不再移动。最后的结果是点和质心之间的均方差达到最小。

三、KMeans算法的Python实现

下面我们以 k = 3 为例演示这个过程。

1、初始化

1
2
3
4
5
6
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import copy

%matplotlib inline
1
2
3
4
5
6
7
8
df = pd.DataFrame({
'x': [12, 20, 28, 18, 29, 33, 24, 45, 45, 52, 51, 52, 55, 53, 55, 61, 64, 69, 72],
'y': [39, 36, 30, 52, 54, 46, 55, 59, 63, 70, 66, 63, 58, 23, 14, 8, 19, 7, 24]})

np.random.seed(200)

k = 3
centroids = {i+1: [np.random.randint(0, 80), np.random.randint(0, 80)] for i in range(k)}
1
2
3
4
5
6
7
8
9
fig = plt.figure(figsize = (5, 5))
plt.scatter(df['x'], df['y'], color = 'k') # 画出所有的(x, y)
colmap = {1: 'r', 2: 'g', 3: 'b'}
for i in centroids.keys():
plt.scatter(*centroids[i], color = colmap[i]) # 画出3个聚类中心点

plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()

2、分配

1
2
3
4
5
6
7
8
9
10
11
def assignment(df, centroids):
# 计算每个点到聚类中心点的距离
for i in centroids.keys():
df["distance_from_{}".format(i)] = (np.sqrt((df['x'] - centroids[i][0])**2 + (df['y'] - centroids[i][1])**2))

# 每个点都计算其离三个中心点的距离,取出最短的那个,归类为它
centroid_distance_cols = ["distance_from_{}".format(i) for i in centroids.keys()]
df['closest'] = df.loc[:, centroid_distance_cols].idxmin(axis = 1)
df['closest'] = df['closest'].map(lambda x: int(x.lstrip('distance_from_')))
df['color'] = df['closest'].map(lambda x: colmap[x])
return df
1
2
df = assignment(df, centroids)
df.head()
xydistance_from_1distance_from_2distance_from_3closestcolor
0123926.92582456.08030056.7274181r
1203620.88061348.37354653.1507291r
2283014.14213641.76122653.3385411r
3185236.87817850.99019544.1021541r
4295438.11823740.80441234.0587733b
1
2
3
4
5
6
7
fig = plt.figure(figsize=(5, 5))
plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolor='k')
for i in centroids.keys():
plt.scatter(*centroids[i], color=colmap[i])
plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()

3、更新

1
2
3
4
5
def update(k):
for i in centroids.keys():
centroids[i][0] = np.mean(df[df['closest'] == i]['x'])
centroids[i][1] = np.mean(df[df['closest'] == i]['y'])
return k
1
2
old_centroids = copy.deepcopy(centroids)
centroids = update(centroids)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
fig = plt.figure(figsize=(5, 5))
ax = plt.axes()
plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolor='k')
for i in centroids.keys():
plt.scatter(*centroids[i], color=colmap[i])
plt.xlim(0, 80)
plt.ylim(0, 80)
for i in old_centroids.keys():
old_x = old_centroids[i][0]
old_y = old_centroids[i][1]
dx = (centroids[i][0] - old_centroids[i][0]) * 0.75
dy = (centroids[i][1] - old_centroids[i][1]) * 0.75
ax.arrow(old_x, old_y, dx, dy, head_width=2, head_length=3, fc=colmap[i], ec=colmap[i])
plt.show()

4、重新分配

1
df = assignment(df, centroids)
1
2
3
4
5
6
7
fig = plt.figure(figsize=(5, 5))
plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolor='k')
for i in centroids.keys():
plt.scatter(*centroids[i], color=colmap[i])
plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()

可以看到一个红色的点,变成了绿色的;一个蓝色的点变成了红色的。我们更加接近最终目标了。

5、继续这个过程

现在重复这个过程,直到每一个集群都没有变化为止。

1
2
3
4
5
6
while True:
closest_centroids = df['closest'].copy(deep = True)
centroids = update(centroids)
df = assignment(df, centroids)
if closest_centroids.equals(df['closest']):
break
1
2
3
4
5
6
7
fig = plt.figure(figsize=(5, 5))
plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolor='k')
for i in centroids.keys():
plt.scatter(*centroids[i], color=colmap[i])
plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()

现在得到3个清晰地集群和3个质点在这三个集群的中间。

四、KMeans算法的scikit-learn实现

1
2
3
4
5
6
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

%matplotlib inline
1
2
3
df = pd.DataFrame({
'x': [12, 20, 28, 18, 29, 33, 24, 45, 45, 52, 51, 52, 55, 53, 55, 61, 64, 69, 72],
'y': [39, 36, 30, 52, 54, 46, 55, 59, 63, 70, 66, 63, 58, 23, 14, 8, 19, 7, 24]})
1
2
kmeans = KMeans(n_clusters = 3)
kmeans.fit(df)
1
KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,n_clusters=3, n_init=10, n_jobs=1, precompute_distances='auto',random_state=None, tol=0.0001, verbose=0)
1
2
labels = kmeans.predict(df)
centroids = kmeans.cluster_centers_
1
2
3
4
5
6
7
8
9
10
fig = plt.figure(figsize=(5, 5))

colors = list(map(lambda x: colmap[x+1], labels)) # colors只是一个迭代子,需要加一个list()来得到结果

plt.scatter(df['x'], df['y'], color=colors, alpha=0.5, edgecolor='k')
for idx, centroid in enumerate(centroids):
plt.scatter(*centroid, color=colmap[idx+1])
plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()

五、手肘法寻找最佳K值

以上已经介绍了 KMeans 方法的具体流程,但是我们还面临一个问题,如何确定 K 值。

1、手肘法原理

手肘法的评价K值好坏的标准是SSE(sum of the squared errors):

$$
SSE= \sum_{p\in C_i}|p-m_i|^2
$$

其中 Ci代表第i个簇,p是簇Ci里的样本点,mi是簇的质心。

随着聚类数k的增大,样本划分会更加精细,每个簇的聚合程度会逐渐提高,那么误差平方和SSE自然会逐渐变小。并且,当k小于最佳聚类数时,由于k的增大会大幅增加每个簇的聚合程度,故SSE的下降幅度会很大,而当k到达最佳聚类数时,再增加k所得到的聚合程度回报会迅速变小,所以SSE的下降幅度会骤减,然后随着k值的继续增大而趋于平缓,也就是说SSE和k的关系图是一个手肘的形状,而这个肘部对应的k值就是数据的最佳聚类数。这也是该方法被称为手肘法的原因。

2、scikit-learn实现

现在我们使用 sklearn 库中的 KMeans 方法来跑一下聚类过程,然后将到聚类中心的平均值变化作图。

1
2
3
4
5
6
7
8
9
loss = []
point_number = len(df)

for i in range(1, 10):
kmeans = KMeans(n_clusters=i, max_iter=100).fit(df)
loss.append(kmeans.inertia_ / point_number)

plt.plot(range(1, 10), loss)
plt.show()

六、KMeans的优缺点

1、优点

  1. 原理简单
  2. 实现容易
  3. 聚类效果中上(依赖K的选择)

2、缺点

  1. 无法确定K的个数 (根据什么指标确定K)
  2. 对离群点敏感 (容易导致中心点偏移)
  3. 算法复杂度不易控制 O(NKm), 迭代次数可能较多 (m可能会比较大)
  4. 局部最优解而不是全局优 (这个和初始点选谁有关)

七、参考文章

赞赏一杯咖啡
0%