K-Means

K-Means是一种非监督学习，解决的是聚类问题。K代表的是K类，Means代表的是中心，我们可以理解这个算法的本质是确定K类的中心点，当你找到了这些中心点，也就完成了聚类

我们需要思考以下三个问题：

• 如何确定K类的中心点？
• 如何将其他点划分到K类中？
• 如何区分K-Means与KNN？

K-Means的工作原理

我们先思考一个场景，假设有20支亚洲足球队，想要将它们按照成绩划分成3个等级，可以怎样划分？

对亚洲足球队的水平，我们可能有自己的主观判断。比如：伊朗或韩国是一流；中国是二流；越南是三流

那么伊朗、中国、越南可以说是三个等级的典型代表，也就是我们每个类的中心点

所以，如何确定K类的中心点？一开始我们是可以随机指派的，当确认了中心点后，就可以按照距离将其他足球队划分到不同的类别中

这也就是K-Means的中心思想，就是这么简单直接。你可能会问：如果一开始，选择一流球队是中国，二流球队是伊朗，三流球队是韩国，中心点选择错了怎么办？

其实不用担心，K-Means有自我纠正机制，在不断的迭代过程中，会纠正中心点。中心点在整个迭代过程中，并不是唯一的，只是需要设置一个初始值，一般算法会随机设置初始的中心点

K-Means的工作原理总结如下：

• 选取K个点作为初始的类中心点，这些点一般都是从数据集中随机抽取的；
• 将每个点分配到最近的类中心点，这样就形成了K个类，然后重新计算每个类的中心点；
• 重复第二步，直到类不发生变化，或者你也可以设置最大迭代次数，这样即使类中心点发生变化，但是只要达到最大迭代次数就会结束

如何给亚洲球队做聚类

对于机器来说需要数据才能判断类中心点，2015-2019年亚洲球队的排名，如下表所示

其中2019年国际足联的世界排名，2015年亚洲杯排名均为实际排名。2018年世界杯中，很多球队没有进入到决赛圈，所以只有进入到决赛圈的球队才有实际的排名

如果是亚洲区预选赛12强的球队，排名会设置为40。如果没有进入亚洲区预选赛12强，球队排名会设置为50

针对上面的排名，我们首先需要做的是数据规范化。可以把这些值划分到[0,1]或者按照均值为0，方差为1的正态分布进行规范化

如果我们随机选取中国、日本、韩国为三个类的中心点，我们就需要看下这些球队到中心点的距离

距离有多种计算的方式，有关距离的计算跟KNN算法一致

• 欧氏距离
• 曼哈顿距离
• 闵可夫斯基距离
• 切比雪夫距离
• 余弦距离

欧氏距离是最常用的距离计算方式，这里我们选择欧氏距离作为距离的标准，计算每个队伍分别到中国、日本、韩国的距离，然后根据距离远近来划分，我们看到大部分的队，会和中国队聚类到一起

如果按照中国、日本、韩国为3个分类的中心点，欧氏距离的计算结果如下表所示

然后我们再重新计算这三个类的中心点，如何计算呢？最简单的方式就是取平均值，然后根据新的中心点按照距离远近重新分配球队的分类，再根据球队的分类更新中心点的位置。计算过程这里不展开，最后一直迭代（重复上述的计算过程：计算中心点和划分分类）到分类不再发生变化，可以得到以下的分类结果：

所以我们能看出来第一梯队有日本、韩国、伊朗、沙特、澳洲；第二梯队有中国、伊拉克、阿联酋、乌兹别克斯坦；第三梯队有卡塔尔、泰国、越南、阿曼、巴林、朝鲜、印尼、叙利亚、约旦、科威特和巴勒斯坦

如何使用sklearn中的K-Means算法

sklearn是Python的机器学习工具库，如果从功能上来划分，sklearn可以实现分类、聚类、回归、降维、模型选择和预处理等功能。这里我们使用的是sklearn的聚类函数库，因此需要引用工具包，具体代码如下：

from sklearn.cluster import KMeans


