关联规则基础上数据挖掘最新算法

课程设计报告

名    称： 数据仓库与数据挖掘         

  题    目： 数据挖掘中关联规则的发展趋势

院    系： 经济管理系                 

班    级： 信管1201                   

学    号： ************                

****  ***                     

****  **                       

成    绩：                  

日期：2015年5月

一、引 言 3

二、基于复杂数据组织形式的关联规则算法3

(一)并行数据库 3

(二)数据仓库 3

(三)时间连续数据库 4

(四)增量式更新数据库4

三、新研究方法的引入 5

(一)模糊集 5

(二)概念格 5

(三)其他研究方法 5

四、前沿研究 5

(一)时间-空间数据库 5

(二)Web挖掘 6

(三)多媒体数据库6

(四)可视化挖掘 6

五、总结与展望 7

数据挖掘中关联规则的发展趋势

一、引 言

目前,越来越多的行业都存在巨量数据处理的问题,结构简明的关联规则凭借简单易懂的规则表达形式较其他数据挖掘方法更容易被接受,其广泛的应用前景也被学术界所认同。理论体系的逐渐完善和实际应用的巨大成功使关联规则一度成为数据挖掘的重要研究方向。但随着现代数据库技术的发展和应用领域的拓宽,数据存储形式甚至数据格式都发生了巨大变化,关联规则研究也面临着前所未有的挑战。

为了明确关联规则研究的现实意义和未来发展趋势,笔者考察了近几年国内外相关的研究成果和最新动态。在对复杂数据组织形式的关联规则挖掘详细描述的基础上,探讨了其他学科领域对关联规则的理解及相应的研究方法,最后提出了关联规则的前沿研究问题和未来的发展趋势。

二、基于复杂数据组织形式的关联规则算法

  随着并行和分布式数据库系统、数据仓库、联机分析处理(OLAP)和数据立方体等数据组织、存储、分析和处理技术的出现和成熟,使关联规则挖掘在并行数据库、数据仓库、时间连续数据库和增量更新数据库等复杂数据组织形式中的应用成为可能,相应地产生了一系列新的关联规则算法。

(一)并行数据库

对于并行数据库而言,一般具有多个可以同时运行的处理器(结点),并通过网络交换信息。由于并行体系结构计算能力强,数据处理量大,因而基于并行体系结构的关联规则算法明显优于基于单处理器的顺序算法。并行数据库可以分为无共享体系(share-nothing)结构和内存共享体系(shared-memory)结构。关联规则并行算法的设计主要从数

据合理分配、减少I/O操作、负载平衡、减少结点间的通信和同步以及减少计算冗余等方面权衡考虑。

无共享体系结构中,数据库分布在各个结点(即分布式数据库),各结点间有网络连接,每个结点可处理子数据库。主要算法都是将原有的顺序算法并行化,如Agrawal,R.等(1996)的Countdistribu2tion,DataDistribution和CandidateDistribution[1];Park,J.S.等(1995)的PDM[2];Cheung,D.W.等(1996)的FDM[3]和Cheung,D.W.等(1996)的DMA[4],以及Za2ki,M.J.等(1997)的ParEclat[5]等算法。在内存共享体系结构中多个结点共用内存和数据库,各结点通过共享变量通信。这类算法采用了异步候选集生成,比宽度优先算法的扫描次数少。但各结点可访问数据库,因此需要解决I/O通道共享和并发访问数据库时I/O占用问题。由于这类并行数据库较少使用,相关的研究也不多,有代表性的算法是APM[6]。

(二)数据仓库

目前,数据仓库已经成为标准的数据存储和组织形式。在数据仓库中各种数据以形式组织,即数据立方体。而采用OLAP技术驱动的数据仓库具有数据质量高、相关数据环境好和实时分析等优点。因此相应的算法就直接针对数据立方体设计,并由OLAP技术实现。这类算法多是已有的关联规则算法的推广和优化。

