2022年数据挖掘实验三应用Apriori算法挖掘频繁项集宣贯 .pdf

实验三、应用 Apriori 算法挖掘频繁项集学院 计算机科学与软件学院?实验目的：（1）熟悉 VC+ 编程工具和 Apriori 频繁项集挖掘算法。（2）根据管理层的需求，确定数据挖掘的任务，明确数据挖掘的功能，也就是明确要挖掘什么。（3）由确定的数据挖掘任务，从实验一处理后的结果中，采用切块或切片等联机分析处理技术，选择出挖掘任务相关数据。（4）用 VC+ 编程工具编写 Apriori 算法的程序，对任务相关数据运行 Apriori 算法，挖掘出所有的频繁项集。1.写出实验报告。?实验原理：1 、Apriori 算法 Apriori 使用一种称作逐层搜索的迭代方法，k 项集用于探索（ k+1）项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁 1 项集的集合。该集合记作 L 1 。然后， L 1 用于找频繁 2 项集的集合L 2 ，L 2 用于找 L 3 ，如此下去，直到不能再找到频繁 k 项集。找每个 L k 需要一次数据库全扫描。2、提高频繁项集逐层产生的效率 Apriori 性质：频繁项集的所有非空子集也必须是频繁的。三、 实验内容：1、实验内容在给定的数据中提取统一购物篮购买的商品信息，由这些数据构成事务数据库 D，挖掘其中的频繁项集 L。挖掘频繁项集的算法描述如下：Apriori 算法：使用逐层迭代找出频繁项集输入：事务数据库 D；最小支持度阈值。输出： D 中的频繁项集 L。（1） L 1 = find_frequent_1-itemsets(D); / 挖掘频繁 1-项集，比较容易（2） for (k=2;L k-1 ;k+) （3） C k = apriori_gen(L k-1 ,min_sup); / 调用 apriori_gen 方法生成候选频繁k-项集分为两步：合并、减枝（4） for each transaction t D / 扫描事务数据库 D （5） Ct = subset(C k ,t); （6） for each candidate c Ct （7） c.count+; / 统计候选频繁 k-项集的计数（8） （9） L k =c Ck|c.countmin_sup / 满足最小支持度的 k-项集即为频繁 k-项集名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - （10） （11） return L= k L k ; / 合并频繁 k-项集（ k0）算法在根据频繁 k-1 项集生成频繁 K 项集过程中要计算频繁 K 项集中每个元素的支持度，并计算 K 项集中每个 k-1 项子集是否在 F k-1 中，上述两条任何一条不满足，则删去这个 K 项集中的元素。2 、实验过程 1、打开试验用数据，读取出同一流水号的商品 ID 并取前 5 位，生成以行为单位生成事务数据集 transitions; 2、ind_frequent_1-itemsets 生成频繁一项集for（each transaction in transitions） for(each item in transaction） oneItemSet；oneItemSet.count+；/ 对 1 项集进行计数 3、apriori-gen (L k-1 ) 候选集产生算法For all itemset p Lk-1 do For all itemset q Lk-1 do If p.item1=q.item1, p.item2=q.item2, ,p.itemk-2=q.itemk-2, p.item k-1 !=q.item k-1 then begin c=pq/p 、q 合并后任意的 L k-1 子集if has_infrequent_subset(c, L k-1 ) then delete c / 存在 c 不属于 L k-1 剪枝else add c to Ck End Return Ck 4、has_infrequent_subset(c, L k-1 ）判断候选集的元素For all (k-1)-subsets of c do If Not(S Lk-1) THEN return TRUE; Return FALSE; 1.流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 4、主要程序代码1、/ 产生事务数据库代码（加注释）#include #include #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - #include using namespace std; class Sales_n public: string serial; int market; char date10; int sn; int id; float num; float price; ; int main() /打开并创建txt 文件/ char name150,name250; ifstream infile; cout选择要打开的文件：1019n.txt 1020n.txt 1021n.txtname1; infile.open(name1,ios:in); /*string contents;*/ if(infile.fail() cout error open! endl; cout要保存的文件名：name2; ofstream outfile(name2,ios:out); if(!outfile) coutopen eror! salsal_size.serial salsal_size.market salsal_size.date salsal_size.sn salsal_size.id salsal_size.num salsal_size.price; sal_size+; /取统一流水的商品ID 前三位按升序无重复的保存起来/ new100=sal0.id/10000; for (int i =1;isal_size;i+) if (sali.serial=sali-1.serial) new1mn=sali.id/10000; /流水号相同n+; /outfilesali.id/100t; else /排序/ for(int k = 0;kn;k+) for(int j = 0;j new1mj+1) int t = new1mj; new1mj = new1mj+1; new1mj+1 = t; for(int l= 0;l n;l+) if(new1ml-1!=new1ml) outfilenew1mlt; outfileendl; m+; n = 0; new1mn=sali.id/10000; n+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - infile.close();/ 关闭文件 outfile.close();/ 关闭文件system( PAUSE ); 2、/Apriori 算法挖掘频繁项集support = 2（加注释）#include #include #include #include #include #include #include #include #include using namespace std; const int minsup=2; / 设置最小支持度map items_count; / 统计各个项集的数目vector mergeItem(vector vect1,vector vect2,int round); /合并生成新的候选项集int isExist(vector item,vectorvector items); / 判断项集 item 是否已经存在候选项集集合items 中,存在则返回vector mergeItem(vector vect1,vector vect2,int round) /判断两个项集是否可以合并(要求只有一项不同)成一个新的项集（做为候选集） /剪枝工作 / int count=0; / 统计两个 vector 中相同的项的数目 vector vect; map tempMap; / 辅助判断两个vector 中重复的项 for(vector:size_type st=0;stvect1.size();st+) tempMapvect1st+; vect.push_back(vect1st); for(int st=0;stvect2.size();st+) tempMapvect2st+; if(tempMapvect2st=2) / 表示这两项相同 count+; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - vect.push_back(vect2st); if(count+1)!=round) / 要求两个项目集只有一个项目不相同，其他都相同 vect.clear(); return vect; int isExist(vector item,vectorvector items) / 判断项集 item 是否已经存在候选项集集合items 中,存在则返回 int count; / 统计相同的项的数目 if(!items.empty() for(vectorvector :size_type ix=0;ix!=items.size();ix+) count=0; for(vector:size_type iy=0;iy!=itemsix.size();iy+) for(vector:size_type iz=0;iz!=item.size();iz+) if(itemiz=itemsix.at(iy) count+; if(count=item.size() /表示存在 return 1; return 0; int main() vectorvector datavec; /原始数据项集 vectorvector candidatevec; / 候选项集 vectorvector frequentvec; / 频繁项集 vectormap bitmap; / 判断某个项目在某一个事务中是否存在，存在则值为 1，反之为 0 long trancount=0; / 原始事务总数 char name150; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - ifstream file; cout选择要打开的文件：new1.txt new2.txt new3.txtname1; file.open(name1,ios:in); / 打开数据文件 if(!file) / 检查文件是否打开成功 coutFail to open data file!endl; return 1; else string temp; vector item; / 项集的临时vector int begin,end; while(getline(file,temp) / 一行一行读入数据 trancount+; begin=0; temp.erase(0,temp.find_first_not_of(rtn ); /去除字符串首部的空格 temp.erase(temp.find_last_not_of(rtn)+1); while(end=temp.find(t,begin)!=string:npos) /每一个事务中的项是以t 为分隔符的 item.push_back(temp.substr(begin,end-begin); / 将每一个项插入item 中 begin=end+1; item.push_back(temp.substr(begin); / 一个事务中的最后一项 datavec.push_back(item); /将一个事务中的所有项当成一个整体插入另一个大的 vector 中 item.clear(); /清空 item coutPress Enter to continue the processing; /pause getchar(); map item_map; for(vectorvector :size_type ix=0;ix!=datavec.size();+ix) for(vector:size_type iy=0;iy!=datavecix.size();+iy) items_countdatavecix.at(iy)+; / 该项集的计数加 item_mapdatavecix.at(iy)=1; / 表示该项目在该事务中存在，值为1，否则默认为 0 bitmap.push_back(item_map); item_map.clear(); /这里一定要清空一下名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - map:const_iterator map_it=items_count.begin(); cout候选项集 1:endl; while(map_it!=items_count.end() / 输出候选 1 项集 coutfirstendl; map_it+; coutPress Enter to continue the processing; /pause getchar(); map_it=items_count.begin(); cout频繁 1 项集(minsup=2):secondminsup) / 支持度大于 2 cout.setf(ios:fixed); coutfirst 支持度 :setprecision(6)secondfirst); frequentvec.push_back(item); / 插入候选项集的vector 中 item.clear(); map_it+; if(!frequentvec.empty() / 判断频繁项集是否为空，为空则退出 coutPress Enter to continue the processing; /pause getchar(); int round=1; /生成候选项集轮次 int found; /是否包含有非频繁的子集,为表示含有，有的话进行剪枝 string tempstr; vector tempvec; do /生成下一轮的候选项集 vectorvector :size_type st=frequentvec.size(); candidatevec.clear(); / 清除上一轮的候选项集 for(vectorvector :size_type st1=0;st1st;st1+) for(vectorvector :size_type st2=st1+1;st2st;st2+) found=0; item=mergeItem(frequentvecst1,frequentvecst2,round); / 调用函数合名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - 并生成下一轮的候选项集 if(!item.empty()&!isExist(item,candidatevec) / 若经过判断处理后返回的 vector 不为空且还不存在该项集，则作为候选项集加入候选vector 中 / 实现剪枝 / string teststr; int testint; tempvec=item; sort(tempvec.begin(),tempvec.end(); while(next_permutation(tempvec.begin(),tempvec.end() / 遍历所有的组合 for(vector:size_type tempst=0;tempst!=tempvec.size();tempst+) / 拼接出该字符串组合 tempstr+=tempvectempst; for(map:const_iterator tempit=items_count.begin();tempit!=items_count.end();tempit+) if(tempit-secondfirst)!=string:npos) /表示包含有非频繁子项集 found=1; teststr=tempit-first; testint=tempit-second; break; tempstr.erase(); if(found) / 包含非频繁子项集 break; if(!found) / 只有不包含有非频繁子项集才加入候选项集中，否则剪枝掉 candidatevec.push_back(item); found=0; / 重置 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - frequentvec.clear(); /清除上一轮的频繁项集 round+; cout 候选round 项集:endl; for(vectorvector :size_type ix=0;ix!=candidatevec.size();+ix) /输出候选项集 cout; for(vector:size_type iy=0;iy!=candidatevecix.size();+iy) coutcandidatevecix.at(iy) ; coutendl; if(candidatevec.empty() / 候选项集为空 cout 候选round 项集为空 !endl; int flag; /标记某个项集在某条事务中是否出现，出现为1，不出现为0 int count; /统计某个想集在整个交易的事务集中出现的次数 string tempstr; /临时 string，用于串接各个项成一个字符串 int mark; /为避免执行多余的字符串串接工作 for(vectorvector :size_type sx=0;sx!=candidatevec.size();+sx) / 构造下一轮的频繁项集 mark=1; count=0; for(vectormap :size_type sy=0;sy!=bitmap.size();+sy) flag=1; / 初始化为 1，表出现 for(vector:size_type sz=0;sz!=candidatevecsx.size();+sz) if(bitmapsycandidatevecsx.at(sz)=0) /存在某一个子项不存在，则没出现项集 flag=0; if(mark=1) / 只串接一次 tempstr+=candidatevecsx.at(sz); / 串接字符串 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - if(flag) /flag仍然为，表示该项集在该条事务中出现了，计数加 count+; mark+; if(countminsup) /支持度大于2 frequentvec.push_back(candidatevecsx); / 插入频繁项集 items_counttempstr=count; / 对应该项集的计数值 sort(candidatevecsx.begin(),candidatevecsx.end(); /排序 string tempstr2; while(next_permutation(candidatevecsx.begin(),candidatevecsx.end() /取下一排列组合 for(vector:size_type tempst=0;tempst!=candidatevecsx.size();tempst+) / 拼接出该字符串组合 tempstr2+=candidatevecsxtempst; items_counttempstr2=count; / 对应该项集的计数值 tempstr2.erase(); tempstr.erase(); coutPress Enter to continue the processing; /pause getchar(); if(!frequentvec.empty() / 频繁项集不为空 cout 频繁 round项集(minsup=2):endl; for(int sx=0;sx!=frequentvec.size();+sx) / 输出频繁项集 cout.setf(ios:fixed); cout; for(vector:size_type sz=0;sz!=frequentvecsx.size();+sz) coutfrequentvecsx.at(sz) ; tempstr+=frequentvecsx.at(sz); /串接字符串 cout; coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - tempstr.erase(); coutPress Enter to continue the processing; /pause getchar(); else cout 没有 round-频繁项集 ,Apriori 算法结束 !endl; while(!frequentvec.empty(); / 频繁项集不为空 ,则循环继续 file.close(); return 0; else return 0; /end of if(!frequentvec.empty() /end of if(!file) ?实验结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -