机器学习基础-K 均值聚类

什么是聚类？

本次分享聚类中最常用的方法，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<bi，样本被分配到错误的簇中，聚类结果不可接受。对于接近0的结果，则表明聚类结果有重叠的情况。

将每个样本的轮廓系数求和取平均，即可获得对应k的轮廓系数，选择轮廓系数最高的k为最佳K值

如何优化k-means？

1. 确定类k的数量；

2.随机选择k个点，作为初始聚类中心；（选择概率较大的k个点可以提高迭代速度，后续有空专题分享）

3.计算每个样本到k个点分别的距离（选择合适的距离度量标准）；

4.将每个样本分给最近的聚类中心点（一般用各个点的均值作为类中心点，但是可以通过加权平均，众数等不同的方法获得不一样的聚类中心点）；

5.将样本分好后，重新计算每个类的中心点；

6.重复2~5，直到样本聚类结果没有变化，则停止聚类；