版权所有：内蒙古大学图书馆 技术提供：维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
二叉决策树生成算法的VC维上界
On Upper Bound of VC Dimension of Binary Decision Tree Algorithms作者机构：上海交通大学图象处理及模式识别研究所上海200030
出 版 物：《计算机仿真》 (Computer Simulation)
年 卷 期：2005年第22卷第2期
页 面：74-78,126页
学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
摘 要：在统计学习理论中 ,尤其对于分类问题 ,VC维扮演着中心作用。大多数常用算法的VC维未知。该文计算了二叉决策树生成算法的VC维上界 ,获得了定理 2 ,认为该上界随决策树的复杂度和节点可调参数个数的增大而提高。作为补充 ,还计算了单变量决策树非叶子节点的VC维上界 ,获得了定理 3。为了评估定理 2的数值结果 ,通过实验验证了有关的经验结论 ,发现它们在决策树复杂度较大时能够与实际符合。比较定理 2和经验结论发现两者存在较大的数值差别但是变化趋势相同。
