【机器学习】【关联分析】【Apriori】
关联分析
关联规则(association rules)是常用的无监督学习算法,目标是
一句话简介:找到特征之间有意义的关系,构建有用的特征和对应的应用。
关联规则通常分两类:一是简单关联(事物之间的普通关系),二是序列关联(考虑事物普通关系同时关注时间先后顺序)
简单关联规则
事务:我们的分析对象,可理解为一种行为,由事务标识TID和项目集合组成
项集:事务中一组项目的集合,是项目全体。通常指具体的东西,如一种商品
按照实图理解,上图有4个事务,有5个项目,第一个事务有三个项目,称为X是一个3-项集
关联规则一般表现形式:
- X叫前项(项目和项集),Y叫后项(结论或事实)
- 表示规则支持度为,表示规则置信度为
有效性判断
我们可以探索到很多关联规则,但不是都是有效的,有些是令人信服的程度不高,所以我们需要有指标去度量该关联规则是否有效。置信度和支持度
- 规则置信度(Confidence)
对规则的准确度的测量,事务中包含项目A同时也包含项目B的概率:
- 规则支持度(Support)
对应用的普适性的测量,项目A和B同时出现概率:
实用性判断
有些规则或许是有效的,但不一定实用,例如“怀孕->女性”没啥实用价值,同时我们还要考虑这个规则是否有指导意义,帮我们在现有基础上做出有价值的优化。为了避免出现AtoB置信度很高是因为本身B的支持度很高,而实际与A没关系。
- 规则提升度(Lift),置信度与后项支持度之比:
提升度可以反映A的出现对B出现的影响程度,若A不影响B的出现,代表A与B相互独立,那么P(AB)=P(A)P(B),提升度为1. 若提升度大于1,则A对B有促进作用
Apriori算法
核心目的:解决海量数据中快速找到关联规则
频繁项集
指的是大于等于最小支持度的项集,包含k个项目,叫频繁k-项集,
两大性质:
- 频繁项集的子集必为频繁项集。{A,C} {A},{C}
- 非频繁集的超集一定也是非频繁的。{D}{A,D},{C,D}
若的所有超集都是频繁项集,可称其为最大频繁k-项集,有它可以知道得到的关联规则具有较高普适性。
寻找频繁项集
这一步是apriori的核心,目的就是为了提高寻找规则的效率
采用的方法是迭代寻找超集,并在超集中发现最大频繁项集. 具体流程:
- K=1,计算 K 项集的支持度;
- 筛选掉小于最小支持度的项集;
- 如果项集为空,则对应 K-1 项集的结果为最终结果。
- 否则 K=K+1,重复 1-3 步。
在最大频繁项集中产生简单关联规则
计算所有非空子集的置信度:
例如{A,B,C}有子集,{A}{B}{C}{A,B}{A,C}{B,C}
置信度达到最低要求,就是有效的~
FP-Growth算法
根据上面的方法,我们可以想到,如果项目特别多,不断的做排列组合,还要多次重复扫描数据集去计算支持度,是非常计算资源的,所以有人提出了FP-Growth算法
特点:
- 用一个FP树存储频繁项集,在创建前把不满足最小支持度的项都删除,减少存储空间
- 整个生成过程只遍历数据集两次,大大减少计算量
步骤:
-
创建项头表(item header table)
这个表的作用是帮助构建FP树,同时提供频繁项集的索引。
先扫描一遍数据集,删除不满足最小支持度的单个项,不满足最小支持度的单项的超集都要剔除,然后按照支持度从高到低排序,形状如下:
链表指的是该项在FP树中的链表,初始时为空。 -
构建FP树
根节点为NULL,再次扫描筛选后的数据集上的每一条数据,若节点存在就计数+1,如果不存在就创建,此时会更新项投表的链表。类似于下图: -
通过FP树去挖掘频繁项集
用到一个概念叫“条件模式基”,意思是以要挖掘的节点作为叶子节点,从底部向上求出子树,将子树的祖先节点设置为叶子节点之和。【这个解释不好理解,其实就是把属于该节点的子树凑在一起】,请看实例解释:
- F的条件模式基为{A:2,C:2,E:2,B:2},最大的频繁项集就是{A:2,C:2,E:2,B:2,F:2},其实还有2项集和3项集就不写了。
- 我们可以看看D,D有两条路,条件模式基为{A:2,C:2,E:1,G:1},在条件模式基下,E和G的支持度都低于阈值,故删除,最后得到最大频繁项集{A:2,C:2,D:1}
这样就可以求得我们想看的单项的频繁项集了