图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这样应用该方法的聚类算法。即使在不同的聚类方法之间也可以看到一些等价的关系。
比如，Dhillon et al.（2004）表明谱聚类和核K-means是等价的，在选择谱聚类的要点时，其中目标函数的选择和核K-means是相同的。（Ding et al.,2005）展示了聚类非负矩阵因子分解和核K-means算法的等价性。所有这些方法都和相似度矩阵特征向量分析直接相关。
以上这些讨论说明了聚类的一个很重要的事实：没有最好的聚类算法。每一种聚类算法都或明确或含蓄的给数据一种结构。当模型和数据之间有一个好的匹配时，就能得到一个好的划分。因为数据的结构事先是不知道的，在处理手上的聚类任务时，就需要通过尝试使用竞争的和多样的方法来最终决定合适的算法。这种没有最好的聚类算法的思想和不可能理论部分的相符，表明没有一个聚类算法同时满足数据聚类的所有基本原则。 3.5. 聚类算法的容许性分析
Fisher和vanNess（1971）正式以比较聚类算法和为选择聚类步骤提供指导为目标分析了聚类算法。他们定义了一些聚类算法的容许性准则。这些准则测试聚类算法关于不改变本质结构的数据改变的敏感性。如果一个聚类满足准则A，那么这个聚类叫做A容许。有些准则包括凸状点、簇均衡、簇冗余和单调。下面简要描述他们：
(a)凸状：一个聚类算法聚类结果的簇的凸壳并不相交则称该聚类算法是是凸状容许的。
(b)簇均衡：如果聚类算法的结果使一些簇复制任意次数情况下，簇的边界都不改变，那么就称这个聚类算法为簇均衡容许。
(c)簇冗余：如果从聚类算法结果中移除其中一个簇的数据，再运行算法，得到的K-1个簇和未再运行时的K-1个簇是一样的，那么就称该聚类算法为冗余容许的。
(d)单调：如果当相似度矩阵元素单调改变时，聚类算法结果不发生改变，那么就称该聚类算法是单调容许的。
Fisher和Van Ness证明不能设计出满足一定容许准则的算法。比如，如果一个算法是单调容许的，那么它不能是基于层次的聚类算法。
Kleinberg（2002）指出了一个相似的问题，并定义了三个准则：
(a)标度不变性：任意标度的相似度矩阵不改变聚类结果。 (b)丰富性：聚类算法能获得数据的所有可能划分。
(c)一致性：收缩簇内距离和拉伸簇间距离，聚类结果并不改变。
Kleinberg也提供了和（Fisher与VanNess，1971）相似的结论，表明设计出同时满足所有这些特性的算法是不可能的。因此，他论文的题目是《关于聚类的不可能理论》。（Kleinberg，2002）进一步讨论揭示可以通过将“满足”准则的条件放宽到“近似满足”准则来设计聚类算法。尽管在这里定义的设定在很大程度上是合理的，但他们绝不是唯一可能的设定。因此聚类算法评价的结果必须根据实际情况去解读（Ben-David和Ackerman，2008）。
4. 数据聚类的趋势
信息爆炸不仅仅是创造了大量的数据，同时也创造了包括有结构的和无结构的多样化的数据。无结构的数据是指一个并不遵从一定格式的对象集。比如，图像、文本、声频和视频等。另一方面，有结构的数据是指数据对象之间有重要的语义关系。大部分聚类方法忽略用于聚类的对象的结构，并对有结构和无结构的数据采用基于特征向量的表示法。基于向量特征表示法的传统数据划分观点并不能提供充足的框架。比如，当使用点集（Lowe，2004）、消费者购买记录（Guha et al.,2000）、通过问卷和排名获得的数据（Critchlow，1985）、社交网络（Wasserman和Faust，1994）以及数据流（Guha et al.,2003b）来代表对象的情形。很多模型和算法被开发用于处理大量的异构数据。数据聚类中最近的一些趋势简要的总结如下： 4.1. 聚类集成
有监督学习的集成方法应用的成功激发了无监督学习集成方法的发展（Fred和Jain，2002）。主要思想是，通过对同一数据的多样考察生成同一数据的多样划分（聚类集成）。即使当簇并不是很紧凑而且分离的很好时，也能通过综合划分的结果来获得一个较好的数据划分。Fred和Jain采区这种方式通过K-means进行划分的集成。这个集成通过改变不同的K值和使用随机的簇初始化得到。
通过使用共生矩阵，这些划分被综合起来产生了一个不错的簇的分离结果。一个聚类集成的例子展示在图11中，一个“2—螺旋 ”数据集被用来证明聚类集成的有效性。K-means在不同的簇数量K值下运行了N次。一对点之间新的相似度被定义为在N次K-means运行过程中两个点同时出现在一个簇中的次数。基于新的对间相似度进行聚类获得最终的聚类结果。Strehl和Ghosh（2003）提出了集中应用于集成多重划分的概率模型。更新的关于聚类集成的工作可以在（Hore et al.,2009a）中找到。
图11. 聚类集成。通过多次运行K-means，基于簇中点的“共现”学习对间相似度。这种相似度可以被用来找到任意形状的簇。
有很多方法用于产生聚类集成和综合划分结果。比如多重数据划分可以通过以下方法产生：（i）应用不同的聚类算法。（ii）用同一个聚类算法但是带有不同的参数值或者初始化。（iii）结合不同的数据表示法（特征空间）和聚类算法。结合不同的划分提供的信息，这一证据的积累步骤可以看做是数据点之间相似性测度的学习。 4.2. 半监督聚类
聚类问题本身是一个病态问题。它的目标是只基于固有的信息将数据划分成不知道簇数目的簇。聚类问题数据驱动的特性使得设计出准确找到给定数据的簇变得非常困难。除了n*d维模式矩阵或者n*n维相似度矩阵之外任何可用的外部或者边带信息都对找到一个好的数据的划分非常有用。使用这样的边带信息的聚
类算法被叫做运行在半监督模式（Chapelle et al.,2006)的聚类算法。这里有两个开放式的问题：（i）应该如何定义边带信息。（ii）在实践中如何获得边带信息。确定边带信息最常见的方法是以对间约束形式。一个“必须连接”约束，确定受约束的某对点属于同一个簇。另一方面，一个“不能连接”约束，确定受约束的某对点不属于同一簇。通常假设这些约束是由领域的专家提供的。从数据自动导出约束的相关工作现在还很有限。有些人尝试通过邻域本体论和其它外部源引出聚类算法的约束包括利用词网本体论、基因本体论和维基百科等来指导聚类求解。然而这些大多是整体特征的约束而不是对于特定实体的约束（Hotho et al.,2003;Liu et al.,2004;Banerjee et al.,2007b）。其它包含边带信息的方法包括（i）“播种”，为了更好的聚类，使用大量无标识的数据中含有一些有标识数据的数据集（Basu et al.,2002）。（ii）允许加强或弱化连接的方法（Law et al.,2005;Figueiredo et al.,2006）。
图12是半监督学习在图像分割中应用的一个例子（Lange et al.,2005）。图12a表示用于分割（聚类）的纹理图像。除了图像本身，也提供了一系列由用户确定的关于像素点的对间约束。图12b是在没有约束使用情况下得到的聚类结果，而图12c表示的是在使用约束的情况下聚类结果的改善情况。在两种情况下，簇的数目都假定已知（K=5）。
图12. 半监督学习。图（a）表示由5种均匀质地区域组成的输入图像；像素点之间必须连接（蓝色实线）和不能连接（红色断线）约束已被确定。图（b）表示在无约束下的5簇解（分割）。图（c）表示在有10%数据点包含有对间约束时得到的改进的聚类结果（有5个簇）。
大部分半监督聚类方法（Bar-Hillel et al.,2003;Basu et al.,2004;Chapelle et