面向实体解析的无监督聚类方法综述

高广尚

GAO Guangshang1，2

1.桂林理工大学 现代企业管理研究中心，广西 桂林 541004

2.桂林理工大学 商学院，广西 桂林 541004

1.Research Center for Modern Enterprise Management,Guilin University of Technology,Guilin,Guangxi 541004,China

2.School of Management,Guilin University of Technology,Guilin,Guangxi 541004,China

1　引言

大数据环境下，数据既有多样性（variety）[1]，又有演化性[2]。具体到数据集而言，多样性体现在，若干不同形式的记录（或称为数据对象）描述现实世界同一实体。由于这些记录的某些对应属性的值之间存在细微差别，因而它们被称为近似重复记录（approximate duplicate record）[3-4]。而演化性体现在，属性值会以相对较快的速度产生细微变化。从聚类角度来看，实体解析（Entity Resolution，ER）定义为：通过合适的相似性函数以尽可能快地将描述现实世界同一实体的所有近似重复记录聚类到同一个聚簇中（或划分到同一个组中），使得每个聚簇表示不同的实体[5-9]。目前从整体上来看，实体解析分为两大类：成对实体解析（Pairwise ER）和基于聚类的实体解析（Clustering-based ER）[8]。其中，成对实体解析需要对数据集中所有记录进行两两比较，涉及的时间复杂度为Ο(n2)，而基于聚类的实体解析则无需进行两两比较，因此涉及的时间复杂度可能会远小于Ο(n2)。

然而在实际应用中，聚类又分为监督聚类和无监督聚类两种[10-12]，前者需要训练数据，后者却不需要训练数据，并且不依赖领域知识，不需要事先设定聚簇的数量。无监督聚类本质上就是将根据某些标准被判定为彼此相似的记录聚类到同一个聚簇的过程[13-15]，最后使得位于同一聚簇内的所有记录彼此间高度相似（同质性），而位于不同聚簇内的所有记录彼此间高度不相似（整齐分隔性（neatly separation））[12，16]。无监督聚类结果的好坏取决于精心设计的算法是否能最小化聚类过程中可能存在的两种不正确匹配情形：false-positives（错误肯定）和false-negatives（错误否定），前者表示被算法认为匹配的两条记录实际上却不与同一实体相对应，后者表示两条记录实际上对应于同一实体但却被算法认为不匹配[17]。鉴于此，本文主要从无监督聚类角度，梳理和总结一些重要的引导无监督聚类过程的启发式方法，并分析现有研究中取得的成果及存在的不足，最后提出未来的研究重点。

2　基于特定类型的无监督聚类方法

针对特定类型的分析有助于引导无监督聚类过程。现有研究中基于特定类型的无监督聚类方法主要分为4种：基于优先队列的无监督聚类、基于图分割的无监督聚类、基于中心结点的无监督聚类和基于紧凑集的无监督聚类。

2.1　基于优先队列的无监督聚类

基于优先队列的聚类思路：首先，使用记录的若干属性产生排序键（sorting key），继而得到排序键值（sorting key values），然后，将数据集中记录按排序键值升序（或降序）进行排序，这让那些最有可能相似的记录相邻地排列在一起；最后，依次取出排序后的记录并与优先队列中的元素进行比较（从优先级高的元素开始），以判定当前记录是分配到与其比较的元素所指定的聚簇中，还是分配到新增的聚簇中（此时，当前记录还需要加入到优先队列中作为新的元素，同时其优先级设定为最高）[18-19]。具体过程如图1所示，其中聚簇C1中的点表示对应的记录，以下类似。

基于优先队列的聚类具有以下优点：（1）在速度上，实验结果表明，它能减少近75%的记录对比较次数，因为每条记录仅与少量的元素进行比较即可，无需与整个数据集进行比较[20-21]。（2）在精度上，由于融合了近邻排序思想（sorted neighborhood），它的匹配精度与基本近邻排序方法（basic sorted neighborhood）相当。（3）在比较过程中，它能很好地自适应通过排序键值所发现的记录块（如图1内表格中的虚线框所示）。其存在的不足：（1）聚类过程在很大程度上依赖于产生的排序键值，如果记录中充当或部分充当排序键值的属性值出现异常（例如不一致、过时、冗余和不精确等），那么该记录将很少有机会获得成功的匹配。（2）队列中的元素通常并不能代表它所对应的聚簇本身，元素本质上是一个在比较过程中动态产生的由若干记录组成的集合，因此在将元素与其他记录进行比较时，就可能无法正确算出它们之间的相似性值，从而容易出现错误肯定或错误否定的情形。

2.2　基于图分割的无监督聚类

