python决策树id3算法_三种决策树算法 (ID3, CART, C4.5) 及 Python 实现

三种决策树算法 (ID3, CART, C4.5) 及 Python 实现

Github: https://github.com/yingzk/MyML

1. 决策树 (Decision Tree) 简介

1.1. 决策树的原理

决策树是属于机器学习监督学习分类算法中比较简单的一种, 决策树是一个预测模型; 他代表的是对象属性与对象值之间的一种映射关系树中每个节点表示某个对象, 而每个分叉路径则代表的某个可能的属性值, 而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值决策树仅有单一输出, 若欲有复数输出, 可以建立独立的决策树以处理不同输出 是通过一系列规则对数据进行分类的过程

示例: 一个周末是否出去玩的例子

决策树即是将数据集转换成树形的结构, 如下:

1.2. 决策树的构造过程

一般包含三个部分

1 特征选择: 特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准, 如何选择特征有着很多不同量化评估标准标准, 从而衍生出不同的决策树算法, 如 CART, ID3, C4.5 等

2 决策树生成: 根据选择的特征评估标准, 从上至下递归地生成子节点, 直到数据集不可分则停止决策树停止生长 树结构来说, 递归结构是最容易理解的方式

3 剪枝: 决策树容易过拟合, 一般来需要剪枝, 缩小树结构规模缓解过拟合剪枝技术有预剪枝和后剪枝两种

伪代码

if 遇到终止条件:

return 类标签

else:

寻找一个最优特征对数据集进行分类

创建分支点

对每个分支节点进行划分, 将分支点返回到主分支

return 分支节点

1.3. 决策树的优缺点

决策树适用于数值型和标称型 (离散型数据, 变量的结果只在有限目标集中取值), 能够读取数据集合, 提取一些列数据中蕴含的规则在分类问题中使用决策树模型有很多的优点, 决策树计算复杂度不高便于使用而且高效, 决策树可处理具有不相关特征的数据可很容易地构造出易于理解的规则, 而规则通常易于解释和理解决策树模型也有一些缺点, 比如处理缺失数据时的困难过拟合以及忽略数据集中属性之间的相关性等

1.4. 三种决策树算法简介

决策树算法中的核心部分即是: 如何选择划分属性?

最早的决策树算法起源于 CLS(Concept Learning System) 系统, 即概念学习系统

这就必须采用量化的方法来进行判断, 量化的方法有很多, 其中一项就是通过信息论度量信息分类基于信息论的决策树算法有: ID3, CART, C4.5 等算法

ID3 算法是由 Ross Quinlan 发明的, 建立在奥卡姆剃刀的基础上, 越简单的决策树越优于越大的决策树 (Be Simple),ID3 算法中, 根据信息论的信息增益来进行评估和特征的选择, 每次选择信息增益最大的特征作为判断模块 ID3 算法可以用于划分标称型数据集, 没有剪枝的过程, 为了去除过度数据匹配的问题, 可通过裁剪合并相邻的无法产生大量信息增益的叶子节点 (例如设置信息增益阀值) 使用信息增益的话其实是有一个缺点, 那就是它偏向于具有大量值的属性就是说在训练集中, 某个属性所取的不同值的个数越多, 那么越有可能拿它来作为分裂属性, 而这样做有时候是没有意义的, 另外 ID3 不能处理连续分布的数据特征, 于是就有了 C4.5 算法 (目前也出现了 C5.0 算法 商业版)CART 算法也支持连续分布的数据特征

C4.5 是 ID3 的一个改进算法, 继承了 ID3 算法的优点 C4.5 算法用信息增益率来选择划分属性, 克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝; 能够完成对连续属性的离散化处理; 能够对不完整数据进行处理 C4.5 算法产生的分类规则易于理解准确率较高; 但效率低, 因树构造过程中, 需要对数据集进行多次的顺序扫描和排序也是因为必须多次数据集扫描, C4.5 只适合于能够驻留于内存的数据集

CART 算法的全称是 Classification And Regression Tree, 采用的是 Gini 指数 (选 Gini 指数最小的特征 s) 作为分裂标准, 同时它也是包含后剪枝操作 ID3 算法和 C4.5 算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息, 但其生成的决策树分支较大, 规模较大为了简化决策树的规模, 提高生成决策树的效率, 就出现了根据 GINI 系数来选择测试属性的决策树算法 CART

熵: 度量随机变量的不确定性 (纯度)

(1) 信息熵

在概率论中, 信息熵给了我们一种度量不确定性的方式, 是用来衡量随机变量不确定性的, 熵就是信息的期望值若待分类的事物可能划分在 N 类中, 分别是 x_1,x_2,\cdots,x_n, 每一种取到的概率分别是 p_1,p_2,\cdots,p_n, 那么数据集 D 的熵就定义为:

H(D)=-\sum^{|n|}_{i=1}p_ilogp_i

从定义中可知: 0H(D)log(n)

当随机变量只取两个值时, 即 D 的分布为 P(D=1)=p, P(D=0)=1-p, 0p1 则熵为: H(D)=plog_2p(1p)log_2(1p)

熵值越高, 则数据混合的种类越高, 其蕴含的含义是一个变量可能的变化越多 (反而跟变量具体的取值没有任何关系, 只和值的种类多少以及发生概率有关), 它携带的信息量就越大

