小工具      在线工具  汉语词典  css  js  c++  java

决策树的ID3算法

基本概念
  • 决策树是包含一个根节点、多个内部节点和多个叶节点的树结构。根节点包含完整的样本集,叶节点对应决策结果,内部节点对应特征和属性或属性测试。从根节点到每个叶节点的路径对应于一个决策测试序列。决策树学习的目的是产生具有很强泛化能力的决策树,即处理未见过的例子的能力很强。机器的基本流程简单直观。对于分治策略来说,决策树的生成是一个递归过程。
  • 构建决策树的核心问题是如何在每一步选择合适的特征来分割样本。主要算法有CART、ID3、C4.5; CART使用基尼指数作为选择特征的标准。 ID3使用信息增益作为特征选择的标准。 C4.5使用信息增益比作为特征选择的标准。决策树的剪枝是为了防止树的过拟合,增强其泛化能力,包括预剪枝和后剪枝。
  • 决策树的优点和缺点
  1. 决策树算法易于理解,能做可视化分析,容易提取出规则。其次,决策树可同时处理标称型和数值型数据。在
    次,决策树能很好的扩展到大型数据库中。

  2. 决策树由于样本太少、特征太多,容易出现过拟合,忽略了数据集中属性的相关性。 ID3算法计算的信息增益偏向于数值较多的特征。

信息熵

数学期望:每次可能的结果的概率乘以其结果的的总和。
信息价值:在沙漠地区,告诉你明天不下雨,和明天下雨的信息价值是不同的,前者为高概率,显然概率越小的事件其价值越高。信息价值公式:l ( x i ) = − l o g 2 p ( x i ) \ l(xi) = \ -log_2p(xi)X=-G2pX

// 信息值与概率的关系
from math import log
import matplotlib.pyplot as plt
x= [i/100 for i in range(1,100)]
p=[-log(i,2) for i in x]
plt.xlabel("x")
plt.ylabel("l(x)")
plt.plot(x,p)
plt.show()

在这里插入图片描述
决策树原理(以是否打球决策树为例):
在这里插入图片描述

为了简化程序,ID3 算法处理数值数据。先把文本转换成数值会方便很多。这里0、1、2分别代表三个特征,天气、场馆人数、加时赛; 4代表类别;表中的0、1代表该特性的状态“否”和“是”。

在这里插入图片描述

在构造决策树树时,需要将那些起决定性作用的特征作为首要决策点,须利用一定算法对特征进行评估也是上面的三个算法。 

信息熵:一条信息的信息量大小和和它的不确定性有直接关系,信息熵是信息价值的数学期望【即类别的信息价值平均值】。公式:H = − Σ n = 0 n p ( x i ) l o g 2 p ( x i ) \ H = -\sum_{n=0}^{n}p(xi)log_2p(xi)H=-n=0ΣnpXG2pX

# 导入包
import numpy as np
import pandas as pd

#导入数据
data={
    0:[1,0,0,"打球"],
    1:[1,0,1,"打球"],
    2:[0,1,1,"打球"],
    3:[0,0,1,"不打球"],
    4:[1,1,1,"打球"]
}

# 计算熵的函数
def ent(data):
    print("原始数据:")
    df0=pd.DataFrame(data)
    print(df0)
    print("整理后的数据")
    df=df0.T
    print(df)
    print("数据长度:")
    data_length=len(data)
    print(data_length)
    print("取出结论熵【信息价值的期望值】")
    target=df.iloc[:,-1]  # pandas的行列操作函数loc和iloc
    print(target)
    print("分类计数")
    label_counts=target.value_counts()  # pandas的value_counts()计数函数
    print(label_counts)
    print("转字典类型")
    label_dict=label_counts.to_dict()    #pandas的转换字典的函数
    print(label_dict)
    entropy=0
    for key in label_dict:
        prob=float(label_dict[key])/data_length
        entropy-=prob*np.log2(prob)
    return entropy
print(ent(data))

在这里插入图片描述

最终输出0.7219280948873623就是类别信息熵。

信息增益:类别信息熵与某个属性状态下不同特征的信息熵【条件概率】的差值,公式:i n f o ( H ) = H − Σ i = 1 v H v H χ H ( v ) info(H)=H-\sum_{i=1}^{v} \frac{Hv}{H}\chi H(五)nFH=H-=1ΣvHHvχHv

公式的含义是:不同属性下,每个特征占数据总量的比例乘以该特征下的信息熵之和。 (有点难理解,接下来用数学表达式进一步解释)

#导入库
import pandas as pd
import numpy as np
#写入数据
data={
    0:[1,1,0,0,1],
    1:[0,0,1,0,1],
    2:[0,1,1,1,1],
    3:["打球","打球","打球","不打球","打球"]
}
#pandas处理数据
df=pd.DataFrame(data)
print(df)

#封装计算熵的函数
def ent(df):
    target=df.iloc[:,-1] #取表的最后一列仍为DataFrame类型
    data_length=len(df)
    label_counts=target.value_counts() #value_count()聚合函数,统计数量
    label_dict=label_counts.to_dict() #将统计后的结果转化为字典类型
    entropy=0 #初始化熵的值
    #熵的计算公式
    for key in label_dict:
        prob=float(label_dict[key])/data_length
        entropy-=prob*np.log2(prob)
    return entropy

