判断是否适合外出的决策树决策树:决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。Entropy(熵) = 系统的凌乱程度,使用算法ID3, C4.5和C5.0生成树算法得出熵,这一度量是基于信息学理论中熵的概念。决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。决策树是一种十分常用的分类方法,是一种监督学习。
决策树的构造
在构造决策树时,我们需要解决的第一个问题就是,当前数据集上那个特征在划分数据分类时起决定性的作用。为了找到决定性的特征,划分出最好的结果,我们必须评估每个特征。完成测试之后,原始数据集就会被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型,则已正确划分数据类型,如过不同,则需重复划分数据子集。划分数据子集的算法和原始数据相同,直到所有的节点都是同一类型为止。
信息增益
上面说到我们需要找到决定性的特征来划分出最好的结果,这也是决策树核心问题所在,那怎么确定这个最优特征呢?我们常用的方法就是用信息论中的信息增益来确定这个特征。
在划分数据集之前之后信息发生的变化叫做信息增益,知道如何计算信息增益,获得计算增益最高的特征就是最好的选择。
在1948年,香农引入了信息熵,将其定义为离散随机事件出现的概率,一个系统越有序,信息熵就越低,反之一个系统越混乱,它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。
熵定义为信息的期望值,既然是要算期望,就得先知道信息的定义。如果待分类的事件可能划分在多个分类之中,则事件(Xi)的信息定义为:
info(xi) = -log2p(xi)
其中p(xi)是选择该类别的概率。
为了计算熵,需要计算出信息的期望,即:(这里要吐槽一下简书,不支持MathJax,所以只能找图片替代公式)
接下来以气象数据为例子,来说明决策树的构建过程:
outlook | temperature | humidity | windy | play |
---|---|---|---|---|
sunny | hot | high | FALSE | no |
sunny | hot | high | TRUE | no |
overcast | hot | high | FALSE | yes |
rainy | mild | high | FALSE | yes |
rainy | cool | normal | FALSE | yes |
rainy | cool | normal | TRUE | no |
overcast | cool | normal | TRUE | yes |
sunny | mild | high | FALSE | no |
sunny | cool | normal | FALSE | yes |
rainy | mild | normal | FALSE | yes |
sunny | mild | normal | TRUE | yes |
overcast | mild | high | TRUE | yes |
overcast | hot | normal | FALSE | yes |
rainy | mild | high | TRUE | no |
在没有使用特征划分类别的情况下,有9个yes和5个no,当前的熵为:
计算熵
假设我们以 outlook 特征划分数据集,对该特征每项指标分别统计:在不同的取值下 play 和 no play 的次数:
outlook | yes | no |
---|---|---|
sunny | 2 | 3 |
overcast | 4 | 0 |
rainy | 3 | 2 |
此时各分支的熵计算如下:
因此如果用特征outlook来划分数据集的话,总的熵为:
outlook划分后的总熵
那么最终得到特征属性outlook带来的信息增益为:IG(outlook)=0.940−0.694=0.246,然后用同样的方法,可以分别求出temperature,humidity,windy的信息增益。IG(temperature)=0.029,IG(humidity)=0.152,IG(windy)=0.048。可以得出使用outlook特征所带来的信息增益最大,所以应该首先选择outlook来划分数据集。然后继续划分各个分支的数据集,知道每个分支下的所有实例都具有相同的分类。最终构造出决策树:
最终的决策树(图片源自网络)
决策树代码实现
1. 计算香农熵
# 计算香农熵
def calShannonEntropy(dataSet):
numEntries = len(dataSet) # 数据总数
labelCounts = {}
for featureVect in dataSet:
currentLabel = featureVect[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
probability = float(labelCounts[key]) / numEntries
shannonEnt -= probability * log(probability, 2)
return shannonEnt
2. 按照给定的特征划分数据集
# 划分数据集
def splitDataSet(dataSet, featureIndex, featureValue):
newDataSet = []
for featVec in dataSet:
if featVec[featureIndex] == featureValue:
reducedFeatVec = featVec[:featureIndex]
reducedFeatVec.extend(featVec[featureIndex+1:])
newDataSet.append(reducedFeatVec)
return newDataSet
3. 选择最佳特征值划分数据集
def chooseBestFeatureToSplit(dataSet):
numFeature = len(dataSet[0]) - 1
baseEntropy = calShannonEntropy(dataSet)
bestFeature = -1; bestInfoGain = 0
for i in range(numFeature):
featList = [entry[i] for entry in dataSet] # 取出每一种属性
uniqueValue = set(featList) # 得到该属性有哪些值(用集合的方法去掉重复值)
newEntropy = 0.0
for value in uniqueValue:
subDataSet = splitDataSet(dataSet, i, value)
probility = len(subDataSet) / float(len(dataSet))
newEntropy += probility * calShannonEntropy(subDataSet)
infoGain = baseEntropy - newEntropy
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
return bestFeature
4. 投票决定不确定结果
如果数据集已经处理了所有属性,但是类标签依然不是唯一的,通常我们才有多数表决的方法决定该叶子节点的分类。
# 找出票数最多的标签
def majorityVote(classList):
classCount = {}
for vote in classList:
if vote not in classList.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reversed=True)
return sortedClassCount[0][0]
5. 创建决策树
def createTree(dataset, labels):
# 取出位于最后一列的类别标签
classList = [label[-1] for label in dataset]
if classList.count(classList[0]) == len(classList): # 类别完全相同时,停止划分
return classList[0] # 返回唯一特征值
if len(dataset[0]) == 1: # 已经遍历完所有特征,只剩最后一列类别标签
return majorityVote(classList) # 返回票数最多的类标签
# 开始划分
# 先选取最好的划分特征值
bestFeature = chooseBestFeatureToSplit(dataset)
bestFeatureLabel = labels[bestFeature]
# 初始化树
myTree = {bestFeatureLabel: {}}
subLabels = labels[:]
del subLabels[bestFeature]
# 递归构建决策树
featList = [entry[bestFeature] for entry in dataset]
uniqueValues = set(featList)
for value in uniqueValues:
myTree[bestFeatureLabel][value] = createTree(splitDataSet(dataset, bestFeature, value), subLabels)
return myTree
6. 使用决策树执行分类
# 使用决策树执行分类
def classify(inputTree, featLabels, testVec):
# 取出根节点,python2直接写成inputTree.keys()[0]
firstStr = list(inputTree.keys())[0]
# 找到根节点下面的分支(该分类特征的分支)
childDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
# 遍历分类特征的所有取值
for key in childDict.keys():
# 如果测试向量的该类值等于分类特征的第key个节点
if testVec[featIndex] == key:
# 判断该节点是否为字典类型
if type(childDict[key]).__name__ == 'dict':
# 是字典类型,继续遍历
classLabel = classify(childDict[key], featLabels, testVec)
else:
# 不是字典,返回最终结果
classLabel = childDict[key]
return classLabel
7. 存储决策树
构建决策树是非常耗时的任务,即使很小的数据集,也要花费几秒的时间来构建决策树,这样显然耗费计算时间。所以,我们可以将构建好的决策树保存在磁盘中,这样当我们需要的时候,再从磁盘中读取出来使用即可。为了解决这个问题,可以使用pickle序列化对象,任何对象都可以执行序列化操作,字典对象也不例外。
网友评论