概述
目录
Hunt算法：
ID3算法
信息熵 (Entropy)
数据集的信息熵
使用熵衡量数据纯度
按照条件进行划分的信息熵
信息增益
C4.5算法
改进1：信息增益的问题
改进2：连续值属性与分裂点
改进3： C4.5中缺失值的处理
改进4：学习过程中的过度拟合
决策树剪枝
从决策树导出产生式规则
CART决策树
分类树---GINI值
回归树---回归方差
分类树与回归树的构建
CART如何分裂成一个二叉树
CART如何剪枝
CHAID决策树
决策树算法总结
决策树基本概念
决策树的基本原理
决策树特点
对数据的要求
决策树的优势
sklearn
• 什么是决策树？
– 从训练数据中学习得出一个类似于流程图的树型结构
– 根、儿子、叶子、深度的概念
– 每个儿子结点表示在一个属性上的测试
– 每个叶子结点表示一种决策结果
• 决策树的生成由两个阶段组成
– 决策树构建
• 如何选择属性（顺序、连续属性的离散化、阈值）
– 剪枝
• 许多分枝反映的是训练数据中的噪声和孤立点，可剪去
• 决策树的意义
– 分析分类结果与各属性之间的内在联系，形成模型
– 运用模型对未知样本进行分类预测
有许多决策树算法：
- hunt算法
- 信息增益--Information gain (ID3)
- 增益比率--Gain ration(C4.5)
- 基尼系数--Gini index(CART)
- 卡方检验--CHAID决策树
Hunt算法：
bug:如何去选最优属性？
ID3算法
ID3算法主要针对属性选择问题
• 使用信息增益度选择测试属性
1 决定分类属性集合；
2 对目前的数据表，建立一个节点N
3 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类(纯的类别)
4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别(不纯的类别)
5 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性
6 节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏
7如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树
信息熵 (Entropy)
信息熵的概念:解决了信息的度量问题，量化出信息的作用
信息量就等于不确定性的多少
信息量的比特数和所有可能情况的对数有关
香农指出，它的准确信息量应该是
p1,p2,...,p32分别是概率，香农把它称作信息熵，单位为比特；
对于任意一个随机变量X，它的熵定义为:
变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大
数据集的信息熵
设数据集D中有m个不同的类C1, C2, C3, ..., Cm
设
是数据集D中Ci类的样本的集合, |D|和 |
|分别是D和 
中的样本个数
数据集D的信息熵:
其中pi是数据集D中任意样本属于类Ci的概率，用
估计
使用熵衡量数据纯度
假设有一个数据集合D，其中只有两个类，一个是正例类，一个是负例类计算D中正例类和负例类在三种不同的组分下熵的变化情况。
（1）D中包含有20%的正例和80%的负例。
H(D) = -0.2 * log20.2 - 0.8 * log20.8 = 0.722
（2）D中包含有50%的正例和50%的负例。
H(D) = -0.5 * log20.5 - 0.5 * log20.5 = 1
（3）D中包含有100%的正例和0%的负例。
H(D) = -1 * log21 - 0 * log20 =0
可以看到一个趋势，当数据变得越来越“纯”时，熵的值变得越来越小。当D中正反例所占比例相同时，熵取最大值。当D 中所有数据都只属于一个类时，熵得到最小值。因此熵可以作为数据纯净度或混乱度的衡量指标。这正是决策树学习中需要的
按照条件进行划分的信息熵
假设按属性 A 划分 D 中的样本，且属性 A 根据训练数据的观测具有 v个不同取值{ a1, a2, ..., aj , ..., av }。
如果 A 是离散值，可依属性 A 将 D 划分为 v 个子集 { D1, D2, ...,Dj , ..., Dv }
其中，Dj为D中的样本子集，它们在A上具有属性值aj
这些划分将对应于从该节点A出来的分支。
按属性A对D划分后，数据集的信息熵:
其中， 
充当第 j 个划分的权重。InfoA(D)越小，表示划分的纯度越高
信息增益
它首先对数据进行处理，利用归纳法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树技术发现数据模式和规则的核心是采用递归分割的贪婪算
代码
import numpy as np
def createDataSet():
"""
outlook-> 0: sunny | 1: overcast | 2: rain
temperature-> 0: hot | 1: mild | 2: cool
humidity-> 0: high | 1: normal
windy-> 0: false | 1: true
"""
dataSet = np.array([[0, 0, 0, 0, 'N'],
[0, 0, 0, 1, 'N'],
[1, 0, 0, 0, 'Y'],
[2, 1, 0, 0, 'Y'],
[2, 2, 1, 0, 'Y'],
[2, 2, 1, 1, 'N'],
[1, 2, 1, 1, 'Y']])
labels = np.array(['outlook', 'temperature', 'humidity', 'windy'])
return dataSet, labels
def createTestSet():
"""
outlook-> 0: sunny | 1: overcast | 2: rain
temperature-> 0: hot | 1: mild | 2: cool
humidity-> 0: high | 1: normal
windy-> 0: false | 1: true
"""
testSet = np.array([[0, 1, 0, 0],
[0, 2, 1, 0],
[2, 1, 1, 0],
[0, 1, 1, 1],
[1, 1, 0, 1],
[1, 0, 1, 0],
[2, 1, 0, 1]])
return testSet
def dataset_entropy(dataset):
print(dataset[:,-1])
classLabel = dataset[:,-1]
labelCount = {}
for i in range(classLabel.size):
label = classLabel[i]
labelCount[label]=labelCount.get(label,0)+1
#熵值
ent=0
for k,v in labelCount.items():
ent+=-v/classLabel.size*np.log2(v/classLabel.size)
return ent
def splitDataSet(dataset,featureIndex):
#划分后的子集
subdataset=[]
featureValues = dataset[:,featureIndex]
featureSet = list(set(featureValues))
for i in range(len(featureSet)):
newset=[]
for j in range(dataset.shape[0]):
if featureSet[i]==featureValues[j]:
newset.append(dataset[j,:])
newset =np.delete(newset,featureIndex,axis=1)
subdataset.append(np.array(newset))
return subdataset
if __name__=="__main__":
dataset,labels = createDataSet()
# print(dataset_entropy(dataset))
s = splitDataSet(dataset,0)
for item in s:
print(item)import numpy as np
import operator
def createDataSet():
"""
outlook-> 0: sunny | 1: overcast | 2: rain
temperature-> 0: hot | 1: mild | 2: cool
humidity-> 0: high | 1: normal
windy-> 0: false | 1: true
"""
dataSet = np.array([[0, 0, 0, 0, 'N'],
[0, 0, 0, 1, 'N'],
[1, 0, 0, 0, 'Y'],
[2, 1, 0, 0, 'Y'],
[2, 2, 1, 0, 'Y'],
[2, 2, 1, 1, 'N'],
[1, 2, 1, 1, 'Y']])
labels = np.array(['outlook', 'temperature', 'humidity', 'windy'])
return dataSet, labels
def createTestSet():
"""
outlook-> 0: sunny | 1: overcast | 2: rain
temperature-> 0: hot | 1: mild | 2: cool
humidity-> 0: high | 1: normal
windy-> 0: false | 1: true
"""
testSet = np.array([[0, 1, 0, 0],
[0, 2, 1, 0],
[2, 1, 1, 0],
[0, 1, 1, 1],
[1, 1, 0, 1],
[1, 0, 1, 0],
[2, 1, 0, 1]])
return testSet
def dataset_entropy(dataset):
classLabel = dataset[:,-1]
labelCount = {}
for i in range(classLabel.size):
label = classLabel[i]
labelCount[label]=labelCount.get(label,0)+1
#熵值
ent=0
for k,v in labelCount.items():
ent+=-v/classLabel.size*np.log2(v/classLabel.size)
return ent
def splitDataSet(dataset,featureIndex,value):
subdataset = []
for example in dataset:
if example[featureIndex]==value:
subdataset.append(example)
return np.delete(subdataset,featureIndex,axis=1)
def chooseBestFeature(dataset,labels):
#特征的个数
featureNum = labels.size
#最小熵值
minEntropy,bestFeatureIndex=1,None
#样本的总数
n = dataset.shape[0]
for i in range(featureNum):
#指定特征的条件熵
featureEntropy =0
#返回所有子集
featureList = dataset[:, i]
featureValues = set(featureList)
for value in featureValues:
subDataSet = splitDataSet(dataset,i,value)
featureEntropy+=subDataSet.shape[0]/n*dataset_entropy(subDataSet)
if minEntropy>featureEntropy:
minEntropy = featureEntropy
bestFeatureIndex = i
print(minEntropy)
return bestFeatureIndex
def mayorClass(classList):
labelCount = {}
for i in range(classList.size):
label = classList[i]
labelCount[label] = labelCount.get(label, 0) + 1
sortedLabel = sorted(labelCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedLabel[0][0]
def createTree(dataset,labels):
classList = dataset[:,-1]
if len(set(classList))==1:
return dataset[:,-1][0]
if labels.size==0:
return mayorClass(classList)
bestFeatureIndex = chooseBestFeature(dataset,labels)
bestFeature = labels[bestFeatureIndex]
dtree = {bestFeature:{}}
featureList = dataset[:,bestFeatureIndex]
featureValues = set(featureList)
for value in featureValues:
subdataset = splitDataSet(dataset,bestFeatureIndex,value)
sublabels = np.delete(labels,bestFeatureIndex)
dtree[bestFeature][value]=createTree(subdataset,sublabels)
return dtree
def predict(tree,labels,testData):
rootName = list(tree.keys())[0]
rootValue = tree[rootName]
featureIndex = list(labels).index(rootName)
classLabel = None
for key in rootValue.keys():
if testData[featureIndex] == int(key):
if type(rootValue[key]).__name__=="dict":
classLabel = predict(rootValue[key],labels,testData)
else:
classLabel = rootValue[key]
return classLabel
def predictAll(tree,labels,testSet):
classLabels = []
for i in testSet:
classLabels.append(predict(tree,labels,i))
return classLabels
if __name__=="__main__":
dataset,labels = createDataSet()
# print(dataset_entropy(dataset))
# s = splitDataSet(dataset,0)
# for item in s:
# print(item)
tree = createTree(dataset,labels)
testSet = createTestSet()
print(predictAll(tree,labels,testSet))
import decision_tree.treePlotter as treePlotter
treePlotter.createPlot(tree)C4.5算法
- 改进1：用信息增益率代替信息增益来选择属性
- 改进2：能够完成对连续值属性的离散化处理
- 改进3：能处理属性值缺失的情况
- 改进4：在决策树构造完成之后进行剪枝
改进1：信息增益的问题
假设按属性 A 划分 D 中的样本，且属性 A 根据训练数据的观测具有 v 个不同取值{ a1, a2, ..., aj , ..., av }。
如果 A 是离散值，可依属性 A 将 D 划分为 v 个子集 { D1, D2, ..., Dj , ..., Dv }
其中，Dj为D中的样本子集，它们在A上具有属性值aj这些划分将对应于从该节点A出来的分支。
信息增益度量偏向于对取值较多的属性进行测试，即它倾向于选择v较大的属性A
举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。
对属性PID划分得到的信息增益最大，显然，这种划分对分类没有用处
C4.5使用分裂信息(split information)将信息增益规范化
该值表示数据集D按属性A分裂的v个划分产生的信息
选择具有最大信息增益率的属性作为分裂属性
改进2：连续值属性与分裂点
对于连续值属性，按属性值大小从小到大排序，取每对相邻值的中点作为可能的分裂点split_point。
假设一连续值属性共有N个不同的属性值，则可找到N-1个可能的分裂点。检查每个可能分裂点，取能使得信息增益最大的分裂点，将D分裂成
D1: A <= split_point 和 D2: A > split_point(一个分裂点，二分法，二叉树)
- 使用二元划分
- 划分点v选择
– N个记录中所有属性值作为划分点 - 对每个划分进行类计数, A < v and A >= v
- 计算每个候选点v的信息增益指标，并从中选择具有最大信息增益的候选划分点
- 时间复杂度为(n2)
• 降低计算复杂性的方法, – 将记录进行排序
– 从两个相邻的排过序的属性值之间选择中间值作为划分点
– 计算每个候选点的信息增益值
– 选择修正后信息增益(InforGain)最大的分裂点作为该特征的最佳分裂点
– 计算最佳分裂点的信息增益率（Gain Ratio）作为特征的Gain Ratio – 时间复杂度为nlogn
改进3： C4.5中缺失值的处理
• 建树过程（学习过程）
– 选定训练样本实例有缺失值，如何知道要将其分配到哪个分支？
计算 SplitInfo 时，将缺失的属性值当作一个正常值进行计算，
分裂时，将属性值缺失的实例分配给所有分支，但是带一个权重
• 分类过程（测试过程或者工作过程）
– 待分类实例有缺失值，如何测试该实例属于哪个分支？
改进4：学习过程中的过度拟合
上述的决策树算法增长树的每一个分支的深度，直到恰好能对训练样例比较完美地分类。实际应用中，当训练样本中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，该策略可能会遇到困难.在以上情况发生时，这个简单的算法产生的树会过度拟合训练样例 (过度拟合: Over fitting)
过度拟合产生的原因：
- 训练样本中有噪声
训练样本中噪声导致的过度拟合，错误的类别值/类标签，属性值等
- 训练样例太小等
训练样本中缺乏代表性样本所导致的过度拟合,根据少量训练记录作出的分类决策模型容易受过度拟合的影响。由于训练样 本缺乏代表性的样本，在没有多少训练记录的情况下，学习算法仍然继续细化模型就会导致过度拟合。
决策树剪枝
- 预剪枝(prepruning：在完全正确分类训练集之前就停止树的生长。
最直接的方法：事先限定树的最大生长高度
- 后剪枝(postpruning)：由“完全生长”的树剪去子树
训练过程中允许对数据的过度拟合，然后再利用测试集对树进行修剪
在测试集上定义损失函数C，我们的目标是通过剪枝使得在测试集上C的值下降。
例如通过剪枝使在测试集上误差率降低。
1. 自底向上的遍历每一个非叶节点(除了根节点)，将当前的非叶节点从树中减去，其下所有的叶节点合并成一个节点，代替原来被剪掉的节点。
2. 计算剪去节点前后的损失函数，如果剪去节点之后损失函数变小了，则说明该节点是可以剪去的，并将其剪去；如果发现损失函数并没有减少，说明该节点不可剪去，则将树还原成未剪去之前的状态。
3. 重复上述过程，直到所有的非叶节点(除了根节点)都被尝试了
从决策树导出产生式规则
• 大型决策树可读性较低，可通过从决策树导出产生式规则以提高可读性
• 把从根结点到叶子结点的路径中遇到的所有测试条件联合起来，便可建立相对应的规则集
• 但这样的规则会导致某些不必要的复杂性
• 可用类似的方法对规则集进行剪枝
• 对于某一规则，将它的单个条件暂时去除，在测试集上估计误差率，并与原规则的误差率进行比较，若新规则的结果较好，则
删除这个条件
import numpy as np
import operator
def createDataSet():
"""
outlook-> 0: sunny | 1: overcast | 2: rain
temperature-> 0: hot | 1: mild | 2: cool
humidity-> 0: high | 1: normal
windy-> 0: false | 1: true
"""
dataSet = np.array([[0, 0, 0, 0, 'N'],
[0, 0, 0, 1, 'N'],
[1, 0, 0, 0, 'Y'],
[2, 1, 0, 0, 'Y'],
[2, 2, 1, 0, 'Y'],
[2, 2, 1, 1, 'N'],
[1, 2, 1, 1, 'Y']])
labels = np.array(['outlook', 'temperature', 'humidity', 'windy'])
return dataSet, labels
def createTestSet():
"""
outlook-> 0: sunny | 1: overcast | 2: rain
temperature-> 0: hot | 1: mild | 2: cool
humidity-> 0: high | 1: normal
windy-> 0: false | 1: true
"""
testSet = np.array([[0, 1, 0, 0],
[0, 2, 1, 0],
[2, 1, 1, 0],
[0, 1, 1, 1],
[1, 1, 0, 1],
[1, 0, 1, 0],
[2, 1, 0, 1]])
return testSet
def dataset_entropy(dataset):
classLabel = dataset[:,-1]
labelCount = {}
for i in range(classLabel.size):
label = classLabel[i]
labelCount[label]=labelCount.get(label,0)+1
#熵值
ent=0
for k,v in labelCount.items():
ent+=-v/classLabel.size*np.log2(v/classLabel.size)
return ent
def splitDataSet(dataset,featureIndex,value):
subdataset = []
for example in dataset:
if example[featureIndex]==value:
subdataset.append(example)
return np.delete(subdataset,featureIndex,axis=1)
def chooseBestFeature(dataset,labels):
#特征的个数
featureNum = labels.size
baseEntropy = dataset_entropy(dataset)
#最小熵值
maxRatio,bestFeatureIndex=0,None
#样本的总数
n = dataset.shape[0]
for i in range(featureNum):
#指定特征的条件熵
featureEntropy =0
splitInfo = 0
#返回所有子集
featureList = dataset[:, i]
featureValues = set(featureList)
for value in featureValues:
subDataSet = splitDataSet(dataset,i,value)
featureEntropy+=subDataSet.shape[0]/n*dataset_entropy(subDataSet)
splitInfo+=-subDataSet.shape[0]/n*np.log2(subDataSet.shape[0]/n)
gainRatio = (baseEntropy-featureEntropy)/splitInfo
if gainRatio>maxRatio:
maxRatio = gainRatio
bestFeatureIndex = i
return bestFeatureIndex
def mayorClass(classList):
labelCount = {}
for i in range(classList.size):
label = classList[i]
labelCount[label] = labelCount.get(label, 0) + 1
sortedLabel = sorted(labelCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedLabel[0][0]
def createTree(dataset,labels):
classList = dataset[:,-1]
if len(set(classList))==1:
return dataset[:,-1][0]
if labels.size==0:
return mayorClass(classList)
bestFeatureIndex = chooseBestFeature(dataset,labels)
bestFeature = labels[bestFeatureIndex]
dtree = {bestFeature:{}}
featureList = dataset[:,bestFeatureIndex]
featureValues = set(featureList)
for value in featureValues:
subdataset = splitDataSet(dataset,bestFeatureIndex,value)
sublabels = np.delete(labels,bestFeatureIndex)
dtree[bestFeature][value]=createTree(subdataset,sublabels)
return dtree
def predict(tree,labels,testData):
rootName = list(tree.keys())[0]
rootValue = tree[rootName]
featureIndex = list(labels).index(rootName)
classLabel = None
for key in rootValue.keys():
if testData[featureIndex] == int(key):
if type(rootValue[key]).__name__=="dict":
classLabel = predict(rootValue[key],labels,testData)
else:
classLabel = rootValue[key]
return classLabel
def predictAll(tree,labels,testSet):
classLabels = []
for i in testSet:
classLabels.append(predict(tree,labels,i))
return classLabels
if __name__=="__main__":
dataset,labels = createDataSet()
# print(dataset_entropy(dataset))
# s = splitDataSet(dataset,0)
# for item in s:
# print(item)
tree = createTree(dataset,labels)
print(tree)
testSet = createTestSet()
print(predictAll(tree,labels,testSet))
import decision_tree.treePlotter as treePlotter
treePlotter.createPlot(tree)CART决策树
CART，又名分类回归树，是在ID3的基础上进行优化的决策树，学习CART记住以下几个关键点：
• （1）CART既能是分类树，又能是回归树；
• （2）CART是分类树时，采用GINI值作为节点分裂的依据；选择叶子节点中数量占比最大的类别作为输出的类别；当CART是回归树时，采用样本的最小方差作为节点分裂的依据；一般情况下选择使用中值、平均值或者众数进行表示
• （3）CART是一棵二叉树。
• 分类树的作用是通过一个对象的特征来预测该对象所属的类别，而回归树的目的是根据一个对象的信息预测该对象的属性，
并以数值表示。
• CART既能是分类树，又能是回归树，如上表所示，如果我们想预测一个人是否已婚，那么构建的CART将是分类树；如果想
预测一个人的年龄，那么构建的将是回归树。
分类树---GINI值
分裂的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。如果是分类树，CART采用GINI值衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度。节点越不纯，节点分类或者预测的效果就越差。
• GINI值的计算公式
• 节点越不纯，GINI值越大。以二分类为例，如果节点的所有数据只有一个类别，则
• 如果两类数量相同，则
回归树---回归方差
回归方差计算公式：
分类树与回归树的构建
如果两类数量相同，则方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为0，此时可以很肯定得认为该节点的输出值；如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大
因此，无论是分类树还是回归树，CART都要选择使子节点的GINI值或者回归方差最小的属性作为分裂的方案。
即最小化（分类树）：
或者回归树：
CART如何分裂成一个二叉树
• 节点的分裂分为两种情况，连续型的数据和离散型的数据。
• 对于离散型属性，理论上有多少个离散值就应该分裂成多少个节点。但CART是一棵二叉树，每一次分裂只会产生两个节点。只要将其中一个离散值独立作为一个节点，其他的离散值生成另外一个节点即可。
• 这种分裂方案有多少个离散值就有多少种划分的方法，举一个简单的例子：如果某离散属性一个有三个离散值X，Y，Z，则该属性的分裂方法有{X}、{Y，Z}，{Y}、{X，Z}，{Z}、{X，Y}，分别计算每种划分方法的基尼值或者样本方差确定最优的方法
CART如何剪枝
CART采用CCP（代价复杂度）剪枝方法。代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右
子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝
• 令决策树的非叶子节点为
• a）计算所有非叶子节点的表面误差率增益值
• b）选择表面误差率增益值
最小的非叶子节点
（若多个非叶子节点具有相同小的表面误差率增益值，选择节点数最多的非叶子节点）。
• c）对进行剪枝
• 表面误差率增益值的计算公式：
import numpy as np
import operator
def createDataSet():
"""
outlook-> 0: sunny | 1: overcast | 2: rain
temperature-> 0: hot | 1: mild | 2: cool
humidity-> 0: high | 1: normal
windy-> 0: false | 1: true
"""
dataSet = np.array([[0, 0, 0, 0, 'N'],
[0, 0, 0, 1, 'N'],
[1, 0, 0, 0, 'Y'],
[2, 1, 0, 0, 'Y'],
[2, 2, 1, 0, 'Y'],
[2, 2, 1, 1, 'N'],
[1, 2, 1, 1, 'Y']])
labels = np.array(['outlook', 'temperature', 'humidity', 'windy'])
return dataSet, labels
def createTestSet():
"""
outlook-> 0: sunny | 1: overcast | 2: rain
temperature-> 0: hot | 1: mild | 2: cool
humidity-> 0: high | 1: normal
windy-> 0: false | 1: true
"""
testSet = np.array([[0, 1, 0, 0],
[0, 2, 1, 0],
[2, 1, 1, 0],
[0, 1, 1, 1],
[1, 1, 0, 1],
[1, 0, 1, 0],
[2, 1, 0, 1]])
return testSet
def dataset_entropy(dataset):
classLabel = dataset[:,-1]
labelCount = {}
for i in range(classLabel.size):
label = classLabel[i]
labelCount[label]=labelCount.get(label,0)+1
#熵值
ent=0
for k,v in labelCount.items():
ent+=-v/classLabel.size*np.log2(v/classLabel.size)
return ent
def splitDataSet(dataset,featureIndex,value):
subdataset = []
for example in dataset:
if example[featureIndex]==value:
subdataset.append(example)
return np.delete(subdataset,featureIndex,axis=1)
def classLabelPi(dataset):
classLabel = dataset[:, -1]
labelCount = {}
for i in range(classLabel.size):
label = classLabel[i]
labelCount[label] = labelCount.get(label, 0) + 1
valueList = list(labelCount.values())
sum = np.sum(valueList)
pi = 0;
for i in valueList:
pi+=(i/sum)**2
return pi
def chooseBestFeature(dataset,labels):
#特征的个数
featureNum = labels.size
baseEntropy = dataset_entropy(dataset)
#最小熵值
maxRatio,bestFeatureIndex=0,None
#样本的总数
n = dataset.shape[0]
minGini =1
for i in range(featureNum):
#指定特征的条件熵
featureEntropy =0
gini = 0
#返回所有子集
featureList = dataset[:, i]
featureValues = set(featureList)
"""
3/7(1-1/9-4/9)=0.1904
=0.3408
4/7*1/2+0.1904 = 0.4797
4/7*(1-1/16-9/16)+0.1904=0.4046
"""
for value in featureValues:
subDataSet = splitDataSet(dataset,i,value)
pi = subDataSet.shape[0]/n
gini+=pi*(1-classLabelPi(subDataSet))
print(gini)
if minGini>gini:
minGini = gini
bestFeatureIndex = i
print(bestFeatureIndex)
return bestFeatureIndex
def mayorClass(classList):
labelCount = {}
for i in range(classList.size):
label = classList[i]
labelCount[label] = labelCount.get(label, 0) + 1
sortedLabel = sorted(labelCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedLabel[0][0]
def createTree(dataset,labels):
classList = dataset[:,-1]
if len(set(classList))==1:
return dataset[:,-1][0]
if labels.size==0:
return mayorClass(classList)
bestFeatureIndex = chooseBestFeature(dataset,labels)
bestFeature = labels[bestFeatureIndex]
dtree = {bestFeature:{}}
featureList = dataset[:,bestFeatureIndex]
featureValues = set(featureList)
for value in featureValues:
subdataset = splitDataSet(dataset,bestFeatureIndex,value)
sublabels = np.delete(labels,bestFeatureIndex)
dtree[bestFeature][value]=createTree(subdataset,sublabels)
return dtree
def predict(tree,labels,testData):
rootName = list(tree.keys())[0]
rootValue = tree[rootName]
featureIndex = list(labels).index(rootName)
classLabel = None
for key in rootValue.keys():
if testData[featureIndex] == int(key):
if type(rootValue[key]).__name__=="dict":
classLabel = predict(rootValue[key],labels,testData)
else:
classLabel = rootValue[key]
return classLabel
def predictAll(tree,labels,testSet):
classLabels = []
for i in testSet:
classLabels.append(predict(tree,labels,i))
return classLabels
if __name__=="__main__":
dataset,labels = createDataSet()
# print(dataset_entropy(dataset))
# s = splitDataSet(dataset,0)
# for item in s:
# print(item)
tree = createTree(dataset,labels)
print(tree)
testSet = createTestSet()
print(predictAll(tree,labels,testSet))
import decision_tree.treePlotter as treePlotter
treePlotter.createPlot(tree)CHAID决策树
名称：CHAID (chi-squared automaticinteraction detection，卡方自动交互检测)
主要特征是利用 卡方检测 判断属性优先级
优点：
– 可产生多分枝的决策树
– 目标变量可以定距或定类
– 从统计显著性角度确定分支变量和分割值，进而优化树的分枝过程
提供了一种在多个自变量中自动搜索与因变量最具相关性的变量的方案。
• 相关性度量采用：
显著性程度（卡方值）
若要推断的论述为H1：“X与Y有关系”，可以利用独立性检验来考察两个变量是否有关系，卡方值的计算公式如下
算法伪代码
函数：DT(S,F)
输入：训练集数据S，训练集数据属性集合F
输出：CHAID决策树
(1)if 样本S全部属于同一个类别C then
(2) 创建一个叶结点，并标记类标号为C；
(3) return；
(4)else
(5) 计算属性集F中目标属性与其他每一个属性的卡方值，取卡方值最大的属性；
(6) 创建结点，取属性A为该结点的决策属性；
(7) for 结点属性A的每个可能的取值V do
(8) 为该结点添加一个新的分支，假设SV为属性A取值为V的样本子集；
(9) if 样本SV全部属于同一个类别C then
(10) 为该分支添加一个叶结点，并标记类标号为C；
(11) else
(12) 递归调用DT(SV, F-{A})，为该分支创建子树；
(13) end if
(11) end for
(12)end if
from sklearn.feature_selection import SelectKBest,chi2
import pandas as pd
file = "data.csv"
df = pd.read_csv(file,encoding="gbk")
X = df.iloc[:,:-1].values
y = df.iloc[:,-1].values
new_data = SelectKBest(chi2,k=1).fit_transform(X,y)
print(new_data)
决策树算法总结
决策树基本概念
决策树的优点
1、推理过程容易理解，决策推理过程可以表示成If Then形式；
2、推理过程完全依赖于属性变量的取值特点；
3、可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考
关于归纳学习(1)
决策树技术发现数据模式和规则的核心是归纳算法。
归纳是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论。
归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述。即从特殊事实到普遍性规律的结论。归纳对于认识的发展和完善具有重要的意义。人类知识的增长主要来源于归纳学习
关于归纳学习(2)
归纳学习的过程就是寻找一般化描述的过程。这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据
关于归纳学习(3)
归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设：任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件
关于归纳学习(4)
归纳过程就是在描述空间中进行搜索的过程。归纳可分为自顶向下，自底向上和双向搜索三种方式。自底向上法一次处理一个输入对象。将描述逐步一般化。直到最终的一般化描述。自顶向下法对可能的一般性描述集进行搜索，试图找到一些满足一定要求的最优的描述
从机器学习看分类及归纳推理等问题（1）
从特殊的训练样例中归纳出一般函数是机器学习的中心问题；从训练样例中进行学习通常被视为归纳推理。每个例子都是一个对偶（序偶）（x, f(x)），对每个输入的x，都有确定的输出f(x)。
学习过程将产生对目标函数f的不同逼近。F的每一个逼近都叫做一个假设。假设需要以某种形式表示。例如，y=ax+b。通过调整假设的表示，学习过程将产生出假设的不同变形。在表示中通常需要修改参数（如a, b）。
从机器学习看分类及归纳推理等问题（2）
分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数进行评估。这些计数存储在混同矩阵
从机器学习看分类及归纳推理等问题（3）
归纳学习假设
机器学习的任务是在整个实例集合X上确定与目标概念c相同的假设
。一般H表示所有可能假设。H中每个假设h表示X上定义的布尔函数。由于对c仅有的信息只是它在训练样例上的值，因此归纳学习最多只能保证输出的假设能与训练样例相拟合。若没有更多的信息，只能假定对于未见实例最好的假设就是训练数据最佳拟合的假设。
定义 归纳学习假设：任一假设如果在足够大的训练样例中很好地逼近目标函数，则它也能在未见实例中很好地逼近目标函数。
（Function Approximation）
决策树的基本原理
•决策树学习是以实例为基础的归纳学习。
• 从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。
• 概念分类学习算法：来源于
– Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概念。
– 1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。
– Schlimmer 和Fisher于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。
– 1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。
– 1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。
– 另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。
• 其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子
节点处的熵值为零，此时每个叶节点中的实例都属于同一类
• 决策树学习采用的是自顶向下的递归方法。
• 决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。
• 从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应着一组析取的规则。
• 决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。如果在应用中发现不符合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中
• 树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识，分枝用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。
• 决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束
构造一棵决策树要解决四个问题：
1.收集待分类的数据，这些数据的所有属性应该是完全标注的。
2. 设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。
3.分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。
4.设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，
因此在必要的时候应该停止数据集分裂：
• 该节点包含的数据太少不足以分裂，
• 继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献，
• 树的深度过大不宜再分。
5.通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小最大的准则，这种方案使最具有分类潜力的准则最先被提取出来
决策树特点
• 决策树有很多的优点，可解释性、计算快捷、缺失值的处理、对于多值名义变量不需要建立哑变量、对输入变量异常值稳健。
• 一些树模型作为最后模型并不合适。它经常作为很多熟悉模型（如回归模型）的辅助工具。标准的回归模型具有线性和可加性。他们需要更多的数据准备阶段：如缺失值的处理、哑变量编码。他们统计计算的有效性严重的被许多不相关和冗余的输入变量影响。
对数据的要求
• 进行分析时，决策树对变量的量纲的差异、离群值的存在以及有偏分布不太敏感，也就是说对数据准备要求不高。
• 当每一类的训练样本数较小时，决策树是容易出错的，有好多分支的树或者每个节点有太多枝的树最有可能这样，决策树对输出结果的密度很敏感
决策树的优势
• 决策树方法之所以经常被选用是因为它能理顺一些可以理解的规则。然而这些能力有时有些夸大确实对于某一个已经分过类的记录来说，为了产生这种分类，很简单只要沿着从根到叶的路径走就可以了，然而一个较复杂的决策树可能包含成千上万的叶，这么一棵树从整体上很难提供有关问题可以理解的信息。
• 而回归模型的回归系数具有可解释性，在流行病学研究中，对致病因素的效应，常用一些危险度指标来衡量因素与发病（或死亡）的联系程度或对人群发病的致病作用的大小均可通过拟合该模型得出。
sklearn
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
import matplotlib.pyplot as plt
import pandas as pd
import os
from sklearn import tree
from sklearn.metrics import confusion_matrix,roc_curve,auc
import pydotplus
file = "data.csv"
dataset = pd.read_csv(file,encoding="gbk").values
x_train,x_test,y_train,y_test = train_test_split(dataset[:,:-1],dataset[:,-1],test_size=0.3)
#参数的调节
def getCriterion():
criterions = ["gini","entropy"]
for criterion in criterions:
model = DecisionTreeClassifier(criterion=criterion)
model.fit(x_train,y_train)
print(criterion," training score:",model.score(x_train,y_train))
print(criterion," testing score:",model.score(x_test,y_test))
#树的深度调节
def getDepth():
max_depths=range(1,30)
train_score =[]
test_score = []
for max_depth in max_depths:
model = DecisionTreeClassifier(max_depth=max_depth)
model.fit(x_train, y_train)
train_score.append(model.score(x_train,y_train))
test_score.append(model.score(x_test,y_test))
print(train_score)
print(test_score)
plt.plot(max_depths,train_score,label="train",marker="*")
plt.plot(max_depths,test_score,label="test",marker="o")
plt.xlabel("max_depth")
plt.ylabel("score")
plt.legend(loc="best")
plt.show()
#最小分裂点
def getMinSampleSplit():
train_score = []
test_score = []
min_samples_split=range(100,1000,50)
for min_samples in min_samples_split:
model = DecisionTreeClassifier(min_samples_split=min_samples)
model.fit(x_train, y_train)
train_score.append(model.score(x_train, y_train))
test_score.append(model.score(x_test, y_test))
print(train_score)
print(test_score)
plt.plot(min_samples_split, train_score, label="train", marker="*")
plt.plot(min_samples_split, test_score, label="test", marker="o")
plt.xlabel("max_depth")
plt.ylabel("score")
plt.legend(loc="best")
plt.show()
#叶子节点最小数
def getMinLeaf():
train_score = []
test_score = []
min_samples_leaf = range(50,300,10)
for min_samples in min_samples_leaf:
model = DecisionTreeClassifier(min_samples_leaf=min_samples)
model.fit(x_train, y_train)
train_score.append(model.score(x_train, y_train))
test_score.append(model.score(x_test, y_test))
print(train_score)
print(test_score)
plt.plot(min_samples_leaf, train_score, label="train", marker="*")
plt.plot(min_samples_leaf, test_score, label="test", marker="o")
plt.xlabel("max_depth")
plt.ylabel("score")
plt.legend(loc="best")
plt.show()
# 输出树形图
def out_image():
# 模型初始化
clf = DecisionTreeClassifier(max_depth=3)
# 训练模型
clf.fit(x_train, y_train)
# 输出.dot文件
tree.export_graphviz(clf, out_file=file.replace('.csv', '.dot'), filled=True, rounded=True)
# #输出pdf/png
# dot_data = tree.export_graphviz(clf,out_file=None,filled=True,rounded=True)
# graph = pydotplus.graph_from_dot_data(dot_data)
# # graph.write_pdf(file.replace('.csv', '.pdf'))
# graph.write_png(file.replace('.csv', '.png'))
#roc曲线
def graph_roc():
model = DecisionTreeClassifier(criterion="entropy",max_depth=5,min_samples_split=300)
model.fit(x_train,y_train)
#输出结果为1的概率
proba1=model.predict_proba(x_test)[:,1]
df1 = pd.read_csv(file, encoding="gbk")
cols = list(df1.columns)[0:-1]
df_test = pd.DataFrame(x_test, columns=cols)
# 生成预测值和预测概率
df_test.loc[:, '营销是否成功'] = y_test
df_test.loc[:, '预测为1的概率'] = proba1
if not os.path.exists("test.csv"):
df_test.to_csv("test.csv",encoding="utf-8",index=False)
# 输出混淆矩阵和ROC曲线
def plot_roc():
# 构建模型
clf = DecisionTreeClassifier(max_depth=3)
# 训练数据
clf.fit(x_train, y_train)
# 输出混淆矩阵
pre = clf.predict(x_test)
tn, fp, fn, tp = confusion_matrix(y_test, pre).ravel()
# 更好的输出(二分类)
print('tn={0},fp={1},fn={2},tp={3}'.format(tn,fp,fn,tp))
# 输出预测测试集的概率
y_prb_1 = clf.predict_proba(x_test)[:, 1]
# 得到误判率、命中率、门限
fpr, tpr, thresholds = roc_curve(y_test, y_prb_1)
print(thresholds)
# 计算auc
roc_auc = auc(fpr, tpr)
# 对ROC曲线图正常显示做的参数设定
plt.rcParams['font.sans-serif'] = ['SimHei'] # 用来正常显示中文标签
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
# 绘图
plt.scatter(fpr, tpr)
plt.plot(fpr, tpr, 'g', label='AUC = %0.2f' % (roc_auc))
plt.title('ROC曲线')
# 设置x、y轴刻度范围
plt.xlim([-0.05, 1.05])
plt.ylim([-0.05, 1.05])
plt.legend(loc='lower right')
# 绘制参考线
plt.plot([0, 1], [0, 1], 'r--')
plt.ylabel('命中率')
plt.xlabel('误判率')
plt.show()
if __name__=="__main__":
#getCriterion()
#getDepth()
# getMinSampleSplit()
#getMinLeaf()
# out_image()
#graph_roc()
plot_roc()
最后
以上就是碧蓝衬衫为你收集整理的决策树Hunt算法：ID3算法C4.5算法CART决策树CHAID决策树决策树算法总结sklearn的全部内容，希望文章能够帮你解决决策树Hunt算法：ID3算法C4.5算法CART决策树CHAID决策树决策树算法总结sklearn所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复