事实上，记录之间的两两比较结果可表示成一个相似性图形（similarity graph），其中结点表示记录，边表示其所连接的两条记录被算法判定为相似，边上的权值表示记录间的相似性值，如图2所示。很显然，图2中的相似性图形包含两个子图，一个由结点r1～r4组成（S1），另一个由结点r5～r6组成（S2）。基于图分割的聚类思路：首先，预先设定每个子图中允许最多包含的结点数量，或设定边的权值不能少于某个阈值；之后，依据这些特征持续分割子图，直到满足要求；最后，分割后的每个子图表示一个新的聚簇[13，22]。

图1　基于优先队列的聚类

图2　基于比较结果构成的相似性图形

以子图S1为例，如果设定子图中允许包含的最大结点数量为nc=2，那么该子图上具有最小权值（5.05）的边将首先被删除（假设从最小权值开始），于是子图被分割成两个新的子图。由于此时两个新的子图各自所包含的结点数量均未大于2，因此分割将不再持续，这时它们表示两个不同的聚簇，一个由结点r1和r2组成，另一个由结点r3和r4组成。

同样以子图S1为例，如果设定子图中边的权值不能少于阈值tc=5.25，那么结点r2和r3之间的边将最先被删除，之后结点r1和r2之间的边也将被删除，最后由于r3和r4之间边上的权值为5.25。因此删除过程将不再持续，最后子图被分割成3个子图，表示3个不同的聚簇，一个由结点r1组成，一个由结点r2组成，另一个由结点r3和r4组成。

基于图分割的聚类具有以下优点：分割过程容易实现；不需要复杂的计算。其存在的不足：本应属于同一子图的结点可能会因阈值选取不当而被划分到不同的子图中，从而导致真正的匹配被遗漏，错误的匹配被认可。

2.3　基于中心结点的无监督聚类

为在相似性图形上进行聚类分析，除采用分割思想外，还可以采用中心结点思想。基于中心结点的聚类思路：首先，将子图中所有边按其权值降序进行排序；然后，将最靠前的边(ri,rj)上的结点ri指定为聚簇的中心结点；最后，将所有出现在排序列表中的边(ri,rj)上的结点rj分配到该聚簇中，而不是任何其他聚簇[23]。

同样以子图S1为例，起初，所有边按其权值降序排序后形成的列表为：(r3,r4)、(r1,r2)和(r2,r3)，分别对应权值5.25、5.20和5.05。首先，考虑最靠前的边(r3,r4)，如果结点r3被标记为聚簇的中心结点，那么结点r4也属于该聚簇，因为它们由同一条边相连。随后考虑边(r1,r2)，很显然，此时结点r1和r2均没有被标记为聚簇的中心结点或属于某个聚簇，因此结点r1应被标记为另一个聚簇的中心结点，同理，结点r2属于该聚簇。最后考虑边(r2,r3)，由于其中两个结点均已被分配给某些聚簇，因此这条边将不再作进一步考虑。最后，通过采用中心结点思想，可在该子图上产生两个聚簇，一个由结点r1和r2组成，另一个由结点r3和r4组成。

在实际应用中，从一对结点中选择哪个结点作为聚簇的中心结点，有时可能会显著影响最终的聚类结果。为解决这一问题，MERGE-CENTER方法[23]认为，当两个聚簇的中心结点非常相似时，可将两个聚簇合并为一个聚簇。

基于中心结点的聚类方法可能会产生比基于图分割的聚类方法更多的聚簇，因为它只将那些与聚簇中心的记录相似的记录放入同一个聚簇。

2.4　基于紧凑集的无监督聚类

在相似性图形上进行聚类分析有一定的局限性，因为相似性图形结构本身由用于判定记录对为匹配或非匹配的阈值决定，它是一个用于所有被比较的记录对的全局参数。为此，有专家认为可利用紧凑集（Compact Set，CS）特征来进行聚类分析[13，24]，它定义表示同一实体的记录彼此更相似，可为每个聚簇设置不同的阈值，以半径p表示。基于紧凑集的聚类思路：利用记录对之间计算出的所有相似性值，而不仅仅是那些被判定为匹配的记录对之间的相似性值，来对数据集进行聚类，同时利用那些彼此相似的记录，以及位于它们周围的记录的数量来引导聚类过程[13]，最后使得形成的聚簇是一个具有稀疏邻居的紧凑集。这种方法类似于基于密度的聚类方法[15]。

