关联规则

?

1. 项与项集

数据库中不可分割的最小单位信息称为项（或项目），用符号表示，项的集合称为项集。设集合是项集，中项目的个数为，则集合称为-项集。例如，集合{啤酒，尿布，奶粉}是一个3-项集。

1. 事务

设是由数据库中所有项目构成的集合，事务数据库是由一系列具有唯一标识的事务组成的。每一个事务包含的项集都是的子集。例如，顾客在商场里同一次购买多种商品，这些购物信息在数据库中有一个唯一标识，用以表示这些商品是同一顾客同一次购买的，称该用户的本次购物活动对应一个数据库事务。

1. 项集的频数（支持度计数）

包括项集的事务数称为项集的频数（支持度计数）。

1. 关联规则

关联规则是形如的蕴含式，其中分别是的真子集，并且。称为规则的前提，称为规则的结果。关联规则反映中的项目出现时，中的项目也跟着出现的规律。

1. 关联规则的支持度（support）

关联规则的支持度是交易集中同时包含和的交易数与所有交易数之比，它反映了和中所含的项在事务集中同时出现的频率，记为support ，即

????supportsupport????????????

(1)

?

1. 关联规则的置信度（confidence）

关联规则的置信度是交易集中包含和的交易数与所有交易数中包含的交易数之比，记为，置信度反映了包含的事务中出现的条件概率。即

????????????????????????

(2)

?

3

?

1. 最小支持度与最小置信度

通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈值，此两个值称为最小支持度阈值（min_sup）和最小置信度阈值（min_conf）。其中，min_sup描述了关联规则的最低重要程度，min_conf规定了关联规则必须满足的最低可靠性。

1. 强关联规则

且，称关联规则为强关联规则，否则称为弱关联规则。通常所说的关联规则一般是指强关连规则。

1. 频繁项集

对项目集，在事务数据库中所有满足用户指定的最小支持度的项目集，即不小于的的非空子集，称为频繁项目集或大项目集。

1. 项目集空间理论

Agrawal等人建立了用于事务数据库挖掘的项目集空间理论。理论的核心为：频繁项目集的子集仍是频繁项目集；非频繁项目集的超集是非频繁项目集。

?

Apriori算法原理

1. Apriori算法的基本思想

Apiori算法的基本思想是通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集从而生成关联规则。Apriori算法对数据集进行多次扫描。第一次扫描得到频繁1-项集的集合，第次扫描首先利用第次扫描的结果来产生候选-项集的集合，然后在扫描的过程中确定中元素的支持度，最后在每一次扫描结束时计算频繁-项集的集合，算法在当候选-项集的集合为空时结束。

1. Apriori算法产生频繁项集的过程

产生频繁项集的过程主要分为连接和剪枝两步：

1. 连接步。

为找到，通过与自身作连接产生候选-项集的集合。

设和是中的项集。记表示的第个项。Aprior算法假定事务或项集中的项按字典次序排序；对于项集，对应的项排序为。如果的元素和的前个对应项相等，则和可连接。即如果时，和可连接。条件可以保证不产生重复，而按照，次序寻找频繁项集可以避免对事务数据库中不可能发生的项集所进行的搜索和统计工作。连接和产生的结果项集为。

1. 剪枝步。

由Apriori算法的性质可知，频繁-项集的任何子集必须是频繁项集。由连接生成的集合需要进行验证，去除不满足支持度的非频繁-项集。

1. Apriori算法的主要步骤
   1. 扫描全部数据，产生候选1-项集的集合。
   2. 根据最小支持度，由候选1-项集的集合产生频繁1-项集的集合。
   3. 对，重复执行步骤（4）、（5）、（6）。
   4. 由执行连接和剪枝操作，产生候选-项集的集合。
   5. 根据最小支持度，由候选-项集的集合，产生频繁-项集的集合。
   6. 若，则，否则跳往步骤（4）；否则，跳往步骤（7）。
   7. 根据最小置信度，由频繁项集产生强关联规则，结束。
2. Apriori算法描述

输入：数据库，最小支持度阈值。

输出：中的频繁集。

1. Begin
2. =1-频繁项集；
3. do begin
4. {调用函数通过频繁-项集产生候选-项集}
5. for所有数据库 do begin {扫描用于计数}
6. {用subset找出该事务中候选的所有子集}
7. for所有候选集 do
8. 
9. end;
10. 
11. end
12. end
13. Return {形成频繁项集的集合}

?

Apriori算法实例分析

?

表1 数据库的事务列表

?

设最小支持度计数为2，即min_sup=2,利用Apriori算法产生候选项集及频繁项集的过程如下所示。

1. 第一次扫描

扫描数据库获得每个候选项的计数：

????????????????????????????????????????????

?

?

?

?

?

?

?

?

?

?

?

?

由于最小事务支持数为2，没有删除任何项目。可以确定频繁1-项集的集合，它由具有最小支持度的候选1-项集组成。

1. 第二次扫描

为发现频繁2-项集的集合，算法使用产生候选2-项集的集合。在剪枝步没有候选从中删除，因为这些候选的每个子集也是频繁的。

?

1. 第三次扫描
2. 第四次扫描

关联规则1