您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 数据挖掘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)foreachtransactiont∈D{//扫描事务数据库D(5)Ct=subset(Ck,t);(6)foreachcandidatec∈Ct(7)c.count++;//统计候选频繁k-项集的计数(8)}(9)Lk={c∈Ck|c.count≥min_sup}//满足最小支持度的k-项集即为频繁k-项集(10)}(11)returnL=∪kLk;//合并频繁k-项集(k0)2、算法流程①首先单趟扫描数据集,计算各个一项集的支持度,根据给定的最小支持度闵值,得到一项频繁集L1。②然后通过连接运算,得到二项候选集,对每个候选集再次扫描数据集,得出每个候选集的支持度,再与最小支持度比较。得到二项频繁集L2。③如此进行下去,直到不能连接产生新的候选集为止。④对于找到的所有频繁集,用规则提取算法进行关联规则的提取。3、算法的不足:(1)数据库重复扫描的次数太多。在由CK寻找LK的过程中,CK中的每一项都需要扫描事务数据库进行验证,以决定其是否加入Lk,存在的频繁K-项集越大,重复扫描的次数就越多。这一过程耗时太大,增加了系统1/0开销,处理效率低[10],不利于实际应用。(2)产生的候选集可能过于庞大。如果一个频繁1-项集包含100个项,那么频繁2-项集就有C2100个,为找到元素个数为100的频繁项集,如{b1,b2,…,b100},那么就要扫描数据库100次,产生的候选项集总个数为:举例:对于一个这样庞大的项集,计算机难以存储和计算,挖掘效率低下。二、算法的改进11、改进方法:性质1:频繁项集的所有非空子集都必须是频繁的。(Apriori性质,记为性质1)性质2:若频繁K-项集Lk中各个项可以做链接产生Lk+1,则Lk中每个元素在Lk中出现的次数应大于或等于K,若小于K,则删除该项在Lk中所有的事务集[11]。(Apriori性质的推论,记为性质2)改进的方法:在连接之后得到的候选频繁k项,直接进行最小支持度判断,并进行剪枝,从而直接得到频繁k项集,避免候选项集可能过大的问题;2、算法的流程①首先单趟扫描数据集,计算各个一项集的支持度,根据给定的最小支持度阈值,得到一项频繁集L1。②然后通过连接运算,对于每个连接的到项直接进行最小支持度判断,如果大于最小支持度的加入频繁二项集,如果小于则舍弃,循环直到连接完毕;得到二项频繁集L2。③如此进行下去,直到不能连接产生新的频繁项集为止。3、代码实现的描述(详细描述文末附上):使用C++,构造了一个Apriori类:classApriori{public://初始化,输入数据源,得到原始数据集、频繁1项集voidinit(stringfileName);//连接频繁k项集、并且直接剪枝,得到频繁k+1项集,加入到容器item_listvoidapri_gen();;//连接频繁k项集、并且直接剪枝,得到频繁k+1项集,加入到频繁项集集合frequentvec中floatcalculateSup(vectorstringjudge_item);//求候选项的支持度vectorstringmergeItem(vectorstringvect1,vectorstringvect2,intround);//判断两个项是否可以合并成一个新的项集做为新的候选项,能则合并,不能的返回空容器voidshowItem();//输出频繁项集private:vectorsetstringdatavec;//原始数据集inttrancount;//原始数据项数量vectorvectorpairvectorstring,floatfrequentvec;//频繁项集的集合doubleminsup;//设置最小支持度和最小置信度doubleminconf;//设置最小支持度和最小置信度};运行结果:效果对比:数据集大小:9835数据元素多少:170置信度:0.05原始:频繁1项集28候选2项集2^28频繁2项集3改进后:频繁1项集28频繁2项集3算法的改进2第一次扫描数据库时,对于数据库中的数据,利用各项元素的数字编号来替换各数据元素的名称;即将数据元素的名称字符传用数字来替换,从而减少在求各候选项的支持度时的资源消耗;代码中的改进之处,string类型的元素转为对应的int代号:储存频繁项集的容器由vectorvectorpairvectorstring,float变为vectorvectorpairvectorint,float;然后对代码进行相应的调整,使得代码正常运行;代码的描述:classApriori{public:voidinit(stringfileName);//初始化,输入数据源,得到原始数据集、频繁1项集voidapri_gen();//连接频繁k项集、并且直接剪枝,得到频繁k+1项集,加入到频繁项集集合frequentvec中floatcalculateSup(vectorintjudge_item);//求候选项的支持度vectorintmergeItem(vectorintvect1,vectorintvect2,intround);//判断两个项是否可以合并成一个新的项集做为新的候选项,能则合并,不能的返回空容器voidshowItem();//输出频繁项集private:vectorsetintdataNumVec;//原始数据集转换出来的、数据项用代号来表示的数据mapstring,intreflection;//原始数据中各个不同的元素的代号映射,数据元素从1开始编号inttrancount;//原始数据项数量vectorvectorpairvectorint,floatfrequentvec;//频繁项集集合,储存各项以及其支持度doubleminsup;//设置最小支持度和最小置信度};运行结果:效果对比:改进后14.496;14.549;14.577改进前20.165;20.463;20.383效率提升28.1%附:改进1的代码(改进2与改进1代码几乎相同,不同之处在于储存频繁项的数据类型,代码略)#includeiostream#includefstream#includestring#includevector#includemap#includecmath#includealgorithm#includeiomanip#includeset#includeutility#includetime.husingnamespacestd;/*最大数据集数量,置信度阈值,*/classApriori{public://初始化,输入数据源,得到原始数据集、频繁1项集voidinit(stringfileName);//连接频繁k项集、并且直接剪枝,得到频繁k+1项集,加入到容器item_listvoidapri_gen();//判断候选项,是否为频繁项floatcalculateSup(vectorstringjudge_item);vectorstringmergeItem(vectorstringvect1,vectorstringvect2,intround);//判断两个项集是否可以合并(要求只有一项不同)成一个新的项集(做为候选集)voidshowItem();private:vectorsetstringdatavec;//原始数据集inttrancount;//原始数据项数量vectorvectorpairvectorstring,floatfrequentvec;//频繁项集de集合doubleminsup;//设置最小支持度和最小置信度doubleminconf;//设置最小支持度和最小置信度};voidApriori::init(stringfileName){//std::cout调用initendl;minsup=0.05;minconf=0.5;trancount=0;ifstreamfile(fileName);//打开数据文件if(!file)//检查文件是否打开成功{std::coutFailtoopendatafile!endl;}else{stringtemp;setstringitem;//项集的临时setintbegin,end;while(getline(file,temp))//一行一行读入数据{trancount++;begin=0;temp.erase(0,temp.find_first_not_of(\r\t\n));//去除字符串首部的空格temp.erase(temp.find_last_not_of(\r\t\n)+1);//去除字符串尾部的空格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);//将一个事务中的所有项当成一个整体插入另一个大的vector中item.clear();//清空item//couttempendl;}mapstring,intitems_count;//统计各个项集的数目for(vectorsetstring::size_typeix=0;ix!=datavec.size();++ix){for(setstring::iteratoriy=datavec[ix].begin();iy!=datavec[ix].end();++iy){if(items_count.find(*iy)==items_count.end())items_count[*iy]=1;elseitems_count[*iy]++;//该项集的计数加1}}vectorstringelem;vectorpairvectorstring,floatcandidatevec;//候选项集for(mapstring,int::iteratorix=items_count.begin();ix!=items_count.end();ix++){if((float(ix-second))/trancount=minsup)//判断候选频繁1项集中的各项,是否大于最小频繁度,如果是,则为频繁项集;{elem.push_back(ix-first);candidatevec.push_back(make_pair(elem,(float(ix-second))/trancount));}elem.clear();//一定要清空}if(!candidatevec.empty()){frequentvec.push_b
本文标题:数据挖掘Apriori算法C++实现
链接地址:https://www.777doc.com/doc-3800163 .html