数据挖掘Apriori算法

1、 实 验 报 告实验课程名称： 数据挖掘 实验项目名称： Apriori算法 理 学 院实验时间： 2014 年 11 月 11 日学生所在学院：理学院 专业： 统计学 班级：姓 名学 号实验组实验时间指导教师成 绩实验项目名称Apriori算法实验目的及要求：1. 加强对Apriori算法的理解2. 锻炼分析问题、解决问题以及动手能力3. 编程实现Apriori算法实验（或算法）原理：Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代：频繁K项Lk集用于搜索频繁(K+1)项集Lk+1，如此下去，直到不能找到维度更高的频繁项集为止。这种方法依赖连接和剪枝这两步来实现。算

2、法的第一次遍历仅仅计算每个项目的具体值的数量，以确定大型l项集。随后的遍历，第k次遍历，包括两个阶段。首先，使用在第(k-1)次遍历中找到的大项集Lk-1和用Aprioir-gen函数产生候选项集Ck。接着扫描数据库，计算Ck中候选的支持度。用Hash树可以有效地确定Ck中包含在一个给定的事务t中的候选。算法如下：(1) L1 = 大项目集1项目集;(2) for  (k = 2; Lk-1 != 空; k+)  do  begin(3

3、)  Ck = apriori-gen(Lk-1);      /新的候选集(4) for  所有事务 t D  do  begin(5)      Ct = subset ( Ck，t);     /t中所包含的候选 (6)  for  所有候选&

4、#160;c Ct  do (7) c.count+;(8) end(9) Lk = c Ck | c.count  minsupp(10) end(11) key = Lk；Apriori-gen函数：1Apriori候选产生函数Apriori-gen的参数Lk-1，即所有大型(k-1)项目集的集合。它返回所有大型k项目集的集合的一个超集(Superset)。首先，在Jion(连接)步骤，我们把Lk-1和Lk-1相连接以获得候选的最终集合的一个

5、超集Ck：(1) insert  into  Ck(2) select  p1，p2，pk-1，qk-1(3) from  Lk-1p，Lk-1q(4) where  p1 = q1，pk-2 = qk-2，pk-1 < qk-接着，在Prune(修剪)步骤，我们将删除所有的项目集 cCk，如果c的一些k-1子集不在Lk-1中，为了说明这个产生过程为什么能保持完全性，要注意对于Lk

6、中的任何有最小支持度的项目集，任何大小为k-1的子集也必须有最小支持度。因此，如果我们用所有可能的项目扩充Lk-1中的每个项目集，然后删除所有k-1子集不在Lk-1中的项目集，那么我们就能得到Lk中项目集的一个超集。上面的合并运算相当于用数据库中所有项目来扩展Lk-1；如果删除扩展项目集的第k-1个项目后得到的k-1项目集不在Lk-1中，则删除该扩展项目集。条件pk-1 < qk-1保证不会出现相同的扩展项。因此，经过合并运算，Ck>Lk。类似原因在删除运算中，删除Ck中其k-1子项目集不在Lk-1中的项目集，同样没有删除包含在Lk中的项目集。(1) 

7、for  所有项目集c Ck  do(2)  for  所有c的 (k-1) 子集 s  do (3) if (sLk-1)  then(4) 从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

8、 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

9、中的指针。所有的节点最初都创建成叶节点。当一个叶节点中项集数量超过某个指定的阈值时，此叶节点就转为一个内节点。从根节点开始，Subset函数寻找所有包含在某个事务t中的候选，方法如下：若处于一个叶子，就寻找此叶子中的哪些项目集是包括在t中的，并对它们附加引用指向答案集合。若处于一个内节点，而且是通过Hash项目i从而到达此节点的，那么就对t中i之后的每个项目进行Hash，并对相应Bucket中的节点递归地应用这个过程。对于根节点，就对t中的每个项目进行Hash。尽管Apriori算法已经可以压缩候选数据项集Ck，但是对于频繁项集尤其是2维的候选数据项集产生仍然需要大量的存储空间。也就是说对于2

