焦树军 安志江

(河北华航通信技术有限公司 河北 石家庄 050031)

基于最大间隔的决策树归纳算法

焦树军 安志江

(河北华航通信技术有限公司 河北 石家庄 050031)

决策树归纳是归纳学习的一种。由于NP困难，寻找最优的决策树是不现实的，从而探索各种启发式算法去产生一个高精度的决策树变成了这类研究的焦点。考虑到支持向量机(SVM)的分类间隔与泛化能力的关系，可以使用SVM的最大间隔作为生成决策树的启发式信息，使得决策树有较强的泛化能力。本文针对实值型数据，提出了一种基于最大间隔的决策树归纳算法。实验结果表明了本文算法的有效性。

支持向量机；支持向量机反问题；间隔；决策树归纳

0 引言

决策树归纳是归纳学习中最实用最重要的学习和推理方法,由于构造最优的决策树问题已经被证明是NP完全问题[2,3,4],因此典型的决策树学习算法都是在完全假设空间的自顶向下的贪心搜索算法，但各搜索算法所采用的启发式有所不同。其中选用最小信息熵为启发式信息的ID3算法是一个典型代表，这种方法生成的决策树规模小且计算复杂度低，但其泛化能力(generalization)不佳。

统计学习理论(Statistical Learning Theory或SLT)是一种专门研究小样本情况下机器学习规律的理论，它是建立在一套较坚实的理论基础之上的,为解决有限样本学习问题提供了一个统一的框架。V.Vapnik等人从六、七十年代开始致力于此方面研究[5]，到九十年代中期,随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视[7,8]。……