id3决策树算法实例

⑴ ID3算法的介绍

ID3算法是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。

⑵ 实现ID3决策树学习算法

http://www.rulequest.com/download.html
http://www.rulequest.com/See5-demo.zip
这里有些。
Diversity(整体)-diversity(左节点)-diversity(右节点)，值越大，分割就越好。

三种diversity的指标：

1. min(P(c1),P(c2))

2. 2P(c1)P(c2)

3. [P(c1)logP(c1)]+[P(c2)logP(c2)]

这几个参数有相同的性质：当其中的类是均匀分布的时候，值最大；当有一个类的个数为0的时候，值为0。

选择分割的时候，对每个字段都考虑；对每个字段中的值先排序，然后再一一计算。最后选出最佳的分割。

树的生成：

错误率的衡量：最初生成的树中也是有错误率的！因为有些叶子节点并不是“Pure”的。

树的修剪：是不是当所以的叶子都很纯是，这棵树就能工作的很好呢?

修剪的要点是：应该回溯多少、如何从众多的子树总寻找最佳的。

1) 鉴别生成候选子树 ：使用一个调整的错误率。AE(T)=E(T)+aleaf_count(T)。一步步的生成一些候选子树。

2) 对子树的评估：通过test set找到最佳子树

3) 对最佳子树进行评估：使用evaluation set。

4) 考虑代价(cost)的问题

⑶ 决策树的算法

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
具体算法步骤如下；
1创建节点N
2如果训练集为空，在返回节点N标记为Failure
3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N
4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；
5for each 候选属性 attribute_list
6if 候选属性是连续的then
7对该属性进行离散化
8选择候选属性attribute_list中具有最高信息增益率的属性D
9标记节点N为属性D
10for each 属性D的一致值d
11由节点N长出一个条件为D=d的分支
12设s是训练集中D=d的训练样本的集合
13if s为空
14加上一个树叶，标记为训练集中最普通的类
15else加上一个有C4.5（R - {D},C，s）返回的点 背景：
分类与回归树(CART——Classification And Regression Tree)) 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。
分类与回归树CART 模型最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显着。模型的关键是预测准则的构建，准确的。
定义：
分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。

⑷ 通过ID3算法得出的决策树怎么去测试别的实例啊还有ID3算法是只能分析数值型的数据吗

如果通过训练集已经得出决策树的话， 那使用测试集测试就很简单了。 可以人工测试，也可以用数据分析软件。

数据可以有很多种类型，关键是看你怎么提取出数据的属性进行分析。

请采纳最佳答案~

⑸ 以汽车保险为例:假定训练数据库具有两个属性:年龄和汽车类型。 使用ID3算法得到一个决策树,怎么画

咨询记录 · 回答于2021-10-18

⑹ 决策树之ID3算法及其python实现

决策树之ID3算法及其Python实现

