算法001.机器学习其它资料机器学习实战

决策树

优点

计算复杂度不高， 输出结果易于理解。对中间值的缺失不敏感，可以处理不相关特征数据。

缺点

可能会产生过度匹配问题

适合数据类型

数值型和标称型

第一个问题：当前数据集中哪个特征在划分数据分类时起决定性作用。 为了找到决定性的特征，划分出最好的结果，我们必须评估每一个特征。

决策树的流程

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

一些决策树算法采用二分法划分数据，这里依据某个属性划分数据将会产生4个可能的值，我们把数据划分为四块，并创建四个不同的分支。 这里使用ID3算法划分数据集。

每次划分数据集时我们只选取一个特征属性，如果训练集中存在20个特征，第一次我们选择哪个特征作为划分的参考属性呢？？

比如：特征有，不浮出水面是否可以生存，是否有脚蹼。可以将这些动物分为两类：鱼类和非鱼类。现在想决定依据第一个特征还是第二个特征划分数据呢。 我们比如采用量化的方法判断如何划分数据

信息增益

划分数据集的原则：将无序的数据变得更加有序。可以由很多种方法划分数据集，各有各的优缺点。其中一种是使用信息论度量信息。信息论是量化处理信息的分支科学。可以在划分数据集前后使用信息论量化度量信息的内容。

在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择

如何计算信息增益

集合信息的度量方式称为香农熵或者简称熵。这个名字来源于信息论之父克劳德·香农。

熵

定义为信息的期望值。

信息：如果待分类的事物可能划分在多个分类之中，则符号xi的信息定义为l(xi)=-log2p(xi). 其中p(xi)是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式。H = -Ep(xi)log2p(xi).其中n为分类的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 计算给定数据集的香农熵
from math import log2p
def calcShannonEnt(dataSet):
	numEntries = 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]) / numEntries
		# 以2为底求对数
		shannonEnt -= prob * log(prob,2)
	return shannonEnt

以上，首先计算数据集中实例的总数，我们也可以在需要时再计算这个值，但是由于代码中多次用到这个值，为了提高代码效率，我们显式地声明一个变量保存实例总数。然后，创建一个数据字段，它的键值是最后一列的数值。

最后，使用所有类标签的发生频率计算类别出现的概率，我们将用这个概率计算香农熵，统计所有类标签发生的次数。

下面看看如何使用熵划分数据集。

1
2
3
4
5
6
7
8
9
# trees.py
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
1
2
myDat, labels = trees.createDataSet()
trees.calcShannonEnt(myDat)

熵越高，则混合的数据也越多，我们可以在数据集中添加更多的分类，观察熵是如何变化的。

1
2
3
4
# 增加一个类别
myDat[0][-1] = 'maybe'
myDat
trees.calcShannonEnt(myDat)

得到熵之后，我们就可以按照获取最大信息增益的方法划分数据集，下面具体介绍：如何划分数据集以及如何度量信息增益。

另一度量集合无序程度的方法是基尼不纯度，简单地说就是从一个数据集中随机选取子项，度量其被错误分类到其他分组里的概率。

划分数据集

上面介绍了如何度量数据集的无序程度，分类算法除了需要测量信息熵，还需要划分数据集。度量划分数据集的熵，以便判断当前是否正确的划分了数据集。

我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。

想象一个分部在二维空间的数据散点图，需要在数据之间画条线，将它们分为两部分，我们应该按照x轴还是y轴划线呢？

1
2
3
4
5
6
7
8
9
def splitDataSet(dataSet, axis, value):
	# 创建新的list对象
	retDataSet = []
	for featVec in dataSet:
		if featVec[axis] == value:
			reducedFeatVec = featVec[:axis]
			reducedFeatVec.extend(featVec[axis +1:])
			retDataSet.append(reducedFeatVec)
	return retDataSet

以上输入三个参数：待划分的数据集，划分数据集的特征，需要返回的特征的值。