机器学习笔记——16 聚类(clustering)：系统聚类与k-means聚类及对“距离”的重新认识(实战项目：利用k-means实现对图像的压缩)

机器学习笔记——16 聚类(clustering)：系统聚类与k-means聚类及对“距离”的重新认识(实战项目：利用k-means实现对图像的压缩)

在无监督学习中，由于没有标签值，所以也就失去了损失函数这个用样本来近似总体的监督准则，因此我们的学习就需要从样本本身的属性出发。那么从样本的本身属性值出发，有什么信息是可以利用的呢，一般常用的有：

样本属性间的“距离”样本属性间的方差与相关性，或者更一般地说，样本属性的各阶样本原点矩和样本中心矩

重新认识距离

“距离”对我们并不陌生，最符合我们“直觉”和出名的大概就是欧式距离了。但是，欧式距离只是对两点间“距离”的一种刻画。一般来讲，我们可以从日常经验中抽象总结出“距离”应该具有的最简和最本质的公理，只要一种刻画方式满足公理，它自然也可以用来刻画距离。

欧式空间

在向量空间中，通过定义内积(仿造三维的内积定义)，可以引申出距离和角度的定义，此时该空间也称为欧式空间(大概是为了纪念欧几里得)。具体的，两个向量的内积应该满足的公理如下：

可交换性和正则性：$$\varphi (\xi ,\eta )=\varphi (\eta ,\xi )$$$$\varphi (\xi ,\xi )>0when\xi !=0$$线性性：$$\varphi (a\xi ,\eta )=a\varphi (\xi ,\eta )$$可加性：$$\varphi ({\xi }_1+{\xi }_2,\eta )=\varphi ({\xi }_1,\eta )+\varphi ({\xi }_2,\eta )$$ 此时可以由内积来定义长度，以及两点间的距离：$$L(\xi )=\sqrt{\varphi (\xi ,\xi )}>=0$$ 角度余弦定义：$$cos(\xi ,\eta )=\frac{\varphi (\xi ,\eta )}{L(\xi )L(\eta )}\in (-1,1)$$

角度定义中的取值限制是由柯西不等式决定的$$\varphi (\xi ,\eta {)}^2<=\varphi (\xi ,\xi )\varphi (\eta ,\eta )$$事实上，该式有一个更为直观的理解，即斜边长度大于直角边长度：$$|\xi |>\varphi (\xi ,\frac{\eta }{|\eta |})$$

通过内积的定义，可以引出正交性，单位正交基等中重要概念。这里需要对正交性进行更多的解释。所谓正交，即是$$\varphi (\xi ,\eta )=0$$

几何角度，正交意味着$cos(\xi ,\eta )=0$，即向量在该内积定义的欧式空间中相互垂直。数据角度，正交意味着连个数据维度是独立。一般实际中对数据维度的重选只根据相关性。

常用的长度(距离)刻画方式

$\sqrt{x^{T}x}$：这是欧式距离在高位空间的推广。根据上面对内积的一般化讨论，当向量x所依据的基元单位正交时，那么其内积的值即为根号内的形式。$\sqrt{x^T{\Sigma }^{-1}x}$：马氏距离，该距离的公式等价于$\sqrt{(U^{T}x{)}^T{\lambda }^{-1}(U^{T}x)}$，因此马氏距离相当于先消除相关性(特征投影)，然后在去除数据的量纲(除以特征值)。

聚类(clustering)

聚类算法是一种无监督学习方法，他的目的是根据训练集的属性数据，进行类别识别，将训练样本识别成k个类别，得到类别中心，并基于此对新样本进行分类。 聚类算法所利用的信息是各个样本之间的距离，其基本思想是就将距离近的点划分为一类。 在选定距离的一种刻画方式后，就可以利用聚类常用的有两个算法，系统聚类和k-means聚类，来对样本进行分类。

系统聚类

对m个样本，初始将其视为m个类别，执行下列程序

