机器学习ID3构造决策树

一、决策树简介

决策树是一种流行的机器学习方法，它采用树形结构来进行决策和预测。以下是关于决策树的介绍：

1. 基本概念：决策树通过从顶部至底部的递归分裂来形成树状结构。在这一过程中，每个内部节点（非叶节点）代表在一个特定属性上的测试，每个分支代表测试的一个结果，而每个叶节点则对应于一个预测结果或类别。
2. 算法种类：存在多种不同的决策树生成算法，如ID3、C4.5和C5.0等。这些算法在树的生成方式、处理数据缺失、剪枝策略等方面各有特点。
3. 分类与回归：虽然决策树通常用于分类问题，但它也可以应用于回归问题。在分类任务中，决策树模型根据输入特征对实例进行分类；而在回归任务中，它可以用来预测一个连续值。

二、信息熵和信息增益

2.1、信息熵

熵被用来衡量随机变量的不确定性或混乱程度。

熵的公式：

熵越高，随机变量的不确定性越大，熵越小，随机变量越稳定。当所有可能的状态等概率时，熵达到最大值。

2.2、信息增益

信息增益是ID3算法中用于选择最佳划分属性的标准。

信息增益的概念是基于信息熵的，它衡量的是在知道某个特定属性的信息之后，数据集不确定性减少的程度。具体来说，信息增益反映了在决策树的某个节点上，按照某个属性进行划分后，结果集的纯净程度提高了多少。以下是信息增益的具体解析：

• 信息熵：信息熵是度量数据集合纯度的一个指标，它表示随机变量不确定性的度量。
• 信息增益计算：信息增益是通过父节点的信息熵减去所有子节点加权信息熵的总和得到的。加权信息熵是指每个子节点的信息熵乘以该子节点样本数占父节点样本总数的比例。
• 属性选择：ID3算法会比较所有属性的信息增益，并选择信息增益最大的属性作为当前节点的划分属性。这样做的原因是信息增益大的属性能够最大限度地降低分类的不确定性，从而得到更好的分类效果。
• 决策树构建：通过递归地应用上述过程，ID3算法可以构建出一棵决策树，其中每个非叶节点都基于信息增益最大的属性来划分数据。

三、ID3、C4.5、C5.0

3.1、ID3

ID3算法的核心是信息增益，它基于信息熵的概念来选择特征进行数据的划分。

具体来说，ID3算法首先计算父节点的信息熵，然后按照每个特征进行划分，计算所有子节点的加权信息熵，最后用父节点的信息熵减去子节点的加权信息熵得到信息增益。这个过程可以形式化为以下步骤：

1. 计算父节点的信息熵：对于当前的数据集合，计算其信息熵，表示为 ，其中 𝑝(𝑥𝑖)p(xi​) 是第 𝑖i 类样本在数据集中的概率。
2. 计算特征的信息增益：对于每一个特征，计算如果按照这个特征划分数据后得到的子节点的加权信息熵，加权信息熵是指每个子节点的信息熵乘以一个权重，这个权重是子节点样本数占父节点样本数的比例。
3. 选择最大信息增益的特征：在所有特征中选择信息增益最大的一个作为当前节点的最优划分特征。
4. 递归构建决策树：对每个由最优特征划分出的子数据集，重复以上过程，直到满足停止条件（如所有样本属于同一类别或没有更多特征可用）。

3.2、C4.5

C4.5算法是一种决策树生成算法，它是ID3算法的改进版本。

C4.5算法在ID3算法的基础上进行了多方面的优化，具体如下：

1. 信息增益率：与ID3使用信息增益不同，C4.5采用信息增益率来选择划分属性。这种方法可以有效处理属性值分布不均匀的问题。
2. 连续属性处理：C4.5能够处理连续型属性，通过对连续属性进行离散化，将其分成多个区间，使得连续属性也能够用于决策树的构建。
3. 缺失值处理：C4.5提供了一种处理缺失值的方法，即在构造树的过程中，对于缺失值的处理是通过将它们分散到已有的分支上，而不是简单地忽略这些样本。
4. 剪枝策略：C4.5采用了悲观剪枝的策略，这是一种后剪枝方法，通过计算每个节点的误差来避免过度拟合，从而简化决策树的结构。
5. 适用性：C4.5适用于分类问题，它通过学习输入数据集的属性值与类别之间的关系，构建决策树模型，然后利用这个模型对新的未知类别的数据进行分类预测

3.3、C5.0

C5.0算法是在C4.5算法的基础上提出的改进版本，它是一种决策树算法，主要用于处理大量数据的数据集分析。

C5.0算法与C4.5算法的主要区别在于：