1. 决策树背景知识
??决策树是数据挖掘中最重要且最常用的方法之一，主要应用于数据挖掘中的分类和预测。决策树是知识的一种呈现方式，决策树中从顶点到每个结点的路径都是一条分类规则。决策树算法最先基于信息论发展起来，经过几十年发展，目前常用的算法有：ID3、C4.5、CART算法等。
2. 决策树一般构建过程
??构建决策树是一个自顶向下的过程。树的生长过程是一个不断把数据进行切分细分的过程，每一次切分都会产生一个数据子集对应的节点。从包含所有数据的根节点开始，根据选取分裂属性的属性值把训练集划分成不同的数据子集，生成由每个训练数据子集对应新的非叶子节点。对生成的非叶子节点再重复以上过程，直到满足特定的终止条件，停止对数据子集划分，生成数据子集对应的叶子节点，即所需类别。测试集在决策树构建完成后检验其性能。如果性能不达标，我们需要对决策树算法进行改善，直到达到预期的性能指标。
??注：分裂属性的选取是决策树生产过程中的关键，它决定了生成的决策树的性能、结构。分裂属性选择的评判标准是决策树算法之间的根本区别。
3. ID3算法分裂属性的选择——信息增益
??属性的选择是决策树算法中的核心。是对决策树的结构、性能起到决定性的作用。ID3算法基于信息增益的分裂属性选择。基于信息增益的属性选择是指以信息熵的下降速度作为选择属性的方法。它以的信息论为基础，选择具有最高信息增益的属性作为当前节点的分裂属性。选择该属性作为分裂属性后，使得分裂后的样本的信息量最大，不确定性最小，即熵最小。
??信息增益的定义为变化前后熵的差值，而熵的定义为信息的期望值，因此在了解熵和信息增益之前，我们需要了解信息的定义。
??信息：分类标签xi 在样本集 S 中出现的频率记为 p(xi)，则 xi 的信息定义为：?log2p(xi) 。
??分裂之前样本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 为分类标签的个数。
??通过属性A分裂之后样本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始样本集通过属性A的属性值划分为 m 个子样本集，|Sj| 表示第j个子样本集中样本数量，|S| 表示分裂之前数据集中样本总数量。
??通过属性A分裂之后样本集的信息增益：InfoGain(S,A)=E(S)?EA(S)
??注：分裂属性的选择标准为：分裂前后信息增益越大越好，即分裂后的熵越小越好。
4. ID3算法
??ID3算法是一种基于信息增益属性选择的决策树学习方法。核心思想是：通过计算属性的信息增益来选择决策树各级节点上的分裂属性，使得在每一个非叶子节点进行测试时，获得关于被测试样本最大的类别信息。基本方法是：计算所有的属性，选择信息增益最大的属性分裂产生决策树节点，基于该属性的不同属性值建立各分支，再对各分支的子集递归调用该方法建立子节点的分支，直到所有子集仅包括同一类别或没有可分裂的属性为止。由此得到一棵决策树，可用来对新样本数据进行分类。
ID3算法流程：
(1) 创建一个初始节点。如果该节点中的样本都在同一类别，则算法终止，把该节点标记为叶节点，并用该类别标记。
(2) 否则，依据算法选取信息增益最大的属性，该属性作为该节点的分裂属性。
(3) 对该分裂属性中的每一个值，延伸相应的一个分支，并依据属性值划分样本。
(4) 使用同样的过程，自顶向下的递归，直到满足下面三个条件中的一个时就停止递归。
??A、待分裂节点的所有样本同属于一类。
??B、训练样本集中所有样本均完成分类。
??C、所有属性均被作为分裂属性执行一次。若此时，叶子结点中仍有属于不同类别的样本时，选取叶子结点中包含样本最多的类别，作为该叶子结点的分类。
ID3算法优缺点分析
优点：构建决策树的速度比较快，算法实现简单，生成的规则容易理解。
缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性；不能处理属性值连续的属性；无修剪过程，无法对决策树进行优化，生成的决策树可能存在过度拟合的情况。

⑺ 常见决策树分类算法都有哪些

