下载文档原格式
Apriori ['eɪprɪ'ɔ:rɪ]Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。
而且算法已经被广泛的应用到商业、网络安全等各个领域。
其核心是基于两阶段频集思想的递推算法。
该关联规则在分类上属于单维、单层、布尔关联规则。
在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。
经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。
Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。
通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。
百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。
Apriori算法应用于网络安全领域，比如网络入侵检测技术中。
早期中大型的电脑系统中都收集审计信息来建立跟踪档，这些审计跟踪的目的多是为了性能测试或计费，因此对攻击检测提供的有用信息比较少。
它通过模式的学习和训练可以发现网络用户的异常行为模式。
采用作用度的Apriori算法削弱了Apriori 算法的挖掘结果规则，是网络入侵检测系统可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高了基于关联规则的入侵检测系统的检测性。
Apriori算法应用于高校管理中。
随着高校贫困生人数的不断增加，学校管理部门资助工作难度也越加增大。
针对这一现象，提出一种基于数据挖掘算法的解决方法。
将关联规则的Apriori算法应用到贫困助学体系中，并且针对经典Apriori挖掘算法存在的不足进行改进，先将事务数据库映射为一个布尔矩阵，用一种逐层递增的思想来动态的分配内存进行存储，再利用向量求"与"运算，寻找频繁项集。
Apriori ['eɪprɪ'ɔ:rɪ]Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。
而且算法已经被广泛的应用到商业、网络安全等各个领域。
其核心是基于两阶段频集思想的递推算法。
该关联规则在分类上属于单维、单层、布尔关联规则。
在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。
经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。
Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。
通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。
百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。
Apriori算法应用于网络安全领域，比如网络入侵检测技术中。
早期中大型的电脑系统中都收集审计信息来建立跟踪档，这些审计跟踪的目的多是为了性能测试或计费，因此对攻击检测提供的有用信息比较少。
它通过模式的学习和训练可以发现网络用户的异常行为模式。
采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则，是网络入侵检测系统可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高了基于关联规则的入侵检测系统的检测性。
Apriori算法应用于高校管理中。
随着高校贫困生人数的不断增加，学校管理部门资助工作难度也越加增大。
针对这一现象，提出一种基于数据挖掘算法的解决方法。
将关联规则的Apriori算法应用到贫困助学体系中，并且针对经典Apriori挖掘算法存在的不足进行改进，先将事务数据库映射为一个布尔矩阵，用一种逐层递增的思想来动态的分配内存进行存储，再利用向量求"与"运算，寻找频繁项集。
数组在apriori算法改进中的应用摘要 apriori算法是经典的关联规则挖掘算法，该算法存在的一个缺陷就是多次扫描数据库需要大量的io操作。
文章提出了应用数组来减少apriori算法的io操作，从而提高apriori算法的效率。
关键词数组；apriori；算法；数据库中图分类号tp392 文献标识码a 文章编号 1674-6708（2013）93-0227-020引言数据挖掘（data mining，简称 dm）就是从大量的、不完全的数据中，提取隐含在其中的有用信息的过程。
数据挖掘的一个重要研究方向就是关联规则挖掘，其目的就是为了发现事务之间的关联关系，并利用发现的关联关系来指导人们工作。
apriori算法是关联规则挖掘中的一个经典算法，该算法是由r.araw等人于1994年提出，并在超市销售活动的购物分析中得到充分应用。
关联规则挖掘涉及到最小支持度和最小置信度两个度量标准，只有关联规则的支持度和置信度都分别大于等于最小支持度和最小置信度时，这样的关联规则才是人们感兴趣的关联规则，也称为强关联规则。
关联规则挖掘分为两个步骤：首先，根据最小支持度标准查找事务数据库中的频繁项集，然后根据最小置信度由频繁项集生成强关联规则，其中的第一个步骤生成频繁项集是关联规则生成的关键步骤，影响关联规则的整体挖掘效率。
apriori算法就是为了发现关联规则挖掘中的频繁项集，因此，对aprior算法进行改进就可以促进关联规则挖掘效率的提高。
1 apriori算法1.1 apriori算法基本思想apriori算法是通过逐层迭代的方法来产生频繁项集，首先扫描数据库，根据最小支持度生成1项频繁项集，然后由1项频繁项集与自身进行连接操作生成2项候选项集，再一次扫描事务数据库，根据最小支持度生成2项频繁项集，然后再由2项频繁项集与自身进行连接操作生成3项候选项集，再进行数据库扫描根据最小支持度来生成3项频繁项集，以此类推，直到生成的候选项集或频繁项集为空，则该算法结束。
Apriori算法中频繁项集求法的改进
摘要：分析传统apriori效率较低的原因，采用0-1矩阵改进数据库事务集的描述，提高apriori中统计匹配的时间效率；分析各频繁项集的计数，改进传统apriori算法完全从低维频繁项集产生高维频繁项集的方式，通过先求出1项频繁集和最大频繁项集，减少中间的频繁项集剪枝数量，从而达到提高算法效率的目的。
关键词：0-1矩阵；统计匹配；剪枝
1 关联规则[1]挖掘及apriori算法概述
一提到关联规则挖掘就会令人联想到“尿布与啤酒”的故事，这是借助数据挖掘技术对大量原始交易数据进行分析揭示的一条规律。
apriori[2]算法是由美国学者r. agrawal等在1993年提出的一种从大规模商业数据中挖掘关联规则的有效方法。
现在已经被广泛用于商业决策、社会科学、科学数据处理等各种各样的数据挖掘领域之中。
使用基于支持度的剪枝技术，系统地控制候选项集指数增长。
其核心是使用候选项集找频繁项集。
算法具体的执行步骤如下：
（1）根据用户的要求确定最小支持度和最小置信度；（2）找出所有的频繁项集：先由数据库读入所有的数据项，得出候选1项集c1，然后根据最小支持度要求确定频繁1项集l1；使用l1与l1自连接产生候选2项集c2，继续对数据库扫描，得出候选2项集c2的支持度，确定频繁2项集l2；继续执行上述的步骤，不断进行连接与剪枝，重复对数据库的扫描，并和最小支持度进行比较，产生
更高层次的频繁项集，直到不再产生新的候选频繁项集为止；（3）根据频繁项集产生强关联规则。
2 apriori算法的缺点及改进方法
apriori算法能够有效地进行数据关联规则挖掘，但该算法存在效率不高的问题。
该算法使用迭代方法，通过低维频繁项集产生高维频繁项集，该算法存在两个比较明显的缺点：一个是可能产生大量的候选集，时间开销和空间开销都很大；另一个是需要多次扫描数据库，需要很大的 i/o开销。
2.1 采用0-1矩阵描述数据库事务集
设i={i1，i2，…，in}是项的集合，d是数据库事务集，其中每个事务t是项的集合，使得t？哿i。
按如下规则用0-1矩阵描述数据库事务集：如果i中某一项ik在事务t中存在，用“1”表示，否则就用“0”表示。
数据库事务集d就转化为m*n矩阵的0-1矩阵，其中m为数据库事务集d的大小，即包含多少个事务，n为集合i的计数。
采用0-1矩阵描述数据库事务集能带来如下好处：
（1）运算简单；便于统计，横向统计“1”的个数就是事务t包含的项数，纵向统计“1”的个数就是1项集的统计数；（2）使用0-1矩阵算法，提高统计项集时候的匹配效率，传统的统计匹配效率正比于n，采用0-1矩阵匹配时间效率正比于n；（3）减少对数据库的扫描，排序后，求频繁k项集的时候，统计项集时不需要扫描数据库，只需要统计包含大于等于k个项目数的事务；（4）易于
对数据库事务集按事务包含的项目数大小降序排序；（5）易于求出最大频繁项集。
2.2 改进后的算法 myapriori描述
要提高apriori算法的效率，一般来说就是要考虑两个方面的问题：一是减少对数据库的扫描，二是在剪枝的时候减少统计项集的次数。
采用0-1矩阵，并排序以后，可以减少对数据库的扫描，在求k项频繁项集时候，只需要扫描包含大于等于k个项目的项集，不需要扫描全部的数据库。
传统apriori算法采用从频繁1项集开始，由频繁k-1项集产生频繁k项集，中间产生大量候选集，对这些候选集要进行统计并剪枝，运算量大；通过多次试验发现：对于1项频繁集，2项频繁集，……，m-1项频繁集，m项频繁集（m项频繁集为最大频繁项集），其数量分布有一定规律，就是两头的数量相对较少，尤其是最大频繁项集数量不多，中间频繁项集的数量较多，数量分布整体呈现为“纺锤状”。
可以先通过统计的方法求出最大频繁项集，然后利用“频繁项集的所有非空子集一定也是频繁的”这一定理，再由k-1项频繁项集产生k项频繁项集时，剔除最大频繁项集的子集的项集，只需要统计分析剩余的项集是否为频繁项集即可，减少了剪枝的运算量，优化算法。
算法myapriori：输入原始数据库事务集矩阵a，输出0-1矩阵fi表示的各项频繁项集。
上述算法的优点：在减少了剪枝的运算量，减少了数据库的扫描次数；缺点是对原始数据库0-1化处理、排序和统计产生最大频繁
maxfi增加了额外开销，其中0-1化处理、排序要对数据库各扫描1次，统计产生最大频繁maxfi也需要对数据库进行扫描；其中0-1化处理、排序增加的开销并不是很大，统计产生最大频繁maxfi可能会带来较大的开销。
总体来说，从时间效率上来讲，改进的算法优于传统的算法，尤其在maxfi比较容易求取的情况下；从空间效率来讲，改进后的算法要用到counta01、cca01、sa01等矩阵，效率会有所降低。
2.3 myapriori算法性能分析与实验
对某关于公积金数据库事务集{{t1：i1，i3，i4，i6}；{t2：i2，i3，i4}；{t3：i1，i2，i3；}；{t4：i2，i6}；{t5：i2，i3，i4，i5}；{t6：i2，i3，i5}；{t7：i1，i2，i3，i4，i6}；{t8：i1，i3，i4，i5，i6}；{t9：i1}；{t10：i1，i5}，令sup=0.3：
采用传统apriori算法，求1项频繁集时，有6个候选频繁项集，每个项集需要与原数据库匹配1次，原始数据库大小为10项，要匹配6*10=60次，得到6个1项频繁集；求2项频繁集时，产生c62=15个候选频繁项集，每个项集需要与原数据库匹配1次，原始数据库大小为10项，要匹配15*10=150次，得2项频繁集有9项；求3
项频繁集时，产生13个候选频繁项集，每个项集需要与原数据库匹配1次，原始数据库大小为10项，要匹配13*10=130次，得3
项频繁集有5项；求4项频繁集时，产生3个候选频繁项集，每个项集需要与原数据库匹配1次，原始数据库大小为10项，要匹配3*10=30次，得4项频繁集有1项，4项频繁集即为最大频繁项集。
在上述过程中，共计需要匹配的次数为：60+150+130+30=370。
采用改进后的算法myapriori算法，求1项频繁项集匹配60次，2项频繁项集匹配96次，3项频繁项集匹配76次，4项频繁项集匹配4次，共计匹配236次，加上扫描2遍数据库，可近似计为2*10次=20次，总计为236+20=256次，小于传统apriori算法的370次；减少了对数据库的扫描和剪枝的运算量。
实验验证：采用matlab编程，2g内存，2.5g双核cpu， windows xp环境；使用gjj数据库，采用传统apriori算法和改进后的myapriori算法各运行10000次，时间分别为0.3440ms和0.2950ms，可以得出改进后的算法更快。
参考文献
[1]jiawei han micheline kamber著.范明，孟小峰.数据挖掘概念与技术（加）[m].机械工业出版社，2008年12月.
[2]agrawal r，imielinskit， swami a.mining association rules between sets of items in large databases. proceedings of acmsigmod conference on management of data，1993：207-216.。
