Technology-机器学习-决策树算法

本文介绍决策树算法(Division Tree)。

决策树算法类似于用流程图进行分类判断。

构造

优点:计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据;
缺点:可能会产生过度匹配(overfitting)问题;
使用数据类型:数值型和标称型。

流程

收集数据:可以使用任何方法;
准备数据:树构造算法只适用于标称型数据，因此数值型数据必须离散化;
分析数据:可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期;
训练算法:构造树的数据结构;
测试算法:使用经验树计算错误率;
使用算法:此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

信息增益

信息增益(Infomation Gain):在划分数据集之前之后信息发生的变化。

熵(Entropy)/香农熵:集合信息的度量方式。

如果数据集可能划分在多个分类中，则符号$x_i$的信息定义为:

$$
l(x_i) = -log_2p(x_i)
$$

其中，$p(x_i)$是选择该分类的概率。

将所有类别，每个类别里面的所有可能值包含的信息期望值叠加，就是熵的计算方式：

$$H = -\sum_{i=1}^np(x_i)log_2p(x_i)$$

例如，数据集:

1	[[1, 'yes'], [0, 'yes'], [1, 'no'], [0, 'no'], [0, 'no']]

其中，熵的计算为:

1
2
3

p('yes') = 2 / 5 //yes的概率
p('no') = 3/ 5   //no的概率
H = -(p('yes') * log(2, p('yes')) + p('no') * log(2, p('no')))

划分数据集

在选择一个数据集的特征的时候，可以通过计算每个特征值划分数据集的信息增益(通过熵衡量)，越高，则代表该特征值的划分效果越好。

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
	
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, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

带入上述代码，结果为：

意外着，通过第一列的特征去进行分类，效果是最好的。

递归

得到原始数据集后，基于最好的特征值分类，第一次划分后，可以进行递归，每次都在剩下的特征值中取最好的进行分类，直到递归结束。

递归结束的条件是：

程序遍历完所有划分数据集的属性;
每个分支下的所有实例都具有相同的分类。

如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时可以采用多数表决的方法处理。

def majorityCnt(classList):
	classCount = {}
	for vote in classList:
		if vote not in classCount.keys() : 
			classCount[vote] = 0
		classCount[vote] += 1
	sortedClassCount = sorted(classCount.iteriems(), key=operator.itemgetter(1), reverse=True)
	return sortedClassCount[0][0]

递归构造树:

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)
	bestFeatLabel = lables[bestFeat]
	myTree = {bestFeatLabe:{}}
	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

结果:

1	{'no surfacing':{0:'no', 1:{'flippers':{0:'no', 1:'yes'}}}}

测试

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

结果:

labels:{'no surfacing', 'flippers'}
myTree:{'no surfacing':{0:'no', 1:{'flippers':{0:'no', 1:'yes'}}}}
classify(myTree, labels, {1, 0})
'no'
classify(myTree, labels, {1, 1})
'yes'

存储

构造决策树是很耗时的任务，可以将已经构造好的树，序列化到硬盘中，要用时，在反序列化到内存中。

优化

对于某些情景，可能匹配选项太多了，会导致过度匹配(overfitting)问题，例如下图，对于这种情况，可以对其进行裁剪，去掉一些不必要的叶子节点。如果叶子节点只能增加少许信息，则可以删除该节点，将它并入到其他叶子节点中。