较为简单的算法是建立在频繁谓词集上的,把谓词作为项,谓词的出现次数作为支持度,不考虑谓词出现的强度。如Apriori-Cube算法[7](高学东等(2003))直接在数据立方体上搜索频繁谓词集。而考虑概念层次的算法较复杂,如Adaptive-FP算法[8]和FP-Growth[9]类似,但是先对项加入概念层次编码后再建立FP-tree,采用同一支持度挖掘同一概念层次的维间和维内频繁集,采用可变支持度挖掘不同维或者同维不同概念层次的频繁集,贺琼等(2004)在Adaptive-FP的基础上进一步利用概念层次信息优化了FP-tree的建立过程[10]。

(三)时间连续数据库

时间连续数据库包含了随时间延续而变化的事务数据或事件记录。这类数据的特点是具有明显的时间顺序,且呈现一定的规律性或者周期性。这方面的研究主要集中在连续时间的事务数据集和多个时间序列中的关联规则挖掘。连续时间的事务数据集中的关联规则挖掘类似具有时间维度的关联规则挖掘,但直接将时间效应引入算法,增加算法的适应性和可扩展性。施平安等(2001)认为事务的出现频率和时间段有关。因此先定义频繁集的高频适用期和低频适用期,然后分别挖掘高频适用期和低频适用期中的频繁集;喻伟等(2002)建立了延迟关联规则模型:XϖTY,当T>0时,称为延迟规则;当T=0时为一般规则,并提出了DirectDelay算法挖掘延迟规则。在时间序列中,每个序列都表示一个数值属性的取值曲线或者事件的持续时间和间隔。而数值属性的时间序列可映射为多个取值区间的事件序列，因此时间序列都可转化为事件序列。事件序列的关联规则更强调规律性和周期性,常被称为频繁序列模式(frequentsequentialpattern)或者频繁片断模式(frequentepisodepattern)①。Villafane,R.等(2000)分析多个时序的事件在时间段上的包含关系[13],由此建立可传递的闭合包含图(transitivelyclosedcontain2mentgraph),再通过点和边的计数得到频繁包含关系的支持度和可信度。Harms,S.K.等(2004)提出了挖掘片断关联规则的MOWCATL算法[14],可在关联规则的前件和后件中分别引入用户指定的内包约束(inclusionconstraint),还可指定固定的或者最大的时间滞后值。

(四)增量式更新数据库

增量式更新数据库中的关联规则挖掘面临的问题主要有两个:第一,给定的支持度和置信度阈值,新的事务数据值d加入原数据集D时,如何得到d∪D的关联规则;第二,给定事务数据库D,支持度和置信度阈值发生变化时,如何得到新的关联规则。

Cheung,D.W.等(1996)首先考虑了第一个问题,并提出了增量式更新数据库中关联规则挖掘的FUP算法[15]。FUP基于Apriori[16]并假设已有频繁集和支持度已经保存。该算法没有充分利用已有的频繁集信息,需要对d∪D进行n次扫描(n为D中最大频繁项集的大小),扫描次数过多;而李宝东等(2002)的EFUP算法[17],只要先逐层扫描d,再扫描D一次,就能得到d∪D的频繁集。对于第二个问题,有两种情况:第一,支持度阈值变大导致频繁集减少;第二,支持度阈值变小导致频繁集增加。第一种情况只需扫描一次数据库并保留满足新的支持度的频繁集即可。第二种情况较为复杂,需要重新设计算法。代表算法有IUA[18]。IUA算法使用了一种新的候选集生成方法,充分利用了已有的频繁集信息。但IUA中的iua-gen()函数的连接操作所得候选集数目过大,而修剪操作还会误删频繁集。陈丽等(2001)的EIUA算法[19]和石冰等(2000)的LAA算法[20]分别改进了iua-gen()函数,避免误删频繁集的同时又提高了算法的效率。

三、新研究方法的引入

(一)模糊集