紧凑集内部的记录对之间的距离小于任何非紧凑集内的记录对之间的距离，表示为：ri,rj∈CS：dist(ri,rj)＜dist(ri,rk)，∀rk∉CS 。此外，记录 ri的邻居集定义为：N(ri)=p·nn(ri)，其中，nn(ri)是记录ri到其最近邻居的距离，p决定以ri为中心的圆的半径大小。如果ri的邻居集N(ri)中的记录数量低于某一常数阈值，那么ri的邻居就被定义为稀疏的。如图3显示了一个紧凑集，包含结点r1、r2和r3，以及作为边的权值的距离（等于1减去相似性值），其中r1的邻居集N(r1)=p·nn(r1)=0.1×p=0.1p，假定它包含结点r4和r5。

图3　基于紧凑集的聚类

基于紧凑集的聚类具有以下优点：大小受限的聚簇有助于高效计算；能避免产生过大的聚簇。其存在的不足：聚簇的形成取决于记录的邻近记录的数量和密度，而不是一个全局阈值。

3　基于经典算法的无监督聚类方法

基于特定类型的无监督聚类具有一定的局限性：算法可扩展性不强，算法理论基础不完备和算法性能不稳定等；相比之下，基于经典算法的无监督聚类却具有诸多优越性：理论基础坚实，算法实现简单，可扩展性较好和可处理高维数据等。现有研究中基于经典算法的无监督聚类方法主要分为3种：基于凝聚层次聚类的无监督聚类（Agglomerative Hierarchical Clustering，AHC）、基于相关性聚类的无监督聚类（Correlation Clustering，CC），以及基于局部敏感哈希的无监督聚类（Locality-Sensitive Hashing，LSH）。

3.1　基于凝聚层次聚类的无监督聚类

凝聚层次聚类的基本思想：在给定待聚类的N个记录对象和N×N的距离矩阵的情况下，从每个对象作为个体聚簇开始，每一步合并两个最接近的聚簇[25-26]。凝聚层次聚类涉及两个重要参数：相似性度量方法和阈值，前者通过欧式距离来判断两个聚簇之间的相似度，后者用作聚类迭代过程的终止条件，即当最近的两个聚簇的距离大于阈值时，则认为迭代可以终止。图4（a）显示了迭代聚类过程，最终返回C1、C3和r6（单独作为一个聚簇）3个聚簇（假定满足终止条件）；图4（b）相应地显示了这一自底向上的迭代聚类过程，同时也说明了凝聚层次聚类具有“层次”特性。

凝聚层次聚类的关键是如何计算聚簇之间的距离，现有研究主要采用4种方法：单链接方法、全链接方法、平均链接方法和权威记录方法[26]。单链接方法又称最小值方法，聚簇之间的距离等于聚簇内成员间的最短距离。这种方法容易造成“Chaining”效应，即两个实际上相离较远的聚簇因为聚簇内个别距离较近的点而合并，使得相离较远的点因为若干相离较近的“中介点”而被链接起来，并且这种效应可能会逐渐扩大。全链接方法又称最大值方法，聚簇之间的距离等于聚簇内成员间的最远距离，与单链接方法相反，全链接方法中相离较近的聚簇可能因为其中个别相离较远的点而无法合并。平均链接方法是单链接方法和全链接方法的折中策略。权威记录方法需要首先为每个聚簇构造权威记录，之后任意两个聚簇之间的相似度就定义为二者的权威记录之间的相似度。一般情况下，选择哪种方法与具体的应用相关。

基于凝聚层次聚类的无监督聚类具有以下优点：（1）定义距离和规则的相似度较容易，并且限制少；（2）可以发现聚簇的层次关系；（3）可以聚类成其他形状。其存在的不足：（1）计算复杂度较高，尤其在处理大量数据时，因为每次都要计算多个聚簇内所有数据点的两两距离；（2）奇异值也能对聚类过程产生很大影响，甚至对聚类的结果起到决定性作用；（3）可能会出现链状的聚类结果。

3.2　基于相关性聚类的无监督聚类

相关性聚类的基本思想：在带权的相似性图形上进行划分（聚类），使得每个划分尽可能地与结点间的相似性保持一致，最后划分出的最佳聚类结果满足“最大化一致性权值”原则或“最小化不一致性权值”原则[27-28]。其中，一致性权值定义为：聚簇内部标记为“+”边的权值和聚簇之间标记为“-”边的权值的总和。同理，不一致性权值定义为：聚簇内部标记为“-”边的权值和聚簇之间标记为“+”边的权值的总和。简单来说，相关性聚类就是在不需要预先指定聚簇数量的情况下，尽可能地将所有记录聚类成具有最佳数量的聚簇。

图4　基于凝聚层次聚类的聚类