在机器学习中，有一个体系叫做决策树，决策树能够解决很多问题。在决策树中，也有很多需要我们去学习的算法，要知道，在决策树中，每一个算法都是实用的算法，所以了解决策树中的算法对我们是有很大的帮助的。在这篇文章中我们就给大家介绍一下关于决策树分类的算法，希望能够帮助大家更好地去理解决策树。
1.C4.5算法
C4.5算法就是基于ID3算法的改进，这种算法主要包括的内容就是使用信息增益率替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理；使用k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性等内容，这种算法是一个十分使用的算法。
2.CLS算法
CLS算法就是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。
3.ID3算法
ID3算法就是对CLS算法的最大改进是摒弃了属性选择的随机性，利用信息熵的下降速度作为属性选择的度量。ID3是一种基于信息熵的决策树分类学习算法，以信息增益和信息熵，作为对象分类的衡量标准。ID3算法结构简单、学习能力强、分类速度快适合大规模数据分类。但同时由于信息增益的不稳定性，容易倾向于众数属性导致过度拟合，算法抗干扰能力差。
3.1.ID3算法的优缺点
ID3算法的优点就是方法简单、计算量小、理论清晰、学习能力较强、比较适用于处理规模较大的学习问题。缺点就是倾向于选择那些属性取值比较多的属性，在实际的应用中往往取值比较多的属性对分类没有太大价值、不能对连续属性进行处理、对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。
3.2.ID3算法的核心思想
根据样本子集属性取值的信息增益值的大小来选择决策属性，并根据该属性的不同取值生成决策树的分支，再对子集进行递归调用该方法，当所有子集的数据都只包含于同一个类别时结束。最后，根据生成的决策树模型，对新的、未知类别的数据对象进行分类。
在这篇文章中我们给大家介绍了决策树分类算法的具体内容，包括有很多种算法。从中我们不难发现决策树的算法都是经过不不断的改造趋于成熟的。所以说，机器学习的发展在某种程度上就是由于这些算法的进步而来的。

⑻ 用python实现红酒数据集的ID3,C4.5和CART算法

ID3算法介绍
ID3算法全称为迭代二叉树3代算法（Iterative Dichotomiser 3）
该算法要先进行特征选择，再生成决策树，其中特征选择是基于“信息增益”最大的原则进行的。
但由于决策树完全基于训练集生成的，有可能对训练集过于“依赖”，即产生过拟合现象。因此在生成决策树后，需要对决策树进行剪枝。剪枝有两种形式，分别为前剪枝（Pre-Pruning）和后剪枝（Post-Pruning），一般采用后剪枝。
信息熵、条件熵和信息增益
信息熵：来自于香农定理，表示信息集合所含信息的平均不确定性。信息熵越大，表示不确定性越大，所含的信息量也就越大。
设x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x
1

,x
2

,x
3

,...x
n

为信息集合X的n个取值，则x i x_ix
i

的概率：
P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n
P(X=i)=p
i

,i=1,2,3,...,n

信息集合X的信息熵为：
H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}
H(X)=−
i=1
∑
n

p
i

logp
i

条件熵：指已知某个随机变量的情况下，信息集合的信息熵。
设信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y
1

,y
2

,y
3

,...y
m

组成的随机变量集合Y，则随机变量（X，Y）的联合概率分布为
P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}
P(x=i,y=j)=p
ij

条件熵：
H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}
H(X∣Y)=
j=1
∑
m

p(y
j

)H(X∣y
j

)
由
H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ⁡ p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}
H(X∣y
j

)=−
j=1
∑
m

p(y
j

)
i=1
∑
n

p(x
i

∣y
j

)logp(x
i

∣y
j

)
和贝叶斯公式：
p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)
p(x
i

y
j

)=p(x
i

∣y
j

)p(y
j

)
可以化简条件熵的计算公式为:
H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ⁡ p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}
H(X∣Y)=
j=1
∑
m

i=1
∑
n

p(x
i

,y
j

)log
p(x
i

,y
j

)
p(x
i

)

信息增益：信息熵-条件熵，用于衡量在知道已知随机变量后，信息不确定性减小越大。
d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)
d(X,Y)=H(X)−H(X∣Y)

python代码实现
import numpy as np
import math

def calShannonEnt(dataSet):
""" 计算信息熵 """
labelCountDict = {}
for d in dataSet:
label = d[-1]
if label not in labelCountDict.keys():
labelCountDict[label] = 1
else:
labelCountDict[label] += 1
entropy = 0.0
for l, c in labelCountDict.items():
p = 1.0 * c / len(dataSet)
entropy -= p * math.log(p, 2)
return entropy

def filterSubDataSet(dataSet, colIndex, value):
"""返回colIndex特征列label等于value，并且过滤掉改特征列的数据集"""
subDataSetList = []
for r in dataSet:
if r[colIndex] == value:
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
subDataSetList.append(newR)
return np.array(subDataSetList)

