-
Apriori
算法详解之【一、相关概念和核心步骤】
Apriori
算法核心步骤
感谢红兰整理的
PPT
,简单易懂,现在将其中精彩之处整理,与大家分享。
一、
Apriori
算法简介:
Apriori
算法是一种挖掘关联规则的频繁项集算
法,其核心思想是通过候
选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。
p>
Apriori
(先验的,推测的)算法
应用
广泛,可用于消费市场价格分析,猜测顾客的消费习惯;网络安全领域中的入侵检测
技术;可用
在用于高校管理中,根据挖掘规则可以有效地辅助学校管理部门有针对性的开
展贫困助学工作;
也可用在移动通信领域中,指导运营商的业务运营和辅助业务提供商的
决策制定。
二、挖掘步骤:
1.
依据支持度找出所有频繁项集(频度)
2.
依据置信度产生关联规则(强度)
三、基本概念
对于
A->B
①支持度:
P(A
∩
B)
,既
有
A
又有
B
的
概率
②置信度:
< br>P(B|A)
,在
A
发生的事件
中同时发生
B
的概率
p(AB)/P(A)
例如购物篮分析:牛奶
?
面包
<
/p>
例子:
[
支持度:
3%
,置信度:
40%]
1
支持度
3%
:意味着
3%
顾客同时购买牛奶和
面包
置信度
40%
< br>:意味着购买牛奶的顾客
40%
也购买面包
③如果事件
A
中包含
p>
k
个元素,那么称这个事件
A
为
k
项集事件
A
满足最小支持度阈值的事件
称为频繁
k
项集。
④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则
四、实现步骤
Aprior
i
算法是一种最有影响的挖掘布尔关联规则频繁项集的算法
Ap
riori
使用一种称作逐层搜
索的迭代方法,“
K-1
项集”用于搜索“
K
项集”。
首先,找出频繁
“
1
项集”的集合,该集合记作
L1
。
L1
用于找频繁“
2
p>
项集”的集合
L2
,而
L2
用于找
L3
。如此下去,直到
不能找到“
K
项集”。找每个
Lk
p>
都需要一次数据库扫描。
核心思想是:连
接步和剪枝步。连接步是自连接,原则是保证前
k-2
项相同,
并按照字典顺序连
接。剪枝步,是使任一频繁项集的所有非空子集也必须是频繁的。反之
,如果某
个候选的非空子集不是频繁的,那么该候选肯定不是
频繁的,从而可以将其从
CK
中删除。
简单的讲,
1
、发现频繁项集,过程为
(
1
)扫描(
2
)计数(
3
)比较(
4
)产生频繁项集(
5
)连
接
、剪枝,产生候选项集
重复步骤(
1
)
~
(
5
)直到不能发现更大的频集
2
、产生关联规则,过程为
:
根据前面提到的置
信度的定义,关联规则的产生如下:
(
1
)对于每个频繁项集
L
,产生
p>
L
的所有非空子集;
(
2
)对于
L
的每个非空子集
S
,如果
2
P
(
L
)
/P
(
S
)≧
mi
n_conf
则输出规则
“
S
à
L-S
”
注:
L-S
表示在项
集
L
中除去
S
子集的项集
一、
< br>Apriori
算法伪代码实现:
[plain]
view plaincopy
1.
伪代码描述:
2.
//
找出频繁
1
项集
3.
L1
=find_frequent_1-itemsets(D);
4.
For(k=2;Lk-1 !=null;k++){
3
-
-
-
-
-
-
-
-
-
上一篇:典型法国餐馆菜单
下一篇:产权分析范式-阿尔钦