019. K-means

本文将讨论K-means算法，它是一种基于聚类的无监督机器学习算法。
此外，我们还将讨论如何使用K-means来压缩图像。

在深入研究K-means算法的细节之前，让我们先了解一下无监督机器学习是什么，以及它的实际应用是什么。
与有标记数据的监督机器学习不同，无监督机器学习处理未标记数据的问题。
如果你熟悉经典的有监督机器学习，你可能会问，如何从未标记的数据集中学习任何有用的东西？
成本函数是否不需要输出标签来计算算法的执行方式？
我们在K-means中用来确定聚类有多好的成本函数称为失真成本函数。
本质上，它是数据点与分配给它的聚类质心的平均距离。
无监督机器学习（更具体地说是K-means），是通过将相似的数据点聚集在高维空间中来实现的。

数据点最初是分散的。
假设我们不知道每个数据点是如何相关的，但它们不失普遍性。
换句话说，仅仅通过查看图表，我们无法确定某某点是否相似，只是因为它们彼此靠近（同样，想象数据点是高维的，即大于3维）。
聚类的作用是，它将彼此更接近的数据点分组到一个聚类中，而不管维度的数量，从而表明属于单个聚类的数据点属于特定类。

这个简单的想法有可能解决我们社会面临的许多问题：（精准定位，投其所好）
1. 市场细分：根据不同的特征将潜在客户的市场划分或细分的过程。
创建的细分市场由消费者组成，消费者将对营销策略做出类似响应，并且共享诸如类似兴趣，需求或位置等特征。
2. 社交网络分析：分析具有相似品味的社交媒体平台的用户的过程。
在识别具有相似品味的用户之后，运行有针对性的广告变得更容易。
3. 天文数据分析：分析未标记的天文数据以找出隐藏模式的过程。
注意：当今世界中标记数据的数量只是可用数据量的一小部分。因此，这一事实进一步增强了无监督机器学习的优势。

K-means算法：是我们最常用的基于距离的聚类算法，其认为两个目标的距离越近，相似度越大。

K-means 有一个著名的解释：牧师—村民模型：
有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的村民，
于是每个村民到离自己家最近的布道点去听课。
听课之后，大家觉得距离太远了，
于是每个牧师统计了一下自己的课上所有的村民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。
牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个村民又去了离自己最近的布道点……
就这样，牧师每个礼拜更新自己的位置，村民根据自己的情况选择布道点，最终稳定了下来。
我们可以看到牧师的目的是为了让每个村民到其最近中心点的距离和最小。

所以 K-means 的算法步骤为：
1. 选择初始化的 k 个样本作为初始聚类中心；
2. 针对数据集中每个样本，计算它到 k 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；
3. 针对每个类别，重新计算它的聚类中心（即属于该类的所有样本的质心）；
4. 重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

So k-means clustering requires some distance metric (say Euclidean), 
a hypothesized fixed number of clusters, and an initial guess as to cluster centroids.

When it's finished k-means clustering returns a final position of each cluster's centroid 
as well as the assignment of each data point or observation to a cluster.

具体步骤：
1. 选择K，这是聚类的数量
虽然我们讨论的是无监督机器学习，但算法并不会神奇地将输入数据集聚集到一定数量的聚类中，我们需要指定我们想要的聚类个数。
基于领域知识，可以轻松指定所需的聚类。尽管如此，即使您不熟悉存在多少个聚类，也有一种技术可以确定如何选择K。
2. 从所有可用数据点的集合中，随机选择K个数据点(随机选择K行)并将其称为“聚类质心”(centroid)，即每类中所有点的中心（均值），这里是起始质心。
3. 聚类分配
遍历整个数据集，对于每个数据点x（i），将其分配给距其最近的一个聚类质心。
我们如何确定距离？
即需要进行某种距离计算。
我们可以使用所喜欢的任意距离度量方法，数据集上K-means算法的性能会受到所选距离计算方法的影响。
这里通过计算欧氏距离来做到这一点。
现在，我们将形成聚类。
我们将c（i）表示为最接近x（i）的聚类质心的索引。
4. 移动质心。
基于新分配到类的点更新质心，将聚类质心移动到另一个位置，该位置由它们所属的聚类中的点的平均值（即聚类内所有点的位置的平均值）确定。
5. 连续重复步骤3和4，直到质心不再改变。

