数据挖掘Apriori算法

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

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

3、候选c Ctdo(7) c.co un t+;(8) end(9) Lk = c Ck | c.count minsupp(10) end(11) key = U Lk；Apriori-ge n 函数：1Apriori 候选产生函数Apriori-gen 的参数Lk-1，即所有大型(k-1)项目集的集合。匕返回所有大型k项目集的集合的一个超集(Superset)。首先，在Jion(连接)步骤， 我们把Lk-1和Lk-1相连接以获得候选的最终集合的一个超集Ck：(1) in sertintoCk(2) selectp1，p2，pk-1，qk-1(3) fromLk-1p，Lk-1q wherep

4、1= q1，pk-2= qk-2，pk-1 qk-接着，在Prune(修剪)步骤，我们将删除所有的项目集c Ck,如果c的一些k-1子学生所在学院：理学院专业：统计学班级:集不在Lk-1中，为了说明这个产生过程为什么能保持完全性，要注意对于Lk中的任何有最小支持度的项目集，任何大小为k-1的子集也必须有最小支持度。因此，如果我们用所有可能的项目扩充Lk-1中的每个项目集，然后删除所有 k-1子集不在Lk-1 中的项目集，那么我们就能得到 Lk中项目集的一个超集。上面的合并运算相当于用数据库中所有项目来扩展Lk-1 ;如果删除扩展项目集的第k-1个项目后得到的k-1项目集不在Lk-1中，则删除该

