探究链接在多关系数据挖掘中的应用_涂芳.pdf

DOI:1019392/jcnki1671-7341202308024探究链接在多关系数据挖掘中的应用涂 芳1*曾 铭2邓左祥31上汽通用五菱汽车股份有限公司广西柳州545007;2湖南湖大艾盛汽车技术开发有限公司湖南长沙410221;3广西科技大学计算机科学与技术学院广西柳州545006摘要:随着大数据时代的来临，数据挖掘已经成为热门的研究方向，多关系数据挖掘，是数据挖掘的研究内容之一。本文对多关系数据挖掘进行概述，介绍了描述链接存在于多关系之中，通过多关系数据挖掘的五个研究成果，探究链接在多关系数据挖掘中的应用。已有的一些研究成果证实，在多关系中巧妙地利用链接，可以研究出高效的多关系数据挖掘算法，链接在多关系中的作用是非常大的，可以节省空间和时间，提高准确率，有很大的可扩展性。关键词:数据挖掘;多关系;链接;应用中图分类号:TP311文献标识码:AAbstract:With the advent of the era of big data，data mining has become a popular research directionMulti-relational datamining is one of the research contents of data miningThis paper gives an overview of multi-relational data mining，introduces theexistence of description links in multi-relationship，through five research results of multi-relational data mining，and explores theapplication of links in multi-relational data miningSome existing research results confirm that skillfully using links in multi-rela-tionships can study efficient multi-relational data mining algorithms，The role of links in multiple relationships is very large，whichcan save space and time，improve the accuracy，and have great scalabilityKeywords:Data mining;multiple relations;link;application1 多关系数据挖掘概述随着网络技术的不断发展和进步，人类社会已经进入大数据时代1，数据在关系数据库中的存储，通常以多关系，也就是多表的形式来存储。多关系数据挖掘2，是在关系数据库中相互关联的多张表(也就是关系)上，进行知识学习。对于多关系进行数据挖掘来说，一个传统方法，就是把多张表集成到一张表中，然后运用传统的数据挖掘算法，对集成后的表进行挖掘。但是在实践中，这种传统方法，存在着很多问题。这种传统方法，不但需要大量的计算，而且有可能丢失数据原有的结构特点，造成信息丢失，使得效率、可扩展性都很差。因此，有必要寻找一种直接在多关系上进行挖掘的算法，对可以直接在多关系上进行数据挖掘的算法进行研究，是一个值得研究的问题，当然也会面临一些挑战。多关系数据挖掘的算法，可以减少多关系数据挖掘所需要的时间和空间，能够增大效率并具有可扩展性。多关系数据挖掘的任务，主要包括在多关系上进行分类、在多关系上进行聚类、在多关系上进行关联规则挖掘。多关系分类，是一个在多关系中，进行分类的过程，它基于存储在多关系中的信息，并且还可以进行预测。在多关系分类中，有一个目标关系，它的元组称为目标元组，它们都有一个类标签，如果假设有两个类，则可以把一个类称为正类，另一个类称为负类。多关系分类，就是在可以与目标关系进行连接操作的关系中，根据目标关系中元组的正负类，来区别出关系中正类的元组和负类的元组。多关系聚类，就是使用多关系中数据的信息，根据它们之间的相似度，来把数据对象划分成一系列簇的过程。多关系关联规则挖掘，它的目标是发现存在于不同关系中相互关联的项的模式，进而可以产生多关系关联规则。2 链接存在于多关系之中链接在互联网有着巨大的作用。互联网上的网页，通过链接，互相关联在一起，对于数据挖掘来说，链接同样有着重要的作用，比如多关系数据挖掘。关系数据库是最流行的结构数据的贮存器。在关系数据库中，多关系通过实体 关系模型相互链接在一起。在多关系中，每个关系和每个关系之间主键和外键的对应，就是多关系中链接的表现形式之一。如果多关系数据库中的两个关系，可以通过数据库中物理连接的操作，连接在一起，则这个关系就存在链接。许多分类方法(比如神经网络和支持向量机)，仅仅能够运用在单关系表格中，也就是说，数据存储在一个独立的表格。然而，在现实世界中，多关系数据是普遍和大量存在的。有效地运用多关系之间的链接，可以实现多关系17科技风 2023 年 3 月电子信息数据挖掘，也就是直接在多关系之中进行挖掘，提高挖掘的准确率和效率。3 链接在多关系数据挖掘中的应用有效地利用多关系中的链接，可以解决多关系数据挖掘的问题，直接从多关系中挖掘知识，节省时间和空间，提高准确率、可扩展性。一些研究学者，巧妙地利用多关系中的链接，已经提出一些高效的多关系数据挖掘算法。本小节，通过描述一些多关系数据挖掘的研究成果，来探究链接在多关系数据挖掘中的应用，包括五个研究成果，分别是:CrossMine3、Graph-NB4、CrossClus5、LinkClus6、Distinct7。31 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 要更高。32 Graph-NB:一个有效、准确的多关系贝叶斯分类算法Graph-NB 是一个有效、准确的多关系贝叶斯分类算法。第一，它可以直接地处理多关系，也就是说，并不需要对关系进行连接操作，就可以分类，节省时间和空间。而现有的其他贝叶斯分类法在处理多关系时，都必须先对关系进行物理连接，相比之下，Graph-NB 避免物理连接，代价较低。第二，为了充分利用表格之间的链接，并且有区别的对待链接到目标关系的不同表，建立一个语义关系图，用来描述关系，以及避免关系和关系之间不必要的连接操作。第三，为了优化语义挖掘，使得可以停止一些无用的挖掘，可以对语义关系图，采取裁减策略。语义关系图是一个无环图(V，E，W)，V 代表顶点，每个顶点对应于一个表，E 代表边，而 W 代表两个表之间的连接属性。33 CrossClus:一种在用户指导下的多关系聚类算法在多关系聚类中，传统的方法，在计算两个对象的相似度时，是根据可以与它们进行连接操作的元组来判断的。然而，这种方法有两个问题。第一，它根据连接元组来计算相似度，因为一个多关系中可以连接的元组通常很多，所以计算它们代价是很大的。第二，在一个数据库中，通常有许许多多的属性，它们覆盖许多不同方面的信息，但是仅仅有一小部分是和用户聚类任务有关的，使用这个方法进行聚类的话，所有的属性都会不加区分，这样子就不太可能产生用户希望得到的聚类结果。虽然以上问题，可以通过用户半指导聚类的方法来解决，但是这个方法也有不足。因为这个方法，通常需要用户拥有比较丰富的知识，能够提供高质量的测试集，然而，多关系数据的复杂性，使得用户有时候很难提供它。CrossClus 可以解决上述问题。它只需要用户提供聚类的任务，包括聚类的目标关系，以及一个或者多个指定属性。在用户指定聚类任务后，CrossClus 搜寻一些相关属性，这些相关属性，是与用户指定的属性有关联的属性。在搜寻相关属性的过程中，CrossClus 使用启发式算法，在这种情况下，需要确定哪些属性是相关属性，相关属性的选择，是基于用户指定属性的。从根本上说，如果两个属性聚类元组的方式非常不同，则它们的相似性就低，而且不太可能相关，反过来，如果聚类的方式相似，它们相似性就会高，就有可能相关。所以，要找出相关属性，就要找出与用户指定属性具有一定相似度的属性。因此，需要一种计算方法，来计算相似度，相似度是用户指导的属性和其他属性之间的相关属性。总之，为了达到聚类的目的，CrossClus 最终选择的是一系列具有高相关，但是却不冗余的属性。Crossclus 使用相似向量，来计算属性之间的相似度。在找相关属性的过程中，为了找到所有可以与目标关系的元组进行连接关系的元组，CrossClus 采用元组 ID 传播的方法，运用多关系之间的链接，进行虚连接，节省时间和空间。34 LinkClus:一种运用多样的语义链接的有效聚类算法在进行多关系聚类时，传统的方法，在计算相似度时，需要计算两两对象之间的相似度。在这个方法中，两个对象的相似度，递归的定义为链接到这两个对象的所有对象之间，两两相似度的平均值。比如说，如果需要计算两个研究学者的相似度，假设他们都在某些会议上发表过论文，那么，这两个研究学者的相似度，可以用这些会议之27电子信息科技风 2023 年 3 月间，两两相似度的平均值来计算。虽然这个传统方法很有用，但是它的代价是很高的。不管是什么对象，它都迭代的计算两两对象之间的相似度，无论在空间上和时间上，时间复杂度和空间复杂度都很大。为了减小多关系聚类的时间复杂度和空间复杂度，实现高质量的聚类，Linkclus 设计出一种树形的数据结构Simtree，以多粒度的方式来存储相似度，可以用来存储和计算对象之间的相似度。它是一种通过链接来计算相似度的方法，通过存储比较有意义的相似度，压缩一些没有意义的相似度，有效地节省空间和时间。在 Simtree 中，不需要计算两两对象之间的相似度，只需要计算一部分对象之间的相似度，节省空间和时间。虽然只计算一部分对象之间的相似度，但是任意两两对象之间的相似度，依然可以通过树形结构 Simtree 中的链接得到。Simtree 构造树形结构的思想，来源于现实生活，现实生活中，许多对象的等级结构，是自然存在的。比如，动植物的等级结构，或者商品的等级结构等。在某些超市中就存在商品的等级结构，比如全部的商品，包括食品、电器和服装等，而电器又包括电视、冰箱