数据挖掘读书笔记--第六章：频繁模式挖掘、关联及相关性
散记知识点
——“哪些商品组合频繁地被顾客同时购买？”
1. 基本概念
1.1 频繁项集、闭项集和关联规则
(1) 支持度和置信度
设L={I_{1}, I_{2},...,I_{3}}是项 的集合D是数据库事务的集合包含每个事务 T(是一个非空项集，T \subseteq L)，设项集 A有A \to B的关联规则在事务集中成立，该条规则具有支持度s(表示中包含A \bigcup B的概率)，置信度c(表示中包含的事务同时也包含B的事务的概率)。
规则的支持度 和置信度 是规则兴趣度的两种度量，分别反映了所发现规则的有用性和确定性。
(2) 项集、频繁项集和闭频繁项集
项的集合称为项集。包含k个项的项集称为k项集如{computer, cell phone}为一个2项集。项集出现的频度 是包含项集的事务数，简称为项集的频度、(绝对)支持度(计数) 。(1)中定义的是项集的相对支持度 ，如果一个项集的相对支持度满足于预定义的最小支持度阈值 ，则该项集是频繁项集 。
- 挖掘关联规则的问题可以归结为挖掘频繁项集
关联规则的挖掘过程一般有两步 ：
-
找出所有的频繁项集 ：满足最小支持度的所有项集。
-
由频繁项集产生强关联规则 ：这些规则必须满足最小支持度和最小置信度。
如果项集X在数据集中不存在真超项集 Y(即X \subset Y)使得与在中具有相同的支持度，则项集是闭的。如果在中是闭的和频繁的，则称是闭频繁项集 。如果不存在超项集使得并且在是频繁的，则称是极大频繁项集 。
2. 频繁项集挖掘方法
2.1 Apriori算法
(1) 两条经典的先验性质：
-
频繁项集的所有非空子集一定是频繁的。
-
非频繁项集的所有超集一定不是频繁的。
(2) 两个重要步骤 ：
设L_{k-1}为第k-1步的频繁项集合，C_{k}为下一步的候选项集合。为从找出L_{k}，经历以下两个步骤：
- 连接步 ：为找出，通过将与自身连接产生候选项集合。设l_{i}为的项集，记l_{i}[j]表示的第j项(例如l_{i}[k-1]表示的倒数第2项)。对于(k-1)项集，把项排序，使得$l_{i}[1]l_{1}l_{2}C_{k}kkL_{k}C_{k}k(k-1)L_{k-1}C_{k}L_{k}DC_{1}L_{1}C_{2}DC_{2}L_{2}C_{3}k(k-1)DL_{2}C_{3}lls
Xstep1Dstep2DI_{2}I_{1}I_{2}step3I_{5}I_{5}I_{5}
(k+1)k
A \to B[support, confidence, correlation]
lift(A, B)=\frac{P(A \bigcup B)}{P(A)P(B)}= \frac{P(B/A)}{P(B)}AB
ABall_conf(A, B)=\frac{sup(AUB)}{max{sup(A), sup(B)}}=min{P(A | B), P(B|A)}ABmax_conf(A, B)=max{P(A | B), P(B|A)}Kulc(A, B)=\frac{1}{2}(P(A | B)+ P(B|A))cosine(A,B)=\frac{P(A \bigcup B)}{\sqrt{P(A) \times P(B)}}=\frac{sup(AUB)}{\sqrt{sup(A) \times sup(B)}}=\sqrt{P(A|B) \times P(B|A)}
ABD_{1}D_{2}D_{1}D_{2}D_{3}D_{1}D_{3}D_{4}
\overline{mc}\overline{mc}AB
IR(A, B)= \frac{|sup(A)-sup(B)|}{sup(A)+sup(B)-sup(A\bigcup B)}ABD_{5}D_5D_6