前言
如果说k-邻近算法还比较简单,那么决策树的构造就涉及到比较多的函数调用,所以我自己将流程画出来,防止自己在各种各样的调用中晕头转向
决策树
k-邻近算法可以完成很多分类任务,但是它存在最大的缺点在于无法给出数据的内在含义
决策树的主要优势在于数据形式非常容易理解
决策树的一个重要任务是为了理解数据中所蕴含的知识信息,因此决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,这些机器根据数据集创建规则的过程,就是机器学习的过程。
决策树的构造
优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据
缺点:可能会产生过度匹配问题
使用数据类型:数值型和标称型
概念:信息增益
划分数据集的大原则是:将无序的数据变得更加有序。
在划分数据集之前之后信息发生的变化称为信息增益,知道如何计算信息增益,我们就可以计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择
集合信息的度量方式称为香农熵或者简称为熵。
熵就是信息量如果我们根据它公式来形容这个概念的话,那么对于一个事物,它的分类越多,越复杂则表明他的熵更大。计算熵的代码:
1 2 3 4 5 6 7 8 9 10 11 12 13
| def calcShannonEnt(dataSet): numEntires=len(dataSet) labelCounts={} for featVec in dataSet: currentLabel=featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel]=0 labelCounts[currentLabel]+=1 shannonEnt=0.0 for key in labelCounts: prob=float(labelCounts[key])/numEntires shannonEnt-=prob*log(prob,2) return shannonEnt
|
上面的代码主要用于计算yes和no这两种分类的熵,用到的dataset定义如下
1 2 3 4 5 6 7 8
| 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
|
划分数据集
我们将每个特征划分数据集的结果计算一次信息熵,然后判断按照哪个特征划分数据集是最好的划分方式
划分数据集只需要构造一个dataset每个特征的子集即可
1 2 3 4 5 6 7 8
| def splitDataSet(dataSet,axis,value): retDataSet=[] for featVec in dataSet: if featVec[axis]==value: reducedFeatVec=featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet
|
创建一个选择最好数据集划分方式的函数,将划分数据集和计算熵的过程加进去,对每一个特征都进行划分数据集和计算熵,把计算出来的熵减去基础熵,算出信息增益,信息增益最多的就是最好的数据集划分方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| def chooseBestFeatureToSplit(dataSet): numFeatures=len(dataSet[0])-1 baseEntropy=calcShannonEnt(dataSet) bestInfoGain=0.0;bestFeature=-1 for i in range(numFeatures): featList=[example[i] for example in dataSet] uniqueVals=set(featList) 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
|
上面所述的为寻找最佳特征,流程图如下
递归构建决策树
递归函数停止的条件有两个,一:所有分类标签完全相同,则直接返回该类标签。二:使用完了所有特征,仍然不能将数据集划分成仅包含唯一类别的分组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| def createTree(dataSet,labels): classList=[example[-1] for example in dataSet] if classList.count(classList[0])==len(classList): return classList[0] if len(dataSet[0])==1: return majorityCnt(classList) bestFeat=chooseBestFeatureToSplit(dataSet) print bestFeat 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
|
这个递归有点绕需要仔细阅读,我表达能力有限也说不清楚。总之我们就是建立了一个决策树,最后一步就是使用这个决策树来完成分类啦。
分类函数也是一个递归函数,在存储带有特征的数据会面临一个问题:程序无法确定特征在数据集中的位置,例如前面例子的第一个用于划分数据集的特征是no surfacing属性,但是在实际数据集中该属性存储在哪个位置?第一个属性还是第二个属性?特征标签列表将帮助我们处理这个问题。使用index方法查找当前列表中第一个匹配firstStr变量的元素。然后代码递归遍历整棵树,比较testVec变量中的值与树节点的值,如果达到叶子节点,则返回当前节点的分类标签。
1 2 3 4 5 6 7 8 9 10 11
| def classify(inputTree,featLabels,testVec): firstStr=inputTree.keys()[0] secondDict=inputTree[firstStr] featIndex=featLabels.index(firstStr) for key in secondDict.keys(): if testVec[featIndex]==key: if type(secondDict[key]).__name__=='dict': classLabel=classify(secondDict[key],featLabels,testVec) else: classLabel=secondDict[key] return classLabel
|
Read More