#封装分割数据的函数
def split(df,feature_rank):
    groups=df.groupby(feature_rank)
    data_group={}
    for key in groups.groups.keys():
        data_group[key]=df.loc[groups.groups[key],:]
    return data_group

def _main_(data,feature_rank):
    init=ent(data)
    group_dict=split(data,feature_rank)
    new_ent=0
    for key in group_dict:
        prob=len(group_dict[key])/len(data)
        new_ent+=prob*ent(group_dict[key])
    return init-new_ent
print(_main_(data,0))
    

数据的数值算法思想均来源于Python机器学习的实际开发(王新宇主编,邮电出版社出版,谢谢!!!)

// 分别计算0,1,2特征的信息增益
print("特征0的信息增益为:",_main_(data,0))
print("特征1的信息增益为:",_main_(data,1))
print("特征2的信息增益为:",_main_(data,2))

特征 信息增益
0(天气) 0.3219
1(场内人数) 0.1709
2(加时赛) 0.0729

计算出的信息增益可以看出,天气对是否比赛影响很大,加时赛影响最小。通过排序,可以按顺序列出特征对结果的影响分布,并选择特征构建决策树。

信息获取详情: (以下表中的数据为例)
在这里插入图片描述

该表是两周内是否有PlayTimes的数据,对于Outlook的属性来说,其一共有三种特征即Sunnny,Rain,Overcast
对于类别统计:
在这里插入图片描述

那么对于整个表来说其类别信息熵为:H ( 播放时间 ) = − 9 14 l o g 2 9 14 − 5 14 l o g 2 5 14 = 0.942107 H(播放时间) = - \frac{9}{14}log_2\frac{9}{14}-\frac {5}{14}log_2\frac{5}{14}=0.942107HAy时间es=-149G2149-145G2145=0942107

属性Outlook的熵(三个熵值):
在这里插入图片描述

在这里插入图片描述

Rain特征总数为5个,其中Yes占3/5,No占2/5; Sunny特征总数为5个,其中Yes占2/5,No占3/5; Overcast特征总数为4个,Yes占100%

