淘先锋技术网

首页 1 2 3 4 5 6 7

决策树

本文根据《机器学习》与《机器学习实战》自学,写出以下内容。(仅供学习而用,非商业用途。)

一、基本流程

一颗决策树包含一个根节点、若干个内部节点与若干个叶节点,叶节点对应于决策结果,其他节点对应于一个属性的测试;根节点包含样本全集,从根节点到每个叶节点的路径对应了一个判定测试序列,决策树学习的目的就是为了产生一颗泛化能力强的决策树,其基本流程如下:
输入:训练集 D={(x1,y1),(x2,y2),…,(xm,ym)}
属性集(特征集)A={a1,a2,…,ad}
过程:TreeGenerate(D,A)
1.生成节点node
2.if D中样本全属于同一类别C then
3. 将node标记为C类叶节点;return
4.end if
5.if A为空集 or D中样本在A上取值相同 then
6. 将node标记为叶节点,其类别标记为D中样本数最多的类;return
7.end if
在这里插入图片描述
决策树的生成是一个递归过程,有三种情形导致递归返回:
1.当前节点包含的样本全属于同一类别,无需划分
2.当前属性集为空,或所有样本在所有属性上取值相同,(把当前节点标记为叶节点)。
3.当前节点包含的样本集合为空(同样把当前节点标记为叶节嗲按,但将其类别设定为其父节点所含样本最多的类别)

二、划分的一般原则

信息增益Gain(A)越大,使用属性A划分所获得的“纯度”提升越大
2.1
信息熵的公式:
在这里插入图片描述
以下代码为计算信息信息熵的公式。

import operator
from math import log
def Ent(dataSet):
	ent_num = len(dataSet)
	label_counts = {}
	for feat_Vec in dataSet:
		current_label = feat_Vec[-1]
		if current_label not in label_counts.keys():
			label_counts[current_label] = 0
			label_counts[current_label] +=1
		ent_1 =0.0
		for key in label_counts:
			prob = float(label_counts[key])/ent_num
			ent_1 -=prob*log(prob,2)

计算完信息熵之后,按照最大信息增益的方法划分数据集。

def split_dataset(dataSet,axis,value):#dataset待划分数据集,特征(属性),特征的返回值
	re_dataSet = []#创建新的列表对象
	for feat_Vec in dataSet:    #将符合特征的数据抽取出来
		if feat_Vec[axis] ==value:
			del_feat_vec = feat_Vec[:axis]
			del_feat_vec.extend(feat_Vec[axis + 1:])
			re_dataSet.append(del_feat_vec)
		return re_dataSet

循环上述代码,找出最好的特征划分方式。以下为选择最好的数据集划分方式代码:

def best_feature_split(dataSet):
	feature_num = len(dataSet[0])-1
	base_ent = Ent(dataSet)
	best_Gain = 0.0
	best_feature =-1
	for i in range(feature_num):
		feat_list = [example[i] for example in dataSet]
		unique_Vals = set(feat_list)
		new_ent = 0.0
		for value in unique_Vals:
			sub_dataset = split_dataset(dataSet, i, value)
			prob = len(sub_dataset) / float(len(dataSet)) 
			new_ent += prob * Ent(sub_dataset)  
			info_Gain = base_ent - new_ent  #信息增益
			if info_Gain > best_Gain:
				best_Gain = info_Gain
				best_feature = i
		return best_feature

如果数据集已经处理了所有属性,但是类标签依然不是唯一的,此时我们需要决定如何定义该叶子结点,一般会采用多数表决的方法确定该叶子结点的分类。代码如下:

def majorityCnt(classList):
    classCount = {}  # 创建唯一值的数据字典
    for vote in classList:
        if vote not in classCount.keys():  # 如果该标签不再字典中,就扩展字典,并将value值设为0
        	classCount[vote] = 0
        classCount[vote] += 1  # 否则就+1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)  # 利用operator操作键值排序字典,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 = best_feature_split(dataSet)  # 找出最佳数据集划分的特征属性的索引
    bestFeatLabel = labels[bestFeat]  # 获取最佳索引对应的值
    myTree = {bestFeatLabel: {}}
    del (labels[bestFeat])  # 删除最佳索引的列
    featValues = [example[bestFeat] for example in dataSet]
    unique_Vals = set(featValues)  # 使用set集合去除重复的值,得到列表包含的所有属性值
    for value in unique_Vals:  # 遍历所有最佳划分的分类标签
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(split_dataset(dataSet, bestFeat, value), subLabels)  # 递归调用
    return myTree

到此,构建决策树的所有过程(代码)已经比较完整了。后面会进行具体的项目实战,也就是决策树的用法和可视化,敬请期待。发现代码有误的请及时指正。∩∪∩!!!