关联算法aprior毕业论文

Apriori算法的主要思想是找出存在于事物数据集中的最大频繁项集，再利用得到的最大频繁项集与预先设定的最小置信度阈值生成强关联规则。 项集是项的集合。包含k个项的项集成为k项集。项集的出现频率是所有包含项集的事务计数，又称为绝对支持度或支持度计数。如果项集I的相对支持度满足预定义的最小支持度阈值，则I是频繁项集。频繁k项集通常记作k。 项集A、B同时发生的概率称为关联规则的支持度（也称为相对支持度）。 项集A发生，则项集B发生的概率为关联规则的置信度。 最小支持度是用户或专家定义的衡量支持度的一个阈值，表示项目集在统计意义上的最低重要性；最小置信度是用户或专家定义的衡量置信度的一个阈值，表示关联规则的最低可靠性。同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。 项集A的支持度计数是事务数据集中包含项集A的事务个数，简称为项集的频率或计数。 频繁项集哦的所有非空自己也必须是频繁项集。根据该性质可以得出：向不是频繁项集I的项集中添加事务A，新的项集I U A一定也不是频繁项集。 1）找出所有的频繁项集（支持度必须大于等于给丁的最小支持度阈值），在这个过程中连接步和剪枝步互相融合，最终得到最大频繁项集Lk。 连接步的目的是找到K项集，对给定的最小支持度阈值，分别对1项候选集C1，剔除小于该阈值的项集得到1项频繁项集L1；下一步由L1自身连接产生2项候选集C2，保留C2中满足约束条件的项集得到2项频繁集，记为L2；再下一步由L2与L3连接产生3项候选集C3，保留C2中满足约束条件的项集得到3项频繁集，记为L3···这样循环下去，得到最大频繁项集Lk。 剪枝步紧接着连接步，在产生候选项Ck的过程中起到减小搜索空间的目的。由于Ck是Lk-1与L1连接产生的，根据Apriori的性质频繁项集的所有非空子集也必须是频繁项集，所以不满足该性质的项集不会存在于Ck中，该过程就是剪枝。 2）由频繁项集产生强关联规则：由过程1）可知未超过预定的最小支持度阈值的项集已被提出，如果剩下这些规则又满足了预定的最小置信度阈值，那么就挖掘出了强关联规则。