'''
n_clusters:即K值，一般需要多试一些K值来保证更好的聚类效果。可以随机设置一些K值，然后选择聚类效果最好的作为最终的K值
init：即初始值选择的方式，默认是采用优化过的k-means++方式，你也可以自己指定中心点，或者采用random完全随机的方式
    1. 自己设置中心点一般是对于个性化的数据进行设置，很少采用
    2. random的方式则是完全随机的方式，一般推荐采用优化过的k-means++方式
n_init：初始化中心点的运算次数，默认是10。程序是否能快速收敛和中心点的选择关系非常大，所以在中心点选择上多花一些时间，来争取整体时间上的快速收敛还是非常值得的。由于每一次中心点都是随机生成的，这样得到的结果就有好有坏，非常不确定，所以要运行n_init次,取其中最好的作为初始的中心点。如果K值比较大的时候，可以适当增大n_init这个值
max_iter：最大迭代次数，如果聚类很难收敛的话，设置最大迭代次数可以让我们及时得到反馈结果，否则程序运行时间会非常长
algorithm：k-means的实现算法，有auto、full、elkan三种。一般来说建议直接用默认的"auto"。简单说下这三个取值的区别，如果选择full采用的是传统的K-Means算法，auto会根据数据的特点自动选择是选择full还是elkan。我们一般选择默认的取值，即：auto

'''
KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm='auto')

当然K-Means只是sklearn.cluster中的一个聚类库，实际上包括K-Means在内，sklearn.cluster一共提供了9种聚类方法，比如Mean-shift，DBSCAN，Spectralclustering（谱聚类）等。这些聚类方法的原理和K-Means不同，这里不做展开

在创建好K-Means类之后，就可以使用它的方法，最常用的是fit和predict这个两个函数。可以单独使用fit函数和predict函数，也可以合并使用fit_predict函数。其中fit(data)可以对data数据进行k-Means聚类。predict(data)可以针对data中的每个样本，计算最近的类

from sklearn.cluster import KMeans
from sklearn import preprocessing
import pandas as pd

# 输入数据
data = pd.DataFrame({"国家": ['中国', '日本', '韩国', '伊朗', '沙特', '伊拉克', '卡塔尔', '阿联酋', '乌兹别克斯坦', '泰国', '越南', '阿曼', '巴林', '朝鲜',
                            '印尼', '澳洲', '叙利亚', '约旦', '科威特', '巴勒斯坦'],
                     "2019年国际排名": [73, 60, 61, 34, 67, 91, 101, 81, 88, 122, 102, 87, 116, 110, 164, 40, 76, 118, 160,
                                   96],
                     "2018世界杯": [40, 15, 19, 18, 26, 40, 40, 40, 40, 40, 50, 50, 50, 50, 50, 30, 40, 50, 50, 50],
                     "2015亚洲杯": [7, 5, 2, 6, 10, 4, 13, 6, 8, 17, 17, 12, 11, 14, 17, 1, 17, 9, 15, 16],
                     })

train_x = data[["2019年国际排名", "2018世界杯", "2015亚洲杯"]]
df = pd.DataFrame(train_x)
kmeans = KMeans(n_clusters=3)
# 规范化到[0,1]空间
min_max_scaler = preprocessing.MinMaxScaler()
train_x = min_max_scaler.fit_transform(train_x)
# kmeans算法
kmeans.fit(train_x)
predict_y = kmeans.predict(train_x)
# 合并聚类结果，插入到原数据中
result = pd.concat((data, pd.DataFrame(predict_y)), axis=1)
result.rename({0: u'聚类'}, axis=1, inplace=True)
print(result)

总结

如何确定K类的中心点？

其中包括了初始的设置，以及中间迭代过程中中心点的计算。在初始设置中，会进行n_init次的选择，然后选择初始中心点效果最好的为初始值。在每次分类更新后，都需要重新确认每一类的中心点，一般采用均值的方式进行确认

如何将其他点划分到K类中？

这里实际上是关于距离的定义，我们知道距离有多种定义的方式，在K-Means和KNN中，我们都可以采用欧氏距离、曼哈顿距离、切比雪夫距离、余弦距离等。对于点的划分，就看它离哪个类的中心点的距离最近，就属于哪一类

如何区分K-Means和KNN这两种算法呢？

我们可以从三个维度来区分K-Means和KNN这两个算法：

