机器学习-决策树(基本流程、划分选择)

发布于:2022-11-16 ⋅ 阅读:(11) ⋅ 点赞:(0) ⋅ 评论:(0)

1.决策树简介

决策树是一棵树,其中每个分支节点代表多个备选方案之间的选择,每个叶节点代表一个决策。它是一种监督学习算法,主要用于分类问题,适用于分类和连续输入和输出变量。 是归纳推理的最广泛使用和实用的方法之一(归纳推理是从具体例子中得出一般结论的过程)。决策树从给定的例子中学习和训练数据,并预测不可见的情况。

·与决策树相关的重要术语

基本术语:

  • 根节点(Root Node):它代表整个种群或样本,并进一步分为两个或更多个同类集。
  • 拆分(Splitting):这是将节点划分为两个或更多个子节点的过程。
  • 决策节点(Decision Node):当子节点分裂成更多的子节点时,它被称为决策节点。
  • 叶子/终端节点(Leaf/ Terminal Node):不分割的节点称为叶子或终端节点。

1.1决策树实例

决策树算法的本质是一种图结构,只需要问一系列问题就可以对数据进行分类

可以看出,在这个决策过程中,我们一直在对记录的特征进行提问。最初的问题所在的地方叫做根节点,在得到结论前的每一个问题都是中间节点,而得到的每一个结论都叫做叶子节点。

决策树算法的核心是要解决两个问题:

(1)如何从数据表中找出最佳节点和最佳分枝?(即怎么构造决策树)

(2)如何让决策树停止生长,防止过拟合?(即如何剪枝)

几乎所有决策树有关的模型调整方法,都围绕这两个问题展开。

1.2基本流程

(1)收集数据

(2)准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化。

(3)分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期。

(4)训练算法:构造树的数据结构。

(5)测试算法:使用经验树计算错误率。

(6)使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。

2.划分选择

2.1信息增益(ID3算法)

信息增益指的就是划分可以带来纯度的提高,信息熵的下降。它的计算公式,是父亲节点的信息熵减去所有子节点的信息熵。在计算的过程中,我们会计算每个子节点的归一化信息熵,即按照每个子节点在父节点中出现的概率,来计算这些子节点的信息熵。所以信息增益的公式可以表示为:

ID3的算法规则相对简单,可解释性强。同样也存在缺陷,比如我们会发现ID3算法倾向于选择取值比较多的属性。这种缺陷不是每次都会发生,只是存在一定的概率。在大部分情况下,ID3 都能生成不错的决策树分类。

 ID3算法的核心思想:根据样本子集属性取值的信息增益值的大小来选择决策属性(即决策树的非叶子结点),并根据该属性的不同取值生成决策树的分支,再对子集进行递归调用该方法,当所有子集的数据都只包含于同一个类别时结束。最后,根据生成的决策树模型,对新的、未知类别的数据对象进行分类。

 ID3算法优点:方法简单、计算量小、理论清晰、学习能力较强、比较适用于处理规模较大的学习问题。

 ID3算法缺点:倾向于选择那些属性取值比较多的属性,在实际的应用中往往取值比较多的属性对分类没有太大价值、不能对连续属性进行处理、对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。

决策树算法的关键在于如何选择最优划分属性。一般而言,我们希望决策树的分支节点所包含的样本尽可能属于同一类别,即其纯度越高越好。

通常,使用信息熵(information entropy)来作为度量样本纯度的标准,计算公式为:

Ent( D ) 的值越小,则 D 的纯度越高
计算信息熵时约定:若 p = 0 ,则 p log 2 p =0
• Ent( D ) 的最小值为 0 ,最大值为 log 2 |y|

2.2增益率

增益率定义为:

 

其中

 称为属性α的“固有值”.不难发现,属性 α取值数目越多(即M越大),则作为IV(α) 的值通常会越大. 因此,当有些属性取值过多时,可能会导致ID3算法误选取值较多的属性,此时使用增益率作为指标是一个很好的选择,这叫做C4.5决策树.

2.3基尼指数

3.决策树创建及展示(以信息增益划分属性)

现在我们要构建一个睡觉时间、是否运动、是否护肤对皮肤的影响的决策树

数据加载

def createDataSet():
    """
    传入要处理的数据集
    :return: 数据集内容,数据集标签
    """
    dataSet = [[1, 1, 1, 'yes'],
               [1, 1, 1, 'yes'],
               [0, 1, 1, 'no'],
               [1, 0, 1, 'yes'],
               [1, 0, 1, 'yes'],
               [0, 0, 1, 'no']]
    labels = ['十一点前睡觉', '每天运动', '每天护肤']
    # print(f'dataset:\n{dataSet}')
    return dataSet, labels

计算给定数据的香农熵