10、维的候选数据项集，Apriori算法的剪枝操作几乎不起任何作用。例如：1维高频数据项集L1的规模是O(n)，则2维候选数据项集的规模将达到O(n2)。如果我们考虑一般情况，即在没有支持度的情况下1维高频数据项集L1的规模是103，则2维候选数据项集的规模C2将达到C10005×105这种空间复杂度以指数形式的增长，使得这个经典的算法的执行效率很难让人满意Apriori算法的两大缺点就是产生大量的候选集，以及需重复扫描数据库。 实验硬件及软件平台：Windows7、Visual C+ 6.0实验内容（包括实验具体内容、算法分析、源代码等等）：#include<iostream&g

11、t; #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 int> find_freitem

12、();/求事务的频繁项 /连接连个k-1级频繁项，得到第k级频繁项 map< vector<string>,unsigned int > apri_gen(unsigned int K , map< vector<string>,unsigned int > K_item); /展示频繁项集 void showAprioriItem(unsigned int K,map< vector<string>,unsigned int > showmap); private: map< int , vector<str

13、ing> > item;/存储所有最开始的事务及其项 map< vector<string>,unsigned int > K_item;/存储频繁项集 size_t item_size;/事务数目 unsigned int min_value;/最小阈值 ; void Apriori:getItem()/用户输入最初的事务集 int ci = item_size; for (int i=0;i<ci;i+) string str; vector<string> temp; cout<<"请输入第"<&

