3.1　关联分析介绍

关联规则分析（association rules）是数据挖掘的购物篮分析（market basket analysis），即：从顾客的交易中发现买A产品的顾客可能会买B产品。例如，尿布与啤酒的故事，每星期四晚上，买尿布的顾客的交易（事务）多数会买啤酒。营销应用在推荐商品、交叉促销、商店布置等。关联规则还应用在许多领域，包括：网站页面分析、广告使用分析、用户关键词搜寻、入侵检测、连续生产及生物信息学等。

图3-1是关联规则名词概念图。

3.1.1　事务与项目的定义

关联分析的数据表示如图3-2。

定义关联分析的名词：

（1）项目（item）：商品或物品名称，例如A、B、尿布、啤酒。

（2）项目集或称项集（itemset）：一个及一个以上项目集合，例如{A}、{B}、{A，B}、{尿布，啤酒}。项目或项集是数据框的列。

项目是变量，用 A，B，C表示，也会当作项集。

项集是集合，用 X，Y表示，例如X = {A}简记 A，X = {A，B}简记AB。

X=AB，Y=EFG，X∪Y=ABEFG。

（3）k-项集（k- itemset）：包含k个项目的集合。ABEFG是5-项集。

（4）空项集（empty itemset）：没有项目的集合，例如{ }。

（5）事务标识（TID）：顾客的标记。数据框的行。

（6）事务（transaction）：顾客的交易，例如{A=1，B=0，C=1}、{尿布=1，啤酒=0}。

（7）零事务（null transaction）：没有交易的事务，例如图3-2的 TID = 5。

（8）支持度（support）：项集X={A}（简记 A）的支持度，#表示数目。

Support（A）= S（A）= #{事务i| A=1} / n，n = #（D）= 所有事务的数目。

S（A）= {A=1的事务的数目} / {所有事务的数目}。

Support（{A，B}）= S（AB）= #{事务i| A=1，B=1} / n = #（A×B）/ n 。

S（AB）=　# {A=1且B=1的事务的数目} / {所有事务的数目}。

S（X）= {X所有事务 = 1的数目} / {所有事务的数目}。

S（A）≧S（AB），项集的项目越多，支持度就越小。

S（X）≧S（X∪Y），S（Y）≧S（X∪Y），对所有项集 X，Y。

（9）子项集（subitemset）与超项集（superitemset）：若项集 X，Y，X⊆Y，则X称为Y的子项集；Y称为X的超项集。例如X = AB，Y = ABC，X是子项集，Y是超项集。

Support（子项集）≥Support（超项集），S（子项集）≥S（超项集）

（10）支持度阈，最小支持度（minimum support threshold）：阈值，支持度门槛值。记作 Minsupport。

（11）频繁项集（frequent itemset）：项集X的支持度大于最小支持度阈值，称为频繁项集S（X） > Minsupport。

（12）所有频繁项集的子项集，都是频繁项集。

青（子项集频繁）出于蓝（是因为超项集频繁），而胜于蓝（子项集比超项集更频繁）。

（13）所有非频繁项集的超项集，都是非频繁项集。非频繁的子项集，其超项集一定是非频繁。子不教（子项集非频繁），父之过（因为超项集非频繁）。

3.1.2　项集的关联规则

关联规则可以用条件概率检查，买什么东西的顾客，会再买什么东西。例如，买尿片的，会买啤酒，P （B买啤酒 | A买尿片）> P （B买啤酒）。

若两个项集X，Y，其交集为空集合 X∩Y ={}，即X，Y没有共同的项集，则项集X，Y的关联规则X→Y，X称为规则的前项或先导（antecedent或left-hand-side，lhs），Y称为规则的后项或后继（consequent或right-hand-side，rhs）。

AB→ACD不能成为规则。

关联规则的测量有如下几项。

（1）支持度（support）：X→Y的支持度：规则的有用性。

Support（X→Y）= S（X→Y）= S（Y→X）= S（X∪Y）

（2）置信度（confidence）：X→Y的置信度：规则前项（因）后项（果）的可信度或确定性。

置信度是条件概率：P（顾客买Y|顾客买X）。请参考《大话统计学》5.5节。

Confidence（X→Y）= C（X→Y）= S（X→Y）/ S（X）

（3）提升度（lift）：X→Y的提升度：顾客买X带给购买Y信息的提升度。

Lift（X→Y）= L（X→Y）= C（X→Y）/ S（Y）= S（X→Y）/ [S（X）×S（Y）]

在数据挖掘称为提升度，在购物篮分析称为改善度（improvement）。项集X搭配项集Y销售，是单独销售项集Y结果的L（X→Y）倍。L（X→Y）可能 ＜1，＝1，或 ＞1。

事物频数如表3-1所示。

支持度 S（A）=（a+b）/ n；

支持度 S（B）=（a+c）/n；

支持度 S（A→B）= a / n = S（B→A）；

置信度 C（A→B）= a /（a+b）；

置信度 C（B→A）= a /（a+c）；

提升度 L（A→B）= a（a+b+c+d）/（a+b）（a+c）= L（B→A）；

若提升度 Lift = 1，则A和B是独立的。因为a × n =（a+b）×（a+c）。

若提升度Lift > 1，则A和B是（互相）正面提升的。

若提升度Lift < 1，则A和B是（互相）负面提升的。

但是，提升度会受到零事务和样本数的影响。

以上有关统计学的独立和条件概率，《大话统计学》中第5章有详细说明。

（4）支持度阈（minimum support threshold），阈又叫阈值，支持度门槛值。记作Min_support。

（5）置信度阈（minimum confident threshold），置信度门槛值。记作Min_ confident。

通常支持度要大于 0.1，置信度要大于0.1或 0.2，提升度要大于1，正面信息。但是当项目（变量）越多时，支持度会越小。

（6）强关联规则。

Support（X→Y）= S（X→Y）> Min_support

Confidence（X→Y）= C（X→Y）> Min_confident

（7）支持度和提升度符合交换律，置信度不符合交换律。

Support（X→Y）= Support（Y→X），S（A→B）= S（B→A）

Confidence（X→Y）≠ Confidence（Y→X），C（X→Y）≠ C（Y→X）

Lift（X→Y）= Lift（Y→X），L（X→Y）= L（Y→X）

（8）Support（{}→X）= Support（X）

Confidence（{}→X）= Support（X），Confidence（X→{}）= 1

Lift（{}→X）= 1