3.3 关联规则的算法
Apriori算法，是翻译为先的验算法，1994年由Agrawal & Srikant等首先提出，是最为著名且广泛运用的关联规则算法。Apriori算法是基于广度优先的算法。另外有Eclat算法，是基于深度优先的算法，还有FP成长树算法，不在此赘述。
3.3.1 Apriori算法
Apriori算法分成两部分：第一部分，计算所有的频繁项集；第二部分，计算所有的强关联规则。Apriori算法概念如下。
（1）设定关联规则：一个项集的最小支持度阈Minsupport；两个项集关联规则的最小支持度阈 Min_support和最小置信度阈 Min_confident。通常Minsupport = Min_support。
（2）根据最小支持度阈Minsupport，计算所有的频繁项集，k = 1。
1）找出k-项集所有频繁项集。
2）（剪枝步骤）若其中有非频繁项集，则其超项集为非频繁项集，予以删除。
3）k =k + 1，回到2），直到所有n-项集被计算或删除。
（3）根据最小置信度阈 Min_confident，计算的强关联规则。
根据频繁项集的规则，计算强关联规则。
剪枝步骤：根据下列定理。
如果规则 X→Y-X不是强关联规则，不满足置信度阈值，则Z→Y-Z也不是强关联规则，其中Z是X的子项集。
例如：Y=ABCD，X=BCD，Y-X=A，Z=B，Y-Z＝ACD
如果BCD→A非强关联规则，则B→ACD非强关联规则。
非强关联规则有两个条件：
（1）S（BCD→A）=S（B→ACD）=S（ABCD）< Min_support
（2）C（B→ACD）= S（ABCD）/S（B）< S（ABCD）/S（BCD）= C（BCD→A）< Min_confident
因为 S（B） > S（BCD）
具体如图3-4和图3-5所示。
图3-4 Apriori算法计算频繁项集的剪枝步骤
图3-5 Apriori算法的计算强关联规则
3.3.2 关联规则其他测度值
项集关联的测度值，除了支持度，置信度，提升度，关联规则的测量还有许多测度值。（参考网站http://michael.hahsler.net/research/association_rules/measures.html）。
在R语言的关联规则包中arules的函数interestMeasure（）可以有这些测量。如表3-2所示。
表3-2 事务频数表
下列关联规则测度值，没有前项后项（A→B或B→A）的差别（交换律），只有关联，没有因果的规则。除了置信度有前项后项的差别。
（1）χ2期望值：
如果a >χ2（A,B），则提升度 > 1。
（2）互信息（mutual information）：
（3） Jaccard系数：
（4）全置信度（all_confidence）：
All_conf（A,B）=min{P（A|B）,P（B|A）}
（5）最大置信度：
max_conf（A,B）=max{P（A|B）,P（B|A）}
（6）余弦度量Cosine测度：
（7）杠杆率（leverage）：
leverage（A→B）= Support（A→B）－Support（A）*Support（B）
杠杆率类似提升度，leverage（A→B）>1是正相关；leverage（A→B）=1是独立；
leverage（A→B）< 1是负相关。
（8）Phi相关系数Phi correlation coefficient ：
（9） Kulczynski测度：
Kulc（A,B）=（0.5）{P（A|B）+P（B|A）}
（10）确信度（conviction）：
Conviction（A→B）=[1 － Support（B）] / [1 － Confidence（A →B）]
确信度或定罪率 Conviction（A→B）= 1.2表示有20%的错误率。
（11）失调率（imbalance ratio）不平衡比：
以上测度值（1）～（9）测量值越高，表示A，B的关联越好，（10）确信度和（11）失调率是越低越好。
3.3.3 负关联规则
关联规则是计算两个项集的关联，以购物篮来说，（A→B）是已经买了项集A，会再买项集B的概率。例如，顾客买了面包，还会再买牛奶的概率。
负关联规则（¬A→B）是没有买项集A，会买项集B的概率。或者（A→¬B）是买项集A，不会买项集B的概率。例如，顾客买了豆浆，就不会再买牛奶的概率。
请见3.6.2节【R例3.4】商店数据有负关联规则的R程序代码。