进行相关性聚类实质上是求解整数线性规划问题（Integer Linear Programming，ILP）。假设 erirj∈{0,1}表示两条记录ri、rj是否位于同一个聚簇（其中1表示位于同一个聚簇）∈[0,1]表示将记录ri、rj聚类到一起的代价，∈[0,1]表示将记录ri、rj放置到两个不同聚簇的代价。于是，相关性聚类的目标就是在保证满足传递性性质的约束式子∀ri,rj,rk,erirj+erirk+erjrk≠2成立的条件下，尽量最小化目标函数的值。图5显示了一个聚类后的结果，其中发生错误的是三条标记为“＋”的边，它们的总权值为5。

图5　基于相关性聚类的聚类

基于相关性聚类的无监督聚类具有以下优点：不需要选择距离阈值；不是孤立考虑记录对之间（聚簇之间）的相似性值，而是综合考虑多个待识别结点之间的相似性值；能够有效消除噪声对聚类结果产生的影响。其存在的不足：聚类过程本质上是一个NP-hard问题[29]，即在费时的聚类过程后可能无法得到满意的聚类结果。鉴于此，现有研究提出了许多近似的贪婪方法以对相关性聚类进行改进，例如 BEST/FIRST/VOTE[30]、PIVOT[29]和Local Search[31-32]等方法。

3.3　基于局部敏感哈希的无监督聚类

局部敏感哈希的基本思想：在空间转换过程中保持数据之间的相似性，对于原始空间中相似的两个数据点，经过相同的哈希函数映射后，这两个数据点在映射后的空间中依然相似，即位于同一个桶中（聚簇）；反之，如果两个数据点在原始空间中不相似，那么映射后的两个数据点依然不相似，即位于不同的桶中[33-34]。简单来说，如果原来的数据相似，那么哈希以后的数据同样保持相似性。

事实上，为对数据集中记录进行有效聚类，局部敏感哈希使用哈希函数簇来产生多个键（Keys），以便相似的记录能被划分到同一聚簇中[35]。值得指出的是，哈希函数的值域一般都是有限的，而被哈希的数据却是先前无法预知的，可能会大大超过值域，这会导致多余一个的数据点不可避免地拥有相同的哈希值，从而使得位于同一个桶中的数据点可能彼此并不全部相似。图6中存在一个发生冲突的桶，即桶中的数据点彼此并不相似。

图6　基于局部敏感哈希的聚类

基于局部敏感哈希的聚类具有以下优点：（1）能够克服邻居驱动的数据聚类过程中的有限可扩展性[10]；（2）能够有效处理高维空间中的最近邻搜索（nearest neighbor）[36]；（3）更新哈希索引结构的代价较小；（4）查找最近邻的时间复杂度为Ο(1)，具有极高的性能。其存在的不足：（1）需要大量存储空间；（2）不能100%保证找到最近邻，因为相似数据可能分布在多个桶中。

4　基于经典算法改进的无监督增量聚类方法

随着大数据时代的到来和不断发展，数据集愈发具有动态性，即数据更新速度更快，同时数据量也更大[2，37-38]。这时，上述具有接近平方级计算复杂性等局限性的无监督聚类方法，将难以满足动态数据集上的增量聚类需求。鉴于此，考虑到经典算法具有的诸多优越性，以及动态数据集本身所具有的特征，现有研究通过对经典算法进行改进以满足动态数据集上的增量聚类需求：基于凝聚层次聚类的无监督增量聚类、基于相关性聚类的无监督增量聚类，以及基于局部敏感哈希的无监督增量聚类。

4.1　基于凝聚层次聚类的无监督增量聚类

针对动态环境中新出现数据的聚类效率偏低问题，Widyantoro等[39]提出了增量凝聚层次聚类算法（Incremental Hierarchical Clustering，IHC），旨在构建一个能同时满足同质性（homogeneity）与单调性（monotonicity）的概念层次结构。这让满足同质性的聚簇具有相似密度的对象集，满足单调性的聚簇具有其聚簇的密度总是高于其父辈聚簇的特征。通过自底向上的方式，算法能将新出现数据放置于层次结构中，之后仅对受其影响的区域进行一系列层次结构调整。通过在不同领域上的实验结果表明，算法能产生高质量的聚簇层次结构，能有效减少计算时间，同时对数据的出现顺序不敏感。Li等[40]提出了另一增量聚类算法（Herarchical Incremental RELational clustering，HIREL），包含Incremental-Divisive和Agglomerative两个阶段，其中Incremental-Divisive阶段负责自底向上递归地更新叶子结点，直到根结点，Agglomerative阶段负责改善聚簇质量。由于算法仅需要对数据集进行一遍扫描，并能利用代表对象（representative objects）和平衡查找树（balanced search tree）来减少聚类过程中的距离计算量，因此它能显著加快学习过程并改善聚类效率。Jin等[41]提出了一种适用于单链接层次聚类的增量分布式算法IncDiSC，它克服了统一框架下的数据依赖性和算法复杂性挑战。该算法不仅可以扩展到大型数据集，还可以合并新数据的增量累积。

