决策树算法研究及在查询接口发现中的应用

摘要

本文针对决策树学习过程中存在的多值偏向问题,提出两种改进方法,从不同的角度来解决ID3算法的缺陷并优化决策树学习算法。同时,在算法优化的基础上,以Eclipse为开发平台,设计实现了决策树算法演示软件,将其作为算法的实验平台,并使用UCI机器学习数据集作为实验数据,对相应的算法进行实验效果的验证。同时又将决策树学习算法应用到Deep Web查询接口发现中,更好的对查询接口进行分类与发现。
　　 本文的主要研究成果概括为以下四个方面:
　　 (1)分析研究决策树构建过程中存在的多值偏向问题,并在此基础上提出了一种基于等预测能力的决策树分支合并算法,采用预剪枝的策略对非叶子节点中分类预测能力相等的分支进行合并。
　　 (2)针对经典ID3算法中采用信息增益作为选择标准存在多值偏向问题,引入均欧氏距离作为启发信息,提出了一种基于均欧氏距离的决策树优化算法,通过理论分析,该算法可以有效的克服多值偏向问题。
　　 (3)以决策树算法演示软件作为实验平台,将上述方法应用于其中,分析各个算法的优劣和各类参数的性能比较,并提出可以进一步改进实验效果的若干思想。
　　 (4)以Deep Web为应用平台,将改进的决策树优化算法应用于Deep Web查询接口发现中,改善了过去查询接口发现中分类准确率较低,时间开销较大的问题。