前向决策树算法的研究与改进

《前向决策树算法的研究与改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、河北大学工学硕士学位论文性差。因此，在不影响分类正确率的前提下，产生了大量的优化算法来简化决策树，优化后的决策树规模更小，导出的分类规则更简单易懂。目前，用于决策树优化的方法主要有剪枝算法[2]、修改测试属性空间[4]、修改测试属性选择标准[5]、对数据进行限制[6]、改进数据结构[5]等。然而，目前存在的大多数决策树归纳算法，比如ID3[7]，C4.5[5]和CART[8]，它们都使用局部启发式试图产生规模较小的树，这些算法都是基于局部最优的贪婪算法。贪婪算法一个主要缺点是错误的决策引起的损害是不可

2、逆转的：一旦一个属性被选择用来分裂，就不能回溯或选择另一个属性进行替代。众所周知，局部最优不一定能保证全局最优，而找到全局最优决策树是NP-hard问题[9]，所以人们希望能有一种方法改变这种局部最优的状况以缩小贪婪算法产生的近似最优解与最优解之间的差距。前向搜索正是这样一种技术[10]。在前向决策树归纳过程中，每个结点在做出最终决策之前，前向搜索试图通过预测来避免错误的或无贡献的分裂。由于k层前向搜索算法随搜索深度的增加，时间复杂度呈指数级的增长，我们经常使用一层搜索。但是随着近些年计算能力的快速提

3、高，对于中等大型数据集，有限步的前向搜索已经是可行的。1.2国内外研究现状目前，许多研究者对前向决策树算法进行了研究，这些研究主要集中在对前向决策树算法进行的改进，从而得出比较好的结果。1995年，Sreeramak.Murthy&StevenSalzberg[11]对前向决策树算法与贪婪算法进行了比较，旨在决策树的归纳过程中准确的量化有限步的前向搜索产生的益处。通过大量的实验发现尽管前向搜索需要大量的计算，但它产生的益处非常小甚至是不存在。前向搜索唯一的好处是它产生的树深度可能会稍小。文章认为使用前

4、向搜索不仅不能产生益处，事实上它经常会伤害决策树的质量。由于文献[11]指出前向搜索不会产生更好的决策树，使得接下来的几年里前向决策树算法的发展很缓慢。直到2001年Dong&Kothari提出了前向模糊决策树算法[12]。考虑到决策树的贪婪与局部特性，作者提出了把共生矩阵与现有的分裂标准（信息增益、增益比率，或其他的分裂标准）相结合，共同选择用来分裂的属性。此方法与现有方法相比较，其得到的决策树规模更小，预测精度更高。2第1章绪论在处理逻辑函数方面，前向决策树算法是一种标准的方法。然而此方法通常只能

5、处理两个或三个变量的函数，因为时间复杂度随搜索深度的增加呈指数级增长。针对此缺点，2003年，DavidPage&SoumyaRay[13]提出了一种新的方法——skewing。对于适量的数据，此方法能处理六个或七个变量的函数，其时间复杂度只有常数级。由于文献[11]只是从实验的角度说明了使用前向搜索会伤害决策树的质量，并没有理论上的分析。2005年，TapioElomaa&TuomoMalinen[14,15]从偏置和不一致两个方面分析了前向搜索为什么会对决策树归纳产生不好的影响。文章同时提出了使用

6、有限深度的前向决策树算法与投票算法相结合，来处理连续值属性，其产生的决策树精度更高。2004年，SaherEsmeir&ShaulMarkovitch[16,17]提出了两种新的基于前向搜索的任意时间决策树归纳算法——ID3-k和LSID3(lookaheadbystochasticID3)。ID3-k主要是对ID3算法进行扩展，在选择分裂属性时，使搜索深度加深到k层，试图得到好的决策树。LSID3重复调用随机ID3算法，从候选属性中选择一个用于分裂的属性。通过在不同的数据库上做实验，分别得到了较好的

7、结果。与国外相比，国内对前向决策树算法的研究相对很少，具有代表性的是刘小虎等学者以ID3为基础提出的改进的优化算法[19]。该算法在选择一个新的属性时，不仅考虑该属性带来的信息增益，而且考虑选择该属性后继续选择的属性带来的信息增益，即同时考虑树的两层结点。针对文献[16]提出的LSID3算法，2007年，JianXue&YunxinZhao[18]把此算法应用到了语音模型的状态绑定中。文章使用了两种方法来建造语音决策树：受限制的方法和随机方法。为了找到一棵与训练数据一致的简洁的树，受限制的前向搜索方法

8、在预先选定的问题子集中搜索最优语音问题；随机前向搜索方法对一个结点分裂时，使用子树的大小代替信息增益来选择最优语音问题。实验结果表明，文中提出的方法能减小决策树的规模提高识别精度。针对现有前向决策树算法的不足，很多研究人员在控制决策树的规模和提高决策树的精度等方面做出了努力，同时提出了许多新的算法和标准。前向决策树算法发展很缓慢主要是由于其计算代价很大，得到的效果也不是很理想。1.2论文主要研究内容与结构安排本文在前人工作的基础上，针对前向决策树算法进行