机器学习决策树算法学习笔记

作者：xiabigao

基本概念

决策树是分类算法。

数据类型：数值型和标称型。因为构造算法只适用于标称型，所以数值型数据必须离散化。

工作原理

利用香浓熵找到信息增益最大的特征，按照信息增益最大的特征划分数据，如此反复，让无序的数据变的更加有序。使用ID3算法构建树结构。当传入一个新数据时，按照数据找到对应树节点，直到最后没有叶子节点时，完成分类。

样例

不浮出水面是否可以生存？ 是否有脚蹼？ 是否是鱼类？

通过“不浮出水面是否可以生存”和“是否有脚蹼”这两个特征来判断是否是鱼类。构建一个简单决策树，如果得到一个新的生物，可以用此来判断是否是鱼类。

样例代码

defcreateDataSet():dataSet = [[1, 1, ‘yes’], [1, 1, ‘yes’], [1, 0, ‘no’], [0, 1, ‘no’], [0, 1, ‘no’]] labels = [‘no surfacing’,’flippers’] returndataSet, labels

香农熵公式

如果待分类的事务可能划分在多个分类之中，则符号Xi的信息定义为：

其中P(Xi)是选择该分类的概率

为了计算熵，需要计算所有类别所有可能值包含的信息期望值总和，公式为：

其中n是分类的数目

香农熵算法

defcalcShannonEnt(dataSet):# 选择该分类的概率 就是每个类型/总个数# 总数，多少行数据numEntries = len(dataSet) labelCounts = {} # 取到的每个类型个数forfeatVec indataSet: currentLabel = featVec[-1] ifcurrentLabel notinlabelCounts.keys(): labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1shannonEnt = 0.0forkey inlabelCounts: # 得到选择该分类的概率prob = float(labelCounts[key])/numEntries # 按照公式shannonEnt -= prob * log(prob,2) #log base 2returnshannonEnt

按照香农熵划分数据

除了需要测量信息熵，还需要划分数据集，度量花费数据集的熵，以便判断当前是否正确划分。 循环计算香浓熵和splitDataSet()，找到最好的特征划分方式。

defsplitDataSet(dataSet, axis, value):# 这个算法返回axis下标之外的列retDataSet = [] forfeatVec indataSet: iffeatVec[axis] == value: reducedFeatVec = featVec[:axis] #chop out axis used for splittingreducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) returnretDataSet defchooseBestFeatureToSplit(dataSet):# 先取最后一列，用在标签结果：是鱼或不是鱼。numFeatures = len(dataSet[0]) – 1# 原始香浓熵baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0; bestFeature = -1# 遍历所有的特征fori inrange(numFeatures): # 创建一个列表包含这个特征的所有值featList = [example[i] forexample indataSet] # 利用set去重uniqueVals = set(featList) newEntropy = 0.0# 计算该特征所包含类型的香浓熵之和forvalue inuniqueVals: 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 # 返回下标returnbestFeature

数据集需要满足一定的要求：

数据必须是一种有列表元素组成的列表。（二维数组）所有列表元素必须有相同长度。最后一列必须是当前实例的标签。

递归构建决策树

多数表决算法

如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决决定该叶子节点。

importoperator defmajorityCnt(classList):# 排序取出种类最多的classCount={} forvote inclassList: ifvote notinclassCount.keys(): classCount[vote] = 0classCount[vote] += 1sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) returnsortedClassCount[0][0]

构建树算法

defcreateTree(dataSet,labels):# 取出结果classList = [example[-1] forexample indataSet] # 如果结果里的第一个元素所代表的数据个数等于结果本身，说明没有其他分类了ifclassList.count(classList[0]) == len(classList): returnclassList[0] # 如果没有更多数据了，超过一个才有分类的意义iflen(dataSet[0]) == 1: # 多数表决，返回出现次数最多的returnmajorityCnt(classList) # 选出最适合用于切分类型的下标bestFeat = chooseBestFeatureToSplit(dataSet) # 根据下标取出标签bestFeatLabel = labels[bestFeat] # 构建树myTree = {bestFeatLabel:{}} # 删除取出过的标签，避免重复计算del(labels[bestFeat]) featValues = [example[bestFeat] forexample indataSet] # 利用set去重uniqueVals = set(featValues) forvalue inuniqueVals: # 复制所有的子标签，因为是引用类型，以避免改变原始标签数据subLabels = labels[:] # 递归的构建树myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels) returnmyTree

使用决策树分类

defclassify(inputTree,featLabels,testVec):firstStr = inputTree.keys()[0] secondDict = inputTree[firstStr] featIndex = featLabels.index(firstStr) # print ‘featIndex %s’ % (featIndex)key = testVec[featIndex] # print ‘key %s’ % (key)valueOfFeat = secondDict[key] ifisinstance(valueOfFeat, dict): classLabel = classify(valueOfFeat, featLabels, testVec) else: classLabel = valueOfFeat returnclassLabel dataSet, labels = createDataSet() mytree = createTree(dataSet, labels[:]) #因为内部会删除labels里的值所以用这样copy一份 printmytree # {‘no surfacing’: {0: ‘no’, 1: {‘flippers’: {0: ‘no’, 1: ‘yes’}}}}printclassify(mytree, labels, [0,1]) no

决策树的存储

构造决策树是耗时的任务，即使处理很小的数据集。所以我们可以使用构造好的决策树。

defstoreTree(inputTree,filename):importpickle fw = open(filename,’w’) pickle.dump(inputTree,fw) fw.close() defgrabTree(filename):importpickle fr = open(filename) returnpickle.load(fr)

优点

计算复杂度不高输出结果易于理解对中间值缺失不敏感可以处理不相关特侦

缺点

可能产生过度匹配问题