目录

一、问题描述

二、算法实现

1. CART决策树

1.1 算法步骤

1.1.1 计算基尼指数

1.1.2 选择最优特征

1.1.3 划分数据集

1.1.4 递归构建决策树

1.2 实验源码

1.3 测试结果

2. ID3决策树

2.1 算法步骤

2.1.1 计算香农熵（经验熵）

2.1.2 按特征划分数据集

2.1.3 选择最优特征

2.1.4 递归构建决策树

2.2 实验源码

2.3 测试结果

三、实验总结

---

决策树（decision tree）：决策树是一种基于树结构的监督学习算法，用于分类和回归任务。它通过递归地将数据划分为不同的子集，每个分支代表一个决策规则，最终形成树状模型。在训练过程中，算法会选择最优的特征和分裂点，以最大化子集的纯度或最小化误差。

一、问题描述

实验数据包括四个属性特征：年龄段，是否有工作，是否有房屋，信贷情况，根据这四个属性特征来决定是否给予贷款。

训练集数据如下：

对数据集进行属性标注：

• 年龄：0代表青年，1代表中年，2代表老年；
• 有工作：0代表否，1代表是；
• 有自己的房子：0代表否，1代表是；
• 信贷情况：0代表一般，1代表好，2代表非常好；
• 类别(是否给贷款)：0代表否，1代表是。

测试集数据如下：

二、算法实现

1. CART决策树

CART分类树通过递归地划分数据集，每次选择一个最优特征来将数据集分成两个子集，直到满足停止条件。

1.1 算法步骤

1.1.1 计算基尼指数

CART 算法使用基尼指数（Gini Index）来选择最优特征。基尼指数衡量的是数据的不纯度，值越小表示数据越纯净（即类别越单一）。

• 基尼指数的计算公式：

  

   

  其中，pk​ 是第 k 类样本在数据集 D 中的比例。

• 条件基尼指数：

  

  其中，Di​ 是数据集 D 在特征 A 上取值为i的子集。

1.1.2 选择最优特征

在每次划分时，CART算法计算每个特征的基尼指数增益，并选择基尼指数增益最大的特征作为划分特征。

• 基尼指数增益：

  

   

  选择使Gain(D,A)最大的特征A。

1.1.3 划分数据集

根据选择的最优特征，将数据集划分为两个子集。CART算法是二叉树，每次划分将数据集分为两部分。

1.1.4 递归构建决策树

对每个子集递归地重复步骤2-4，直到满足停止条件：

• 所有样本属于同一类别。

• 没有更多的特征可以划分。

• 子集的大小小于某个阈值。

最终生成的决策树是一个二叉树，每个节点表示一个特征的划分，每个叶节点表示一个类别。

1.2 实验源码

import numpy as np
from numpy import *
from collections import Counter

# 划分子集：根据特征（axis）的属性值（value）划分数据集，并返回等于属性值（value）的子集。
# equal：返回值等于或不等于value的子集，该值进行控制
def splitdataset(dataset, axis, value, isequal):
    retdataset = []  # 定义一个用于存放子集的变量
    length = len(dataset)  # 元素个数获取，有几行
    if isequal:  # 判断是否相等
        for i in range(length):  # 遍历
            if dataset[i][axis] == value:  # 判断第一行的下标为axis的元素是不是等于value
                ret = dataset[i][:axis]  # 是的话就将该元素前的所有元素给一个临时变量ret
                ret.extend(dataset[i][axis + 1:])  # 并且给这个临时变量ret添加上axis之后的元素，相当于不要axis列
                retdataset.append(ret)  # 将新的一行元素添加到retdataset之中
    else:
        for i in range(length):
            if dataset[i][axis] != value:
                ret = dataset[i][:axis]
                ret.extend(dataset[i][axis + 1:])
                retdataset.append(ret)
    return retdataset  # 返回，这是一个部分，不是全部

