Question

K-Means（一）K值的选择

Answer 1

算法1.1 基本K均值算法

    1：选择K个点作为初始质心

    2：repeat

    3：    将每一个点指派到最近的质心，形成K个簇

    4：    重新计算每个簇的质心

    5：until    质心不发生变化

关于K值的选择

        Tan et al.的《数据挖掘导论》给了许多簇评估的方式，包括非监督的、监督的和相对的。这里只介绍两种非监督的。其中重点介绍第一种，关于凝聚度和分离度的方法。

        （1）使用凝聚度和分离度

        凝聚度是衡量簇内点的临近程度，而分离度是指簇与簇之间的临近程度。衡量总体的有效性可以用凝聚度、分离度或者是两者的某种组合。

        关于两者的计算，分为基于图的观点和基于原型（有质心）的观点。都不难理解。一个是基于点本身，另一个基于点与质心。

        ①基于图的观点

        凝聚度可以定义为用连接簇内点的邻近度图中边的加权和。

        分离度可以用从一个簇到另一个簇的点的边的加权和来表示。

        ②基于原型的观点

        凝聚度可以定义为关于簇原型（质心或中心）的邻近度的和。

        分离度可以用两个簇的临近性度量。就是两个簇质心之间的距离。

        ③关于凝聚度与分离度之间的关系

        聚类的目标就是使组内的相似性越大，组间的差别越大。而这两个指标可以用凝聚度和分离度来表示。也就是说，使凝聚度越小，分离度越大。于是我想到可以把两者结合起来对聚类效果进行评价。然而，在《数据挖掘导论》写道：

        是否可以这样理解，总TSS不变，减少SSE就是增加SSB，这就是聚类的目标。即，我们只需要关注两者其一即可。问题是，SSE随着K值的增加，是会减少的。可以看到，随着K越来越大，甚至趋向于m（数据集总的样本数），SSE这时等于0。所以单单通过这个值评价聚类效果我认为是不合理的。在实际应用中还是需要结合domain knowledge选择K。

        Tan在书中写道可以通过观察“拐点”来选择最优K值。但是像我这张图是很难找到一个拐点的。

        ④使用轮廓系数

        轮廓系数结合了凝聚度和分离度。轮廓系数的定义不难理解，就是一种度量凝聚度和分离度的方式。计算个体的轮廓系数由三步组成。

        Definition 轮廓系数

        ⅰ 对于第i个对象，计算它到簇中所有其他对象的平均距离，记为ai

        ⅱ 对于第i个对象和不包含该对象的任意簇，计算该对象到给定簇中所有对象的平均距离。关于所有的簇，找出最小值，记作bi

         ⅲ 对于第i个对象，轮廓系数Si=（bi - ai） /  max（ai, bi）

        轮廓系数的值在-1与1之间，我们不希望出现负值。因为出现负值表示点到簇内点的平均距离大ai于点到其他簇的最小平均距离。这在直觉上也是不对的，因为我们想要簇内距离最小。

        我们可以简单地取簇中点的轮廓系数的平均值，计算簇的平均轮廓系数。通过计算所有点的平均轮廓系数，可以得到聚类优良性的总度量。

        轮廓系数越趋近于1，说明聚类效果越好。因为此时ai越趋近于0。

        类似于绘制SSE，我们也可以绘制K与轮廓系数的图，通过观察“拐点”选择最优K值。值得注意的是，轮廓系数是越高越好，而SSE是越低越好，两种拐点的类型在图上有微小差别。

总结：

        本小节主要介绍了基本K-Means算法和K值的选择。接下来会介绍K-Means的优化算法。

参考文献：

[1]Pang-Ning Tan, Michael Steinbach, Vipin Kumar. 数据挖掘导论 [M]. 人民邮电出版社, 2011.