#### 样例代码

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

#### 香农熵算法

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

#### 按照香农熵划分数据

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)