python 实现 Kmeans 算法

发表于 | 分类于

KMeans 算法原理

算法流程图

1.png

评价指标

1.png

实现

kmeans.py

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
import numpy as np

class KMeans:
    def __init__(self, k):
        self._k = k      # 聚类簇数
        self.centroids = None  # 聚类中心

        # 聚类标签，第一列为样本聚类结果的中心，第二列为样本和聚类中心的距离
        self.clusterLabel = None


    def _euclDistance(self, sample, centroid):
        """  计算一个样本和所有聚类中心的距离 """
        return np.sum((sample - centroid) ** 2, axis=1)


    def fit(self, X):
        numSamples = X.shape[0]
        self.centroids = X[np.random.choice(numSamples, self._k), :]  # 随机采样
        self.clusterLabel = np.zeros((numSamples, 2))

        clusterChanged = True        # 标记聚类中心是否改变

        # 循环，直到聚类中心不再改变
        while clusterChanged:
            clusterChanged = False

            # 遍历每个样本
            for i in range(numSamples):
                # 计算样本和每个聚类中心的距离，并找到最小距离
                distances = self._euclDistance(X[i, :], self.centroids)
                minIndex = np.argmin(distances)

                # 更新样本的聚类结果
                if self.clusterLabel[i, 0] != minIndex:
                    self.clusterLabel[i, :] = minIndex, distances[minIndex]

            # 更新聚类中心
            for i in range(self._k):
                # 取出第 i 蔟 的所有点
                pointsInCluster = X[np.nonzero(self.clusterLabel[:, 0] == i)[0]]
                # 新的聚类中心
                new_centroid = np.mean(pointsInCluster, axis=0)
                # 若聚类中心改变，进行更新
                if (self.centroids[i, :] != new_centroid).all():
                    clusterChanged = True
                    self.centroids[i, :] = new_centroid


    def predict(self, X_test):
        y_pred = np.zeros(len(X_test))
        for i in range(len(X_test)):
            distances = self._euclDistance(X_test[i, :], self.centroids)
            y_pred[i] = np.argmin(distances)

        return y_pred

测试

1
2
3
4
5
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from kmeans import KMeans
1
2
3
4
5
6
7
8
9
# 制作数据集
X, y = make_blobs(n_samples=500, n_features=2, centers=4, random_state=100)

# 展示数据
color = ["red","pink","orange","gray"]
fig, ax = plt.subplots(1)
for i in range(4):
    ax.scatter(X[y==i, 0], X[y==i, 1], marker='o', s=8, c=color[i])
plt.show()

1.png

1
2
3
4
5
6
7
8
9
10
11
12
13
kmeans = KMeans(4)
kmeans.fit(X)
centroids = kmeans.centroids

# 展示结果
color = ["red","pink","orange","gray"]
fig, ax = plt.subplots(1)
for i in range(4):
    ax.scatter(X[y==i, 0], X[y==i, 1], marker='o', s=8, c=color[i])

ax.scatter(centroids[:, 0], centroids[:, 1], marker='x', s=50, c='black')

plt.show()

1.png

调用 sklearn 库

API

3.png

重要参数：init

2.png

代码

1
2
3
4
5
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score   # 轮廓系数

kmeans = KMeans(n_clusters=4).fit(X)
silhouette_score(X, kmeans.labels_)   # 0.729

KMeans 优缺点

优点

  • 原理简单，实现容易
  • 聚类效果较优
  • 只有簇数K需要调参

缺点

  • K值得选取不好把握，实际中可以通过轮廓系数画学习曲线，确定最优K值
  • 聚类中心得随机初始化对结果影响较大，实际中可以通过 kmeans++ 的改进来初始化
  • 对于不是凸的数据集难收敛，可以改用基于密度的聚类算法，比如：DESCAN