资源描述：
《一种多关系频繁模式挖掘算法 》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一种多关系频繁模式挖掘算法数据挖掘,就是从大型的数据库中提取人们感兴趣的知识。大多数传统的数据挖掘方法只适用于在数据库的单表上进行挖掘。当面对多表时,不得不把这些表物理上连接到一张表中,这样会出现准确率低、效率低等问题。在这种情况下,多关系数据挖掘应运而生1]。多关系数据挖掘研究直接在数据库多张表上进行挖掘的方法,无须向单表转换。 1相关工作 1.1传统频繁模式挖掘算法 挖掘频繁模式算法最有代表性的是Apriori算法2],但是它只适用于单维的、单层的数据。在文献3]中提出的频繁模式挖掘算法是一种传统的单表频繁模式挖掘算法,虽然适用于多维,但是只能处理单
2、表频繁模式挖掘,不适用于多表,当面对多表时,首先不得不把多表集成到单表,存在效率低的问题。 1.2基于ILP的多关系数据挖掘算法 目前大多数的多关系数据挖掘算法都是借鉴ILP思想4]发展起来的。ILP使用逻辑编程语言作为知识表示方式,这种知识表示方式更具表达力,能够灵活方便地表示关系学习与多关系数据挖掘过程中的多关系数据、背景知识以及涉及多关系的复杂模式。此外,ILP方法便于在归纳推理过程中使用背景知识。这些都是ILP思想成为多关系数据挖掘主要方法的直接原因。但ILP思想存在一些缺点:a)处理不确定性和有噪声数据的能力有限;b)ILP使用基于θ包含
3、的操作在假设空间中进行启发式搜索,而θ包含计算实质上是一个NP完全问题,这使得ILP思想效率低,可扩展性差。 R5,6]和FARMER7]是两种基于ILP思想的多关系频繁模式挖掘算法。R算法的核心思想与Apriori算法相同,采用逐层的、宽度优先的搜索策略。FARMER采用一种复杂的数据结构Trie树来存储和操纵查询,Trie树中从根节点到叶子节点的每条路径都对应一个查询,利用该树进行查询的生成和支持度的计算。由于R和FARMER都基于ILP思想,这使得两者的效率都不高。 1.3基于元组ID传播的多关系数据挖掘算法 除了ILP思想,多关系数据挖掘
4、也可以借鉴文献8]中提出的元组ID传播思想。元组ID传播是一种在多表间建立虚连接的思想,它的定义如下:假设有两个关系R1和R2,R1的主键是整数属性,这些整数代表R1中每个元组的ID(如果没有这样的主键,可以创建一个,表示为R1.ID)。假定关系R1和R2可以按属性R1.k和R2.k连接(R1包含R2的主键k)。则在R2中增加一列属性IDset(R1),对R2的每一个元组t,其在IDset(R1)属性上的值是,R1中所有可与t连接的元组在R1.ID上的值,即t在IDset
5、(R1)上的值等于∪u∈R1,u.k=t.kR1.ID(u),R1.ID(u)表示元组u在R1.ID上的值。也就是说,R1中所有元组的ID都传播到R2可与之连接的元组的属性IDset(R1)上。 CrossMine8]是一种基于元组ID传播思想的多关系分类算法。CrossMine利用元组ID传播来评估每个谓词的foil增益,把最佳谓词添加到当前规则中。借助元组ID传播,CrossMine无须物理连接,大大提高了分类的效率。 Crossclus9]是一种基于元组ID传播思想的用户指导的多关系
6、聚类算法。在用户指定某一属性后,Crossclus利用元组ID传播来搜索相关属性,通过这些属性计算对象之间的相似度。借助元组ID传播,Crossclus无须物理连接,聚类效率较高。 MFP10]是一种基于元组ID传播的用户指导的多关系关联规则算法。在用户指定某些属性后,MFP发现由这些属性所产生的关联规则。借助元组ID传播,MFP无须物理连接,效率较高。 1.4本文工作 本文针对传统的频繁模式挖掘算法不适用于解决基于ILP思想的多关系频繁模式挖掘算法效率低的问题,提出了一种多关系频繁模式挖掘算法。借助于元组ID传播的思想,对表进行虚连接,使算法可以直接在多张表
7、上挖掘出所有频繁模式,提高了在多关系中挖掘频繁模式的效率。 在挖掘多表频繁项集时,只考虑来自以下两种情况的表所产生的项集:a)两个表之间存在主键与外键的对应;b)两个表的主键同时是某个第三表的外键。不考虑其他情况,因为其他情况在数据库中代表这些表没有很强的相关性。 2术语定义 定义1项。包含于任一个表的非主键和外键属性的每个不同取值称为一个项,记为一个属性和取值对:属性=取值,或用惟一的一个标志符表示,如用标志符X表示一个项。 定义2项集。多个项构成的集合称为项集。 定义3单表项集。项集中的每个项,若都来自同一个表,则称为单