• 首先，这两个算法解决数据挖掘的两类问题。K-Means是聚类算法，KNN是分类算法
• 其次，这两个算法分别是两种不同的学习方式。K-Means是非监督学习，也就是不需要事先给出分类标签，而KNN是有监督学习，需要我们给出训练数据的分类标识
• 最后，K值的含义不同。K-Means中的K值代表K类。KNN中的K值代表K个最接近的邻居

常用场景

聚类的一个常用场景就是对图像进行分割。图像分割就是利用图像自身的信息，比如颜色、纹理、形状等特征进行划分，将图像分割成不同的区域，划分出来的每个区域就相当于是对图像中的像素进行了聚类

单个区域内的像素之间的相似度大，不同区域间的像素差异性大。这个特性正好符合聚类的特性，所以可以把图像分割看成是将图像中的信息进行聚类

当然聚类只是分割图像的一种方式，除了聚类，我们还可以基于图像颜色的阈值进行分割，或者基于图像边缘的信息进行分割等

将微信开屏封面进行分割，微信开屏图如下所示：

我们先设定下聚类的流程，聚类的流程和分类差不多，如图所示：

在准备阶段里，我们需要对数据进行加载。因为处理的是图像信息，我们除了要获取图像数据以外，还需要获取图像的尺寸和通道数，然后基于图像中每个通道的数值进行数据规范化

这里我们需要定义个函数load_data，来帮我们进行图像加载和数据规范化。代码如下：

# 加载图像，并对数据进行规范化
def load_data(filePath):
    # 读文件
    f = open(filePath,'rb')
    data = []
    # 得到图像的像素值
    img = image.open(f)
    # 得到图像尺寸
    width, height = img.size
    for x in range(width):
        for y in range(height):
            # 得到点(x,y)的三个通道值
            c1, c2, c3 = img.getpixel((x, y))
            data.append([c1, c2, c3])
    f.close()
    # 采用Min-Max规范化
    mm = preprocessing.MinMaxScaler()
    data = mm.fit_transform(data)
    return np.mat(data), width, height

因为jpg格式的图像是三个通道(R,G,B)，也就是一个像素点具有3个特征值。这里我们用c1、c2、c3来获取平面坐标点(x,y)的三个特征值，特征值是在0-255之间

为了加快聚类的收敛，我们需要采用Min-Max规范化对数据进行规范化。我们定义的load_data函数返回的结果包括了针对(R,G,B)三个通道规范化的数据，以及图像的尺寸信息。在定义好load_data函数后，我们直接调用就可以得到相关信息，代码如下：

# 加载图像，得到规范化的结果img，以及图像尺寸
img, width, height = load_data('./weixin.jpg')

假设我们想要对图像分割成2部分，在聚类阶段，我们可以将聚类数设置为2，这样图像就自动聚成2类。代码如下：

# 用K-Means对图像进行2聚类
kmeans =KMeans(n_clusters=2)
kmeans.fit(img)
label = kmeans.predict(img)
# 将图像聚类结果，转化成图像尺寸的矩阵
label = label.reshape([width, height])
# 创建个新图像pic_mark，用来保存图像聚类的结果，并设置不同的灰度值
pic_mark = image.new("L", (width, height))
for x in range(width):
    for y in range(height):
        # 根据类别设置图像灰度, 类别0 灰度值为255， 类别1 灰度值为127
        pic_mark.putpixel((x, y), int(256/(label[x][y]+1))-1)
pic_mark.save("weixin_mark.jpg", "JPEG")

我们使用了fit和predict这两个函数来做数据的训练拟合和预测，因为传入的参数是一样的，我们可以同时进行fit和predict操作，这样我们可以直接使用fit_predict(data)得到聚类的结果

得到聚类的结果label后，实际上是一个一维的向量，我们需要把它转化成图像尺寸的矩阵。label的聚类结果是从0开始统计的，当聚类数为2的时候，聚类的标识label=0或者1

如果想对图像聚类的结果进行可视化，直接看0和1是看不出来的，还需要将0和1转化为灰度值。灰度值一般是在0-255的范围内，我们可以将label=0设定为灰度值255，label=1设定为灰度值127。具体方法是用int(256/(label[x][y]+1))-1

可视化的时候，主要是通过设置图像的灰度值进行显示。所以我们把聚类label=0的像素点都统一设置灰度值为255，把聚类label=1的像素点都统一设置灰度值为127。原来图像的灰度值是在0-255之间，现在就只有2种颜色（也就是灰度为255，和灰度127）

