机器学习实战二（决策树）

一. 决策树

1. 概念： 决策树学习是根据数据的属性采用树状结构建立的一种决策模型，可以用此模型解决分类和回归问题。常见的算法包括 CART(Classification And Regression Tree), ID3, C4.5等。
2. 优缺点

• 优点

• • 易于理解和解释，甚至比线性回归更直观；
• • 与人类做决策思考的思维习惯契合；
• • 模型可以通过树的形式进行可视化展示；
• • 可以直接处理非数值型数据，不需要进行哑变量的转化，甚至可以直接处理含缺失值的数据；

• 缺点：

• • 对于有大量数值型输入和输出的问题，决策树未必是一个好的选择；
• • 产生过拟合
• • 特别是当数值型变量之间存在许多错综复杂的关系，如金融数据分析；
• • 决定分类的因素取决于更多变量的复杂组合时；
• • 模型不够稳健，某一个节点的小小变化可能导致整个树会有很大的不同。

二. 决策树算法

1. 概念：决策树算法主要是指决策树进行创建中进行树分裂(划分数据集)的时候选取最优特征的算法，他的主要目的就是要选取一个特征能够将分开的数据集尽量的规整，也就是尽可能的纯. 最大的原则就是: ==将无序的数据变得更加有序==
2. 决策树学习算法主要由三部分构成:

• 特征选择
• 决策树生成
• 决策树的剪枝

三. 特征选择

1. 常用方法：

• 信息增益(information gain)
• 增益比率(gain ratio)
• 基尼不纯度(Gini impurity)

2. 代码实现

# 为所有可能的分类创建字典
def uniquecounts(rows):
    results = {}
    for row in rows:
        # 计数结果在最后一列
        r = row[len(row)-1]
        if r not in results:results[r] = 0
        results[r]+=1
    return results # 返回一个字典

# 熵
def entropy(rows):
    from math import log
    log2 = lambda x:log(x)/log(2)
    results = uniquecounts(rows)
    # 开始计算熵的值
    ent = 0.0
    for r in results.keys():
        p = float(results[r])/len(rows)
        # 以2为底求对数
        ent = ent - p*log2(p)
    return ent

四. 决策树的生成

1. 经典的实现算法：

• ID3算法
• C4.5算法
• CART算法

2. ID3的算法思想（依据信息增益进行特征选取和分裂）

• 从根节点开始，选择信息增益最大的特征作为结点的特征，并由该特征的不同取值构建子节点
• 对子节点递归地调用以上方法，构建决策树
• 直到所有特征的信息增益均很小或者没有特征可选时为止。

// 算法框架如下
class DecisionTree(object):
    def fit(self, X, y):
        # 依据输入样本生成决策树
        self.root = self._build_tree(X, y)

    def _build_tree(self, X, y, current_depth=0):
        #1. 选取最佳分割特征，生成左右节点
        #2. 针对左右节点递归生成子树
      
    def predict_value(self, x, tree=None):
        # 将输入样本传入决策树中，自顶向下进行判定
        # 到达叶子节点即为预测值

3. C4.5算法

• C4.5算法与ID3算法的区别主要在于它在生产决策树的过程中，使用==信息增益==比来进行特征选择。

4. CART算法

• CART假设决策树是一个二叉树，它通过递归地二分每个特征，将特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。
• CART算法中，对于回归树，采用的是平方误差最小化准则；对于分类树，采用基尼指数最小化准则。
• 平方误差最小化
• 基尼指数

五. 决策树的剪枝

1. 过拟合问题的解决方法：

• 当熵减少的数量小于某一个阈值时，就停止分支的创建。这是一种贪心算法。（限制Gain的阈值）
• 先创建完整的决策树，然后再尝试消除多余的节点，也就是采用减枝的方法。

六. 完整代码

1. 完整代码

• github决策树代码实践