def calcShanonEnt(dataSet):
    """
    计算数据集的信息熵
    此处还没有乘权重
    :param dataSet:划分好的数据集
    :return:子数据集的信息熵,还没有考虑权重进来
    """

    # 数据中实例的总数
    numEntries = len(dataSet)
    # 为数据集所有可能性划分字典
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        # 如果字典中不存在,添加到字典中
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        # 对存在的结果计数
        labelCounts[currentLabel] += 1
        # print(f'我是labelCounts2:\n{labelCounts}')
        # 得到{'yes': 2, 'no': 3}
    shannonEnt = 0.0
    # 此部分用于计算一个数据集的信息熵,还没有加入权重(不一定是二叉树,有几个key分支就包含几种,这里考虑到了)
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * log(prob, 2)
    # print(f'我是初始信息熵shannonEnt:\n{shannonEnt}')
    return shannonEnt

选择最佳属性划分数据集

def chooseBestFeatureToSplit(dataSet):
    """
    对于信息熵的计算
    :param dataSet:
    :return:
    """
    # 得到特征数据的长度(特征的个数) 2
    numFeatures = len(dataSet[0]) - 1
    # 原数据集的信息熵
    baseEntropy = calcShanonEnt(dataSet)
    # 定义初始的熵增益
    bestInfoGain = 0.0;

    bestFeature = 0;
    for i in range(numFeatures):
        # 取某一列特征的值,example在此处代表列 我是featList:[1, 1, 0, 1, 1]
        featList = [example[i] for example in dataSet]
        # set集合去重取出每一特征下的所有可能情况 我是uniqueVals:{0, 1}
        uniqueVals = set(featList)
        # 定义一个变量为新的信息熵
        newEntropy = 0.0
        # 结合上方,按照某一个特征的不同value可以将数据集分割成len(uniqueVals)个子集,分割子数据集,并对子数据集求信息熵
        for value in uniqueVals:
            subDataSet = spliDataStet(dataSet, i, value)
            # print(f'我是subDataSet:\n{subDataSet}')
            # 此段代码中,prob是在某一特征分类下的权重,而self.calcShanonEnt函数计算出的为数据集的信息熵
            prob = len(subDataSet) / float(len(dataSet))
            # 得到的为按某一特征划分后的信息熵
            newEntropy += prob * calcShanonEnt(subDataSet)
        # 熵增益
        infoGain = baseEntropy - newEntropy
        # infoGain = newEntropy
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    # print(f'bestFeature:\n{bestFeature}')
    return bestFeature

按分类后类别数量排序

def majorityCnt(classList):
    # 创建键值为classList中唯一值的数据字典,字典对象存储了classList中每个类标签出现的频率
    # 利用operator操作键值排序字典,并返回出现次数最多的分类名称
    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)
    # print(f'我是sortedClassCount:\n{sortedClassCount}')
    # print(f'我是sortedClassCount:\n{sortedClassCount[0][0]}')
    return sortedClassCount[0][0]

构建决策树

def createTree(dataSet, labels):
    """
    构造树的过程
    :param dataSet:
    :param labels:
    :return:
    """
    classList = [example[-1] for example in dataSet]
    print(f'我是classList:\n{classList}')
    # 递归函数的第一个停止条件是所有的类标签完全相同,则直接返回该类标签
    # print(classList.count(classList[0],'==',len(classList)))
    # print(classList.count(classList[0]==len(classList)))
    if classList.count(classList[0]) == len(classList):
        """
        通过打印发现错误,第一个if判断语句的地方没有进来
        """
        print('yyyyy', classList[0])
        return classList[0]
    # 递归函数的第二个停止条件是使用完了所有特征,仍然不能将数据集划分成仅包含唯一类别的分组
    elif len(dataSet[0]) == 1:
        return majorityCnt(classList)
    # print(f'我是classList[0]:\n{classList[0]}')
    # return majorityCnt(classList[0])
    # if len(dataSet[0]) == 1:
    #     return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    print(f'bestFeat:\n{bestFeat}')
    bestFeatLabel = labels[bestFeat]
    print(f'我是bestFeatLabel:\n{bestFeatLabel}')
    # 分类结果储存到字典中
    myTree = {bestFeatLabel: {}}
    # 在标签列表中删除最佳标签
    del (labels[bestFeat])
    # 得到最佳标签一列的所有可能特征值集合
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    # 遍历特征值集合
    for value in uniqueVals:
        # 复印列表清单
        subLabels = labels[:]
        # 递归迭代,逐条插入字典
        myTree[bestFeatLabel][value] = createTree(spliDataStet(dataSet, bestFeat, value), subLabels)
    return myTree

运行结果

目录

1.决策树简介

1.1决策树实例

1.2基本流程

2.划分选择

2.1信息增益(ID3算法)

2.2增益率

2.3基尼指数

3.决策树创建及展示(以信息增益划分属性)