多表数据的物理联接

多表数据的物理联接

挖掘来自大数据库的信息。大多数传统的数据挖掘方法只适用于在数据库的单表上进行挖掘。当面对多表时,不得不把这些表物理上连接到一张表中,这样会出现准确率低、效率低等问题。在这种情况下,多关系数据挖掘应运而生1相关工作1.1传统频率模式的挖掘算法挖掘频繁模式算法最有代表性的是Apriori算法1.2基于ilp的多关系挖掘算法目前大多数的多关系数据挖掘算法都是借鉴ILP思想WARMR1.3id传播思想除了ILP思想,多关系数据挖掘也可以借鉴文献中提出的元组ID传播思想。元组ID传播是一种在多表间建立虚连接的思想,它的定义如下:假设有两个关系CrossMineCrossclusMFP1.4模式挖掘算法本文针对传统的频繁模式挖掘算法不适用于解决基于ILP思想的多关系频繁模式挖掘算法效率低的问题,提出了一种多关系频繁模式挖掘算法。借助于元组ID传播的思想,对表进行虚连接,使算法可以直接在多张表上挖掘出所有频繁模式,提高了在多关系中挖掘频繁模式的效率。在挖掘多表频繁项集时,只考虑来自以下两种情况的表所产生的项集:a)两个表之间存在主键与外键的对应;b)两个表的主键同时是某个第三表的外键。不考虑其他情况,因为其他情况在数据库中代表这些表没有很强的相关性。2支持度计数多关系频繁模式1项。包含于任一个表的非主键和外键属性的每个不同取值称为一个项,记为一个属性和取值对:属性=取值,或用惟一的一个标志符表示,如用标志符2项集。多个项构成的集合称为项集。3单表项集。项集中的每个项,若都来自同一个表,则称为单表项集。4多表项集。项集中的每个项,若涉及多个表,则称为多表项集。5支持度计数。一个项集6频繁项集。由用户给定一个支持度计数阈值,所有支持度计数不小于该阈值的项集称为频繁项集。7多关系频繁模式挖掘。给定支持度计数阈值,发现存在于一个数据库的多个表中的所有不小于阈值的频繁项集,包括单表频繁项集和多表频繁项集。3算法步骤3.1属性取值的处理常见的数据库属性包括二元属性、分类属性、序数型属性、区间标度属性。由于二元属性、分类属性、序数型属性的取值是有限的,可以直接进行挖掘。而区间标度属性的取值包含有无限多个连续值,不利于统计计数,因此必须对其预处理。对区间标度属性预处理的方法是使用预定义的概念分层对其进行离散化3.2支持度计数2-频繁项集的创建算法的工作过程如下:a)由用户设定支持度计数的阈值。b)对任何一对存在主键外键对应的两个表之间进行元组ID传播。c)对每个表的每个属性(除了主键、外键、IDset)进行扫描,对该属性所产生的每个项进行支持度计数,支持度计数不小于阈值的项都是1-频繁项集。为了区别每个项,把它表示成“表.属性(值)”的形式。在存储每个1-频繁项集时,保存它的三类信息:(a)该项集的名称,即“表.属性(值)”。(b)该项集的支持度计数,设项集名称为(c)包含该项集的所有元组ID的值,也就是保存该表中的包含该项集的所有元组的主键值,设项集名称为d)把每两个1-频繁项集组合起来,产生候选2-项集。在产生候选2-项集时,不用考虑同一个表的同一个属性所产生的项组合而成的2-项集,因为必然没有哪个元组包含这个2-项集,其支持度计数必然是0。只考虑组合不同属性所产生的项。设有两个项,分别是(a)如果(b)如果如果这两个表是有一个表包含另一个表的IDset,假设如果这两个表是同时包含某个第三方表的IDset,假设支持度计数不小于阈值的候选2-项集都是2-频繁项集。在保存2-频繁项集时,类似于1-频繁项集,也需要保存以下三类:(a)该项集的名称,因为要区分出项所在的表的名称,所以应该保存为“表.属性(值),表.属性(值)”。(b)该项集的支持度计数。(c)包含该项集的所有元组ID集的值,对于任意一个产生该项集一个支持度的情况,无论是单表项集,还是多表项集,都保存为“表.ID(值),表.ID(值)”。例如,假设一个由e)在发现了2-频繁项集后,就要找出候选3-项集。利用Apriori算法的性质——频繁项集的所有非空子集也必须是频繁的。因此,候选3-项集的所有子集都必须是频繁项集。根据这一点,产生候选3-项集。为候选3-项集计数的方法与前面的1-项集和2-项集有所不同,不再通过扫描数据库来计数,而是通过如下方法来为候选3-项集计数。为候选3-项集计数的方法是:假设有三个项举一个计数方法的例子,并说明理由。假设有三个表支持度计数不小于阈值的候选3-项集都是3-频繁项集。需要保存的3-频繁项集的信息与前面2-频繁项集是类似的。f)4-频繁项集,以及项的个数大于4的频繁项集的挖掘方法,与3-频繁项集类似。算法的伪码如下:算法:在多关系中挖掘频繁项集。输入:一个多关系数据库输出:方法:=传播元组ID(=挖1-项集(iffor({foreach{项集foreachIDifID.count++;if把}returnProcedure传播元组ID(foreach关系foreach关系if把returnProcedure挖1-项集(foreach关系foreach属性if为if把returnProcedure挖2-项集(foreach1-频繁项集foreach1-频繁项集合并if比较elseif取项的ID对应的元组的IDset值的并集,与另一个项的ID进行比较,相同的ID个数为项集{if取if{把{returnProcedureapriori_gen(foreach项集foreach项集if({ifhas_infrequent_subset(删除else把returnProcedurehas_infrequent_subset(foreach(ifreturnfalse;4支持度计数阈值2.本文使用PKDDCUP1999中的包含八个表的金融数据库(http://lisp.vse.cz/pkdd99/Challenge/chall.ht),作为实验数据集,做两个实验。实验环境:操作系统为WindowsXPProfessional;内存为512MB;CPU为Pentium43.0GHz;平台为BorlandC++Builder6.0。1目的:比较多关系频繁模式挖掘算法和物理连接多表并采用传统的单表频繁模式挖掘算法的运行时间。过程:从数据集中选择两个表(loan、account),进行裁剪,保留200个元组;设定支持度阈值为4%,也就是支持度计数阈值为200×4%=8。结果:运行时间对比如表1所示。从实验结果可以看到,本文提出的算法有较高的效率。2目的:分别在表的个数、元组个数、支持度变化的情况下,比较运行时间的变化。过程:保持元组个数不变(对八个表都进行裁剪,使每个表都只保留200个元组)、支持度不变(设定支持度阈值为4%,也就是支持度计数阈值为200×4%=8),改变表的个数(分别从八个表中选择其中的两个表(loan、account)、四个表(loan、account、order、transaction)、六个表(loan、account、order、transaction、district、disposition),以及全部八个表),作为算法的输入,得出它们的运行时间。结果:运行时间变化如图1所示。从图1可以看到,随着表的个数的不断增加,运行时间不断增加,并且增长速度越来越快。过程:保持表的个数不变(选择loan、account两个表)、元组个数不变(对两个表都进行裁剪,使每个表都只保留500个元组),改变支持度(设定三个支持度阈值2%、4%、6%),作为算法的输入,得出它们的运行时间。结果:运行时间变化如图2所示。从图2可以看出,随着支持度阈值的不断增加,运行时间不断下降。过程:保持表的个数不变(选择loan、account、district三个表)、支持度不变(设定支持度阈值为4%),改变元组的个数(对三个表都进行裁剪,使三个表分别都保留50、100、200、300、400、500个元组),作为算法的输入,得出它们的运行时间。结果:运行时间变化如图3所示。从图3可以看出,随着每张表的元组的个数的不断增加,运行时间不断增加,并且增长速度越来越快。5基于ilp的多关系频繁模式挖掘算法由于传统的数据挖掘方法在处理多关系频繁