机器学习常见算法模型练习——决策树

小鸡
阅读576 喜欢3 算法 更新2019-3-21

决策树

以下概念介绍转自——参考文章:决策树算法介绍及应用
决策树是附加概率结果的一个树状的决策图,是直观的运用统计概率分析的图法。机器学习中决策树是一个预测模型,它表示对象属性和对象值之间的一种映射,树中的每一个节点表示对象属性的判断条件,其分支表示符合节点条件的对象。树的叶子节点表示对象所属的预测结果。

决策树案例

上图是一棵结构简单的决策树,用于预测贷款用户是否具有偿还贷款的能力。贷款用户主要具备三个属性:是否拥有房产,是否结婚,平均月收入。每一个内部节点都表示一个属性条件判断,叶子节点表示贷款用户是否具有偿还能力。例如:用户甲没有房产,没有结婚,月收入 5K。通过决策树的根节点判断,用户甲符合右边分支 (拥有房产为“否”);再判断是否结婚,用户甲符合左边分支 (是否结婚为否);然后判断月收入是否大于 4k,用户甲符合左边分支 (月收入大于 4K),该用户落在“可以偿还”的叶子节点上。所以预测用户甲具备偿还贷款能力。

决策树建立

本文上一节已经讨论如何用一棵决策树进行分类。本节将通过特征选择、剪枝,介绍如何根据已有的样本数据建立一棵决策树。

首先介绍下特征选择。选择一个合适的特征作为判断节点,可以快速的分类,减少决策树的深度。决策树的目标就是把数据集按对应的类标签进行分类。最理想的情况是,通过特征的选择能把不同类别的数据集贴上对应类标签。特征选择的目标使得分类后的数据集比较纯。如何衡量一个数据集纯度,这里就需要引入数据纯度函数。下面将介绍两种表示数据纯度的函数。

信息增益

信息熵表示的是不确定度。均匀分布时,不确定度最大,此时熵就最大。当选择某个特征对数据集进行分类时,分类后的数据集信息熵会比分类前的小,其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。

假设在样本数据集 D 中,混有 c 种类别的数据。构建决策树时,根据给定的样本数据集选择某个特征值作为树的节点。在数据集中,可以计算出该数据中的信息熵:

其中 D 表示训练数据集,c 表示数据类别数,Pi 表示类别 i 样本数量占所有样本的比例。

对应数据集 D,选择特征 A 作为决策树判断节点时,在特征 A 作用后的信息熵的为 Info(D),计算如下:

其中 k 表示样本 D 被分为 k 个部分。

信息增益表示数据集 D 在特征 A 的作用后,其信息熵减少的值。公式如下:

对于决策树节点最合适的特征选择,就是 Gain(A) 值最大的特征。

算法

找bug太累了!!!

计算信息熵

def calc_san(data): #计算信息熵
count = {}
index = {}
i = - 1
for a in data:
charge = a[-1]
if str(charge) in index:
temp = index[str(charge)]
count[temp] = count[temp] + 1
else:
i += 1
index[str(charge)] = i
count[i] = 1
total = 0
info = 0.0
for t in range(len(count)):
total = total + count[t]

for t in range(len(count)):
r = count[t] / float(total)
info = info - r * math.log(r,2)

return info

划分数据集并计算划分后的信息熵

def splitData(data, proper): #划分数据集并计算划分后的信息熵
proper_key = []
proper_item = {}
cut = 0
for d in data:
value = str(d[proper])
if value in proper_item:
proper_item[value].append(d)
else:
proper_item[value] = []
proper_key.append(value)
info = 0
for pk in proper_key:
min_data = proper_item[pk]
r = len(min_data) / float(len(data))
info = info + r * calc_san(min_data)
return {info:info,key:proper,value:proper_key,data:proper_item}

选择一个最好的属性

def chooseBestProper(data,com_key): # 根据信息增益,选择一个最好的属性
cur_info = calc_san(data[1])
cur_data = {}
gain = 0
for p in range(len(data[0])-1):
if data[0][p] in com_key:
continue
p_data = splitData(data[1],p)
if cur_info - p_data[info] > gain:
gain = cur_info - p_data[info]
cur_data = p_data

return cur_data

数据集

编号,色泽,根蒂,敲声,纹理,脐部,触感,好瓜
1,青绿,蜷缩,浊响,清晰,凹陷,硬滑,是
2,乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,是
3,乌黑,蜷缩,浊响,清晰,凹陷,硬滑,是
4,青绿,蜷缩,沉闷,清晰,凹陷,硬滑,是
5,浅白,蜷缩,浊响,清晰,凹陷,硬滑,是
6,青绿,稍蜷,浊响,清晰,稍凹,软粘,是
7,乌黑,稍蜷,浊响,稍糊,稍凹,软粘,是
8,乌黑,稍蜷,浊响,清晰,稍凹,硬滑,是
9,乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,否
10,青绿,硬挺,清脆,清晰,平坦,软粘,否
11,浅白,硬挺,清脆,模糊,平坦,硬滑,否
12,浅白,蜷缩,浊响,模糊,平坦,软粘,否
13,青绿,稍蜷,浊响,稍糊,凹陷,硬滑,否
14,浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,否
15,乌黑,稍蜷,浊响,清晰,稍凹,软粘,否
16,浅白,蜷缩,浊响,模糊,平坦,硬滑,否
17,青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,否

结果如下

{‘纹理’: {‘清晰’: {‘根蒂’: {‘稍蜷’: {‘触感’: {‘硬滑’: ‘是’, ‘软粘’: {‘色泽’: {‘青绿’: ‘是’, ‘乌黑’: ‘否’}}}}, ‘硬挺’: ‘否’, ‘蜷缩’: ‘是’}}, ‘模糊
’: ‘否’, ‘稍糊’: {‘敲声’: {‘沉闷’: ‘否’, ‘浊响’: {‘脐部’: {‘凹陷’: ‘否’, ‘稍凹’: ‘是’}}}}}}

源码地址:https://github.com/flymysql/Fly_Mac_learing