KMeans聚类算法简介

聚类是一类经典的无监督学习算法。所谓无监督就是指训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。在给定的数据情况下，聚类算法通过度量数据间的“距离”或者特征相似度，自动将这些数据分为若干个类别。Kmeans算法就是一个经典的聚类算法。

距离度量

大多数聚类算法是建立在距离度量之上的，下面例举了几种典型的距离度量方式：
1.闵可夫斯基距离
给定m维向量样本集合X，其中xi,xj是m维向量，属于X，xi和xj的闵可夫斯基距离定义为：

2.曼哈顿距离
当闵可夫斯基距离的p=1时，闵可夫斯基距离就变成了曼哈顿距离：

3.欧式距离
当闵可夫斯基距离的p=2时，闵可夫斯基距离就变成了欧式距离：

4.切比雪夫距离

当闵可夫斯基距离的p=∞时，闵可夫斯基距离就变成了切比雪夫距离：

5.相关系数
相关系数是用来度量两个样本的相似度的，相关系数越接近1说明两个样本越相似，相关系数越接近0说明两个样本区别越大：

6.夹角余弦
夹角余弦也是用来度量两个样本的相似度的，夹角余弦越接近1说明两个样本越相似，夹角余弦越接近0说明两个样本区别越大：

我们采用欧式距离作为KMeans算法度量样本间距离的方式。下面是KMeans算法的计算流程：
1）根据要聚类为K个类，随机初始化K个质心；
2）根据每个样本和质心的距离来进行聚类，最后有K个类；
3）计算现在的聚类情况，重新计算新的质心；
4）判断是否达到要求或者已经迭代到了最大次数，如果是就停止，输出聚类结果，如果不是的话，则继续到第2）步，把每个数据进行聚类；
下面我们来实现一下KMeans算法。

假设我有一个数据集，每个数据由两个数字构成，分别代表两个坐标轴

import matplotlib.pyplot as plt

x = []
y = []
data = []
f = open('./machinelearninginaction/Ch10/testSet.txt','r')
for line in f.readlines():
    x.append(float(line.split('\t')[0]))
    y.append(float(line.split('\t')[1]))
    data.append([float(line.split('\t')[0]),float(line.split('\t')[1])])
    
plt.scatter(x,y)
plt.show()

从数据分布上，我们可以看出这些数据大概可以聚类为四个类别。
下面我们先定义一个计算欧氏距离的函数：

import numpy as np

def distance(x1, x2):
    dist = np.sqrt(np.sum(np.power(x1-x2,2)))
    return dist

然后定义一个随机初始化K个质心的函数：

def center(data, k):
    m, n = data.shape
    centers = np.zeros((k, n))
    for i in range(k):
        center = data[np.random.choice(range(m))] # 从m个数据中随机选择一个作为质心
        centers[i] = center
    return centers

计算每个样本x距离最近的质心：

def closest_center(x, centers):
    index = 0
    closest_dist = float('inf')
    for i, center in enumerate(centers):
        dist = distance(x, center)
        if dist < closest_dist:
            index = i
            closest_dist = dist
    return index

对数据进行聚类，聚合为K个类：

def classify(centers, data, k):
    clusters = [[] for _ in range(k)] # 定义一个二维数组作为质心数组
    #for i in range(k):
    #    clusters.append()
    for i, x in enumerate(data):
        index = closest_center(x, centers)
        clusters[index].append(x)
        #clusters[index].append(i)
    return clusters

寻找新的质心：

def new_center(clusters, data, k):
    m, n = data.shape
    centers = np.zeros((k, n))
    for i, cluster in enumerate(clusters):
        #center = np.mean(data[cluster],axis=0)
        center = np.mean(cluster,axis=0)
        centers[i] = center
    return centers

组合在一起，形成KMeans算法：

def kmeans(data, k, max_iter):
    centers = center(data, k) # 计算初始聚类中心
    for i in range(max_iter):
        clusters = classify(centers, data, k) # 根据质心把数据分为k个簇
        current_centers = centers # 把当前的质心存储下来
        centers = new_center(clusters, data, k) # 根据k个簇来计算新的质心
        diff = centers - current_centers # 计算新的质心和老的质心的差别
        if not diff.any(): # 如果已经没有差别，说明无法再进化了就停止
            break
    return (clusters,centers) # 这里我返回的是聚类的簇，以及K个质心

下面我们来测试一下这个算法：

data = np.array(data)
# 因为看上去之前的数据可以聚合为4类，所以我的k设置为4，最大迭代次数设置为1000
(clusters,centers) = kmeans(data, 4, 1000)
colormap = ['yellow','green','black','blue'] # 设置聚合后四个簇的样本颜色
for i, cluster in enumerate(clusters):
    X = []
    for d in cluster:
        X.append(list(d))

    X = np.array(X)
    plt.scatter(X[:,0],X[:,1],c=colormap[i]) # 这里我让每个不同的簇显示不同的颜色


 # 画出每个簇的质心
plt.scatter(centers[:,0], centers[:,1], c='r', marker='d')
plt.show()

可以看到，聚类的效果还是不错的，并且各自的质心对其簇内的数据而言，基本都处在“中心”位置。
下面，我们用sklearn来解决同样的问题。

from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=4, random_state=0).fit(data)
# print(kmeans.labels_)
data = np.array(data)
plt.scatter(data[:, 0], data[:, 1], c=kmeans.labels_, cmap=plt.cm.Paired)

我们根据聚类后的四个类标签设置颜色，和我自己编写的程序结果一样。
KMeans等聚类算法还常常被应用到图像压缩领域中，下面我们就尝试着用KMeans算法来对图像进行一下压缩。

import numpy as np
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

def compress_image(img, num_clusters):
    X = img.reshape((-1,1)) # 把图像打成一个一维数组
    kmeans = KMeans(n_clusters=num_clusters, n_init=4, random_state=5)
    kmeans.fit(X) # 执行聚类
    centroids = kmeans.cluster_centers_.squeeze() 
    labels = kmeans.labels_
    # 提取聚类后的质心数据，并还原成原来图片的大小
    input_image_compressed = np.choose(labels, centroids).reshape(img.shape)
    return input_image_compressed

读取经典的lena.jpg，并转成灰度图，也就是单通道图像，便于计算

from skimage import io,transform,color
img = io.imread('lena.jpg')
gray_img = color.rgb2gray(img)

print(gray_img)

io.imshow(gray_img)
io.show()

对原图进行压缩并展示

img2 = compress_image(gray_img, 4)
io.imshow(img2)
io.show()

由于我们设置了图像聚类为4类，因此，可以看到损失较大

当然，如果我们设置图像聚类的簇较多的话，图像将会更保真，比如我设置图像聚类为24的话，可以看到：

基本和原图没有很大差别了。