关联分析概念

一、事务数据库

定义5.1 设I={i1，i2，…，im}是一个全局项的集合，其中ij（1≤j≤m）是项（item）的唯一标识，j表示项的序号。

 比如：I={牛奶、面包、麦片、糖、黄油、鸡蛋}

事务数据库（transactional databases）D={t1，t2，…，tn}是一个事务（transaction）的集合，每个事务ti（1≤i≤n）都对应I上的一个子集，其中ti是事务的唯一标识，i表示事务的序号。

定义5.2  由I中部分或全部项构成的一个集合称为项集（itemset），任何非空项集中均不含有重复项。

如I1={i1，i3，i4}就是一个项集。为了算法设计简单，本章中除特别声明外，假设所有项集中列出的各个项均按项序号或字典顺序有序排列。

购物篮问题：设I是全部商品集合，D是所有顾客的购物清单，每个元组即事务是一次购买商品的集合。

如表5.1所示是一个购物事务数据库的示例，其中，I={i1，i2，i3，i4，i5}，D={t1，t2，t3，t4，t5，t6，t7，t8，t9}，t1={i1，i2，i5}，…，t9={i1，i2，i3}。

二、关联规则及其度量

1、关联规则

关联规则表示项之间的关系，它是形如X→Y的蕴涵表达式，其中X和Y是不相交的项集，即X∩Y=Ф，X称为规则的前件，Y称为规则的后件。

例如，{cereal，milk}→{fruit}关联规则表示的含义是购买谷类食品和牛奶的人也会购买水果，它的前件为{cereal，milk}，后件为{fruit}，有时也表示为{cereal，milk}→{fruit}或cereal and milk→fruit等形式。

2、支持度

定义5.3 给定一个全局项集I和事务数据库D，一个项集I1ÍI在D上的支持度是包含I1的事务在D中所占的百分比，即

其中，|•|表示•集合的计数，即其中元素个数。对于形如X→Y的关联规则，其支持度定义为：

采用概率的形式等价地表示为：

显然，support(X→Y)与support(Y→X)是相等的。例如，在表5.1的事务数据库D中，总的元组数为9，同时包含i1和i2的元组数为4，则

support(i1→i2)=support(i2→i1)=4/9=0.44，这里相当于X={i1}，Y={i2}。

支持度是一种重要性度量，因为低支持度的规则可能只是偶然出现。

从实际情况看，低支持度的规则多半是没有意义的。

例如，顾客很少同时购买a、b商品，想通过对a或b商品促销（降价）来提高另一种商品的销售量是不可能的。

3、置信度

定义5.4 给定一个全局项集I和事务数据库D，一个定义在I和D上的关联规则形如X→Y，其中X、Y∈I，且X∩Y=Ф，它的置信度（或可信度、信任度）是指包含X和Y的事务数与包含X的事务数之比，即：

采用概率的形式等价地表示为：

其中P(Y|X)表示Y在给定X下的条件概率。

置信度确定通过规则进行推理具有的可靠性。对于规则X→Y，置信度越高，Y在包含X的事务中出现的可能性越大。

　显然confidence(X→Y)与confidence(Y→X)不一定相等。例如，

confidence(i1→t2)=4/6=0.67，confidence (i2→t1)=4/7=0.57。

对于形如X→Y关联规则，support(X→Y)≤confidence(X→Y)总是成立的。

一个规则的支持度总是不大于其置信度。

定义5.5  给定D上的最小支持度（记为min_sup）和最小置信度（记为min_conf），分别称为最小支持度阈值和最小置信度阈值，同时满足最小支持度阈值和最小置信度阈值的关联规则称为强关联规则。

也就是说，某关联规则的最小支持度≥min_sup、最小置信度≥min_conf，则它为强关联规则。

三、频繁项集

定义5.6给定全局项集I和事务数据库D，对于I的非空子集I1，若其支持度大于或等于min_sup，则称I1为频繁项集（Frequent Itemsets）。

若I包含m个项，那么可以产生2m-1个非空项集。

　例如，I={i1，i2，i3}，可以产生的非空项集为{i1}，{i2}，{i3}，{i1，i2}，{i1，i3}，{i2，i3}，i1，i2，i3}，共7个。 

定义5.7  对于I的非空子集I1，若某项集I1中包含有I中的k个项，称I1为k-项集。

若k-项集I1是频繁项集，称为频繁k-项集。显然，一个项集是否频繁，需要通过事务数据库D来判断。

四、挖掘关联规则的基本过程

挖掘关联规则就是找出事务数据库D中的强关联规则，通常采用以下两个判断标准：

最小支持度（包含）：表示规则中的所有项在事务数据库D中同时出现的频度应满足的最小频度。最小置信度（排除）：表示规则中前件项的出现暗示后件项出现的概率应满足的最小概率。

挖掘强关联规则两个基本步骤如下：

①找频繁项集：通过用户给定最小支持度阈值min_sup，寻找所有频繁项集，即仅保留大于或等于最小支持度阈值的项集。

②生成强关联规则：通过用户给定最小置信度阈值min_conf，在频繁项集中寻找关联规则，即删除不满足最小置信度阈值的规则。

关联规则

关联规则