4.2　基于相关性聚类的无监督增量聚类

针对在线数据的在线聚类问题，Claire等[42]提出了基于相关性聚类的增量相关性聚类算法（incremental correlation clustering）。该算法可执行4个基本操作：为到来的结点v产生一个新的聚簇{v}；将结点v加入到现有的聚簇中；合并任何原先存在的聚簇；分裂原先存在的聚簇。尽管算法最终输出的结果可能与真实聚类情形不一致，因为分类器本身可能存在错误，或可能根本不存在真实的最优聚簇数量信息，但作者结合实例证明了该算法实施增量聚类时的有效性和合理性，即能最小化不一致性值或最大化一致性值。

为解决动态数据集上的聚类问题，Anja等[38]研究了融合相关性聚类的增量聚类算法，并在此基础上提出了一个端到端框架end-to-end framework。它能在数据集中不断出现插入、删除和更新数据情形时，仅针对这些相关数据去增量更新数据集中的匹配结果，从而可避免每次对整个数据集重新运用聚类分析。此外，考虑到数据集中的每次动态更新可能会影响较大范围的记录集，因此作者继而提出了一个贪婪算法来合并或划分与每次更新相连的聚簇，并能在这些聚簇之间有效移动记录。值得说明的是，由于作者综合考虑了3种数据操作情形，因此提出的算法不仅能轻松实现之前研究的合并、分裂等操作，而且能充分利用每次更新中的新证据来修正原先聚类结果中存在的匹配错误，并且无损聚类质量。

4.3　基于局部敏感哈希的无监督增量聚类

针对大型文本序列数据集上新出现记录的聚类问题，Costa等[43]提出了基于哈希索引结构的最近邻分类（nearest-neighbor classi fi cation）方法，它通过索引结构映射任何记录到一个索引键（indexing keys）集合中，并将语法上高度相似的记录分配到相同的桶中。索引键由键产生程序分两步产生：首先，识别记录之间相似的记录分量，尽管其中可能存在一定程度上的语法异构性；然后，通过另一个最小哈希函数将先前产生的记录的中间表示与它们的索引键关联起来。

事实上，在两步之间可能会使用多个最小哈希函数，一些基于最小独立分布（min-wise independent permutations）[44-45]的局部敏感哈希函数，它们被分层结合在一起，以反映记录及其分量之间的语法差异性，并使在线匹配更有效。重要的是，使用多个最小哈希函数有两个目的：降低错误肯定和错误否定；直接控制用于索引任何记录的键的数量，从而为整体存储空间的紧凑性提供必要保证。值得说明的是，尽管进行增量聚类时需要依赖一个合适的基于哈希的索引结构，但该方法不需要完全扫描原始数据集，也不需要使用代价高昂的相似性度量。

5　基于演化分析的无监督增量聚类方法

动态数据集本质上是一个演化的数据集，其中数据不断频繁产生或更新[17，46-47]。这种演化特性形成了一种新的数据形态——数据流。现有针对数据流的聚类研究相当于是在动态数据集上进行增量聚类研究[48]。为实现数据流上的聚类，现有研究主要从两个方面展开工作：基于数据流分析的无监督增量聚类和基于规则演化分析的无监督增量聚类。

5.1　基于数据流分析的无监督增量聚类

针对给定记录流的聚类问题，Charikar等[49]在分析一些贪婪算法的基础上，提出了新的确定性随机增量聚类算法（Deterministic and Randomized Incremental Clustering Algorithms），它的目标是在新记录出现时维护具有较小直径的聚簇。作者通过与先前算法进行对比分析证明了提出的算法具有较好的优越性。Aggarwal等[50]认为针对大量流数据的传统聚类算法大部分效率偏低，例如一些针对数据流的“单遍扫描（One-Pass）”聚类算法，尽管解决了聚类过程中的可扩展性问题，但它们通常无视数据演化问题，而且没有解决以下两个问题：（1）当数据随时间快速演化时，形成聚簇的质量较差；（2）数据流聚类算法需要更多功能以发现和探索数据流中不同部分上的聚簇。鉴于此，提出了CluStream算法，它将数据流看成是一个随时间推移而不断变化的过程，并能在这个演化环境中不同时间区间上进行聚类，这与其他试图一次性聚类整个数据流的算法相比有着明显的区别。实验结果证实CluStream算法具有较高的聚簇质量、效率，而且可扩展性也强。

