机器学习实战之决策树
简介：
决策树是一类常见的机器学习方法，以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新数据进行分类，比如通过一组数据通过模型训练得到以下的决策树：
理论：
决策树学习的关键是如何选择最优划分属性，一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。
1、信息熵
熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事
务可能划分在多个分类之中，则符号
其中
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：
其中n是分类的数目,H的值越小，则数据纯度越高。
2、信息增益
假定当前样本集D按照属性a来分类，a的属性取值有
信息增益越大，意味着使用属性a来划分所获得的“纯度提升”越大，决策树中的ID3学习算法就是使用信息增益来选择划分属性的。
3、信息增益率
实际上，信息增益准则对可取值数目较多(V较大)的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5决策树算法使用增益率来选择划分属性，增益率定义为：
其中
称为属性a的固有值。属性a的可能取值数目越多，则IV(a)值通常会越大。但是增益率准则对可取值数目较少的属性有所偏好，因此C4.5不是直接选择增益率最大的候选划分属性，而是使用启发式：先从候选划分属性中找到信息增益高于平均水平的属性，再从中选择增益率最高的。
4、基尼指数
CART决策树使用“基尼指数”来选择划分属性，数据集D的纯度可用基尼值来度量：
Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，Gini(D)越小，则数据集D的纯度越高。
属性a的基尼指数定义为
我们选择属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。
实践：
这里我们采用信息增益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’}}}}