• 信息增益率：C5.0继续使用信息增益率来选择最佳分裂属性，这是对ID3中使用的信息增益的改进，可以更好地处理属性值分布不均匀的问题。
• 剪枝方法：C5.0的剪枝方法是通过减少树的深度来进行的，这有助于避免过拟合，使模型更加精简高效。
• 处理连续型属性：C5.0能够处理连续型属性，通过对连续属性进行离散化，将其分成多个区间，使得连续属性也能够用于决策树的构建。
• 自动选择分枝变量和分割点：C5.0算法能够自动选择最佳的分枝变量和分割点，这使得它在构建决策树时更加灵活和高效。

四、ID3构建决策树

4.1实例

有四个特征（天气、温度、湿度、有无风），和一个标签（是否出去玩）

这个是根据上图写出的数据

import math
# 定义数据集
def createDataSet():
    dataSet = [
        [0, 0, 0, 0, 'no'],
        [0, 0, 0, 1, 'no'],
        [0, 1, 0, 1, 'yes'],
        [0, 1, 1, 0, 'yes'],
        [0, 0, 0, 0, 'no'],
        [1, 0, 0, 0, 'no'],
        [1, 0, 0, 1, 'no'],
        [1, 1, 1, 1, 'yes'],
        [1, 0, 1, 2, 'yes'],
        [1, 0, 1, 2, 'yes'],
        [2, 0, 1, 2, 'yes'],
        [2, 0, 1, 1, 'yes'],
        [2, 1, 0, 1, 'yes'],
        [2, 1, 0, 2, 'yes'],
        [2, 0, 0, 0, 'no'],
    ]
    labels = ['1、AGE', '2、WORK', '3、HOME', '4、LOAN']  # 特征标签
    return dataSet, labels

这个函数是用来 统计样本数量

# 统计数据集中的样本数量
def getMaxLabelByDataSet(curLabelList, maxValuex=None):
    # 创建一个空字典，用于存储各个类别的样本数量
    classCount = {}
    # 初始化最大类别和样本数量的变量
    maxKey, maxValue = None, None
    # 遍历数据集中的每一个类别
    for label in curLabelList:
        # 如果该类别已经在字典中，增加其数量
        if label in classCount.keys():
            classCount[label] += 1
            # 如果指定了最大值，并且当前类别数量大于最大值，则更新最大值和对应的类别
            if maxValuex < classCount[label]:
                maxKey, maxValue = label, classCount[label]
        # 如果该类别不在字典中，将其加入字典，并初始化最大类别和样本数量
        else:
            classCount[label] = 1
            if maxKey is None:
                maxKey, maxValue = label, 1
    # 返回样本数量最多的类别
    return maxKey

这个函数是用来计算数据集的熵

# 计算数据集的熵
def calcEntropy(dataSet):
    # 获取数据集的样本数量
    exampleNum = len(dataSet)
    # 创建一个空字典，用于存储各个类别的样本数量
    labelCount = {}
    # 统计数据集中各个类别的样本数量
    for featVec in dataSet:
        curLabel = featVec[-1]  # 获取样本的类别
        if curLabel in labelCount.keys():
            labelCount[curLabel] += 1
        else:
            labelCount[curLabel] = 1
    entropy = 0  # 初始化熵的值为0
    # 计算数据集的熵
    for key, value in labelCount.items():
        p = labelCount[key] / exampleNum  # 计算每个类别在数据集中的占比
        curEntropy = -p * math.log(p, 2)  # 计算当前类别的信息熵
        entropy += curEntropy  # 累加信息熵
    return entropy  # 返回数据集的总信息熵

这个函数是用来选择最佳的划分特征

# 选择最佳的划分特征
def chooseBestFeatureToSplit(dataSet):
    # 获取特征的数量，即每个样本的特征维度减去类别所占的维度
    featureNum = len(dataSet[0]) - 1
    # 计算当前数据集的熵
    curEntropy = calcEntropy(dataSet)
    # 初始化最佳信息增益和最佳特征索引
    bestInfoGain = 0
    bestFeatureIndex = -1
    # 遍历每一个特征
    for i in range(featureNum):
        # 获取当前特征列的所有取值
        featList = [example[i] for example in dataSet]
        # 将取值转换为集合，以便去重
        uniqueVals = set(featList)
        newEntropy = 0
        # 遍历当前特征的每一个取值
        for val in uniqueVals:
            # 对当前特征的每个取值进行数据集的划分，并计算划分后的加权熵
            subDataSet = splitDataSet(dataSet, i, val)
            weight = len(subDataSet) / len(dataSet)
            newEntropy += (calcEntropy(subDataSet) * weight)
        # 计算信息增益
        infoGain = curEntropy - newEntropy
        # 更新最佳信息增益和对应的特征索引
        if bestInfoGain < infoGain:
            bestInfoGain = infoGain
            bestFeatureIndex = i
    # 返回最佳特征索引
    return bestFeatureIndex

这个函数是用来根据特征值划分数据集

