码农小屋 码农小屋
  • 首页
  • 文章
    • Python
    • 计算机基础
    • C语言
    • Java
    • 数据库
    • Linux
  • 资源
  • 随笔
  • 优秀软件
  • 24h新鲜事
  • 专题
  • 留言板
  • 注册 登录
立即登录
0文章
0评论
0获赞
  • 首页
  • 博客中心
    • 文章
    • 资源
  • 随笔
  • 优秀软件
  • 24h新鲜事
  • 专题
  • 留言板
主页 › 文章 › Python › 机器学习——决策树
#Python#

机器学习——决策树

3月前
145 0 0

决策树算法概述

机器学习——决策树-码农小屋

认识决策树

决策树思想的来源非常朴素,程序设计中的条件分支结构就是if-else结构,最早的决策树就是利用这类结构分割数据的一种分类学习方法。

例如以前的一个游戏,二十个问题的游戏,游戏的规则很简单:参与游戏的一方在脑海里想某个事物,其他参与者向他提问题,只允许提20个问题,问题的答案也只能用对或错回答。问问题的人通过推断分解,逐步缩小待猜测事物的范围。决策树的工作原理与20个问题类似,用户输人一系列数据,然后给出游戏的答案。

我们经常使用决策树处理分类问题,近来的调查表明决策树也是最经常使用的数据挖掘算法。它之所以如此流行,一个很重要的原因就是不需要了解机器学习的知识,就能搞明白决策树是如何工作的。

我们来看一个例子:你母亲要给你介绍男朋友,是这么来对话的:

女儿:多大年纪了?
母亲:26。
女儿:长的帅不帅?
母亲:挺帅的。
女儿:收入高不?
母亲:不算很高,中等情况。
女儿:是公务员不?
母亲:是,在税务局上班呢。
女儿:那好,我去见见。

由此可以看出,如何高效的进行决策,取决于特征选取的先后顺序,那么如何决定特征选取的先后顺序?这就是决策树算法主要解决的问题。

基于信息论确定特征选取顺序

信息熵的定义

在信息论里,用H表示信息熵,表示随机变量不确定性的度量,单位是bit。如果待分类的事务可能划分在多个分类之中,则每个分类xi的信息定义为:

机器学习——决策树-码农小屋

计算信息熵H,需要计算所有类别所有可能值包含的信息期望值(数学期望):

机器学习——决策树-码农小屋

其中n是分类的数目,p(xi)是选择该分类的概率。

我们认为熵越大,随机变量的不确定性就越大。

信息增益

划分数据集的大原则是:将无序的数据变得更加有序。我们可以使用多种方法划分数据集,但是每种方法都有各自的优缺点。组织杂乱无章数据的一种方法就是使用信息论度量信息,信息论是量化处理信息的分支科学。我们可以在划分数据之前或之后使用信息论量化度量信息的内容。在划分数据集之前之后信息发生的变化称为信息增益,知道如何计算信息增益,我们就可以计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择。

在可以评测哪种数据划分方式是最好的数据划分之前,我们必须学习如何计算信息增益。集合信息的度量方式称为香农熵或者简称为熵,这个名字来源于信息论之父克劳德·香农。

如果看不明白什么是信息增益( information gain )和熵( entropy )请不要着急。它们自诞生的那一天起,就注定会令世人十分费解。克劳德·香农写完信息论之后,约翰·冯·诺依曼建议使用“熵”这个术语,因为大家都不知道它是什么意思。

决策树的划分依据

当然决策树的原理不止信息增益这一种, 还有其他方法。但是原理都类似,我们就不去举例计算。类似的如下:

  • ID3:信息增益最大的准则
  • C4.5:信息增益比最大的准则
  • CART:分类树——基尼系数最小的准则(在sklearn中可以选择划分的默认原则)。优势:划分更加细致

决策树的一般流程

  1. 收集数据:可以使用任何方法。
  2. 准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化。
  3. 分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期。
  4. 训练算法:构造树的数据结构。
  5. 测试算法:使用经验树计算错误率。
  6. 使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。

决策树算法特性

