二叉决策树生成算法的VC维上界

摘要：

在统计学习理论中,尤其对于分类问题,VC维扮演着中心作用.大多数常用算法的VC维未知.该文计算了二叉决策树生成算法的VC维上界,获得了定理2,认为该上界随决策树的复杂度和节点可调参数个数的增大而提高.作为补充,还计算了单变量决策树非叶子节点的VC维上界,获得了定理3.为了评估定理2的数值结果,通过实验验证了有关的经验结论,发现它们在决策树复杂度较大时能够与实际符合.比较定理2和经验结论发现两者存在较大的数值差别但是变化趋势相同.探讨了产生差别的原因以及定理对实际应用的指导意义.

关键词：决策树、维、统计学习理论

所属期刊栏目：22

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2005-04-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：74-78,126