计算两两之间的距离$L$，计算量为$C_m^2$对距离最小的两类合并，计算新类的中心${\mu }_{new}$计算新类与其他点的距离，计算量为$m-1$重复1-3

分析可知，距离的计算次数为$$C_m^2+\sum _{i=1}^{m}i=m^2-m=O(m^2)$$ 由此可以看到，系统聚类是有缺陷的，他的计算量在m比较大时，是很大的。在大数据背景下动辄几百万的数据下，比如一百万，则需要计算大概1万亿次距离，这显然是很慢和低效的。 通过分析也可发现，我们并不需要计算出所有两两点之间的距离，因为计算出来的很多距离并没有用上。

k-means 聚类

k-means 需要我们先确定类别个数$k$，并初始化$k$个类中心${\mu }_k$在此基础，执行下列程序：

E： 对于每个样本，计算其到各个类中心的距离，并将其分类到距离最近的类中，即设对于第$x_{(i)}$将其分类到第$C^{(i)}$类$$C^{(i)}=ar{g}_{i}min||\varphi (x^{(i)},{\mu }_i)||$$M： 更新$k$个类中心${\mu }_k$，取分类点中的平均值(或者其他可以代表类整体的中心刻画方式)$${\mu }_j:=\frac{{\sum }_{i=1}^{m}1\{C^{(i)}=j\}{x}^{(i)}}{{\sum }_{i=1}^{m}1\{C^{(i)}=j\}}$$重复1-2

我们首先分析这个算法的计算量。每一次迭代E步需要计算$km$次距离，而迭代M步中，对类中心的更新中计算量较小，可忽略。则若迭代N次，共需要$$km\ast N=kmN=O(m)$$在m较大是，迭代次数$N<<m$。因此其计算距离次数对样本量的增长是线性的，主要得益于其无须对样本点进行距离两两计算。

关于 k-means 收敛性的理论分析

如果采用事后判别$|{\mu }^{{}^{\prime \prime }}-{\mu }^{{}^{\prime }}|<ϵ$，可以证明该算法一定后收敛。首先定义一个全局总距离函数(英文原文为 distortion funtion)$$J(c,\mu )=\sum _{i=1}^m\varphi (x^{(i)},{\mu }_{(c^{(i)})})$$显然该函数有下界。进一步，每一次迭代的E步，我们通过调整$c^{(i)}$必然可以严格降低$J$，否则迭代结束。然后在M步是我们通过调整${\mu }_j$，必然也可以降低$J$。因为对于${\sum }_{i=1}^{m}1\{c^{(i)}=j\}(x^{(i)}-\mu {)}^2$，当$\mu$为调整后的值，即$$\mu :=\frac{{\sum }_{i=1}^{m}1\{C^{(i)}=j\}{x}^{(i)}}{{\sum }_{i=1}^{m}1\{C^{(i)}=j\}}$$此时该式达到最小。 综上，每一次EM迭代，都能降低$J$，从而对于的$ϵ>0$，必定存在某次迭代使得$|J^{\prime }-J^{\prime \prime }|<ϵ$，否则与有下界矛盾。

注：首先无法保证J能降到全局最低，因为$J$是非凸函数，其次理论上存在一定的可能性，使得$\mu ,c$ 出现震荡现象，最后类中心的收敛值未必是理想的。

The distortion function J is a non-convex function, and so coordinate descent on J is not guaranteed to converge to the global minimum. In other words, k-means can be susceptible to local optima. Very often k-means will work fine and come up with very good clusterings despite this. But if you are worried about getting stuck in bad local minima, one common thing to do is run k-means many times (using different random initial values for the cluster centroids μj). Then, out of all the different clusterings found, pick the one that gives the lowest distortion J(c, μ). ---- Andrew Ng

k-means 的改进 k-means++

(待续)

实战项目： 利用k-means实现图像压缩(python)

一些说明与注意事项：

