数据挖掘Apriori算法.doc

数据发掘Apriori算法
数据发掘Apriori算法
1 / 14
数据发掘Apriori算法
-
条件
p[k-1]
< q[k-1] 保证不会出现同样的扩展项。因此，经过合并运算，
Ck>Lk。近似
原因在删除运算中，删除
Ck 中其 k-1
子项目集不在 Lk-1 中的项目集，同样没有删除
包括在 Lk 中的项目集。
(1)
for
所有项目集 c ∈Ck
do
(2)
for
所有 c 的
(k-1)
子集 s
do
(3) if
(s ￠Lk-1)
then
从 Ck中删除 c
比方： L3 为{{1
2
3} ，{1 2
4} ，{1
3 4} ， {1 3 5} ， {2 3 4}}
。 Jion 步
骤此后， C4为 {{1
2
3 4} ，{1
3 4
5}} 。Prune 步骤将删除项集 {1
3 4
5} ，
因为项集 {1 4
5} 不在 L3 中。
Subset 函数：
候选项目集 Ck 积蓄在一棵 Hash树中。Hash 树的一个节点包括了项集的一个链表
( 一个
叶节点 ) 或包括了一个 Hash表( 一个内节点 ) 。在内节点中， Hash 表的每个 Bucket 都指向另一个节点。 Hash 树的根的深度定义为 1。在深度 d 的一个内节点指向深度 d+1 的节点。项目集积蓄在叶子中。要加载一个项目集 c 时，从根开始向下直到一个叶子。
在深度为 d 的一个内节点上，要决定采用哪个分枝，能够对此项目集的第 d 个项目使
用一个 Hash函数，此后随从相应 Bucket 中的指针。所有的节点最初都创办成叶节点。
当一个叶节点中项集数量高出某个指定的阈值时，此叶节点就转为一个内节点。
从根节点开始， Subset 函数搜寻所有包括在某个事务 t 中的候选，方法以下：若处于一个叶子，就搜寻此叶子中的哪些项目集是包括在 t 中的，并对它们附加引用指向答案会集。若处于一个内节点，而且是经过 Hash项目 i 从而到达此节点的，那么就对 t
i 此后的每个项目进行 Hash，并对相应 Bucket 中的节点递归地应用这个过程。 对于根节点，就对 t 中的每个项目进行 Hash。
尽管 Apriori 算法已经能够压缩候选数据项集 Ck，可是对于频频项集特别是 2 维的候选数据项集产生依旧需要大量的积蓄空间。 也就是说对于 2 维的候选数据项集， Apriori 算法的剪枝操作几乎不起任何作用。比方： 1 维高频数据项集 L1 的规模是 O(n) ，则 2 维候选数据项集的规模将达到 O(n2) 。若是我们考虑一般情况， 即在没有支持度的情况
1 维高频数据项集 L1 的规模是 103，则 2 维候选数据项集的规模 C2 将达到C1000≈5×105．这种空间复杂度以指数形式的增添，使得这个经典的算法的执行效率很难让人满意． Apriori 算法的两大缺点就是产生大量的候选集， 以及需重复扫描数据库。
数据发掘Apriori算法
数据发掘Apriori算法
5 / 14
数据发掘Apriori算法
数据发掘Apriori算法
数据发掘Apriori算法
14 / 14
数据发掘Apriori算法
-
实验硬件及软件平台：
Windows7、
实验内容（包括实验详尽内容、算法剖析、源代码等等） ：
#include<iostream>
#include<string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
class Apriori
{
public:
Apriori(size_t is =0,unsigned int mv=0)
{
item_size = is;
min_value = mv;
}
//~Apriori() {};
void getItem();
map< vector<string>,unsigned