关联规则挖掘的基础知识

## 1.概述

从事务数据关系看，关联性可测度事物之间联系程度，更关注事物之间是否出现一定的关联作用关系。
本节介绍关联规则挖掘的基本概念，包括测度事物之间关联作用的支持度和相关置信度概念，并界定关联规则。
通过规则分类，给出规则挖掘的技术路径与评价标准

关联规则的经典案例是基于大型超市大数据，通过挖掘消费者选择不同商品之间的关联信息，分析促进商品销售的规则。通过关联规则算法得到相关强关联规则结论，可以用于辅助用户决策行为

| *T* 事务标识 | 项目 | *T* 事务标识 | 项目  |
| --- | --- | --- | --- |
| 100 | ABCDF | 600 | ACF |
| 200 | BCEF | 700 | ABCDEF |
| 300 | BCE | 800 | ABCE |
| 400 | BE | 900 | BC |
| 500 | ABC | 1000 | EF |

事务标识栏表示单次购买行为T的记录标志，项目表示单次购买行为T的商品集合。例如，购买事务100对应的商品为A、B、C、D、F，其余购买事务可以此类推。由表中数据集，可以计算出很多关联规则

`支持度: 全部事务中包含商品X的事务T的比率。`

`置信度: 同时包含商品X和Y的事务数与包含X的事务数之比, 称为关联规
则X⟹Y的置信度。`

① “关联规则”A⇒B, 购买商品A的事务有 5 个, 分别为T100、T500、T600、 T700、 T800, 其中同时购买商品B的事务有 4 个，分别为T100、T500、T700、T800, 购买商品A的事务中有 80% 的事务也购买了商品B；
② “关联规则”A⇒C, 购买商品 A 的事务有 5 个, 其中同时购买商品C的事务有 5 个, 购买商品A的事务中有 100% 的事务也购买了商品C；
③ “关联规则”E,C⇒B, 购买商品B和商品E的事务有 5 个, 其中同时购买商品C的事务有 4 个, 同时购买商品E和商品B的事务中有 80% 的事务也购买了商品C

需要用户基于分析目标通过技术和主观两个层面判定规 则的价值:

### 1.技术层面
**在技术层面：基于“支持度-置信度”判定关联强规则算法而言, 有时也会产生一些无意义的结论。**

- 如调查 4000 名学生晨练情况, 得到 2200 名学生打篮球, 2750 名学生晨跑, 1800 名学生打篮球、晨跑的数据。如果设最小支持度为 40%, 最小置信度 为 60%， 可 以 得 （打篮球） ⇒ （晨跑）（1800/4000=45%，1800/2200=81% ）的关联规则。但这条规则其实并没有意义, 因为单纯晨跑学生的比例已高达68%。而考虑（打篮球） ⇒ （（不）晨跑）（400/4000=10%，400/2200）的关联时, 虽然该规则支持度和置信度比较低, 但是对分析学生晨练更有价值。

- `支持度和置信度的高低组合设定是技术层面的关键因素，其决定关联规则的合理性和应用价值`

- `当支持度和置信度设定得足够低时，可能得到两条矛盾的强关联规则；但如果把参数设定得足够高，则只能得到不精确的规则。总之，没有一对支持度和可信度的组合可以产生充分合理的关联
`

**在实际应用中，最小支持度和置信度的设定，面临如下选择问题：**

- 要么是把支持度设定得足够低，避免丢失任何有意义的规则；
- 要么提高最小支持度则面临丢失一些重要规则的风险。前一种情形存在计算效率问题，而后一种情形则存在有可能丢失对用户有意义的规则。

**为了解决上述支持度和置信度设定选择问题，相关专家提出很多改进的方法，大体分为三类：**
- 一类是设法寻找置信度度量的替代物（如兴趣度、有效度、匹配度等）；
- 一类是改进原有固定支持度阈值限制的客观评价方法；
- 一类是Liu（1999）等人提出的多支持度阈值关联规则挖掘算法，如使用随着项集长度增加而减少的可变支持度阈值技术等。

### 2.主观层面

在主观层面上，一个规则的价值最终取决于用户的感觉判断。只有用户可以决定规则的有效性、可行性。所以可以将用户的需求和挖掘分析更加紧密的结合起来。

- 如可以采用由用户对挖掘的数据附加约束条件，常见的约束内容有：数据约束，即由用户指定对哪些数据进行挖掘；维和层次约束，用户指定进行数据挖掘的维度及在这些维的层次；规则约束，用户指定所需的规则类型等。
- 关联规则挖掘是早期数据挖掘技术形成的重要推动力;
- 1993年阿格拉瓦尔等学者提出关联规则概念和初步的AIS挖掘算法;
- 1994年其又提出项集格空间理论以及 Apriori 算法;
- 阿格拉瓦尔等进一步提出 AprioriTid 算法，以及 Apriori 和 AprioriTid 算法相结合的 AprioriHybird 算法；希德伯 （1999）提出了在线挖掘关联规则(CARMA)算法；
- Han等（2000）提出了基于频繁模式树（FP-Tree）发现频繁项集的FP-growth算法;
- 扎基（2000）提出挖掘效率提高的 Eclat 算法等;
- 目前关联规则仍是数据挖掘分析中最常用的方法之一;
- Apriori 作为关联规则挖掘算法的经典，目前仍然作为该方法的基础被广泛讨论。