过度投射的信息熵: H ( 过度投射 ) = − 4 4 l o g 2 4 4 − 0 = 1.0 过度投射的信息熵: H(Overcast) = - \frac{4}{4}log_2\frac{4}{4 }-0=1.0verCAst兴趣HverCAst=-44G244-0=10
S u n n y 的信息熵: H ( S u n n y ) = − 2 5 l o g 2 2 5 − 3 5 l o g 2 3 5 = 0.970 Sunny 的信息熵: H(Sunny) = - \frac{2}{5}log_2\frac {2}{5}-\frac{3}{5}log_2\frac{3}{5}=0.970Snny兴趣HSnny=-52G252-53G253=0970
Ra i n 的信息熵: H ( Rain ) = − 4 5 l o g 2 4 5 − 1 5 l o g 2 1 5 = 0.722 Rain 的信息熵: H(Rain) = - \frac{4}{5}log_2\frac {4}{5}-\frac{1}{5}log_2\frac{1}{5}=0.722An兴趣HAn=-54G254-51G251=0722
Overlook 的信息增益: G ( R a in ) = H ( Play Time s ) − ( 4 14 H ( Overcast ) + 5 14 H ( Sun n y ) + 5 14 H ( R a in ) = 0.888 Overlook 的信息增益: G(雨) = H(播放次数)- (\frac{4}{14}H(阴)+\frac{5}{14}H(晴) +\frac{5}{14}H(雨) =0.888verk兴趣增加有利GAn=HAy时间es-144HverCAst+145HSnny+145HAn=0888
到此已经计算出Overlook的信息增益了。

构造决策树

计算信息增益就是为了在当前的状态下选择最合适特征作为节点,以递归构造决策树,而构造决策树的目的反过来又是对新的数据分类,确定未知的数据类别。具体就是需要一部分数据作为训练集指定规则(决策树),然后利用这些规则(决策树)对新的数据进行分类。
在这里插入图片描述

具体构造决策树的流程参照生成决策树@代码拖拉鸡,谢谢!!!

那么,如何用代码实现呢?决策树分类器方法已经集成了生成决策树的代码,我们只需要会运用即可。
在这里插入图片描述

上表数据构造决策树,判断[1,1,0]是否打球?

#以是否打球为例构建决策树

import pandas as pd
data={
    0:[1,0,0,"打球"],
    1:[1,0,1,"打球"],
    2:[0,1,1,"打球"],
    3:[0,0,1,"不打球"],
    4:[1,1,1,"打球"]
}
df0=pd.DataFrame(data)
df=df0.T
print(df)

from sklearn import tree  #导入模块
x=[[1,0,0],[1,0,1],[0,1,1],[0,0,1],[1,1,1]]   #训练集的数据,矩阵类型(0,1分别表示不同特征)
y=[1,1,1,0,1]    #训练集类别  列表类型(0,1表示不同类别)
tree_model = tree.DecisionTreeClassifier(criterion='entropy')  #构造决策树模型,entropy表示信息增益计算即ID3算法
clf = tree_model.fit(x, y)   #用构建的决策树模型拟合训练数据
clf.predict([[1,1,0]])   #预测[1,1,0]是否打球

结果:
在这里插入图片描述
输出了1,表示打球,即[1,1,0]状态下也打球。
构建的决策树如下:

// 输出决策树代码
# 可以用 Graphviz 格式(export_graphviz)输出。
# 如果使用的是 conda 包管理器,可以用如下方式安装:
# conda install python-graphviz  window+r +cmd中进行
# pip install graphviz


# 以下展示了用 Graphviz 输出上述从鸢尾花数据集得到的决策树,结果保存为 iris.pdf

# import graphviz
# iris = load_iris()
# dot_data = tree.export_graphviz(clf, out_file=None)
# graph = graphviz.Source(dot_data)
# graph.render("iris")
# export_graphviz 支持使用参数进行视觉优化,包括根据分类或者回归值绘制彩色的结点,也可以使用显式的变量或者类名。
# Jupyter Notebook 还可以自动内联呈现这些绘图。


import graphviz     
#iris = load_iris()
clf = tree.export_graphviz(tree_model, out_file=None)
graph = graphviz.Source(clf)
graph

在这里插入图片描述

未来会更新c4.5算法

. . .

相关推荐

额外说明

关于杰克逊

Jackson Jackson是一个开源的Java序列化和反序列化工具,可以将Java对象序列化为XML或JSON格式的字符串,以及将XML或JSON格式的字符串反序列化为Java对象。由于其使用简单,速度较快,且不依靠除JDK外的其他库,被众多用户所使

额外说明

PAT考试笔记02-多项式加法

一个萝卜一个坑 exp代表了数组下标,coef代表了系数,f【exp】代表了exp指数对应的系数,ccount代表了结果f3中非零项的个数,当f3每个单元的系数不为0的时候就直接输出完事了 #include <iostream> #include <a

额外说明

Redis 三种集群对比

    主从   哨兵   集群   sentinel模式基本可以满足一般生产的需求,具备高可用性。但是当数据量过大到一台服务器存放不下的情况时,主从模式或sentinel模式就不能满足需求了,这个时候需要对存储的数据进行分片,将数据存储到多个Redis

额外说明

thymeleaf模板引擎(绿色前台day01)

①. thymeleaf简介 1>. thymeleaf简介 1.什么是thymeleaf Thymeleaf是一个适用于Web和独立环境的现代服务器端Java模板引擎。SpringBoot 官网推荐使用的模板引擎是thymeleaf 2. thymel

额外说明

云原生向量数据库Milvus知识大全,看完这篇就够了[基本概念、系统架构、主要组件、应用场景]

1.Milvus简介 1.1什么是 Milvus Milvus 是一款云原生向量数据库,它具备高可用、高性能、易拓展的特点,用于海量向量数据的实时召回。 Milvus 基于 FAISS、Annoy、HNSW 等向量搜索库构建,核心是解决稠密向量相似度检索

额外说明

一文开启无监督学习之旅

1. 聚类分析简介 我们知道,机器学习本质上是一类优化问题——获取数据样本和目标函数,并尝试优化目标函数。在监督学习中,目标函数基于数据数据样本的标签,我们的目标是最小化模型预测和实际标签之间的差异,但在无监督学习中,我们并没有数据样本的标签。 本文主要

额外说明

【Java 基础篇】Java 泛型程序设计详解

文章目录 导言 一、泛型的概念 二、泛型类和泛型方法 1、泛型类 2、泛型方法 三、类型边界和通配符 1、类型边界 2、通配符 四、类型擦除和桥方法 五、泛型和反射 总结 导言 Java 泛型程序设计是 Java 5 版本引入的一项重要特性,它允许我们在

额外说明

Tampermonkey实践:安装引导及开发一个网页背景色更改插件

-作者简介,黑夜开发者,CSDN领军人物,全栈领域优质创作者✌,CSDN博客专家,阿里云社区专家博主,2023年6月csdn上海赛道top4。 -数年电商行业从业经验,历任核心研发工程师,项目技术负责人。 -本文已收录于专栏:100个JavaScript

额外说明

高质量论文推荐第三期(20230827)

文章目录 SeamlessM4T -大规模多语言和多模式机器翻译 StableVideo:文本驱动的一致性感知扩散视频编辑 GNU Radio上的开源LoRa物理层原型 ChatHaruhi:通过大语言模型在现实中复活动漫角色 Graph of Thou

额外说明

【从零开始学微服务】06.微服务架构的建设思路

大家好,欢迎来到万猫学社,跟我一起学,你也能成为微服务专家。 微服务看起来很美,但其实是需要一个技术体系或平台体系来支撑并且落地的。微服务架构建设分为两种思路: 框架模式 服务网格(Service Mesh)模式 接下来我们对上面的两个思路进行详细的介绍

ads via 小工具