决策树

简单解释: 为信息的期望值,计算公式如下。

$$ info(D) = -\sum_{i=1}^m p_i log_2(p_i) $$

信息增益 是指在划分数据集之前之后信息发生的变化。对信息按属性A划分后取得的熵。
$$ info_A(D) = \sum_{j=1}^v \frac{|D_j|}{|D|}info(D_j) $$

计算两者之间的变化就是信息增益。
$$ gain(A) = info(D) - info_A(D) $$

如下算法计算最大信息增益。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#! /data/sever/python/bin/python
# -*- coding:utf-8 -*-
"""
决策树算法
"""
from __future__ import division
import math
import operator
from collections import Counter

__author__ = 'xyz'


def calc_shannon_ent(data_set):
"""
计算香农熵
:param data_set:
:return:
"""
data_length = len(data_set)
label_counts = Counter([val[-1] for val in data_set])
pilog2pi = [val / data_length * math.log(val / data_length, 2) for val in label_counts.itervalues()]
return - reduce(
operator.add,
pilog2pi
) if pilog2pi else 0


def split_data_set(data_set, axis, value):
"""
分割数据集,筛选指定特征下的数据值的集合
:param data_set: 数据集合
:param axis: 第几列
:param value: 筛选的值
:return: 除去axis列的,并且axis列的值为value的的数据集合
"""
return [[v for i, v in enumerate(val) if i != axis] for val in data_set if val[axis] == value]


def choose_best_feature_to_split(data_set):
"""
选择最好的数据集划分方式
:param data_set: 数据集
:return: 划分方式最好是第几项
"""
base_ent = calc_shannon_ent(data_set)
# 定义最好的信息增益,信息增益最好的那项
best_info_gain, best_feature = 0.0, -1
for i in range(len(data_set[0]) - 1):
unique_value = set(data_set[i])
child_ent = 0.0
for val in unique_value:
child_data_set = split_data_set(data_set, i, val)
child_ent += (len(data_set) - 1) / len(data_set) * calc_shannon_ent(child_data_set)
# 信息增益
info_gain = base_ent - child_ent
if info_gain > best_info_gain:
best_info_gain = info_gain
best_feature = i
return best_feature


def majority_ent(class_list):
"""
取出出现次数最多的标签
:param class_list:
:return:
"""
class_count = Counter(class_list)
sorted_class_count = sorted(class_count.items(), key=lambda x, y: cmp(x[1], y[1]), reverse=True)
return sorted_class_count[0][0]


def create_tree(data_set, labels):
"""
创建树
:param data_set: 数据集
:param labels: 标签集合
:return: 决策树
"""
class_list = [val[-1] for val in data_set]
if class_list.count(class_list[0]) == len(class_list):
return class_list[0]
if len(data_set[0]) == 1:
return majority_ent(class_list)
best_feat = choose_best_feature_to_split(data_set)
best_feat_label = labels[best_feat]
my_tree = {best_feat_label: {}}
del labels[best_feat]
feat_values = [val[best_feat] for val in data_set]
unique_vals = set(feat_values)
for value in unique_vals:
sub_labels = labels[:]
my_tree[best_feat_label][value] = create_tree(split_data_set(data_set, best_feat, value), sub_labels)
return my_tree

if __name__ == "__main__":
data_set = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
# 计算熵
print calc_shannon_ent(data_set)
# 分割数据集
print split_data_set(data_set, 0, 1)
# 获取最大信息增益项
print choose_best_feature_to_split(data_set)
# 生成决策树
print create_tree(data_set, ['no surfacing', 'flippers'])

ID3算法

ID3算法就是在每次需要分裂时,计算每个属性的增益率,然后选择增益率最大的属性进行分裂。

C4.5算法

定义分裂信息

$$ splitInfo_A(D) = - \sum_{j=1}^v \frac{|D_j|}{|D|} log_2(\frac{|D_j|}{|D|}) $$

定义增益率

$$ gain\_ratio(A) = \frac{gain(A)}{split\_info(A)} $$

C4.5选择具有最大增益率的属性作为分裂属性。
http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
决策树到底是干嘛用的,怎么去灵活运用决策树?