## 2. 关联规则挖掘的相关概念

### 1.关联规则

上述引例问题可以表示为, 设商品项目全集$$I={I_1,I_2....I_p}$$中, 消费者购物行为事务 的全集为D, 消费者将商品放入购物篮的事务为T⊆D，若商品项集X⊆I和商品项集Y⊆I,X∩Y=∅, 且蕴含X⇒Y的关联作用关系,X称为关联规则的条件,Y称为关系规则的结果。

### 2.关联支持度

将事务全集D中同时包含商品X和Y事务T的比率, 称为关联规则X⊆Y对事项集 D的支持度（support），即

$$s(X\Rightarrow Y)=P(X\cup Y)=\frac{count(同时包含商品X.Y的事务)}{count（事务全集）}$$

其中,P($$\cdot$$)表示概率, 即事务全集D中同时包含商品X和事务Y的百分比。$$count(\cdot)$$称为项集的频率、支持计数或者支持度计数。

### 3.关联置信度

将包含X同时包含Y事务数与包含X事务数的比率，称为关联规则X⇒Y对事务全集D的置信度（confidence），即

$$c(X\Rightarrow Y)=P(Y\vert X)=\frac{count(同时包含X和Y的事务)}{count(包含X的事务)}$$

将上述引例具体为购买计算机(X)与购买财务管理软件(Y)。如果得到相应关联规则为: Computer⇒financial_management_softwar[s=2%,c=60%]，其表示: 在大型超市全部购买事项中, 同时购买计算机和财务管理软件事项仅得到 2% 的支持; 而在购买计算机事项中, 购买财务管理软件置信度高达 60%

### 4.强关联规则

进而, 如果支持度和置信度均大于给定的最小支持度阈值$$min_s$$和最小置信度阈值$$min_c$$。即:

$$s(X⇒Y)\geq min_s$$

$$c(X⇒Y)\geq min_c$$

则称该关联规则为`强规则`; 否则为`弱规则`。
- 关联规则挖掘主要是对强规则的挖掘, 力图得到基于最小支持度和最小置信度的事物之
间关联规则

### 5.基于事项变量类别,关联规则可划分为布尔型和数值型

- `布尔型关联规则`：如果关联事项是以 “肯定” 或 “否定” 存在, 则关联规则是布尔 型的。如上述购物篮分析引例得出的关联规则。
- `量化型关联规则`: 如果关联事项是以数量及属性关系存在, 则该关联规则是量化型的

>例如, 分析不同消费者购买高清电视可能性。设x表示消费者, 且x的年龄 (age) 和收
入 (income) 属性以离散化数值表示。于是可有如下量化型关联规则:

$$age(X,''30,''''L,39'')\wedge income(X,42K,''''L,48K'')\Rightarrow buys(X,''high\_resolution\_TV'')$$

- 关联规则也可以由布尔和量化两类混合构成。例如: 分析性别、职业、收入 的关联关系, 可有:
（性别=“女”） ⇒ （职业=“秘书”）的布尔型关联规则;
（性别=“女”） ⇒ （avg(月收入)月收入=2300ሻ 的量化型关联规则。

### 6.基于事项分层，关联规则可以划分为单层和多层

多层关联规则: 事项或属性存在不同层次关系。例如, 不同年龄属性消费者购买计算机 
(computer) 和笔记本电脑（laptop computer）的关联规则:

$$age(X,'30,L,39')⇒buys(X,'laptop computer')$$

$$age(X,'30,L,39')⇒buys(X,'computer')$$

其中, 存在 “computer”包含 “laptop computer”的层次关系, 其关联规则是多
层的。

### 7. 基于事项属性维数, 关联规则可以分为单维的和多维的

- 单维关联规则：处理事务单个属性间关系，称为单维关联规则。
>例如：消费者购买 物品：“ (咖啡) ⇒ (砂糖)” 的关联规则。

- 多维关联规则：处理事物多维属性之间 关系, 称为多维关联规则。
>例如: 分析任职人员性别和秘书职业的关联性时, 得到: 
（性别＝“女”) ⇒ (职业= “秘书”)

的规则其中, 该事项涉及人员及其任职的两维属性, 是两个维度的一条关联规则。

### 8. 基于频繁集概念的关联规则分类

在关联规则挖掘实践中, 为了提高效率, 节约计算机资源, 人们定义强规则X⇒Y对应的项集 (X∪Y)为频繁集。从而, 把关联规则挖掘划分为以下两个子问题:
`一是根据最小支持度找出事务集中的所有频繁项集`；
`二是根据频繁项集和最小置信度产生关联规则`。