Python实现决策树(Decision Tree)算法

||
字数总计:2.2k|阅读时长:9分钟|阅读量:…
文章最后更新于 1564 天前,其中的信息可能已经过时。

决策树算法基础原理分析

信息的不纯度(决定决策树分支的指标)

不纯度是在决策树中衡量特征分裂优异性的最主要的指标,用于衡量样本在根据某一特征的分类标准分裂后,样本是否被正确分类的准确程度。

主要有 3 种计算方式,分别对应了 3 类决策树:

决策树类别 不纯度计算方式
ID3 信息增益(Information Gain)
C4.5 信息增益率(Information Gain Ratio)
CART 基尼系数(Gini index)
  • 信息熵的计算 信息熵的计算公式为:

    $ H(D)=-\displaystyle\sum_{i=1}^n p_i log_2 p_i $
    其中$ n $为样本D的类别数,$ p_i $为该样本所占样本总数的比例
  • 信息增益的计算 信息增益的计算公式:

    $ g(D,A)=H(D)-H(D|A) $
    其中,$ H(D|A) $代表在以$ A $为标准分类后的所有样本的信息熵之和
  • 信息增益率 信息增益率的计算公式:

    $$ IGR=\frac{g(D,A)}{H(A)} $$
    其中 $ H(A) $代表 $ A $
  • 基尼系数 基尼系数的计算公式:

    $ Gini(p)=\displaystyle\sum_{i=1}^n p_i (1-p_i) = 1 - \displaystyle\sum_{i=1}^n p_i ^2 $
    其中$ n $为样本D的类别数,$ p_i $为该样本所占样本总数的比例 基尼系数值越小,表示该分类方法贡献的信息度越高,即不纯度越小

特征的最佳切分点

特征的类型分为两种情况:

  • 离散型变量
  • 连续性变量
  1. 对于离散型变量: 可分为二叉树与多叉树
  2. 对于连续性变量
    1. 首先将样本的某一连续变量的值去重后按照升序进行排列
    2. 计算两两相邻的平均值
    3. 遍历,将的每一个点都作为该连续变量的切分点,并计算其分裂的不纯度,获得长度为 n − 1 的不纯度集
    4. 其中最大的不纯度,其切分点即为最佳切分点
  3. 特征在决策树中决策的先后顺序 决策的先后顺序,即为根据不同变量进行分裂的顺序。在找出每个变量的最佳分裂点后,可以计算出以该点分裂所能获得的信息度(信息增益/信息增益率/基尼系数…等),以最大信息度的变量放在最前面进行分裂,最小的放在最后面分裂。这样就确定了在对样本进行区分的时候,越早分裂的样本能以最佳的区分方法进行划分。

ID3, C4.5, CART 对比说明

类型 特点 劣势
ID3 多叉树;特征只用一次;健壮性较好,能训练属性值有缺失的情况 1.当特征取值类型较多时,信息增益会越大,容易造成过拟合;2. 只能用于分类;3. 只能处理离散变量;4. 对缺失值敏感
C4.5 多叉树;特征只用一次;使用信息增益比对特征值多的特征进行惩罚,减少过拟合;可以处理连续变量;可以处理缺失值 处理连续值只是将其离散化,形成多个离散值
CART 二叉树;特征使用多次;可以用于回归任务 -

决策树算法 python 代码实现

创建数据集

PYTHON
def createDataSet():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfaceing', 'flippers']
return dataSet, labels

计算香农熵

PYTHON
# 计算香农熵,分两步,第一步计算频率,第二部根据公式计算香农熵
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for feaVec in dataSet:
currentLabel = feaVec[-1]
if currentLabel not in labelCounts:
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

划分数据集

PYTHON
# 划分数据集,将满足X[aixs]==value的值都划分到一起,返回一个划分好的集合(不包括用来划分的aixs属性,因为不需要)
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

选择划分的最佳属性

PYTHON
# 选择最好的属性进行划分,思路很简单就是对每个属性都划分下,看哪个好。这里使用到了一个set来选取列表中唯一的元素,这是一中很快的方法
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]
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

采用多数表决的方式计算结点分类

PYTHON
# 因为我们递归构建决策树是根据属性的消耗进行计算的,所以可能会存在最后属性用完了,但是分类
# 还是没有算完,这时候就会采用多数表决的方式计算节点分类
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
return max(classCount)

基于递归构造决策树

PYTHON
# 基于递归构建决策树。这里的label更多是对于分类特征的名字,为了更好看和后面的理解。
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: {}}
del (labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:] # 为了不改变原始列表的内容复制了一下
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree

调用函数 构造主函数

PYTHON
def main():
data, label = createDataSet()
# t1 = time.clock()
myTree = createTree(data, label)
# t2 = time.clock()
print(myTree)
# print('execute for ',t2-t1)
if __name__ == '__main__':
main()

完整源代码

PYTHON
#!/user/bin/env python3
# -*- coding: utf-8 -*-
import operator
from math import log
import time
def createDataSet():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfaceing', 'flippers']
return dataSet, labels
# 计算香农熵,分两步,第一步计算频率,第二部根据公式计算香农熵
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for feaVec in dataSet:
currentLabel = feaVec[-1]
if currentLabel not in labelCounts:
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
# 划分数据集,将满足X[aixs]==value的值都划分到一起,返回一个划分好的集合(不包括用来划分的aixs属性,因为不需要)
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
# 选择最好的属性进行划分,思路很简单就是对每个属性都划分下,看哪个好。这里使用到了一个set来选取列表中唯一的元素,这是一中很快的方法
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]
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
# 因为我们递归构建决策树是根据属性的消耗进行计算的,所以可能会存在最后属性用完了,但是分类
# 还是没有算完,这时候就会采用多数表决的方式计算节点分类
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
return max(classCount)
# 基于递归构建决策树。这里的label更多是对于分类特征的名字,为了更好看和后面的理解。
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: {}}
del (labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:] # 为了不改变原始列表的内容复制了一下
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,
bestFeat, value), subLabels)
return myTree
def main():
data, label = createDataSet()
# t1 = time.clock()
myTree = createTree(data, label)
# t2 = time.clock()
print(myTree)
# print('execute for ',t2-t1)
if __name__ == '__main__':
main()

本文源代码参考自 机器学习----决策树 (Decision Tree)算法原理及 python 实现与python 决策树算法原理及基于 numpy 的代码实现

评论

评论加载中…

站内搜索