优点

  • 计算复杂度不高
  • 能够实现可视化
  • 对数据规格无要求(离散、连续)
  • 对中间值的缺失不敏感,可以处理不相关特征数据
  • 模型相对固定
  • 输出结果易于理解

缺点(不足)

  • 数据不能缺失
  • 可能会产生过度匹配的问题
  • 要求对树的生长有控制

构建决策树

ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征,递归地构建决策树。

  • Step1:计算数据集所有的特征的信息增益。
  • Step2:选择信息增益最大的特征作为结点的特征。
  • Step3:由该特征的不同取值划分数据集;
  • Step4:计算对step3中划分的所有子集进行以下操作。
    • Step4.1:子集中的样本的目标值属于同一分类或者子集中所有特征的信息增益均很小或没有特征可以选择,算法end并得到一个决策树;
    • Step4.2:否则,再对子集递归地调用Step1到Step4。

实施决策树算法

Python核心代码如下:

def majorityCut(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, featLables):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    if len(labels) == 0:
        return majorityCut(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLable = labels[bestFeat]
    featLabels.append(bestFeatLable)
    myTree = {bestFeatLable: {}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels.copy()
        myTree[bestFeatLable][value] = createTree
            (splitDataSet(dataSet, bestFeat, value),subLabels, featLables)
    return myTree

函数说明:统计classList中出现此处最多的元素(类标签)

Parameters:
classList - 类标签列表
Returns:
sortedClassCount[0][0] - 出现此处最多的元素(类标签)

函数说明:创建决策树

Parameters:
dataSet - 训练数据集
labels - 分类属性标签
featLabels - 存储选择的最优特征标签
Returns:
myTree - 决策树

注:这只是实施决策树算法核心代码,并不是所有代码,完整代码和解析将会在下一篇实战文章中列出。

0
Mr Gu
相关文章
机器学习——K-均值聚类算法
Logistic回归实战——病症状预测
机器学习——Logistic回归
线性回归实战——使用岭回归预测二手乐高的价格
机器学习——线性回归算法
评论 (0)
再想想
Mr Gu管理员
Better late than never.
45文章 1评论 51获赞
文章推荐
ZIP Pro 3 – 文件压缩分享加密管理套件
2月前
Uninstall Tool-专业的软件卸载工具
3月前
Speccy:优秀的硬件检测工具
4月前
CleanMyPC-专为 Windows打造的清理工具
4月前
Internet Downloader Manager-一款专业的Win下载工具
4月前
Wise Care 365-Windows 系统清理和加速工具
4月前
新鲜事
新Mac太牛:在电脑上运行iPhone、iPad的软件、游戏
2月前
自从苹果M1芯片发布之后,使用这颗芯片的Mac电脑,就被大家认为是有史以来最强的Mac,因为这颗小米的芯片,在性能上已经打败了苹果使用的最高端的i9芯 ...[阅读全文]
苹果发布会总结:一个芯片,三款产品!苹果这把棋下得可真深
2月前
北京时间11月11日凌晨2点,苹果在圣何塞召开了本年度最后一场发布会。在这次发布会上,苹果推出了基于ARM架构的全新M1自研处理器。 ...[阅读全文]
荣耀命运落定:救了自己,也救华为
2月前
华为出售荣耀一事终于落槌。 ...[阅读全文]
发布会停不下来,苹果下月发布新Mac
3月前
今年的苹果有些与众不同,往年只开一次秋季发布会,今年在九月十月连开两场。 ...[阅读全文]
iPhone 12 开启 5G 续航锐减,苹果回应
3月前
对于今年的 iPhone 12 来说,除了回归直角边框设计之外,最大的亮点就是 5G 了。 ...[阅读全文]
华为Mate40正式发布
3月前
定位高端旗舰的华为Mate40系列共发布四款新机:华为Mate40(6.5英寸)、华为Mate40 Pro(6.76英寸)、华为Mate40 Pro+ ...[阅读全文]
更多
  • 专题
  • 文章
  • 友情链接
  • 留言板
Copyright © 2020-2021 码农小屋. 苏ICP备20033168号