def chooseFeature(dataSet):
""" 通过计算信息增益选择最合适的特征"""
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeatureIndex = -1
for i in range(featureNum):
uniqueValues = np.unique(dataSet[:, i])
condition_entropy = 0.0

for v in uniqueValues: #计算条件熵
subDataSet = filterSubDataSet(dataSet, i, v)
p = 1.0 * len(subDataSet) / len(dataSet)
condition_entropy += p * calShannonEnt(subDataSet)
infoGain = entropy - condition_entropy #计算信息增益

if infoGain >= bestInfoGain: #选择最大信息增益
bestInfoGain = infoGain
bestFeatureIndex = i
return bestFeatureIndex

def creatDecisionTree(dataSet, featNames):
""" 通过训练集生成决策树 """
featureName = featNames[:] # 拷贝featNames，此处不能直接用赋值操作，否则新变量会指向旧变量的地址
classList = list(dataSet[:, -1])
if len(set(classList)) == 1: # 只有一个类别
return classList[0]
if dataSet.shape[1] == 1: #当所有特征属性都利用完仍然无法判断样本属于哪一类，此时归为该数据集中数量最多的那一类
return max(set(classList), key=classList.count)

bestFeatureIndex = chooseFeature(dataSet) #选择特征
bestFeatureName = featNames[bestFeatureIndex]
del featureName[bestFeatureIndex] #移除已选特征列
decisionTree = {bestFeatureName: {}}

featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已选特征列所包含的类别， 通过递归生成决策树
for v in featureValueUnique:
FeatureName = featureName[:]
subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, FeatureName)
return decisionTree

def classify(decisionTree, featnames, featList):
""" 使用训练所得的决策树进行分类 """
classLabel = None
root = decisionTree.keys()[0]
firstGenDict = decisionTree[root]
featIndex = featnames.index(root)
for k in firstGenDict.keys():
if featList[featIndex] == k:
if isinstance(firstGenDict[k], dict): #若子节点仍是树，则递归查找
classLabel = classify(firstGenDict[k], featnames, featList)
else:
classLabel = firstGenDict[k]
return classLabel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
下面用鸢尾花数据集对该算法进行测试。由于ID3算法只能用于标称型数据，因此用在对连续型的数值数据上时，还需要对数据进行离散化，离散化的方法稍后说明，此处为了简化，先使用每一种特征所有连续性数值的中值作为分界点，小于中值的标记为1，大于中值的标记为0。训练1000次，统计准确率均值。

from sklearn import datasets
from sklearn.model_selection import train_test_split

iris = datasets.load_iris()
data = np.c_[iris.data, iris.target]

scoreL = []
for i in range(1000): #对该过程进行10000次
trainData, testData = train_test_split(data) #区分测试集和训练集

