挫折感很大、觉得很难熬的时候，可以闭上眼睛，想像自己已经是十年之后的自己，置身一段距离之外，转头去看正在遭遇的那些事。 练习这样做，心情可能会平静些，知道眼前这一切，都会过去。——蔡康永

别太嚣张，对自己没好处。——李秘书

你今天泼给我的冷水，我定要烧开了给你泼回去。——宋晓峰

小人别得地，得地就起屁。 ——刘能

目录

1 关联规则概述

关联规则挖掘是数据挖掘的热点之一。关联规则反映一个对象与其他对象之间的相互依赖性，如果多个对象之间存在一定的关系，那么一个对象就能够通过其他对象来进行预测。

关联规则可以采用与分类规则相同的方式产生。由于得到的关联规则的数量庞大，通常需要通过使用覆盖率和准确率进行修剪，覆盖率也称为支持度，指的是应用规则之后预测正确的实例数量。准确率也称为置信度，表示为支持度数值应用规则后的数量比例。

相关术语：

支持度: P(A∩B)，即A和B这两个项集在事务集D中同时出现的概率。

置信度: P(B∣A)，即在出现项集A的事务集D中，项集B也同时出现的概率。

频繁项集：指经常出现在一块的物品的集合。 关联规则暗示两种物品之间存在很强的关系。(这里我们事先定义阀值，超过该阀值，证明两者之间存在很强的关系).

2 关联算法的介绍

2-1 Apriori算法

算法介绍

Apriori算法利用了两个重要的性质，用于压缩搜索的空间。

【1】若X为频繁项目集，则X的所有子集都是频繁项目集。

【2】若X为非频繁项目集，则X的所有超集均为非频繁项目集。

Apriori算法的处理流程为：宽度优先搜索整个项集空间，从k=0开始，迭代产生长度为k+1的候选项集的集合Ck+1。候选项集是其所有子集都是频繁项集的项集（初始化C1由I0中所有的项构成），在第k层产生所有长度为k+1的项集。

由两步完成：

第一步，Fk自连接。将Fk中具有相同(k-1)-前缀的项集连接成长度为k的候选项集。

第二步是剪枝，如果项集的所有长度为k的子集都在Fk中，该项集才能作为候选项集被加入Ck+1中。为了计算所有长度为k的候选项集的支持度，在数据库水平表示方式下，需要扫描数据库一遍。在每次扫描中，对数据库中的每条交易记录，为其中所包含的所有候选k-项集的支持度计数加1。所有频繁的k-项集被加入Fk中。

此过程直至Ck+1等于空集时结束。

算法  AprioriInput:          Transaction DataBase D，Minimum support threshold minsup。Output：      Frequent pattern L(1) L1=search_frequent_1-itemsets( D );///生成频繁一项集(2) for(k=2;Lk-1≠φ;k++) do(3) begin(4)    Ck=apriori-gen(Lk-1);//生成候选k项集(5)    for all transactions t D do /// 扫描数据库中的每一个事务t(6)    begin(7)      Ct=subset(Ck，t);//识别属于t的所有候选项集(8)      for all candidates c Ct do(9)        c.count++;(10)    end(11)    Lk ={c Ck|c.count≥minsup}  //根据支持度来提取频繁k项集(12) end(13) Answer L=∪kLk;Procedure Search_frequent_1-itemsets( D )(1) begin(2)  for all transactions t D do(3)  begin(4)    for each item ik t do(5)      ik.count++;(6)  end(7)  L1 ={ i I | i.count≥minsup}(8)  return L1;(9) endProcedure apriori_gen(Lk)(1) begin(2)   for each itemset l1 Lk do(3)     for each itemset l2 Lk do(4)     begin(5)       if ( l1[1]=l2[1]) ( l1[2]=l2[2]) … ( l1[k-1]=l2[k-1]) ( l1[k]

在主程序中，第一步首先扫描整个交易数据库D，统计每个项目(item)的支持数，计算其支持度，将支持度大于等于最小支持度minsup的项目构成的集合放入到L1 中；从第2步到第11步，用k-1频繁项集构成的Lk-1生成候选集的集合Ck，以便从中生成Lk，其中apriori_gen函数(第4步)用来从Lk-1中生成Ck，然后对数据库进行扫描(第5步)，对于数据库中的每一个交易，subset函数用来发现此交易包含的所有候选集(第7步)，并为这些候选集的计数器加1(第8-9步)。最后满足minsup的候选集被放入到Lk中。