压缩比分析：未进行压缩时，该图像需要512 * 512 * 3 B= 768 KB，使用k个颜色进行压缩，若k = 16，则4比特就可以表示每个像素的信息，即每个像素存储空间为 半个字节，共需要 512 * 512 * 0.5 B ，忽略16种颜色的文件头声明，压缩后的图像只要之前的1/6存储空间。 一般的，设原存储每个像素需要n个字节，而在k-means中的类别数为设为$k=2^m$，则现在存储每个像素只需m个比特，忽略文件头声明，则压缩比为m：8n。通过运行可以发现，kmeans在一开始的几次迭代，distort funtion下降的很快，此时对图片来说，其肉眼可见的改变很大，而后面的迭代其改变肉眼已经很难有所发现了。编写程序注意事项：利用cs229的数据，其三维数组的类型是uint8，因此需要先转化为float64，否则会有一些运算错误和赋值精度损失。此外，运算时尽可能地采用矢量化方式，以加快速度。程序运行结果： k = 4 初始迭代: 第30次迭代 k = 16 初始迭代: 第30次迭代

python代码

from matplotlib.image import imread import matplotlib.pyplot as plt import numpy as np def distortFun(Image,C,clusterCenter): # 本函数计算返回distort Funtion 的值 Fun = 0 for i in range(clusterCenter.shape[0]): sample_in_i = Image[C == i] distances = sample_in_i - clusterCenter[i,:] Fun = Fun + np.sum(distances*distances) return Fun def E_updata(Image,C,clusterCenter): # 本函数对利用新的类中心对各个样本进行重新归类，即更新C for i in range(Image.shape[0]): for j in range(Image.shape[1]): distances = clusterCenter - Image[i,j,:] distances = distances*distances # 计算样本到各个类中心的距离,*表示元素点乘 distances = np.sum(distances,axis = 1) C[i,j] = np.argmin(distances) # 选择距离最小的类别 def M_updata(Image,C,clusterCenter): # 本函数对重新分配类别后的类中心进行更新，即更新clusterCenter for i in range(clusterCenter.shape[0]): sample_in_i = Image[C == i] # 选取i类别的像素点，这里利用bool矩阵索引: Image[indexMat] clusterCenter[i,:] = np.sum(sample_in_i,axis = 0)/(sample_in_i.shape[0]) # 更新第i个类中心的值 def reducedImage(shape,C,clusterCenter): # 本函数返回压缩后的图像矩阵 rImage rImage = np.zeros((shape),dtype = np.uint8) for i in range(clusterCenter.shape[0]): rImage[C == i] = clusterCenter[i,:] return rImage def main(): # 读取图片的矩阵数据 Image = imread('C:/Users\Administrator\Desktop\image\mandrill-large.tiff') Image = Image.astype(np.float64) # 像素所属类别分配矩阵 C = np.ones((Image.shape[0],Image.shape[1]),dtype = np.int32) # 设置k-means的类别数 k = 48 # 随机选取16个样本作为初始类中心 rowRand = np.random.randint(Image.shape[0],size = k) colRand = np.random.randint(Image.shape[1],size = k) # 花式索引，返回副本 clusterCenter = Image[rowRand,colRand,:] # 最大迭代次数设置 iterMax = 100 # distort Fun 前后收敛限设置 epsilon = 100 iterN = 0 J2 = 0 J1 = 0 while((iterN < iterMax) and ((iterN < 2) or (J1 - J2 > epsilon))): J1 = J2 print("{0:-^70}".format(' 迭代次数:'+str(iterN))) # 更新类别 E_updata(Image,C,clusterCenter) # show the reduced figure every ten times if(iterN%10 == 0): rImage = reducedImage(Image.shape,C,clusterCenter) plt.imshow(rImage) plt.show() # 更新类中心 M_updata(Image,C,clusterCenter) J2 = distortFun(Image,C,clusterCenter) print('EM iteration later:',J2) iterN = iterN + 1 # show the finally reduced figure rImage = reducedImage(Image.shape,C,clusterCenter) plt.imshow(rImage) plt.show() if __name__ == '__main__': main()