featNames = iris.feature_names[:]
for i in range(trainData.shape[1] - 1): #对训练集每个特征，以中值为分界点进行离散化
splitPoint = np.mean(trainData[:, i])
featNames[i] = featNames[i]+'<='+'{:.3f}'.format(splitPoint)
trainData[:, i] = [1 if x <= splitPoint else 0 for x in trainData[:, i]]
testData[:, i] = [1 if x <= splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
print 'score: ', np.mean(scoreL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输出结果为：score: 0.7335，即准确率有73%。每次训练和预测的准确率分布如下：

数据离散化
然而，在上例中对特征值离散化的划分点实际上过于“野蛮”，此处介绍一种通过信息增益最大的标准来对数据进行离散化。原理很简单，当信息增益最大时，说明用该点划分能最大程度降低数据集的不确定性。
具体步骤如下：

对每个特征所包含的数值型特征值排序
对相邻两个特征值取均值，这些均值就是待选的划分点
用每一个待选点把该特征的特征值划分成两类，小于该特征点置为1， 大于该特征点置为0，计算此时的条件熵，并计算出信息增益
选择信息使信息增益最大的划分点进行特征离散化
实现代码如下：

def filterRawData(dataSet, colIndex, value, tag):
""" 用于把每个特征的连续值按照区分点分成两类，加入tag参数，可用于标记筛选的是哪一部分数据"""
filterDataList = []
for r in dataSet:
if (tag and r[colIndex] <= value) or ((not tag) and r[colIndex] > value):
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
filterDataList.append(newR)
return np.array(filterDataList)

def dataDiscretization(dataSet, featName):
""" 对数据每个特征的数值型特征值进行离散化 """
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)

for featIndex in range(featureNum): #对于每一个特征
uniqueValues = sorted(np.unique(dataSet[:, featIndex]))
meanPoint = []

for i in range(len(uniqueValues) - 1): # 求出相邻两个值的平均值
meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)
bestInfoGain = 0.0
bestMeanPoint = -1
for mp in meanPoint: #对于每个划分点
subEntropy = 0.0 #计算该划分点的信息熵
for tag in range(2): #分别划分为两类
subDataSet = filterRawData(dataSet, featIndex, mp, tag)
p = 1.0 * len(subDataSet) / len(dataSet)
subEntropy += p * calShannonEnt(subDataSet)

## 计算信息增益
infoGain = entropy - subEntropy
## 选择最大信息增益
if infoGain >= bestInfoGain:
bestInfoGain = infoGain
bestMeanPoint = mp
featName[featIndex] = featName[featIndex] + "<=" + "{:.3f}".format(bestMeanPoint)
dataSet[:, featIndex] = [1 if x <= bestMeanPoint else 0 for x in dataSet[:, featIndex]]
return dataSet, featName
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
重新对数据进行离散化，并重复该步骤1000次，同时用sklearn中的DecisionTreeClassifier对相同数据进行分类，分别统计平均准确率。运行代码如下:

from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
scoreL = []
scoreL_sk = []
for i in range(1000): #对该过程进行1000次
featNames = iris.feature_names[:]
trainData, testData = train_test_split(data) #区分测试集和训练集
trainData_tmp = .(trainData)
testData_tmp = .(testData)
discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根据信息增益离散化
for i in range(testData.shape[1]-1): #根据测试集的区分点离散化训练集
splitPoint = float(discritizationFeatName[i].split('<=')[-1])
testData[:, i] = [1 if x<=splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

clf = DecisionTreeClassifier('entropy')
clf.fit(trainData[:, :-1], trainData[:, -1])
clf.predict(testData[:, :-1])
scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))

print 'score: ', np.mean(scoreL)
print 'score-sk: ', np.mean(scoreL_sk)
fig = plt.figure(figsize=(10, 4))
plt.subplot(1,2,1)
pd.Series(scoreL).hist(grid=False, bins=10)
plt.subplot(1,2,2)
pd.Series(scoreL_sk).hist(grid=False, bins=10)
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
两者准确率分别为：
score: 0.7037894736842105
score-sk: 0.7044736842105263

准确率分布如下：

两者的结果非常一样。
（但是。。为什么根据信息熵离散化得到的准确率比直接用均值离散化的准确率还要低啊？？哇的哭出声。。）

最后一次决策树图形如下：

决策树剪枝
由于决策树是完全依照训练集生成的，有可能会有过拟合现象，因此一般会对生成的决策树进行剪枝。常用的是通过决策树损失函数剪枝，决策树损失函数表示为:
C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|
C
a

(T)=
t=1
∑
T

N
t

H
t

(T)+α∣T∣

其中，H t ( T ) H_t(T)H
t

(T)表示叶子节点t的熵值，T表示决策树的深度。前项∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑
t=1
T

N
t

H
t

(T)是决策树的经验损失函数当随着T的增加，该节点被不停的划分的时候，熵值可以达到最小，然而T的增加会使后项的值增大。决策树损失函数要做的就是在两者之间进行平衡，使得该值最小。
对于决策树损失函数的理解，如何理解决策树的损失函数? - 陶轻松的回答 - 知乎这个回答写得挺好，可以按照答主的思路理解一下