模糊集由Zadeh,A.于1965年创立。其主要创新是把经典集合里特征函数的取值函数由二值域{0,1}扩展到闭区间[0,1],并给出了模糊集的定义:一个定义在论域U上的模糊集合F由隶属函数μF:Uϖ[0,1]表征,其中μF表示在模糊集合F上的隶属度。模糊集主要用于提高关联规则的有趣度和可理解性。Hong,T.等(1999)提出一种典型的定量关联规则挖掘算法[21]。先使用隶属函数将每个定量数据转化为带有语言值的标量基数,再在该模糊集中挖掘关联规则。Wang,S.等(2002)考虑了时间连续的事务数据库中挖掘模糊相似的序列模式的问题[22]。Hong,T.等(2003)提出了模糊多层关联规则的挖掘方法[23]。

(二)概念格

在形式概念分析中[24],概念的外延表示这个概念的所有对象的集合,而内涵表示所有对象共有的属性集合。以此将概念的哲学理解形式化。概念格(conceptlattice)是形式概念分析中的核心数据结构,概念格的结点关系体现了概念之间的泛化和实例化关系,因此非常适合用来挖掘规则型知识。

Missaoui,R.等(1994)首次从概念格中提取近似规则[25],实现了基于概念格的关联规则挖掘;Pasquier,N.等(1999)利用了概念格中概念连接的闭合性,创新地定义了闭合项集格[26],并通过A-close算法挖掘频繁闭合项集(frequentcloseditemset);Pei,J.等(2000)的CLOSET算法以FP-tree为基础,使用深度优先策略搜索频繁闭合集[27];Wang,J.等(2003)在FP-tree结构、修剪策略和验证闭合性等方面对CLOSET做出改进得到CLOSET+算法[28];而Zaki,M.J.等(2002)建立的CHARM算法采用了tid2set和diffsets结构表示事务标签集[29],并同时搜索项集和事务标签集,可高效修剪并得到频繁闭合集。

(三)其他的研究方法

粗糙集由波兰数学家Pawlak,Z.于1982年创新。粗糙集强调数据的不可辨(indiscernibility)与模棱两可(ambiguity),研究不同类中的对象组成的集合间的关系。因此粗糙集在关联规则中的应用主要是规则挖掘前的数据约简和降维等预处理;朱建平等(2004)给出了事务数据库的粗糙集表示[30],并详细讨论了事务性数据库的粗糙集压缩的信息损失问题,大大减少了后续的关联规则挖掘的搜索空间;刘发升等(1999)利用粗糙集泛化概念层次树,以约简所得的关联规则[31];Guan,J.W.等(2003)使用粗糙集方法挖掘文本数据库系统的关联规则[32]。

基于生物遗传算法的关联规则发现方法,利用遗传算法的自适应寻优及智能搜索技术获取与客观事实相容的关联规则。生物遗传算法需要首先确定染色体编码方案,然后确定适应度函数,最后确定遗传操作。通过遗传算子(如选择,交叉(重组)和变异等)来产生一群新的更适应环境的染色体,形成新的种群。许国艳等(2002)对图书馆借阅数据采用生物遗传算法挖掘关联规则[33]。

四、前沿研究

作为最成功的一种数据挖掘工具,关联规则挖掘得到了全面而深入的研究。目前,前沿研究主要有以下几个方面。

(一)时间—空间数据库

时间—空间关联规则(spatio-temporalassocia2tionrule),就是在关联规则的谓词集中加入空间谓词和时间谓词。这方面的研究主要集中在地理信息系统和地球科学等自然科学领域,由于时间—空间数据库的规模异常庞大,主要使用空间换时间的算法策略,在较短的时间内尽快挖掘出有效规则。

Tan,P.等(2001)采用时间序列的关联规则算法挖掘地球生态变化模式[34];Su,F.等(2004)采用空间分布式数据的关联规则算法挖掘生态关联规则,并对中国黄海区域的鱼群分布进行了实例分析[35]。

(二)Web挖掘