为在聚类数据流时保证正确性，Whang等[37]定义了通用增量性质（General Incremental），并据此提出了满足通用增量性质的增量数据算法（Incremental Data Algorithm）。由于算法能充分利用之前得到的中间聚类结果，并能一次解析数据流中的一条记录，因此在聚类时有较好的效率和正确性。Can等[51]将操作数据集时涉及的一系列数据看成是动态数据流，并认为数据集上之前形成的聚簇需要据此进行定期更新。在明确研究背景的基础上，作者提出了一个针对动态数据的增量聚类算法(C2ICM)，它通过“种子（Seed）”思想来仅对与动态数据相关的聚簇进行聚类。由于聚类过程整体上不显著影响其他聚簇结构，因此它能提升聚类效率。

此外，为解决数据集中新数据或新特征（记录属性）不断出现时的聚类问题，Omar等[52]提出了“Incremetnal F-Swoosh”算法，它起初利用一些哈希表和集合来保存初始运行过程后的相应值，之后就能在新的运行过程中避免进行一些不必要的记录比较，尤其是在它们之间不匹配情形已知晓的情况下。事实上，通过这种方式，能避免已在初始运行过程中进行过的任何属性值比较。

5.2　基于规则演化分析的无监督增量聚类

随着实际应用中数据被更好地理解，用于聚类的匹配规则也应作相应演化，以便据此得到的聚类结果更能真实反映数据（流）的聚类形态。为实现面向数据流的基于规则演化分析的聚类，Whang等[53]提出了规则演化框架（Rule Evolution Framework），它利用物化的（Materialization）结果来减少冗余工作量，并引入两个性质（规则单调性、上下文无关性）来使用于聚类的匹配规则更为有效。其中，匹配规则是判定两条记录是否相似的基本逻辑，例如，匹配规则“如果两条记录的“名称”属性值相似，那么这两条记录将匹配”。

随着更多记录不断出现（同时也被更好地理解），如果一成不变地使用上述匹配规则去对它们进行聚类，那么势必会产生不正确的聚类结果，同时效率也不佳。但如果将匹配规则演化为“如果两条记录的“名称”属性值相似，并且“邮政编码”属性值也相似，那么这两条记录将匹配”，这样就可从旧匹配规则下产生的聚类结果中，容易得到新匹配规则所产生的聚类结果，从而减少不必要的比较次数。值得指出，新匹配规则应比旧匹配规则更严格。具体过程如图7所示。

图7　基于规则演化分析的聚类

此外，考虑到规则演化的重要性，Whang等[37]在已有研究的基础上又另外提出了两个性质：通用增量性、顺序无关性，这让满足这些性质的聚类过程在速度上和精度上都得到了一定的保障。

6　结论

实体解析在数据分析、信息集成和知识库构建等领域起着至关重要的作用，并且为大数据环境下的智能推理提供了极为重要的数据质量保障。无监督聚类因将解析记录看成是一个不需要利用训练数据的聚簇构建过程，而成为实体解析研究的一种重要方法。本文通过对以往研究中一些比较有代表性的无监督聚类算法、无监督增量聚类算法的思路进行梳理和总结，以便进一步揭示它们的策略与技巧，最终有助于从更深一层意义上认识、完善和发展实体解析。如表1，对面向实体解析的无监督聚类方法在逻辑思路、性能特点、适用范围和局限性这四方面进行了详细比较。

展望未来，面向实体解析的无监督聚类方法在准确性、可扩展性和解析效率等方面仍存在一些开放性的研究方向：

（1）深层挖掘记录之间的链接关系。当前的聚类算法在聚类记录时更多地考虑独立的记录对（independent pairwise）之间的相似性值，而不是记录组内部的协作关系[54-55]，因而导致较为准确的记录之间的属性相似性值未被包含进聚类决策过程中，从而较易出现记录漏配情形。因此，研究如何推理出协作组以充分挖掘记录之间的链接关系，并降低推理过程中的计算复杂性是无监督聚类方法面临的主要挑战之一。

（2）动态调整记录之间的聚类规则。在大多数实体解析场景中，用于实体解析的聚类规则会随着时间的变化而演化，因为应用程序本身会发展演化，而且用于比较记录的专业知识也会逐步得到改善等[37，53]。因此，在记录之间相似关系的复杂性提高的情况下，研究如何利用深厚的领域知识来动态构造聚类规则以让实体解析过程仍保持较高的聚类性能，是无监督聚类方法面临的主要挑战之一。

（3）有效增强记录之间的实时聚类。随着信息技术，尤其是传感器、通信、计算机和互联网技术的迅猛发展和广泛应用，人们获取数据的手段越来越多，速度也大大加快，与此同时，数据的层次和尺度更为精细，其揭示的自然现象和社会现象也更为深刻。因此，一些实体解析应用在要求解析结果准确可靠的同时，更要求解析过程必须在规定时间内或近乎实时完成[56-57]。例如，金融信贷领域数据实时分析、互联网领域数据实时监测、公共安全领域数据实时查询和工农业领域数据实时预测等。

