机器学习之决策树

时间：2022-10-15 17:51:33

一、决策树基本介绍

Decision Tree

  1. 可以解决分类和回归问题
  2. 监督学习算法

二、决策树工作原理

从根开始，按照决策树的分类属性，从上往下，逐层划分。直到叶子节点，便能获得结果。所以决策树算法的核心在于如何构造一颗决策树？

最常见核心的决策树算法有三个——ID3、C4.5、CART

1. ID3

核心思想：以信息增益来度量特征选择，选择信息增益最大的特征进行分裂

机器学习之决策树
条件熵H(D|A)：已知A条件下的熵。A是训练集中除标签外的一个属性，即根据A属性的不同取值将原训练集D划分成若干子集(D1，D2，D3…)。条件熵是各子集所占比重×子集的信息熵 的加和得出。

条件给的越好，划分出子集的信息熵就越小(因为每个子集基本都是同一分类)，条件熵就越小，信息增益就越大。所以信息增益最大的属性即当前最好的属性。

计算示例

机器学习之决策树

缺点

  • ID3 没有剪枝策略，容易过拟合
  • 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
  • 只能用于处理离散分布的特征
  • 没有考虑缺失值。

2. C4.5

改进

  • 引入悲观剪枝策略进行后剪枝（用递归的方式从底往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉）
  • 引入信息增益率作为划分标准
  • 将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点
  • 对于缺失值的处理可以分为两个子问题： 1. 在特征值缺失的情况下进行划分特征的选择？ （即如何计算特征的信息增益率）2. 选定该划分特征，对于缺失该特征值的样本如何处理？ （即到底把这个样本划分到哪个结点里）
    • 针对问题一，C4.5 的做法是： 对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
    • 针对问题二，C4.5 的做法是： 将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。
      机器学习之决策树

缺点

  • 剪枝策略可以再优化；
  • C4.5 用的是多叉树，用二叉树效率更高；
  • C4.5 只能用于分类；
  • C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
  • C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

3. CART

分类标准是基尼系数，其他内容待进一步学习

机器学习之决策树

剪枝

机器学习之决策树

机器学习之决策树

1. 预剪枝

机器学习之决策树
预剪枝使得决策树的很多分支都没有“展开”，不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但可能导致欠拟合。

2. 后剪枝

机器学习之决策树
后剪枝通常比预剪枝决策树保留了更多的分支，欠拟合风险很小，泛化性能优于预剪枝。但要自底向上对非叶节点进行逐一考察，因此训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

三、手写决策树算法核心

# 构造决策树
def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]        # 所有分类的数组
    if classList.count(classList[0]) == len(classList):     # 所有标签都属于一个分类
        return classList[0]
    if len(dataSet[0]) == 1:        # 使用完了所有特征,仍不能将数据集划分成仅包含唯一类别的分组
        return majorityCnt(classList)  # 若所有属性都被考虑，仍无法划分标签，采用多数表决决定该叶子结点的分类
    bestFeat = chooseBestFeatureToSplit(dataSet)    # 选取信息增益最大的特征作为下一次分类的依据
    bestFeatLabel = labels[bestFeat]                # 选取特征对应的标签
    myTree = {bestFeatLabel:{}}     # 创建tree字典,紧跟现阶段最优特征,下一个特征位于第二个大括号内,循环递归
    del(labels[bestFeat])      # 使用过的特征从中删除
    featValues = [example[bestFeat] for example in dataSet]
    uniqueValues = set(featValues)
    for value in uniqueValues:
        subLabels = labels[:]   # 复制labels列表,避免每次调用createTree()函数将原始列表改变,因为有的调用在前有的调用在后
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)  # 循环递归生成树
    return myTree


