- 最经常使用的机器学习算法
- k近邻法最大缺点是无法给出数据的内在含义，决策树主要优势是数据形式非常容易理解
机器根据数据集创建规则的过程，就是机器学习的过程
一、决策树的构造
- 优点：计算复杂度不高，输出结果易理解，对中间值缺失不敏感，可以处理不相关特征数据
- 缺点：可能会产生过度匹配问题
- 适用数据类型：数值型、标称型
根据数学上的信息论，评估每个特征，找到决定性的特征，划分出最好的结果。原始数据集会被划分成几个数据集，这些子数据集会分布在第一个决策点的所有分支上。
如果某个分支下的数据属于同一类型，则此子数据集已经被正确划分数据分类，无需进一步对数据集进行分割。
如果子数据集的数据不属于同一类型，则需要重新划分数据子集的过程，知道所有具有相同类型对的数据均在同一个数据子集内。
创建分支的伪代码函数
def CreateBranch():
检查数据集中每个子项是否属于统一分类
if True:
返回类标签
else:
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每一个划分的子集：
递归回调函数CreateBranch()自身，并且增加返回结果到分支节点中
return 分支节点
决策树的一般流程
- 收集数据：任何方法
- 准备数据：数构造算法只适用于标称型数据，因此数值型数据必须离散化
- 分析数据：任何方法，构造树完成之后，我们应该检查图形是否符合预期。
- 训练算法：构造数的数据结构
- 测试算法：使用经验树计算错误率
- 使用算法：此步骤适用于任何监督学习算法，而决策树可以更好得理解数据的内在含义
这里使用ID3算法划分数据集，每次划分数据集时，只选择一个特征属性。
信息增益
划分数据的大原则是：将无序的数据变得更加有序。使用信息论度量信息。划分数据之前之后发生的变化叫信息增益。信息增益是熵的减少或者数据无序度的减少
计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
计算信息增益（information gain）：
集合信息的度量方式：香农熵（信息熵）简称熵(entropy)，也就是信息的期望值
信息熵是消除不确定性所需信息量的度量，即未知事件可能含有的信息量。通俗的讲信息熵是用来衡量信息量的大小。
- 若不确定性越大，则信息量越大，熵越大。
- 若不确定性越小，则信息量越小，熵越小。
信息量的定义：如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为：
其中p(xi)是选择该分类的概率
信息熵：计算所有类别所有可能值包含的信息期望值：
其中n是分类的数目
代码
from math import log
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-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
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
运行
>>> import trees
>>> myDat, labels = trees.createDataSet()
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myDat)
0.9709505944546686
熵越高，则混合的数据也越多，增加第三个名为maybe的分类，测试熵的变化
>>> myDat[0][-1]='maybe'
>>> myDat
[[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myDat)
[1, 1, 'maybe']
[1, 1, 'yes']
[1, 0, 'no']
[0, 1, 'no']
[0, 1, 'no']
1.3709505944546687
得到熵以后，可以按照获取最大信息增益的方法划分数据集
另一张度量集合无序程度的方法是基尼不纯度（Gini impurity）:从一个数据集合中随机选取子项，度量其错误分类到其他分组里的概率
划分数据集
对每个特征划分数据集的结果计算一次信息熵，然后判断按照那个特征划分数据集时最好的划分方式
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value: #抽取所有符合要求的元素
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:]) #去掉该特征值本身
retDataSet.append(reducedFeatVec) #创建划分数据集
return retDataSet
运行：
>>> import trees
>>> myDat, labels = trees.createDataSet()
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.splitDataSet(myDat, 0, 0)
[[1, 'no'], [1, 'no']]
遍历整个数据集，循环计算信息熵和splitDataSet()函数，找到最好的特征划分方法
熵计算将会告诉我们如何划分数据集是最好的数据组织方式
选取特征，划分数据集，计算得到最好的划分数据集的特征
输入数据：
- 必须是由列表元素组成的列表，而且所有的列表元素都要具有相同的数据长度
- 数据最后一列是当前实例的类别标签
- 无需限定list中的数据类型，既可以是数字也可以是字符串
from math import log
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-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
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.extend(featVec[axis+1:]) #去掉该特征值本身
retDataSet.append(reducedFeatVec) #创建划分数据集
return retDataSet
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShannonEnt(dataSet) #计算整个数据集的原始香农熵
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet] #所有第i个特征值或所有可能存在的值
uniqueVals = set(featList) #创建唯一的分类标签列表
newEntropy = 0.0
for value in uniqueVals: #对每个唯一属性值划分一次数据集
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
运行：
>>> from importlib import reload
>>> reload(trees)
<module 'trees' from 'D:\\Data\\File\\ML\\trees\\trees.py'>
>>> myDat, labels = trees.createDataSet()
>>> trees.chooseBestFeatureToSplit(myDat)
0
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
递归构建决策树
工作原理：
-
得到原始数据集
-
基于最好的属性值划分数据集，由于特征值可能多于2个，所以可能存在大于2个分支的数据集划分
-
第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据，因此可以采用递归的原则处理数据集
-
递归结束条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类
-
第一个结束条件使得算法可以终止，甚至可以设置算法可以划分的最大分组数目
-
其他决策树算法：如C4.5,CART，这些算法运行时并不总是在每次划分分组时都会消耗特征。
-
如果数据集已经处理完所有属性，但是类标签依然不是唯一的，此时需要决定如何定义该叶子节点，通常采用多数表决的方法决定该叶子的分类
投票表决代码：
代码开头加上
import operator
def majorityCnt(classList): #分类名称的列表
classCount = {}
for vote in classList: #创建键值为classList为唯一值的数据字典
if vote not in classList.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]
myTree = {bestFeatLabel:{}} #用字典存储树的信息
labels = labels[:]
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet] #得到列表包含的所有属性值
uniqueVals = set(featValues)
#遍历当前特征包含所有属性值，在每个数据集划分上递归调用函数createTree()
for value in uniqueVals:
subLabels = labels[:] #复制类标签
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree
运行：
>>> reload(trees)
<module 'trees' from 'D:\\Data\\File\\ML\\trees\\trees.py'>
>>> myDat, labels = trees.createDataSet()
>>> myTree = trees.createTree(myDat, labels)
>>> myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
这棵树有3个叶子节点，2个判断节点
学习自
信息熵（香农熵）、条件熵、信息增益的简单了解
《机器学习实战》
网友评论