什么是聚类？
本次分享聚类中最常用的方法，K-means
所谓聚类，就是将对象，按照某种属性进行划分，使得同种类别之间有较高相似性，不同类别有较大区分。
在机器学习领域，属于无监督模型，像之前的线性回归，逻辑回归，决策树均是有监督学习，聚类是无监督学习，只要根据有没有目标作为参照学习就可以区分。
所以聚类算法，若要达到我们想要的目的，特征的选择及相似性的度量标准，将是十分重要，也是十分考究功底的。
常用距离公式
我们用距离公式衡量相似性，常用的距离公式包括：闵科夫斯基距离(Minkowski distance)、余弦距离(Cosine Similarity)、马氏距离(Mahalanobis Distance)、KL散度(KL divergence)
1.闵科夫斯基距离(Minkowski distance)
当p=1时，闵科夫斯基距离即曼哈顿距离(Manhattan distance)
当p=2时，闵科夫斯基距离即欧式距离(Euclidean distance)
当p→∞时，闵科夫斯基距离即切比雪夫距离(Chebyshev Distance)
2.余弦距离(Cosine Similarity)
利用闵可夫斯基度量对高维数据进行聚类通常是无效的，因为样本之间的距离随着维数的增加而增加。余弦距离测量两个矢量之间的夹角，而不是两个矢量之间的幅值差。它适用于高维数据聚类时相似度测量。
3.马氏距离(Mahalanobis Distance)
马氏距离，即数据的协方差距离，于欧式距离不同的是它考虑到各属性之间的联系，如考虑性别信息时会带来一条关于身高的信息，因为二者有一定的关联度，而且独立于测量尺度。
当其中Σ是数据集x,y的协方差矩阵。马氏距离在非奇异变换下是不变的，可用来检测异常值需要注意的是：马氏距离是建立在总体样本的基础上的，这一点可以从上述协方差矩阵的解释中可以得出，也就是说，如果拿同样的两个样本，放入两个不同的总体中，最后计算得出的两个样本间的马氏距离通常是不相同的，除非这两个总体的协方差矩阵碰巧相同；其次要求总体样本的协方差矩阵存在。
4.KL散度(KL divergence)
KL散度又称为相对熵，它是描述对随机变量X的两个概率分布PP和QQ差别的非对称性度量，它不满足距离基本性质中的对称性和直递性。特别的，在信息论中，DKL(P(x)||Q(x))DKL(P(x)||Q(x))表示当概率分布Q(x)Q(x)来拟合真实分布P(x)P(x)时，产生的信息损耗。
连续形式如下：
什么是K-means？
不说那些复杂的概念，看下面的步骤，按着步骤，更新聚类中心，等聚类稳定之后，结果既所求：
步骤如下：
1.确定类k的数量；
2.随机选择k个点，作为初始聚类中心；
3.计算每个样本到k个点分别的距离；
4.将每个样本分给最近的聚类中心点；
5.将样本分好后，重新计算每个类的中心点；
6.重复2~5，直到样本聚类结果没有变化，则停止聚类；
K-means优点
1.是解决聚类问题的一种经典算法，简单、快速
2.对处理大数据集，该算法保持可伸缩性和高效性
3.当簇接近高斯分布时，它的效果较好。
K-means缺点
在簇的平均值可被定义的情况下才能使用，可能不适用于某些应用；
在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适；
在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果(可能会陷入死循环)；
该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的；
若簇中含有异常点，将导致均值偏离严重(即:对噪声和孤立点数据敏感)；
不适用于发现非凸形状的簇或者大小差别很大的簇。
如何选择最佳K值？
聚类有一个评估方法最为常用，叫轮廓系数结合了凝聚度和分离度，其计算步骤如下：
对于第 i 个对象，计算它到所属簇中所有其他对象的平均距离，记 ai (体现凝聚度)
对于第 i 个对象和不包含该对象的任意簇，计算该对象到给定簇中所有对象的平均距离，记 bi (体现分离度)
第 i 个对象的轮廓系数为 si = (bi-ai)/max(ai, bi)
从上面可以看出，轮廓系数取值为[-1, 1]，其值越大越好，且当值为负时，表明 ai
将每个样本的轮廓系数求和取平均，即可获得对应k的轮廓系数，选择轮廓系数最高的k为最佳K值
如何优化k-means？
1. 确定类k的数量；
2.随机选择k个点，作为初始聚类中心；(选择概率较大的k个点可以提高迭代速度，后续有空专题分享)
3.计算每个样本到k个点分别的距离(选择合适的距离度量标准)；
4.将每个样本分给最近的聚类中心点(一般用各个点的均值作为类中心点，但是可以通过加权平均，众数等不同的方法获得不一样的聚类中心点)；
5.将样本分好后，重新计算每个类的中心点；
6.重复2~5，直到样本聚类结果没有变化，则停止聚类；