决策树算法总结
一、什么是决策树
决策树是一类常见的机器学习方法，通过历史数据得到的树结构模型对新数据进行分类决策。
决策树是一种基于实例的归纳学习方法，它能从给定的无序的训练样本中，提炼出树形的分类模型。
树中的每个非叶子节点记录了使用哪个特征来进行类别的判断，每个叶子节点则代表了最后判断的类别。根节点到每个叶子节点均形成一条分类的路径规则。
每次判断都是对某个属性的测试，每次判断都会缩小考虑的范围。
一棵决策树包含一个根节点、若干个内部结点和若干个叶节点；叶节点对应于决策结果，其他每个节点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点；
根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判断测试序列。
决策树的生成是一个递归的过程，有三种情形不会再分类：
当前节点包含的样本全属于同一类别
当前属性集为空
当前节点的样本集合为空
对于第二种情形，其类别设定为结点所含样本最多的类别。对于第三种情形，将其类别设定为其父节点所含样本最多的类别
二、常见决策树分类算法
1、CLS算法：是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。
2、ID3算法：对CLS算法的最大改进是摒弃了属性选择的随机性，利用信息熵的下降速度作为属性选择的度量。ID3是一种基于信息熵的决策树分类学习算法，以信息增益和信息熵，作为对象分类的衡量标准。
ID3算法结构简单、学习能力强、分类速度快适合大规模数据分类。但同时由于信息增益的不稳定性，容易倾向于众数属性导致过度拟合，算法抗干扰能力差。
ID3算法缺点：倾向于选择那些属性取值比较多的属性，在实际的应用中往往取值比较多的属性对分类没有太大价值、不能对连续属性进行处理、对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。
3、C4.5算法：基于ID3算法的改进，主要包括：使用信息增益率替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理，提升了算法的普适性。
三、决策树特征选择准则
1 信息增益
“信息熵”是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第K类样本所占的比例为PK，则D的信息熵定义为
信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大
ID3决策树学习算法就是以信息增益为准则来选择划分属性的。
2 信息增益率
实际上信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响。使用信息增益率来选择最优划分属性。
C4.5算法常使用信息增益率来选择最优属性划分
3 基尼指数
CART决策树使用“基尼指数”来选择划分属性，
数据集D的纯度可用基尼值来度量：
Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。故其值越小越好。数据集D的纯度越高。
属性a的基尼指数定义为
于是，我们在候选属性集合A中，选择哪个使得划分后基尼指数最小的属性作为最优划分属性。
4 剪枝处理
剪枝是决策树学习算法对付“过拟合”的主要手段。剪枝的基本策略有“预剪枝”和“后剪枝”。
预剪枝是指在决策树生成过程中，对每个结点在划分前进行估计，若当前节点的划分不能带来决策树泛化能力提升，则停止划分并将当前节点标记为叶节点。
后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化能力提升，则将该节点替换为叶节点。
5 连续与缺失值
5.1 连续值处理
将该节点上的所有样本按照属性的取值有小到大排序，在两个值之间去平均值，依次将所有平均值作为分割点，分别计算他们的信息增益率，将值最大的那个作为最优分割点。
5.2 缺失值的处理
处理过程如下
四、sklearn参数
criterion：gini或者entropy,前者是基尼系数，后者是信息熵。两种算法差异不大对准确率无影响，信息墒运算效率低一点，
因为它有对数运算.一般说使用默认的基尼系数”gini”就可以了，即CART算法。除非你更喜欢类似ID3, C4.5的最优特征选择方法。
splitter： best or random 前者是在所有特征中找最好的切分点 后者是在部分特征中，默认的”best”适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐”random” 。
max_features：None（所有），log2，sqrt，N 特征小于50的时候一般使用所有的
max_depth：int or None, optional (default=None) 一般来说，数据少或者特征少的时候可以不管这个值。
如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。
常用的可以取值10-100之间。常用来解决过拟合
min_samples_split：如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分，
如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。
min_samples_leaf：这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝，
如果样本量不大，不需要管这个值，大些如10W可是尝试下5
min_weight_fraction_leaf： 这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝默认是0，就是不考虑权重问题。
一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。
max_leaf_nodes： 通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。
如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制具体的值可以通过交叉验证得到。
class_weight： 指定样本各类别的的权重，主要是为了防止训练集某些类别的样本过多导致训练的决策树过于偏向这些类别。这里可以自己指定各个样本的权重，
如果使用“balanced”，则算法会自己计算权重，样本量少的类别所对应的样本权重会高。
min_impurity_split： 这个值限制了决策树的增长，如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值则该节点不再生成子节点。
即为叶子节点 。
