频繁项集Apriori算法(2)

2.1 频繁k-1项集生成2项子集，这里的2项指的生成的子集中有两个k-1项集。使如有3个2项频繁集｛a, b｝｛b, c｝｛c, f｝，则它所有的2项子集为｛｛a, b｝｛b, c｝｝｛｛a, b｝｛e, f｝｝｛｛b, c｝｛c, f｝｝

2.2 对由2.1生成的2项子集中的两个项集根据上面所述的定理 i 进行连接，生成k项集。

2.3 对k项集中的每个项集根据如上所述的定理 ii 进行计算，舍弃掉子集不是频繁项集即不在频繁k-1项集中的项集。

2.4 扫描，计算2.3步中过滤后的k项集的支持度，舍弃掉支持度小于阈值的项集，生成频繁k项集。

3. 当当前生成的频繁k项集中只有一个项集时循环结束。

关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性，是数据挖掘的一个重要技术， 用于从大量数据中挖掘出有价值的数据项之间的相关关系。 其中关联规则挖掘的最经典的例子就是沃尔玛的啤酒与尿布的故事 ，通过对超市购物篮数据进行分析，即顾客放入购物篮中不同商品之间的关系来分析顾客的购物习惯，发现美国妇女们经常会叮嘱丈夫下班后为孩子买尿布，30%-40%的丈夫同时会顺便购买喜爱的啤酒，超市就把尿布和啤酒放在一起销售增加销售额。

二.基本概念

关联规则挖掘是寻找给定数据集中项之间的有趣联系。如下图所示：

其中，I={I1,I2,…Im}是m个不同项目的集合,集合中的元素称为项目（Item）。项目的集合I称为项目集合（Itemset），长度为k的项集成为k-项集。设任务相关的数据D是事务的集合，其中每个事务T是项的集合，使得 T ?? I 。每个事务有一个标识符TID；设A是一个项集，事务T包含A当且仅当 A??I ，则关联规则形式为A=>B（其中 A ?? I ， B ?? I ，并且 A ∩ B = ??）。

在关联规则度量中有两个重要的度量值：支持度和置信度 。对于关联规则R:A=>B，则：

1. 支持度（suppport ）： 是交易集中同时包含A和B的交易数与所有交易数之比。

Support(A=>B)=P(A∪B)=count(A∪B)/|D|

2. 置信度（confidence ）： 是包含A和B交易数与包含A的交易数之比。

Confidence(A=>B)=P(B|A)=support(A∪B)/support(A)

如上图中D，包含4个事务，项集I={I1,I2,I3,I4,I5}，分析关联规则：I1=>I4，事务1、4包含I1，事务4同时包含I1和I4。

支持度support=1/4=25%（1个事务同时包含I1和I4,共有4个事务）指 在所有交易记录中有25%的交易记录同时包含I1和I4项目

置信度confidence=1/2=50%（1个事务同时包含I1和I4,2个事务包含I1）指 50%的顾客在购买I1时同时还会购买I4

使用关联规则对购物篮进行挖掘，通常采用两个步骤进行： 下面将通超市购物的例子对关联规则挖掘进行分析。

a.找出所有频繁项集（文章中我使用Apriori算法>=最小支持度的项集）

b.由频繁项集产生强关联规则（>=最小支持度和最小置信度）

三.举例：Apriori算法挖掘频繁项集

Apriori算法是一种对有影响的挖掘布尔关联规则频繁项集的算法，通过算法的连接和剪枝即可挖掘频繁项集。 补充频繁项集相关知识： K-项集：指包含K个项的项集； 项集的出现频率：指包含项集的事务数，简称为项集的频率、支持度计数或计数； 频繁项集：如果项集的出现频率大于或等于最小支持度计数阈值，则称它为频繁项集，其中频繁K-项集的集合通常记作L k 。

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-62906-2.html