# CART：根据基尼系数选择当前数据集的最优划分特征
def CART_chooseBestFeatureToSplit(dataset):
    numFeatures = len(dataset[0]) - 1  # 特征的数量4
    numrows = len(dataset)  # 行数，有多少个训练数据
    bestgini = 0  # 因为计算的增益，最后取增益最大的，所以这里初始为0
    bestFeature = -1  # 初始化最佳划分特征 -1
    array = mat(dataset)  # 在CART_gini中有说明
    giniloan = CART_gini(dataset)
    for i in range(numFeatures):  # 循环
        count = Counter(np.transpose(array[:, i]).tolist()[0])
        axisnum = len(count)
        for item in count:
            isDataItem = splitdataset(dataset, i, item, True)  # 取等于该元素的子集
            notDataItem = splitdataset(dataset, i, item, False)  # 取不等于等于该元素的字集，因为是二分，所以必须这么做
            isDataItemGini = CART_gini(isDataItem)  # 获取子集的基尼系数
            notDataItemGini = CART_gini(notDataItem)  # 同上。#下面语句为计算基尼指数增益的公式，去百度。
            gini = giniloan - int(count[item]) / numrows * isDataItemGini - (
                        numrows - int(count[item])) / numrows * notDataItemGini
            if gini > bestgini:  # 当增益出现新高度的时候，进行刷新
                bestgini = gini
                bestFeature = i
    return bestFeature  # 返回一个值，是一个int类型的准确的值

# 返回一个dataset的基尼系数(1-something)的形式
def CART_gini(dataset):
    gini = 0
    numrows = len(dataset)
    numFeatures = len(dataset[0]) - 1
    array = mat(dataset)  # 将列表转化为矩阵
    dic = Counter(np.transpose(array[:, numFeatures]).tolist()[0])  # 取矩阵的第numFeatures列，并转置成行，然后转化为列表，并放入字典dic之中，自动进行统计
    for item in dic:
        gini += (dic[item] / numrows) ** 2  # 与下一行一起，是用于计算基尼系数的(基尼系数与基尼指数是两个不同的概念)
    return 1 - gini

# CART决策树构建
def CART_createTree(dataset, labels):
    classList = [example[-1] for example in dataset]  # 取分类标签(是否放贷：1(yes) or 0(no))
    if classList.count(classList[0]) == len(classList):  # 如果类别完全相同，则停止继续划分
        return classList[0]

    bestFeat = CART_chooseBestFeatureToSplit(dataset)  # 选择最优特征
    bestFeatLabel = labels[bestFeat]  # 最优特征的标签
    CARTTree = {bestFeatLabel: {}}  # 根据最优特征的标签生成树
    del (labels[bestFeat])  # 删除已经使用的特征标签
    featValues = [example[bestFeat] for example in dataset]  # 得到训练集中所有最优特征的属性值
    uniqueVls = set(featValues)  # 去掉重复的属性值

    for value in uniqueVls:  # 遍历特征，创建决策树
        CARTTree[bestFeatLabel][value] = CART_createTree(splitdataset(dataset, bestFeat, value, True), labels[:])
    return CARTTree

# 根据构建好的决策树以及对应的标签，对用例进行分类，输出分类结果0或1，这个函数是TireTree的搜索
def classify(inputTree, featLabels, testVec):
    firstStr = next(iter(inputTree))  # 首先进入传进来的树的根节点，也就是house结点
    secondDict = inputTree[firstStr]  # 然后定义一个字典，进入根节点的值空间之中，就是第二层花括号，看的时候很容易理解，此时花括号里面有两个元素，一个是确定的键值对，另一个是键-字典对
    featIndex = featLabels.index(firstStr)  # 根据传进的labels，判断这个根节点是第几列的
    for key in secondDict.keys():  # 遍历这个字典，一般是有两对元素，一对是确定结果，另一个会进入深层的字典
        if testVec[featIndex] == key:  # 如果说，对应列的测试数据等于这个键
            if type(secondDict[key]).__name__ == 'dict':  # 判断这个键是不是字典
                classLabel = classify(secondDict[key], featLabels, testVec)  # 如果是字典，就要进入递归
            else:
                classLabel = secondDict[key]  # 不是字典，就可以直接返回结果
    return classLabel  # 若以上都不是，就直接返回结果，这里返回的结果是一个准确的值

# 从文件中读取数据集
def load_dataset(file_path):
    dataset = []
    with open(file_path, 'r') as f:
        for line in f:
            line = line.strip()
            if line:  # 非空行
                dataset.append(line.split(','))
    return dataset

# 主函数
if __name__ == '__main__':
    # 数据集文件路径
    dataset_path = "C:\\Users\\wu\\Desktop\\dataset.txt"
    testset_path = "C:\\Users\\wu\\Desktop\\testset.txt"

    # 读取数据集和测试集
    dataset = load_dataset(dataset_path)
    testset = load_dataset(testset_path)

    labels = ['age', 'job', 'house', 'credit situation']  # label就是四个标签，构建决策树的时候需要使用
    labels_tmp = labels[:]  # 因为在CART_createTree()函数里面会对于labels_tmp进行处理，所以这里拷贝了一个副本

    # 构建决策树
    CARTdesicionTree = CART_createTree(dataset, labels_tmp)
    print("决策树：")
    print(CARTdesicionTree)

    # 对测试集进行分类
    print("测试集分类结果：")
    for testVec in testset:
        result = classify(CARTdesicionTree, labels, testVec)
        print(f"测试样本 {testVec} 的分类结果为：{result}")

