一种多关系频繁模式挖掘算法

减小字体 增大字体 作者:邓左祥 刘连芳 梁一平 周小平  来源:www.zhonghualunwen.com  发布时间:2009-10-12 23:27:51

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

[1] [2] [3] [4]  下一页

Tags:

作者:邓左祥 刘连芳 梁一平 周小平
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论