前言:请确保已知晓无监督学习和聚类的定义。

K-mean聚类算法

K-mean又称K均值算法,意思是将数据集分为K簇,每个簇以属于该簇的数据集均值为该簇的中心(或质心)。K-mean算法流程大致为:

  1. 首先随机选择K个初始聚类中心。

  2. 计算各个点到每个聚类中心的距离,将各个点归到距离最近的簇中。

  3. 用每个簇的数据重新计算各自的中心。

  4. 重复2、3过程,直到簇中心不再变化或者超过最大迭代次数。

可以看出,K-mean算法相对来说很简单,容易实现。但也导致它有一些缺点,关于K-mean算法的优缺点将在后面讨论。

在上述过程中,第二步中提到了计算距离,接下来先讨论距离计算。

距离计算

不同情况的距离度量选择是不同的,下面介绍常用的三种:

欧氏距离

\(d(x,y) = \sqrt{(x_1-y_1)^2+...+(x_n-y_n)^2} = \sqrt{\sum_{i=1}^n(x_i-y_i)^2}\)

曼哈顿距离

\(d(x,y) = \sum_{i=1}^n|x_i-y_i|\)

余弦相似度

\(\cos(\theta) = \frac{\vec A\cdot\vec B}{||\vec A||*||\vec B||}\)

K-mean算法实现

数据集可以私发

需要的包:

1
2
3
import numpy as np
import matplotlib.pyplot as plt
from sklearn.preprocessing import StandardScaler

StandardScal包是拿来标准化数据集的,关于手动实现Z-score标准化请见:

多元线性回归模型_Twilight Sparkle.的博客-CSDN博客

下面每一步都对照上面说到的步骤。

步骤1:随机选择初始质心

1
2
3
4
5
# 随机选择样本最为初始质心
def init_centroid(daraSet,K):
randIdx = np.random.permutation(daraSet.shape[0])
centroids = daraSet[randIdx[:K]]
return centroids

步骤2:欧式距离计算以及寻找最近质心

1
2
3
4
5
6
7
8
9
10
11
12
# 寻找最近质心索引
def find_closed_centroid(dataSet,centroids):
K = centroids.shape[0] # 质心个数
idx = np.zeros(dataSet.shape[0],dtype=int) # 样本到最近质心的索引
for i in range(dataSet.shape[0]):
# 计算一个样本到所有质心的欧氏距离
diff = np.tile(dataSet[i],(K,1)) - centroids # tile可以复制矩阵,用法自查
squaredDist = np.sum(diff**2,axis=1) # axis = 1计算每一行的和
distance = squaredDist ** 0.5
# 选出距离最小的质点索引
idx[i] = np.argmin(distance)
return idx

步骤3:根据分好的簇重新计算质心

1
2
3
4
5
6
7
8
9
10
11
12
# 计算质心
def compute_centroids(dataSet,idx,K,oldCentroids):
m,n = dataSet.shape
centroids = np.zeros((K, n))
for k in range(K):
# 提取属于同一类的样本
points = np.array(dataSet[np.where(idx == k)])
# 计算质心
centroids[k] = points.mean(axis=0) # 计算每一列的均值
# 计算变化量
changed = centroids - oldCentroids
return centroids,changed

步骤4:组合K-mean各模块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 组合K—mean
def run_Kmean(dataSet,K,max_iters = 100):
m,n = dataSet.shape
idx = []
# 初始化质点
centroids = init_centroid(dataSet,K)
for i in range(max_iters):
# 寻找最近质点(分组)
idx = find_closed_centroid(dataSet,centroids)
# 计算新质点
centroids,changed = compute_centroids(dataSet,idx,K,centroids)
if np.all(changed == 0):
break
return idx

绘图

1
2
3
4
5
6
7
# 绘图
def Kmean_plot(dataSet,idx,K):
for k in range(K):
# 提取属于同一类的样本
points = np.array(dataSet[np.where(idx == k)])
plt.scatter(points[:, 0], points[:, 1])
plt.show()

主函数(含数据标准化)

K-mean算法需要数据标准化。

1
2
3
4
5
6
7
8
if __name__ == '__main__':
dataSet = np.load('ex7_X.npy')
# K-mean需要数据标准化
scaler = StandardScaler()
dataSet = scaler.fit_transform(dataSet)
K = 3
classification = run_Kmean(dataSet,K)
Kmean_plot(dataSet,classification,K)

运行结果:

使用K-mean进行图像压缩

现在用K-mean来做一些有趣的事情吧!

原始图像:

我们需要将这张图像变为只有8个颜色构成的图像。

数据预处理

需要将图片转化为2维矩阵,这张图是\(128\times128\times3\)的,需要变为\((128\times128,3)\) 的矩阵,并且需要归一化。

1
2
3
4
5
6
original_img = plt.imread('bird_small.png')
# 归一化
original_img/=255
# 将图像转化为m*3的二维矩阵,m为图像像素,这里m应为128*128。
X_img = np.reshape(original_img, (original_img.shape[0] * original_img.shape[1], 3))
# print(X_img.shape)

压缩图像

需要在函数run_Kmean的返回值里多加一个centroids,其余代码不变。

1
2
3
4
5
6
K = 8
# max_iters = 10
idx,centroids = run_Kmean(X_img,K)
# 现在,将每一个像素覆盖为它所属的簇质心的值
X_recovered = centroids[idx]
X_recovered = np.reshape(X_recovered, original_img.shape)

绘制图像

1
2
3
4
5
6
7
8
9
10
11
12
13
# Display original image
fig, ax = plt.subplots(1, 2, figsize=(8, 8))
plt.axis('off')

ax[0].imshow(original_img * 255)
ax[0].set_title('Original')
ax[0].set_axis_off() # 不显示坐标轴

# Display compressed image
ax[1].imshow(X_recovered * 255)
ax[1].set_title('Compressed with %d colours' % K)
ax[1].set_axis_off()
plt.show()

结果:

使用sklearn的K-mean

网上随便找了张图片,来压缩吧!

写代码时发现一个很奇怪的问题,这张图它居然是4个图层的,变为二维数组时需要注意一下,不是变成\(m*3\) 而是\(m*4\) 。(后来发现只要是QQ截图的都是4图层的。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

if __name__ == '__main__':
original_img = plt.imread('color.png')
print("Shape of original_img is:", original_img.shape)
original_img /= 255
X_img = np.reshape(original_img, (original_img.shape[0] * original_img.shape[1], 4))
# 模型训练
K = 8
model = KMeans(n_clusters=K)
model.fit(X_img)
centroids = model.cluster_centers_
# labels得到的是质心索引
labels = model.predict(X_img)
# print(labels[:6])
# 替换样本
X_recovered = centroids[labels]
X_recovered = np.reshape(X_recovered, original_img.shape)

plt.imshow(X_recovered*255)
plt.axis('off')
plt.show()

压缩后:

K-mean算法的缺点

  1. 算法中的K是事先给定的,但是K的选择在许多时候是难以估计的,很多时候不知道数据集应该分为多少类最合适。

  2. K-mean初始质心选择如果选的不好,有可能无法得到有效的聚类结果。可能会局部收敛而非全局收敛。为了解决该问题,提出了二分K-mean算法,实验表明二分K-mean的聚类效果要好于普通的K-mean算法。

  3. 数据集较大时收敛较慢。

  4. 如果遇到非球状的数据,K-mean算法不适用。

该图来源:K-means聚类算法原理及python实现_杨Zz.的博客-CSDN博客_kmeans算法python实现