apriori_gen 过程完成两种操作：并(join)和剪枝(prune)。在并运算步骤中，Lk-1 与Lk-1 进行并运算生成潜在的候选集(2-7步)，条件l1[k-1]

2-2 FP-Growth算法

FP-Growth(频繁模式增长)算法是韩家炜老师在2000年提出的关联分析算法，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree），但仍保留项集关联信息；该算法和Apriori算法最大的不同有两点：第一，不产生候选集，第二，只需要两次遍历数据库，大大提高了效率。

算法伪代码

算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。输入：事务数据库D；最小支持度阈值min_sup。输出：频繁模式的完全集。1． 按以下步骤构造FP-树：(a) 扫描事务数据库D 一次。收集频繁项的集合F 和它们的支持度。对F 按支持度降序排序，结果为频繁项表L。(b) 创建FP-树的根结点，以“null”标记它。对于D 中每个事务Trans，执行：选择 Trans 中的频繁项，并按L 中的次序排序。设排序后的频繁项表为[p | P]，其中，p 是第一个元素，而P 是剩余元素的表。调用insert_tree([p | P], T)。该过程执行情况如下。如果T 有子女N 使得N.item-name = p.item-name，则N 的计数增加1；否则创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同item-name 的结点。如果P 非空，递归地调用insert_tree(P, N)。

procedure FP_growth(Tree, a)if Tree 含单个路径P then{         for 路径P中结点的每个组合（记作b）         产生模式b U a，其支持度support = b 中结点的最小支持度；} else {         for each a i 在Tree的头部(按照支持度由低到高顺序进行扫描){                  产生一个模式b = ai U a，其支持度support = ai .support；                  构造b的条件模式基，然后构造b的条件FP-树Treeb；                  if Treeb 不为空 then                            调用 FP_growth (Treeb, b)；           }}FP-growth是整个算法的核心，再多啰嗦几句。FP-growth函数的输入：tree是指原始的FPTree或者是某个模式的条件FPTree，a是指模式的后缀（在第一次调用时a=NULL，在之后的递归调用中a是模式后缀）FP-growth函数的输出：在递归调用过程中输出所有的模式及其支持度（比如{I1,I2,I3}的支持度为2）。每一次调用FP_growth输出结果的模式中一定包含FP_growth函数输入的模式后缀。

参考

3 关联算法Weka实现

3-1 Apriori关联规则挖掘

对天气的标称数据进行Apriori关联规则挖掘。

=== Run information ===Scheme:       weka.associations.Apriori -N 10 -T 0 -C 0.9 -D 0.05 -U 1.0 -M 0.1 -S -1.0 -c -1Relation:     weather.symbolicInstances:    14Attributes:   5              outlook              temperature              humidity              windy              play=== Associator model (full training set) ===Apriori=======Minimum support: 0.15 (2 instances)Minimum metric 
     
      : 0.9Number of cycles performed: 17Generated sets of large itemsets:Size of set of large itemsets L(1): 12Size of set of large itemsets L(2): 47Size of set of large itemsets L(3): 39Size of set of large itemsets L(4): 6Best rules found: 1. outlook=overcast 4 ==> play=yes 4    
      
        lift:(1.56) lev:(0.1) [1] conv:(1.43) 2. temperature=cool 4 ==> humidity=normal 4    
       
         lift:(2) lev:(0.14) [2] conv:(2) 3. humidity=normal windy=FALSE 4 ==> play=yes 4    
        
          lift:(1.56) lev:(0.1) [1] conv:(1.43) 4. outlook=sunny play=no 3 ==> humidity=high 3    
         
           lift:(2) lev:(0.11) [1] conv:(1.5) 5. outlook=sunny humidity=high 3 ==> play=no 3    
          
            lift:(2.8) lev:(0.14) [1] conv:(1.93) 6. outlook=rainy play=yes 3 ==> windy=FALSE 3 
           
             lift:(1.75) lev:(0.09) [1] conv:(1.29) 7. outlook=rainy windy=FALSE 3 ==> play=yes 3 
            
              lift:(1.56) lev:(0.08) [1] conv:(1.07) 8. temperature=cool play=yes 3 ==> humidity=normal 3 
             
               lift:(2) lev:(0.11) [1] conv:(1.5) 9. outlook=sunny temperature=hot 2 ==> humidity=high 2 
              
                lift:(2) lev:(0.07) [1] conv:(1)10. temperature=hot play=no 2 ==> outlook=sunny 2 
               
                 lift:(2.8) lev:(0.09) [1] conv:(1.29)