探究链接在多关系数据挖掘中的应用

涂芳 曾铭 邓左祥

1.上汽通用五菱汽车股份有限公司 广西柳州 545007；2.湖南湖大艾盛汽车技术开发有限公司 湖南长沙 410221；3.广西科技大学计算机科学与技术学院 广西柳州 545006

1 多关系数据挖掘概述

随着网络技术的不断发展和进步，人类社会已经进入大数据时代[1]，数据在关系数据库中的存储，通常以多关系，也就是多表的形式来存储。多关系数据挖掘[2]，是在关系数据库中相互关联的多张表(也就是关系)上，进行知识学习。

对于多关系进行数据挖掘来说，一个传统方法，就是把多张表集成到一张表中，然后运用传统的数据挖掘算法，对集成后的表进行挖掘。但是在实践中，这种传统方法，存在着很多问题。这种传统方法，不但需要大量的计算，而且有可能丢失数据原有的结构特点，造成信息丢失，使得效率、可扩展性都很差。因此，有必要寻找一种直接在多关系上进行挖掘的算法，对可以直接在多关系上进行数据挖掘的算法进行研究，是一个值得研究的问题，当然也会面临一些挑战。多关系数据挖掘的算法，可以减少多关系数据挖掘所需要的时间和空间，能够增大效率并具有可扩展性。

多关系数据挖掘的任务，主要包括在多关系上进行分类、在多关系上进行聚类、在多关系上进行关联规则挖掘。多关系分类，是一个在多关系中，进行分类的过程，它基于存储在多关系中的信息，并且还可以进行预测。在多关系分类中，有一个目标关系，它的元组称为目标元组，它们都有一个类标签，如果假设有两个类，则可以把一个类称为正类，另一个类称为负类。多关系分类，就是在可以与目标关系进行连接操作的关系中，根据目标关系中元组的正负类，来区别出关系中正类的元组和负类的元组。多关系聚类，就是使用多关系中数据的信息，根据它们之间的相似度，来把数据对象划分成一系列簇的过程。多关系关联规则挖掘，它的目标是发现存在于不同关系中相互关联的项的模式，进而可以产生多关系关联规则。

2 链接存在于多关系之中

链接在互联网有着巨大的作用。互联网上的网页，通过链接，互相关联在一起，对于数据挖掘来说，链接同样有着重要的作用，比如多关系数据挖掘。

关系数据库是最流行的结构数据的贮存器。在关系数据库中，多关系通过实体——关系模型相互链接在一起。在多关系中，每个关系和每个关系之间主键和外键的对应，就是多关系中链接的表现形式之一。如果多关系数据库中的两个关系，可以通过数据库中物理连接的操作，连接在一起，则这个关系就存在链接。

许多分类方法(比如神经网络和支持向量机)，仅仅能够运用在单关系表格中，也就是说，数据存储在一个独立的表格。然而，在现实世界中，多关系数据是普遍和大量存在的。有效地运用多关系之间的链接，可以实现多关系数据挖掘，也就是直接在多关系之中进行挖掘，提高挖掘的准确率和效率。

3 链接在多关系数据挖掘中的应用

有效地利用多关系中的链接，可以解决多关系数据挖掘的问题，直接从多关系中挖掘知识，节省时间和空间，提高准确率、可扩展性。一些研究学者，巧妙地利用多关系中的链接，已经提出一些高效的多关系数据挖掘算法。本小节，通过描述一些多关系数据挖掘的研究成果，来探究链接在多关系数据挖掘中的应用，包括五个研究成果，分别是：CrossMine[3]、Graph-NB[4]、CrossClus[5]、LinkClus[6]、Distinct[7]。

3.1 CrossMine：一种有效的在多关系中分类的算法

传统的方法，在处理多关系分类时，采取物理连接多关系的方法，例如ILP分类方法。ILP把FOIL作为它的分类算法，为了实现分类，FOIL需要创建一个个规则，每个规则都包含一个个谓词，FOIL通过评估每个谓词的好坏，在现有的规则中，加入最好的谓词。在这种情况下，需要一个估计谓词的方法，可以用Foil Gain来估计每一个谓词。拥有最大Foil Gain的谓词，就是最好的谓词。但是，ILP采用对关系进行物理连接的方法，来计算出Foil Gain，这就会造成耗时大的问题。

