本文件算法将实现Python简单实现K-means聚类算法，然后进行两个案例：

• 对普通数据进行聚类
• 压缩图像

然后使用scikit-learn包实现图片压缩案例。
实验环境：win10 、Jupyter

普通数据聚类

1 加载数据并可视化

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sb
from scipy.io import loadmat
%matplotlib inline
data = loadmat('ex7data2.mat')
X = data['X']
fig, ax = plt.subplots(figsize=(8, 4))
ax.scatter(X[:,0], X[:,1])

# 根据上面的数据，可以初始化这几个类的中点，设置3个中点
initial_centroids =  np.array([[3, 3], [6, 2], [8, 5]])

构建一个根据现有簇中心点，设置数据所属簇类别的函数

def find_closest_centroids(X, centroids):
    """找到数据中每个实例最接近的聚类中心的数据
    args
    X:数据点
    centroids:数据点初始化中心
    return:距离聚类中心最近的数据索引
    """
    m = X.shape[0]           # 获取数据条数
    k = centroids.shape[0]   # 获取类别数
    idx = np.zeros(m)        # 数据X每个样本对应的类别
    
    # 遍历所有数据，找到距离聚类中心最近的
    for i in range(m):
        min_dist = 1000000
        # 确定当经数据，离哪个中心点更近
        for j in range(k):
            # 计算当前点与k个类别中心的举例
            dist = np.sum((X[i,:] - centroids[j,:]) ** 2)
            if dist < min_dist:
                min_dist = dist
                idx[i] = j
    return idx

# 第一次计算各个点所属类别
idx = find_closest_centroids(X, initial_centroids)  
idx[0:5]    # 查看前几个类别
"""
array([0., 2., 1., 0., 0.])
"""

构建一个函数：根据类别、数据及其所属类别计算新的簇中心

def compute_centroids(X, idx, k):
    """计算当前簇的中心点，获取新的聚类中心
    arg
    X:数据X
    idx:数据X对应的聚类类别
    k:簇的个数
    return:新的簇中心
    """
    # 得到矩阵大小，初始化矩阵
    m, n = X.shape
    centroids = np.zeros((k, n))  # 即数据又k簇，每簇的中心点由数据的特征数决定
    # 计算聚类中心
    for i in range(k):
        # 获取数据中类别为i的数据索引
        indices =  np.where(idx == i)
        # 计算新的中心点
        centroids[i,:] = (np.sum(X[indices,:], axis=1) / len(indices[0])).ravel()
    
    return centroids

compute_centroids(X, idx, 3)  # 查看更新后的簇中心点
"""
array([[2.42830111, 3.15792418],
       [5.81350331, 2.63365645],
       [7.11938687, 3.6166844 ]])
"""

2 构建kmeans算法

上面已经把kmeans的主要模块函数书写完毕，实际运行该算法并可视化结果。

def run_k_means(X, initial_centroids, max_iters):
    """计算当前簇的聚类中心
    arg
    X:数据
    idx:数据对应的类别
    k:簇的个数
    max_iters:迭代次数
    return:最后数据X对应的所属簇号，以及簇的中心点
    """
    m, n = X.shape
    k = initial_centroids.shape[0]
    idx = np.zeros(m)
    centroids = initial_centroids
    # STEP2：实施聚类算法，调用之前的两个函数
    # your code here  (appro ~ 2 lines)    
    for i in range(max_iters):
        idx = find_closest_centroids(X, centroids)
        centroids = compute_centroids(X, idx, k)
    
    return idx, centroids

idx, centroids = run_k_means(X, initial_centroids, 10) 

3 绘制结果

cluster1 = X[np.where(idx == 0)[0],:]   # 第一个簇
cluster2 = X[np.where(idx == 1)[0],:]   # 第二个簇
cluster3 = X[np.where(idx == 2)[0],:]   # 第三个簇
# 绘制结果
fig, ax = plt.subplots(figsize=(12,8))
ax.scatter(cluster1[:,0], cluster1[:,1], s=30, color='r', label='Cluster 1')
ax.scatter(cluster2[:,0], cluster2[:,1], s=30, color='g', label='Cluster 2')
ax.scatter(cluster3[:,0], cluster3[:,1], s=30, color='b', label='Cluster 3')
ax.legend()

注： 在上面kmeans函数的构建中，是根据数据可视化自己选择簇的中心，这可能可以影响算法的收敛。

下面创建一个选择随机样本点作初始聚类中心的函数。

def init_centroids(X, k):
    """随机初始化聚类中心
    arg
    X:数据
    k:聚类数
    return:初始化簇中心点
    """
    m, n = X.shape  # 获取数据数量及特征数
    # 根据数据信息以及簇个数构建各簇中心点
    centroids = np.zeros((k, n))
    # 在数据中随机找三个点作为簇中心点
    idx = np.random.randint(0, m, k)
    
    for i in range(k):
        centroids[i,:] = X[idx[i],:]
    
    return centroids