C4.5算法
ID3算法通过信息增益来进行特征选择会有一个比较明显的缺点：即在选择的过程中该算法会优先选择类别较多的属性（这些属性的不确定性小，条件熵小，因此信息增益会大），另外，ID3算法无法解决当每个特征属性中每个分类都只有一个样本的情况（此时每个属性的条件熵都为0）。
C4.5算法ID3算法的改进，它不是依据信息增益进行特征选择，而是依据信息增益率，它添加了特征分裂信息作为惩罚项。定义分裂信息：
S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ⁡ ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}
SplitInfo(X,Y)=−
i
∑
n

∣X∣
∣X
i

∣

log
∣X∣
∣X
i

∣

则信息增益率为：
G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}
GainRatio(X,Y)=
SplitInfo(X,Y)
d(X,Y)

关于ID3和C4.5算法
在学习分类回归决策树算法时，看了不少的资料和博客。关于这两个算法，ID3算法是最早的分类算法，这个算法刚出生的时候其实带有很多缺陷：

无法处理连续性特征数据
特征选取会倾向于分类较多的特征
没有解决过拟合的问题
没有解决缺失值的问题
即该算法出生时是没有带有连续特征离散化、剪枝等步骤的。C4.5作为ID3的改进版本弥补列ID3算法不少的缺陷：

通过信息最大增益的标准离散化连续的特征数据
在选择特征是标准从“最大信息增益”改为“最大信息增益率”
通过加入正则项系数对决策树进行剪枝
对缺失值的处理体现在两个方面：特征选择和生成决策树。初始条件下对每个样本的权重置为1。
特征选择：在选取最优特征时，计算出每个特征的信息增益后，需要乘以一个**“非缺失值样本权重占总样本权重的比例”**作为系数来对比每个特征信息增益的大小
生成决策树：在生成决策树时，对于缺失的样本我们按照一定比例把它归属到每个特征值中，比例为该特征每一个特征值占非缺失数据的比重
关于C4.5和CART回归树
作为ID3的改进版本，C4.5克服了许多缺陷，但是它自身还是存在不少问题：

C4.5的熵运算中涉及了对数运算，在数据量大的时候效率非常低。
C4.5的剪枝过于简单
C4.5只能用于分类运算不能用于回归
当特征有多个特征值是C4.5生成多叉树会使树的深度加深
————————————————
版权声明：本文为CSDN博主“Sarah Huang”的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_44794704/article/details/89406612

⑼ 决策树算法的典型算法

决策树的典型算法有ID3，C4.5，CART等。
国际权威的学术组织，数据挖掘国际会议ICDM （the IEEE International Conference on Data Mining）在2006年12月评选出了数据挖掘领域的十大经典算法中，C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法产生的分类规则易于理解，准确率较高。不过在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，在实际应用中因而会导致算法的低效。
决策树算法的优点如下：
（1）分类精度高；
（2）生成的模式简单；
（3）对噪声数据有很好的健壮性。
因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。

⑽ 简述ID3算法基本原理和步骤

1.基本原理：
以信息增益/信息熵为度量，用于决策树结点的属性选择的标准，每次优先选取信息量最多（信息增益最大）的属性，即信息熵值最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0。（信息熵 无条件熵 条件熵 信息增益 请查找其他资料理解）
决策树将停止生长条件及叶子结点的类别取值：
①数据子集的每一条数据均已经归类到每一类，此时，叶子结点取当前样本类别值。
②数据子集类别仍有混乱，但已经找不到新的属性进行结点分解，此时，叶子结点按当前样本中少数服从多数的原则进行类别取值。
③数据子集为空，则按整个样本中少数服从多数的原则进行类别取值。

步骤：
理解了上述停止增长条件以及信息熵，步骤就很简单