# 使用决策树的分类函数
def classify(inputTree,featLabels,testVec):
    firstStr = list(inputTree.keys())[0]          # 第一个按照其分类的属性
    secondDict = inputTree[firstStr]        # 第一个属性下的节点字典,也就是子树
    featIndex = featLabels.index(firstStr)   # 将标签换为索引
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    if isinstance(valueOfFeat, dict):  # 如果还是个字典,说明没到叶子结点,继续递归
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else:  # 如果到达叶子结点,直接返回分类标签
        classLabel = valueOfFeat
    return classLabel

四、sklearn实现决策树算法

1. 分类问题

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier

iris = datasets.load_iris()  # 加载鸢尾花数据集
X = iris.data[:, 2:]         # 只取后两个维度特征
y = iris.target

dt_clf = DecisionTreeClassifier(max_depth=2, criterion="entropy")  # 最大深度2,使用信息熵作为划分标准
dt_clf.fit(X, y)

"""
    sklearn的决策树实现: CART算法
    DecisionTreeClassifier部分参数(默认值)
    
    criterion='gini': 划分标准.默认gini,也可以改成entropy等
    max_depth=2: 限制整棵树的最大深度.越大越容易过拟合
    max_leaf_nodes=None: 最多有几个叶子结点.越大越容易归你和
    min_samples_leaf=1: 对于一个叶子结点,最少应该有几个样本.越小越容易过拟合
    min_samples_split=2: 对于一个节点,至少有多少个样本数据,才继续拆分.越小越容易过拟合
"""


# 绘制决策边界
def plot_decision_boundary(model, axis):
    x0, x1 = np.meshgrid(
        np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
        np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1),
    )
    X_new = np.c_[x0.ravel(), x1.ravel()]

    y_predict = model.predict(X_new)
    zz = y_predict.reshape(x0.shape)

    from matplotlib.colors import ListedColormap
    custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])

    plt.contourf(x0, x1, zz, cmap=custom_cmap)


plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
plt.scatter(X[y==0,0], X[y==0,1])
plt.scatter(X[y==1,0], X[y==1,1])
plt.scatter(X[y==2,0], X[y==2,1])
plt.show()

DecisionTreeClassifier()构造函数部分参数及默认值

clf = KNeighborsClassifier(n_neighbors=5,weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, 
metric=’minkowski’,metric_params=None, n_jobs=1, **kwargs)
  1. criterion='gini': 划分标准.默认gini,也可以改成entropy等
  2. max_depth=2: 限制整棵树的最大深度.越大越容易过拟合
  3. max_leaf_nodes=None: 最多有几个叶子结点.越大越容易归你和
  4. min_samples_leaf=1: 对于一个叶子结点,最少应该有几个样本.越小越容易过拟合
  5. min_samples_split=2: 对于一个节点,至少有多少个样本数据,才继续拆分.越小越容易过拟合

2. 回归问题

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

boston = datasets.load_boston()
X = boston.data
y = boston.target
from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=666)

# Decision Tree Regressor
from sklearn.tree import DecisionTreeRegressor

dt_reg = DecisionTreeRegressor()
dt_reg.fit(X_train, y_train)

dt_reg.score(X_test, y_test)
# 0.58605479243964098
dt_reg.score(X_train, y_train)
# 1.0

总结

优缺点

1. 优点

  • 计算复杂度不高，输出结果易于理解，可解释性强
  • 对中间值的缺失不敏感
  • 可以处理不相关特征和数据

2. 缺点

  • 可能会产生过拟合的问题
  • 适用数据类型：数值型和标称型(是或否)

问题

  1. 书上提到：“预剪枝显著减少了决策树的训练时间开销和测试时间开销‘”。以西瓜的例子来讲，预剪枝需要在验证集计算如果不再以当前属性划分，验证集的精度是多少；如果以当前属性划分，验证集的精度是多少；然后通过两个精度对比，决定是否继续划分。这不是增加了训练时间吗？本来只需要直接划分就好了。是因为如果当前节点不再划分，就没有后续子节点了，所以树的深度小了，所以训练时间开销降低吗？
标签：

相关文章