决策树算法总结
目录
一、决策树算法思想
二、决策树学习本质
三、总结
一、决策树（decision tree）算法思想：
决策树是一种基本的分类与回归方法。本文主要讨论分类决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以看做是if-then的条件集合，也可以认为是定义在特征空间与类空间上的条件概率分布。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，内部结点表示一个特征或属性，叶结点表示一个类。（椭圆表示内部结点，方块表示叶结点）
decision tree
决策树与if-then规则的关系
决策树可以看做是多个if-then规则的集合。将决策树转换成if-then规则的过程是：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，且只被一条路径或一条规则所覆盖。这里的覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
决策树与条件概率分布的关系
决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布，就构成一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。
决策树模型的优点
决策树模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化原则建立决策树模型；预测时，对新的数据，利用决策树模型进行分类。
二、决策树学习本质：
决策树学习是从训练数据集中归纳一组分类规则、与训练数据集不相矛盾的决策树可能有多个，也可能一个没有。我们需要训练一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看决策树学习是训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该是不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。决策树的学习使用损失函数表示这一目标，通常的损失函数是正则化的极大似然函数。决策树的学习策略是以损失函数为目标函数的最小化。当损失函数确定后，决策树学习问题变为损失函数意义下选择最优决策树的问题。这一过程通常是一个递归选择最优特征，并根据特征对训练数据进行分割，使得对各个子数据集有一个最好分类的过程。这一过程对应着特征选择、决策树的生成、决策树的剪枝。
特征选择：在于选择对训练数据具有分类能力的特征，这样可以提高决策树的学习效率。
决策树的生成：根据不同特征作为根结点，划分不同子结点构成不同的决策树。
决策树的选择：哪种特征作为根结点的决策树信息增益值最大，作为最终的决策树（最佳分类特征）。
信息熵 ：在信息论与概率统计中，熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为P(X=) =
，i=1，2，3...n，则随机变量X的熵定义为
H(X) = — ，0 <= H(X) <= 1，熵越大，随机变量的不确定性就越大。
条件熵（Y|X）：表示在已知随机变量X的条件下随机变量Y的不确定性。
信息增益 ：表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
信息增益 = 信息熵(父结点熵 ) — 条件熵（子结点加权熵）
三、总结：
优点
1、可解释性高，能处理非线性的数据，不需要做数据归一化，对数据分布没有偏好。
2、可用于特征工程，特征选择。
3、可转化为规则引擎。
缺点
1、启发式生成，不是最优解。
2、容易过拟合。
3、微小的数据改变会改变整个数的形状。
4、对类别不平衡的数据不友好。
