数据挖掘Apriori算法C++实现 - 图文 

- --

一、原Apriori算法 1、算法原理：

该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法 （1）L1 = find_frequent_1-itemsets(D); // 挖掘频繁1-项集，比较容易 （2）for (k=2;Lk-1 ≠Φ ;k++) {

（3）Ck = apriori_gen(Lk-1 ,min_sup); // 调用apriori_gen方法生成候选频繁k-项集 （4）for each transaction t ∈ D { // 扫描事务数据库D （5）Ct = subset(Ck,t);

（6）for each candidate c ∈ Ct

（7）c.count++; // 统计候选频繁k-项集的计数 （8）}

（9）Lk ={c ∈ Ck|c.count≥min_sup} // 满足最小支持度的k-项集即为频繁k-项集 （10） }

（11） return L= ∪ k Lk; // 合并频繁k-项集（k>0） 2、算法流程

① 首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度闵值，得到一项频繁集L1。

② 然后通过连接运算，得到二项候选集，对每个候选集再次扫描数据集，得出每个候选集的支持度，再与最小支持度比较。得到二项频繁集L2。

③ 如此进行下去，直到不能连接产生新的候选集为止。

④ 对于找到的所有频繁集，用规则提取算法进行关联规则的提取。

3、算法的不足：

（１ ）数据库重复扫描的次数太多。在由 Ｃ Ｋ 寻找 Ｌ Ｋ 的过程中， Ｃ Ｋ 中的每一项都需要扫描事务数据库进行验证，以决定其是否加入 Ｌ ｋ ，存在的频繁 Ｋ － 项集越大，重复扫描的次数就越多。这一过程耗时太大，增加了系统 １ ／ ０ 开销，处理效率低 ［１０ ］ ，不利于实际应用。

（２ ）产生的候选集可能过于庞大。如果一个频繁１ － 项集包含１００个项，那么频繁２ － 项集就有 Ｃ２ １００ 个，为找到元素个数为１００的频繁项集，如｛ｂ １ ， ｂ ２ ，…， ｂ １００ ｝，那么就要扫描数据库１００次，产生的候选项集总个数为： 举例：

对于一个这样庞大的项集，计算机难以存储和计算，挖掘效率低下。

二、算法的改进1 1、改进方法：

性质１：频繁项集的所有非空子集都必须是频繁的。（ Ａｐｒｉｏｒｉ性质，记为性质１ ） 性质２：若频繁Ｋ － 项集 Ｌ ｋ 中各个项可以做链接产生 Ｌ ｋ ＋１

，则Ｌ ｋ 中每个元素在 Ｌ ｋ 中出现的次数应大于或等于 Ｋ ，若小于 Ｋ ，则删除该项在 Ｌ ｋ 中所有的事务集 ［１１ ］ 。（Ａｐｒｉｏｒｉ性质的推论，记为性质２ ）

改进的方法：在连接之后得到的候选频繁k项，直接进行最小支持度判断，并进行剪枝，从而直接得到频繁k项集，避免候选项集可能过大的问题；

2、算法的流程

① 首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度阈值，得到一项频繁集L1。

- . -word资料-

- --

② 然后通过连接运算，对于每个连接的到项直接进行最小支持度判断，如果大于最小支持度的加入频繁二项集，如果小于则舍弃，循环直到连接完毕；得到二项频繁集L2。 ③ 如此进行下去，直到不能连接产生新的频繁项集为止。

3、代码实现的描述（详细描述文末附上）： 使用C++，构造了一个Apriori类：

class Apriori {

public: //初始化，输入数据源，得到原始数据集、频繁1项集 void init(string fileName); //连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到容器item_list void apri_gen();;//连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到频繁项集集合frequentvec中 float calculateSup(vector judge_item); //求候选项的支持度 vector mergeItem(vector vect1,vector vect2,int round); //判断两个项是否可以合并成一个新的项集做为新的候选项，能则合并，不能的返回空容器 void showItem();//输出频繁项集 private: vector> datavec; //原始数据集 int trancount; //原始数据项数量 vector,float>>> frequentvec; //频繁项集的集合 double minsup; //设置最小支持度和最小置信度 double minconf; //设置最小支持度和最小置信度 };

运行结果： 效果对比：

数据集大小：9835 数据元素多少：170 置信度：0.05

原始：频繁1项集28 候选2项集2^28 频繁2项集3

改进后：频繁1项集28 频繁2项集3

算法的改进2

第一次扫描数据库时，对于数据库中的数据，利用各项元素的数字编号来替换各数据元素的名称；即将数据元素的名称字符传用数字来替换，从而减少在求各候选项的支持度时的资源消耗； 代码中的改进之处，

string类型的元素转为对应的int代号：储存频繁项集的容器由vector,float>>>变为vector,float>>>；然后对代码进行相应的调整，使得代码正常运行；

代码的描述： class Apriori

- . -word资料-

- --

{

public: void init(string fileName); //初始化，输入数据源，得到原始数据集、频繁1项集 void apri_gen();//连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到频繁项集集合frequentvec中 float calculateSup(vector judge_item); //求候选项的支持度 vector mergeItem(vector vect1,vector vect2,int round); //判断两个项是否可以合并成一个新的项集做为新的候选项，能则合并，不能的返回空容器 void showItem();//输出频繁项集 private: vector> dataNumVec;//原始数据集转换出来的、数据项用代号来表示的数据 map reflection; //原始数据中各个不同的元素的代号映射,数据元素从1开始编号 int trancount; //原始数据项数量 vector,float>>> frequentvec; //频繁项集集合，储存各项以及其支持度 double minsup; //设置最小支持度和最小置信度 };

运行结果：

效果对比：

改进后14.496；14.549；14.577 改进前20.165；20.463；20.383 效率提升28.1%

- . -word资料-

- --

附：改进1的代码（改进2与改进1代码几乎相同，不同之处在于储存频繁项的数据类型，代码略） #include #include #include #include #include

- --

中 //std::cout<<\调用init\minsup = 0.05; minconf = 0.5; trancount=0; ifstream file(fileName); //打开数据文件 if(!file) //检查文件是否打开成功 { std::cout<<\} else { string temp; set item; //项集的临时set int begin,end; while(getline(file,temp)) //一行一行读入数据 { trancount++; begin=0; temp.erase(0,temp.find_first_not_of(\ //去除字符串首部的空格 temp.erase(temp.find_last_not_of(\ //去除字符串尾部的空格 while((end=temp.find(',',begin))!=string::npos) //每一个事务中的项是以空格为分隔符的 { item.insert(temp.substr(begin,end-begin)); //将每一个项插入item中 begin=end+1; } item.insert(temp.substr(begin)); //一个事务中的最后一项 datavec.push_back(item); //将一个事务中的所有项当成一个整体插入另一个大的vectoritem.clear(); //清空item //cout< items_count; //统计各个项集的数目 for(vector >::size_type ix= 0 ;ix !=datavec.size(); ++ix) { for(set::iterator iy=datavec[ix].begin();iy!=datavec[ix].end();++iy) { if (items_count.find(*iy) == items_count.end()) items_count[*iy]=1; else items_count[*iy]++; //该项集的计数加1 } } - . -word资料-