Apriori算法研究

Apriori算法研究Apriori算法是一个挖掘关联规则的算法，是Agrawal等设计的一个基本算法。它采用两阶段挖掘的思想，并且基于多次扫描事务数据库来执行。1. 关联规则1.1. 基本概念关联规则是形如 X Y 的蕴涵式，表示通过 X 可以推导 “ 得到 ” Y ，其中 X 和 Y 分别称为关联规则的先导 (antecedent 或 left-hand-side, LHS) 和后继 (consequent 或 right-hand-side, RHS)。关联规则 A-B 的支持度 support=P(AB) ，指的是事件 A 和事件 B 同时发生的概率。置信度 confidence=P(B|A)=P(AB)/P(A), 指的是发生事件 A 的基础上发生事件 B 的概率。同时满足最小支持度阈值和最小置信度阈值的规则称为强规则 。如果事件 A 中包含 k 个元素，那么称这个事件 A 为 k 项集， 并且事件 A 满足最小支持度阈值 的事件称为频繁 k 项集 。1.2. 挖掘过程第一，找出所有的频繁项集；其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。第二，由频繁项集产生强规则。其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称为强规则。通常，频繁项集产生的计算开销远大于产生规则所需的计算开销。2. Apriori算法思想Apriori 算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法， k 项集用于探索 (k+1) 项集。首先，通过扫描事务（交易）记录，找出所有的频繁 1 项集，该集合记做 L1 ，然后利用 L1 找频繁 2 项集的集合 L2 ， L2 找 L3 ，如此下去，直到不能再找到任何频繁 k 项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。其中， Apriori 算法具有这样一条性质 ：任一频繁项集的所有非空子集也必须是频繁的。因为假如 P(I)1），具体做法是：在挖掘出候选频繁k-项集（Ck）之后，根据最小置信度minSup来筛选，得到频繁k-项集。最后合并全部的频繁k-项集（k0）。挖掘频繁项集的算法描述如下：算法 Apriori算法的频繁集产生1: L1 = find_frequent_1-itemsets(D); / 挖掘频繁1-项集，比较容易2: for (k=2;Lk-1 ;k+) 3: Ck = apriori_gen(Lk-1 ,min_sup); / 调用apriori_gen方法生成候选频繁k-项集4: for each transaction t D / 扫描事务数据库D5: Ct = subset(Ck,t);6: for each candidate c Ct7: c.count+; / 统计候选频繁k-项集的计数8: 9: Lk =c Ck|c.countmin_sup / 满足最小支持度的k-项集即为频繁k-项集10: 11: return L= k Lk; / 合并频繁k-项集（k0）Apriori算法的频繁项集产生的部分有两个重要的特点：第一，它是一个逐层算法，即从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层；第二，它使用产生-测试策略来发现频繁项集。在每次迭代之后，新的候选项集都由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最小支持度阈值进行比较。该算法需要的总迭代次数是kmax+1，其中kmax是频繁项集的最大长度。3.2. 挖掘频繁关联规则基于第1步挖掘到的频繁项集，继续挖掘出全部的频繁关联规则。置信度大于给定最小置信度minConf的关联规则称为频繁关联规则（Frequent Association Rule）。在这一步，首先需要从频繁项集入手，首先挖掘出全部的关联规则（或者称候选关联规则），然后根据minConf来得到频繁关联规则。挖掘频繁关联规则的算法描述如下：算法 挖掘频繁关联规则1: 初始状态 ： L = k Lk; AR = ; / L是频繁项集集合，AR是频繁关联规则集合2: for all k （k是L的元素，是一个k-频繁项集，大小为n）1. for all k （k是k 的非空真子集）i. if(k m的置信度= minConf) / 这里，m + k = n，其中k m是一个关联规则a) AR = AR (k m);ii. 2. 3: 4: return AR;4. Apriori算法计算复杂度1.2.3.4.4.1. 影响因素Apriori算法计算复杂度受如下因素影响。支持度阈值 降低支持度阈值通常将导致更多的频繁项集。这给算法的计算复杂度带来不利影响，因为必须产生更多候选集并对其计数。随着支持度阈值的降低，频繁项集的最大长度将增加。而随着频繁项集最大长度的增加，算法需要扫描数据集的次数也将增多。项数（维度） 随着项数的增加，需要更多的空间来存储的支持度计数。如果频繁项集的数目也随着数据维度增加而增长，则由于算法产生的候选项集更多，计算量和I/O开销将增加。事务数 由于Apriori算法反复扫描数据集，因此它的运行时间随着事务数的增加而增加。事务的平均宽度 对于密集数据集，事务的平均宽度可能很大，这将在两个方面影响Apriori算法的复杂度。首先，频繁项集的最大长度随事务平均宽度增加而增加，因而，在候选项产生和支持度计算时必须考察更多候选项集；其次，随着事务宽度的增加，事务中将包含更多的项集，这将增加支持度计数时Hash树的遍历次数。4.2. 时间复杂度频繁1-项集的产生 对于每个事务，需要更新事务中出现的每个项的支持度计数。假定w为事务的平均宽度，则该操作需要的时间为O(Nw)，其中N为事务的总数。候选的产生 为了产生候选k-项集，需要合并一对频繁(k-1)-项集，确定它们是否至少有k-2个项相同。每次合并操作最多需要k-2次相等比较。在最好情况下，每次合并都产生一个可行的候选k-项集；在最坏的情况下，算法必须合并上次迭代发现的每对频繁(k-1)-项集。因此，合并频繁项集的总开销为：k=2w(k-2)Ck合并开销k=2w(k-2)Fk-12Hash树在候选产生时构造，以存放候选项集。由于Hash树的最大深度为k，将候选项集散列到Hash树的开销为O(k=2wkCk)。在候选项剪枝的过程中，需要检验每个候选k-项集的k-2个子集是否频繁。由于在Hash树上查找一个候选的花费是O(k)，因此候选剪枝需要的时间是O(k=2wk(k-2)Ck)。支持度计数 每个长度为|t|的事务将产生Ctk个k-项集。这也是每个事务遍历Hash树的有效次数。支持度计数的开销为O(NkCwkk)，其中w是事务的最大宽度，k是更新Hash树中一个候选k-项集的支持度计数的开销。5. Apriori算法应用经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。Apriori算法应用于网络安全领域，比如时候入侵检测技术中。它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则，是网络入侵检测系统可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高了基于关联规则的入侵检测系统的检测性。Apriori算法应用于高校管理中。随着高校贫困生人数的不断增加，学校管理部门资助工作难度也越加增大。针对这一现象，提出一种基于数据挖掘算法的解决方法。将关联规则的Apriori算法应用到贫困助学体系中，并且针对经典Apriori挖掘算法存在的不足进行改进。实验结果表明，改进后的Apriori算法在运行效率上有了很大的提升，挖掘出的规则也可以有效地辅助学校管理部门有针对性的开展贫困助学工作。Apri