文档介绍：数据发掘Apriori算法
数据发掘Apriori算法
1 / 14
数据发掘Apriori算法
-
实验报告
实验课程名称：数据发掘
实验项目名称： Apriori 算法
理学院
实验时间： 2014 年 11 月 11 日
数据发掘Apriori算法
数据发掘Apriori算法
14 / 14
数据发掘Apriori算法
-
学生所在学院：理学院专业：统计学班级：
姓名学号实验组
实验时间指导教师成绩
实验项目名称 Apriori 算法
目的及要求：
加 Apriori 算法的理解
剖析、解决以及手能力
程 Apriori 算法
（或算法）原理：
Apriori 算法是一种找繁目集的基本算法。其基根源理是逐搜寻的迭代：繁 K
Lk 集用于搜寻繁 (K+1) 集 Lk+1，这样下去，直到不能够找到度更高的繁集止。种方法依接和剪枝两步来。
算法的第一次遍算每个目的详尽的数量，以确定大型 l 集。随后的遍，第 k 次遍，包括两个段。第一，使用在第 (k-1) 次遍中找到的大集 Lk-1 和用 Aprioir-gen 函数生候集 Ck。接着描数据，算 Ck 中候的支持度。用 Hash 能够有效地确定 Ck中包括在一个定的事 t 中的候。算法以下：
L1 = { 大目集 1 目集 };
(2)
for
(k = 2;
Lk-1
!=
空;
k++)
do
begin
(3)
Ck
= apriori-gen(Lk-1);
// 新的候集
(4) for
所有事
t ∈D
do
begin
(5)
Ct =
subset
(
Ck，t);
//t
中所包括的候
(6)
for
所有候
c ∈Ct
do
++;
end
(9) Lk = {c ∈Ck ≥ minsupp}
end
key = ∪Lk； Apriori-gen 函数：
1]Apriori 候生函数 Apriori-gen 的参数 Lk-1 ，即所有大型 (k-1) 目集的会集。它返回所有大型 k 目集的会集的一个超集 (Superset) 。第一，在 Jion( 接 ) 步，
我把 Lk-1
和 Lk-1 相接以得候的最会集的一个超集
Ck：
(1)
insert
into
Ck
(2)
select
p[1]
，p[2] ，⋯⋯， p[k-1] ，q[k-1]
(3)
from
Lk-1p ，Lk-1q
(4)
where
p[1]
= q[1] ，⋯⋯， p[k-2]=
q[k-2]
， p[k-1]< q[k-
接着，在 Prune( 修剪 ) 步，我将除所有的目集
c∈Ck，若是 c 的一些 k-1 子
数据发掘Apriori算法
数据发掘Apriori算法
3 / 14
数据发掘Apriori算法
数据发掘Apriori算法
数据发掘Apriori算法
14 / 14
数据发掘Apriori算法
-
集不在 Lk-1 中，为了说明这个产生过程为什么能保持圆满性，要注意对于
Lk 中的任
何有最小支持度的项目集，任何大小为
k-1 的子集也必定有最小支持度。因此，若是
我们用所有可能的项目扩大 Lk-1
中的每个项目集，此后删除所有 k-1 子集不在 Lk-1
中的项目集，那么我们就能获取
Lk 中项目集的一个超集。
上面的合并运算相当于用数据库中所有项目来扩展
Lk-1 ；若是删除扩展项目集的第 k-1
个项目后获取的 k-1 项目集不在 Lk-1
中，则删除该扩展