机器学习实战之决策树

https://mp.weixin.qq.com/s/1-gGXqtigu4Bt9vsUhaB8A

一、简介

决策树是一类常见的机器学习方法，以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新数据进行分类，比如通过一组数据通过模型训练得到以下的决策树：

二、理论

决策树学习的关键是如何选择最优划分属性，一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

1、信息熵

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事
务可能划分在多个分类之中，则符号的信息定义为

其中是当前样本集合D中第i类样本所占的比例。

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：

其中n是分类的数目,H的值越小，则数据纯度越高。

2、信息增益

假定当前样本集D按照属性a来分类，a的属性取值有共V种情形，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为的样本，该样本记为.并计算出的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重，即样本数越多的分支结点对信息熵的影响越大，于是可计算出用属性a对样本集D进行划分所获得的“信息增益”。

信息增益越大，意味着使用属性a来划分所获得的“纯度提升”越大，决策树中的ID3学习算法就是使用信息增益来选择划分属性的。

3、信息增益率

实际上，信息增益准则对可取值数目较多(V较大)的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5决策树算法使用增益率来选择划分属性，增益率定义为：

其中

称为属性a的固有值。属性a的可能取值数目越多，则IV(a)值通常会越大。但是增益率准则对可取值数目较少的属性有所偏好，因此C4.5不是直接选择增益率最大的候选划分属性，而是使用启发式：先从候选划分属性中找到信息增益高于平均水平的属性，再从中选择增益率最高的。

4、基尼指数

CART决策树使用“基尼指数”来选择划分属性，数据集D的纯度可用基尼值来度量：

Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，Gini(D)越小，则数据集D的纯度越高。

属性a的基尼指数定义为

我们选择属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

三、Python实践

这里我们采用信息增益ID3学习算法来选择划分属性，首先是计算给定数据集的信息熵，首先，计算数据集中实例的总数。然后，创建一个数据字典，它的键值是最后一列的数值。如果当前键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。最后，使用所有类标签的发生频率计算类别出现的概率。我们将用这个概率计算香农熵，统计所有类标签发生的次数。

from math import log
import numpy as np

def cal_entropy(data):

num_data = data.shape[0]

count_dic = {}

sum_entropy = 0.0

for value in data[:, -1]:
if value not in count_dic:

count_dic[value] = 0

count_dic[value] += 1

for key in count_dic.keys():

prob = float(count_dic[key]) / num_data

sum_entropy -= prob*log(prob, 2)
return sum_entropy

以上我们知道怎么计算信息熵，接下来是划分数据集，度量划分数据集的熵，以便判断当前是否正确地划分了数据集。我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。

def sub_data(data, axis, value):

subgroup = []

ret_data = []

index = 0

for feat_vec in data:
if feat_vec[axis] == value:

ret_data.extend(feat_vec[:axis])

ret_data.extend(feat_vec[axis+1:])

subgroup.append(ret_data)
# extend和append的功能差不多，但是区别它们的参数为list的实现结果

index += 1

ret_data = []

subgroup = np.array(subgroup)
return subgroup

接下来我们将遍历整个数据集，循环计算信息熵和sub_data()函数，根据信息增益最大的值找到对应最好的特征划分方式。

def split_feat(data):

num_feat = data.shape[1]-1

base_entropy = cal_entropy(data)

best_feat = -1

best_info = 0.0

for i in range(num_feat):

feat_value = set([example[i] for example in data])

new_entropy = 0.0

for value in feat_value:

subgroup = sub_data(data, i, value)

prob = subgroup.shape[0] / float(data.shape[0])

new_entropy += prob * cal_entropy(subgroup)

info_gain = base_entropy - new_entropy
if best_info < info_gain:

best_info = info_gain

best_feat = i
return best_feat

最后递归构建决策树，得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。
递归结束的条件是：情况一是程序遍历完所有划分数据集的属性，通过少数服从多数的原则，确定该分支的类别，构建函数maj_cnt()来找到该分支出现次数最多的类别。情况二是每个分支下的所有实例都具有相同的分类。

def maj_cnt(class_list):

   class_count = {}
   for vote in class_list:
   if vote not in class_count.keys():

class_count[vote] = 0

class_count[vote] += 1

max_class = max(zip(class_count.keys(), class_count.values()))
return max_class[0]

def create_tree(data, feat_name):

# feat_name为特征名

   class_list = [example[-1] for example in data]
   if class_list.count(class_list[0]) == len(class_list):
   return class_list[0]
   if data.shape[1] == 1:
   return maj_cnt(class_list)

best_feature = split_feat(data)
#if best_feature == -1:

feat_label = feat_name[best_feature]

my_tree = {feat_label: {}}
del(feat_name[best_feature])

feat_values = [example[best_feature] for example in data]

uni_values = set(feat_values)
for value in uni_values:

sub_name = feat_name[:]

my_tree[feat_label][value] = create_tree(sub_data(data, best_feature, value), sub_name)
return my_tree

最后采用《机器学习实战》第三章的案例数据来测试。

if __name__ == "__main__":

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

feat_names = ['no surfacing', 'flippers']

tree = create_tree(np.array(data), feat_names)

print(tree)

构建的决策树为：

{‘no surfacing’:{0:’no’,1:{‘flippers’:{0:’no’,1:’yes’}}}}

参考：《机器学习实战》

ITPub博客

机器学习实战之决策树

最新文章