决策树
决策树也是经常使用的数据挖掘算法，其不用了解机器学习的知识，就能搞明白决策树是如何工作的。
image.png
决策树算法能够读取数据聚合，构建类似上图的决策树。决策树的 一个重要任务是为了理解数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取一系列规则，这些机器根据数据集创建规则的过程，就是机器学习的过程。
信息增益
在构造决策树的时候，需要解决的第一个问题就是，当前数据集在哪个特征上划分数据分类起到决定性的作用。
划分数据集的大原则是：将无序的数据变得更加有序。信息增益(熵)定义为信息的期望值，如果待分类的事务可能划分在多个分类之中，则符号
其中 表示选择该分类的概率
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，
from math import log
'''
计算给定数据集的香农熵
'''
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
print(featVec)
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
print(labelCounts)
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
测试香农熵的计算
if __name__ == '__main__':
myDat,labels = createDataSet()
result = calcShannonEnt(myDat)
print(result)
>>>0.9709505944546686
划分数据集
分类算法除了需要测量信息熵，还需要划分数据集，度量划分数据集的熵，一遍判断当前是否正确的划分了数据集。我们需要将每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。
'''
param dataSet 带划分的数据集
param axis 划分数据集的特征
param value 需要返回的特征的值
'''
def splitDataSet(dataSet,axis,value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reduceFeactVec = featVec[:axis]
reduceFeactVec.extend(featVec[axis+1:])
retDataSet.append(reduceFeactVec)
return retDataSet
if __name__ == '__main__':
myDat,labels = createDataSet()
result = splitDataSet(myDat,0,1) #calcShannonEnt(myDat)
print(result)
>>> [[1, 'yes'], [1, 'yes'], [0, 'no']]
遍历数据集中所有的特征，按照特征选出最好的特征划分方式
'''
选择最好的数据划分方式
'''
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #每组数据特征的个数 出去标签
baseEntropy = calcShannonEnt(dataSet) #整个数据集的原始香农熵
bestInfoGain = 0.0;bestFeature = -1
print(numFeatures)
for i in range(numFeatures):
featList = [example[i] for example in dataSet] #返回数据集重所有的第i个特征的特征值
print("featList:",featList)
uniqueVals = set(featList) #去重
print("uniqueVals:",uniqueVals)
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
if __name__ == '__main__':
myDat,labels = createDataSet()
result = chooseBestFeatureToSplit(myDat)
print(result)
>>> 0 说明第一个特征是最好的划分方式
chooseBestFeatureToSplit 调用之前需要做数据处理。数据必须是一种由列表元素组成的列表，而且所有的列表具有相同的数据长度；数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签。
递归构建决策树
得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能过于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上我们再次划分数据。可以采用递归的原则处理数据。
递归结束的条件是:程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。
'''
返回出现次数最多的分类名称
'''
def majorityCnt(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)
print(sortedClassCount)
return sortedClassCount[0][0]
'''
构建决策树
'''
def createTree(dataSet,labels):
classList = [example[-1] for example in dataSet]
# print(classList)
tmplabels = labels[:]
if classList.count(classList[0]) == len(classList): #返回数组中classList[0]出现的次数
return classList[0]
# print("dataSet",dataSet)
if len(dataSet[0]) == 1:
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = tmplabels[bestFeat]
print(bestFeatLabel)
myTree = {bestFeatLabel:{}}
del(tmplabels[bestFeat]) #删除已经计算过的在标签组中的标签
featValues = [example[bestFeat] for example in dataSet] #获取数据集中bestFeat特征对应的值
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = tmplabels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels) #递归计算
return myTree
if __name__ == '__main__':
myDat,labels = createDataSet()
print(myDat)
result = createTree(myDat,labels)
print("result:",result)
>>> {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
测试算法
依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类
'''
测试分类函数
param inputTree 已构造好的树
param featLabels 数据集的标签
param testVec 要测试数据的特征值 与训练数据集的特征值结构一样
'''
def classify(inputTree,featLabels,testVec):
temLabel = featLabels[:]
firstStr = list(inputTree.keys())[0]
secondDict = inputTree[firstStr]
# print(firstStr)
featIndex = temLabel.index(firstStr)
for key in secondDict.keys():
if testVec[featIndex] == key:
if type(secondDict[key]).__name__ == 'dict':
classLabel = classify(secondDict[key],temLabel,testVec)
else: classLabel = secondDict[key]
return classLabel
if __name__ == '__main__':
myDat,labels = createDataSet()
result = createTree(myDat,labels) #splitDataSet(myDat,1,0) #calcShannonEnt(myDat)
cls = classify(result,labels,[1,0])
print(cls)
>>> no
网友评论