决策树算法

决策树方法最早产生于上世纪60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。

决策树算法：顾名思义，以二分类问题为例，即利用自变量构造一颗二叉树，将目标变量区分出来，所有决策树算法的关键点如下：

1.分裂属性的选择。即选择哪个自变量作为树叉，也就是在n个自变量中，优先选择哪个自变量进行分叉。而采用何种计算方式选择树叉，决定了决策树算法的类型，即ID3、c4.5、CART三种决策树算法选择树叉的方式是不一样的，后文详细描述。

2.树剪枝。即在构建树叉时，由于数据中的噪声和离群点，许多分支反映的是训练数据中的异常，而树剪枝则是处理这种过分拟合的数据问题，常用的剪枝方法为先剪枝和后剪枝。

决策树算法-ID3（一）

ID3算法大致思想描述：

对当前例子集合，计算属性的信息增益； 选择信息增益最大的属性Ai(关于信息增益后面会有详细叙述)；把在Ai处取值相同的例子归于同于子集，Ai取几个值就得几个子集；对依次对每种取值情况下的子集,递归调用建树算法，即返回a； 若子集只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处。

下面用一个例子看一下：

示例数据

计算过程：

计算

ID3树形状

决策树

ID3算法的优缺点

ID3的优点

不存在无解的危险；可以利用全部训练例的统计性质进行决策，从而抵抗噪音。

ID3的缺点

处理大型数据速度较慢，经常出现内存不足，不可以并行，不可以处理数值型数据；ID3（并行）和ID3（number）解决了后两个问题。只适用于非增量数据集，不适用于增量数据集，可能会收敛到局部最优解而非全局最优解，最佳分离属性容易选择属性值多一些的属性。

最近会介绍一些数据分析经典算法，感兴趣的同学关注一下一起学习哦！