数据挖掘Apriori算法C++实现

《数据挖掘Apriori算法C++实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、riori_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

3、c.count≥min_sup}//满足最小支持度的k-项集即为频繁k-项集（10）}（11）returnL=∪kLk;//合并频繁k-项集（k>0）2、算法流程①首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度闵值，得到一项频繁集

4、L1。②然后通过连接运算，得到二项候选集，对每个候选集再次扫描数据集，得出每个候选集的支持度，再与最小支持度比较。得到二项频繁集L2。③如此进行下去，直到不能连接产生新的候选集为止。④对于找到的所有频繁集，用规则提取算法进行关联规则的提取。3、算法的不足：（１）数据库重复扫描的次数太多。在由ＣＫ寻找ＬＫ的过程中，ＣＫ中的每一项都需要扫描事务数据库进行验证，以决定其是否加入Ｌｋ，存在的频繁Ｋ－项集越大，重复扫描的次数就越多。这一过程耗时太大，增加了系统１／０开销，处理效率低［１０］，不利于实际应用。（２）产生的候选集可能过于庞大。如果一个频繁１－项集包含１００个项，那么频繁２－项集就有Ｃ

5、２１００个，为找到元素个数为１００的频繁项集，如｛ｂ１，ｂ２，…，ｂ１００｝，那么就要扫描数据库１００次，产生的候选项集总个数为：举例：对于一个这样庞大的项集，计算机难以存储和计算，挖掘效率低下。二、算法的改进11、改进方法：性质１：频繁项集的所有非空子集都必须是频繁的。（Ａｐｒｉｏｒｉ性质，记为性质１）性质２：若频繁Ｋ－项集Ｌｋ中各个项可以做链接产生Ｌｋ＋１，则Ｌｋ中每个元素在Ｌｋ中出现的次数应大于或等于Ｋ，若小于Ｋ，则删除该项在Ｌｋ中所有的事务集［１１］。（Ａｐｒｉｏｒｉ性质的推论，记为性质２）改进的方法：在连接之后得到的候选频繁k项，直接进行最小支持度判断，并进行剪枝，从而直接得

6、到频繁k项集，避免候选项集可能过大的问题；2、算法的流程①首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度阈值，得到一项频繁集L1。word教育资料..②然后通过连接运算，对于每个连接的到项直接进行最小支持度判断，如果大于最小支持度的加入频繁二项集，如果小于则舍弃，循环直到连接完毕；得到二项频繁集L2。③如此进行下去，直到不能连接产生新的频繁项集为止。3、代码实现的描述（详细描述文末附上）：使用C++，构造了一个Apriori类：classApriori{public://初始化，输入数据源，得到原始数据集、频繁1项集voidinit(stringfileName);/

7、/连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到容器item_listvoidapri_gen();;//连接频繁k项集、并且直接剪枝，得到频繁k+1项集，加入到频繁项集集合frequentvec中floatcalculateSup(vectorjudge_item);//求候选项的支持度vectormergeItem(vectorvect1,vectorvect2,intround);//判断两个项是否可以合并成一个新的项集做为新的候选项，能则合并，不能的返回空容器voidshowItem();//输出频繁项集

8、private:vector>datavec;//原始数据集inttrancount;//原始数据项数量vector,float>>>frequentvec;//频繁项集的集合doubleminsup;//设置最小支持度和最小置信度doubleminconf;//设置最小支持度和最小置信度};运行结果：效果对比：数据集大小：9835数据元素多少：170置信度：0.05