Keep and carry on.

前言

如果说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

递归构建决策树

递归函数停止的条件有两个,一:所有分类标签完全相同,则直接返回该类标签。二:使用完了所有特征,仍然不能将数据集划分成仅包含唯一类别的分组

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) #由于不知道决策树第一个特征在label中为第几个,所以需要index定位特征的位置
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
⬆︎TOP