通常互联网站无法获取用户访问网页的完整行为,只能得到大量访问日志文件和网页链接的点击记录。因此,Web挖掘理所当然地成为数据挖掘的一个主要研究领域。现阶段的研究集中在Web内容挖掘和Web使用挖掘。关联规则作为Web挖掘的重要工具,既可通过分析Web日志文件和Web链接数据挖掘出用户的访问规律,也可作为Web内容聚类和检索的预处理步骤。有关的研究有李颖基等(2003)提出的基于Web拓朴概率模型和有趣关联规则的IAR算法[36],可对Web日志进行关联规则挖掘;宋擒豹等(2003)提出一种Web文档聚类算法[37],先采用向量空间模型表示主题,根据主题表示文档;再把文档作为事务,主题作为项,采用关联规则算法得到主题频繁集,以供后续的聚类操作;Xing,D.等(2004)将用户访问页面的停留时间和点击链接的顺序作为偏好程度,并以此提出UAM和PNT算法挖掘频繁浏览模式[38]。

(三)多媒体数据库

现在多媒体数据库的容量和规模快速增长,迫切地需要一个有效的查询技术以提高多媒体数据库的使用效率。可是,现代计算机图形技术提供的基于图形描述符的图形检索与用户输入的查询的概念描述仍然存在差距。这是因为:第一,低层次的图形特征关系无法准确反映用户查询的概念描述;第二,用户主观性也会导致概念描述的差异。此外,多媒体数据库本身也在不断完善之中,相应的数据库操作仍在研究之中,因此关联规则挖掘还局限在静态图像的范围内。

Za󰂧ane,O.R.等(1998)在基于OLAP技术的数据挖掘系统DBMiner和基于数字图书馆的图形检索系统C-BIRD基础上,建立了可挖掘高层次信息的多媒体数挖掘系统MultiMediaMiner[39],该系统采用数据立方体的数据组织形式并实现了关联规则挖掘在内的多种数据挖掘方法;Sánchez,D.等(2003)提出图像语言值学习模型[40],把图像的语言值作为图像的概念描述进行检索,使用图像的视觉属性来表征图像。通过模糊关联规则来描述特征与概念之间的关系,在图像语言值的层次上进行图像检索,用模糊关联规则的不确定性表示用户主观性。

(四)可视化挖掘

人类视觉系统是一个非常宽域的信息通道。可视化方法就是利用人类这一能力来发现并解释基于图形表示的数据模式和结构。因此关联规则发现过程的可视化就成为最具潜力的研究方向之一。

Kopanakis,I.等(2003)提出了并行的柱状图系统[41],利用柱状图各种特征(长度,颜色和背景等)实现数据降维和关联规则发现;Kimani,S.等(2004)提出VidaMine系统[42],向用户提供一致统一的可视界面,用户不仅能可视化地处理数据,还能够控制整个数据挖掘过程的方向。

五、总结与展望

本文首先对复杂数据组织形式的关联规则挖掘进行了详细的考察,随后探讨了其他学科领域对关联规则的理解及相应的研究方法。在较完整地回顾了关联规则在近十年内的产生、演进过程和现状之后,笔者认为关联规则未来的发展趋势大致有以下四个方向:

1关联规则算法体系的标准化,模块化。关联规则的定义较简单,虽然算法形式多变,但基本思想和策略变化不大。有必要建立一个系统的算法体系归纳总结现有的各种算法。该系统至少应满足:(1)各算法具有统一的数据输入和输出格式,(2)算法模块使用,(3)提供标准统一的算法测试平台。

2处理非结构化数据库。与具有明确的属性域取值的结构化数据不同,非结构化数据不具有明显的结构形式。如流式数据,多媒体数据和文本数据等。这类非结构化数据库的大量使用,无疑将引导关联规则研究进入一个全新的领域。

3辅助研究。在生命科学、天文科学、生态科学和环境科学等数据密集型的自然科学研究领域,关联规则可以提供高效的规律发现和模式识别方法,验证已有的和发现全新的经验和规律。可以预见,关联规则将成为科学研究的重要辅助工具。

4辅助决策。关联规则在医药、金融、商业和工业制造等领域的成功应用证明了关联规则的理论生命力和实际应用价值。如何将关联规则和其他的决策方法结合,为决策者提供科学有效的依据将成为关联规则研究中最具现实意义的课题。