14、lt;i+1<<"个事务的项集(wang end)：" while (cin>>str && str !="wang") temp.push_back(str); sort(temp.begin(),temp.end(); pair< map<int ,vector<string> >:iterator , bool> ret = item.insert(make_pair(i+1 ,temp); if (!ret.second) -i; cout<<"你输

15、入的元素已存在！请重新输入！"<<endl; cout<<"-运行结果如下：-"<<endl; map< vector<string>,unsigned int> Apriori:find_freitem() unsigned int i = 1; bool isEmpty = false; map< int , vector<string> >:iterator mit ; for (mit=item.begin();mit != item.end();mit+) vector&

16、lt;string> vec = mit->second; if (vec.size() != 0) break; if (mit = item.end()/事务集为空 isEmpty = true; cout<<"事务集为空！程序无法进行."<<endl; map< vector<string>,unsigned int> empty; return empty; while(1) map< vector<string>,unsigned int > K_itemTemp = K_item

17、; K_item = apri_gen(i+,K_item); if (K_itemTemp = K_item) i = UINT_MAX; break; /判断是否需要进行下一次的寻找 map< vector<string>,unsigned int > pre_K_item = K_item; size_t Kitemsize = K_item.size(); /存储应该删除的第K级频繁项集，不能和其他K级频繁项集构成第K+1级项集的集合 if (Kitemsize != 1 && i != 1) vector< map< vector&

18、lt;string>,unsigned int >:iterator > eraseVecMit; map< vector<string>,unsigned int >:iterator pre_K_item_it1 = pre_K_item.begin() , pre_K_item_it2; while (pre_K_item_it1 != pre_K_item.end() ) map< vector<string>,unsigned int >:iterator mit = pre_K_item_it1; bool isEx

19、ist = true; vector<string> vec1; vec1 = pre_K_item_it1->first; vector<string> vec11(vec1.begin(),vec1.end()-1); while (mit != pre_K_item.end() vector<string> vec2; vec2 = mit->first; vector<string> vec22(vec2.begin(),vec2.end()-1); if (vec11 = vec22) break; +mit; if (mi

20、t = pre_K_item.end() isExist = false; if (!isExist && pre_K_item_it1 != pre_K_item.end() eraseVecMit.push_back(pre_K_item_it1);/该第K级频繁项应该删除 +pre_K_item_it1; size_t eraseSetSize = eraseVecMit.size(); if (eraseSetSize = Kitemsize) break; else vector< map< vector<string>,unsigned in

21、t >:iterator >:iterator currentErs = eraseVecMit.begin(); while (currentErs != eraseVecMit.end()/删除所有应该删除的第K级频繁项 map< vector<string>,unsigned int >:iterator eraseMit = *currentErs; K_item.erase(eraseMit); +currentErs; else if(Kitemsize = 1 ) break; cout<<endl; showAprioriItem

22、(i,K_item); return K_item; map< vector<string>,unsigned int > Apriori:apri_gen(unsigned int K , map< vector<string>,unsigned int > K_item) if (1 = K)/求候选集C1 size_t c1 = item_size; map< int , vector<string> >:iterator mapit = item.begin(); vector<string> vec;

23、 map<string,unsigned int> c1_itemtemp; while (mapit != item.end() )/将原事务中所有的单项统计出来 vector<string> temp = mapit->second; vector<string>:iterator vecit = temp.begin(); while (vecit != temp.end() ) pair< map<string,unsigned int>:iterator , bool > ret = c1_itemtemp.inser

24、t(make_pair(*vecit+ , 1); if (!ret.second) + ret.first->second; +mapit; map<string,unsigned int>:iterator item_it = c1_itemtemp.begin(); map< vector<string>,unsigned int > c1_item; while (item_it != c1_itemtemp.end() )/构造第一级频繁项集 vector<string> temp; if ( item_it->second

25、 >= min_value) temp.push_back(item_it->first); c1_item.insert(make_pair(temp , item_it->second) ); +item_it; return c1_item; else cout<<endl; showAprioriItem(K-1,K_item); map< vector<string>,unsigned int >:iterator ck_item_it1 = K_item.begin(),ck_item_it2; map< vector&l

26、t;string>,unsigned int > ck_item; while (ck_item_it1 != K_item.end() ) ck_item_it2 = ck_item_it1; +ck_item_it2; map< vector<string>,unsigned int >:iterator mit = ck_item_it2; /取当前第K级频繁项与其后面的第K级频繁项集联合，但要注意联合条件 /联合条件：连个频繁项的前K-1项完全相同，只是第K项不同，然后两个联合生成第K+1级候选频繁项 while(mit != K_item.end(

27、) ) vector<string> vec,vec1,vec2; vec1 = ck_item_it1->first; vec2 = mit->first; vector<string>:iterator vit1,vit2; vit1 = vec1.begin(); vit2 = vec2.begin(); while (vit1 < vec1.end() && vit2 < vec2.end() ) string str1 = *vit1; string str2 = *vit2; +vit1; +vit2; if ( K

28、=2 | str1 = str2 ) if (vit1 != vec1.end() && vit2 != vec2.end() ) vec.push_back(str1); else break; if (vit1 = vec1.end() && vit2 = vec2.end() ) -vit1; -vit2; string str1 = *vit1; string str2 = *vit2; if (str1>str2) vec.push_back(str2); vec.push_back(str1); else vec.push_back(str1)

29、; vec.push_back(str2); map< int , vector<string> >:iterator base_item = item.begin(); unsigned int Acount = 0 ; while (base_item != item.end() )/统计该K+1级候选项在原事务集出现次数 unsigned int count = 0 ,mincount = UINT_MAX; vector<string> vv = base_item->second; vector<string>:iterator

30、vecit , bvit ; for (vecit = vec.begin();vecit < vec.end();vecit+) string t = *vecit; count = 0; for (bvit=vv.begin();bvit < vv.end();bvit+) if (t = *bvit) count+; mincount = (count < mincount ? count : mincount ); if (mincount >=1 && mincount != UINT_MAX) Acount += mincount; +bas

31、e_item; if (Acount >= min_value && Acount != 0) sort(vec.begin(),vec.end(); /该第K+1级候选项为频繁项，插入频繁项集 pair< map< vector<string>,unsigned int >:iterator , bool> ret = ck_item.insert(make_pair(vec,Acount); if (! ret.second) ret.first->second += Acount; +mit; +ck_item_it1; i

32、f (ck_item.empty()/该第K+1级频繁项集为空，说明调用结束，把上一级频繁项集返回 return K_item; else return ck_item; void Apriori:showAprioriItem(unsigned int K,map< vector<string>,unsigned int > showmap) map< vector<string>,unsigned int >:iterator showit = showmap.begin(); if (K != UINT_MAX) cout<<e

33、ndl<<"第 "<<K<<" 级频繁项集为："<<endl; else cout<<"最终的频繁项集为："<<endl; cout<<"项 集"<<" t "<<"频率"<<endl; while (showit != showmap.end() ) vector<string> vec = showit->first; vector<string>:iterator vecit = vec.begin(); cout<<" " while (vecit != vec.end() cout<<*vecit<<" " +vecit; cout<<""<<"t" cout<<showit->sec