我们看下伪代码：
获取数据 n 个 m 维的数据
随机生成 K 个 m 维的点
while(t)
	for(int i=0;i < n;i++)
		for(int j=0;j < k;j++)
			计算点 i 到类 j 的距离
    for(int i=0;i < k;i++)
        1. 找出所有属于自己这一类的所有数据点
        2. 把自己的坐标修改为这些数据点的中心点坐标
end

复杂度：
时间复杂度：O(tknm)，其中，t 为迭代次数，k 为簇的数目，n 为样本点数，m 为样本点维度。
空间复杂度：O(m(n+k))，其中，k 为簇的数目，m 为样本点维度，n 为样本点数。

优缺点:
1 优点
容易理解，聚类效果不错，虽然是局部最优，但往往局部最优就够了；
处理大数据集的时候，该算法可以保证较好的伸缩性；
当簇近似高斯分布的时候，效果非常不错；
算法复杂度低。
2 缺点
K 值需要人为设定，不同 K 值得到的结果不一样，K 值的选取对 K-means 影响很大，这也是 K-means 最大的缺点；
对初始的簇中心敏感，不同选取方式会得到不同结果；
对异常值敏感；
样本只能归为一类，不适合多分类任务；
不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类。

算法调优与改进：
针对 K-means 算法的缺点，我们可以有很多种调优方式：如数据预处理（去除异常点），合理选择 K 值，高维映射等。以下将简单介绍：
1. 数据预处理
K-means 的本质是基于欧式距离的数据划分算法，均值和方差大的维度将对数据的聚类产生决定性影响。
所以未做归一化处理和统一单位的数据是无法直接参与运算和比较的。
常见的数据预处理方式有：数据归一化，数据标准化。
此外，离群点或者噪声数据会对均值产生较大的影响，导致中心偏移，因此我们还需要对数据进行异常点检测。
2. 合理选择K-means中的K:
在不依赖于领域知识或可视化的情况下，选择K的方法是采用elbow method,即肘部法/手肘法。
我们用不同的K值运行K-means几次（即首先只有一个聚类质心，然后是两个，以此类推）。
对于每次运行，收集成本函数（每个点距离聚类质心距离之和）的输出（Y轴）并将其绘制在针对K（X轴）的图形上。
随着K增加，我们观察到成本函数减小了。
但过了一段时间后，在K=某个值以后，成本函数开始慢慢减少。
你会得到一个看起来像肘部的图表，根据经验，肘点对应于K的最佳值。
手肘法的缺点在于需要人工看不够自动化，所以我们又有了 Gap statistic 方法。
这个方法出自斯坦福大学的几个学者的论文：Estimating the number of clusters in a data set via the gap statistic。
Gap(K) = E(log Dk) - log Dk
其中，Dk为损失函数，这里E(log Dk)指的是log Dk的期望，这个数值通常通过蒙特卡洛模拟产生。
我们在样本所在的区域中按照均匀分布随机产生和原始样本数一样多的随机样本，并对这个随机样本做 K-Means，从而得到一个 Dk。
如此往复多次，通常 20 次，我们可以得到 20 个 Dk。对这 20 个数值求平均值，就得到了 E(log Dk) 的近似值。
最终可以计算 Gap Statisitc。
而 Gap statistic 取得最大值所对应的 K 就是最佳的 K。
Github 上一个项目叫 gap_statistic ，可以更方便的获取建议的类簇个数。
3. 采用核函数
基于欧式距离的 K-means 假设了各个数据簇的数据具有一样的的先验概率并呈现球形分布，但这种分布在实际生活中并不常见。
面对非凸的数据分布形状时我们可以引入核函数来优化，这时算法又称为核 K-means 算法，是核聚类方法的一种。
核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。
非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。
4. K-means++
我们知道初始值的选取对结果的影响很大，对初始值选择的改进是很重要的一部分。
在所有的改进算法中，K-means++ 最有名。
K-means++ 算法步骤如下所示：
1 随机选取一个中心点；
2 计算数据到之前 n 个聚类中心最远的距离 D(x)，并以一定概率选择新中心点 ai；
3 重复第二步。
简单地来说，就是 K-means++ 就是选择离已选中心点最远的点。
这也比较符合常理，聚类中心当然是互相离得越远越好。
但是这个算法的缺点在于，难以并行化。
所以 k-means II 改变取样策略，并非按照 k-means++ 那样每次遍历只取样一个样本，而是每次遍历取样 k 个，重复该取样过程 log(n) 次，
则得到 klog(n) 个样本点组成的集合，然后从这些点中选取 k 个。当然一般也不需要 log(n) 次取样，5 次即可。
5 ISODATA
ISODATA 的全称是迭代自组织数据分析法。
它解决了 K 的值需要预先人为地确定这一缺点。
当遇到高维度、海量的数据集时，人们往往很难准确地估计出 K 的大小。
ISODATA 就是针对这个问题进行了改进，它的思想也很直观：
当属于某个类别的样本数过少时把这个类别去除，当属于某个类别的样本数过多、分散程度较大时把这个类别分为两个子类别。

