Apriori算法

频繁模式是频繁出现在数据集中的模式(如项集，子序列等)。例如：频繁的同时出现在交易数据集中的商品（牛奶，面包）的集合就是频繁项集。频繁项集挖掘导致发现大型事务或关系数据集中有趣的关联或相关。规则的支持度和置信度是规则兴趣度的两种度量。它们分别反映所发现的规则的有用性和确定性。关联规则的支持度（support）为2%意味着所分析的所有销售记录中有2%的顾客同时购买计算机和杀毒软件support(A→B)=P(A∪B)。60%置信度（confidence）则意味着，所有购买计算机的顾客中，有60%的顾客也购买了杀毒软件confidence(A→B)=P(B|A)。典型情况下，如果关联规则同时满足最小支持度阈值（min_sup）和最小置信度阈值(min_conf)，则此关联规则是有趣的。这些阈值可以由用户或领域专家设定。名词解释：1.项集。项的集合为项集，包含k个项的集合成为k项集。例如｛面包，牛奶｝是一个2项集。2.支持度计数。项集的出现频率是包含项集的事务数，简称项集的频率，支持度计数，也称项集的绝对支持度。项集的相对支持度为项集在事务集中发生的概率。3.频繁项集。如果项集A的支持度满足预定义的最小支持度阈值，则A是频繁项集。频繁K项集通常被记作Lk。confidence(A→B)=P(B|A)=support(A∪B)support(A)上式表明挖掘关联规则的问题可以归结为挖掘频繁项集。一般来说，关联规则的挖掘可以看做两步：1.找出所有的频繁项集：根据定义，这些项集的频繁性至少与预定义的最小支持计数一样。2.由频繁项集产生强关联规则：这些规则必须满足最小支持度和最小置信度。然而有这么一个需要思考的问题：从大型数据集中挖掘频繁项集的主要挑战是常常产生大量满足最小支持度的项集。当min_sup设的低时尤其如此。这是因为如果一个项集是频繁的，那么它的每个子集也是频繁的。例如，一个长度为100的频繁项集｛a1,a2,…,a100｝包含C1001=100个频繁1项集，包含C1002个频繁2项集，如此等等。这对于任何一个计算机，项集的个数都太大。Apriori算法使用一种称作逐层搜索的迭代方法，k项集用于探索k+1项集。首先，通过扫描数据库，积累每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记作L1。然后用L1找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k项集。Apriori性质：频繁项集的所有非空子集也必须是频繁的。那么我们就知道：如果项集A不满足最小支持度阈值，则A不是频繁的，如果添加项a到项集A中，则项集（AUa）不可能比项集A更频繁出现。这称为反单调性，指如果一个集合不能通过测试，则所有包含它的集合也不能通过测试。那么如何由Lk−1找到Lk（k=2）呢？这是由连接步和剪枝步完成的。一，连接步：为找Lk，通过将Lk−1与自身连接产生候选k项集的集合。该候选项集的集合记作Ck。设M1，M2是Lk−1中的项集，记号Mi[j]表示Mi中的第j项，例如M1[k-2]表示M1的倒数第二项。为方便起见，Apriori假定事务或项集中的项按字典次序排序。对于（k-1）项集Mi，将排序使Mi[1]Mi[2]…Mi[k-1]。执行连接Lk−1&Lk−1，如果它们的前（k-2）个项相同的话，那么Lk−1的元素是可连接的。如果（M1[1]=M2[1]）^（M1[2]=M2[2]）^…^（M1[k-1]=M2[K-1]）^（M1[k-1]M2[k-1]），那么Lk−1的元素M1，M2是可连接的。条件M1[k-1]M2[k-1]仅仅是保证不产生重复。连接M1，M2产生的结果项集是M1[1]，M1[2]，…，M1[k-1]，M2[k-1]。二，剪枝步：Ck是Lk的超集，也就是说Ck的子集可以是也可以不是频繁的，但所有的频繁k项集都包含在Ck中。扫描数据库，确定Ck中每个候选项集的计数，从而确定Lk（即计数值不小于最小支持度计数的所有候选项集是频繁的）。然而，Ck可能很大，这样所涉及的计算量就很大，为了压缩Ck，可以使用Apriori性质，任何非频繁的（k-1）项集都不是频繁k项集的子集。因此，如果候选k项集的（k-1）项子集不在Lk−1中，则该候选项集也不可能是频繁的，从而可以从Ck中删除，这种子集测试可以使用所有频繁项集的散列树快速完成。有如下数据：每一行表示一条交易，共有9行，既9笔交易，左边表示交易ID，右边表示商品名称。最小支持度是22%，那么每件商品至少要出现9*22%=2次才算频繁。第一次扫描数据库，使得在每条交易中，按商品名称递增排序。第二次扫描数据，找频繁项集为1的元素有：左边表示商品名称，右边表示出现的次数，都大于阈值2。在此基础上找频繁项集是2的元素（候选集C2），第三次扫描数据得到它们出现的次数：这里{I1,I4},{I3,I4},{I3,I5},{I4,I5}出现的次数都小于2，过滤掉，实际频繁项集为2（L2）的元素有：由L2产生候选C3：{I1,I2,I3}和{I1,I2,I5}，因为它们的支持度计数都是2，所以L3即C3，为{I1,I2,I3}、{I1,I2,I5}；再由L3产生C4，连接结果为｛I1,I2,I3,I5｝,但是它的子集｛I2，I3,I5｝不是频繁的，所以C4是空集，算法终止，找出了所有的频繁项集。