1.3 测试结果

2. ID3决策树

ID3算法的核心是通过递归地选择信息增益最大的特征来划分数据集，从而构建决策树，直到满足停止条件。

2.1 算法步骤

2.1.1 计算香农熵（经验熵）

香农熵用于衡量数据集的不确定性。计算公式为：

其中，pk​ 是第 k 类样本在数据集 D 中的比例。

2.1.2 按特征划分数据集

根据某个特征的某个值，将数据集划分为子集。例如，根据特征 有自己的房子 是否为 1，将数据集分为两部分。

2.1.3 选择最优特征

计算每个特征的信息增益，选择信息增益最大的特征作为划分特征。

信息增益公式：

其中，H(D∣A) 是条件熵。

2.1.4 递归构建决策树

• 如果所有样本属于同一类别，返回该类别。

• 如果没有更多特征可以划分，返回出现次数最多的类别。

• 否则，选择最优特征，划分数据集，递归构建子树。

2.2 实验源码

from math import log
import operator

# 从文件中读取数据集
def load_dataset(file_path):
    dataset = []
    with open(file_path, 'r') as f:
        for line in f:
            line = line.strip()
            if line:  # 非空行
                dataset.append(line.split(','))
    return dataset

# 计算给定数据集的经验熵（香农熵）
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
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

# 按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reduceFeatVec = featVec[:axis]
            reduceFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reduceFeatVec)
    return retDataSet

# 选择最优特征
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1

    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0.0

        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet) / float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)

        infoGain = baseEntropy - newEntropy
        print("第%d个特征的增益为%.3f" % (i, infoGain))

        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i

    return bestFeature

# 统计classList中出现次数最多的元素（类标签）
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, featLabels):
    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]
    featLabels.append(bestFeatLabel)
    myTree = {bestFeatLabel: {}}
    del(labels[bestFeat])

    featValues = [example[bestFeat] for example in dataSet]
    uniqueVls = set(featValues)

    for value in uniqueVls:
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),
                                                  labels[:], featLabels)
    return myTree

# 根据决策树对测试样本进行分类
def classify(inputTree, featLabels, testVec):
    firstStr = next(iter(inputTree))
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]).__name__ == 'dict':
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:
                classLabel = secondDict[key]
    return classLabel

# 主函数
if __name__ == '__main__':
    # 数据集文件路径
    dataset_path = "C:\\Users\\wu\\Desktop\\dataset.txt"
    testset_path = "C:\\Users\\wu\\Desktop\\testset.txt"

    # 读取数据集和测试集
    dataSet = load_dataset(dataset_path)
    testset = load_dataset(testset_path)

    # 定义特征标签
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况']
    featLabels = []

    # 构建决策树
    myTree = createTree(dataSet, labels, featLabels)
    print("决策树：")
    print(myTree)

    # 对测试集进行分类
    print("测试集分类结果：")
    for testVec in testset:
        result = classify(myTree, featLabels, testVec)
        print(f"测试样本 {testVec} 的分类结果为：{result}")

2.3 测试结果

三、实验总结

• 算法原理：

  • ID3 算法通过计算信息增益选择最优特征，适合生成多叉树，能够更细致地划分数据，但可能导致树的复杂度较高；CART 算法通过计算基尼指数选择最优特征，生成二叉树，结构简洁且易于理解和解释，但可能对某些特征的信息敏感度不足。

• 模型的选择：

  • ID3 算法适合特征值较多、需要更细致划分数据的场景，而 CART 算法更适合需要生成简洁模型、便于解释的场景。在实际应用中，需要根据具体问题的需求和数据特点选择合适的算法。

• 模型优缺点对比：

  • ID3 算法：

    • 优点：简单直观，易于实现；能够有效地减少数据的不确定性。

    • 缺点：倾向于选择特征值较多的特征，可能导致过拟合；生成的多叉树结构复杂度较高。

  • CART 算法：

    • 优点：生成的二叉树结构简洁，易于理解和解释；对数据的分布假设较少，适用于分类和回归任务。

    • 缺点：对特征的选择较为严格，可能导致某些特征的信息被忽略；二叉树结构可能导致树的深度较大，影响模型的效率。