一、数据挖掘定义

今天我们来讲述其中的关联分析

三、关联分析

典型例子：啤酒与尿布

常用方法 —— 关联规则挖掘 (Association Rule Mining)

        给出事务的集合, 能够发现一些规则：𝐴 => 𝐵

        当事务中某些子项出现时，预测其他子项也出现

基本概念：

Association Rule（关联规则）

    形如X → Y的表达式，X, Y均为项集

    例：{Milk, Diaper} →{Beer}

Confidence (置信度)

    度量包含X的事务中同时出现Y的频率

    例：对于关联规则{Milk, Diaper} →{Beer}

    confidence({Milk, Diaper} →{Beer})= 2/3

强关联规则

    用户自行设定最小置信度阈值min _conf，置信度大于min _conf的规则称为强关联规则

    例：设min _conf = 0.5，则{Milk, Diaper} →{Beer}为强关联规则

四、APriori算法

生成频繁项集

核心思想：广度优先搜索，自底而上遍历，逐步生成候选集与频繁项集

反单调性原理：如果一个项集是频繁的，则它的所有子集一定也是频繁

成立原因：

        ∀X, Y: X ⊆ Y → Support X ≥ Support(Y)

        依据该性质，对于某k+1项集，只要存在一个k项子集不是频繁项集， 则可以直接判定该项集不是频繁项集

 

算法步骤

        连接步：从频繁 K-1 项集生成候选K项集

        剪枝步：从候选 K 项集筛选出频繁K项集

举个例子：

下图为某商店的用户购买记录，共有9个事务，A-Priori假定事务中的项按字典次序存放。

(1) 在算法的第一次迭代，每个项都是候选1项集的集合的成员。算法简单地扫描所有的事务，对每个项的出现次数计数

(2) 设最小支持度计数=2，可以确定频繁1项集的集合

(3) 使用L1⋈ L1产生候选2项集的集合

(4) 扫描数据集，计算中每个候选项集的支持度

(5)最小支持度计数=2，确定频繁2项集的集合

(6) 使用L2⋈ L2产生候选3项集的集合

(7) 扫描数据集，计算中每个候选项集的支持度

(9) 使用L3⋈ L3产生候选4项集的集合C4，尽管连接产生结果  ，这个项集被

剪去，因为它的子集 不是频繁的。则C4 = ∅ ,因此算法终止，找出了所有的

频繁项集如下

五、生成规则

关联规则挖掘的第二步：如何从频繁项集中生成规则？

若{A,B,C,D}是频繁项集, 候选规则有14种:

ABC →D, ABD →C, ACD →B, BCD →A,

A →BCD,B →ACD, C →ABD, D →ABC

AB →CD,AC → BD, AD → BC, BC →AD,BD →AC, CD →AB,

若, 则有 种候选的关联规则(忽略L → 和 → L)

六、辛普森悖论