因为什么原因才引出来的决策树概念？？？

        人在做决策时，通常是这么思考的：如果A成立就继续看B，如果B成立就继续看C，最终得出结论。这个思维其实就是一棵“人脑中的决策树”。那问题来了，机器能不能也像人一样一步步判断？能不能将这个思维方式"程序化"？因此就引出了“决策树”的概念。决策树就是对这种“人类决策逻辑”的数学化表达。

决策树

        决策树(Decision Tree)是一种常见的机器学习算法和数据分析算法，它用类似“树状结构”的方式来做决策或者分类。可以把它理解成一连串“如果……那么……”的问题。

        核心思想：不断提问，把数据一步步地“分干净”。

        本质：通过一系列的“特征划分，让同一类的数据越来越纯”。

        决策树的结构：

                                

        组成：根节点（开始）；内部节点（判断条件）；叶子节点（最终分类结果）。

        那此时就有一个核心的问题了，怎么选出最好的划分呢？

       这就引入了新的概念：信息熵

信息熵（Entropy）——混乱程度【衡量数据“乱不乱”】

        公式：

        （D：数据集；pi：第i类的概率；k：类别数量）

        怎么理解信息熵呢？

                咱们以【西瓜数据集】为例：

                假设现在有50%的好瓜，50%的坏瓜，此时的信息熵最大，数据最混乱；

                假设现在有100%好瓜，0%的坏瓜，此时的信息熵等于零，数据最纯。

·        那么又有问题了，数据是纯了，但是西瓜可不止一个特征，那用那个特征用来分数据最好？

信息增益（Information Gain）——ID3

        定义：就是划分前的不确定性减去划分后的不确定性。

        公式：       看公式就可以看出，公式里是包含信息熵的。

        （A：某个特征；Dv：按特征A取值划分后的子集；|Dv| / |D|：权重）

        怎么理解信息增益？

                就是这个特征能不能让数据“更纯”？如果切完之后每一堆数据都很纯，那它就是好特征；如果切完发现数据还是很混乱，那它就是差特征。

        但很快就发现了一个严重的问题，信息增益有偏好！！！它特别喜欢取值很多的特征，比如ID号，为什么偏好ID号？因为ID号每个样本都是单独一类，它的信息熵为0，信息增益极大。这种划分就是“无意义的过拟合”。

        那么就引入了新的概念：信息增益率

信息增益率（Gain Raatio）——C4.5

        信息增益率是做什么的？？？为什么会出现信息增益率？？？

                信息增益率就是在考虑怎么惩罚“胡乱分裂”的特征。它是为了解决信息增益率的缺点。

        核心思想就是刚刚说的对“胡乱分裂”的特征进行惩罚。

        公式：        

        本质改进就是加了一个“惩罚项”；分得越碎，IV越大，比值就越小。

        怎么理解信息增益率？？？

                信息增益：只看“分得好不好”，其他的都不管；

                而信息增益率：既看“分得好不好”，也看“是不是乱划分的”。

        举个例子：

                还是我们的“ID号”，我们上面判断了信息增益率“很高很高”，但是呢划分的太碎了，每个ID号都是一类，信息增益率做的事情就是把信息增益率的值给压下来。

        特点：抑制多值特征，更合理。

        不出问题的话又要出问题了，又出现了新的问题：它的计算太过于复杂了（有log），求完信息熵，求信息增益，才能求信息增益率，一环套一环；对于大数据量很慢。那有没有更简单、更快的“纯度指标”呢？？有的有的——基尼指数。

基尼指数（Gini）——CART

        为什么选择基尼指数呢？因为他没有log，计算很快；数学公式简单，并且效果更接近熵。

        公式：

        怎么理解基尼指数？

                “随机选择一个样本，被分错的概率”。

        举个例子：

                假设100%好瓜，那它的基尼指数=0；

                假设50%好瓜，50%坏瓜，此时的基尼指数最大。

        特点：计算简单，要比熵快；效果更接近信息增益；还有就是在Sklearn中它是默认使用基尼指数的，要用信息增益需要手动修改。信息增益率（C4.5）在sklearn中没有实现。

from sklearn.tree import DecisionTreeClassifier
DecisionTreeClassifier(criterion="gini")        #默认
DecisionTreeClassifier(criterion="entropy")     #信息增益

三者的区别

        信息增益：只看“分完的数据有没有更纯”；

        信息增益率：防止“信息增益乱切分作弊”；

        基尼指数：直接衡量“分类错误的概率”。

总结

        通过选择最优特征（信息增益 / Gini），递归划分数据，使每个子集尽可能纯，从而完成分类或回归任务。

决策树的优缺点

        优点：可解释性强（像规则）；不需要数据归一化；能处理非线性。

        缺点：容易过拟合（重点）；对数据波动敏感；单棵树效果很一般（因为这个原因才引出的随机森林、GBDT等）。

就是因为决策树的致命问题，太容易过拟合了，虽然树越长，训练集越准，但是测试机会变差。

那怎么解决这个问题呢？？？——剪枝【预剪枝、后剪枝】

预剪枝（Pre-Pruning）

        思想：在树“生长之前”就限制它，不让它长得太复杂了。

        决策逻辑：在每一次准备划分时，先问一个问题:“这次划分是否有意义？”如果”提升的不明显“或”数据太少“，直接不往下继续划分。

        流程：

                1.从根节点开始，开始划分；

                2.判断：”划分后是否提升性能（验证集）“，是否满足阈值；

                3.如果不满足，停止分裂（变成叶子节点）；

                4.递归继续。

        本质：预剪枝就是用参数限制树的生长。

        预剪枝的优缺点：

                优点：防止过拟合；节省计算；简单易实现。

                缺点：容易欠拟合；难以选择最佳的停止条件；可能会错过更重要的深层模式（有些规则需要更深层才能体现）。

        预剪枝在sklearn的表示：

from sklearn.tree import DecisionTreeClassifiter
model = DecisionTreeClassifier(
            max_depth = 3,            #最大深度（最重要）
            min_samples_split = 10,   #至少有10个样本才允许分裂
            min_samples_leaf = 5,     #叶子节点至少有五个样本
            max_leaf_nodes = 20       #最大叶子点数
)

后剪枝（Post-Pruning）

        核心思想：先让树长满，然后在剪掉没用的分支。

        流程：

                1.先生成一颗“完整树”（过拟合也无所谓）；

                2.从叶子节点开始往上看；

                3.判断：“删掉这个子树效果会不会更好？”

                4.如果更好：直接剪掉（变成叶子节点）；

                5.继续向上剪枝。

        判断标准：通常用验证集准确率，损失函数。

        本质：后剪枝就是先过拟合再优化。

        后剪枝的优缺点：

                优点：泛化能力强；更接近最优树；对阈值选择不敏感。

                缺点：计算量大；实现太复杂；可能会剪掉一些小模式（过度剪枝会丢失少量有用的规则）。

        预剪枝和后剪枝简单总结：

                预剪枝：提前“拦截”过深的分裂，速度快，但是可能欠拟合；

                后剪枝：先让树自由生长，再进行修剪，速度慢，但是泛化好。