# 李航《统计学习方法》决策树ID3算法实现

```age,work,hourse,loan,class

1、查看数据基本信息

```import pandas as pd
import numpy as np
from sklearn import preprocessing

dataset.info()```
```#获取数据集的形状
n_data = dataset.shape[0]
# 得到变量列表，得到格式为list
cols = dataset.columns.tolist()```

2、描述型变量转数值型变量

```#创建obj_vals列表，并将描述型变量存入
for col in cols:
if dataset[col].dtype == "object":
obj_vars.append(col)
print(obj_vars)```
```# 将描述变量转化为数值型变量
# 并将转化为的数据附加到原始数据上
le = preprocessing.LabelEncoder()
for col in obj_vars:
tran = le.fit_transform(dataset[col].tolist())
tran_dataset = pd.DataFrame(tran, columns=['num_'+col])
dataset = pd.concat([dataset, tran_dataset], axis=1)```

Decision Tree ID3算法初始形式

## ID3算法：

```import pandas as pd
import numpy as np
from math import log

'''
输入：文件
输出：csv数据集
'''
return dataset

def calcShannonEnt(dataset):
'''
输入：数据集
输出：数据集的香农熵
描述：计算给定数据集的香农熵
'''
numEntries = dataset.shape[0]
labelCounts = {}
cols = dataset.columns.tolist()
classlabel = dataset[cols[-1]].tolist()
for currentlabel in classlabel:
if currentlabel not in labelCounts.keys():
labelCounts[currentlabel] = 1
else:
labelCounts[currentlabel] += 1

ShannonEnt = 0.0

for key in labelCounts:
prob = labelCounts[key]/numEntries
ShannonEnt -= prob*log(prob, 2)

return ShannonEnt

def splitDataSet(dataset, axis, value):
'''
输入：数据集，所占列，选择值
输出：划分数据集
描述：按照给定特征划分数据集；选择所占列中等于选择值的项
'''
cols = dataset.columns.tolist()
axisFeat = dataset[axis].tolist()
#更新数据集
retDataSet = pd.concat([dataset[featVec] for featVec in cols if featVec != axis], axis=1)
i = 0
dropIndex = [] #删除项的索引集
for featVec in axisFeat:
if featVec != value:
dropIndex.append(i)
i += 1
else:
i += 1
newDataSet = retDataSet.drop(dropIndex)
return newDataSet.reset_index(drop=True)

def chooseBestFeatureToSplit(dataset):
'''
输入：数据集
输出：最好的划分特征
描述：选择最好的数据集划分维度
'''
numFeatures = dataset.shape[1] - 1
ShannonEnt = calcShannonEnt(dataset)
bestInfoGain = 0.0
bestFeature = -1
cols = dataset.columns.tolist()
for i in range(numFeatures):
equalVals = set(dataset[cols[i]].tolist())
newEntropy = 0.0
for value in equalVals:
subDataSet = splitDataSet(dataset, cols[i], value)
prob = subDataSet.shape[0] / dataset.shape[0]
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = ShannonEnt - newEntropy
print(cols[i],infoGain)
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = cols[i]
return bestFeature, bestInfoGain

def majorityCnt(classList):
'''
输入：分类类别列表
输出：子节点的分类
描述：数据集已经处理了所有属性，但是类标签依然不是唯一的，
采用多数判决的方法决定该子节点的分类
'''
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reversed=True)
return sortedClassCount[0][0]

def createTree(dataset, dropCol):
'''
输入：数据集，删除特征
输出：决策树
描述：递归构建决策树，利用上述的函数
'''
cols = dataset.columns.tolist()[:-1]
classList = dataset[dataset.columns.tolist()[-1]].tolist()

#若数据集中所有实例属于同一类Ck，则为单节点树，并将Ck作为该节点的类标记
if classList.count(classList[0]) == len(classList):
return classList[0]

#若特征集为空集，则为单节点树，并将数据集中实例数最大的类Ck作为该节点的类标记
if len(dataset[0:1]) == 0:
return majorityCnt(classList)