CrossMine是一种有效的在多关系中分类的算法。与ILP类似，CrossMine也同样要一次一个地把谓词加进规则里去，也要计算出Foil Gain，以找出最好的谓词。但是，与ILP不同的是，CrossMine不用直接对表进行连接，就可以计算出Foil Gain，它采取的是一种基于多关系之间链接的元组ID传播的方法。在一般情况下，多关系数据库的目标关系中的主键，代表每个目标元组的ID。CrossMine使用元组ID传播的方法，在所有活动的关系中(初始情况下，只有目标关系是活动关系)，以及那些可以与活动关系进行物理连接的关系中，寻找拥有最大Foil Gain的谓词。

算法FOIL和CrossMine大体上类似，所不同的是，FOIL采用物理连接，CrossMine采用基于多关系之间链接的元组ID传播。因此，CrossMine在时间和空间上的花费，都比物理连接的FOIL少很多，对于准确率、效率、可扩展性来说，CrossMine也比FOIL要更高。

3.2 Graph-NB：一个有效、准确的多关系贝叶斯分类算法

Graph-NB是一个有效、准确的多关系贝叶斯分类算法。第一，它可以直接地处理多关系，也就是说，并不需要对关系进行连接操作，就可以分类，节省时间和空间。而现有的其他贝叶斯分类法在处理多关系时，都必须先对关系进行物理连接，相比之下，Graph-NB避免物理连接，代价较低。第二，为了充分利用表格之间的链接，并且有区别的对待链接到目标关系的不同表，建立一个语义关系图，用来描述关系，以及避免关系和关系之间不必要的连接操作。第三，为了优化语义挖掘，使得可以停止一些无用的挖掘，可以对语义关系图，采取裁减策略。语义关系图是一个无环图(V，E，W)，V代表顶点，每个顶点对应于一个表，E代表边，而W代表两个表之间的连接属性。

3.3 CrossClus：一种在用户指导下的多关系聚类算法

在多关系聚类中，传统的方法，在计算两个对象的相似度时，是根据可以与它们进行连接操作的元组来判断的。然而，这种方法有两个问题。第一，它根据连接元组来计算相似度，因为一个多关系中可以连接的元组通常很多，所以计算它们代价是很大的。第二，在一个数据库中，通常有许许多多的属性，它们覆盖许多不同方面的信息，但是仅仅有一小部分是和用户聚类任务有关的，使用这个方法进行聚类的话，所有的属性都会不加区分，这样子就不太可能产生用户希望得到的聚类结果。虽然以上问题，可以通过用户半指导聚类的方法来解决，但是这个方法也有不足。因为这个方法，通常需要用户拥有比较丰富的知识，能够提供高质量的测试集，然而，多关系数据的复杂性，使得用户有时候很难提供它。

CrossClus可以解决上述问题。它只需要用户提供聚类的任务，包括聚类的目标关系，以及一个或者多个指定属性。在用户指定聚类任务后，CrossClus搜寻一些相关属性，这些相关属性，是与用户指定的属性有关联的属性。在搜寻相关属性的过程中，CrossClus使用启发式算法，在这种情况下，需要确定哪些属性是相关属性，相关属性的选择，是基于用户指定属性的。从根本上说，如果两个属性聚类元组的方式非常不同，则它们的相似性就低，而且不太可能相关，反过来，如果聚类的方式相似，它们相似性就会高，就有可能相关。所以，要找出相关属性，就要找出与用户指定属性具有一定相似度的属性。因此，需要一种计算方法，来计算相似度，相似度是用户指导的属性和其他属性之间的相关属性。总之，为了达到聚类的目的，CrossClus最终选择的是一系列具有高相关，但是却不冗余的属性。

Crossclus使用相似向量，来计算属性之间的相似度。在找相关属性的过程中，为了找到所有可以与目标关系的元组进行连接关系的元组，CrossClus采用元组ID传播的方法，运用多关系之间的链接，进行虚连接，节省时间和空间。

3.4 LinkClus：一种运用多样的语义链接的有效聚类算法

