决策树 ID3 算法中选择分区背后的直觉

关键词：

【中文标题】决策树 ID3 算法中选择分区背后的直觉【英文标题】：Intuition behind choosing partition in decision tree ID3 algorithm 【发布时间】：2016-07-06 11:05:36 【问题描述】：

我试图理解机器学习中决策树分类器背后的直觉。我知道决策树中每个节点的目标是进一步划分可能标签的当前空间，以便根据对该节点给定问题的回答尽可能多地消除候选标签。但是，这与基于最小化分区“熵”的属性选择分区有什么关系呢？其中“熵”定义如下：

H(S) = −p_1*log2(p_1) −... −p_n*log2(p_n)

和分区熵：

H = q_1*H(S_1) +...+ q_m*H(S_m)

with H(S): entropy of a given subset
     H: partition entropy
     p_i's: proportions of data belonging to class i
     q_i's: proportions of data belonging to subset i based on given partition

此外，每个节点的“问题”是否必须是一个是/否问题，从而将当前标签空间分成 2 个？与 3 个或更多子集相反？任何明确的例子将不胜感激。

【问题讨论】：

【参考方案1】：

。但是，这与基于最小化分区“熵”的属性选择分区有什么关系呢？

熵（这里是香农熵）是一种不确定性的度量，它简单地表达了你的每类分离的清晰程度。如果熵很高 - 那么有很多来自不同类别的样本，因此在这个特征中进行拆分将是有价值的，因为显然需要更多的决策规则来分离对象。另一方面，如果熵很小——节点已经主要由一个类的样本组成，因此进一步分裂没有意义。特别是当其中一个类的概率等于 1 时，您将获得 0 熵，因此获得最小值，如果您在此处创建叶子，则有 100% 的机会正确分类。

另外，每个节点的“问题”是否必须是是/否问题，从而将当前标签空间分成 2 个？

不，您可以轻松创建具有任意数量子级的决策树。从计算的角度来看，简单地分成两部分要简单得多（量化是否有一个好的分裂点比是否有多个共同创造好的分裂点更容易量化）。特别是这也是为什么您可以有效地学习线性分类器（如逻辑回归、感知器、支持向量机）而不是多阈值线性分类器（如多阈值熵线性分类器）的原因 - 构建多阈值模型要复杂得多，但仍然 - 可能并且在某些情况下是有利的。

【讨论】：

我仍然对第一部分感到困惑。您说“如果熵很高......因此拆分此功能很有价值”，但不是根据选择最小化分区熵（第二个公式）的分区来选择特定分区吗？至少这是我从书中学到的。 好吧，不。您始终选择具有 最高 值的节点，例如参见 people.cs.pitt.edu/~milos/courses/cs2750-Spring04/lectures/…。目标是让树的熵最小，因此（因为这通常是一种贪婪的学习）你会找到具有最高的节点，然后将其拆分以减少它。 【参考方案2】：

决策树算法

此算法适用于分类器和回归器。

分类器演示

import pandas as pd

import numpy as np

import matplotlib.pyplot as plt

from sklearn.tree import DecisionTreeClassifier

from sklearn.tree import export_graphviz

from sklearn.model_selection import train_test_split


df=pd.read_csv("D:\\heart.csv")

iris="data":np.array(df[["age","sex","cp","trestbps","chol","fbs","restecg","thalach","exang","oldpeak","slope","ca","thal"]],ndmin=2),"target":np.array(df["target"]),"target_names":np.array(["No_problem","Problem"])

X_train,X_test,Y_train,Y_test=train_test_split(iris["data"],iris["target"],random_state=0
)

dt=DecisionTreeClassifier(criterion="gini",random_state=100,max_depth=10,min_samples_leaf=2)

dt.fit(X_train,Y_train)

x_new=np.array([[71,0,0,112,149,0,1,125,0,1.6,1,0,2]])

prediction=dt.predict(x_new)

print("The value is : \n".format(prediction))

print("The name is : \n".format(iris["target_names"][prediction]))

print("Accurecy is : :.2f".format(dt.score(X_train,Y_train)*100))

【讨论】：

欢迎来到 SO！当您发布答案时，请尝试解释一下。

catboost算法中对称树背后的直觉是啥？

】catboost算法中对称树背后的直觉是啥？【英文标题】：Whatistheintuitionbehindsymmetrictreesincatboostalgorithm?catboost算法中对称树背后的直觉是什么？【发布时间】：2018-10-0918:46:30【问题描述】：我一直在使用catboost算法，我很难理解使... 查看详情

sparkmllib回归算法之决策树

SparkMLlib回归算法之决策树（一），决策树概念1，决策树算法（ID3，C4.5，CART）之间的比较：　　1，ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性... 查看详情

