机器学习算法系列(9)k均值

本项目github地址:https://github.com/swordspoet/machinelearningformyself

聚类是一种了解数据内在结构的方法,它通过将数据集中的样本划分为若干不相交的子集,每个子集称为一个“簇”(cluster)。如何定义簇以及簇的数量则完全人工自行决定。

在先前的文章中涉及到的算法都是监督学习,现在我们开始接触到机器学习中第一个无监督学习算法——k-均值。不同于以往的数据集,无监督学习所用到的数据集都是没有标签的,也就是事先并不知道数据的内在性质及规律。

k-均值的最终目的是最小化平方误差:

\[\begin{equation}\begin{split} E = \sum_{i=1}^{k}\sum_{x\in C_i}{||x-\mu_i||}_2^2 \label{k-means} \end{split}\end{equation}\]

一、k-means基本思路

k-均值算法的基本思路:

  1. 随机生成k个随机质心
  2. 计算样本值到质心之间的欧式距离,将样本点划分到距离最近的质心
  3. 重新更新各个簇的质心位置
  4. 重复2-3步,直到质心位置不再变化
  5. 得出输出结果

二、基于Python的k均值算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
from numpy import *
# 导入文件
file_name = "E:/Python/mla/Ch10/testSet.txt"
def load_data(file_name):
data_mat = []
fr = open(file_name)
for line in fr.readlines():
# 将文本文档的每一行转换成浮点型并添加到矩阵中
current_line = line.strip().split('\t')
data_mat.append([float(current_line[0]), float(current_line[1])])
dataset = mat(data_mat)
return dataset
dataset = load_data(file_name)
1
2
3
# 计算向量间欧几里得距离
def cal_dist(vec_a, vec_b):
return sqrt(sum(power(vec_a - vec_b, 2)))
1
2
3
4
5
6
7
8
9
# 生成k个随机质心(centroids)
def rand_centroid(dataset, k):
n = shape(dataset)[1]
centroids = mat(zeros((k, n)))
for j in range(n):
min_j = min(dataset[:, j])
range_j = float(max(dataset[:, j]) - min_j)
centroids[:, j] = min_j + range_j * random.rand(k, 1)
return centroids
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
# k均值聚类算法
def k_means(dataset, k):
m = shape(dataset)[0] # 获取数据的行数m
# 簇分配结果矩阵'cluster'包含两列:
# 第一列记录簇索引值,第二列存储误差
cluster = mat(zeros((m, 2)))
centroids = rand_centroid(dataset, k)
# 创建一个标志变量'cluster_changed'
cluster_changed = True
while cluster_changed:
cluster_changed = False
for i in range(m):
min_dist = inf
min_index = -1
# 分别计算'dataset'中第i个点与k个质心之间的欧几里得距离,
# 并将距离最小的质心的索引赋给簇分配结果
for j in range(k):
dist_i_j = cal_dist(centroids[j, :], dataset[i, :])
if dist_i_j < min_dist:
min_dist = dist_i_j
min_index = j
if cluster[i, 0] != min_index:
cluster_changed = True
cluster[i, :] = min_index, min_dist**2
print(centroids)
# 更新质心的位置,直到簇分配结果不再改变为止
for cent in range(k):
index = cluster[:, 0].A # 簇分配结果中的所有索引
value = nonzero(index == cent)
sample_in_cent = dataset[value[0]]
centroids[cent, :] = mean(sample_in_cent, axis=0) # 按列计算均值
return centroids, cluster

经过四次迭代之后算法收敛,得到4个质心,四个质心以及原始数据的散点图在下图给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[[ 1.71514331 4.38373482]
[-2.07697989 -2.34923269]
[ 1.37232864 -1.69241204]
[-4.4940993 -0.98212537]]
[[ 1.21336621 3.14825539]
[-2.98849186 -3.14785829]
[ 2.8692781 -2.54779119]
[-3.56936853 0.80979859]]
[[ 1.98283629 3.1465235 ]
[-3.38237045 -2.9473363 ]
[ 2.80293085 -2.7315146 ]
[-2.768021 2.65028438]]
[[ 2.6265299 3.10868015]
[-3.38237045 -2.9473363 ]
[ 2.80293085 -2.7315146 ]
[-2.46154315 2.78737555]]
1
2
3
4
5
6
7
8
9
10
11
def showCluster(dataset, k, centroids, cluster):
numSamples, dim = dataset.shape
mark = ['or', 'ob', 'og', 'ok']
for i in range(numSamples):
markIndex = int(cluster[i, 0])
plt.plot(dataset[i, 0], dataset[i, 1], mark[markIndex])
mark = ['*r', '*b', '*g', '*k']
# 画出质心
for i in range(k):
plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)
plt.show()
k均值聚类的结果

k均值聚类的结果

三、讨论

缺点:

  • 对异常值敏感,因为在计算各个簇质心位置时,异常点往往会使得结果变得扭曲
  • 在对事物没有一定了解的前提下事先难以确定k值
  • 算法的时间复杂度较高,在处理大数据时是相对可伸缩和有效的,通常需要使用合适规模的样本
  • 只能发现球状簇,对不规则的簇效果一般

解决异常值敏感可采用k中心算法,k中心点算法中,每次迭代后的质点都是从聚类的样本点中选取,而选取的标准就是当该样本点成为新的质点后能提高类簇的聚类质量,使得类簇更紧凑。该算法使用绝对误差标准来定义一个类簇的紧凑程度。另外的优化手段还有凝聚的与分裂的层次聚类。

觉得还不错?帮我赞助点域名费吧:)