决策树是什么
决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3,C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。
决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
分类树（决策树）是一种十分常用的分类方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。
信息熵与最优划分
1）决策树算法的思想
解决分类问题时，决策树算法的任务是构造决策树模型，对未知的样本进行分类；
决策树算法利用了信息熵和决策树思维：
信息熵越小的数据集，样本的确定性越高，当数据集的信息熵为 0 时，该数据集中只有一种类型的样本；
训练数据集中有很多类型的样本，通过对数据集信息熵的判断，逐层划分数据集，最终将每一类样本单独划分出来；
划分数据集的方式有很多种，只有当按样本类别划分数据集时（也就是两部分数据集中不会同时存在相同类型的样本），划分后的两部分数据集的整体的信息熵最小；反相推断，当两部分数据集的整体的信息熵最小时，则两部分数据集中不会同时存在相同类型的样本；
2）划分步骤
划分点：某一特征的某一个数值；（根据该特征值对数据集样本进行划分）
数据集中样本的排序：根据特征的数值大小进行排序；
（一般不直接打乱原始数据集中样本的排列顺序，而是使用 np.argsorted( 特征向量 )，返回特征向量中元素排序后对应的 index）
选取划分点：要没有遗漏的迭代所有情况的划分点对应的划分情况；
将特征值排序后，从 0 号开始，选取相邻的但不相等的两个特征值的平均数作为一个划分点；按此方式迭代找出一组特质向量中的所有划分点；
3）划分结果
两种数据集：X_left、X_right 机器对应的 y；
特征类型，及其最优的划分点的特征值；
Cart生成算法：
最小二乘回归树生成算法
之所以称为最小二乘回归树，是因为，回归树以误差平方和为准则选择最优二分切点，该生成算法在训练数据集上所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域的输出值，在这里分为两种情况，一是输出值为子区域输出值的均值该种情况下为回归树，二是输出值为子区域输入与输出的线性回归，输出值为回归系数，该种情况下为模型树。
算法实现步骤：
1）选择最优切分特征J与切分点s，按照如下原则：
minj,s[minc1∑(yi−c1)+minc2∑(yi−c2)]minj,s[minc1∑(yi−c1)+minc2∑(yi−c2)]
c1,c2c1,c2分别为左右子区域输出的均值（模型树时是输出变量的回归值），可通过遍历每个变量的每个可能取值来切分数据集找出最优切分点。
2）用切分点划分区域并决定相应的输出值
3）递归调用1）2）直到满足停止条件
4）利用字典，递归调用创建二叉树，生成决策树
CART生成算法（分类树）
在这里需要提一下基尼系数：
在分类问题中，假设有KK类，样本点属于第kk类的概率为pkpk,则概率分布的基尼指数定义为：
Gini(p)=∑Kk=1pk(1−pk)=(p1+p2+...+pK)−∑Kk=1p2k=1−∑Kk=1p2kGini(p)=∑k=1Kpk(1−pk)=(p1+p2+...+pK)−∑k=1Kpk2=1−∑k=1Kpk2
对于分类问题：设CkCk为DD中属于第kk类的样本子集，则基尼指数为：
Gini(D)=1−∑Kk=1(|Ck||D|)2Gini(D)=1−∑k=1K(|Ck||D|)2
设条件AA将样本DD切分为D1D1和D2D2两个数据子集，则在条件AA下的样本DD的基尼指数为：
Gini(D,A)=|D1|DGini(D1)+|D2|DGini(D2)Gini(D,A)=|D1|DGini(D1)+|D2|DGini(D2)
注意：基尼指数也表示样本的不确定性，基尼指数值越大，样本集合的不确定性越大。
算法实现步骤：
1）计算现有样本DD的基尼指数，之后利用样本中每一个特征AA，及AA的每一个可能取值aa，根据A>=aA>=a与A<aA<a将样本分为两部分，并计算Gini(D,A)Gini(D,A)值
2）找出对应基尼指数最小Gini(D,A)Gini(D,A)的最优切分特征及取值，并判断是否切分停止条件，否，则输出最优切分点
3）递归调用1）2）
4）生成CART决策树
