al.,2006;Lu和Leen，2007）都通过修正当前聚类算法的目标函数来包含对间约束。我们想要的是能够有一个半监督聚类方法在提高已有聚类算法性能的同时又不改变它。BoostCluster（Liu et al.,2007）采用了这样的观点并遵循一个推动框架，通过使用对间约束去提高任何给定聚类算法的性能。它通过产生新的数据表示法（转换n*n的相似度矩阵）迭代的修正聚类算法的输入，这样的话在满足对间约束的同时也保持了聚类输出的完整性。图13展示了基于在UCI库（Blake，1998）中的有4000个256维数据的手写数字数据库的BoostCluster的性能。BoostCluster可以提高3种用于聚类的常见算法，K-means、单连接、谱分析，当数据带有对间约束时的表现。这里只有“必须连接”约束而且簇的数目假定已知（K=10）。
图13. 随着对间约束增加BoostCluster（使用标准化的交互信息（NMI）来衡量）的性能变化。三个折现图相当于提高了性能的K-means、单连接（SLINK）和谱聚类（SPEC）。
4.3. 大规模聚类
大规模数据聚类处理关于由数以千计特征表示的有数以百万计数据点的数据集的聚类问题的挑战。表1展示了一些大规模数据聚类实际应用的例子。下面
我们回顾一下大规模数据聚类在基于内容的图像检索中的应用。
表1. 大规模数据聚类应用的例子
基于内容的图像检索（CBIR）的目标是根据给定的查询图像检索出看上去相似的图像。虽然大概过去的15年一直在研究这个问题，目前还只有有限的成果。大部分关于CBIR的早期工作都是通过计算基于特征的颜色、形状和纹理来定义图像之间的相似度。2008年一个关于CBIR的调查，总结了用于CBIR的以时间为序的不同方法（Datta et al.,2008）。最近的用于CBIR的方法使用基于特征的关键点。比如，SIFT（Lowe，2004）描述符可以被用来表示图像（见图14）。然而，一旦图像数据库扩大（大约1000万），并假设计算一对图像的匹配时间需要10ms，一个线性搜索大约需要消耗大学30h来响应一个查询指令。这显然是不可接受的。
图14.使用SIFT关键点表示的三个纹身。图（a）表示一对相似图像间有370个一致的关键点；图（b）表示一对不同图像间有64个一致的关键点。绿色的线表示图像间的一致关键点（Lee et al.,2008）。
另一方面，文本检索的应用要快很多。在Google大概只需要十分之一秒就能检索100亿的文档。一个图像检索的新方法是将问题转化为文本检索问题。所有图像的关键点，首先被聚类成大量的簇（数量上往往比图的关键点少的多）。这些被叫做视觉单词。这样一幅图就可以被视觉单词的柱状图所表示。也就是图的关键点数量就在于每个字或每个簇中。通过用视觉字的柱状图表示每一幅图，我们就将图的搜索问题转化为文本的检索问题，然后开发用于高效图像检索的文本搜索引擎。量化关键点的主要挑战是用于聚类的对象数量。对于有1000幅图的图像集，其中平均每幅图有1000个关键点，以及5000个目标视觉字，需要将10万个对象聚类成5000个簇。
能够有效处理大规模数据集的聚类算法已经开发了很多了。大部分这些研究可以被分成四类：
(a)有效最近邻（NN）搜索：在任何聚类算法中的一个基本操作是确定每个数据点的簇身份，而这需要NN搜索。用于有效NN搜索的算法主要是基于树的（比如kd树（Moore，1998；Muja和Lowe，2009））和基于随机投影的（比如位置敏感散列（Buhler，2001））。
(b)数据概括：它的目标是通过先将大数据集概括为相对小的子集，然后应
用聚类算法对概括后的数据集进行聚类来提高聚类的效率。相关算法包括BIRCH（Zhang et al.,1996）,divide-and-conquer（Steinbach et al.,2000）,核心集K-means（Har-peled和Mazumdar，2004），以及粗化方法（Karypis和Kumar，1995）。
(c)分布式计算：这一类方法（Dhillon和Modha，1999）将数据聚类算法的每个步骤分成许多可以独立计算的程序。这些独立的计算程序将在不同的处理器中平行的执行用以减少整体的计算时间。
(d)增量聚类：这类算法，比如（Bradley et al.,1998）设计对数据进行单次扫描用以提高数据聚类的效率。这和大多数聚类算法形成对比，因为它们在识别数据中心之前需要多次扫描数据点。COBWEB是一个受欢迎的基于层次的聚类算法，它对可用的数据进行单次扫描并递增的将数据安排到分类树中（Fisher，1987）。
(e)基于抽样的方法：像CURE（Guha et al.,1998;Kollios et al.,2003）这样的算法,有选择的对大数据集进行二次抽样，并对较小的数据集进行聚类，最后再将结果转化到大的数据集。 4.4. 多方式聚类
被用来聚类的对象或者实体往往是相关的不同成分的一个组合。比如，一个文档是由字、标题、作者和引文等组成。虽然在聚类之前对象的各个成分都可以转化到一个合并的特征向量，但这不是对象的自然表示法，而且很有可能导致糟糕的聚类表现。
共同聚类（Hartigan，1972；Mirkin，1996）试图对数据实体和特征同时进行聚类（或者说对n*d维模式矩阵的行和列），也即明确特征子集，有了特征子集，根据一定的评估准则的聚类结果就会有意义。这个问题第一次研究是在Hartigan（1972）写的叫做《直接聚类》中。这也被叫做二维聚类（Cheng et al.,2000）、双聚类、对聚类或者双模聚类。这个概念也和子空间聚类有关，所有的簇在共同的子空间中是确定的。共同聚类在生物信息领域，尤其是基因聚类中最受欢迎，而且也被成功的应用在文本聚类中（Slonim和Tishby，2000；Dhillon et al.,2003）。
共同聚类框架被拓展到多方式聚类（Bekkerman et al.,2005），通过聚类对象
集的同时也聚类对象集中的不同成分。这个问题实际上要有挑战性的多，因为不同成分对之间可能有不同的相似度关系。另外，有些关系可能涉及不只两种成分。Banerjee et al.(2007a)提出了一个适用于一类关于被称为Bregman分歧的损失函数的多方式聚类方案族。 4.5. 异构数据
在传统的模式识别设定中，一个特征向量由一个对象的不同特性的衡量组成。对几种类型的数据来说这种对象的表示法并不是一种自然表示法。异构数据是指那些不能由固定长度的特征向量自然表示的对象数据。
排名数据：考虑不同的人对n部电影排名所生成的数据集，n个对象中只有一些被排名了。任务是聚类排名相似的用户，而且要明确每一组的代表性排名（Mallows，1957；Critchlow，1985；Busse et al.,2007）。
动态数据：动态数据和静态数据相反，比如博客、网页等会随着时间进程而发生改变。当数据修改之后，聚类结果必须相应的更新。数据流就是一种动态数据，它本质上是瞬态的，不能存储在硬盘上。例子包括路由器接收到的网络包、股票市场、连锁店和信用卡的交易数据流。数据流的特征包括它们的高容量、潜在无界规模、顺序存取以及动态演化。这给传统的聚类算法提出了额外的要求，要求算法能够快速处理和概括大量连续抵达的数据。它还要求算法有适应数据分布改变的能力，侦测新生簇、分辨新生簇和数据中的噪声以及融合旧簇和抛弃失效簇的能力。因为期望是单次扫描算法（Guha et al.,2003b）,上述这些要求就使得数据流聚类成为一个重大的挑战。因为要求高速处理，很多数据流聚类方法（Guha et al.,2003a;Aggarwal et al.,2004;Cao et al.2006;Hore et al.,2009b）都是像K-means、K-medoid、模糊c-means或基于密度聚类的拓展，然后用于数据流环境的设定。
图数据：有些对象，比如说化合物、蛋白质结构等可以非常自然的用图来表示。很多最初的关于图聚类的工作专注于抽象出图的特征，从而可以使用已有的聚类算法来处理图的特征向量（Tsuda和Kudo，2006）。特征的提取可以是像频繁子图、最短路径、循环和基于树这样基于模式的。伴随着核学习的兴起，有越来越多的工作专注于更适合基于图的数据的核函数的开发。一种确定图之间相