优化的ID3算法在酒店客房续费问题中的应用

发布时间：2017-09-19 07:06

  本文关键词：优化的ID3算法在酒店客房续费问题中的应用

  更多相关文章： 数据挖掘 决策树算法 ID3算法 多值偏向 算法优化

【摘要】：随着数据库技术的逐步成熟,分类预测之类的数据挖掘技术也得到了高速的发展,分类预测技术中的决策树方法也常常被应用于多个行业领域。ID3算法作为影响力最大的决策树算法之一而且得到了大范围的应用,然而ID3算法也有一些不足之处。本文主要针对ID3算法多值偏向、算法公式计算量大两方面的的缺陷,通过对ID3算法进行算法改进和公式简化,从而实现对ID3算法的优化,主要进行的工作为:(1)提出基于矫正函数的ID3优化方案。在基于矫正函数的ID3优化方案中,克服多值偏向问题的方法为:通过引入矫正函数的定义,对子元组所需的期望信息量进行矫正,多值偏向分析证明改进后的ID3算法可克服多值偏向问题;克服ID3信息增益公式运算较为耗时的方法为:通过利用等价无穷小简化信息增益公式,使得简化后的信息增益公式中已消除了较为耗时的对数运算。最后,将算法改进和信息增益公式简化两部分的工作相结合,并提出了基于矫正函数的决策树优化算法。实验结果分析表明:与ID3算法相比,在分类精度和计算时间两个方面,基于矫正函数的决策树优化算法具有更好的优化效果。(2)提出基于相关系数的ID3优化方案。在基于相关系数的ID3优化方案中,克服多值偏向问题的方法为:将相关系数修改成适用于决策树领域的新型相关系数,通过引入新型相关系数子元组所需的期望信息量进行重新矫正,实验中的多值偏向相关理论的分析证明了改进后的ID3算法能够解决克服多值偏向的缺陷;克服ID3信息增益公式运算较为耗时的方法为:通过利用麦克劳林公式简化信息增益公式,使得简化后的信息增益公式中已消除了较为耗时的对数运算。最后,将算法改进和信息增益公式简化两部分之间工作进行结合,得到了基于相关系数的决策树优化算法。实验结果表明,相比于ID3算法,基于相关系数的决策树优化算法既能克服多值偏向问题,又具有更高的分类精度,同时也降低了决策树的生成时间;相比于基于矫正函数的决策树优化算法,除了在决策树生成时间方面,基于相关系数的决策树优化算法的时间较长;但在分类精度方面,基于相关系数的决策树优化算法则更显优势。最后将提出的两种ID3优化算法应用于酒店客房续费问题中,并在Visual Studio 2013上用C++语言分别将其实现。将酒店客户基本信息和客户入住后的居住意见整理成样本集合,分别用ID3算法及提出的两种优化算法建立决策树并提取出规则,通过对算法生成结果进行对比分析,表明两种优化后的ID3决策树算法在生成规则上具有更好的实验效果。
【关键词】：数据挖掘 决策树算法 ID3算法 多值偏向 算法优化
【学位授予单位】：江西理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：F719.2;TP311.13
【目录】：

