NP-hard 问题,所以在实际应用中,决策树学习算法通常采用启发
式方法,近似求解这一问题。
决策树学习的算法通常是一个递归地选择最优特征,并根据该
特征对训练数据进行分割,使得各个子数据集有一个最好的分类的
过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。
第一步,构建根节点,将所有训练数据都放在根节点。选择一个最
优特征,按照这一特征将训练数据集分割成子集,使得各个子集有
一个在当前条件下最好的分类。如果这些子集已经能够被基本正确
分类,那么构建叶节点,并将这些子集分到所对应的叶节点中去;
如果还有子集不能被正确分类,那么就对这些子集选择新的最优特
征,继续对其进行分割,构建相应的节点。如此递归地进行下去,
直至所有训练数据子集都基本被正确分类,或者没有合适的特征为
止。最后每个子集都被分到叶节点上,即都有了明确的类别,这样
就完成了一棵决策树的构建。
上面方法构建的决策树可能对训练数据有很好的分类能力,但
对未知的测试数据却未必有好的分类效果,即可能发生过拟合。需
要对生成的树自下而上进行剪枝,让树变得更简单,从而具有很好
的泛化能力。具体来说,就是去掉过于细分的叶节点,使其回退到
父节点,甚至更高的节点,然后将父节点或更高的节点改为新的叶
节点。
如果特征数量很多,可以在决策树学习开始的时候,对特征进
行选择,只留下那些对训练数据有足够分类能力的特征。
决策树学习算法包括特征选择、决策树生成和决策树剪枝的过
程。决策树表示一个条件概率分布,因此深浅不同的决策树对应着
不同复杂度的概率模型。决策树生成对应着模型的局部选择,决策
树剪枝对应着模型的全局选择。决策树生成只考虑局部最优,相反,
经过了剪枝过程,得到的模型才有可能是全局最优的。
3.1.2 特征选择
特征选择的目的是选取对训练数据具有最好分类能力的特征,
这样可以提高决策树的学习效率。如果利用一个特征进行分类的结
果与随机分类的结果相比没有很大的差别,则称这个特征是没有分
类能力的。经验上扔掉这样的特征对决策树的精度影响不大。通常
进行特征选择的准则是信息增益或信息增益比。
评论0
最新资源