机器学习 | 决策树算法

可以是树的深度达到预定值，节点包含的样本数小于某一阈值，或者节点的基尼系数或信息增益低于某一阈值。：通过根据数据特征不断分割数据集，将数据划分成具有相似特征的子集，从而实现分类或回归的目标。抽取作为特征值的属性，再计算以不同属性值作为特征值时的信息熵，找到最优数据划分时对应的属性值。：是决策树的最末端节点，表示数据的最终分类或回归值。：当停止条件满足时，将叶子节点分配给一个类别标签，即决策树的叶子

Li.879

420人浏览 · 2023-11-06 20:20:36

Li.879 · 2023-11-06 20:20:36 发布

1. 信息熵（Information Entropy）

2. 信息增益（Information gain）

一、决策树

1.1 基本概念

决策树是一种用于分类与回归问题的监督学习方法。决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。核心思想：通过根据数据特征不断分割数据集，将数据划分成具有相似特征的子集，从而实现分类或回归的目标。决策树用于在每个内部节点上根据一些属性值进行决策，最终到达叶子节点，给出一个分类或回归的结果。每个内部节点表示一个属性测试，每个分支代表一个测试结果，而每个叶子节点代表一种类别。

特征测试：在每个内部节点，决策树根据某个特征的值将数据集分成两个或多个子集。这个特征测试的目标是选择能够最好地将数据划分为不同类别或值的特征。

内部节点：表示一个特征或属性。

叶子节点：是决策树的最末端节点，表示数据的最终分类或回归值。每个叶子节点包含一个类别标签或一个数值。

决策路径：从根节点到叶子节点的路径构成了一个决策路径，它代表了对数据的一系列特征测试和决策。

决策规则：决策树可以转化为一组简单的决策规则，这些规则对于新的数据点可以用来进行分类或回归预测。

1.2 基本流程

1）数据收集：收集包含特征和目标变量的训练数据集。特征用于做出决策的属性，目标变量是要预测或分类的值。

2）特征选择：选择一个用于构建决策树的特征，这个特征将成为根节点。

3）数据分裂：使用所选的特征将数据集分成多个子集，每个子集包含具有相似特征值的数据点。

4）递归构建子树：对于每个子集，重复特征选择和数据分裂的步骤，直到满足停止条件。停止条件可以是树的深度达到预定值，节点包含的样本数小于某一阈值，或者节点的基尼系数或信息增益低于某一阈值。在每次分裂后，生成新的节点并继续构建子树。

5）叶子节点赋值：当停止条件满足时，将叶子节点分配给一个类别标签，即决策树的叶子节点，表示最终的决策结果。

6）剪枝：为了避免过拟合，可以对构建好的树进行剪枝，即删除一些子树或节点，以提高模型的泛化能力，同时减少时间复杂度和空间复杂度。

二、如何进行属性划分

1. 信息熵（Information Entropy）

信息熵是决策树中用来度量数据不纯度的指标
假定当前样本集合D中第k类样本所占的比例为pk ( k = 1 , 2 , . . . , ∣ y ∣)，则D的信息熵定义为

若p = 0，则plog2p=0

Ent(D)的值越小，则D的纯度越高。Ent(D)的最小值为0，最大值为log2|y|。

2. 信息增益（Information gain）

信息增益是决策树中用来选择最佳属性进行分割的指标。

假定离散属性a有V个可能的取值{ a1, a2, ..., aV}，若使用a来对样本集D进行划分，则会产生V VV个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为 $a^{V}$ 的样本，即 $D^{V}$ 。

$Gain(D,a) = Ent(D) - \sum_{v=1}^{V} \frac{\left |D^{v} \right |}{\left |D\right |} Ent(D^{v})$

信息增益越大，使用属性a对样本集D进行划分所获得的纯度提升越大。

信息增益对可取值数目较多的属性有偏好。

3. 增益率（Gain Ratio）

增益率是信息增益的一种改进版本，它考虑了属性取值的多样性。

$Gain_-ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$

IV(a)称为属性a的固有值，属性a的可能取值数目越多（即V越大），则IV(a)的值通常就越大

$IV(a)=-\sum_{v=1}^{V}\frac{\left | D^{v} \right |}{\left | D \right |}log_{2}\frac{\left | D^{v} \right |}{\left | D \right |}$

增益率的优点是能够减少对取值多的属性的偏好，使决策树更加平衡。

4. 基尼指数

基尼系数是用于度量数据不纯度的另一种指标。

假设D有K个类，样本点属于第k类的概率为𝑝𝑘，则概率分布的基尼值为：

$Gini(D) = \sum_{k=1}^{K} p_{k}(1- p_{k})=1-\sum_{k=1}^{K} p_{k}^{2}$

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

三、剪枝处理

1. 预剪枝

预剪枝：在树的构建过程中，在每个内部节点处，考虑是否要停止继续分裂，通常通过限制树的最大深度、最小样本数或最小信息增益来实现。若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

优点：降低过拟合风险，减少训练和测试的时间开销。

缺点：有欠拟合的风险——有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能显著提高性能。例如：在判断好瓜坏瓜例子中，若特征值为凹陷，对该分支计算精度，判断是否继续划分。若划分前后精度下降或不变，根据预剪枝方法需停止对凹陷这一分支分裂。但如果在特征值为凹陷的基础上继续进行分裂，其精度可能会显著提高。

2. 后剪枝

后剪枝：首先构建一棵完整的决策树，然后通过自底向上地对非叶子结点进行考察，剪掉一些分支来减小树的复杂度，通常通过交叉验证来确定哪些分支可以剪掉。若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