• 摘要4-5
• Abstract5-10
• 第一章 绪论10-15
• 1.1 课题研究背景与意义10
• 1.2 国内外研究现状10-12
• 1.2.1 国外决策树算法研究进程10-11
• 1.2.2 国内决策树算法研究进程11-12
• 1.3 课题研究内容12-13
• 1.4 课题组织结构13-15
• 第二章 数据挖掘技术简介和决策树算法15-22
• 2.1 数据挖掘概述15-17
• 2.1.1 数据挖掘的定义15
• 2.1.2 数据挖掘的方法15-16
• 2.1.3 数据挖掘的步骤16-17
• 2.2 决策树概述17-18
• 2.2.1 决策树的相关介绍及其生成17
• 2.2.2 决策树的规则提取及预测17-18
• 2.3 ID3算法概述18-21
• 2.3.1 ID3算法的基本思想18
• 2.3.2 ID3算法的算法描述18-19
• 2.3.3 ID3算法的实例分析19-21
• 2.3.4 ID3算法的优缺点21
• 2.4 本章小结21-22
• 第三章 基于矫正函数的决策树优化算法22-36
• 3.1 引言22
• 3.2 相关基本理论22-25
• 3.2.1 ID3算法改进的理论基础22-23
• 3.2.2 等价无穷小相关简化理论基础23-24
• 3.2.3 基于矫正函数的ID3决策树优化算法的实现方案24-25
• 3.3 结合矫正函数的ID3算法改进25-28
• 3.3.1 矫正函数的提出25
• 3.3.2 矫正函数的选取25-26
• 3.3.3 矫正函数的相关证明26-27
• 3.3.4 基于矫正函数的ID3改进算法27
• 3.3.5 改进后ID3算法的多值偏向分析27-28
• 3.4 信息增益公式的简化28-29
• 3.5 基于矫正函数的ID3决策树优化算法的提出29-30
• 3.6 实验研究30-35
• 3.6.1 实验说明及评价标准30
• 3.6.2 DTCF算法的实例验证与分析30-32
• 3.6.3 实验验证及分析32-35
• 3.6.4 实验结论35
• 3.7 本章小结35-36
• 第四章 基于相关系数的决策树优化算法36-52
• 4.1 引言36-37
• 4.2 相关基本理论37-39
• 4.2.1 麦克劳林公式相关简化理论37-38
• 4.2.2 相关系数的定义及含义38-39
• 4.2.3 基于相关系数的决策树优化算法的实现方案39
• 4.3 结合相关系数的ID3算法改进39-42
• 4.3.1 属性之间相关系数的引入39-41
• 4.3.2 基于相关系数的ID3改进算法41
• 4.3.3 改进后ID3算法的多值偏向分析41-42
• 4.4 信息增益公式的简化42-43
• 4.5 基于相关系数的决策树优化算法的提出43
• 4.6 实验研究43-51
• 4.6.1 实验说明及评价标准43-44
• 4.6.2 DTCC算法的实例验证与分析44-49
• 4.6.3 实验验证及分析49-50
• 4.6.4 实验结论50-51
• 4.7 本章小结51-52
• 第五章 优化的ID3算法在酒店客房续费问题中的应用52-61
• 5.1 引言52
• 5.2 问题确立52-53
• 5.3 数据准备53-54
• 5.4 数据挖掘算法的执行54-58
• 5.4.1 ID3算法的实现55
• 5.4.2 DTCF算法的实现55-56
• 5.4.3 DTCC算法的实现56-57
• 5.4.4 三种算法运行结果的比较分析57-58
• 5.5 提取规则及预测58-60
• 5.6 本章小结60-61
• 第六章 总结和展望61-63
• 6.1 本文工作总结61-62
• 6.2 课题展望62-63
• 参考文献63-66
• 致谢66-67
• 攻读学位期间的研究成果67-68

【相似文献】

中国期刊全文数据库 前10条

1 葛磊;武芳;王鹏波;张冬林;;3维建筑综合中基于最小特征的面平移算法[J];测绘科学技术学报;2009年02期

2 骆雯,孙延明,陈振威,陈锦昌;判断点与封闭多边形相对关系的改进算法[J];机械;1999年03期

3 李林;卢显良;;一种基于切割映射的规则冲突消除算法[J];电子学报;2008年02期

4 刘巧玲;张红英;林茂松;;一种简单快速的图像去雾算法[J];计算机应用与软件;2013年07期

5 林亚平,杨小林;快速概率分析进化算法及其性能研究[J];电子学报;2001年02期

6 章郡锋;吴晓红;黄晓强;何小海;;基于暗原色先验去雾的改进算法[J];电视技术;2013年23期

7 杨铁军;靳婷;;一种动态整周模糊值求解算法及其仿真分析[J];系统工程与电子技术;2007年01期

8 周秀玲;郭平;陈宝维;王静;;几种计算超体积算法的比较研究[J];计算机工程;2011年03期

9 吴一戎,胡东辉,彭海良;Chirp Scaling SAR成象算法及其实现[J];电子科学学刊;1995年03期

