决策树

发表于 | 分类于

决策树

决策树以数据特征做划分，利用特征鲜明且完备的方式将数据划入不同的分类。是一种数值离散的聚类算法。 其中最主要的两个知识点是信息熵和信息增益。决策树根据所给数据特征的信息增益决定划分方式。

特征选择

选取对训练数据具有分类功能的特征 信息熵 在信息论和概率统计中对随记变量不确定性的度量 设X是一个取有限个值的离散随机变量，其概率分布：

$$
P(X = x_i)=p_i, i = 1,2,···n
$$

则X的熵定义为：$H(X) =- \sum_{i=1}^{n}p_ilog(p_i)$log以2为底单位为比特（bit） 上式表明熵越大X的不确定度越大 若有二维随机变量(X,Y），其联合概率为：
$$
P(X = x_i,Y = yj) = p{ij} ， i = 1,2,3······n,j= 1,2,3······m
$$
条件熵H(Y|X)
表示在已知随机变量X的条件下随机变量Y的不确定度。
$$
H(Y|X) = \sum_{i = 1}^{n}p_iH(Y|X=x_i)
$$

$$
p_i = P(X = x_i),i = 1,2,3······n
$$
在得到一批数据后可以通过数据估计，所得熵与条件熵称经验熵和经验条件熵
信息增益
表示在得知特征X的条件下，而使得Y的信息不确定性减少的程度。 特征 X对训练数据集Y的信息增益g(Y,X)，定义为集合Y的经验熵H(Y)与特征 X给定条件下Y的经验条件熵H(Y|X)之差
$$
g(Y,X) = H(Y) - H(Y|X)
$$
因此对给定数据集和特征，信息增益越大的特征具有更强的分类能力 所以特征选择的方法：对数据集，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征，并迭代进行

计算信息熵（香农熵）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 计算信息熵 
def CalcShannonEnt(dataSet) : # 计算数据集的输入个数 
numEntries=len(dataSet) # []列表,{}元字典,()元组 
labelCounts= {} # 创建存储标签的元字典 
# 对数据集dataSet中的每一行featVec进行循环遍历 
for featVec in dataSet : 
	currentLabels=featVec[-1] # currentLabels为featVec的最后一个元素 
if currentLabels not in labelCounts.keys() : # 如果标签currentLabels不在元字典对应的key中
	labelCounts[currentLabels]=0 # 将标签currentLabels放到字典中作为key，并将值赋为0
	labelCounts[currentLabels]+=1 # 将currentLabels对应的值加1 
shannonEnt=0.0 # 定义香农熵shannonEnt 
for key in labelCounts : # 遍历元字典labelCounts中的key，即标签		   
	prob=float(labelCounts[key]) / numEntries # 计算每一个标签出现的频率，即概率
	shannonEnt -=prob * log(prob, 2)# 根据信息熵公式计算每个标签信息熵并累加到shannonEnt上
return shannonEnt# 返回求得的整个标签对应的信息熵

计算条件熵选择最好的分类特征

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def chooseBestFeatureToSplit(dataSet): # 选择使分割后信息增益最大的特征，即对应的列 
	numFeatures=len(dataSet[0]) - 1 # 获取特征的数目，从0开始，dataSet[0]是一条数据 
	baseEntropy=CalcShannonEnt(dataSet) # 计算数据集当前的信息熵 
	bestInfoGain=0.0 # 定义最大的信息增益 
	bestFeature=-1 # 定义分割后信息增益最大的特征 
	for i in range(numFeatures):# 遍历特征，即所有的列，计算每一列分割后的信息增益，找出信息增益最大的列 
		featList=[example[i] for example in dataSet] # 取出第i列特征赋给featList 
		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 # 分割的最好特征列赋为i 
	return bestFeature # 返回分割后信息增益最大的特征列
Donate comment here