决策树

陈词滥调决策树。提到决策树，不能不说不纯度的概念。

• 回归不纯度
  

  i(N)=∑j(yj−rj)2
  
  其中，rj为该结点的预测值输出值，通常此处设为该节点所有值的均值，yj为真值。我们的目标是最小化该值。

• 分类不纯度
  熵不纯度： i(N)=∑jP(ωj)log(ωj)
  Gini不纯度：i(N)=∑j≠iP(wi)P(wj)=∑jP(wj)(1−P(wj))=1−∑jP(wj)2
  错分不纯度：i(N)=1−maxP(wj)

决策树是1个统称，其实它包括若干类，常见的种类有： ID3、C4.5 和CART,说说各自特点：
ID3: 1986 Ross Quinlan提出，采取 熵不纯度规则分裂节点，通常分支因子Bj>2，标准版本的ID3没有剪枝操作。
C4.5: 为ID3改进版本，特点值可以处理连续变量，采取信息熵增益比。
CART：分类回归树，与ID3和C4.5最重要的区分便是，其能处理回归问题，即数值预测。节点分裂准则采取Gini不纯度。（其实，现在的CART算法，不纯度模式是可选的）
　　由于CART的通用性，在1些机器学习库中实现的决策树绝大多数是CART树，如opencv 和sklearn中。有必要系统的学习1下。以下以opencv为原型学习。
　　根据特点属性和标签属性是数值型还是分类型，可将决策树分为4类：

• 特点为种别的分类树 ：find_split_cat_class（）
• 特点为数值的分类树：find_split_ord_class（）
• 特点为种别的回归树：find_split_cat_reg（）
• 特点为数值的回归树：find_split_ord_reg（）

详细讲授请参照博文：opencv 决策树源码分析 http://blog.csdn.net/zhaocj/article/details/50503450