分类算法：决策树（c4.5）(转)

C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法，相比于ID3算法，改进有如下几个要点： 1）用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来... 查看详情

决策树算法

　决策树算法在机器学习中算是很经典的一个算法系列了。它既可以作为分类算法，也可以作为回归算法，同时也特别适合集成学习比如随机森林。本文就对决策树算法原理做一个总结，上篇对ID3，C4.5的算法思想做了总结，下... 查看详情

决策树算法

利用ID3算法来判断某天是否适合打网球。（1）类别属性信息熵的计算由于未分区前，训练数据集中共有14个实例，    其中有9个实例属于yes类（适合打网球的），5个实例属于no类（不适合打网球），   &n... 查看详情

5.10决策树与id3算法

参考技术Ahttps://blog.csdn.net/dorisi_h_n_q/article/details/82787295决策树（decisiontree）是一个树结构（可以是二叉树或非二叉树）。决策过程是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点... 查看详情

决策树——id3算法

...xff0c;有一系列的算法得以脱颖而出——“回归分析”、“决策树”、“人工神经网络”等等那么今天我就来介绍一下”决策树“——ID3算法一、ID3算法ID3作为一种经典的决策树算法，是 查看详情

5-3决策树id3决策树的生成算法(代码片段)

ID3算法在决策树各个结点上应该信息增益准则选择特征，递归地构建决策树输入训练数据集D特征集A阈值ϵ\\epsilonϵ输出决策树T过程若D中所有实例属于同一类CkC_kCk​，则T为单结点树，并将类，则T为单结点树，... 查看详情

十大经典算法

...大经典算法：一、C4.5C4.5，是机器学习算法中的一个分类决策树算法，它是决策树(决策树也就是做决策的节点间的组织方式像一棵树，其实是一个倒树)核心算法，ID3的改进算法，所以基本上了解了一半决策树构造方法就能构造... 查看详情

决策树分类算法（id3）

1.什么是决策树/判定树（decisiontree)?      判定树是一个类似于流程图的树结构：其中，每个内部结点表示在一个属性上的测试，每个分支代表一个属性输出，而每个树叶结点代表类或类分布。树的最顶层是... 查看详情

决策树之id3算法(代码片段)

概述ID3算法是构建决策树算法中一种非常重要的算法，可以说它是学习决策树算法的基础吧。比如，下一篇博客要说的C4.5决策树，就是基于ID3上的一个改进算法。还有CART、随机森林算法，都是后面要讲解的。版... 查看详情

机器学习：决策树(decisiontree)--id3算法(代码片段)

决策树的主要算法构建决策树的关键：按照什么样的次序来选择变量（属性/特征）作为分类依据。根据不同的目标函数，建立决策树主要有以下三种算法ID3(J.RossQuinlan-1975)核心：信息熵，信息增益C4.5——ID... 查看详情

决策树之id3算法(代码片段)

概述ID3算法是构建决策树算法中一种非常重要的算法，可以说它是学习决策树算法的基础吧。比如，下一篇博客要说的C4.5决策树，就是基于ID3上的一个改进算法。还有CART、随机森林算法，都是后面要讲解的。版... 查看详情

决策树

（1）建树  1.选择属性    ID3算法用的是信息增益，C4.5算法用信息增益率；CART算法使用基尼系数 2.选择属性的最优分割点   ID3算法：使用信息增益作为分裂的规则，信息增益越大，则选取该... 查看详情

决策树--id3算法小结

...eDichotomiser3迭代二叉树3代)，是一个由RossQuinlan发明的用于决策树的算法；简单理论是越是小型的决策树越优于大的决策树。算法归纳：1、使用所有没有使用的属性并计算与之相关的样本熵值；2、选取其中熵值最小的属性3、生成... 查看详情

决策树算法cart和c4.5决策树有啥区别？各用于啥领域？

...计算GINI系数，GINI系数，GINI系数越小则划分越合理。2、决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本... 查看详情

id3决策树算法|机器学习(代码片段)

目录1.ID3决策树原理1.1基本原理1.2信息熵1.3条件熵1.4信息增益2.代码实现2.1计算信息熵calEnt2.2获得数据子集splitdataset2.3获得最优特征索引2.4处理样本中只有一个特征或者特征都一样的情况2.5创建ID3决策树2.6返回一条测试数据的标... 查看详情

决策树--c4.5算法

C4.5是另一个分类决策树算法，是基于ID3算法的改进，改进点如下：1、分离信息 解释：数据集通过条件属性A的分离信息，其实和ID3中的熵； 2、信息增益率 解释：Gain(A)为获的A的信息增益，C4.5中选择具有最大增益率... 查看详情