(2) 条件熵

假设有随机变量 (X,Y), 其联合概分布为:

P(X=x_i,Y=y_i)=p_{ij}, i=1,2,,n;j=1,2,,m 则条件熵 H(YX) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性, 其定义为 X 在给定条件下 Y 的条件概率分布的熵对 X 的数学期望:

H(Y|X)=\sum^{n}_{i=1}p_iH(Y|X=x_i)

(3) 信息增益

信息增益 (information gain) 表示得知特征 X 的信息后, 而使得 Y 的不确定性减少的程度定义为:

Gain(D,A)=H(D)-H(D|A)

(4)Gini 指数

基尼指数 (基尼不纯度): 表示在样本集合中一个随机选中的样本被分错的概率

注意: Gini 指数越小表示集合中被选中的样本被分错的概率越小, 也就是说集合的纯度越高, 反之, 集合越不纯

即 基尼指数 (基尼不纯度)= 样本被选中的概率 * 样本被分错的概率

Gini(p)=\sum^{|y|}{k=1}\sum{k}p_kp^{}k = 1- \sum^{|y|}{k=1}p^2_k

2. ID3 的 Python 实现#!/usr/bin/env python

# -*- coding: utf-8 -*-

importnumpyasnp

importpandasaspd

importoperator

defloadDataSet():

"""

导入数据

@ return dataSet: 读取的数据集# 对数据进行处理

dataSet=pd.read_csv('isFish.csv',delimiter=',')

# dataSet = dataSet.replace('yes', 1).replace('no', 0)

labelSet=list(dataSet.columns.values)

dataSet=dataSet.values

returndataSet,labelSet

defcalcShannonEnt(dataSet):

"""

计算给定数据集的信息熵 (香农熵)

@ param dataSet: 数据集

@ return shannonEnt: 香农熵numEntries=len(dataSet)

labelCounts={}

forfeatVecindataSet:

# 当前样本类型

currentLabel=featVec[-1]

# 如果当前类别不在 labelCounts 里面, 则创建

ifcurrentLabelnotinlabelCounts.keys():

labelCounts[currentLabel]=0

labelCounts[currentLabel]+=1

shannonEnt=0.0

forkeyinlabelCounts:

prob=float(labelCounts[key])/numEntries

shannonEnt-=prob*np.log2(prob)

returnshannonEnt

defsplitDataSet(dataSet,axis,value):

"""

划分数据集, 提取所有满足一个特征的值

@ param dataSet: 数据集

@ param axis: 划分数据集的特征

@ param value: 提取出来满足某特征的 listretDataSet=[]

forfeatVecindataSet:

# 将相同数据特征的提取出来

iffeatVec[axis]==value:

reducedFeatVec=list(featVec[:axis])

reducedFeatVec.extend(featVec[axis+1:])

retDataSet.append(reducedFeatVec)

returnretDataSet

defchooseBestFeature(dataSet):

"""

选择最优的划分属性

@ param dataSet: 数据集

@ return bestFeature: 最佳划分属性# 属性的个数

numFeature=len(dataSet[0])-1

baseEntroy=calcShannonEnt(dataSet)

bestInfoGain=0.0

bestFeature=-1

foriinrange(numFeature):

# 获取第 i 个特征所有可能的取值

featureList=[example[i]forexampleindataSet]

# 去除重复值

uniqueVals=set(featureList)

newEntropy=0.0

forvalueinuniqueVals:

subDataSet=splitDataSet(dataSet,i,value)

# 特征为 i 的数据集占总数的比例

prob=len(subDataSet)/float(len(dataSet))

newEntropy+=prob*np.log2(prob)

inforGain=baseEntroy-newEntropy

ifinforGain>bestInfoGain:

bestInfoGain=inforGain

bestFeature=i

returnbestFeature

defmajorityCnt(classList):

"""

递归构建决策树

@ param classList: 类别列表

@ return sortedClassCount[0][0]: 出现次数最多的类别classCount={}

forvoteinclassList:

ifvotenotinclassCount.keys():

classCount[vote]=0

classCount+=1

# 排序

sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

# 返回出现次数最多的

returnsortedClassCount[0][0]

defcreateTree(dataSet,labels):

"""

构造决策树

@ param dataSet: 数据集

@ param labels: 标签集

@ return myTree: 决策树classList=[example[-1]forexampleindataSet]

# 当类别与属性完全相同时停止

ifclassList.count(classList[0])==len(classList):

returnclassList[0]

# 遍历完所有特征值时, 返回数量最多的

if(len(dataSet[0])==1):

returnmajorityCnt(classList)

# 获取最佳划分属性

bestFeat=chooseBestFeature(dataSet)

bestFeatLabel=labels[bestFeat]

myTree={bestFeatLabel:{}}

# 清空 labels[bestFeat]

del(labels[bestFeat])

featValues=[example[bestFeat]forexampleindataSet]

uniqueVals=set(featValues)

forvalueinuniqueVals:

subLabels=labels[:]

# 递归调用创建决策树

myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)

returnmyTree

if__name__=='__main__':

dataSet,labelSet=loadDataSet()

shannonEnt=calcShannonEnt(dataSet)

tree=createTree(dataSet,labelSet)

print(tree)

其余算法待补充

来源: https://cloud.tencent.com/developer/article/1057143