决策树算法思考总结

小新护肤

决策树是一类常见的机器学习方法，通过历史数据得到的树结构模型对新数据进行分类决策。

决策树是一种基于实例的归纳学习方法，它能从给定的无序的训练样本中，提炼出树形的分类模型。树中的每个非叶子节点记录了使用哪个特征来进行类别的判断，每个叶子节点则代表了最后判断的类别。根节点到每个叶子节点均形成一条分类的路径规则。

每次判断都是对某个属性的测试，每次判断都会缩小考虑的范围。

一棵决策树包含一个根节点、若干个内部结点和若干个叶节点；叶节点对应于决策结果，其他

每个节点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点；

根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判断测试序列。

决策树的生成是一个递归的过程。有三种情形不会再分类。

⑴当前节点包含的样本全属于同一类别。⑵当前属性集为空。⑶当前节点的样本集合为空。

对于第二种情形，其类别设定为结点所含样本最多的类别。对于第三种情形，将其类别设定为其父节点所含样本最多的类别。

常见决策树分类算法 ：

(1)、CLS算法：是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。

(2)、ID3算法：对CLS算法的最大改进是摒弃了属性选择的随机性，利用信息熵的下降速度作为属性选择的度量。ID3是一种基于信息熵的决策树分类学习算法，以信息增益和信息熵，作为对象分类的衡量标准。

ID3算法结构简单、学习能力强、分类速度快适合大规模数据分类。但同时由于信息增益的不稳定性，容易倾向于众数属性导致过度拟合，算法抗干扰能力差。

ID3算法缺点：倾向于选择那些属性取值比较多的属性，在实际的应用中往往取值比较多的属性对分类没有太大价值、不 能对连续属性进行处理、 对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。

(3)、C4.5算法：基于ID3算法的改进，主要包括：使用信息增益率替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理，提升了算法的普适性。

1，信息增益

“信息熵”是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第K类样本所占的比例为PK，则D的信息熵定义为

ID3决策树学习算法就是以信息增益为准则来选择划分属性的。

2，信息增益率

实际上信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响。使用信息增益率来选择最优划分属性。

C4.5算法常使用信息增益率来选择最优属性划分

3，基尼指数

CART决策树使用“基尼指数”来选择划分属性，

数据集D的纯度可用基尼值来度量：

Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。故其值越小越好。数据集D的纯度越高。

属性a的基尼指数定义为

于是，我们在候选属性集合A中，选择哪个使得划分后基尼指数最小的属性作为最优划分属性。

4，剪枝处理

剪枝是决策树学习算法对付“过拟合”的主要手段。剪枝的基本策略有“预剪枝”和“后剪枝”。

预剪枝是指在决策树生成过程中，对每个结点在划分前进行估计，若当前节点的划分不能带来决策树泛化能力提升，则停止划分并将当前节点标记为叶节点。

后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化能力提升，则将该节点替换为叶节点。

5，连续与缺失值

5.1，连续值处理

将该节点上的所有样本按照属性的取值有小到大排序，在两个值之间去平均值，依次将所有平均值作为分割点，分别计算他们的信息增益率，将值最大的那个作为最优分割点。

4.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，就是不考虑权重问题。
                           一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。