有了这些灰度信息，我们就可以用image.new创建一个新的图像，用putpixel函数对新图像的点进行灰度值的设置，最后用save函数保存聚类的灰度图像。这样就可以看到聚类的可视化结果了，如下图所示：

完整代码，如下：

import numpy as np
import PIL.Image as image
from sklearn.cluster import KMeans
from sklearn import preprocessing


# 加载图像，并对数据进行规范化
def load_data(filePath):
    # 读文件
    f = open(filePath, 'rb')
    data = []
    # 得到图像的像素值
    img = image.open(f)
    # 得到图像尺寸
    width, height = img.size
    for x in range(width):
        for y in range(height):
            # 得到点(x,y)的三个通道值
            c1, c2, c3 = img.getpixel((x, y))
            data.append([c1, c2, c3])
    f.close()
    # 采用Min-Max规范化
    mm = preprocessing.MinMaxScaler()
    data = mm.fit_transform(data)
    return np.mat(data), width, height


# 加载图像，得到规范化的结果img，以及图像尺寸
img, width, height = load_data('./weixin.jpg')

# 用K-Means对图像进行2聚类
kmeans = KMeans(n_clusters=2)
kmeans.fit(img)
label = kmeans.predict(img)

# 将图像聚类结果，转化成图像尺寸的矩阵
label = label.reshape([width, height])

# 创建个新图像pic_mark，用来保存图像聚类的结果，并设置不同的灰度值
pic_mark = image.new("L", (width, height))

for x in range(width):
    for y in range(height):
        # 根据类别设置图像灰度, 类别0 灰度值为255， 类别1 灰度值为127
        pic_mark.putpixel((x, y), int(256 / (label[x][y] + 1)) - 1)
pic_mark.save("weixin_mark.jpg", "JPEG")

如果我们想要分割成16个部分，该如何对不同分类设置不同的颜色值呢？这里需要用到skimage工具包，它是图像处理工具包。可以使用pip install scikit-image来进行安装

这段代码可以将聚类标识矩阵转化为不同颜色的矩阵：

from skimage import color
# 将聚类标识矩阵转化为不同颜色的矩阵
label_color = (color.label2rgb(label)*255).astype(np.uint8)
label_color = label_color.transpose(1,0,2)
images = image.fromarray(label_color)
images.save('weixin_mark_color.jpg')

代码中，我们使用skimage中的label2rgb函数来将label分类标识转化为颜色数值，因为我们的颜色值范围是[0,255]，所以还需要乘以255进行转化，最后再转化为np.uint8类型。unit8类型代表无符号整数，范围是0-255之间

