决策树（ID3） - 《机器学习》

算法原理：
信息增益
- 划分数据集的大原则：将无序的数据变得更加有序。
数学基础
- 代码实现：
划分数据集
选择最好的数据集划分方式
- 调用及结果：
代码中的函数介绍：
- 列表表达式：
- set(要转换为集合的对象)：将其他对象(列表、元组、…)转换为集合类型
递归构建决策树
- 获取出现次数最多的特征：
- 创建树：
  - 调用及结果：
项目完整代码

算法原理：

通过对特征值进行分类，使在对数据进行分类时一层一层的根据不同的特征值进行筛选，最终给出分类结果。

例：使用成绩作为特征值对成绩进行分类。

例：使用多个特征对学生进行分类。

信息增益

不论一个数据集有多少特征，每次划分数据集时只能选一个特征，那么第一次选择哪个特征作为划分的参考特征呢？答案一定是分类能力最好的那个特征。
如何判断哪一个特征分类能力最好呢？这时就要引入一个新的概念——信息增益。

划分数据集的大原则：将无序的数据变得更加有序。

在划分数据集之前或之后信息发生的变化称之为信息增益。计算每个特征值划分数据集获得的数据增益，获得信息增益最高的特征就是最好的选择。

数学基础

集合信息的度量方式称之为香农熵或简称为熵。

代码实现：

_# 计算数据的熵 _def calcShannonEnt(dataSet): numEntries = len(dataSet) _#数据量 _labelCounts = {} _#统计类别和出现的次数。{类别 : 频次} _for featVec in dataSet: currentLabel = featVec[-1] _#获取每条数据最后一个元素，即类别 #将类别添加到字典中，没有该类则以该类作为键，并赋值1；若该类已存在则将值加1 _if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0.0 _#初始化香农熵 _for key in labelCounts: prob = float(labelCounts[key]) / numEntries _#P(xi) _shannonEnt -= prob * log(prob,2) _#熵 _return shannonEnt

划分数据集

对划分数据集的熵进行度量，以便判断当前是否正确划分了数据集。

数据集：

def createDataSet(): dataSet = [ [1,1,"yes"], [1,1,"yes"], [1,0,"no"], [0,1,"no"], [0,1,"no"] ] labels = ["no surfacing","flippers"] return dataSet,labels

按照给定特征划分数据集：

_# 按照给定特征划分数据集 _def splitDataSet(dataSet,axis,value): _#待划分的数据集、划分数据集的特征(在一条数据中的索引)、需要返回的特征的值(特征要取的值) _retDataSet = [] for featVec in dataSet: _#读取一行数据 _if featVec[axis] == value: _# 若该条数据的指定特征的取值 = 要求的取值 _reducedFeatVec = featVec[:axis] _# 将每一条数据的指定特征值前的元素赋给reducedFeatVec _reducedFeatVec.extend(featVec[axis+1:]) _# 将每条数据的指定特征值之后的所有元素分别添加到retDataSet _retDataSet.append(reducedFeatVec) _#将每一条数据的指定特征值前的元素以一个元素的形式添加到retDataSet _return retDataSet

调用及结果：

retDataSet = splitDataSet(dataSet,0,0) _#以第0个特征值取0划分数据集_

选择最好的数据集划分方式

遍历整个数据集，循环计算香农熵和调用splitDataSet()函数，找到最好的特征划分方式。
_# 选择最好的数据集划分方式 _def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0]) - 1 _#一条数据除label外的元素个数（特征数量） _baseEntropy = calcShannonEnt(dataSet) _#计算数据集的熵（初始数据集的熵） _bestInfoGain = 0.0 bestFeature = -1 _#初始化最好的数据集划分特征 _for i in range(numFeatures): _#取出每一个特征所在列的索引 _featList = [example[i] for example in dataSet] _#将数据集中的某一种特征的值提取到列表featList _uniqueVals = set(featList) _#列表 --> 集合,即只统计出现了哪些特征值，而不管这些特征值出现了几次 _newEntropy = 0.0 _#初始化熵 _for value in uniqueVals: _#value为某特征的一个取值 _subDataSet = splitDataSet(dataSet,i,value) _#按照指定特征的指定取值划分数据集 _prob = len(subDataSet) / float(len(dataSet)) _#计算此时划分出的数据集的数据数量在全部数据中的占比 # 划分出的数据集的熵 _newEntropy += prob * calcShannonEnt(subDataSet) _#更新熵 _infoGain = baseEntropy - newEntropy _#熵值越大，数据的离散程度越大 _if(infoGain > bestInfoGain): _#对最好的数据集划分特征进行更新 _bestInfoGain = infoGain bestFeature = i return bestFeature _#返回最好的数据集划分特征的索引_

调用及结果：

chooseBestFeatureToSplit(dataSet)

代码中的函数介绍：

列表表达式：

[表达式 for 迭代变量 in 可迭代对象 if 条件表达式]
—-等价于—->
for 迭代变量 in 可迭代对象:
if 条件表达式:
表达式

set(要转换为集合的对象)：将其他对象(列表、元组、…)转换为集合类型

集合中的值不可重复，通常使用该方法获取列表或元组中出现的元素。

递归构建决策树

在前几个步骤中，构建了从数据集构造决策树需要的子模块，工作原理为：得到原始数据集，然后基于最好的特征值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分后，数据将被向下传递到树分支的下一个节点，在这个节点上，可以再次划分数据。故可以采取递归的原则处理数据集。
递归的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都是相同的分类。

获取出现次数最多的特征：

_# 用于返回特征值出现次数最多的特征 _def majorityCnt(classList): _# classList:数据集中每条数据的特征构成的列表 _classCount = {} _# 将特征和出现次数存入字典 _for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 _# 对字典按照值进行排序 _sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1),reverse=True) return sortedClassCount[0][0] _#返回出现次数最多的特征_

创建树：

_#创建树 _def createTree(dataSet,labels): classList = [example[-1] for example in dataSet] _# 获取每条数据最后一个元素，即特征 _if classList.count(classList[0]) == len(classList): _# 如果第一个特征的个数 = 整个特征列表的长度 _return classList[0] if len(dataSet[0]) == 1: return majorityCnt(classList) _#返回出现次数最多的特征 _bestFeat = chooseBestFeatureToSplit(dataSet) _#获取最好的数据集划分特征的索引 _bestFeatLabel = labels[bestFeat] _#获取最好的数据集划分特征 # 构建树 _decisionTree = {bestFeatLabel:{}} del(labels[bestFeat]) _#将当前得到的最好的数据集划分特征从特征列表中去除 _featValues = [example[bestFeat] for example in dataSet] _#获取每条数据中最好特征的取值 _uniqueVals = set(featValues) _#提取最好特征取值列表中出现的值 _for value in uniqueVals: subLabels = labels[:] decisionTree[bestFeatLabel][value] = createTree( splitDataSet(dataSet,bestFeat,value),subLabels _#按照最好特征的各个取值划分的数据集，去除了当前最好特征的特征列表 _) return decisionTree

调用及结果：

createTree(dataSet,labels)

项目完整代码

trees.txt