3. 决策树

1147-柳同学

发表文章数:589

首页 » 算法 » 正文

一、信息熵、条件熵、信息增益

1.信息熵

3. 决策树

2.条件熵

3. 决策树
3. 决策树
3. 决策树

3.信息增益

3. 决策树

二、ID3算法及决策树

ID3算法只有树的生成,所以该算法生成的树容易产生过拟合。
3. 决策树
3. 决策树
3. 决策树
3. 决策树

ID3算法代码实现

# 数据使用统计特征方法上的贷款申请样本数据
import numpy as np
import operator

np.random.seed(0)


def loaddata():
    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']]
    feature_name = ['age', 'job', 'house', 'credit']
    return dataSet, feature_name


# 定义计算数据集的熵的函数
def entropy(dataSet):
    # 数据量
    m = len(dataSet)
    # 标签不同类别的计数字典
    labelCounts = {}
    # 循环数据集
    for featVec in dataSet:
        currentLabel = featVec[-1]
        # 标签类别计数-如果字典中不存在则值为0,否则值加1
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    # 定义一个自变量来保存熵
    e = 0.0
    # 根据公式计算熵
    for key in labelCounts:
        prob = float(labelCounts[key]) / m
        e -= prob * np.log2(prob)
    return e


# 划分数据集——得到对应于轴axis与value的划分的数据集
def splitDataset(dataSet, value, axis):
    # 定义变量保存划分好的数据集
    retDataSet = []
    # 循环数据集
    for dataVec in dataSet:
        # 将当前数据按轴取出的值等于value的数据进行划分
        if dataVec[axis] == value:
            # 这个来控制数据集中的特征数
            temDataSet = dataVec[:axis]
            temDataSet.extend(dataSet[axis + 1:])
            retDataSet.append(dataVec)
    return retDataSet


# 每一个条件熵与信息增益一一对应
# 计算信息增益,并选择信息增益最大的特征
def chooseBestFeature(dataSet):
    # 特征数
    n = len(dataSet[0]) - 1
    # 计算数据集的信息熵
    baseEntropy = entropy(dataSet)
    # 定义变量保存信息增益与轴
    bestInfoGain = 0
    bestFeature = -1

    # 遍历每一个特征
    for i in range(n):
        # 获取当前特征的所有值
        featList = [example[i] for example in dataSet]
        # 当前特征的所有取值
        uniqueFeature = set(featList)
        # 定义临时变量保存当前的条件熵
        conditionEntropy = 0
        for value in uniqueFeature:
            # 按该值进行数据集的划分,形成子集
            subDataset = splitDataset(dataSet, value, i)
            # 计算条件熵
            prob = len(subDataset) / len(dataSet)
            conditionEntropy += prob * entropy(subDataset)
        # 计算信息增益
        infoGain = baseEntropy - conditionEntropy
        # 保存当前最大信息增益及其对应特征
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature


# 类别投票
def calssVote(classList):
    # 字典记录标签个数
    classCountDict = {}
    # 计数
    for vote in classList:
        if vote not in classCountDict:
            classCountDict[vote] = 0
        else:
            classCountDict[vote] += 1
    # 对标签个数进行排序
    # key=operator.itemgetter(1)表示根据字典中的值进行排序

    sortedClassCountDict = sorted(classCountDict.items(), key=operator.itemgetter(1), reverse=True)
    print(sortedClassCountDict)
    return sortedClassCountDict[0][0]


# 递归训练决策树
def trainTree(dataSet, feature_name):
    # 获取所有数据的类
    classList = [example[-1] for example in dataSet]
    # 所有数据类别都一致时,划分截止
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 数据集中只剩下一个特征时,划分截止
    if len(dataSet[0]) == 2:
        return calssVote(classList)
    # 否则,计算信息增益,并取最好特征的轴与特征名
    bestFeature = chooseBestFeature(dataSet)
    bestFeatName = feature_name[bestFeature]

    # 决策树
    myTree = {bestFeatName: {}}
    # 获取信息增益最大特征的每一个可能值
    featValues = [example[bestFeature] for example in dataSet]
    uniqueFeatValue = set(featValues)

    # 循环遍历每一个特征值
    for value in uniqueFeatValue:
        sub_feature_name = feature_name[:]
        myTree[bestFeatName][value] = trainTree(splitDataset(dataSet, value, bestFeature), sub_feature_name)

    return myTree


# 预测
def predict(inputTree, featlabels, testVec):
    # 第一棵树的根节点名称
    firstStr = list(inputTree.keys())[0]
    # 第二棵树的字典
    secondDict = inputTree[firstStr]
    # 第一棵树名称的索引值
    featIndex = featlabels.index(firstStr)
    # 将测试数据中对应的值取出来
    key = testVec[featIndex]
    # 得到第二棵树key对应的值
    value_2 = secondDict[key]

    # 如果对应的值为字典则迭代
    if isinstance(value_2, dict):
        classLabel = predict(value_2, featlabels, testVec)
    else:
        classLabel = value_2
    return classLabel


if __name__ == '__main__':
    dataSet, feature_name = loaddata()
    myTree = trainTree(dataSet, feature_name)
    print(myTree)

    # 预测
    classLabel = predict(myTree, feature_name, [1, 1, 0, 1])
    print(classLabel)