init_centroids(X, 3)   # 初始化簇中心
"""
array([[2.40304747, 5.08147326],
       [3.23197916, 4.93989405],
       [3.20367116, 4.85924759]])
"""

kmeans算法应用——图像压缩

图像压缩原理：原始图像是一个128*128 3 通道的数据，将图像的宽、高压缩到一个维度，保留通道数为一个维度，那么数据就是16384*3的数据量。可以理解为这张图片一共有16384行数据，每行数据有3个特征。然后对这些数据设置16个簇（对于原始图片，可以理解为分成了16块），通过kmeans算法得到16各簇中心点。再将这16384行数据设置所属对应簇，那么保存这张压缩图片，保存这16个簇中心数据，以及这16384行数数据对应类别即可，那么需要的数据量就是16384+16*3 也就是原图片数据的$\frac{1}{3}$多一点。下面看看具体实现。

1 查看图片及数据

# 查看原始图片
from IPython.display import Image
Image(filename='bird_small.png')

# 加载matlab图片数据
image_data = loadmat('bird_small.mat')
image_data.keys()  # 查看mat格式数据有哪些内容
"""
dict_keys(['__header__', '__version__', '__globals__', 'A'])
"""

A = image_data['A']  # 获取数据
A.shape              # 图像为128*128 3通道的图片
"""
(128, 128, 3)
"""

由于各通道数据的数值差别还比较大，需要对数据应用一些预处理。

# 归一化数据
A = A / 255.
# 重置矩阵大小，将行数和列数合并，通道为单独的一维
X = np.reshape(A, (A.shape[0] * A.shape[1], A.shape[2]))
X.shape
"""
(16384, 3)
"""

2 压缩图片

# 随机初始化聚类中心
initial_centroids = init_centroids(X, 16)  # 随机抽取16个样本点作为聚类中心
# 运行kmeans聚类算法，迭代10次
idx, centroids = run_k_means(X, initial_centroids, 10)

# 获取样本点属于类别
idx = find_closest_centroids(X, centroids)

# 把每一个像素值与聚类结果进行匹配
X_recovered = centroids[idx.astype(int),:]
X_recovered.shape
"""
(16384, 3)
"""

# 将数据转成之前的数据格式
X_recovered = np.reshape(X_recovered, (A.shape[0], A.shape[1], A.shape[2]))
X_recovered.shape
"""
(128, 128, 3)
"""

3 使用scikit-learn的kmeans算法压缩图像

我们实现了kmeans算法，但是考虑并不够多，性能相对较差。下面使用scikit-learn包中kmeans模块实现图片压缩。需要的python有skimage、sickit-learn。

from skimage import io

pic = io.imread('bird_small.png') / 255. # 加载图片并进行归一化处理
io.imshow(pic)

pic.shape   # 查看图像数据形状信息，即：宽、高位128、128，3通道
"""
(128, 128, 3)
"""

# 类似之前的操作，重置图像大小
data = pic.reshape(128*128, 3)
data.shape
"""
(16384, 3)
"""

#导入k-means库
from sklearn.cluster import KMeans
# 构建kmeans算法模型
model = KMeans(n_clusters=16, n_init=100, n_jobs=-1)
# 开始训练
model.fit(data)
"""
KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
       n_clusters=16, n_init=100, n_jobs=-1, precompute_distances='auto',
       random_state=None, tol=0.0001, verbose=0)
"""

相关参数：

• n_clusters 设置簇的个数，
• n_init 构建100个kmeans模型，选择最好的（kmeans效果会受到初始化点影响），
• n_jobs 指定使用的进程数，1表示使用所有的cpu进行计算，小于-1，则用到的cpu数为 系统cpu数 + 1 + n_jobs
• max_iter 迭代次数

更多可参考官方文档。

# 得到各簇中心点
centroids = model.cluster_centers_  
print(centroids.shape)              # 查看簇的形状
C = model.predict(data)             # 获取每条数据所属簇
C.shape
"""
(16, 3)
(16384,)
"""

centroids[C].shape                 # 使用kmeans算法得到的数据得到压缩后的图片
"""
(16384, 3)
"""

compressed_pic = centroids[C].reshape((128,128,3))

# 绘制原图和压缩图片
fig, ax = plt.subplots(1, 2)
ax[0].imshow(pic)
ax[1].imshow(compressed_pic)

总结

从上面也之间简要的了解kmeans算法的内容，并不是所有数据都可以使用该方法进行聚类，例如环状数据。当使用scikit-learn包后，你会发现其背后考虑的内容确实很多，也确实对很多算法进行了优化，通过选择不同初始值，调用系统不同数目cpu来加快模型训练，这也是很多人喜欢使用包的一个原因吧，这个轮子我就不造了。
程序源码可在订阅号"AIAS编程有道"中回复“机器学习”即可获取。