# 根据特征值划分数据集
def splitDataSet(dataSet, featureIndex, value):
    returnDataSet = []  # 初始化划分后的数据集
    # 遍历数据集中的每一个样本
    for featVec in dataSet:
        # 如果当前样本的特征值等于给定的取值
        if featVec[featureIndex] == value:
            # 将当前样本中除去给定特征的部分加入到划分后的数据集中
            deleteFeatVec = featVec[:featureIndex]
            deleteFeatVec.extend(featVec[featureIndex + 1:])
            returnDataSet.append(deleteFeatVec)  # 将加工后的样本添加到划分后的数据集中
    return returnDataSet  # 返回划分后的数据集

这个函数是用来创建决策树

# 创建决策树
def createTreeNode(dataSet, labels, featLabels):
    curLabelList = [example[-1] for example in dataSet]
    # 如果数据集中所有样本都属于同一类别，则返回该类别
    if len(curLabelList) == curLabelList.count(curLabelList[0]):
        return curLabelList[0]
    # 如果剩余的特征集合为空，则返回样本中最多的类别
    if len(labels) == 1:
        return getMaxLabelByDataSet(curLabelList)
    # 选择最佳划分特征
    bestFeatIndex = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeatIndex]
    featLabels.append(bestFeatLabel)
    myTree = {bestFeatLabel: {}}
    del labels[bestFeatIndex]
    featValues = [example[bestFeatIndex] for example in dataSet]
    uniqueFeaValues = set(featValues)
    for value in uniqueFeaValues:
        myTree[bestFeatLabel][value] = createTreeNode(
            splitDataSet(dataSet, bestFeatIndex, value), labels.copy(),
            featLabels.copy())
    return myTree

运行代码

import math
# 定义数据集
def createDataSet():
    dataSet = [
        [0, 0, 0, 0, 'no'],
        [0, 0, 0, 1, 'no'],
        [0, 1, 0, 1, 'yes'],
        [0, 1, 1, 0, 'yes'],
        [0, 0, 0, 0, 'no'],
        [1, 0, 0, 0, 'no'],
        [1, 0, 0, 1, 'no'],
        [1, 1, 1, 1, 'yes'],
        [1, 0, 1, 2, 'yes'],
        [1, 0, 1, 2, 'yes'],
        [2, 0, 1, 2, 'yes'],
        [2, 0, 1, 1, 'yes'],
        [2, 1, 0, 1, 'yes'],
        [2, 1, 0, 2, 'yes'],
        [2, 0, 0, 0, 'no'],
    ]
    labels = ['1、AGE', '2、WORK', '3、HOME', '4、LOAN']  # 特征标签
    return dataSet, labels
# 统计数据集中某一类别的样本数量
def getMaxLabelByDataSet(curLabelList, maxValuex=None):
    # 创建一个空字典，用于存储各个类别的样本数量
    classCount = {}
    # 初始化最大类别和样本数量的变量
    maxKey, maxValue = None, None
    # 遍历数据集中的每一个类别
    for label in curLabelList:
        # 如果该类别已经在字典中，增加其数量
        if label in classCount.keys():
            classCount[label] += 1
            # 如果指定了最大值，并且当前类别数量大于最大值，则更新最大值和对应的类别
            if maxValuex < classCount[label]:
                maxKey, maxValue = label, classCount[label]
        # 如果该类别不在字典中，将其加入字典，并初始化最大类别和样本数量
        else:
            classCount[label] = 1
            if maxKey is None:
                maxKey, maxValue = label, 1
    # 返回样本数量最多的类别
    return maxKey
# 计算数据集的熵
def calcEntropy(dataSet):
    # 获取数据集的样本数量
    exampleNum = len(dataSet)
    # 创建一个空字典，用于存储各个类别的样本数量
    labelCount = {}
    # 统计数据集中各个类别的样本数量
    for featVec in dataSet:
        curLabel = featVec[-1]  # 获取样本的类别
        if curLabel in labelCount.keys():
            labelCount[curLabel] += 1
        else:
            labelCount[curLabel] = 1
    entropy = 0  # 初始化熵的值为0
    # 计算数据集的熵
    for key, value in labelCount.items():
        p = labelCount[key] / exampleNum  # 计算每个类别在数据集中的占比
        curEntropy = -p * math.log(p, 2)  # 计算当前类别的信息熵
        entropy += curEntropy  # 累加信息熵
    return entropy  # 返回数据集的总信息熵