在进行多关系聚类时，传统的方法，在计算相似度时，需要计算两两对象之间的相似度。在这个方法中，两个对象的相似度，递归的定义为链接到这两个对象的所有对象之间，两两相似度的平均值。比如说，如果需要计算两个研究学者的相似度，假设他们都在某些会议上发表过论文，那么，这两个研究学者的相似度，可以用这些会议之间，两两相似度的平均值来计算。虽然这个传统方法很有用，但是它的代价是很高的。不管是什么对象，它都迭代的计算两两对象之间的相似度，无论在空间上和时间上，时间复杂度和空间复杂度都很大。

为了减小多关系聚类的时间复杂度和空间复杂度，实现高质量的聚类，Linkclus设计出一种树形的数据结构Simtree，以多粒度的方式来存储相似度，可以用来存储和计算对象之间的相似度。它是一种通过链接来计算相似度的方法，通过存储比较有意义的相似度，压缩一些没有意义的相似度，有效地节省空间和时间。

在Simtree中，不需要计算两两对象之间的相似度，只需要计算一部分对象之间的相似度，节省空间和时间。虽然只计算一部分对象之间的相似度，但是任意两两对象之间的相似度，依然可以通过树形结构Simtree中的链接得到。Simtree构造树形结构的思想，来源于现实生活，现实生活中，许多对象的等级结构，是自然存在的。比如，动植物的等级结构，或者商品的等级结构等。在某些超市中就存在商品的等级结构，比如全部的商品，包括食品、电器和服装等，而电器又包括电视、冰箱、洗衣机等，更进一步，电视又包括各种各样品牌的电视。如果用Simtree来表示沃尔玛超市的商品，则需要计算冰箱和电视的总体相似度，以及每个冰箱和每个冰箱之间的相似度，但是每个冰箱和每个电视的相似度，就不再需要计算，因为它可以通过上述两个相似度推导得到。

3.5 Distinct：一种在多关系中区别同名对象的对象识别算法

在现实世界中，许多对象有可能有着相同的名字，如果不区别这些同名，可能会造成一些迷惑和误解。比如，在计算机领域的论文数据库DBLP中，就有许多同名作者，但是实际上不是同一个人，只是同名同姓。区别同名对象是一个重要的工作，Distinct是一种在多关系中区别同名对象的对象识别算法，它可以用来区别同名对象，具有较高的准确率。

对象识别与一个比较流行的问题类似，就是对象一致问题，也叫副本探测问题，它的目标是把涉及相同对象却命名不同的记录合并起来，比如，找出涉及同一个论文的不同引用名称。但是，和对象一致问题相比较，对象识别又是一个不同的问题，在对象识别问题中，因为同名对象具有相同的名字，所以不能通过名字来计算同名对象之间的相似度。但是，在对象一致问题中，由于对象的命名不同，因此可以通过名字来计算对象之间的相似度。

由于同名对象具有相同的名字，仅仅依靠名字来区别同名对象，是不可能的，因此，需要另外一种方法来区别同名对象。在多关系中，运用链接是一个非常有用的区别同名对象的手段，Distinct运用链接来区分同名对象。如果两个对象存在关联，则这两个对象就存在链接。比如，一篇论文的所有作者之间，都是存在关联，因此存在链接的。一组同名对象，如果是同一个对象，它们的链接，通常存在相同点，以一个比较固定的方式存在。比如，假设两篇论文出现同名作者，如果他们是同一个人，则通常会链接到另一个同名的共同作者，简单地说，这两篇论文如果出现两个同名作者，则这两个同名作者，都很大可能分别是同一个人。另一方面，如果同名对象不是同一个人，同名对象的链接通常也不相同。比如，假设两篇论文出现同名作者，但是其他作者都不相同，这两个同名作者，就有一定的可能，不是同一个人，只是同名同姓的两个人。为了提高区别同名对象的准确率，Distinct定义两个对象之间链接的总体强度，定义为在一定的步数内，从一个对象链接到另外一个对象的可能性。

结语

在多关系数据挖掘中，已有的一些研究成果证实，在多关系中巧妙地利用链接，可以研究出高效的多关系数据挖掘算法。链接在多关系中的作用是非常大的，可以节省空间和时间，提高准确率，有很大的可扩展性。今后，数据挖掘的研究学者，可以继续利用多关系中的链接，研究其他高效的多关系数据挖掘算法。