关联规则的目的在于在一个数据集中找出项之间的关系，也称之为购物篮分析 (market basket analysis)。例如，购买鞋的顾客，有10%的可能也会买袜子，60%的买面包的顾客，也会买牛奶。这其中最有名的例子就是"尿布和啤酒"的故事了。        本篇的Apriori算法主要是基于频繁集的关联分析。其主要目的就是为了寻找强关联规则。        要理解频繁集、强关联规则，要先借助下面的一个情境，来介绍几个重要概念。         下表是一些购买记录： 将购买记录整理，可得到下表，横栏和纵栏的数字表示同时购买这两种商品的交易条数。如购买有Orange的交易数为4，而同时购买Orange和Coke的交易数为2。         置信度，表示这条规则有多大程度上值得可信。         设条件的项的集合为A,结果的集合为B。置信度计算在A中，同时也含有B的概率。即Confidence(A->B)=P(B|A)。例 如计算"如果Orange则Coke"的置信度。由于在含有Orange的4条交易中，仅有2条交易含有Coke。其置信度为。         支持度，计算在所有的交易集中，既有A又有B的概率。         例如在5条记录中，既有Orange又有Coke的记录有2条。则此条规则的支持度为2/5=。现在这条规则可表述为，如果一个顾客购买了Orange,则有50%的可能购买Coke。而这样的情况（即买了Orange会再买Coke）会有40%的可能发生。支持度大于预先定好的最小支持度的项集。        关联规则：令项集I={i1,i2,...in}，且有一个数据集合D，它其中的每一条记录T，都是I的子集。那么关联规则是形如A->B的表达式，A、B均为I的子集，且A与B的交集为空。这条关联规则的支持度：support = P(A并B)。这条关联规则的置信度：confidence = support(A并B）/suport(A)。        强关联规则：如果存在一条关联规则，它的支持度和置信度都大于预先定义好的最小支持度与置信度，我们就称它为强关联规则。下面用一个例子说明算法的过程： 项目集合 I={1，2，3，4，5}; 事务集 T： 设定最小支持度（minsup）=3/7，最小置信度（misconf）=5/7。假设：n-频繁项目集为包含n个元素的项目集，例如1-频繁项目集为包含1个元素的项目集 则这里，1-频繁项目集有：{1}，{2}，{3}，{4}，{5} 生成2-频繁项目集的过程如下：         首先列出所有可能的2-项目集，如下：         {1，2}，{1，3}，{1，4}，{1，5}         {2，3}，{2，4}，{2，5}         {3，4}，{3，5}         {4，5}         计算它们的支持度，发现只有{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{2，5}的支持度    满足要求，因此求得2-频繁项目集：         {1，2}，{1，3}，{1，4}，{2，3}，{2，4} 生成3-频繁项目集： 对于现有的2-频繁项目集，两两取并集，并确保第三个二元组也在2-频繁项目集内，把得到的所有3-项目集分别计算支持度，剔除不满足最小支持度的项目集； 例如， {1，2}，{1，3}的并集得到{1，2，3}； {1，2}，{1，4}的并集得到{1，2，4}； {1，3}，{1，4}的并集得到{1，3，4}； {2，3}，{2，4}的并集得到{2，3，4}；但是由于{1，3，4}的子集{3，4}不在2-频繁项目集中，所以需要把{1，3，4}剔除掉。{2，3，4} 同理剔除。 然后再来计算{1，2，3}和{1，2，4}的支持度，发现{1，2，3}的支持度为3/7 ，{1，2，4}的支持度为2/7，所以需要把{1，2，4}剔除。因此得到3-频繁项目集：{1，2，3}。 重复上面步骤继续寻找n-频繁项目集，直到不能发现更大的频繁项目集。所以，到此，频繁项目集生成过程结束。 这里只说明3-频繁项目集生成关联规则的过程，即以集合{1，2，3}为例： 回顾事物集，先生成1-后件的关联规则： （1，2）—>3，置信度=3/4（出现（1，2）的记录共4条，其中有3条包含3，所以3/4）； （1，3）—>2，置信度=3/5； （2，3）—>1，置信度=3/3； 第二条置信度<5/7，未达到最小置信度，所以剔除掉。所以对于3-频繁项目集生成的强关联规则为：（1，2）—>3和（2，3）—>1。 这表示，如果1、2出现了，则极有可能出现3；2、3出现，则极有可能有1。

基于Apriori算法的关联分析 Aprior算法是关联规则分析中较为经典的频繁项集算法。关联规则反映的是两个或多个事物相互之间的依存性和关联性。如果两个或者多个事物相互之间存在一定的关联关系，则它们之间存在一种关联规则使得它们之间可以进行搭配。 基本概要 Apriori算法利用频繁项集的先验知识，不断地按照层次进行迭代，计算数据集中的所有可能的频繁项集，它的分析主要包括两个核心部分。 1、根据支持度找出频繁项集； 2、根据置信度产生关联规则。 Apriori算法原理 基本流程： 1、扫描历史数据，并对每项数据进行频率次数统计。 2、构建候选集 ，并计算其支持度，即数据出现频率次数与总数的比。 3、对候选项集进行筛选，筛选的数据项支持度应当不小于最小支持度，从而形成频繁项集 . 4、对频繁项集 进行连接生成候选集 ，重复上述步骤，最终形成频繁K项集或者最大频繁项集。 Apriori算法存在两大定理： 1、如果一个集合是频繁项集，那么它的所有子集都是频繁集合。 2、如果一个集合它不是频繁集合，那么它的所有超集都不是频繁项集。 Apriori算法优缺点 优：运算过程非常简单，理论方法也比较容易理解，对数据特征的要求也相对较低。 缺： 1、产生候选集是产生较多的组合，没有考虑将一些无关的元素排除后再进行组合。 2、每次计算项集的过程中都会扫描元素的数据表。 针对不足推出不断改进的Apriori算法： 1、将数据表（事务表）进行压缩。 2、利用哈希表的快速查找特性对项集进行计数统计。 3、合理选样。