本节书摘来自华章计算机《大数据架构和算法实现之路：电商系统的技术实战》一书中的第2章，第2.3节，作者 黄 申，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.3 聚类的效果评估
聚类最终的目标是将相似度很高的数据对象聚集到同一个群组，而将不够相似的数据对象分隔在不同的群组。不过，在实际应用中这些相似度标准导致的结果质量是否足够高呢？是否就一定符合用户的预期呢？最为直接的衡量方法是让用户试用并给出反馈，但是这需要在访谈上耗费大量的时间和人力。与此同时，聚类本身又缺乏黄金标准这样的答案集合。
“对啊，这样听起来好像聚类没有办法做离线的评估哦。”
“也不尽然，虽然很有挑战，但是我们还是有一些迂回的方法可以尝试，这里介绍一个最为常用的外部准则（External Criterion）法。”
其实所谓的外部准则法，就是借鉴分类问题中的黄金标准和评价指标，计算聚类结果和已有标准分类的吻合程度。其基本假设是：对于每个聚出来的群组，希望其组员来自一个分类，尽量“纯净”。举个例子，我们对水果案例中的10颗水果进行聚类，2个聚类算法在结束后分别得到下面的分组。
算法A
{1, 8, 10}, {4, 7}, {2, 3, 5, 6, 9}算法B
{1, 8}, {10}, {4, 7}, {2, 5, 6}, {3, 9}评估之前是无法知道它们的标签的，需要评估的时候，拿出分类的标签作为参考答案，我们可以得到：
算法A
{苹果a，西瓜b，西瓜d}，{甜橙a，西瓜a}，{苹果b，苹果c，甜橙b，甜橙c，西瓜c}
算法B
{苹果a，西瓜b}，{西瓜d}，{甜橙a，西瓜a}，{苹果b，甜橙b，甜橙c0}，{苹果c，西瓜c}
这样就能衡量每个群组的纯度。在此之前，首先简短介绍下熵（entropy）的概念：它是用来刻画给定集合的纯度的，如果一个集合里的元素全部都属于同一个分类，那么熵就为0，表示最纯净。如果元素分布在不同的分类里，那么熵就是大于0的值，而且随着分类的增多，元素的分布就越均匀，熵值也越大，表示混乱程度越高。其计算公式如下：
其中n表示集合中分类的数量，pi表示属于第i个分组的元素在集合中的占比。有了用于分类的训练数据，以及熵的定义，就可以计算每个聚类的纯度了。对于群组{苹果b，苹果c，甜橙b，甜橙c，西瓜c}而言，共5个对象，苹果有2个占0.4，甜橙有2个也占0.4，西瓜占剩余的0.2，其熵值约是1.52：
由于聚类结果有多个群组，最后进行加和平均：
那么算法A聚类的结果其最终整体的熵值为：
算法B聚类的结果其最终整体的熵值为：
不过，由于聚类并不会像分类那样指定类的个数，因此这种最基础的熵值评估存在一个明显的问题：它会偏向于聚出更多的群组，这样评测出的结论是算法B会优于算法A。但果真如此吗？西瓜b和d被算法A聚集了，但被算法B给拆分了。最极端的情况就是每个数据对象就是一个群组，这样全体的熵为0。但是这样并没有实际意义，因为没有产生任何的聚类效果。所以可将整体熵的计算修正为如下形式。
这里假设聚类的划分是合理的，Entropy (C)是基于这个划分计算的熵值，如果一个算法聚出来很多细小的群组，那么Entropy (C)一定很大，会进行一个惩罚。
这样一来，算法A的Entropy (C)计算就会变成如下形式：
算法B的Entropy (C)计算则变成如下形式：
除了标注数据，聚类还可以借鉴分类中的评价指标，例如准确率（Accuracy）和F值（F-Measure）。不过前提是需要将聚出的群组和某个标注的分类对应起来，最基本的方法是看组员大多数属于哪个分类，然后以这个分类作为答案，将群组作为“分类的预测”。这样问题就转化成为分类的离线评估了，具体请参见之前第1章有关分类的阐述。