得到颜色矩阵后把它输出出来，这时会发现输出的图像是颠倒的，原因可能是图像源拍摄的时候本身是倒置的。我们需要设置三维矩阵的转置，让第一维和第二维颠倒过来，也就是使用transpose(1,0,2)，将原来的(0,1,2）顺序转化为(1,0,2)顺序，即第一维和第二维互换

最后我们使用fromarray函数，它可以通过矩阵来生成图片，并使用save进行保存

最后得到的分类标识颜色化图像是这样的：

完整代码如下：

import numpy as np
import PIL.Image as image
from sklearn.cluster import KMeans
from sklearn import preprocessing
from skimage import color


# 加载图像，并对数据进行规范化
def load_data(filePath):
    # 读文件
    f = open(filePath, 'rb')
    data = []
    # 得到图像的像素值
    img = image.open(f)
    # 得到图像尺寸
    width, height = img.size
    for x in range(width):
        for y in range(height):
            # 得到点(x,y)的三个通道值
            c1, c2, c3 = img.getpixel((x, y))
            data.append([c1, c2, c3])
    f.close()
    # 采用Min-Max规范化
    mm = preprocessing.MinMaxScaler()
    data = mm.fit_transform(data)
    return np.mat(data), width, height


# 加载图像，得到规范化的结果img，以及图像尺寸
img, width, height = load_data('./weixin.jpg')

# 用K-Means对图像进行16聚类
kmeans = KMeans(n_clusters=16)
kmeans.fit(img)
label = kmeans.predict(img)
# 将图像聚类结果，转化成图像尺寸的矩阵
label = label.reshape([width, height])
# 将聚类标识矩阵转化为不同颜色的矩阵
label_color = (color.label2rgb(label) * 255).astype(np.uint8)
label_color = label_color.transpose(1, 0, 2)
images = image.fromarray(label_color)
images.save('weixin_mark_color.jpg')

刚才我们做的是聚类的可视化。如果我们想要看到对应的原图，可以将每个簇（即每个类别）的点的RGB值设置为该簇质心点的RGB值，也就是簇内的点的特征均为质心点的特征

完整代码如下：

import numpy as np
import PIL.Image as image
from sklearn.cluster import KMeans


# 加载图像，并对数据进行规范化
def load_data(filePath):
    # 读文件
    f = open(filePath, 'rb')
    data = []
    # 得到图像的像素值
    img = image.open(f)
    # 得到图像尺寸
    width, height = img.size
    for x in range(width):
        for y in range(height):
            # 得到点(x,y)的三个通道值
            c1, c2, c3 = img.getpixel((x, y))
            data.append([(c1 + 1) / 256.0, (c2 + 1) / 256.0, (c3 + 1) / 256.0])
    f.close()
    return np.mat(data), width, height


# 加载图像，得到规范化的结果imgData，以及图像尺寸
img, width, height = load_data('./weixin.jpg')
# 用K-Means对图像进行16聚类
kmeans = KMeans(n_clusters=16)
label = kmeans.fit_predict(img)
# 将图像聚类结果，转化成图像尺寸的矩阵
label = label.reshape([width, height])
# 创建个新图像img，用来保存图像聚类压缩后的结果
img = image.new('RGB', (width, height))
for x in range(width):
    for y in range(height):
        c1 = kmeans.cluster_centers_[label[x, y], 0]
        c2 = kmeans.cluster_centers_[label[x, y], 1]
        c3 = kmeans.cluster_centers_[label[x, y], 2]
        img.putpixel((x, y), (int(c1 * 256) - 1, int(c2 * 256) - 1, int(c3 * 256) - 1))
img.save('weixin_new.jpg')

代码中，把范围为0-255的数值投射到1-256数值之间，这样做的原因是我们知道RGB每个通道的数值在[0,255]之间，所以我们可以用每个通道的数值+1/256，这样数值就会在[0,1]之间

对图像做了"Min-Max"空间变换之后，还可以对其进行反变换，还原出对应原图的通道值

对于点(x,y)，我们找到它们所属的簇label[x,y]，然后得到这个簇的质心特征，用c1,c2,c3表示：

c1 = kmeans.cluster_centers_[label[x, y], 0]
c2 = kmeans.cluster_centers_[label[x, y], 1]
c3 = kmeans.cluster_centers_[label[x, y], 2]

因为c1,c2,c3对应的是数据规范化的数值，因此我们还需要进行反变换，即：

c1=int(c1*256)-1
c2=int(c2*256)-1
c3=int(c3*256)-1

然后用img.putpixel设置点(x,y)反变换后得到的特征值。最后用img.save保存图像

常用场景总结

K-Means聚类有个缺陷：聚类个数K值需要事先指定。如果不知道该聚成几类，那么最好会给K值多设置几个，然后选择聚类结果最好的那个值

通过图像分割，我们发现用K-Means计算的过程在sklearn中就是几行代码，大部分的工作还是在预处理和后处理上。预处理是将图像进行加载，数据规范化。后处理是对聚类后的结果进行反变换

如果涉及到后处理，我们可以自己来设定数据规范化的函数，这样反变换的函数比较容易编写

另外我们还学习了如何在Python中如何对图像进行读写，这里使用PIL这个工具包，它的英文全称叫Python Imaging Library，顾名思义，它是Python图像处理标准库

同时我们也使用到了skimage工具包（scikit-image），它也是图像处理工具包。skimage可以和Matlab相媲美，集成了很多图像处理函数，比如对不同分类标识显示不同的颜色。在Python中图像处理工具包，我们用的是skimage工具包

不同尺寸的图像，K-Means运行的时间也是不同的。如果图像尺寸比较大，可以事先进行压缩，长宽在200像素内运行速度会比较快，如果超过了1000像素，速度会很慢