数据挖掘Apriori算法

实 验 报 告实验课程名称： 数据挖掘 实验项目名称： Apriori算法 理 学 院实验时间： 2014 年 11 月 11 日2学生所在学院：理学院 专业： 统计学 班级：姓 名学 号实验组实验时间指导教师成 绩实验项目名称Apriori算法实验目的及要求：1. 加强对Apriori算法的理解2. 锻炼分析问题、解决问题以及动手能力3. 编程实现Apriori算法实验（或算法）原理：Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代：频繁K项Lk集用于搜索频繁(K+1)项集Lk+1，如此下去，直到不能找到维度更高的频繁项集为止。这种方法依赖连接和剪枝这两步来实现。算法的第一次遍历仅仅计算每个项目的具体值的数量，以确定大型l项集。随后的遍历，第k次遍历，包括两个阶段。首先，使用在第(k-1)次遍历中找到的大项集Lk-1和用Aprioir-gen函数产生候选项集Ck。接着扫描数据库，计算Ck中候选的支持度。用Hash树可以有效地确定Ck中包含在一个给定的事务t中的候选。算法如下：(1)L1=大项目集1项目集;(2)for(k=2;Lk-1!=空;k+)dobegin(3) Ck=apriori-gen(Lk-1);/新的候选集(4) for所有事务tDdobegin(5) Ct=subset(Ck，t);/t中所包含的候选(6) for所有候选cCtdo(7) c.count+;(8) end(9) Lk=cCk|c.countminsupp(10)end(11)key=Lk；Apriori-gen函数：1Apriori候选产生函数Apriori-gen的参数Lk-1，即所有大型(k-1)项目集的集合。它返回所有大型k项目集的集合的一个超集(Superset)。首先，在Jion(连接)步骤，我们把Lk-1和Lk-1相连接以获得候选的最终集合的一个超集Ck：(1)insertintoCk(2)selectp1，p2，pk-1，qk-1(3)fromLk-1p，Lk-1q(4)wherep1=q1，pk-2=qk-2，pk-1qk-接着，在Prune(修剪)步骤，我们将删除所有的项目集cCk，如果c的一些k-1子集不在Lk-1中，为了说明这个产生过程为什么能保持完全性，要注意对于Lk中的任何有最小支持度的项目集，任何大小为k-1的子集也必须有最小支持度。因此，如果我们用所有可能的项目扩充Lk-1中的每个项目集，然后删除所有k-1子集不在Lk-1中的项目集，那么我们就能得到Lk中项目集的一个超集。上面的合并运算相当于用数据库中所有项目来扩展Lk-1；如果删除扩展项目集的第k-1个项目后得到的k-1项目集不在Lk-1中，则删除该扩展项目集。条件pk-1Lk。类似原因在删除运算中，删除Ck中其k-1子项目集不在Lk-1中的项目集，同样没有删除包含在Lk中的项目集。(1)for所有项目集cCkdo(2) for所有c的(k-1)子集sdo(3) if(sLk-1)then(4) 从Ck中删除c例如：L3为123，124，134，135，234。Jion步骤之后，C4为1234，1345。Prune步骤将删除项集1345，因为项集145不在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将达到C10005105这种空间复杂度以指数形式的增长，使得这个经典的算法的执行效率很难让人满意Apriori算法的两大缺点就是产生大量的候选集，以及需重复扫描数据库。 实验硬件及软件平台：Windows7、Visual C+ 6.0实验内容（包括实验具体内容、算法分析、源代码等等）：#include #include #include #include #include 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,unsigned int find_freitem();/求事务的频繁项 /连接连个k-1级频繁项，得到第k级频繁项 map vector,unsigned int apri_gen(unsigned int K , map vector,unsigned int K_item); /展示频繁项集 void showAprioriItem(unsigned int K,map vector,unsigned int showmap); private: map int , vector item;/存储所有最开始的事务及其项 map vector,unsigned int K_item;/存储频繁项集 size_t item_size;/事务数目 unsigned int min_value;/最小阈值 ; void Apriori:getItem()/用户输入最初的事务集 int ci = item_size; for (int i=0;ici;i+) string str; vector temp; cout请输入第i+1str & str !=wang) temp.push_back(str); sort(temp.begin(),temp.end(); pair mapint ,vector :iterator , bool ret = item.insert(make_pair(i+1 ,temp); if (!ret.second) -i; cout你输入的元素已存在！请重新输入！endl; cout-运行结果如下：-endl; map vector,unsigned int Apriori:find_freitem() unsigned int i = 1; bool isEmpty = false; map int , vector :iterator mit ; for (mit=item.begin();mit != item.end();mit+) vector vec = mit-second; if (vec.size() != 0) break; if (mit = item.end()/事务集为空 isEmpty = true; cout事务集为空！程序无法进行.endl; map vector,unsigned int empty; return empty; while(1) map vector,unsigned int K_itemTemp = K_item; K_item = apri_gen(i+,K_item); if (K_itemTemp = K_item) i = UINT_MAX; break; /判断是否需要进行下一次的寻找 map vector,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,unsigned int :iterator eraseVecMit; map vector,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,unsigned int :iterator mit = pre_K_item_it1; bool isExist = true; vector vec1; vec1 = pre_K_item_it1-first; vector vec11(vec1.begin(),vec1.end()-1); while (mit != pre_K_item.end() vector vec2; vec2 = mit-first; vector vec22(vec2.begin(),vec2.end()-1); if (vec11 = vec22) break; +mit; if (mit = 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,unsigned int :iterator :iterator currentErs = eraseVecMit.begin(); while (currentErs != eraseVecMit.end()/删除所有应该删除的第K级频繁项 map vector,unsigned int :iterator eraseMit = *currentErs; K_item.erase(eraseMit); +currentErs; else if(Kitemsize = 1 ) break; coutendl; showAprioriItem(i,K_item); return K_item; map vector,unsigned int Apriori:apri_gen(unsigned int K , map vector,unsigned int K_item) if (1 = K)/求候选集C1 size_t c1 = item_size; map int , vector :iterator mapit = item.begin(); vector vec; map c1_itemtemp; while (mapit != item.end() )/将原事务中所有的单项统计出来 vector temp = mapit-second; vector:iterator vecit = temp.begin(); while (vecit != temp.end() ) pair map:iterator , bool ret = c1_itemtemp.insert(make_pair(*vecit+ , 1); if (!ret.second) + ret.first-second; +mapit; map:iterator item_it = c1_itemtemp.begin(); map vector,unsigned int c1_item; while (item_it != c1_itemtemp.end() )/构造第一级频繁项集 vector temp; if ( item_it-second = min_value) temp.push_back(item_it-first); c1_item.insert(make_pair(temp , item_it-second) ); +item_it; return c1_item; else coutendl; showAprioriItem(K-1,K_item); map vector,unsigned int :iterator ck_item_it1 = K_item.begin(),ck_item_it2; map vector,unsigned int ck_item; while (ck_item_it1 != K_item.end() ) ck_item_it2 = ck_item_it1; +ck_item_it2; map vector,unsigned int :iterator mit = ck_item_it2; /取当前第K级频繁项与其后面的第K级频繁项集联合，但要注意联合条件 /联合条件：连个频繁项的前K-1项完全相同，只是第K项不同，然后两个联合生成第K+1级候选频繁项 while(mit != K_item.end() ) vector vec,vec1,vec2; vec1 = ck_item_it1-first; vec2 = mit-first; vector:iterator vit1,vit2; vit1 = vec1.begin(); vit2 = vec2.begin(); while (vit1 vec1.end() & vit2 str2) vec.push_back(str2); vec.push_back(str1); else vec.push_back(str1); vec.push_back(str2); map int , vector :iterator base_item = item.begin(); unsigned int Acount = 0 ; while (base_item != item.end() )/统计该K+1级候选项在原事务集出现次数 unsigned int count = 0 ,mincount = UINT_MAX; vector vv = base_item-second; vector:iterator 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 =1 & mincount != UINT_MAX) Acount += mincount; +base_item; if (Acount = min_value & Acount != 0) sort(vec.begin(),vec.end(); /该第K+1级候选项为频繁项，插入频繁项集 pair map vector,unsigned int :iterator , bool ret = ck_item.insert(make_pair(vec,Acount); if (! ret.second) ret.first-second += Acount; +mit; +ck_item_it1; if (ck_item.empty()/该第K+1级频繁项集为空，说明调用结束，把上一级频繁项集返回 return K_item; else return ck_item; void Apriori:showAprioriItem(unsigned int K,map vector,unsigned int showmap) map vector,unsigned int :iterator showit = showmap.begin(); if (K != UINT_MAX) coutendl第 K 级频繁项集为：endl; else cout最终的频繁项集为：endl; cout项 集 t 频率endl; while (showit != showmap.end() ) vector vec = showit-first; vector:iterator vecit = vec.begin(); cout ; while (vecit != vec.end() cout*vecit ; +vecit; coutt; coutsecondendl; +sh