数据挖掘实验三应用 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.count≥min_sup} // 满足最小支持度的 k-项集即为频 繁 k-项集

（10） }

（11） return L= ∪ k L k ; // 合并频繁 k-项集（k>0）

算法在根据频繁 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=p∞q//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. 流程图

4、主要程序代码

1、//产生事务数据库代码（加注释）

#include #include #include

#include using namespace std; class Sales_n {

public:

string serial; int market; char date[10]; int sn; int id;

float num; float price; };

int main() {

//////////打开并创建txt文件////////////////////////////////// char name1[50],name2[50]; ifstream infile;

cout<<\"选择要打开的文件：1019n.txt 1020n.txt 1021n.txt\"<>name1;

infile.open(name1,ios::in); /*string contents;*/ if(infile.fail()) { cout << \"error open!\" << endl; }

cout<<\"要保存的文件名：\"<>name2;

ofstream outfile(name2,ios::out); if(!outfile) {

cout<<\"open eror!\"<//////////////////////访问预处理文件///////////////////////////////////////////// Sales_n sal[10000]; int sal_size=0; int ser_size=0; int m = 0,n = 1;

int new1[3400][20]={0}; //暂时储存商品ID

while(!infile.eof()) {

infile >> sal[sal_size].serial >> sal[sal_size].market >> sal[sal_size].date>> sal[sal_size].sn>> sal[sal_size].id>> sal[sal_size].num>> sal[sal_size].price;

sal_size++; }

///////////////取统一流水的商品ID前三位按升序无重复的保存起来/////////////////////////

new1[0][0]=sal[0].id/10000; for (int i =1;inew1[m][n]=sal[i].id/10000; //////流水号相同 n++; //outfile<if(new1[m][j] > new1[m][j+1]) {

int t = new1[m][j];

new1[m][j] = new1[m][j+1]; new1[m][j+1] = t; } } } for(int l= 0;l< n;l++) { if(new1[m][l-1]!=new1[m][l]) outfile<} }

infile.close();//关闭文件 outfile.close();//关闭文件 system( \"PAUSE \"); }

2、//Apriori算法挖掘频繁项集support = 2（加注释）

#include #include #include #include #include

const int minsup=2; //设置最小支持度

map items_count; //统计各个项集的数目

vector mergeItem(vector vect1,vector vect2,int round); //合并生成新的候选项集

int isExist(vector item,vector >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;sttempMap[vect1[st]]++; vect.push_back(vect1[st]); }

for(int st=0;sttempMap[vect2[st]]++;

if(tempMap[vect2[st]]==2) //表示这两项相同 {

count++; } else {

vect.push_back(vect2[st]); } }

if((count+1)!=round) //要求两个项目集只有一个项目不相同，其他都相同 { vect.clear(); }

return vect; }

int isExist(vector item,vector >items) //判断项集item是否已经存在候选项集集合items中,存在则返回

{

int count; //统计相同的项的数目 if(!items.empty()) {

for(vector >::size_type ix=0;ix!=items.size();ix++) {

count=0;

for(vector::size_type iy=0;iy!=items[ix].size();iy++) {

for(vector::size_type iz=0;iz!=item.size();iz++) {

if(item[iz]==items[ix].at(iy)) {

count++; } } }

if(count==item.size()) //表示存在 {

return 1; } } }

return 0; }

