摘要:
决策树是机器学习中一种非常常见的分类与回归方法, 可以认为是 if-else 结构的规则. 分类决策树是由节点和有向边组成的树形结构, 节点表示特征或者属性,
而边表示的是属性值, 边指向的叶节点为对应的分类. 在对样本的分类过程中, 由顶向下, 根据特征或属性值选择分支, 递归遍历直到叶节点, 将实例分到叶节点对应的类别中.
决策树的学习过程就是构造出一个能正取分类 (或者误差最小) 训练数据集的且有较好泛化能力的树, 核心是如何选择特征或属性作为节点,
通常的算法是利用启发式的算法如 ID3,C4.5,CART 等递归的选择最优特征. 选择一个最优特征, 然后按照此特征将数据集分割成多个子集, 子集再选择最优特征,
直到所有训练数据都被正取分类, 这就构造出了决策树. 决策树有如下特点:
原理简单, 计算高效; 使用基于信息熵相关的理论划分最优特征, 原理清晰, 计算效率高.
解释性强; 决策树的属性结构以及 if-else 的判断逻辑, 非常符合人的决策思维, 使用训练数据集构造出一个决策树后, 可视化决策树,
可以非常直观的理解决策树的判断逻辑, 可读性强.
效果好, 应用广泛; 其拟合效果一般很好, 分类速度快, 但也容易过拟合, 决策树拥有非常广泛的应用.
本文主要介绍基于 ID3 的算法构造决策树.
决策树原理
训练数据集有多个特征, 如何递归选择最优特征呢? 信息熵增益提供了一个非常好的也非常符合人们日常逻辑的判断准则, 即信息熵增益最大的特征为最优特征. 在信息论中, 熵是用来度量随机变量不确定性的量纲, 熵越大, 不确定性越大. 熵定义如下:
此处 log 一般是以 2 为底, 假设一个产品成品率为 100% 次品率为 0% 那么熵就为 0, 如果是成品率次品率各为 50%, 那么熵就为 1, 熵越大, 说明不确定性越高, 非常符合我们人类的思维逻辑. 假设分类标记为随机变量 Y, 那么 H(Y)表示随机变量 Y 的不确定性, 我们依次选择可选特征, 如果选择一个特征后, 随机变量 Y 的熵减少的最多, 表示得知特征 X 后, 使得类 Y 不确定性减少最多, 那么就把此特征选为最优特征. 信息熵增益的公式如下:
ID3 算法
决策树基于信息熵增益的 ID3 算法步骤如下:
如果数据集类别只有一类, 选择这个类别作为, 标记为叶节点.
从数据集的所有特征中, 选择信息熵增益最大的作为节点, 特征的属性分别作为节点的边.
选择最优特征后, 按照对应的属性, 将数据集分成多个, 依次将子数据集从第 1 步递归进行构造子树.
python 实现
- #encoding:utf-8
- import pandas as pd
- import numpy as np
- class DecisionTree:
- def __init__(self):
- self.model = None
- def calEntropy(self, y): # 计算熵
- valRate = y.value_counts().apply(lambda x : x / y.size) # 频次汇总 得到各个特征对应的概率
- valEntropy = np.inner(valRate, np.log2(valRate)) * -1
- return valEntropy
- def fit(self, xTrain, yTrain = pd.Series()):
- if yTrain.size == 0:# 如果不传, 自动选择最后一列作为分类标签
- yTrain = xTrain.iloc[:,-1]
- xTrain = xTrain.iloc[:,:len(xTrain.columns)-1]
- self.model = self.buildDecisionTree(xTrain, yTrain)
- return self.model
- def buildDecisionTree(self, xTrain, yTrain):
- propNamesAll = xTrain.columns
- #print(propNamesAll)
- yTrainCounts = yTrain.value_counts()
- if yTrainCounts.size == 1:
- #print('only one class', yTrainCounts.index[0])
- return yTrainCounts.index[0]
- entropyD = self.calEntropy(yTrain)
- maxGain = None
- maxEntropyPropName = None
- for propName in propNamesAll:
- propDatas = xTrain[propName]
- propClassSummary = propDatas.value_counts().apply(lambda x : x / propDatas.size)# 频次汇总 得到各个特征对应的概率
- sumEntropyByProp = 0
- for propClass, dvRate in propClassSummary.items():
- yDataByPropClass = yTrain[xTrain[propName] == propClass]
- entropyDv = self.calEntropy(yDataByPropClass)
- sumEntropyByProp += entropyDv * dvRate
- gainEach = entropyD - sumEntropyByProp
- if maxGain == None or gainEach> maxGain:
- maxGain = gainEach
- maxEntropyPropName = propName
- #print('select prop:', maxEntropyPropName, maxGain)
- propDatas = xTrain[maxEntropyPropName]
- propClassSummary = propDatas.value_counts().apply(lambda x : x / propDatas.size)# 频次汇总 得到各个特征对应的概率
- retClassByProp = {}
- for propClass, dvRate in propClassSummary.items():
- whichIndex = xTrain[maxEntropyPropName] == propClass
- if whichIndex.size == 0:
- continue
- xDataByPropClass = xTrain[whichIndex]
- yDataByPropClass = yTrain[whichIndex]
- del xDataByPropClass[maxEntropyPropName]# 删除已经选择的属性列
- #print(propClass)
- #print(pd.concat([xDataByPropClass, yDataByPropClass], axis=1))
- retClassByProp[propClass] = self.buildDecisionTree(xDataByPropClass, yDataByPropClass)
- return {'Node':maxEntropyPropName, 'Edge':retClassByProp}
- def predictBySeries(self, modelNode, data):
- if not isinstance(modelNode, dict):
- return modelNode
- nodePropName = modelNode['Node']
- prpVal = data.get(nodePropName)
- for edge, nextNode in modelNode['Edge'].items():
- if prpVal == edge:
- return self.predictBySeries(nextNode, data)
- return None
- def predict(self, data):
- if isinstance(data, pd.Series):
- return self.predictBySeries(self.model, data)
- return data.apply(lambda d: self.predictBySeries(self.model, d), axis=1)
- dataTrain = pd.read_csv("xiguadata.csv", encoding = "gbk")
- decisionTree = DecisionTree()
- treeData = decisionTree.fit(dataTrain)
- print(pd.DataFrame({'预测值':decisionTree.predict(dataTrain), '正取值':dataTrain.iloc[:,-1]}))
- import JSON
- print(JSON.dumps(treeData, ensure_ascii=False))
训练结束后, 使用一个递归的字典保存决策树模型, 使用格式 JSON 工具格式化输出后, 可以简洁的看到树的结构.
R 语言实现
- dataTrain <- read.CSV("xiguadata.csv", header = TRUE)
- trainDecisionTree <- function(dataTrain){
- calEntropy <- function(y){ # 计算熵
- values <- table(unlist(y)); # 频次汇总 得到各个特征对应的概率
- valuesRate <- values / sum(values);
- logVal = log2(valuesRate);# log2(0) == infinite
- logVal[is.infinite(logVal)]=0;
- valuesEntropy <- -1 * t(valuesRate) %*% logVal;
- if (is.nan(valuesEntropy)){
- valuesEntropy = 0;
- }
- return(valuesEntropy);
- }
- propNamesAll <- names(dataTrain)
- propNamesAll <- propNamesAll[length(propNamesAll) * - 1]
- print(propNamesAll)
- buildDecisionTree <- function(propNames, dataSet){
- classColumn = dataSet[, length(dataSet)]# 最后一列是类别标签
- classSummary <- table(unlist(classColumn))# 频次汇总
- defaultRet = c(propNames[1], names(classSummary)[which.max(classSummary)]);
- if (length(classSummary) == 1){# 如果所有的都是同一类别, 那么标记为叶节点
- return(defaultRet);
- }
- if (length(propNames) == 1){# 如果只剩一种属性了, 那么返回样本数量最多的类别作为节点
- return(defaultRet);
- }
- entropyD <- calEntropy(classColumn)
- propGains = sapply(propNames, function(propName){ # propName 对应的是 "色泽" "根蒂" "敲声" "纹理" "脐部" "触感"
- propDatas <- dataSet[c(propName)]
- propClassSummary <- table(unlist(propDatas))# 频次汇总
- retGain <- sapply(names(propClassSummary), function(propClass){# propClass 对应色泽的种类 如 浅白 青绿 乌黑
- dataByPropClass <- subset(dataSet, dataSet[c(propName)] == propClass); #筛选出色泽等于 种类 propClass 的数据集
- entropyDv <- calEntropy(dataByPropClass[, length(dataByPropClass)]) #最后一列是标记是否为好瓜
- Dv = propClassSummary[c(propClass)][1]
- return(entropyDv * Dv);# 这里没有直接除 | D|, 最后累加后再除, 等价的
- });
- return(entropyD - sum(retGain)/sum(propClassSummary));
- });
- #print(propGains);
- maxEntropyProp = propGains[which.max(propGains)];# 选择信息熵增益最大的属性
- propName = names(maxEntropyProp)[1]
- #print(propName)
- propDatas <- dataSet[c(propName)]
- propClassSummary <- table(unlist(propDatas))# 频次汇总
- propClassSummary <- propClassSummary[which(propClassSummary> 0)]
- propClassNames <- names(propClassSummary)
- #propClassNames = c(propClassNames[1])
- retGain <- sapply(propClassNames, function(propClass){# propClass 对应色泽的种类 如 浅白 青绿 乌黑
- dataByPropClass <- subset(dataSet, dataSet[c(propName)] == propClass); #筛选出色泽等于 种类 propClass 的数据集
- leftClassNames = propNames[which(propNames==propName) * -1] #去掉这个属性, 递归构造决策树
- ret = buildDecisionTree(leftClassNames, dataByPropClass);
- return(ret);
- });
- #names(retGain) = propClassNames
- retList = retGain
- #retList = list()
- #for (propClass in propClassNames){
- # retList[propClass] = retGain[propClass]
- #}
- #print(retList)
- #索引 1 表示选择的属性名称 索引 2 对应的类别, 如果有子树那么就是 frame, 否则就是类别
- ret = list(propName, retList)
- #ret = data.frame(c(retList))
- #names(ret) = c(propName)
- return(ret);
- }
- retProp = buildDecisionTree(propNamesAll, dataTrain);
- return(retProp);
- }
- decisionTree = trainDecisionTree(dataTrain)
- #print(decisionTree)
- library("rpart")
- library("rpart.plot")
- dataTrain <- read.CSV("xiguadata.csv", header = TRUE)
- print(dataTrain)
- fit <- rpart(HaoGua~.,data=dataTrain,control = rpart.control(minsplit = 1, minbucket = 1),method="class")
- printcp(fit)
- rpart.plot(fit, branch = 1, branch.type = 1, type = 2, extra = 102,shadow.col='gray', box.col='green',border.col='blue', split.col='red',main="DecisionTree")
- #library(jsonlite)
- #dataJson = toJSON(decisionTree)
- #c <- file( "result.txt", "w" )
- #writeLines(dataJson, c )
- #close( c ) #这里需要主动关闭文件
- #for (k in propNames) {
- # eachData <- dataSet[c(k)]
- # values <- table(unlist(eachData))# 频次汇总
- # #print(values)
- # print(k)
- # total <- 0
- # for (m in names(values)) {
- # #print(m)
- # #print(values[m][1])
- # data3 <- subset(dataSet, dataSet[c(k)] == m)
- # entropyDv <- calEntropy(data3[, length(data3)])
- # #print(entropyDv)
- # total = total + entropyDv*values[c(m)][1]
- # }
- # GainDv <- entropyD - total / sum(values);+
- # print(GainDv)
- #}
R 语言代码包含本人自己编写的 R 语言 ID3 算法, 最后使用 R 的 rpart 包训练了一个决策树.
总结:
ID3 算法简洁清晰, 符合人类思路方式.
决策树的解释性强, 可视化后也方便理解模型和验证正确性.
ID3 算法时候标签类特征的样本, 对应具有连续型数值的特征, 无法运行此算法.
有过拟合的风险, 要通过剪枝来避免过拟合.
信息增益有时候偏爱属性很多的特征, C4.5 和 CART 算法可以对此有优化.
这是我的 GitHub 主页 https://github.com/fanchy, 有些有意思的分享.
python 相比 R 语言写起来还是溜多了, 主要是遍历和嵌套, python 比 R 要容易很多, R 的数据筛选和选择方便一点, 这个 python 版本的 id3 算法写的还是很清晰简洁的 正是 Talk is cheap. Show me the code. 这是在网上可以看到原生实现版本中, 最精简的版本之一.
对应的西瓜书数据集为
色泽 根蒂 敲声 纹理 脐部 触感 HaoGua
青绿 蜷缩 浊响 清晰 凹陷 硬滑 是
乌黑 蜷缩 沉闷 清晰 凹陷 硬滑 是
乌黑 蜷缩 浊响 清晰 凹陷 硬滑 是
青绿 蜷缩 沉闷 清晰 凹陷 硬滑 是
浅白 蜷缩 浊响 清晰 凹陷 硬滑 是
青绿 稍蜷 浊响 清晰 稍凹 软粘 是
乌黑 稍蜷 浊响 稍糊 稍凹 软粘 是
乌黑 稍蜷 浊响 清晰 稍凹 硬滑 是
乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑 否
青绿 硬挺 清脆 清晰 平坦 软粘 否
浅白 硬挺 清脆 模糊 平坦 硬滑 否
浅白 蜷缩 浊响 模糊 平坦 软粘 否
青绿 稍蜷 浊响 稍糊 凹陷 硬滑 否
浅白 稍蜷 沉闷 稍糊 凹陷 硬滑 否
乌黑 稍蜷 浊响 清晰 稍凹 软粘 否
浅白 蜷缩 浊响 模糊 平坦 硬滑 否
青绿 蜷缩 沉闷 稍糊 稍凹 硬滑 否
来源: https://www.cnblogs.com/zhiranok/p/decisiontree.html