《2023年Apriori算法实验报告.docx》由会员分享，可在线阅读，更多相关《2023年Apriori算法实验报告.docx（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、题 目Apr ior i算法实现学生姓名学生学号专业班级指导教师2023-12-27或实验一 Aprio ri算法实现一、实验目的1 .加强对Apriori算法的理解；2 .锻炼分析问题、解决问题并动手实践的能力。if(!fr e qu e n tv e c.empt y ()判断频繁1项集是否为空，为空则退出3do。g enC a n ItemsetK();。oge n F r el t em s etK();6whi 1 e (!f r e q u e n tve c .cmpt y ()； 频繁项集不为空,则循环继续outFi 1 e.clos e ()；c o ut ”n结果已保存到“
2、 f Name ”文献!n”；osyst e m(p a use);r e t ur n 0;)/获取原始数据集，并记录事务个数void getO r i Data ()(“ n t flag;c o ut ”数据集文献:n 1 .da t aA.t x t n2.data B .tx t n 请输入A选择dataA,其他选择2) n；oc i n fla g ；st r i n g fi 1 ename;if(fla g = 1 )/打开数据文献f i 1 ename = n d a t a A . txt;else。filenam e = data B .tx tifstream file
3、 (file n a me);oif(!file)/ /检查文献是否打开成功(ocou t Fai 1 to open data file!e n d 1 ;system (pause)；。e x i t(0);)oels estring temp;。vector i t em;/项集的临时 vectorou lV”原始数据集:“endl;i n t b egin, e nd;wh i 1 e(getl i ne(fi 1 e,temp) 一行一行读入数据8 trancount+ + ;0be g in= 0 ;。t e mp.e r as e (0, t em p .f i nd_ f ir
4、st_not_of(rtn )；/ /去除字符串首部的空格tem p .eras e (temp.find_ 1 a s t_ n o t_o f (r t n)+l);/去除字符串尾部的空格w hile (e n d=t e mp.f i n d b e g i n)!= s tri ng： :npo s ) 每一个事务中的项是以空格为分隔符的/item.push_back(temp.substr( b e g in,end-be g i n);将每一个项插入it e m中obegin=end+l ；000 。 item. push_ba c k(t e mp.subst r (be g i
5、n)；/一个事务中的最后一项Kia t avcc.pus h _back( i tcm)；将一个事务中的所有项当成一个整体插入另一个大的vector中item, c lear ();/ /清空 itemo ut t emp e n d 1;。f ile. cl o s e ();)产生并输出候选1项集void genC a n It e ms e t 1()(ma p item_map；for(int i x=0;i x !=datavec.siz e ();+ i x )。for ( i nt iy= 0 ； i y !=d a t a ve c i x .si z e ();+ i y)
6、items_coun t datavecix.at (iy) +;/该项集的计数加 1i tem_map d a tave c i x. at(iy) =true;表达该项目在该事务中存在，值为1,否则默认为0。“bi t map. pus h_ b a ck (it e m_ma p );oi t e m_ma p .clear() ;/ /这里一定要清空一下map:const_ i ter a tor map_it=items_ c ount.b e g in()；o u tF i Ie ”候选 1 项集:” f i rst,en d 1； ma p _i t +;)产生并输出频繁1项集v
7、oid genF r ell e m set 1()(map： ： con s t _itera t or ma p _it=item s _coun t . b e gin()；ou t Fil e *频繁 1 项集： e nd 1 ;ovecto r i tem； 项集的临时 v e ctorw h i 1 e(map_it! =item s _c o u n t . end()频繁 1 项集。i f (f 1 oat)map_ i t- s econd/( f 1 o at)tranc o unt) m in s u p|fabs (float)miip_ i t-second/(f l
8、oat)t r a n c ount) -mi n sup) fi r st n 支持度：” setprecis i o n(2)second/(float)tranc o untfi r st);frequentvec. p u s h _ b a ck (item);插入频繁 1 项集的vector 中。oitcm.c 1 e ar ()；。 map_it+;)产生并输出候选k-项集(k=2)vo i d genCan I temsetK()(生成下一轮的候选项集vect o r item; 项集的临时 vector i nt s t=freque n tve c .size()；a nd
9、id a tevec.cl e a r();清除上一轮的候选项集fo r (int s t l=O;st 1 s t ;stl+)。for(int s t 2 =st 1 +1 ； st2st; s t2+)item=mer g e Item(f r equ e ntve c s 11 , fre q u entve c st2,rou n d);/调用函数合并生成下一轮的候选项集i f(! item.empty()&!i s E xist( i tem, c a n dida t evec) / / 若通过判断解决后返回的vector不为空且还不存在该项集，则作为候选项 集加入候选vect
10、o r中00c u (Not C anlt e msetK(i t e m)；OdO )r ound+ + ；outFilevV”候选ro u n dv项集:”endl；f or( i n t ix=();i x ! =can did a te v e c .s i z e()； + i x) / / 输出候选项集(。ou t File；。for( i n t i y =0; i y!=c a n d idatevec i x. s ize ()； +iy)。 outF i le c andid a tcve c ix. at (i y );8 u t Fi 1 e, 1 e n d 1 ；)
11、i f (candidatev e c .empty() )/ / 候选项集为空。oou t F ile 候选 r o und=2)voi d g e nFreltems e tK()int f 1 ag;标记某个项集在某条事务中是否出现，出现为1,不出现为0,如：Il I 2)oint c ount;/记录某个想集在整个交易的事务集中出现的次数str i ng tempst r ;/ /临时string,用于串接各个项成一个字符串:如：II 12 13 串接为“11 1213”A n t mark;/ /为避免执行多余的字符串串接工作ofre q uentvec. c 1 e a r()；清
12、除上一轮的频繁项集f or(i n t sx= 0 ;s x !=candi d at e vec. s i z e () ; + + s x) / / 构造 下一轮的频繁项集。(ma r k= 1 ;count=0：for (int s y= 0 ;s y ! = b i tm叩.si z e ();+sy) f lag=l;初始化为1,表出现。 for ( i n t s z =0;sz!= can didateve c sxj. size()； +sz)0 )。 i f(bitm a psyc a n d id a t e v ecsx.at(sz)=fal s e )/存在某一个子项不
13、存在，则没出现项集0001。 gfla g =0;000 )。i f (m a r k =1)/ /只串接一次，如II I 2 否则为10个I112的串接000tem p s t r+二 can dida t evec Esx .at( s z); 串接字符串0)。oif(flag) /flag仍然为1,表达该项集在该条事务中出现了,计数加1。count+;e&o m a rk+ + ;00 f ( (fl o at)count/(fl oat )tra n count)minsup|fabs( (f 1 o a t) c oun t /(fl o a t) t rancoun t ) min
14、 s u p) 1 .Oe 7 ) / /支持度大于().2 6 (。 fre q ue n tve c .p u s h_b a c k( c a n did a t e v ec(sx ); 插入频繁项集item s _counttem p s t r =coun t ;相应当项集的计数值/ /假设此时生成的t empstr % 1112 I 3 ,为便于后面的求 置信度的计算，这里需要产生1211 I 3, 1113 12等组合，并。在i tems_count中给它们赋予和H I 213相同的值。so r t(cand i d at e v e csx .begin () , c and
15、 i d a t evecsx. endO )； 排序8st r ing temp s tr2；0 wh i 1 e(next_pcrmut a t ion(c a ndidatevecs x . beg i n(),cand i da teve c sx.end() 取下一排列组合 g。of o r(int tempst= 0 ； tempst!=c a nd i dat e v e csx.s i z e()； tem p st+) 拼接出该字符串组合001。e mpst r 2 += c andidatevec s x tempst;00|oitems_count t em p st r
16、 2=count;/ /相应当项集的计数值tempst r 2.era s e()；。)tem p s t r .era s e ();。i f(! f reque n tvec.em p ty ()/ /频繁项集不为空(outF i le”频繁 n r o und “ 项集:n dl;dfor(int sx=O； s x ! =fr e q uentvec. s ize()； + s x) /输出频繁项 集。 outFile. set f(ios:： fixed);。o u tFil e ；3f o r(int sz=O;sz!= f re q uen t vecsx. s i ze();+
17、sz)6 t empst r += f re q u e nt v e c sx.at ( s z );/ /串接字符串gout Filef r e q u entvecsx . a t (sz)；00 00 。ooutFiIen；。u tFil e 支持度： s e t p recisio n (2) ( floa t ) i tems_coun t t e mpstr/( f loat) t ra n count end 1 ;。 t em p st r . e rase(); )o e 1 s e。(。u t F i le“没有vv r o u n d”-频繁项集,Apri o ri 算
18、法结 束!”vvendl；。 )两个项集合并(规定只有一项不同)成一个新的项集(做为候选集)v ec t or mer g el t em( v e c t or v ec t 1 ,vec to r vcc t 2,int r ound) (i n t c o unt=0;记录两个v e c t o r中相同的项的数目ovectorvect；omap t e mpMap；/辅助判断两个vecto r中反复的项for(un s i g ne d i n t st=O;stvect 1 . si z e (); s t+) (s tempMapve c 11 st+；vect.pu s h _b
19、ack(ve c 11 st);o r ( u n s ig n ed int s t =0;s t vec t 2.si z e() ;st+)二、实验规定使用一种你熟悉的程序设计语言，如C + +或Java,实现Apri or i算法，至 少在两种不同的数据集上比较算法的性能。三、实验环境Win7 旗舰版 + V i s ual St u di o 2023语言：C+四、算法描述1、A p riori算法说明在Ap r iori算法中，寻找频繁项集的基本思想是：A.简朴记录所有含一个元素项目集出现的频率，找出不小于最小支持度的 项目集，即频繁项集；B.从第二步开始，循环解决直到再没有最大项
20、目集生成。循环过程是：第 k步中，根据第k-l步生成的频繁(k-1)项集产生侯选k项集。根据候选 k项集，算出候选k项集支持度，并与最小支持度比较，找到频繁k项集。下文中碰到的以下符号,分别代表相应的内容k-i t em s e t k 项集Lk 频繁k项集Ck 侯选k项集2、Apr iori算法描述数据结构说明“empMap v e ct2s t +;if(tem p Map vect2st =2) / / 表达这两项相同6 (空 o unt+；8 else ( ve c t. push_ b a ck( v ect2 s t)；。if(count+ 1 )!=round)/ /规定两个项目
21、集只有一个项目不相同,其他都相同，如:H I 2 14和II 12 13 。(ve c t.c 1 ear();ore t u rn v ec t ； )/剪枝：剪去合并后项集中具有非频繁项集中的项v o id c utNotCanltemsetK (v e c t or & i t em) (/ / 实现剪枝 / / / / / / s t rin g t empstr;vector tempvec：是否包具有非频繁的子集，为1表达具0bo o I f o u nd = f a Ise;有，有的话进行剪枝，如假设HI4为非频繁项集，则II 1214要剪枝掉os t rin g t estst
22、r;int tes t i n t；s t empvec=item;s o rt( t empv e c. b e g i n (),tem p v e c . end ();w h i 1 e (ne x t_pe r mut a t i o n (tempvec.begin(),tempvec. end () 遍历所有的组合II I 214,要变成111 4 I 2或其他如114才干判断它包含I 114这个非频繁项集(for(int tempst=0; t em p s t ! = t e m p ve c .size();tem p st+) 拼接出 该字符串组合g (。4empstr+
23、=t e mp v ec t emp s t;0)0 f or ( ma p ： : c o n st_iter a t or t empit=i t e ms_c o u n t. b eg i n () ; t emp it! = itcms_co u nt. e nd ();t e mpit+)。f (f 1 o a t)(t e mpit- s e con d )/( f loat)t r anco u n t )first)!=st r ing:： n po s )表达包具有非频繁子项集 ofo u nd= t r ue;。 teststr=tem p it-first；testin
24、t=t e mpit-sec o n d ;。g brea k ;。00 I8 4emps t r .era s e()；-i f ( f ou n d)/包含非频繁子项集( br e a k;。oif(! foun d )只有不包具有非频繁子项集才加入候选项集中，否则剪枝掉。 c andi d a t e v ec. p ush_ b ack (item)； else(。ou t FileVV”剪去项集:；fo r (i n t s t 2 =0;st2!=i t em. s i z e();st2+)outFi 1 e item st2；。outF i 1 e 具有非频繁子项集：”.tes
25、 t s tr t e sti n t /Htr a neo u nt,=,(float)(t e s t int)/ (floa t )tranc o un t )；o utFil e e ndl;)判断项集it em是否已经存在候选项集集合items中，存在则返回1i n t isExi s t (vecto r i t em, v e ct o rve c tori t em s _ c o unt; / /记录各个项集的数目vecto r ve c tor data vec;原始数据项集vecl o rvectorstr i n g c a nd i d a levee；候选项集vec
26、tor v e c t o r fre q uentvec; 频繁项集 ofst ream ou t File;i n t roun d = 1 ；/生成项集轮次long trancount=0; / /原始事务总数/判断某个项目在某一个事务中是否存在，存在则值为1,反之为0v e c t ormap bitmap;A p rior i算法的第一步是简朴记录所有含一个元素的项集出现的频率，来决 定频繁1项集。在第k步，分两个阶段:1,用函数g e n Can Hems etK,通过第(k-1) 步中生成的频繁(k 1)项集来生成侯选k项集;2.计算侯选k项集的支持度， 并找出频繁k项集。Apr
27、i o ri算法描述如下getOriData();o/ /获取原始数据集，并记录事务个数genC a n Itemset 1 (); / /产生输出候选1项集g en F r e It e mse t 1 () ;/ /产生频繁项集if (! f r e quen t ve c . em P ty() )/根据频繁1项集，执行程序。8do00 genCan I temsetK()； / /生成并输出候选k项集。 g enFreltem s etK ()； /计算并输出频繁k项集。 while。freq u en t v ec.em p t y ();频繁项集不为空，则循环继续其中，产生候选k项
28、集函数ge n Can Ite ms etK中涉及两个重要函数，项 集合并函数merg e It e m和剪枝函数c utNo t Can Item s etKo3、函数方法说明/获取原始数据集，并记录事务个数vo i d get 0 riData();合并生成新的候选项集vec t or m e r g e Item(v e ctor vect 1 v e cto r vec t 2, i n t r ou n d);/判断项集it e m是否已经存在候选项集集合i tems中，存在则返回1int isExi s t (ve c t o r i t em,ve c tor v e cto r
29、 it e m s );产生并输出候选1项集void ge n Canitemset 1();/产生并输出频繁1项集void ge n Fr e Itemse t 1 ();/ /产生并输出候选k-项集(k=2)v o id ge n Canlt e m s e t K ();产生并输出频繁k-项集(k=2)v oi d g e n Fr e ItemsetK()；/剪枝：剪去合并后项集中具有非频繁项集中的项vo i d cut No t Canlt e ms e tK(ve ctor & i tem)；五、实验截图1 .程序运营界面2 .输出文献截图1rA.txt -记事本文件(F)福*9)
30、查看(V)做而寺度为 minsup = 0.4(D)穗：0. 40 (C) D E 魁程蠹：0.60 支持度：0.80 (C)支持度:0.50ACAD(BC)(BD)CD频繁2吆集：AB)支持度:0.50没着3-频繁项集,Apriori算法结束!3 .输出文献截图1文件(F) s(E)格式(O)查看(V)再助(H):AD 1/10=0.10:EC 1/10=0.10:AD 1/10=0.10:EC 1/10=0.10:ED 0/10=0. 00:AD 1/10=0.10:EC 1/10=0.10:AD 1/10=0.10:EC 1/10=0.10:ED 0/10=0. 00甑频频麻，频 一二
31、I二二二二 |二TmT 二.二.二-1 有有有有有 含含含含含M:度度度度度I:II支支支支支21:度度度度度度度ABACACBC即. 要支支支支支询酸囚图招群图招髓留疆耦CDCES(ABACAE)幽圈一it襄六、实验总结做完这个实验，有如下收获：1 .同一数据集，最小支持度越小，那么产生的频繁项集维数越高，程序运营 时间越长；.更加深刻理解了：频繁子集的任何子集一定是频繁的，子集频繁父亲一 定频繁；2 . Apriori也存在缺陷：第一在每一步产生侯选项目集时循环产生的组合 过多，没有排除不应当参与组合的元素;第二,每次计算项集的支持度时, 开销会随着数据的增多而成儿何级增长。七、附程序源码
32、 m a in.cpp# i n cl u d e # include #include # in c lud e # i n clu d e # i n c 1 u de # in c 1 u d e u si n g namesp ace std;double minsu p ;/ /设立最小支持度ma p items_ c o un t ;/ / 记录各个项集的数目vect o rvect o rs t r in g data v e c;/ /原始数据项集vectorvectorstring cand i d ate v e c ;候选项集v e c tor vector frequ
33、e ntvec;频繁项集ofslream o utF i le；in t r o u nd= 1 ;生成项集轮次long Iran c ount= 0 ;原始事务总数判断某个项目在某一个事务中是否存在，存在则值为1 ,反之为0vecto r m a p bitmap;获取原始数据集，并记录事务个数void g e t O r iData();合并生成新的候选项集v e c t o r mer g e Item(v e c t o r vec t 1 , v e ct or v e ct2, i nt r ound)；判断项集item是否己经存在候选项集集合items中，存在则返回1int is
34、E x is t (v e c to r i t e m vector v ec t o r it e ms);产生并输出候选1项集v oid g e nCanlt e mset 1 ();产生并输出频繁1项集void g e n F rd t cmse t 1();/产生并输出候选k项集(k=2)voi d ge n Ca n Item s e tK ();/产生并输出频繁k-项集(k =2)void ge n Fr e Item s etK ();剪枝:剪去合并后项集中具有非频繁项集中的项void c u t NotC a nltems e tK(vector & it e m);int main()(唱e tOr i Data ( ) ;。/ /获取原始数据集，并记录事务个数c o u t vv ”请输入结果文献名：；/pa u sestr i ng f Nam e ;c i n fN a m e ；c o u t ”请输入最小支持度c in minsup;out F i 1 e.op e n ( f Name, i o s :： t ru n c );ou t File vv ”最小支持度为 m i nsu p = m i nsup en d I； g enCan I t e inset 1 ();g e n F r eltemsetl();