10 王贵竹;一种产生单向分解值的算法[J];安徽大学学报(自然科学版);2001年03期

中国重要会议论文全文数据库 前10条

1 尹冀锋;;一种新的图象自适应增强算法[A];四川省通信学会一九九二年学术年会论文集[C];1992年

2 宁春平;田家玮;郭延辉;王影;张英涛;郑桂霞;刘研;;计算机辅助增强、分割算法在鉴别乳腺良、恶性肿块中的应用价值[A];中华医学会第十次全国超声医学学术会议论文汇编[C];2009年

3 谢丽聪;;SVB查询改写算法的改进[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年

4 郑存红;;复杂背景下相关跟踪算法研究及DSP实现[A];中国光学学会2010年光学大会论文集[C];2010年

5 杨文杰;吴军;;RFID抗冲突算法研究[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年

6 高山;毕笃彦;魏娜;;一种基于UPF的小目标TBD算法[A];第十四届全国图象图形学学术会议论文集[C];2008年

7 周磊;张卫华;王晓奇;张军;;基于流水算法的智能路障机器人设计[A];2011年全国电子信息技术与应用学术会议论文集[C];2011年

8 潘巍;李战怀;陈群;索博;李卫榜;;面向MapReduce的非对称分片复制连接算法优化技术研究[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

9 李伟伟;蔡康颖;郑新;王文成;;3D模型中重复结构的多尺度快速检测算法[A];第六届和谐人机环境联合学术会议（HHME2010)、第19届全国多媒体学术会议（NCMT2010）、第6届全国人机交互学术会议（CHCI2010）、第5届全国普适计算学术会议（PCC2010）论文集[C];2010年

10 杨任尔;陈恳;励金祥;;基于棱边方向检测的运动自适应去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

中国重要报纸全文数据库 前1条

1 国泰君安资产管理部;“算法交易”是道指暴跌罪魁祸首?[N];上海证券报;2010年

中国博士学位论文全文数据库 前10条

1 冯辉;网络化的并行与分布式优化算法研究及应用[D];复旦大学;2013年

2 许玉杰;云计算环境下海量数据的并行聚类算法研究[D];大连海事大学;2014年

3 李琰;基于猫群算法的高光谱遥感森林类型识别研究[D];东北林业大学;2015年

4 陈加顺;海洋环境下聚类算法的研究[D];南京航空航天大学;2014年

5 王洋;基于群体智能的通信网络告警关联规则挖掘算法研究[D];太原理工大学;2015年

6 雷雨;面向考试时间表问题的启发式进化算法研究[D];西安电子科技大学;2015年

7 熊霖;大数据下的数据选择与学习算法研究[D];西安电子科技大学;2015年

8 周雷;基于图结构的目标检测与分割算法研究[D];上海交通大学;2014年

9 王冰;人工蜂群算法的改进及相关应用的研究[D];北京理工大学;2015年

10 蒋亦樟;多视角和迁移学习识别方法和智能建模研究[D];江南大学;2015年

中国硕士学位论文全文数据库 前10条

1 姚鑫宇;EMD去噪与MUSIC算法在DOA估计中的联合应用[D];昆明理工大学;2015年

2 陆进;面向含噪数据聚类相关算法的研究[D];复旦大学;2014年

3 叶一舟;红外弱小目标检测算法研究[D];上海交通大学;2015年

4 王继重;基于Hadoop和Mahout的K-Means算法设计与实现[D];大连海事大学;2016年

5 何静;遥感图像的快速压缩算法研究[D];北京交通大学;2016年

6 章华燕;钢轨擦伤检测算法研究[D];北京交通大学;2016年

7 王一博;MODIS地震热异常的数据处理与算法研究[D];中国石油大学(华东);2014年

8 成鑫;基于组合优化问题的多目标模因算法的研究[D];南京航空航天大学;2015年

9 傅致晖;基于协同分割的视频目标分割算法研究[D];上海交通大学;2015年

10 张媛;运动车辆检测与跟踪算法的研究与实现[D];大连海事大学;2016年

，

本文编号：880202