1、算法思想：从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点；每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点。最后将实例分配到叶节点的类中。
k近邻算法可以完成多分类任务，缺点是无法给出数据的内在含义，决策树的主要优势在于数据形式容易理解
2、伪代码：
思路是：如果某个分支下的数据属于同一类型，则无需分割 返回类标签；如果数据子集的数据不属于同一类型，则需要重复划分数据子集，直到相同类型的数据在同一个数据子集内。
3、度量数据集的无须程度
划分数据集的原则是将无序的数据变得有序，集合信息的度量方式称为香农熵
熵越高 混合的数据越多，得到熵之后就可以按照最大信息增益的方法划分数据集
测量信息熵-划分的数据集-度量划分数据集的熵
代码如下：
# -*- coding: utf-8 -*- from math import log import operator #创建数据集 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 #计算香农熵 def calcShannonEnt(dataSet): numEntries = len(dataSet) labelCounts = {} #字典 for featVec in dataSet: #the the number of unique elements and their occurance currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0.0 for key in labelCounts: #字典的运用,dict[key]=value prob = float(labelCounts[key])/numEntries shannonEnt -= prob * log(prob,2) #log base 2 return shannonEnt #划分数据集 def splitDataSet(dataSet,axis,value): retDataSet=[] for featVec in dataSet: if featVec[axis]==value: reduceFeatVec=featVec[:axis] reduceFeatVec.extend(featVec[axis+1:]) retDataSet.append(reduceFeatVec) #append() 向列表尾部追加一个新元素，列表只占一个索引位，在原有列表上增加,如果处理对象是列表 则将整个列表作为一个元素添加 #extend() 向列表尾部追加一个列表，将列表中的每个元素都追加进来，在原有列表上增加 return retDataSet #选择最好的数据集划分方式 def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0])-1 #特征的个数 bestEntroy = calcShannonEnt(dataSet) #entroy熵,初始值设为数据集的熵 bestInfoGain = 0.0 #信息增益初始值 bestFeature = -1 for i in range(numFeatures): featureList = [example[i] for example in dataSet] #第i个特征所有的取值 uniqueVals = set(featureList) #去重,set表示集合 集合的特点是每个值互不相同 从列表中创建集合可以得到列表中的唯一元素值 newEntropy = 0.0 for value in uniqueVals: #对每一种唯一属性划分数据集 subDataSet = splitDataSet(dataSet,i,value) prob = len(subDataSet)/float(len(subDataSet)) newEntropy += prob * calcShannonEnt(subDataSet) ##每种划分方式经验条件熵的和 infoGain = bestEntroy - newEntropy ##信息增益 if infoGain > bestInfoGain: bestInfoGain = infoGain bestFeature = i return bestFeature #多数表决规则 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 ) return sortedClassCount[0][0] #创建树函数代码 def createTree(dataSet,labels): #将dataSet中最后一列的元素（也就是类标签）放入到classList列表中 classList = [example[-1] for example in dataSet] # count()方法用于统计字符串里某个字符出现的次数 #若相等表示List中的标签属于同一列别 if classList.count(classList[0]) == len(classList): return classList[0] # len()方法返回字符串长度或者列表元素个数 #表示只有类别列，没有属性列 if len(dataSet[0])==1: #多数表决原则 返回出现次数最多的列别 return mahorityCnt(classList) #确定当前最优的分类特征 bestFeat = chooseBestFeatureToSplit(dataSet) #在特征标签列表中获取该特征对应的值 bestFeatLabel = labels[bestFeat] #按照字典嵌套字典的方式 存储分类树信息 myTree = {bestFeatLabel:{}} del(labels[bestFeat])#删除最优属性 featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) ##去重 for value in uniqueVals: subLabels = labels[:] myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)#递归计算分类树 return myTree #--------------以上完成了决策树的构建---------------- #--------------以下的是使用决策树分类---------------- #完成决策树的构造后，采用决策树实现具体应用 def classify(inputTree,featLabels,testVec): #找到树的第一个分类特征，或者说根节点'no surfacing' #注意python2和3区别，2可写成firstStr=inputTree.keys()[0] 而不支持3 firstStr=list(inputTree.keys())[0] #从树中得到该分类特征的分支，有0和1 secondDict=inputTree[firstStr] #根据分类特征的索引找到对应的标称型数据值 #'no surfacing'对应的索引为0 featIndex=featLabels.index(firstStr) #遍历分类特征所有的取值 for key in secondDict.keys(): #测试实例的第0个特征取值等于第key个子节点 if testVec[featIndex]==key: #type()函数判断该子节点是否为字典类型 if type(secondDict[key]).__name__=='dict': #子节点为字典类型，则从该分支树开始继续遍历分类 classLabel=classify(secondDict[key],featLabels,testVec) #如果是叶子节点，则返回节点取值 else: classLabel=secondDict[key] return classLabel #--------------决策树的存储---------------- #构造决策树好费时间，因此可以将构造好的决策树存储起来下次直接用 #决策树的存储：python的pickle模块序列化决策树对象，使决策树保存在磁盘中 def storeTree(inputTree,filename): #导入pickle模块 import pickle #创建一个可以'写'的文本文件 #pickle存储方式默认是二进制方式 #这里，如果按树中写的'w',将会报错write() argument must be str,not bytes #所以这里改为二进制写入'wb' fw=open(filename,'wb') #pickle的dump函数将决策树写入文件中 pickle.dump(inputTree,fw) #写完成后关闭文件 fw.close() #取决策树操作 def grabTree(filename): import pickle #对应于二进制方式写入数据，'rb'采用二进制形式读出数据 fr=open(filename,'rb') return pickle.load(fr) #--------------示例：使用决策树预测隐形眼镜类型---------------- def predictLensesType(filename): #打开文本数据 fr=open(filename) #将文本数据的每一个数据行按照tab键分割，并依次存入lenses lenses=[inst.strip().split('\t') for inst in fr.readlines()] #创建并存入特征标签列表 lensesLabels=['age','prescript','astigmatic','tearRate'] #根据继续文件得到的数据集和特征标签列表创建决策树 lensesTree=createTree(lenses,lensesLabels) return lensesTree def test(): myData, labels = createDataSet() myTree = createTree(myData, labels) # 再创建一次数据的原因是创建决策树函数会将labels值改动 myData, labels = createDataSet() print (classify(myTree, labels, [1,1])) # 主方法 if __name__ == "__main__": myData,labels=tree.createDataSet() myTree=tree.createTree(myData,labels) print (myTree)