关联分析基本概念解析

关联规则是描述数据库中数据项之间所存在关系的规则，即根据事务中某些项的出现可导出另一些项在同一事务中也出现，即隐藏在数据间的关联或相互关系。关联规则的学习属于无监督学习，在实际生活中的应用很多，例如，分析顾客超市购物记录，可以发现很多隐含的关联规则，如经典的啤酒和尿布问题。

1.关联规则定义

首先给出各项的集合I＝{I1，I2，…，Im}，关联规则是形如X→Y的蕴含式，其中X、Y属于I，且X与Y的交集为空。

2.指标定义

在关联规则挖掘中有4个重要指标。

1)置信度(Confidence)

定义:设W中支持物品集A的事务中有c%的事务同时也支持物品集B，c%称为关联规则A→B的置信度，即条件概率P(B｜A)。

实例说明:以上述的啤酒和尿布问题为例，置信度就回答了这样一个问题——如果一个顾客购买啤酒，那么他也购买尿布的可能性有多大呢?在上述例子中，购买啤酒的顾客中有50%的顾客购买了尿布，所以置信度是50%。

2)支持度(Support)

定义:设W中有s%的事务同时支持物品集A和B，s%称为关联规则A→B的支持度。支持度描述了A和B这两个物品集的交集C在所有事务中出现的概率，即P(A∩B)。

实例说明:某天，共有100个顾客到商场购买物品，其中有15个顾客同时购买了啤酒和尿布，那么上述关联规则的支持度就是15%。

3)期望置信度(Expected Confidence)(www.xing528.com)

定义:设W中有e%的事务支持物品集B，e%称为关联规则A→B的期望置信度。期望置信度是指单纯的物品集B在所有事务中出现的概率，即P(B)。

实例说明:如果某天共有100个顾客到商场购买物品，其中有25个顾客购买了尿布，则上述关联规则的期望置信度就是25%。

4)提升度(Lift)

定义:提升度是置信度与期望置信度的比值，反映了“物品集A的出现”对物品集B的出现概率造成了多大的影响。

实例说明:上述实例中，置信度为50%，期望置信度为25%，则上述关联规则的提升度为2(50%/25%)。

3.关联规则挖掘定义

给定一个交易数据集T，找出其中所有支持度大于等于最小支持度、置信度大于等于最小置信度的关联规则。

有一个简单的方法可以找出所需要的规则，即穷举项集的所有组合，并测试每个组合是否满足条件。一个元素个数为n的项集的组合个数为2n－1(除去空集)，所需要的时间复杂度明显为o(2n)。对于普通的超市，其商品的项集数在1万以上，用指数时间复杂度的算法不能在可接受的时间内解决问题。怎样快速挖掘出满足条件的关联规则是关联挖掘需要解决的主要问题。

仔细想一下，我们会发现对于{啤酒→尿布}、{尿布→啤酒}这两个关联规则的支持度实际上只需要计算{尿布，啤酒}的支持度，即它们交集的支持度。于是我们把关联规则挖掘分如下两步进行。

(1)生成频繁项集:这一阶段找出所有满足最小支持度的项集，找出的这些项集称为频繁项集。

(2)生成强规则:在上一步产生的频繁项集的基础上生成满足最小置信度的规则，产生的规则称为强规则。