5、扩展项目集。条件Pk-1Lh类似原因在删除运算中，删除Ck中其k-1子项目集不在Lk-1中的项目集，同样没有删除 包含在Lk中的项目集。(1) for所有项目集c Ck do for 所有c的(k-1) 子集 s do(3) if (s g 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， 因为项集14 5不在L3中。Subset 函数：候选项目集Ck存储在一棵Hash树中。Hash树的一个节点包含了项集的一个链表(一个 叶节点)或包含了

6、一个Hash表(一个节点)。在节点中，Hash表的每个Bucket都指向另 一个节点。Hash树的根的深度定义为1。在深度d的一个节点指向深度d+1的节点。 项目集存储在叶子中。要加载一个项目集c时，从根开始向下直到一个叶子。在深度为d的一个节点上，要决定选取哪个分枝，可以对此项目集的第d个项目使用一个Hash 函数，然后跟随相应Bucket中的指针。所有的节点最初都创建成叶节点。当一个叶节 点中项集数量超过某个指定的阈值时，此叶节点就转为一个节点。从根节点开始，Subset函数寻找所有包含在某个事务t中的候选，方法如下：若处于 一个叶子，就寻找此叶子中的哪些项目集是包括在t中的，并对它们附加

7、引用指向答案集合。若处于一个节点，而且是通过Hash项目i从而到达此节点的，那么就对t中i之后的每个项目进行Hash,并对相应Bucket中的节点递归地应用这个过程。对于根 节点，就对t中的每个项目进行Hash。尽管Apriori算法已经可以压缩候选数据项集 Ck,但是对于频繁项集尤其是2维的候 选数据项集产生仍然需要大量的存储空间。也就是说对于2维的候选数据项集，Apriori 算法的剪枝操作几乎不起任何作用。例如：1维高频数据项集L1的规模是0(n)，则2 维候选数据项集的规模将达到 0(n2)。如果我们考虑一般情况，即在没有支持度的情况 下1维高频数据项集L1的规模是103，则2维候选数

8、据项集的规模C2将达到 C100O5X105.这种空间复杂度以指数形式的增长，使得这个经典的算法的执行效率 很难让人满意.Apriori算法的两大缺点就是产生大量的候选集，以及需重复扫描数据库。实验硬件及软件平台：Windows7 Visual C+ 6.0实验容(包括实验具体容、算法分析、源代码等等)：#in clude#in clude#in clude #in clude #i nclude using n amespace std;class Aprioripublic:Apriori(size_t is =0,unsigned int mv=0)item_size = is; min

9、_value = mv;Apriori() ;void getltem();map vector,un sig ned int fin d_freitem(); 求事务的频繁项连接连个k-1级频繁项，得到第k级频繁项map vector,unsigned int apri_gen(unsigned int K , map vector,unsigned int K_item);/展示频繁项集void showAprioriltem (un sig ned int K,map vector,un sig ned int showmap);private:map int , vector item

10、;/存储所有最开始的事务及其项map vector,unsigned int K_item; 存储频繁项集size_t item_size; 事务数目unsigned int min_value; 最小阈值;void Apriori:getltem()用户输入最初的事务集int ci = item_size;for (in t i=0;ici;i+)string str;vector temp;cout请输入第i+1 str & str !=wa ng)temp.push_back(str);sort(temp.begi n(),temp.e nd();pair mapint ,vector

11、:iterator , bool ret = item.insert(make_pair(i+1 ,temp); if (!ret.sec ond)-i;cout你输入的元素已存在！请重新输入！e ndl;cout运行结果如下： endl;map vector,unsigned int Apriori:find_freitem()un sig ned int i = 1;bool isEmpty = false;map int , vector :iterator mit ;for (mit=item.begin();mit != item.end();mit+)vector vec = mi

12、t-sec ond;if (vec.size() != 0)break;if (mit = item.end() 事务集为空isEmpty = true;cout事务集为空！程序无法进行.endl;map vector,un sig ned int empty;return empty;while(1)map vector,un sig ned int K_itemTemp = K_item;K_item = apri_ge n( i+,K_item);if (K_itemTemp = K_item)i = UINT MAX;break;/判断是否需要进行下一次的寻找map vector,un

13、 sig ned int pre_K_item = K_item;size_t Kitemsize = K_item.size();/存储应该删除的第K级频繁项集，不能和其他K级频繁项集构成第K+1级项集的集合if (Kitemsize != 1 & i != 1)vector map vector,un sig ned int :iterator eraseVecMit;map vector,unsigned int :iterator pre_K_itemt1= pre_K_item.begin(),pre_K_itemt2;while (pre_K_itemt1 != pre_K_ite

14、m.e nd()map vector,unsigned int :iterator mit = pre_K_item_it1;bool isExist = true;vector vec1;vec1 = pre_K_itemt1-first;vector vec11(vec1.beg in( ),vec1.e nd()-1);while (mit != pre_K_item.e nd()vector vec2;vec2 = mit-first;vector vec22(vec2.begi n(), vec2.e nd()-1);if (vec11 = vec22)break;+mit;if (

15、mit = pre_K_item.e nd()isExist = false;if (!isExist & pre_K_itemt1 != pre_K_item.e nd() eraseVecMit.push_back(pre_K_item_it1); 该第 K 级频繁项应该删除+pre_K_item_it1;size_t eraseSetSize = eraseVecMit.size();if (eraseSetSize = Kitemsize)break;elsevector map vector,un sig ned int :iterator :iterator curre ntErs

16、 = eraseVecMit.begi n();while (currentErs != eraseVecMit.end() 删除所有应该删除的第K级频繁项map vector,un sig ned int :iterator eraseMit = *curre ntErs;K_item.erase(eraseMit);+curre ntErs;elseif(Kitemsize = 1 )break;coute ndl;showAprioriltem(i,K_item);return K_item;map vector,unsigned int Apriori:apri_gen(unsigne

17、d int K , int K_item)if (1 = K)/求候选集 C1size_t c1 = item_size;map int , vector :iterator mapit = item.begin(); vector vec;map c1_itemtemp;while (mapit != item.end() )/将原事务中所有的单项统计出来 vector temp = mapit-sec ond;vector:iterator vecit = temp.begi n();while (vecit != temp.e nd()pairmap:iteratorc1_i temte

18、mp.i nsert(make_pair(*vecit+ , 1);if (!ret.sec ond)+ ret.first-sec ond;+mapit;map:iterator item_it = c1_itemtemp.begi n(); map vector,un sig ned int c1_item;map vector,un sig nedbool retwhile (itemt != c1temtemp.end() )/ 构造第一级频繁项集 vector temp;if ( item_it-sec ond = min_value)temp.push_back(item_it-f

19、irst);c1_item.insert(make_pair(temp , item_it-second);+itemt;return c1_i tem;elsecoute ndl;showAprioriltem(K-1,K_item);map vector,un sig ned int :iterator ck_itemt1 = K_item.begi n( ),ck_itemt2;map vector,un sig ned int ck_item;while (ck_itemt1 != K_item.e nd()ck_itemt2 = ck_itemt1;+ck_item_it2;map

20、vector,unsigned int :iterator mit = ck_item_it2;/取当前第K级频繁项与其后面的第K级频繁项集联合，但要注意联合条件/联合条件：连个频繁项的前K-1项完全相同，只是第 K项不同，然后两个联合生成第K+1级候选频繁项while(mit != K_item.e nd()vector vec,vec1,vec2;vec1 = ck_item_it1-first;vec2 = mit-first;vector:iterator vit1,vit2;vit1 = vec1.begi n();vit2 = vec2.begi n();while (vit1 v

21、ec1.end() & vit2 str2)vec.push_back(str2);vec.push_back(str1);elsevec.push_back(str1);vec.push_back(str2);map int , vector :iterator base_item = item.begin();un sig ned int Aco unt = 0 ;while (base_item != item.end() )/统计该 K+1级候选项在原事务集出现次数 un sig ned int count = 0 ,mincount = UINT_MAX;vector vv = ba

22、se_item-sec ond;vector:iterator vecit , bvit ;for (vecit = vec.begi n() ;vecit vec.e nd();vecit+)stri ng t = *vecit;count = 0;for (bvit=vv.begi n( );bvit vv.e nd();bvit+)if (t = *bvit)coun t+;mincount = (co unt =1 & mincount != UINT MAX)Aco unt += mincount;+base_item;if (Aco unt = min _value & Aco u

23、nt != 0)sort(vec.begi n( ),vec.e nd();/该第K+1级候选项为频繁项，插入频繁项集ret =pair map vector,un sig ned int :iterator , bool ck_item.i nsert(make_pair(vec,Aco un t);if (! ret.sec ond) ret.first-sec ond += Aco unt;+mit; +ck_item_it1;if (ck_item.empty()/该第K+1级频繁项集为空，说明调用结束，把上一级频繁项集返回 return K_item;elsereturn ck_it

24、em;void Apriori:showAprioriltem (un sig ned int K,map vector,un sig ned int showmap)map vector,un sig ned int :iterator showit = showmap.begi n();if (K != UINT_MAX)coutendl第K级频繁项集为：endl;elsecout最终的频繁项集为：endl;cout项 集t 频率endl;while (showit != showmap.e nd()vector vec = showit-first;vector:iterator vec

25、it = vec.begi n();cout;while (vecit != vec.e nd()cout*vecit ;+vecit;coutt;coutsec on de ndl;+showit;unsigned int parseNumber(const char * str)/对用户输入的数字进行判断和转换 if (str = NULL)return 0;elseun sig ned int num = 0;size_t len = strle n( str);for (size_t i=0;i= O & stri = 9)num += stri - O;elsereturn 0;return num;void mai n()/Apriori a;un sig ned in t itemsize = 0;un sig ned int min;docout str;itemsize = parseNumber(str);if (itemsize