数据挖掘Apriori算法C++实现
更新时间:2023-05-20 00:57:01 阅读量: 实用文档 文档下载
- --
一、原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)数据库重复扫描的次数太多。在由CK寻找LK的过程中,CK中的每一项都需要扫描事务数据库进行验证,以决定其是否加入Lk,存在的频繁K-项集越大,重复扫描的次数就越多。这一过程耗时太大,增加了系统1/0开销,处理效率低[10],不利于实际应用。
(2)产生的候选集可能过于庞大。如果一个频繁1-项集包含100个项,那么频繁2-项集就有C2
100个,为找到元素个数为100的频繁项集,如{b1,b2,…,b100},那么就要扫描数据库100次,产生的候选项集总个数为:
举例:
对于一个这样庞大的项集,计算机难以存储和计算,挖掘效率低下。
二、算法的改进1
1、改进方法:
性质1:频繁项集的所有非空子集都必须是频繁的。(Apriori性质,记为性质1)
性质2:若频繁K-项集Lk中各个项可以做链接产生Lk+1
,则Lk中每个元素在Lk中出现的次数应大于或等于K,若小于K,则删除该项在Lk中所有的事务集[11]。(Apriori性质的推论,记为性质2)
改进的方法:在连接之后得到的候选频繁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<string> judge_item); //求候选项的支持度
vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round); //判断两个项是否可以合并成一个新的项集做为新的候选项,能则合并,不能的返回空容器
void showItem();//输出频繁项集
private:
vector<set<string>> datavec; //原始数据集
int trancount; //原始数据项数量
vector<vector<pair<vector<string>,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<vector<pair<vector<string>,float>>>变为vector<vector<pair<vector<int>,float>>>;然后对代码进行相应的调整,使得代码正常运行;
代码的描述:
class Apriori
- . -word资料-
- --
{
public:
void init(string fileName); //初始化,输入数据源,得到原始数据集、频繁1项集
void apri_gen();//连接频繁k项集、并且直接剪枝,得到频繁k+1项集,加入到频繁项集集合frequentvec中float calculateSup(vector<int> judge_item); //求候选项的支持度
vector<int> mergeItem(vector<int> vect1,vector<int> vect2,int round); //判断两个项是否可以合并成一个新的项集做为新的候选项,能则合并,不能的返回空容器
void showItem();//输出频繁项集
private:
vector<set<int>> dataNumVec;//原始数据集转换出来的、数据项用代号来表示的数据
map<string,int> reflection; //原始数据中各个不同的元素的代号映射,数据元素从1开始编号
int trancount; //原始数据项数量
vector<vector<pair<vector<int>,float>>> frequentvec; //频繁项集集合,储存各项以及其支持度
double minsup; //设置最小支持度和最小置信度
};
运行结果:
效果对比:
改进后14.496;14.549;14.577
改进前20.165;20.463;20.383
效率提升28.1%
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
- --
- . -word资料-
正在阅读:
数据挖掘Apriori算法C++实现05-20
中式烹调师实操考场设置标准05-22
2016新人教版二年级数学下册第九单元数学广角教案09-01
小学数学五年级上册培优补差记录表01-03
石家庄小学排名02-14
概率统计分布表(常用)06-02
2.第二章群论自测练习01-16
中学篮球教学存在的问题及对策研究09-13
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- C++
- 数据挖掘
- 算法
- Apriori
- 实现
- 非球面AcrySof ReSTOR+3D人工晶状体的临床应用观察
- 佛山交通路网简介以及五区住宅板块划分
- _通作者之意_开览者之心_金圣叹评点_水浒_美学思想初探
- MP4 AVI RMVB MKV 这几种常见格式都有什么区别
- 国际营销案例分析题
- 床旁连续性血液滤过
- 完成【实验报告2-1】离心泵性能测定实验
- 竹鼠养殖走上致富路
- 新课标人教版高中语文背诵篇目汇编
- 气井临界携液流量的计算方法_熊健
- 校园文化建设实施方案
- 奥巴马就职演讲的人际意义解读
- 浙江大学远程教育英语2 2012秋季 Unit 1
- 廉洁文化社区创建工作总结
- TC4钛合金微弧氧化陶瓷膜层形貌及性能研究
- 并列句详解与复习含中考真题解析
- 2021新版浅谈当下企业安全建设
- 2012年研究院工会工作总结
- 2015深圳市中考物理模拟题(1)
- 养老保险第二支柱:企业年金制度的探索