优点：欠拟合风险小，泛化能力优于预剪枝

缺点：训练时间开销大，需生成完全决策树后再进行计算。

四、实例及代码

以实现预测隐形眼镜类型为例。

计算信息增益构建决策树模型

1. 读取数据集

读取lenses.txt文件中的数据，数据集包含以下属性值：

age：患者的年龄

prescription：视力矫正类型

astigmatic：是否散光

tear_rate：眼泪生产率

标签代表隐形眼镜的类型：

no lenses：视力良好，不需要隐形眼镜

soft：需要软质隐形眼镜

hard：需要硬质隐形眼镜

# 读取lenses.txt文件并设置列名
data = pd.read_csv("lenses.txt", sep="\t", header=None)
data.columns = ["age", "prescription", "astigmatic", "tear_rate", "class"]

2. 构造决策树

信息增益

# 计算数据集的香农熵
def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:     # 为所有可能分类创建字典
        currentLabel = featVec[-1]  # 取数据集的标签
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0           # 分类标签值初始化
        labelCounts[currentLabel] += 1  # 给标签赋值
    shannonEnt = 0.0                    # 熵初始化
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries    # 求得每个标签的概率    # L(Xi) = -log2P(Xi)
        shannonEnt -= prob * log(prob, 2)   # 以2为底求对数   # H = - Σi=1 n  P(Xi)*log2P(Xi)       
    return shannonEnt

信息熵越高，混合的数据越多，通过信息熵划分数据集。

抽取作为特征值的属性，再计算以不同属性值作为特征值时的信息熵，找到最优数据划分时对应的属性值。

# 输入参数分别是：待划分的数据集、划分数据集的特征，需要返回的特征的值
def splitDataSet(dataSet, axis, value):
    retDataSet = [] # 创建新的list对象
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis] # 获取关键特征前面的属性
            reducedFeatVec.extend(featVec[axis + 1 :]) # 填加关键特征后面的属性
            retDataSet.append(reducedFeatVec) # 以上步骤相当于对特征值进行抽取
    return retDataSet # 返回抽取特征后的数据集

# 选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1 #获取每个数据集拥有几个特征（排除最后一个）
    beseEntropy = calcShannonEnt(dataSet) # 计算以最后一个数值为特征的香农熵
    bestInfoGain = 0.0;
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        # 将dataSet中的数据先按行依次放入example中，然后取得example中的example[i]元素，放入列表featList中
        uniqueVals = set(featList) # set() 函数创建一个无序不重复元素集
        newEntropy = 0.0
        for value in uniqueVals: # 计算每种划分方式的信息熵
            subDataSet = splitDataSet(dataSet, i, value) # 按照给定特征划分数据集
            prob = len(subDataSet) / float(len(dataSet)) # 计算当前结果的可能性
            newEntropy += prob * calcShannonEnt(subDataSet) # 不同可能性的香农熵的和
        infoGain = beseEntropy - newEntropy
        if(infoGain > bestInfoGain): # 判断是否是当前最小香农熵，计算出最好的信息增益
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

统计出现次数最多的标签并递归构建决策树

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


#递归构建决策树 
def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList):  # ["yes","yes"]
        return classList[0]     # 结束划分 如果只有一种分类属性  属性标签重复
    if len(dataSet[0]) == 1:    # 结束划分 如果没有更多的特征了  都为同一类属性标签了
        return majorityCnt(classList)   # 计数排序 取最大数特征
    bestFeat = chooseBestFeatureToSplit(dataSet)    # 获取最优特征索引
    bestFeatLabel = labels[bestFeat]                # 获取最优特征属性标签
    myTree = {bestFeatLabel: {}}                    # 决策树初始化 嵌套字典
    # print("0tree", myTree)
    del(labels[bestFeat])                           # 删除已经使用的特征标签 这时应只剩下有脚蹼特征了
    featValues = [example[bestFeat] for example in dataSet]     # 取出数据集所有最优属性值
    uniqueVals = set(featValues)                                # 去重
    # 开始构建决策树
    for value in uniqueVals:
        subLabels = labels[:]   # 得到剩下的所有特征标签 作为我们的子节点可用
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

利用sklearn函数构建决策树模型

1）数据处理

import pandas as pd
 
# 读取lenses.txt文件并设置列名
data = pd.read_csv("lenses.txt", sep="\t", header=None)
data.columns = ["age", "prescription", "astigmatic", "tear_rate", "class"]
 
# 将类别特征转换为数值
data = data.apply(lambda x: pd.Categorical(x).codes if x.dtype == "object" else x)
 
# 转换特征列名为字符串
data.columns = data.columns.astype(str)
 
# 分割数据为特征和目标
X = data.drop("class", axis=1)
y = data["class"]

2）划分训练集和测试集

from sklearn.model_selection import train_test_split
 
# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

3）构建决策树并训练预测模型

from sklearn.tree import DecisionTreeClassifier
 
# 创建决策树模型
model = DecisionTreeClassifier()
# 训练模型
model.fit(X_train, y_train)

# 预测
y_pred = model.predict(X_test)

4）可视化决策树

from sklearn.tree import export_graphviz
import graphviz
 
# 可视化决策树
dot_data = export_graphviz(
    model,
    out_file=None,
    feature_names=data.columns[:-1],
    class_names=data["class"].unique().astype(str),
    filled=True,
    rounded=True,
    special_characters=True,
)
 
graph = graphviz.Source(dot_data)

# 将可视化图形保存为文件
graph.render("lenses_decision_tree")

测试结果：

将生成的 lenses_decision_tree.dot文件，并转为png类型文件，得到如下图所示决策树：