当前位置：首页 > Data clustering:50years beyond k-means翻译 - 图文
息长度（MML）准则（Wallace和Boulton，1968；Wallace和Freeman，1987）结合高斯混合模型（GMM）来估计K。他们的方法从大量的簇开始，然后朝着减少MML准则方向逐步融合已有的簇。一个使用最小描述长度（MDL）原理的相关方法被用在（Hansen和Yu，2001）来选择簇的数量。其他用在选择簇数目的准则有贝叶斯信息准则（BIC）和Akiake信息准则（AIC）。Gap统计（Tibshirani et al.,2001）是另一种普遍使用用来确定簇数量的方法。它的核心假设是当将数据划分成最佳数量的簇时，最后的划分结果对随机摄动有最大的回弹力。狄利克雷方法（DP）（Ferguson，1973；Rasmussen，2000）引入了簇数量的无参数先验。往往通过概率模型可以导出关于簇数量的后验分布，从这个分布可以计算出最有可能的簇数量。尽管我们有这些目标准则，要找到使得簇最有意义的K还是不容易的。图7a展示了由6种高斯分布成分混合产生的合成数据集。真正的簇标展示在图7e中。而这个高斯分布的混合体满足于分别展示在图7b-d图中的划分，分别有2、5、6种成分，每一种看上去都是合理的。
图7. 簇数目K的自动选择。图（a）表示由6个高斯分布混合产生的输入数据；图（b）-（d）各自表示适用于2、5、6个组件的高斯混合模型（GMM）；图（e）表示数据的真实标签。
3.4. 簇的有效性
聚类算法倾向于找到数据中的簇而不考虑是否有簇的存在。图8a展示了一个没有自然聚集的数据集；这里所有的点均匀的产生在一个单位正方形中。然而，图8b展示了当K=3时，K-means算法在这些数据上运行时有3个簇被识别了出来！簇的有效性指的是以一种定量而且客观的方式（Jain和Dubes，1988）评价聚类分析结果的正式程序。事实上，在将聚类算法应用于数据之前，用户就应该确定是否有聚集的趋势（Smith和Jain，1984）。
图8. 聚类有效性。图（a）表示没有自然聚集情况的数据集；图（b）表示K-means当K = 3时的划分结果。
聚类有效性指标可以基于3个不同的准则来定义：内部的、外部的和相对的（Jain和Dubes，1988）。基于内部准则的指标仅仅使用数据本身评估聚类算法应用的结构（聚类结果）和数据的合适性。基于相对的指标比较多种结构（比如说由不同的算法产生的结果）然后决定哪个结构在某种程度上更好。基于外部准则的指标通过对照聚类结构和先验信息来衡量，先验信息也就是“真实”的簇标（通常叫做地面真值）。一般来说，聚类结果是用外部准则来评价的，那么如果我们知道真实的簇标，我们又为什么要费功夫去聚类呢？聚类稳定性的概念（Lange et al.2004）非常有吸引力，因为可以用来衡量内部稳定性。聚类稳定性由输入数据在不同二次抽样的情况下聚类结果的差异量来衡量。不同的差异衡量可以获得不同的稳定性衡量。在（Lange et al.,2004）中，通过把从二次抽样聚类得到的簇标作为“真实”簇标，从数据的二次抽样中训练获得有监督的分类器。在测试子集上分类器的性能表明聚类算法的稳定性。在基于模型的算法（比如K-means中的基于形心表示法和混合高斯模型）中，从不同的二次抽样中得到的
模型之间的距离可以用来衡量稳定性（von Luxburg 和David，2005）。Shamir和Tishby（2008）将稳定性定义为聚类算法的泛化能力（从PAC贝叶斯意义上考虑）。他们认为因为很多算法可以被证明是渐进稳定的，因此关于样本数量的渐进稳定度在衡量聚类稳定性上更有用。交叉检验在评估有监督学习方法时广泛使用。通过用一个不同的有效性衡量的概念替代预测准确性的概念，交叉检验被用在无监督学习上。比如，给定从一个文件的数据中获得的混合模型，其它文件中数据的分布可以作为算法性能的一种显示并被用来决定簇的数目K。
图9. 15个二维模式的几个聚类结果：图（a）表示15个模式；图（b）表示15个模式的最小生成树；图（c）表示FORGY的聚类结果；图（d）表示ISODATA的聚类结果；图（e）表示WISH的聚类结果；图（f）表示CLUSTER的聚类结果；图（g）表示完全连接层次聚类的结果；图（h）表示Jarvis-Patrick聚类算法的聚类结果。（图取自Dubes and Jain（1976））
3.5. 比较聚类算法
即使对于相同的数据不同的聚类算法往往会产生完全不同的划分。在图9中，7种不同的算法被用来聚类15个二维点，其中FORGY、ISODATA、CLUSTER和WISH是最小化平方误差准则的基于划分的算法（他们都是基本K-means算法的变体）。剩下的3种算法，MST（最小生成树）可以看做单连接的基于层次的算法，而JP是一种最近邻算法。注意到一个基于层次的算法可以通过确定一个相似度阈值来产生一个划分。很明显，没有哪个聚类结果是优于哪一个的，但是有些却和另一些相似。
图10. 聚类算法的聚类结果。图（a）表示35种不同算法的层次聚类结果；图（b）表示通过将35种算法Sammon映射到2维空间，其中 的簇被突出用于可视化。其中，组别（4,29，31-35）中的算法是和K-means，谱聚类，高斯混合模型以及沃德连接算法相关的。组别（6,8-10）中的算法相当于是带有不同目标函数的CHAMELEON算法。
一个有趣的问题是如何确定不管数据如何变化，都能产生相似划分的算法。换句话说，我们能对聚类算法进行聚类吗？Jain et al.(2004)基于35种不同的算法对12个不同数据集的划分将他们聚类成5组。一对划分之间的相似度通过使用调整Rand指标（ARI）来衡量。35种聚类算法的一个基于层次的聚类展示在图10a中。相关的算法被聚类在一起这并不令人惊讶。为了得到算法间的相似度可视化结果，通过对35*35的相似度矩阵应用Sammon投影算法（Sammon，1969）得到35种算法嵌入在二维空间中的结果。图10b展示了所有的CHAMELEON变体被聚类到同一个簇中，这幅图表明依据相同聚类策略的聚类算法，尽管在相关参数或者相关目标函数上有小幅差异，却都能产生相似的聚类结果。在（Meila，2003），一个叫做信息变异的术语被提出来作为聚类空间中的另一种尺度。它通过交替聚类时，信息量的丢失或获得来衡量两个聚类算法之间的相似度。
聚类算法也可以基于目标函数在理论层面上进行比较。为了进行这样的比较，聚类方法和聚类算法之间的差异应该被明确（Jain and Dubes，1988）。一个聚类方法是用来解决聚类问题的一个总体策略。而聚类算法仅仅是方法的一个例子。比如，最小化平方误差是一个聚类方法，它涉及很多像K-means这样应用该方法的聚类算法。即使在不同的聚类方法之间也可以看到一些等价的关系。
本文作者：...共分享92篇相关文档