{'house': {0: {'job': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
yes

三、C4.5算法及决策树

3. 决策树
3. 决策树
3. 决策树
3. 决策树

# 数据使用统计特征方法上的贷款申请样本数据
import numpy as np
import operator
import warnings
np.random.seed(0)


def loaddata():
    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']]
    feature_name = ['age', 'job', 'house', 'credit']
    return dataSet, feature_name


# 定义计算数据集的熵的函数
def entropy(dataSet):
    # 数据量
    m = len(dataSet)
    # 标签不同类别的计数字典
    labelCounts = {}
    # 循环数据集
    for featVec in dataSet:
        currentLabel = featVec[-1]
        # 标签类别计数-如果字典中不存在则值为0,否则值加1
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    # 定义一个自变量来保存熵
    e = 0.0
    # 根据公式计算熵
    for key in labelCounts:
        prob = float(labelCounts[key]) / m
        e -= prob * np.log2(prob)
    return e


# 划分数据集——得到对应于轴axis与value的划分的数据集
def splitDataset(dataSet, value, axis):
    # 定义变量保存划分好的数据集
    retDataSet = []
    # 循环数据集
    for dataVec in dataSet:
        # 将当前数据按轴取出的值等于value的数据进行划分
        if dataVec[axis] == value:
            # 这个来控制数据集中的特征数
            temDataSet = dataVec[:axis]
            temDataSet.extend(dataSet[axis + 1:])
            retDataSet.append(dataVec)
    return retDataSet


# 每一个条件熵与信息增益比一一对应
# 计算信息增益比,并选择信息增益比最大的特征
def chooseBestFeature(dataSet):
    # 特征数
    n = len(dataSet[0]) - 1
    # 计算数据集的信息熵
    baseEntropy = entropy(dataSet)
    # 定义变量保存信息增益与轴
    bestInfoGainRate = 0
    bestFeature = -1

    # 遍历每一个特征
    for i in range(n):
        # 获取当前特征的所有值
        featList = [example[i] for example in dataSet]
        # 当前特征的所有取值
        uniqueFeature = set(featList)
        # 定义临时变量保存当前的条件熵
        conditionEntropy = 0
        H_A_D = 0
        for value in uniqueFeature:
            # 按该值进行数据集的划分,形成子集
            subDataset = splitDataset(dataSet, value, i)
            # 计算条件熵
            prob = len(subDataset) / len(dataSet)
            conditionEntropy += prob * entropy(subDataset)
            # 计算数据集D关于特征A的熵
            H_A_D -= prob * np.log2(prob)
        # 计算信息增益
        infoGain = baseEntropy - conditionEntropy
        # 计算信息增益比
        infoGainRate = infoGain / H_A_D
        # 保存当前最大信息增益及其对应特征
        if infoGainRate > bestInfoGainRate:
            bestInfoGainRate = infoGainRate
            bestFeature = i
    return bestFeature


# 类别投票
def calssVote(classList):
    # 字典记录标签个数
    classCountDict = {}
    # 计数
    for vote in classList:
        if vote not in classCountDict:
            classCountDict[vote] = 0
        else:
            classCountDict[vote] += 1
    # 对标签个数进行排序
    # key=operator.itemgetter(1)表示根据字典中的值进行排序

    sortedClassCountDict = sorted(classCountDict.items(), key=operator.itemgetter(1), reverse=True)
    print(sortedClassCountDict)
    return sortedClassCountDict[0][0]


# 递归训练决策树
def trainTree(dataSet, feature_name):
    # 获取所有数据的类
    classList = [example[-1] for example in dataSet]
    # 所有数据类别都一致时,划分截止
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 数据集中只剩下一个特征时,划分截止
    if len(dataSet[0]) == 2:
        return calssVote(classList)
    # 否则,计算信息增益,并取最好特征的轴与特征名
    bestFeature = chooseBestFeature(dataSet)
    bestFeatName = feature_name[bestFeature]

    # 决策树
    myTree = {bestFeatName: {}}
    # 获取信息增益比最大特征的每一个可能值
    featValues = [example[bestFeature] for example in dataSet]
    uniqueFeatValue = set(featValues)

    # 循环遍历每一个特征值
    for value in uniqueFeatValue:
        sub_feature_name = feature_name[:]
        myTree[bestFeatName][value] = trainTree(splitDataset(dataSet, value, bestFeature), sub_feature_name)

    return myTree


# 预测
def predict(inputTree, featlabels, testVec):
    # 第一棵树的根节点名称
    firstStr = list(inputTree.keys())[0]
    # 第二棵树的字典
    secondDict = inputTree[firstStr]
    # 第一棵树名称的索引值
    featIndex = featlabels.index(firstStr)
    # 将测试数据中对应的值取出来
    key = testVec[featIndex]
    # 得到第二棵树key对应的值
    value_2 = secondDict[key]

    # 如果对应的值为字典则迭代
    if isinstance(value_2, dict):
        classLabel = predict(value_2, featlabels, testVec)
    else:
        classLabel = value_2
    return classLabel


if __name__ == '__main__':
    # 消除警告
    warnings.filterwarnings(action='ignore')
    dataSet, feature_name = loaddata()
    myTree = trainTree(dataSet, feature_name)
    print(myTree)

    # 预测
    classLabel = predict(myTree, feature_name, [0, 0, 0, 0])
    print(classLabel)

{'house': {0: {'job': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
no

四、CART算法及决策树

3. 决策树

1. CART决策树的生成

3. 决策树
3. 决策树
回归树的生成见《统计特征方法》

五、决策树剪枝

3. 决策树

损失函数为:
设树T的叶结点个数为|T|,t是树T的叶节点,该叶节点有Nt个样本点,其中属于k类的样本点有Ntk个,Ht(T)是叶节点t上的经验熵

3. 决策树

未经允许不得转载:作者:1147-柳同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《3. 决策树》 发布于2021-01-10

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录