关联规则挖掘Apriori算法综述

文献综述课程名称：科技写作与文献检索完成题目：关联规则挖掘Apriori算法综述专业班级：姓名：学号：完成时间：批阅时间：指导教师：成绩：关联规则挖掘Apriori算法综述摘要：关联规则挖掘是数据挖掘研究领域中的一个重要任务,随着大量数据不停的收集和存储,从数据库中挖掘关联规则变得极为重要。关联规则挖掘Apriori算法是关联规则挖掘中的一种经典算法。为此，本文对国内外有关Apriori算法的研究现状、算法的原理、优化算法的思想进行了探讨，综述了Apriori算法的主要优化方法,并指出了Apriori算法在实际中的应用领域,提出了未Apriori算法的研究方向和应用发展趋势。关键词：关联规则；数据挖掘；Apriori算法；综述Abstract：Theassociativeruleminingtechniqueisanimportanttechniqueindataminingresearch.Apriorialgorithmisaclassicalalgorithmofassociativerules.HowtodigouttherulesoftheassociateddatasetfromthedatabaseintheITdevelopmentprocessisimportantwithincreasingofmassivedatacollectionandstorage.InthispapertheprinciplesandoptimizationideaofApriorialgorithmarediscussedandseveralclassicaloptimizationalgorithmsareanalyzedatthesametime.Finallythetrendsoffuturedevelopmentareforecasted.Keywords：associativerules；massivedata；optimization；developmentaltrends1.引言数据挖掘也称数据库中的知识发现,是指从大型数据库或数据仓库中提取人们感兴趣的知识,这些知识是隐含的、事先未知的潜在有用信息,提取的知识一般可表示为概念、规则、规律、模式等形式[1]。大家知道,如今已可以用数据库管理系统来存储数据,还可用机器学习的方法来分析数据和挖掘大量数据背后的知识，而这两者的结合就促成了数据挖掘技术的产生。数据挖掘是一门交叉性的学科,涉及到机器学习、模式识别、归纳推理、统计学、数据库、数据可视化、高性能计算等多个领域。关联规则挖掘是数据挖掘中最活跃的研究方向之一，其本质是要找出隐藏在数据间的相互关系。Agrawal等于1993年设计了一个基本算法—Apriori算法[2]，首先提出了挖掘顾客交易数据库中项集间的关联规则问题，其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行思想等，以提高算法挖掘规则的效率；提出各种变体模型，如泛化的关联规则、周期关联规则等，对关联规则的应用进行推广。关联规则挖掘作为数据挖掘的重要研究内容之一，主要研究事务数据库、关系数据库和其他信息存储设施中的大量数据项之间隐藏的、有趣的规律。关联规则挖掘最初仅限于挖掘事务数据库的布尔型关联规则[3]，近年来广泛应用于关系数据库。因此，积极开展在关系数据库中挖掘关联规则的相关研究具有重要的意义。数据挖掘是一个在数据库领域中占比较重要地位的领域，国内外数据挖掘的发展趋势及其研究方向主要有知识发现方法的研究及其应用。目前大部分有关数据挖掘的研究文章主要集中在数据挖掘的数据总结、分类、聚类、关联规则等方面。关联规则挖掘作为数据挖掘的核心内容之一，近些年来得到了很快的发展，并成为了当今数据挖掘的热点。2.Apriori算法概述及研究现状Apriori算法是一种最有影响力的挖掘布尔关联规则的频繁项集的算法，它是由RakeshAgrawal和RamakrishnanSkrikant提出的。它使用一种称作逐层搜索的迭代方法，k-项集用于探索（k+1）-项集。首先找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L2，如此下去，直到不能找到k-项集。每找一个Lk需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。其运行定理在于一是频繁项集的所有非空子集都必须也是频繁的，二是非频繁项集的所有父集都是非频繁的。Apriori算法提出以后，很多研究人员对关联规则的挖掘问题进行了大量研究，特别是对关联规则挖掘算法进行了大量的研究和优化，如Savasere等人设计了一个基于划分的算法，Park等人提出的基于散列的算法，Mannila提出的基于采样的方法，Lin和Dunham提出的反扭曲算法，Brin等提出如何减少扫描数据库发现频繁项集算法等[4]。国内目前Apriori算法在应用方面较为成熟，也出现了很多对此算法的改进和优化，但与国外有关关联规则挖掘方法研究相比，我国对数据挖掘的研究相对较晚，有关数据挖掘的研究也只有十几年的时间，主要集中在部分实力相对较强的院校和研究机构，如中国科学院、清华大学、西安交通大学、上海交通大学及国防科技大学等。虽然对关联规则的研究才刚刚起步，但是近几年已经取得了可喜的成果。国内对关联规则挖掘所涉及的研究领域很多，主要集中在求关联规则频繁项集算法的研究、关联规则挖掘的实际应用以及关联规则挖掘理论方面的研究[5~6]。有着重要意义的研究项目有：中国科学院计算机研究所的多策略数据挖掘平台MSMiner系统和复旦大学研制开发的ARMiner系统，目前这两个系统已经在实际应用上取得了一定的成就。3.关于Apriori算法的几种优化方案虽然Apriori算法是关联规则挖掘的最经典的算法,它是采用取循序渐进的方式，一层一层地组合出侯选项目集[7]，并扫描数据库计算侯选项目集支持度与规则强度。虽然该算法已经将许多不可能成立的侯选项目集事先删除，以减少庞大的计算量，但是仍然需要不少的计算，而且需要多次扫数据库，所以对于在大型数据库系统，该算法的效率仍然不够好。许多学者就如何减少扫描数据库的次数以及减少I/O的负载做出了研究,提出了一些优化的算法。3.1基于划分的方法算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频集[8~9],然后合并产生的频集生成所有可能的频集,最后计算这些项集的支持度。这里分块的大小选择要使每个分块可放入主存,每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。3.2基于用户感兴趣项集重要性的方法首先从数据库中利用某些用户感兴趣的项,从数据库的所有项的集合中选择出一个子集作为挖掘对象,然后对数据库进行一次扫描[10~12],实现用事务标识号来表示项目集。在产生项目集后,对项目集中的元素赋以权值,然后利用引入了权值的支持度函数计算项集的支持度以产生频集,最后的工作就是从这些频集中产生关联规则。3.3基于划分的方法算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频集,然后合并产生的频集生成所有可能的频集,最后计算这些项集的支持度[13~14]。这里分块的大小选择要使每个分块可放入主存,每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的3.4基于矩阵的方法它主要是将矩阵的思想应用到Apriori算法当中,把事务数据库表示成矩阵的形式。具体方法为:对每一成员按一序列排列,事务集也按一序列进行排列。成员分别表示行向量,事务表示列向量,若第ｍ个成员在第ｎ个事务中,则矩阵的第ｍ行,第ｎ列的值为1,否则为0,称其为数据库的布尔矩阵。矩阵的行向量之和为成员出现的次数,则项集的支持记数可求出[15]。对于二项集{Ｍｍ,Ｎｎ}只需扫描第ｍ行与第ｎ行即可,它们同一列的值均为1的个数,即为二项集{Ｍｍ,Ｍｎ}的支持记数,依此类推。只需扫描矩阵的第ｍ1,ｍ2,…,ｍｋ行,它们同一列的值均为1的个数即为ｋ项集{Ｍｍ1,Ｍｍ2,…,Ｍｍｋ}的支持记数。3.5采用项编码方法该算法的主要思想是对所有的项,根据它在交易中出现的记录进行编码,在编码的同时就可以统计出项的支持度并生成频繁1-项集[16]。然后通过对不同编码进行“与”的运算来得到频繁二项集,并根据Apriori算法的大项目集性质修改简化编码。如此循环最终得到符合关联规则的频集。从以上描述可以看出该算法只需要扫描一遍数据库,并且大幅减少了侯选集数量。4.未来研究方向及应用发展趋势目前，随着信息量的不断更新变化，信息量的潜在的规则也在不断发生变化，因此，相关算法的研究十分复杂。对于关联规则挖掘的Apriori算法的未来研究方向，笔者经过总结认为，今后一段时间内可能在以下几个方向值得深入研究：一是如何提高算法效率；二是如何对算法进一步优化；三是在关联规则挖掘的过程中，如何与用户进行交互，在挖掘的过程中结合用户的领域知识，能在可视化的环境下产生。而对于关联规则挖掘的Apriori算法的应用趋势，可能涉及到以下几个方面的应用领域：一是挖掘父母学历的高低与子女的个数之间的关联规则，以便更好地制定计划生育政策，从而促进社会更好的发展；二是研究智能化设备，如靠识别语音的自动门等；三是工作效率与学历高低之间的关联规则挖掘；四是人的血型与成功几率之间的关联规则挖掘等。参考文献[1]FayyadUM,Piatetsky-shapiroG,SmythP.Advancesinknowledgediscoveryanddatamining.California:AAAI/MITPress,1996.[2]JiaweiHanandMichelineKamber著,范明,孟小峰等译.数据挖掘概念与技术[M].机械工业出版社,2006.[3]何军,刘红岩等.多关系关联规则挖掘研究综述[J].软件学报，2007.[4]丁一新.一种改进的关联规则挖掘技术研究[D].桂林理工大学,2010.[5]赵洪英,蔡乐才,李先杰.关联规则挖掘的Apriori算法综述[J].四川理工学院学报(自然科学版),2011.[6]崔贯勋,李梁等.关联规则挖掘中Apriori算法的研究与改进[J].计算机应用,2010.[7]邵峰晶,于忠清.数据挖掘原理与算法[M].北京:中国水利水电出版社,2003.[8]AGRAWALR,IMIELINSKIT,SWAMIA.Miningassociationrulesbetweensetsofitemsinlargedatabases[M].NewYork:ACMPress,1993:207-216.[9]黄进,尹治本.关联规则挖掘的Apriori算法的改进[J].电子科技大学学报,2003,32(1):76-79.[10]徐章艳,张师超,区玉明.挖掘关联规则中的一种优化的Aprior算法[J].计算机工程,2003,29(19):83-85.[11]李绪成,王保保.挖掘关联规则中的Apriori算法的一种改进[J].计算机工程,2002,28(7):104-105.[12]蔡伟杰,张晓辉,朱建秋.关联规则挖掘综述[J].计算机工程,2001.[13]刘君强,孙晓莹,潘云鹤.关联规则挖掘技术研究的新进展[J].计算机科学,2004,31(1):110-113.[14]张梅峰,张建伟.基于Apriori的有效关联规则挖掘算法的研究[J].计算机工程与应用,2003,39(19):196-198.[15]朱孝宇,王理东,汪光阳.一种改进的Apriori挖掘关联规则算法[J].计算机技术与发展,2006,16(12):89-90.[16]AGRAWALR,SRIKANTR.FastAlgorithmforminingassociationrulesinlargedatabase[C]//Proc1994IntC