表1　面向实体解析的无监督聚类方法详细比较

参考文献：

[1]Naimi A I，Westreich D J.Big data：A revolution that will transform how we live，work，and think[J].Mathematics&Computer Education，2013，47（17）：181-183.

[2]孟小峰，杜治娟.大数据融合研究：问题与挑战[J].计算机研究与发展，2016，53（2）：231-246.

[3]朱灿，曹健.实体解析技术综述与展望[J].计算机科学，2015，42（3）：8-12.

[4]Dong X L，Srivastava D.Big data integration[C]//Proceedings of IEEE International Conference on Data Engineering，2013：1245-1248.

[5]Brizan D G，Tansel A U.A survey of entity resolution and record linkage methodologies[J].Communications of the IIMA，2006，6（3）：41-50.

[6]Benjelloun O，Garcia-Molina H，Menestrina D，et al.Swoosh：A generic approach to entity resolution[J].The International Journal on Very Large Data Bases，2009，18（1）：255-276.

[7]Mccallum A，Nigam K，Ungar L H.Efficient clustering of high-dimensional data sets with application to reference matching[C]//Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2000：169-178.

[8]Getoor L，Machanavajjhala A.Entity resolution：Theory，practice&open challenges[J].Proceedings of the VLDB Endowment，2012，5（12）：2018-2019.

[9]孙琛琛，申德荣，寇月，等.面向实体识别的聚类算法[J].软件学报，2016，27（9）：2303-2319.

[10]Costa G，Cuzzocrea A，Manco G，et al.Data de-duplication：A review[M]//Learning Structure and Schemas from Documents.Berlin：Springer，2011：385-412.

[11]Enr Quez J，Dom Nguez-mayo F，Escalona M，et al.Entity reconciliation in big data sources：A systematic mapping study[J].Expert Systems with Applications，2017，80：14-27.

[12]庄严，李国良，冯建华.知识库实体对齐技术综述[J].计算机研究与发展，2016，53（1）：165-192.

[13]Naumann F，Herschel M.An introduction to duplicate detection[J].Synthesis Lectures on Data Management，2010，2（1）：1-87.

[14]高广尚.面向数据演化的实体解析述评[J].情报学报，2016，35（3）：326-336.

[15]Han J，Kamber M.The Morgan Kaufmann series in data management systems，data mining：Concepts and techniques[J].Antimicrobial Agents&Chemotherapy，2015，59（3）：1435-1440.

[16]Grabmeier J，Rudolph A.Techniques of cluster algorithms in data mining[J].Data Mining and Knowledge Discovery，2002，6（4）：303-360.

[17]Batini C，Scannapieco M.Data and information quality：Dimensions，principles and techniques[M].Berlin：Springer，2016.

[18]Monge A E.Matching algorithms within a duplicate detection system[J].IEEE Data Eng Bull，2000，23（4）：14-20.

[19]Adumanusarpong K，Kingsley Arthur J.A review of data cleansing concepts achievable goals and limitations[J].International Journal of Computer Applications，2014，76（7）：19-22.

[20]Hern M A.The merge/purge problem for large databases[C]//Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data，San Jose，California，USA，1995：127-138.

[21]Dez M A H，Stolfo S J.Real-world data is dirty：Data cleansing and the merge/purge problem[J].Data Min Knowl Discov，1998，2（1）：9-37.

[22]Christen P.Data matching：Concepts and techniques for record linkage，entity resolution，and duplicate detection[M].Berlin：Springer Science&Business Media，2012.

[23]Hassanzadeh O，Miller R J.Creating probabilistic databases from duplicated data[J].The International Journal on Very Large Data Bases，2009，18（5）：1141-1166.

[24]Chaudhuri S，Ganti V，Motwani R.Robust identification of fuzzy duplicates[C]//Proceedings 21st International Conference on Data Engineering，2005：865-876.

[25]Jain A K，Murty M N，Flynn P J.Data clustering：A review[J].ACM Computing Surveys（CSUR），1999，31（3）：264-323.

[26]Doan A H，Halevy A，Ives Z.Principles of data integration[M].San Francisco：Morgan Kaufmann Publishers Inc，2012：459-485.

[27]Bansal N，Blum A，Chawla S.Correlation clustering[J].Machine Learning，2004，56（1/3）：89-113.

[28]Ahn K J，Cormode G，Guha S，et al.Correlation clustering in data streams[C]//Proceedings of the International Conference on Machine Learning，2015：2237-2246.

