K均值聚类算法

机器学习三大类,监督学习、无监督学习和强化学习。K均值(K-Means)是无监督学习中的一种聚类算法,能有有效的将数据划分子类。

K-means_convergence.gif

应用场景

打开新浪新闻首页,可以发现“要闻”一栏展示了目前最热门的一组新闻。类似的还有google news等

xlxw.png

思路

以二维数据为例,描述一下k-means的实现思路:

1. 在二维平面区域内n个样本点中,首先任意选取m个点,称其为质心点
2. 对n个样本点和m个质心点求距离(欧式距离),找到每个样本点离得最近的质心点
3. 更新m个质心点的位置,重复第2步

以下图为例,描述详细的划分流程

6step.png

1. 在平面内n个样本点中,选2个质心点标记好x,对应b)
2. 分别对n个样本点和2个质心点求距离,找到每个样本点离得最近的质心点;对应图c)  
3. 更新2个质心点的位置对应图d)
4. 重复第2步,找到每个样本点离得最近的质心点;对应图e)
5. 重复第2步,找到每个样本点离得最近的质心点;对应图f)

下面使用Python语言实现模型训练和预测,其中会使用到 numpymatplotlib.pyplotsklearn.datasetsscipy.spatial.distance,不熟悉的童鞋自行先去补一下,看起来事半功倍!

实现代码

思路:使用sklearn.datasets提供的数据来训练出模型。然后使用训练出的模型进行预测并验证模型的正确性!

引入依赖

1
2
3
4
import numpy as np
import matplotlib.pyplot as plt

from sklearn.datasets.samples_generator import make_blobs

初始化数据

1
2
3
4
5
# x 是n个样本点
# y 是每个样本点对应的质心点
x, y = make_blobs(n_samples=100, centers=6, random_state=1234, cluster_std=0.6)
#print(x)
#print(y)

为了方便观察,我们画出图

1
2
plt.figure(figsize=(6,6))
plt.scatter(x[:,0],x[:,1], c=y)

csh.png

编写核心k-means代码,封装一个类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
from scipy.spatial.distance import cdist

class K_Means(object):

# 初始化,参数n_clusters(k), 迭代次数max_iter ,初始质心 centroids
def __init__(self,n_cluster=6,n_iters=300,centeroids=[]):
self.n_cluster = n_cluster
self.n_iters = n_iters
self.centeroids = centeroids

# 训练模型
def fit(self,data):
# 1. 计算每个样本点和样每个质心点欧式距离
distances = cdist(data,self.centeroids)

# 2. 将distances排序,找到最小的那个距离的下标
c_ind = np.argmin(distances,axis=1)

# 3. 对每一类数据进行均值计算,更新质心点位置
for i in self.n_cluster:
if i in c_ind:
self.centeroids[i] = np.mean(data[ c_ind == i ],axis = 0)

# 预测
def predict(self,samples):
distances = cdist(samples,self.centeroids)
return np.argmin(distances,axis=1)

测试,为了方便观察我们先封装一个画子图方法

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
# 画子图函数
def plotKMeans(x,y,centroids,subplot,title):
# 分配子图 121表示1行2列的子图中的第一个
plt.subplot(subplot)
plt.scatter(x[:,0],x[:,1],c='r')
# 画出质心点
plt.scatter(centroids[:,0],centroids[:,1],c=np.array(range(6)),s=100)
plt.title(title)

kmeans = K_Means(max_iter=300,centroids=np.array([[2,1],[2,2],[2,3],[2,4],[2,5],[2,6]]))

plt.figure(figsize=(16,6))
plotKMeans(x,y,kmeans.centroids,121,'Init State')
# 开始聚类
kmeans.fit(x)
plotKMeans(x,y,kmeans.centroids,122,'Final State')

# 预测新数据[0,0]和[10,7]的类别
x_new = np.array([[0,0],[10,7]])
y_pred = kmeans.predict(x_new)
# 打印预测出的类别
print(y_pred)
# 质心点在二维坐标轴的位置
print(kmeans.centroids)

plt.scatter(x_new[:,0],x_new[:,1],s=100,c='black')

end.png

预测的结果是[0,0]属于1; [10,7]属于5,1对应的群组是质心点[-2,0]所在的群组,而5对应的群组是质心点[9,7]所在的群组,显然是正确的。