Apriori算法的改进及应用

实践与经验Apriori算法的改进及应用叶福兰1施忠兴(1.福州外语外贸职业技术学院计算机信息系,福州350018;2福州外语外贸职业技术学院图书馆,福州350018)摘要:描述Apon算法并指出其缺点,提出利用哈希技术及压缩组合项集技末对 Apriori算法进行改进,结合实例详蛔介绍改进的基本思想及具体过程,利用实验对改进算法的效率进行分析,提出改进算法在图书馆个性化服务中的应用关键词:Apon算法;改进;个性化服务1 Apriori算法描述及缺点有事务中出现的概率是期望置信度;而Y在有Ⅹ出Apriori算法是第一个关联规则挖掘算法,它开创现的事务中出现的概率是置信度,通过置信度对期望性地使用基于支持度的剪枝技术,系统地控制候选项置信度的比值反映了在加入“X出现”的条件后,Y的集指数增长,是最有影响的挖掘布尔型频繁项目集的出现概率发生了多大的变化。在上例中作用度为70%算法,是所有关联规则挖掘算法的核心,其基本思想20%=3.5。是重复扫描数据库,根据一个频繁集的任意子集都是定义3由关联挖掘到相关性分析频繁集的原理,可以从长度为k的频繁集迭代地产生大部分关联规则挖掘算法都使用支持度-置信度长度为k+的候选集,再扫描数据库以验证其是否为框架。尽管最小支持度和置信度阈值能够排除大量无频繁集。趣的规则,但是仍然会产生一些用户不感兴趣甚至是Aprior算法在数据挖掘中具有里程碑的作用,但误导的关联规则。是存在着以下缺点如果P(AUB)=P(AP(B),项集A的出现依赖于(1)频繁扫描事务数据库;(2)不适于大型数据库项集B的出现。A与B出现的相关性由下式度量:的关联规则挖掘;(3)不适于稠密集的关联规则挖掘PuB) PA PBCOTAR(1)(4)可能生成的关联规则过于庞大;(5) Apriori算法的若corA<1则负相关;cor=1则独立(没有相关适应面较窄。性); ctAb>1则正相关(一个出现蕴涵另一个的出2相关概念现)。定义1期望置信度( Expected Confidence)3对减少计算支持度计数的工作量上的改进设事务T中有e%的事务支持项集Y,e%称为关联规则=>Y的期望置信度。期望置信度描述了在没31相关性质有任何条件影响时,Y在所有事务中出现的概率有多性质1对于一个k-项集I,若包含I1,r2],…I大。如果某天共有1000个顾客到商场购买物品,其中k1的事务集合分别为TTn,…,T,则包含I的|有200个顾客购买了牛奶,则上述的关联规则的期望事务集合为T。置信度为20%。性质1说明包含一个项集的事务集合等于包含定义2作用度(Iif)该项集的元素的事务的交集,因此我们只要知道所有作用度是置信度与期望置信度的比值。作用度描包含项的事务,就可以求出包含该项集的事务,进而述X的出现对Y的出现有多大的影响。因为Y在所知中国煤化工收稿日期:2009-07-02修稿日期:2009-08-25CNMHG作者简介:叶福兰(1981-),女,研究生,研究方向为数据挖掘MODERN COMPUTER 2009.995实践与经验3.2改进算法的基本思想表2哈希表(1)首先,逐个扫描事务数据库,产生1-项候选支持度计数集合C1,在扫描每个事务时,除了记录包含该项的事TTA TTT,务编号外,还要对每个项计数。这样扫描完一遍数据库后,得到的候选集C1中,每个项集都包含一个相应的事务编号列表及对应的事务数,用哈希表来表示该项的支持度计数即为该项所包含的事务数。哈希表的结构为:(项集 Item set,事务标识符列表 Tid list,支表3频繁1-项集L1持度计数 support);(2)从C1中删除不满足最小支持支持度计数度计数项集,得到L;(3)L41进行自然连接,生成C,对C的计数根据性质1利用C1求得。对于2-项集L的生成,无须扫描事务数据库只要扫描哈希表第i行和第j行中相同元素的个数若要计算K-项集[LJ…l}的支持度计数,只要扫描对于2-项集的生成,由频繁1-项集自然连接生Hash表中第,k行相同元素个数即可。成2-项集,对于2-项集中各项的支持度计数只需判由此可见,此方法在计算支持度计数时,只需扫断项中元素所在行的公共事件数目,即为支持度计数描Hash表的部分行,无需对Hash表全部扫描,也不值。例如2-项集(文学,工业},只要在哈希表中扫描文需要扫描整个数据库,从而使 Apriori算法的效率大学所在的行及工业所在行,找出相同的事务编号个大提高,实现高效挖掘频繁项集的目的。数,因文学行中的事务编号为T,T4T,工业行中的事33政进算法举例务编号为T,TTT发现无公共事务,所以(文学下面以具体实例说明哈希表的构建过程及频繁工业的支持度计数值为0同理可求出其他2-项集及项集的产生,表1是某高校读者的借阅信息,设最小对应的支持度计数,结合最小支持度计数,得到频繁支持度计数为3:2-项集,如表4所示表1读者借阅信息表表4频繁2一项集I2支持度计借闻1借2借网3借闵4高数候选3项集的生成由I2直接连接而成,各项的支算机■■外迅业外持度计数为各项所在行的公共事务数,结合最小支持业高数■综合外诉度计数及先验原理,得到频繁3项集,如表5所示表5频繁3-项集以读者借阅图书为依据,首先扫描读者借阅信息现|数据库,产生C,包含项集及对应的事务编号将其用匚持度计教高数,计算机,外语代|哈希表列出,表中各行元素为各图书所在项的事务编计号,支持度计数为该行的事务数。例如高数出现在事4对减少频繁项集的进一步改进务 TIT3TtT,T9中,则高数行的元素为(TTTT事务数为5,即支持度计数为6。依此类推,创建计算性质2如果频繁k-项集还能产生频繁k+1项集总机,工业,外语综合,文学所在行的元素生成的哈希则频繁k+1项集中包含某项的个数必大于或等于k。第表如表2所示。由性质2,可以实现对该集中出现元素个数进行计从表可得到1-项集,其中第(1≤i≤6项的支持数事中国煤化工个数不到k的话可以度计数为第i行元素的个数,并结合最小支持度计数CNM引起的所有组合。3得到频繁1-项集C,如表3所示对支持度计数筛选得MODERN COMPUTER 2009.996实践与经验到,要求某项在各项在L4中出现次数大于或等于k,置信度和作用度加以判断分析,经筛选得出的关联规若小于k,则删除该项并在L中删除所有包含已经淘则见表7所示汰掉的元素的事务记录,处理过程如表6所示,步骤时间耗费(单位你)1中要求各项出现次数大于或等于1,步骤2中要求各项出现次数大于或等于2,例如(文学}与{工业在L2中出现的次数为1,则删除{文学)与(工业},并删除L有包含这两项的项(文学,计算机与(工业,外语}表6处理过程限频L各在L肀幽现次傲「瓢集L计算机计算机事务集记录数(单位:条文学,计算机高数,计算机计算机图1计算机,外语{外语除(文学与1业})3■高数,计算机,外语」表7筛选得出的关联规则5改进算法与 Apriori算法的比较里信度期望置信度作用度通过上述介绍,可以看到改进的算法与 Aprior算法的共同之处是通过扫描数据得到那些支持度不今界机外语小于用户给定的最小支持度 Minsupport的频繁项集规则高数,计算机]=>(外语},置信度为100%,作l4,不同之处在于:第一,改进的算法首先将数据库变用度为1.29,说明高数,计算机)与{外语}是正相关换成了Hash表,因此,在计算支持度时仅需对k-项的,即读者借阅高数,计算机图书的同时有借阅外语集中出现的项进行扫描,无需对整个Hash表扫描;第图书的趋势;规则(高数外语}=>(计算机的置信度虽二,改进的算法在考虑组合候选项目集C前,对将参然为60%,作用度为09(小于1),这样的关联规则没与组合的元素进行计数处理,根据计数结果决定排除有意义;规则(计算机,外语)=>{高数)的置信度为些不符合组合条件的元素,这就降低了组合的可能75%,作用度为1.35,说明借阅计算机和外语的读者性,直接减少了循环判断的次数。很有可能再借高数;规则{高数=>(计算机,外语)的置6算法实验分析信度为60%,作用度为135,意味着读者借阅高数图为了证实对 Apriori算法改进后的效果,实验采用书同时蕴涵再借计算机和外语的趋势ⅡASS系统中的真实借阅数据,进行图书关联性的挖参考文献掘。在事务较少的情况下, Apriori算法的性能较好,但是随着事务数的增加,改进的 Apriori算法的效率明显[鲍静.关联规则挖掘及其在图书流通数据中的应用研究优于未改进的算法,两种算法的效率比较如图1所示。硕士学位论文合肥:合肥工业大学,20072]姜晗.关联规则的精简方法研究[硕士学位论文]浙江7改进的 Apriori算法在图书馆个性化服浙江师范大学,2005务中的应用广武数据挖掘技术在教务管理系统中的应用硕士学计位论文]辽宁:辽宁科技大,2007预测读者的信息需求,挖掘数据背后隐藏的信息李绪成,王保保控据关联规则中Apio算法的一种改机掌握读者借阅规律,是图书馆开展个性化服务的基础。进计算机工程,2002,7(28):104-105读者借阅数据经过改进的 Apriori算法过程,得5陆觉民,郑字数据挖掘技术的改进在图书馆个性化服务第到所需要的频繁集I={高数,计算机,外语},可得对中国煤化工08,65-67应的关联规则及相应的置信度,在此基础上再给出置信度为55%对频繁项目集产生强关联规则,并以期望a yHsCNMHG厘系统中的应用硕士学川人于,∠(下转第126页)MODERN COMPUTER 2009.9实践与经验性,如何改善供应链各节点的脆弱性,如何更有效地降3王进发李励.军事供应链管理.国防大学出版社2004低集中管理和数据共享带来的安全风险,军队后勤人[4]Sherbrooke, C.C., 1992, Optimal Inventory Modelling of才的培养等,这些在以后的工作中都需要进一步研究。Systems: Multi-Echelon Techniques, Wiley, NewYork[5]Pyke, D F, 1990"Priority Repair and Dispatch Policies for参考文南Repairable Item Logistics System", Naval Researeh Lo-曾洪宁韩永生,杨青,基于供应链的企业应用集成研究gisties37, 1-30计算机应用研究,2007(增刊)6万杰寇纪淞,李敏强供应链中分配机制对牛鞭效应的[2]宋华.电子商务与电子供应链管理.人民大学出版社影响研究.系统工程学报,2002,172004Research on Logistics System IntegrationBased on Supply ChainHUANG SenLIU Feng(The Second Artillery Engineering University, Xi'an 710025)Abstract For currently the information island between users, begetter, depot and maintenance depart-and the demand forn,puts forward a descheme of integration which can improve the efficiency and save the outlay of logistics.(上接第97页)Improvement and Application of Apriori algorithmu-lanSHI Zhong-xing(1. Department of Computer Information, Fuzhou Technical College of Foreign Studies, Fuzhou 3500182. Library of Fuzhou Technical College of Foreign Studies, Fuzhou 350018)Abstract: Describes Apriori algorithm and pointes out its disadvantages and puts forward the use ofhash combination of technology and compression technology to Apriori itemset algorithmimprovements, combines with detailed examples to improve the basic idea and the specific第三一五期processes, analyzes the use of experiments foralgorithm proposed in the library of中国煤化工Keywords: Apriori Algorithm; Improvement; PersonalizedYHECNMHGMODERN COMPUTER 2009.9126