收敛证明
我们先来看一下 K-means 算法的步骤：
先随机选择初始节点，然后计算每个样本所属类别，然后通过类别再更新初始化节点。这个过程有没有想到 EM 算法 。
我们需要知道的是 K-means 聚类的迭代算法实际上是 EM 算法。
EM 算法解决的是在概率模型中含有无法观测的隐变量情况下的参数估计问题。
在 K-means 中的隐变量是每个样本所属类别。
K-means 算法迭代步骤中的 每次确认中心点以后重新进行标记 对应 EM 算法中的 E 步 求当前参数条件下的 Expectation 。
而 根据标记重新求中心点 对应 EM 算法中的 M 步 求似然函数最大化时（损失函数最小时）对应的参数。
EM 算法的缺点就是，容易陷入局部极小值，这也是 K-means 有时会得到局部最优解的原因。

注意：
K-means能处理比层次聚类更大的数据集。
另外，观测值不会永远被分到一类中。当我们提高整体解决方案时，聚类方案也会改动。
但是均值的使用意味着所有的变量必须是连续性的，并且这个方法很有可能被异常值影响。
它在非凸聚类（例如U型）情况下也会变得很差。
	
使用K-Means进行图像压缩：
是时候测试我们对K-Means的知识并将其应用于解决现实生活中的问题了。
我们将使用K-Means来执行图像压缩。
最左边的图像描绘了实际图像。中间图像描绘了一个压缩图像，但剩下一点点分辨率。最右边的图像描绘了高度压缩和低分辨率的图像。
压缩已经使用K-Means完成。
考虑你有一个大小为128 X 128 X 3的图像。
如果你矢量化图像，你将有一个大小为16384 X 3的numpy数组。
我们可以将这个图像视为数字数据的数据点，即我们必须忽略这个事实（这个数据代表一个图像）。
更具体地说，你可以将其视为任何其他大小为16384 X 3的numpy数组，其中示例的总数为m = 16384，并且要素的总数为n = 3。
如果我们将K-Means应用于此数据集，通过选择让我们说K = 16，我们将选择16个最重要的数据点（这些数据点只是集群质心）。
如果我们现在将数组视为一个图像，唯一的区别是，我们现在只使用4位（因为2⁴= 16 = K）来表示图像颜色。
新图像的总大小为：128 X 128 X 4 = 65536位。
但是，我们仍然需要一些存储开销。
我们仅使用4位来表示16种颜色。
但是，每种颜色（如果我们假设RGB格式）每个通道需要8位。
换句话说，R + G + B = 8 + 8 + 8 = 24位以表示一种颜色。
由于我们选择K = 16，对应16种颜色，我们额外需要24 X 16 = 384位。
因此，表示新图像的总位数：65536 + 384 = 65920位。
将其与原始图像进行比较，原始图像具有128 X 128像素，每个像素为24位颜色，结果是128 X 128 X 24 = 393216位。
显然，我们将图像压缩了6倍！结果惊人！
请记住，较高的K值意味着你不会大幅压缩图像，也就是说你将保留很多分辨率。
但是，如果要选择较小的K值，则图像将被高度压缩，因此分辨率较低。