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