int main() {

vector > datavec; //原始数据项集 vector > candidatevec; //候选项集 vector > frequentvec; //频繁项集

vector > bitmap; //判断某个项目在某一个事务中是否存在，存在则值为1，反之为0

long trancount=0; //原始事务总数 char name1[50];

ifstream file;

cout<<\"选择要打开的文件：new1.txt new2.txt new3.txt\"<>name1;

file.open(name1,ios::in); //打开数据文件 if(!file) //检查文件是否打开成功 {

cout<<\"Fail to open data file!\"<string temp;

vector item; //项集的临时vector int begin,end;

while(getline(file,temp)) //一行一行读入数据 {

trancount++; begin=0; temp.erase(0,temp.find_first_not_of(\"\\r\\\n \")); //去除字符串首部的空格 temp.erase(temp.find_last_not_of(\"\\r\\\n\")+1);

while((end=temp.find('\',begin))!=string::npos) //每一个事务中的项是以'\'为分隔符的

{

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 }

cout<<\"Press Enter to continue the processing\"; //pause getchar();

map item_map;

for(vector >::size_type ix=0;ix!=datavec.size();++ix) {

for(vector::size_type iy=0;iy!=datavec[ix].size();++iy) {

items_count[datavec[ix].at(iy)]++; //该项集的计数加

item_map[datavec[ix].at(iy)]=1; //表示该项目在该事务中存在，值为1，否则默认为0

}

bitmap.push_back(item_map);

item_map.clear(); //这里一定要清空一下

}

map::const_iterator map_it=items_count.begin(); cout<<\"候选项集1:\"<while(map_it!=items_count.end()) //输出候选1项集 {

cout<<\"{\"<first<<\ map_it++; }

cout<<\"Press Enter to continue the processing\"; //pause getchar();

map_it=items_count.begin();

cout<<\"频繁1项集(minsup=2):\"<while(map_it!=items_count.end()) //频繁1项集 {

if(map_it->second>minsup) //支持度大于2 {

cout.setf(ios::fixed); cout<<\"{\"<first<<\支持度:\"<second<item.push_back(map_it->first);

frequentvec.push_back(item); //插入候选项集的vector中 item.clear(); }

map_it++; }

if(!frequentvec.empty()) //判断频繁项集是否为空，为空则退出 {

cout<<\"Press Enter to continue the processing\"; //pause getchar();

int round=1; //生成候选项集轮次

int found; //是否包含有非频繁的子集,为表示含有，有的话进行剪枝 string tempstr;

vector tempvec; do {

//生成下一轮的候选项集

vector >::size_type st=frequentvec.size(); candidatevec.clear(); //清除上一轮的候选项集

for(vector >::size_type st1=0;st1for(vector >::size_type st2=st1+1;st2found=0;

item=mergeItem(frequentvec[st1],frequentvec[st2],round); //调用函数合

并生成下一轮的候选项集

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+=tempvec[tempst]; }

for(map::const_iterator

tempit=items_count.begin();tempit!=items_count.end();tempit++)

{

if(tempit->second if(tempstr.find(tempit->first)!=string::npos) //表示包含有非频繁子项集

{

found=1;

teststr=tempit->first; testint=tempit->second; break; } } }

tempstr.erase();

if(found) //包含非频繁子项集 {

break; } }

if(!found) //只有不包含有非频繁子项集才加入候选项集中，否则剪枝掉

candidatevec.push_back(item); found=0; //重置 }

} }

frequentvec.clear(); //清除上一轮的频繁项集 round++;

cout<<\"候选\"<for(vector >::size_type ix=0;ix!=candidatevec.size();++ix) //输出候选项集

{

cout<<\"{\";

for(vector::size_type iy=0;iy!=candidatevec[ix].size();++iy) {

cout<cout<<\ }

if(candidatevec.empty()) //候选项集为空 {

cout<<\"候选\"<int flag; //标记某个项集在某条事务中是否出现，出现为1，不出现为0 int count; //统计某个想集在整个交易的事务集中出现的次数 string tempstr; //临时string，用于串接各个项成一个字符串 int mark; //为避免执行多余的字符串串接工作

for(vector >::size_type sx=0;sx!=candidatevec.size();++sx) //构造下一轮的频繁项集

{

mark=1; count=0;

for(vector >::size_type sy=0;sy!=bitmap.size();++sy) {

flag=1; //初始化为1，表出现

for(vector::size_type sz=0;sz!=candidatevec[sx].size();++sz) {

if(bitmap[sy][candidatevec[sx].at(sz)]==0) //存在某一个子项不存在，则没出现项集

{

flag=0; }

if(mark==1) //只串接一次 {

tempstr+=candidatevec[sx].at(sz); //串接字符串 } }

if(flag) //flag仍然为，表示该项集在该条事务中出现了，计数加 {

count++; }

mark++; }

if(count>minsup) //支持度大于2 {

frequentvec.push_back(candidatevec[sx]); //插入频繁项集 }

items_count[tempstr]=count; //对应该项集的计数值

sort(candidatevec[sx].begin(),candidatevec[sx].end()); //排序 string tempstr2;

while(next_permutation(candidatevec[sx].begin(),candidatevec[sx].end())) //取下一排列组合

{

for(vector::size_type

tempst=0;tempst!=candidatevec[sx].size();tempst++) //拼接出该字符串组合

{

tempstr2+=candidatevec[sx][tempst]; }

items_count[tempstr2]=count; //对应该项集的计数值 tempstr2.erase(); }

tempstr.erase(); }

cout<<\"Press Enter to continue the processing\"; //pause getchar();

if(!frequentvec.empty()) //频繁项集不为空 {

cout<<\"频繁\"<for(int sx=0;sx!=frequentvec.size();++sx) //输出频繁项集 {

cout.setf(ios::fixed); cout<<\"{\";

for(vector::size_type sz=0;sz!=frequentvec[sx].size();++sz) {

cout<tempstr+=frequentvec[sx].at(sz); //串接字符串 }

cout<<\ cout<tempstr.erase(); }

cout<<\"Press Enter to continue the processing\"; //pause getchar(); } else {

cout<<\"没有\"<}while(!frequentvec.empty()); //频繁项集不为空,则循环继续 file.close(); return 0; } else {

return 0;

} //end of if(!frequentvec.empty()) }//end of if(!file) }

• 实验结果：