0x00 内容
学习内容：无监督聚类算法K-Means
k-means：模型原理、收敛过程、超参数的选择
0x01聚类
聚类分析是在数据中发现数据对象之间的关系，将数据进行分组，组内的相似性越大，组间的差别越大，则聚类效果越好。
不同的簇类型：聚类旨在发现有用的对象簇，在现实中我们用到很多的簇的类型，使用不同的簇类型划分数据的结果是不同的。
基于原型的：簇是对象的集合，其中每个对象到定义该簇的原型的距离比其他簇的原型距离更近，如(b)所示的原型即为中心点，在一个簇中的数据到其中心点比到另一个簇的中心点更近。这是一种常见的基于中心的簇，最常用的K-Means就是这样的一种簇类型。 这样的簇趋向于球形。
基于密度的：簇是对象的密度区域，(d)所示的是基于密度的簇，当簇不规则或相互盘绕，并且有早上和离群点事，常常使用基于密度的簇定义。
关于更多的簇介绍参考《数据挖掘导论》。
基本的聚类分析算法
1. K均值：基于原型的、划分的距离技术，它试图发现用户指定个数(K)的簇。
2. 凝聚的层次距离：思想是开始时，每个点都作为一个单点簇，然后，重复的合并两个最靠近的簇，直到尝试单个、包含所有点的簇。
3. DBSCAN:一种基于密度的划分距离的算法，簇的个数有算法自动的确定，低密度中的点被视为噪声而忽略，因此其不产生完全聚类。
1.1 距离量度
不同的距离量度会对距离的结果产生影响，常见的距离量度如下所示：
1.2 K-Means算法
1.2.1 K均值算法：
优点：易于实现
缺点：可能收敛于局部最小值，在大规模数据收敛慢
算法思想：
选择K个点作为初始质心
repeat
将每个点指派到最近的质心，形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数
这里的“重新计算每个簇的质心”，是根据目标函数来计算的，因此在开始时要考虑距离度量和目标函数。
考虑欧几里得距离的数据，使用误差平方和（Sum of the Squared Error,SSE）作为聚类的目标函数，两次运行K均值产生的两个不同的簇集，使用SSE最小的那个。
k表示k个聚类中心，ci表示第几个中心，dist表示的是欧几里得距离。
这里有一个问题就是为什么，我们更新质心是让所有的点的平均值，这里就是SSE所决定的。
1.2.2 K-Means算法的缺陷
k均值算法非常简单且使用广泛，但是其有主要的两个缺陷：
1. K值需要预先给定，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后找出Cost Function最小时所对应的K值，这个值往往能较好的描述有多少个簇类。
2. K-Means算法对初始选取的聚类中心点是敏感的，不同的随机种子点得到的聚类结果完全不同
3. K均值算法并不是很所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇，银冠指定足够大的簇的个数是他通常可以发现纯子簇。
4. 对离群点的数据进行聚类时，K均值也有问题，这种情况下，离群点检测和删除有很大的帮助。
下面对初始质心的选择进行讨论：
拙劣的初始质心
当初始质心是随机的进行初始化的时候，K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕，可能只能得到局部的最优解，而无法得到全局的最优解。
随机初始化的局限
多次运行，每次使用一组不同的随机初始质心，然后选择一个具有最小的SSE的簇集。该策略非常的简单，但是效果可能不是很好，这取决于数据集合寻找的簇的个数。
关于更多，参考《数据挖掘导论》
1.2.3 K-Means优化算法
为了克服K-Means算法收敛于局部最小值的问题，提出了一种二分K-均值(bisecting K-means)
bisecting K-means
将所有的点看成是一个簇
当簇小于数目k时
对于每一个簇
计算总误差
在给定的簇上进行K-均值聚类,k值为2 计算将该簇划分成两个簇后总误差
选择是的误差最小的那个簇进行划分
Mini Batch k-Means
在原始的K-means算法中，每一次的划分所有的样本都要参与运算，如果数据量非常大的话，这个时间是非常高的，因此有了一种分批处理的改进算法。
使用Mini Batch（分批处理）的方法对数据点之间的距离进行计算。
Mini Batch的好处：不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。n 由于计算样本量少，所以会相应的减少运行时间n 但另一方面抽样也必然会带来准确度的下降。
0x02 聚类和分类的区别
聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集成为一个“簇”。通过这样的划分，每个簇可能对应于一些潜在的概念（也就是类别）；需说明的是，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇对应的概念语义由使用者来把握和命名。
聚类是无监督的学习算法，分类是有监督的学习算法。所谓有监督就是有已知标签的训练集（也就是说提前知道训练集里的数据属于哪个类别），机器学习算法在训练集上学习到相应的参数，构建模型，然后应用到测试集上。而聚类算法是没有标签的，聚类的时候，需要实现的目标只是把相似的东西聚到一起。
性能度量
聚类的目的是把相似的样本聚到一起，而将不相似的样本分开，类似于“物以类聚”，很直观的想法是同一个簇中的相似度要尽可能高，而簇与簇之间的相似度要尽可能的低。
性能度量大概可分为两类： 一是外部指标， 二是内部指标 。
外部指标：将聚类结果和某个“参考模型”进行比较。
内部指标：不利用任何参考模型，直接考察聚类结果。
K-Means的原理
对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大
K-Means与KNN
初学者会很容易就把K-Means和KNN搞混，其实两者的差别还是很大的。
K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。
当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。
K-Means的优点与缺点
优点：
简单，易于理解和实现；收敛快，一般仅需5-10次迭代即可，高效
缺点：
1，对K值得选取把握不同对结果有很大的不同
2，对于初始点的选取敏感，不同的随机初始点得到的聚类结果可能完全不同
3，对于不是凸的数据集比较难收敛
4，对噪点过于敏感，因为算法是根据基于均值的
5，结果不一定是全局最优，只能保证局部最优
6，对球形簇的分组效果较好，对非球型簇、不同尺寸、不同密度的簇分组效果不好。
0xFF 小结
K-means算法简单理解，易于实现（局部最优），却会有对初始点、噪声点敏感等问题；还容易和监督学习的分类算法KNN混淆。
参考阅读：
1.《深入理解K-Means聚类算法》
2.《K-Means》
