关联分析学习笔记

1035

收藏 2017-07-28

整理一下最近关于关联分析学习的相关内容。参考的内容如下：
http://blog.csdn.net/bone_ace/article/details/46648965

http://www.cnblogs.com/ybjourney/p/4851540.html

《数据挖掘——概念与计数》3rd Edition

一、什么是关联分析
顾名思义，关联分析就是寻找事务之间的关联关系，一个耳熟能详的例子就是“啤酒与尿布”的问题。挖掘事务内部的关联关系，对于制定精准营销策略具有指导意义。
二、关联分析中术语的定义
为了介绍方便，先给出一个例子：

TID	商品ID
T01	I1,I2,I5
T02	I2,I4
T03	I2,I3
T04	I1,I2,I4
T05	I1,I3
T06	I2,I3
T07	I1,I3
T08	I1,I2,I3,I5
T09	I1,I2,I3

事务：每一个交易记录称为一个事务。在上例，共有9个事务。
项：交易中的每个物品称为项。在上例，I1,I2等均为项。
项集：项的集合。例如，｛I1,I2,I5｝、｛I1,I2,I3｝、｛I1,I3｝等均为项集。
k-项集：元素个数为k的项集称为k-项集。例如，｛I1,I3｝、｛I1,I2,I3,I5｝、｛I1,I2,I3｝分别为2-项集、4-项集与3-项集。
支持度计数：某个项集出现在n个事务中，则该项集的支持度计数为n。例如，项集｛I1,I3｝的支持度计数为4。
支持度：某个项集的支持度计数除以事务总数，一般以百分比表示。例如，项集｛I1,I3｝的支持度为4/9。
频繁项集：支持度大于或等于某个阈值的项集叫做频繁项集。例如，指定阈值为30%，则项集｛I1,I3｝是频繁项集，项集｛I2,I4｝不是频繁项集。
先导和后继：对于关联规则X→Y，X叫做先导，Y叫做后继。
置信度：对于规则X→Y，其置信度（confidence（X,Y））是指项集｛X,Y｝的支持度除以｛X｝的支持度，即confidence（X,Y）=包含X和Y的事务数/包含X的事务总数。
强关联规则：对于某个关联规则:X→Y，它的支持度(support（X→Y）)是指，同时包含其先导与后继的事务数与总事务数的比值，即：support（X→Y）=包含X和Y的事务数/事务总数。若关联规则的支持度与置信度均大于支持度阈值与置信度阈值，则称其为强关联规则。
三、两种算法
关联分析的最终目的就是寻找强关联规则。常用的算法有Apriori算法、FP-Growth算法，下面分别介绍。
<1> Apriori算法
算法思路：由频繁（k-1）-项集生成k-项集，然后根据支持度阈值判断生成的k-项集是否为频繁项集。
两个频繁项集是可连接的，如果它们除最后一个元素之外都是相同的，这里对频繁项集内的元素按照字典序排列。
1.在给出的例子中，指定支持度阈值为2/9。1.首先确定频繁1-项集：

项集	支持度计数	支持度
｛I1｝	6	2/3
｛I2｝	7	7/9
｛I3｝	6	2/3
｛I4｝	2	2/9
｛I5｝	2	2/9

由上表可知，频繁1-项集为｛I1｝、｛I2｝、｛I3｝、｛I4｝、｛I5｝。
2.然后列出所有可能由频繁1-项集组成的2-项集：

项集	支持度计数	支持度
｛I1,I2｝	4	4/9
｛I1,I3｝	4	4/9
｛I1,I4｝	1	1/9
｛I1,I5｝	2	2/9
｛I2,I3｝	4	4/9
｛I2,I4｝	2	2/9
｛I2,I5｝	2	2/9
｛I3,I4｝	0	0
｛I3,I5｝	1	1/9
｛I4,I5｝	0	0

由上表可知，频繁2-项集为｛I1,I2｝、｛I1,I3｝、｛I1,I5｝、｛I2,I3｝、｛I2,I4｝、｛I2,I5｝。
3.继续列出所有可能由频繁2-项集组成的3-项集：

项集	支持度计数	支持度
｛I1,I2,I3｝	2	2/9
｛I1,I2,I5｝	2	2/9

由上表可知，频繁3-项集为｛I1,I2,I3｝、｛I1,I2,I5｝。
在这一步中，首先由频繁2-项集产生的集合共为｛｛I1,I2,I3｝、｛I1,I2,I5｝、｛I1,I3,I5｝、｛I2,I3,I4｝、｛I2,I3,I5｝、｛I2,I4,I5｝｝。根据先验性质，频繁项集的所有子集必须是频繁的，可以确定后4个项集不可能是频繁的，故剔除。
可以进一步验证，由频繁3-项集产生的4-项集均不是频繁的，故算法至此终止。
4.由频繁项集产生关联规则步骤如下：

对于每个频繁项集p，产生p的所有非空子集。
对于p的每个非空子集s，如果p的支持度除以s的支持度不小于置信度阈值，则输出规则“s→（p-s）”

由于规则由频繁项集产生，因此生成的规则自动满足支持度阈值。

对于得到的3-项集｛I1,I2,I3｝，它的所有非空子集为｛I1｝、｛I2｝、｛I3｝、｛I1,I2｝、｛I1,I3｝、｛I2,I3｝，可以得到的关联规则及相应的支持度和置信度如下：

规则	置信度
I1→｛I2,I3｝	33%
I2→｛I1,I3｝	29%
I3→｛I1,I2｝	33%
｛I1,I2｝ →I3	50%
｛I1,I3｝ →I2	50%
｛I2,I3｝ →I1	50%

对于得到的3-项集｛I1,I2,I5｝，它的所有非空子集为｛I1｝、｛I2｝、｛I5｝、｛I1,I2｝、｛I1,I5｝、｛I2,I5｝，可以得到的关联规则及相应的支持度和置信度如下：

规则	置信度
I1→｛I2,I5｝	33%
I2→｛I1,I5｝	29%
I5→｛I1,I2｝	100%
｛I1,I2｝ →I5	50%
｛I1,I5｝ →I2	100%
｛I2,I5｝ →I1	100%

附件列表

新建 Microsoft Visio 绘图.jpg

原图尺寸 62.77 KB

新建 Microsoft Visio 绘图2.bmp

原图尺寸 296.26 KB

新建 Microsoft Visio 绘图.bmp

原图尺寸 826.54 KB

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

全部回复

Mutually_Sincer

2017-7-28 11:23:59

<2>FP树算法
FP算法只需对数据集扫描两次。
第一次与Apriori算法相同，输出频繁1-项集的集合，并得到它们的支持度计数。设支持度阈值为2。频繁项的集合按支持度计数递减排序。
结果记为L，则L={{I2:7},{I1:6},{I3:6},{I4:2},{I5:2}}。
然后，FP树构造如下：首先，创建树的根节点，用“NULL”标记。第二次扫描数据集，每个事务中的项都按L中的次序处理，并对每个事务创建一个分枝。例如，第一个事务“T001：I1,I2,I5”包含三个项，导致构造树的包含三个结点的第一个分枝（按照L中的顺序）<I2:1><I1:1><I5:1>。I2连接到NULL，I1连接到I2，I5连接到I2。第二个事务T002按L的次序包含项I2和I4，它将导致一个分析，I2连接到NULL，I4连接到I2。然而，该事务可以与第一个事务共享I2结点，因此，将节点I2的计数增加1，并创建一个新结点<I4:1>。类似的，可以对其余的事务进行类似的操作。
为了方便表的遍历，创建一个项头表，使每项通过一个结点链指向它在树中的位置。