# dataset.drop(dropCol, axis=1, inplace=True)
print('特征集和类别:',dataset.columns.tolist())
bestFeature, bestInfoGain=chooseBestFeatureToSplit(dataset)
print('bestFeture:',bestFeature)

myTree = {bestFeature:{}}

#del(labels[bestFeat])
# 得到列表包括节点所有的属性值
print(bestFeature)
featValues = dataset[bestFeature]
uniqueVals = set(featValues)
for value in uniqueVals:
myTree[bestFeature][value] = createTree(splitDataSet(dataset, bestFeature, value), bestFeature)
return myTree

def main():
filename = "dataset.csv"
dropCol = []
myTree = createTree(dataset, dropCol)
print(myTree)

if __name__ == '__main__':
main()```

## 输出样例：

```特征集和类别: ['age', 'work', 'hourse', 'loan', 'class']
age 0.08300749985576883
work 0.32365019815155627
hourse 0.4199730940219749
loan 0.36298956253708536
bestFeture: hourse
hourse

age 0.2516291673878229
work 0.9182958340544896
loan 0.47385138961004514
bestFeture: work
work
{'hourse': {'是': '是', '否': {'work': {'是': '是', '否': '否'}}}}```

## ID3算法的不足：

ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。

1. ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
2. ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。
3. ID3算法对于缺失值的情况没有做考虑
4. 没有考虑过拟合的问题

## 写在最后：

0 条评论

• ### 慧安金科黄铃：减少对标注数据的依赖，做规避用户隐私的AI风控丨镁客请讲

慧安金科主要通过自主研发的半监督主动式机器学习技术来构建金融风控方面的预测模型和决策引擎。

• ### 判别模型与生成模型

监督学习方法可以分为生成方法(generative approach)和判别方法(discriminative approach)，所学到的模型分别称为生成模型...

• ### 快速准确的人脸检测、识别和验证新框架（文末附源码）

上一期“计算机视觉战队”已经和大家分享了相关的人脸检测、识别和验证背景及现状的发展状况，今天我们继续说说人脸领域的一些相关技术以及新框架的人脸检测识别系统。

• ### NVIDIA Deepstream 4.0笔记（三）：智能交通场景应用

本次笔记整理自NVIDIA 8月20日在线研讨会，原讲座标题：DEEPSTREAM SDK – ACCELERATING REAL-TIME AI BASED ...

• ### 特征工程

特征工程是用数学转换的方法将原始输入数据转换为用于机器学习模型的新特征。特征工程提高了机器学习模型的准确度和计算效率，体现在以下五个方面

• ### Github上的5个高赞机器学习项目

对于程序员而言，Github无疑是一个巨大的宝库，其全球注册用户超过3100万，仓库数量突破一个亿。（2018年年底统计数据）

• ### DeepMind 团队 CASP 夺冠：用 AlphaFold 预测蛋白质结构

在 2016 年和 2017 年，谷歌旗下 DeepMind 团队的研究成果 AlphaGo 可以说是科技界当之无愧的焦点。2016 年，AlphaGo 以出色...

• ### 【完结】 12篇文章带你完全进入NLP领域，掌握核心技术

专栏《NLP》第一阶段正式完结了。在本专栏中，我们从NLP中常用的机器学习算法开始，介绍了NLP中常用的算法和模型；从朴素贝叶斯讲到XLnet，特征抽取器从RN...

• ### 【GAN优化】从动力学视角看GAN是一种什么感觉？

今天讲述的内容是GAN与动力学，这是一个非常好玩、非常新鲜的视角。考虑到很多人微积分和线性代数等知识的涉猎不多，我将会对涉及的内容都做出基本说明，也并不会涉及过...

• ### 图解LSTM与GRU单元的各个公式和区别

因为自己LSTM和GRU学的时间相隔很远，并且当时学的也有点小小的蒙圈，也因为最近一直在用lstm，gru等等，所以今天没事好好缕了一下，接下来跟着我一起区分并...