K-means 学习笔记

本文最后更新于:4 个月前

K-means 学习笔记

前言

K-means 算法是最为经典的基于划分的聚簇方法,是经典数据挖掘算法之一。简单的说就是在没有任何监督信号的情况下将数据分为 K 份的一种方法, 也就是分门别类。

K-means 算法

算法原理

基本思想:

给定 K 值和 K 个初始类中心点,把每个点分到离其最近的类中心点所代表的类中,所有点分配完毕之后,根据一个类内的所有点重新计算该类的中心点(平均值),然后再迭代的进行分配点和更新类中心点的步骤,直至类中心点的变化很小,或者达到指定的迭代次数。

对一个样本集 , 这里每个 x 都有 m 个维度的属性, 我们想要将其划分为 k 个聚类

首先,我们从样本集 D 中随机获取 k 个样本作为初始类中心点

然后计算每一个对象到每一个聚类中心的欧式距离:

其中,m 为样本点的纬度属性

依次比较每一个对象到每一个聚类中心的距离,将对象分配到距离最近的聚类中心的类簇中,得到 k 个类

类中心就是类内所有对象在各个维度的均值,其计算公式如下

其中, 为第 k 个聚类的中心, 为第 k 个聚类中元素的个数。

总的来说,K-means 算法的基本思想还是容易理解的,主要流程可以分为如下几步:

  1. 选择聚类的个数 K
  2. 任意产生 k 个聚类, 然后确定聚类中心(或者直接生成 K 个中心)
  3. 把每个数据点分配到离它最近的中心点
  4. 再迭代计算新聚类的新中心
  5. 重复以上步骤直到满足收敛要求

效果展示如下:

算法实现

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import numpy as np
import matplotlib.pyplot as plt


# 加载数据
def loadDataSet(file):
dataSet = np.loadtxt(file, delimiter='\t')
return dataSet


# 计算欧式距离
def euclDistance(x, y):
return np.sqrt(np.sum((x - y) ** 2)) # 计算欧氏距离


# 初始化 k 个聚类中心
def getCenter(dataSet, k):
# 行,列大小
m, n = dataSet.shape
# 初始化 k 个聚类中心
center = np.zeros((k, n))
for i in range(k):
# 产生 k 个 [0, m) 的数
index = int(np.random.uniform(0, m))
center[i, :] = dataSet[index, :]
return center


# k均值聚类
def KMeans(dataSet, k):
m = np.shape(dataSet)[0] # 行的数目
# 第一列存样本属于哪一类,初始为 0
# 第二列存样本的到类的中心点的误差
clusterAssment = np.mat(np.zeros((m, 2))) # 创建 m 行 2 列的矩阵
clusterChange = True # 记录样本的点类是否发生变化

# 第1步 初始化center
center = getCenter(dataSet, k)
# 如果上一次迭代过程中仍有样本点的类别发生变化,则继续计算
while clusterChange:
clusterChange = False

# 遍历所有的样本(行数)
for i in range(m):
minDist = np.inf
minIndex = -1

# 第2步 找出离样本点最近的质心
# 遍历所有质心
for j in range(k):
# 计算该样本到质心的欧式距离
distance = euclDistance(center[j, :], dataSet[i, :])
if distance < minDist:
minDist = distance # 更新最短距离
minIndex = j # 更新离该样本最近的中心

# 第 3 步:更新每一行样本所属的类
# 如果样本类别发生变化
if clusterAssment[i, 0] != minIndex:
clusterChange = True
# 更新类别以及误差
clusterAssment[i, :] = minIndex, minDist**2

# 第 4 步:更新质心
# 遍历每一个类
for j in range(k):
# .A 将矩阵转化为数组
# nonzero(a) 返回数组a中非零元素的索引值数组
pointsInCluster = dataSet[np.nonzero(
clusterAssment[:, 0].A == j)[0]] # 获取类所有的点
center[j, :] = np.mean(pointsInCluster, axis=0) # 对矩阵的行求均值

print("Congratulations,cluster complete!")
return center, clusterAssment


def showCluster(dataSet, k, center, clusterAssment):
m, n = dataSet.shape
if n != 2:
print("数据不是二维的")
return 1

mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
if k > len(mark):
print("k值太大了")
return 1

# 绘制所有的样本
for i in range(m):
markIndex = int(clusterAssment[i, 0])
plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
# 绘制质心
for i in range(k):
plt.plot(center[i, 0], center[i, 1], mark[i])
plt.show()


dataSet = loadDataSet("test.txt")
k = 4
center, clusterAssment = KMeans(dataSet, k)

showCluster(dataSet, k, center, clusterAssment)

优缺点

  1. 原理比较简单,实现也是很容易,收敛速度快
  2. 算法的可解释度比较强
  3. 聚类中心的个数 K 需要事先给定,但在实际中 K 值的选定是非常困难的
  4. k-means 算法需要随机地确定初始聚类中心,不同的初始聚类中心可能导致完全不同的聚类结果。

K-means++ 算法

上面我们提到 k-means 算法需要随机地确定初始聚类中心,不同的初始聚类中心可能导致完全不同的聚类结果。对于这个问题,K-means++ 算法进行了优化。

算法原理

K-means++ 算法初始化聚类中心的策略也非常简单,流程如下:

  1. 从数据集中随机选择一个点作为第一个聚类中心
  2. 计算每个样本与最近一个聚类中心的距离, 距离越大表示被选取作为聚类中心的概率越大
  3. 用轮盘法选出下一个聚类中心
  4. 重复上述过程,直到选择出 k 个聚类中心
  5. 执行标准的 K-means 算法

效果展示如下:

算法实现

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
# 样本点到最近的聚类中心的距离
def getClosestDist(data, center):
min_dist = np.inf
m = np.shape(center)[0] # 当前已经初始化的聚类中心的个数
for i in range(m):
# 计算样本点与每个聚类中心之间的距离
d = euclDistance(center[i, :], data)
# 选择最短距离
if min_dist > d:
min_dist = d
return min_dist


# 初始化 k 个聚类中心
def getCenterPlusPlus(dataSet, k):
m, n = dataSet.shape
# 初始化 k 个聚类中心
center = np.zeros((k, n))
# 1、随机选择一个样本点为第一个聚类中心
index = np.random.randint(0, m)
center[0, :] = dataSet[index, :]
# 初始化一个距离的序列
d = [0.0 for _ in range(m)]

for i in range(1, k):
sum_all = 0
for j in range(m):
# 2、对每一个样本找到最近的聚类中心点
d[j] = getClosestDist(dataSet[j, ], center[0:i, ])
# 将所有的最短距离相加
sum_all += d[j]
# 3、用轮盘法选出下一个聚类中心
# 取得sum_all之间的随机值
sum_all *= np.random.random()
for j, dis in enumerate(d):
sum_all -= dis
if sum_all > 0:
continue
# 选择新的聚类中心
center[i, :] = dataSet[j, :]
break
return center

参考资料


本文作者: EmoryHuang
本文链接: https://emoryhuang.cn/blog/3762216339.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明来自EmoryHuang