做百度网站分录,做推广的公司,wordpress图标方块,html导航栏模板目录 1. 什么是决策树? 2. 决策树的原理 2.1 如何构建决策树#xff1f; 2.2 构建决策树的数据算法 2.2.1 信息熵 2.2.2 ID3算法 2.2.2.1 信息的定义 2.2.2.2 信息增益 2.2.2.3 ID3算法举例 2.2.2.4 ID3算法优缺点 2.2.3 C4.5算法 2.2.3.1 C4.5算法举例 2.2.4 CART算法 2.2.4… 目录 1. 什么是决策树? 2. 决策树的原理 2.1 如何构建决策树 2.2 构建决策树的数据算法 2.2.1 信息熵 2.2.2 ID3算法 2.2.2.1 信息的定义 2.2.2.2 信息增益 2.2.2.3 ID3算法举例 2.2.2.4 ID3算法优缺点 2.2.3 C4.5算法 2.2.3.1 C4.5算法举例 2.2.4 CART算法 2.2.4.1 Gini指数基尼指数 2.2.4.2 Cart算法 相关公式 2.2.4.3 Cart算法举例 3. 未完待续。。。 4. 本文涉及的代码 1. 什么是决策树? 决策树分类的思想类似于找对象。 想象一个女孩的母亲要给这个女孩介绍男朋友于是有了下面的对话 女孩决定是否见男孩的一个过程就像一个树形结构只不过是反正的树 数学上或者机器学习里的树根在最上方 最上方的为树的根节点下面的都是子节点 像下图的橙色的部分下面在没有往下的结点的叫叶子节点 如果一颗树每个节点下面最多只有两个节点就属于二叉树 下图的就是一个非二叉树( 到收入下面有三个节点) 上图完整表达了这个女孩决定是否见一个约会对象的策略 其中绿色节点表示判断条件 橙色节点表示决策结果 箭头表示在一个判断条件在不同情况下的决策路径 图中红色箭头表示了上面例子中女孩的决策过程。 这幅图基本可以算是一颗决策树说它“基本可以算”是因为图中的判定条件没有量化 如收入高中低等等还不能算是严格意义上的决策树 如果将所有条件量化则就变成真正的决策树了。 有了上面直观的认识我们可以正式定义决策树了 决策树(decision tree)是一个树结构可以是二叉树或非二叉树)。 其每个非叶节点表示一个特征属性上的测试每个分支代表这个特征属性在某个值域上的输出而每个叶节点存放一个类别。 使用决策树进行决策的过程就是从根节点开始测试待分类项中相应的特征属性并按照其值选择输出分支直到到达叶子节 点将叶子节点存放的类别作为决策结果 可以看到决策树的决策过程非常直观容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支 生物学以及商业等诸多领域。决策树的主要优势就在于数据形式非常容易理解。 决策树算法能够读取数据集合构建类似于上面的决策树决策树很多任务都是为了数据中所蕴含的知识信息因此决策树可以使用不熟悉的数据集合并从中提取出一系列规则机器学习算法最终将使用这些机器从数据集中创造的规则。专家系统中经常使用决策树而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家 2. 决策树的原理 2.1 如何构建决策树 首先例如上方的图我们可以分析到我们要先选择 判断条件 例如有些女孩找男朋友的第一个条件考虑年龄而有的考虑收入有的还考虑长相等等所以这就是构造决策树的第一个关键的点判断条件的顺序 有了判断条件之后怎么判断这个节点的分裂例如年龄这个判断条件是按照30岁分还是按照什么分符合这个条件是一个节点不符合这个判断条件的是另外一个节点这就是构造决策树的第二个关键的点节点分裂的界限或者说节点分裂的定义和分类 构造决策树关键步骤是分裂属性所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支其目标是让各个分裂子集尽可能的“纯”尽可能“纯” 就是尽量让一个分裂子集中待分类项属于同一类别 2.2 构建决策树的数据算法 2.2.1 信息熵 有了刚说的两个关键点对于这个两个关键点的选择就有点困难所以需要具体的算法来做 建决策树的数据算法有很多 ID3算法 C4.5算法 CART算法 ..... 等等 这里面就牵扯了信息论中的信息熵 有关信息熵可参考可以点开全部回答然后搜索 阅读 或者自行查看 信息熵是什么 - 知乎原创文章一家之言。转载请注明出处。个人公众号follow_bobo机器学习入门重要的概念---信息熵Shan…https://www.zhihu.com/question/22178202/answer/265757803 信息熵的数学公式 2.2.2 ID3算法 ID3算法算的是信息增益 2.2.2.1 信息的定义 熵定义为信息的期望值在明确这个概念之前我们必须知道信息的定义如果待分类的事务划分在多个分类之中则符合X的信息定义为 其中p(x)是选择该分类的概率 为了计算熵我们需要计算所有类别所有可能的信息期望值通过下面的公式得到 其中n 是分类的数目 在决策树当中设D为用类别对训练元组进行的划分则D的熵(entropy)表示为 其中pi 表示第i个类别在整个训练元组出现的概率可以用属于此类别元素的数量除以训练元组元素总数作为估计。 熵的实际意义表示是D中元组的类标号所需要的平均信息量 现在我们假设将训练元组D按属性A进行划分则A对D划分的期望信息为 2.2.2.2 信息增益 ID3算法 利用 信息增益来决定优先使用哪个特征进行分裂 先用没有进行任何属性分类的时候计算一个信息熵 再选其中的某一个特征进行分裂构造决策树再计算一个信息熵具体用哪个特征来计算要看哪个特征计算出来的信息熵大就用哪个因为这样算出来的值越大相减之后就消除了原来数据里面最大的不确定性 这两个信息熵之间会有一个差值 这两个信息熵之差得到的值叫做信息增益 2.2.2.3 ID3算法举例 ID3算法就是在每次需要分裂时计算每个属性的增益率然后选择增益率最大的属性进行分裂 如下图假设训练集合包含10条数据预测一下社交网站上的账号是否真实的账号 根据日志密度好友密度是否使用真是头像等这些都为特征来预测 代表的含义 s 小m中等l 大 先完成构建决策树其中一个关键点首先用那个特征进行分裂 计算思路 1⃣️ 先计算没有使用任何特征对账号是否真实的计算的信息熵 2⃣️ 再算随便使用一个特征对账号是否真实的计算的信息熵 代码如下使用 jupyter notebook import pandas as pd
import numpy as np # 计算图中的信息熵确定一个分类的特征
# D 就是我们的原始数据
# 先计算未使用任何特征的进行分类的信息熵所以只需关心账号是否真实这一列
# 账号是否真实 有两种情况分别为 yes no, yes数量为7(概率为0.7)no的数量为3(概率为0.3)
# 根据信息熵公式
info_D -(0.7 * np.log2(0.7) 0.3 * np.log2(0.3))
info_D
# 0.8812908992306927 使用 日志密度 对账号是否真实的信息熵 使用公式 # 使用 日志密度 对账号是否真实的信息熵 使用公式
# j 就是 3因为日志密度有三种情况s,l,m
# s 三个0.3对应账号是否真实列2个no, 1个yes
# l 三个0.3, 对应账号是否真实列0个no, 3个yes
# m 四个0.4, 对应账号是否真实列1个no, 3个yes
# s情况中对日志密度划分的信息熵 s 的 概率 ✖️ s 中对账号是否真实的信息熵 0.3 * ((-1/3) * np.log2(1/2) (-2/3) * np.log2(2/3))
# 同理 l 0.3 * (-1 * log2(1))
# 同理 m
info_D_Log 0.3 * ((-1/3) * np.log2(1/3) (-2/3) * np.log2(2/3)) 0.3 * (-1 * np.log2(1)) 0.4 * ((-1/4) * np.log2(1/4) (-3/4) * np.log2(3/4))
info_D_Log # 使用 日志密度 进行划分的信息增益
info_D - info_D_Log
# 0.2812908992306927# 使用 好友密度 对账号是否真实的信息熵
# s 4个0.4对应账号是否真实列3个no, 1个yes
# m 4个0.4, 对应账号是否真实列0个no, 4个yes
# l 2个0.2, 对应账号是否真实列0个no, 2个yes
info_D_F 0.4 * ((-3/4) * np.log2(3/4) (-1/4) * np.log2(1/4)) 0 0
info_D_F
# 0.32451124978365314# 使用 好友密度 进行划分的信息增益
info_D - info_D_F
# 0.5567796494470396 # 使用 是否使用真实头像 对账号是否真实的信息熵
# no 5个 2个no,3个yes
# yes 5个 1个no,4个yes
info_D_H 0.5 * ((-2/5) * np.log2(2/5) (-3/5) * np.log2(3/5)) 0.5 * ((-1/5) * np.log2(1/5) (-4/5) * np.log2(4/5))
info_D_H
# 0.8464393446710154 # 使用 是否使用真实头像 进行划分的信息增益
info_D - info_D_H
# 0.034851554559677256 根据上述的运算结果可以看到 使用 好友密度 进行划分的信息增益 的 值最大 所以 我们就用好友密度这个特征来构建决策树 再完成构建决策树另外一个关键点首先用那个特征进行分裂节点分裂的界限或者说节点分裂的定义和分类 而这些我们不需要关心ID3算法会帮我们做好只要能确定出来用哪个特征即可 分裂属性分为三种不同的情况 属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试按照“属于此子集”和“不属于此子集”分成两个分支。属性是连续值。此时确定一个值作为分裂点split_point, 按照split_point和split_points生成两个分支。 离散值即 例子中的 s,m,l,这种就是有三个划分而连续值类似年龄这种连续值293031等 2.2.2.4 ID3算法优缺点 优点简单、时间复杂度、时间复杂度都不高缺点数据中大量的离散型的数据会对分裂造成误差 2.2.3 C4.5算法 因为ID3算法在对于离散型特征的处理不好引入C4.5算法 C4.5算法计算的是信息增益率 计算步骤 先计算信息增益再除以这个特征本身的信息熵 2.2.3.1 C4.5算法举例 信息增益上面ID3算法已经计算出来可以直接使用 代码如下 2.2.4 CART算法 2.2.4.1 Gini指数基尼指数 由上面的内容我们已经知道决策树的核心就是寻找纯净的划分因此引入了纯度的概念。在属性选择上我们是通过统计“不纯度”来做判断的ID3 是基于信息增益做判断C4.5 在 ID3 的基础上做了改进提出了信息增益率的概念。实际上 CART 分类树与 C4.5 算法类似只是属性选择的指标采用的是基尼指数。 基尼指数本身反应了样本的不确定度。当基尼系数越小的时候说明样本之间的差异性小不确定程度低。分类的过程本身是一个不确定度降低的过程即纯度的提升过程。所以 CART 算法在构造分类树的时候会选择基尼系数最小的属性作为属性的划分。 在决策树Cart算法中用Gini指数来衡量数据的不纯度或者不确定性 2.2.4.2 Cart算法 相关公式 在分类问题中样本属于第 i 类的概率为 经过特征a分割之后集合D的不确定性基尼指数越大不确定性越大因此我们需要寻找基尼指数越小的特征作为节点 2.2.4.3 Cart算法举例 3. 本文涉及的代码 https://download.csdn.net/download/wei18791957243/88660903https://download.csdn.net/download/wei18791957243/88660903https://download.csdn.net/download/wei18791957243/88660904https://download.csdn.net/download/wei18791957243/88660904 https://download.csdn.net/download/wei18791957243/88664136https://download.csdn.net/download/wei18791957243/88664136
