Apriori算法实验报告

题 目学生姓名学生学号专业班级指导教师

Apriori算法实现

2014-12-27

实验一 Apriori算法实现

一、 实验目的

1. 加强对Apriori算法的理解；

2. 锻炼分析问题、解决问题并动手实践的能力。

二、 实验要求

使用一种你熟悉的程序设计语言，如C++或Java，实现Apriori算法，至少在两种不同的数据集上比较算法的性能。

三、 实验环境

Win7 旗舰版 + Visual Studio 2010 语言：C++

四、 算法描述

1、 Apriori算法说明

在Apriori算法中，寻找频繁项集的基本思想是：

A. 简单统计所有含一个元素项目集出现的频率，找出不小于最小支持度的

项目集, 即频繁项集；

B. 从第二步开始，循环处理直到再没有最大项目集生成。循环过程是: 第

k步中, 根据第k-1步生成的频繁(k-1)项集产生侯选k项集。根据候选k项集，算出候选k项集支持度，并与最小支持度比较, 找到频繁k项集。 下文中遇到的以下符号,分别代表相应的内容 k-itemset k项集

Lk 频繁k项集 Ck 侯选k项集

2、 Apriori算法描述

数据结构说明

double minsup; //设置最小支持度

map items_count; //统计各个项集的数目 vector> datavec; //原始数据项集 vector> candidatevec; //候选项集 vector> frequentvec; //频繁项集 ofstream outFile;

int round=1; //生成项集轮次 long trancount=0; //原始事务总数

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

Apriori算法的第一步是简单统计所有含一个元素的项集出现的频率，来决定频繁1项集。在第k步,分两个阶段：1，用函数genCanItemsetK，通过第(k-1)步中生成的频繁(k-1)项集来生成侯选k项集；2.计算侯选k项集的支持度，并找出频繁k项集。

Apriori算法描述如下 getOriData();

//获取原始数据集，并统计事务个数

genCanItemset1(); //产生输出候选1项集 genFreItemset1(); //产生频繁项集

if(!frequentvec.empty()) //根据频繁1项集，执行程序 {

do {

genCanItemsetK(); //生成并输出候选k项集

}

genFreItemsetK(); //计算并输出频繁k项集

}while(!frequentvec.empty()); //频繁项集不为空,则循环继续

其中，产生候选k项集函数genCanItemsetK中涉及两个重要函数，项集合并函数mergeItem和剪枝函数cutNotCanItemsetK。

3、 函数方法说明

//获取原始数据集，并统计事务个数 void getOriData(); //合并生成新的候选项集

vector mergeItem(vector vect1,vector vect2,int round); //判断项集item是否已经存在候选项集集合items中,存在则返回1 int isExist(vector item,vector >items); //产生并输出候选1项集 void genCanItemset1(); //产生并输出频繁1项集 void genFreItemset1();

//产生并输出候选k-项集（k>=2） void genCanItemsetK();

//产生并输出频繁k-项集（k>=2） void genFreItemsetK();

//剪枝：剪去合并后项集中含有非频繁项集中的项 void cutNotCanItemsetK(vector & item);

五、 实验截图

1. 程序运行界面

2. 输出文件截图1

3. 输出文件截图1