[29]Ailon N，Charikar M，Newman A.Aggregating inconsistent information：Ranking and clustering[J].Journal of the ACM（JACM），2008，55（5）：1-27.

[30]Elsner M，Charniak E.You talking to me?A corpus and algorithm for conversation disentanglement[C]//Proceedings of Meeting of ACL，2008：834-842.

[31]Gionis A，Mannila H，Tsaparas P.Clustering aggregation[J].ACM Transactions on Knowledge Discovery from Data（TKDD），2007，1（1）：4.

[32]Goder A，Filkov V.Consensus clustering algorithms：Comparison and refinement[C]//Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments（ALENEX），2008：109-117.

[33]Verroios V，Garcia-molina H.Top-K entity resolution with adaptive locality-sensitive hashing[R].Stanford University，2017.

[34]Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing[C]//Proceedings of Conference on Very Large Data Bases，1999：518-529.

[35]Kim H S，Lee D.HARRA：Fast iterative hashed record linkage for large-scale data collections[C]//Proceedings of the 13th International Conference on Extending Database Technology，2010：525-536.

[36]Har-peled S，Indyk P，Motwani R.Approximate nearest neighbor：Towards removing the curse of dimensionality[J].Theory of Computing，2012，8（1）：321-350.

[37]Whang S E，Garcia-Molina H.Incremental entity resolution on rules and data[J].The VLDB Journal，2014，23（1）：77-102.

[38]Gruenheid A，Dong X L，Srivastava D.Incremental record linkage[J].Proceedings of the VLDB Endowment，2014，7（9）：697-708.

[39]Widyantoro D H，Ioerger T R，Yen J.An incremental approach to building a cluster hierarchy[C]//Proceedings of IEEE International Conference on Data Mining，2002：705-708.

[40]Li T，Anand S S.Hirel：An incremental clustering algorithm for relational datasets[C]//Proceedings of the 8th IEEE International Conference on Data Mining，2008：887-892.

[41]Jin C，Chen Z，Hendrix W，et al.Incremental，distributed single-linkage hierarchical clustering algorithm using mapreduce[C]//Proceedings of Symposium on High Performance Computing，2015：83-92.

[42]Mathieu C，Sankur O，Schudy W.Online correlation clustering[J].Computational Statistics，2010，21（2）：211-229.

[43]Costa G，Manco G，Ortale R.An incremental clustering scheme for data de-duplication[J].Data Mining and Knowledge Discovery，2010，20（1）：152-187.

[44]Broder A Z，Charikar M，Frieze A M，et al.Min-wise independent permutations[C]//Proceedings of the 30th Annual ACM Symposium on Theory of Computing，1998：327-336.

[45]Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing[C]//Proceedings of Conference on Very Large Data Bases，1999：518-529.

[46]Ilyas I F，Chu X.Trends in cleaning relational data：Consistency and deduplication[J].Foundations and Trends in Databases，2015，5（4）：281-393.

[47]Ramadan B.Indexing techniques for real-time entity resolution[D].Australian National University，2016.

[48]张长水，张见闻.演化数据的学习[J].计算机学报，2013，36（2）：310-316.

[49]Charikar M，Chekuri C，Feder T，et al.Incremental clustering and dynamic information retrieval[J].SIAM Journal on Computing，2004，33（6）：1417-1440.

[50]Aggarwal C C，Han J，Wang J，et al.A framework for clustering evolving data streams[C]//Proceedings of the 29th International Conference on Very Large Data Bases，2003：81-92.

[51]Can F.Incremental clustering for dynamic information processing[J].ACM Transactions on Information Systems，1993，11（2）：143-164.

[52]Benjelloun O，Garcia-Molina H，Menestrina D，et al.Swoosh：A generic approach to entity resolution[J].The VLDB Journal，2009，18（1）：255-276.

[53]Whang S E，Garcia-Molina H.Entity resolution with evolving rules[J].Proceedings of the VLDB Endowment，2010，3（1/2）：1326-1337.

[54]Bhattacharya I，Getoor L.A latent dirichlet model for unsupervised entity resolution[C]//Proceedings of the 2006 SIAM International Conference on Data Mining，2006：47-58.

[55]Zhu L，Ghasemi-Gol M，Szekely P，et al.Unsupervised entity resolution on multi-type graphs[C]//Proceedings of International Semantic Web Conference，2016：649-667.

[56]Christen P，Gayler R，Hawking D.Similarity-aware indexing for real-time entity resolution[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management，2009：1565-1568.

[57]Ramadan B，Christen P.Unsupervised blocking key selection for real-time entity resolution[C]//Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining，2015：574-585.