1700535623
百面机器学习：算法工程师带你去面试 [:1700532196]
1700535624
百面机器学习：算法工程师带你去面试 04 聚类算法的评估
1700535625
1700535626
1700535627
1700535628
场景描述
1700535629
1700535630
人具有很强的归纳思考能力，善于从一大堆碎片化的事实或者数据中寻找普遍规律，并得到具有逻辑性的结论。以用户观看视频的行为为例，可以存在多种直观的归纳方式，比如从喜欢观看内容的角度，可以分为动画片、偶像剧、科幻片等；从常使用的设备角度，可以分为台式电脑、手机、平板便携式设备、电视等；从使用时间段上看，有傍晚、中午、每天、只在周末观看的用户，等等。对所有用户进行有效的分组对于理解用户并推荐给用户合适的内容是很重要的。通常这类问题没有观测数据的标签或者分组信息，需要通过算法模型来寻求数据内在的结构和模式。
1700535631
1700535632
知识点
1700535633
1700535634
数据簇，聚类算法评估指标
1700535635
1700535636
问题 以聚类问题为例，假设没有外部标签数据，如何评估两个聚类算法的优劣？
1700535637
1700535638
难度：★★★☆☆
1700535639
1700535640
分析与解答
1700535641
1700535642
场景描述中的例子就是一个典型的聚类问题，从中可以看出，数据的聚类依赖于实际需求，同时也依赖于数据的特征度量以及评估数据相似性的方法。相比于监督学习，非监督学习通常没有标注数据，模型、算法的设计直接影响最终的输出和模型的性能。为了评估不同聚类算法的性能优劣，我们需要了解常见的数据簇的特点。
1700535643
1700535644
1700535645
1700535646
以中心定义的数据簇：这类数据集合倾向于球形分布，通常中心被定义为质心，即此数据簇中所有点的平均值。集合中的数据到中心的距离相比到其他簇中心的距离更近。
1700535647
1700535648
以密度定义的数据簇：这类数据集合呈现和周围数据簇明显不同的密度，或稠密或稀疏。当数据簇不规则或互相盘绕，并且有噪声和离群点时，常常使用基于密度的簇定义。
1700535649
1700535650
以连通定义的数据簇：这类数据集合中的数据点和数据点之间有连接关系，整个数据簇表现为图结构。该定义对不规则形状或者缠绕的数据簇有效。
1700535651
1700535652
以概念定义的数据簇：这类数据集合中的所有数据点具有某种共同性质。
1700535653
1700535654
由于数据以及需求的多样性，没有一种算法能够适用于所有的数据类型、数据簇或应用场景，似乎每种情况都可能需要一种不同的评估方法或度量标准。例如，K均值聚类可以用误差平方和来评估，但是基于密度的数据簇可能不是球形，误差平方和则会失效。在许多情况下，判断聚类算法结果的好坏强烈依赖于主观解释。尽管如此，聚类算法的评估还是必需的，它是聚类分析中十分重要的部分之一。
1700535655
1700535656
聚类评估的任务是估计在数据集上进行聚类的可行性，以及聚类方法产生结果的质量。这一过程又分为三个子任务。
1700535657
1700535658
（1）估计聚类趋势。
1700535659
1700535660
这一步骤是检测数据分布中是否存在非随机的簇结构。如果数据是基本随机的，那么聚类的结果也是毫无意义的。我们可以观察聚类误差是否随聚类类别数量的增加而单调变化，如果数据是基本随机的，即不存在非随机簇结构，那么聚类误差随聚类类别数量增加而变化的幅度应该较不显著，并且也找不到一个合适的K对应数据的真实簇数。
1700535661
1700535662
另外，我们也可以应用霍普金斯统计量（Hopkins Statistic）来判断数据在空间上的随机性[7]。首先，从所有样本中随机找n个点，记为p1,p2,…,pn，对其中的每一个点pi，都在样本空间中找到一个离它最近的点并计算它们之间的距离xi，从而得到距离向量x1,x2,…,xn；然后，从样本的可能取值范围内随机生成n个点，记为q1,q2,…,qn，对每个随机生成的点，找到一个离它最近的样本点并计算它们之间的距离，得到y1,y2,…,yn。霍普金斯统计量H可以表示为：
1700535663
1700535664
1700535665
．
1700535666
1700535667
（5.15）
1700535668
1700535669
1700535670
1700535671
1700535672
如果样本接近随机分布，那么和的取值应该比较接近，即H的值接近于0.5；如果聚类趋势明显，则随机生成的样本点距离应该远大于实际样本点的距离，即，H的值接近于1。