# 选择最佳的划分特征
def chooseBestFeatureToSplit(dataSet):
    # 获取特征的数量，即每个样本的特征维度减去类别所占的维度
    featureNum = len(dataSet[0]) - 1
    # 计算当前数据集的熵
    curEntropy = calcEntropy(dataSet)
    # 初始化最佳信息增益和最佳特征索引
    bestInfoGain = 0
    bestFeatureIndex = -1
    # 遍历每一个特征
    for i in range(featureNum):
        # 获取当前特征列的所有取值
        featList = [example[i] for example in dataSet]
        # 将取值转换为集合，以便去重
        uniqueVals = set(featList)
        newEntropy = 0
        # 遍历当前特征的每一个取值
        for val in uniqueVals:
            # 对当前特征的每个取值进行数据集的划分，并计算划分后的加权熵
            subDataSet = splitDataSet(dataSet, i, val)
            weight = len(subDataSet) / len(dataSet)
            newEntropy += (calcEntropy(subDataSet) * weight)
        # 计算信息增益
        infoGain = curEntropy - newEntropy
        # 更新最佳信息增益和对应的特征索引
        if bestInfoGain < infoGain:
            bestInfoGain = infoGain
            bestFeatureIndex = i
    # 返回最佳特征索引
    return bestFeatureIndex
# 根据特征值划分数据集
def splitDataSet(dataSet, featureIndex, value):
    returnDataSet = []  # 初始化划分后的数据集
    # 遍历数据集中的每一个样本
    for featVec in dataSet:
        # 如果当前样本的特征值等于给定的取值
        if featVec[featureIndex] == value:
            # 将当前样本中除去给定特征的部分加入到划分后的数据集中
            deleteFeatVec = featVec[:featureIndex]
            deleteFeatVec.extend(featVec[featureIndex + 1:])
            returnDataSet.append(deleteFeatVec)  # 将加工后的样本添加到划分后的数据集中
    return returnDataSet  # 返回划分后的数据集
# 创建决策树
def createTreeNode(dataSet, labels, featLabels):
    curLabelList = [example[-1] for example in dataSet]
    # 如果数据集中所有样本都属于同一类别，则返回该类别
    if len(curLabelList) == curLabelList.count(curLabelList[0]):
        return curLabelList[0]
    # 如果剩余的特征集合为空，则返回样本中最多的类别
    if len(labels) == 1:
        return getMaxLabelByDataSet(curLabelList)
    # 选择最佳划分特征
    bestFeatIndex = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeatIndex]
    featLabels.append(bestFeatLabel)
    myTree = {bestFeatLabel: {}}
    del labels[bestFeatIndex]
    featValues = [example[bestFeatIndex] for example in dataSet]
    uniqueFeaValues = set(featValues)
    for value in uniqueFeaValues:
        myTree[bestFeatLabel][value] = createTreeNode(
            splitDataSet(dataSet, bestFeatIndex, value), labels.copy(),
            featLabels.copy())
    return myTree
# 测试
dataSet, labels = createDataSet()
myDecisionTree = createTreeNode(dataSet, labels, [])
print(myDecisionTree)

运行结果

五、ID3的优缺点

优点：

1. 易于理解和解释：决策树的结构直观，非专业人士也能理解其分类过程，这有助于提高模型的可接受度和信任度。
2. 处理多分类问题：ID3能够处理多分类问题，即它不仅适用于两类问题的分类，还能应对两个以上的类别划分。
3. 数据类型处理能力：尽管ID3本身设计用于处理离散型数据，但它也可以适应处理包含连续型数据的数据集。这意味着ID3可以应用于更广泛的实际问题中。
4. 避免过度拟合：通过剪枝技术，ID3算法可以在构建过程中避免生成过于复杂的树，从而防止过度拟合，提高模型的泛化能力。
5. 基于信息理论：ID3算法基于信息熵来选择属性，这是一个客观的标准，有助于减少在特征选择上的主观性。
6. 递归定义清晰：ID3算法采用递归的方式构建决策树，每个内部结点的选择都是基于最大化信息增益的原则，这使得决策树的构建过程具有明确的目标和方向。

缺点：

1. 偏好取值多的属性：信息增益准则对可取值数目较多的属性有所偏好，这可能导致决策树过于复杂，不利于模型的泛化。
2. 不能处理连续特征：ID3算法没有考虑连续特征，这意味着在面对如工资、长度等连续型数据时，ID3算法无法直接应用。
3. 对噪声数据敏感：ID3算法对噪声和异常值比较敏感，这可能导致生成的决策树不够准确。
4. 只能处理离散型数据：虽然决策树可以处理离散型和连续型数据，但ID3特定版本仅适用于处理离散型数据。
5. 容易产生过拟合：由于ID3算法倾向于创建复杂的树，因此可能会产生过拟合的问题，即模型在训练数据上表现良好，但在未见过的数据上表现不佳。
6. 不稳定性：数据集的微小变化可能会导致生成完全不同的决策树，这降低了模型的稳定性。
7. 不完整性：在某些情况下，如果某个类别的样本全部缺失，ID3算法可能会忽略这些样本，导致决策树不完整。