优缺点和适用范围：
优点：
- 计算不那么费时
- 便于人类的理解
- 可处理非相关特征
缺点：
- 容易过拟合（关于如何尽量避免这种缺点带来的影响，本篇文章后期（剪枝）有介绍和相关代码）
适用范围：
- 数值型和非数值型数据均可
决策树的构型其实也是在模拟人的的思维过程：
一个人在获得一个结论的过程中总是需要多步判断。
但是在开始学习决策树之前应该先了解一些信息论的知识
假设x 为一种分类， p(x) 为这种分类在总的分类中出现的概率
1. 信息的概念：
信息是指人类社会中传播的一切内容。我们显然需要将信息进行量化度量，香农于1948年提出了信息熵（或称香农熵）的概念，用于量化信息
2. 信息熵：
信息的大小很大程度上依赖于信息的不确定性。这也是信息论一个基本的思想，即，一件小概率事件的发生要比一件大概率事件的发生提供更多的信息。信息的不确定性越大，其背后隐藏的信息更大。
3. 信息(或称“自信息”）的计算：
信息则被定义为I(x) = -log(p(x)) ，其中log以2为底。用于表示该标签单独的信息大小
4. 信息熵的计算：
而熵则被定义为 H = SUM(I(x) * p(x)) 即, 对于所有的标签，I(x) * p(x) 的加和。即每一种标签的出现的概率和这种标签下信息的乘积
5. 条件熵：
已知了一种分类条件，首先计算在该分类条件下分得的每一类的信息熵 * 这一类出现概率。最后将所有的进行加和得到了条件熵。理论上来讲，不管哪一种分类方式，条件熵都会比样本的信息熵要小，一是，公式中可以直接看出来。二是，如果将一个数据集进行了分类，显然数据在向着有序的方向在进行。但是，哪一种分类方式能使得当前数据的混乱程度最小呢？？因此引出了 信息增益的概念
6. 信息增益：
信息增益则被定义为 熵 - 条件熵
因此信息增益为正代表着数据向着有序的方向进行
而决策树所做的事情就是绘出一个能让熵下降最快的树，因此每次都要选择在当前情况下信息增益最大的分类方法
一. ID3决策树
有了以上的知识：我们可以开始对于ID3决策树怎么创建进行理解了
决策树的建立是一个递归的过程，事实上如果大家对于树这种结构有一些了解的话可以很快理解为什么这应该是一个递归的过程，因此不再赘述。
首先我们拿到了一个用于训练的样本集合，计算得到了该样本的信息熵。然后以每一个feature分别做分类，获得了每种分类的条件熵。从而计算得到每一种分类的信息增益，其中信息增益最大的那一种对应的就是数据混乱程度下降最快的方向，因此使用这一种的分类，这一分类即为这一点上的决策节点。然后基于这种分类将数据划分成多个子集合，分别再将这些子集合进行如上操作。从而建立决策树
计算熵的代码如下：
def calculate_entropy(data_set):
"""
used to calculate entropy
:param data_set: all of labels
:return: entropy
"""
dirc = {}
length = data_set[:, 0].size
label_pos = data_set[0].size -1
# label_list = label_set.tolist()
res = 0
for i in data_set[:, label_pos]:
if i[0, 0] in dirc.keys():
dirc[i[0, 0]] += 1
else:
dirc[i[0, 0]] = 1
for key in dirc.keys():
prob = float(dirc[key])/float(length)
res -= prob * math.log(prob, 2) # 第二个参数才是基数
return res
那么在一系列数据中想要知道怎样决策，熵下降最快，依靠如下代码计算哪一个特征最适合做数据划分：
思想比较简单，就是分别根据每一个特征进行数据集的划分，找到熵最小的，这个就是决策树的头节点
def split_data_set(data_set, condition):
"""
split the data set according to the condition
:param data_set: data set
:param condition: feature number
:return: the data sets after split
"""
dict = {}
length = data_set[:, 0].size
width = data_set[0, :].size
choice = []
for i in range(0, length):
if data_set[i, condition] not in dict.keys():
dict[data_set[i, condition]] = []
choice.append(data_set[i, condition])
dict[data_set[i, condition]].append([data_set[i, j] for j in range(0, width) if j is not condition])
return [np.mat(dict[key]) for key in dict.keys()], choice
def choose_best_conditional_entropy(data_set):
"""
actually it is choose the best condition which makes the increament is biggest
:param data_set: ..
:return: the condition which performs best
"""
width = data_set[0, :].size
length = data_set[:, 0].size
origin_entropy = calculate_entropy(data_set)
condition = -1
increament = 0
for i in range(0, width-1):
cond_entropy = 0
curr_data_sets, choice = split_data_set(data_set, i)
for data in curr_data_sets:
curr_prob = data[:, 0].size/length
cond_entropy += curr_prob * calculate_entropy(data)
if origin_entropy - cond_entropy > increament:
increament = origin_entropy - cond_entropy
condition = i
return condition
创建决策树：
def most_probably_result(data_set):
"""
when all of features have been considered ,still there are different classification
we just choose the most possible one
:param data_set: the data left
:return: the most possible result
"""
dict = {}
length = data_set[:, 0].size
res = ""
for i in range(0, length):
if data_set[i, 0] not in dict.keys():
dict[data_set[i, 0]] = 0
dict[data_set[i, 0]] += 1
for key in dict.keys():
if res == "" or dict[res] < dict[key]:
res = key
return res
def create_decision_tree(data_set, feature_name):
"""
create decision tree
:param data_set: data set
:param label_set: all of labels
:return: the dictionary of tree
"""
# 出口条件
width = data_set[0, :].size
length = data_set[:, 0].size
flag = 0
if width == 1:
return most_probably_result(data_set)
for i in range(0, length):
if data_set[i, width-1] != data_set[0, width-1]:
flag = 1
break
if flag == 0:
return data_set[0, width-1]
condition = choose_best_conditional_entropy(data_set)
splited_data_set, choice = split_data_set(data_set, condition)
dict = {feature_name[condition]: {}}
len_of_choice = len(choice)
sub_feature_name = [i for i in feature_name if i is not feature_name[condition]]
for i in range(0, len_of_choice):
dict[feature_name[condition]][choice[i]] = create_decision_tree(splited_data_set[i], sub_feature_name)
return dict
效果：
二. C4.5 决策树
实际上，ID3决策树还是存在一些问题的，比如，假设有n个样本，如果有一个特征（比如：编号，1，2，3.....n）对于每一个样本都不一样。在计算熵时候，显然，根据这个特征获得的条件熵最小，信息增益最大，所以编号就会成为这棵树的根结点，然后，这个结点会有n个分支，每一个分支指向一个叶子结点（即一个样本）
这显然不是我们想要的，因为这样的决策树，只适用于测试样本，无法适应新的样本。
为解决这个问题出现了 C4.5
C4.5 引出了一个新的概念：
增益率：
前面我们已经介绍了信息增益：这里信息增益用表示，其中D表示样本集合，a表示所选定的分类标准。
1. 分类标准（或者说 属性）的“固有值”（intrinsic value)定义为：
其中：
这种表示方式，表达的是B这个集合中元素的数量
表示的是a这一特征中的取v的样本的集合
如果定义:
则可以被写为：
有没有觉得上式有一些眼熟，没错，如果a不是分类标准而是样本的最终类别的话，IV(a)就是信息熵
信息熵用于描述数据的不确定性，因此，如果a这一特征下的的数据取值数目越多，IV(a)越大。举个例子：甜度这一属性：取值为甜、不甜的 与 取值为 甜、还好、不甜的 相比IV(a)更小
2. 增益率定义为：
这样的设定之后会发现，增益率同时考虑了信息增益和可取值数量的问题。但是由于公式的原因，实际上，增益率更加偏好可取值数目少的属性。因此C4.5 决策树并没有直接使用增益率，而是先挑出信息增益高于平均值的属性，然后在从其中挑出增益率最高的
修改代码：
def calc_shannon_ent(data_set, pos):
num_entries = len(data_set) # 获得数据量
label_counts = {} # 为标签出现次数计数，字典
for feat_vec in data_set:
current_label = feat_vec[pos] # 获得数据的标签，因为数据的最后一项是标签
if current_label not in label_counts.keys():
label_counts[current_label] = 0
label_counts[current_label] += 1 # 计数
shannon_ent = 0.0
for key in label_counts:
prob = float(label_counts[key])/num_entries # 计算每一项出现的概率
shannon_ent -= prob * log(prob, 2) # 计算香农熵
return shannon_ent
def calculate_gain_ratio(gain, data_set, feat_pos):
iv = calc_shannon_ent(data_set, feat_pos)
return gain/float(iv)
def choose_best_feature_to_split(data_set):
num_features = len(data_set[0]) - 1
base_entropy = calc_shannon_ent(data_set, -1)
best_gain_ratio = 0.0
best_feature = -1
entropy_list = [0] * num_features
for i in range(num_features):
feat_list = [example[i] for example in data_set]
unique_vals = set(feat_list)
new_entropy = 0.0
for value in unique_vals:
sub_data_set = split_data_set(data_set, i, value)
prob = len(sub_data_set)/float(len(data_set))
new_entropy += prob * calc_shannon_ent(sub_data_set, -1)
info_gain = base_entropy - new_entropy
entropy_list[i] = info_gain
average_info_gain = sum(entropy_list)/float(num_features)
for i in range(num_features):
if entropy_list[i] > average_info_gain:
new_gain_ratio = calculate_gain_ratio(entropy_list[i], data_set, i)
if new_gain_ratio > best_gain_ratio:
best_gain_ratio = new_gain_ratio
best_feature = i
return best_feature
对比ID3和C4.5：
数据：
1,young,myope,no,reduced,no lenses
2,young,myope,no,normal,soft
3,young,myope,yes,reduced,no lenses
4,young,myope,yes,normal,hard
5,young,hyper,no,reduced,no lenses
6,young,hyper,no,normal,soft
7,young,hyper,yes,reduced,no lenses
8,young,hyper,yes,normal,hard
9,pre,myope,no,reduced,no lenses
10,pre,myope,no,normal,soft
11,pre,myope,yes,reduced,no lenses
12,pre,myope,yes,normal,hard
13,pre,hyper,no,reduced,no lenses
14,pre,hyper,no,normal,soft
15,pre,hyper,yes,reduced,no lenses
16,pre,hyper,yes,normal,no lenses
17,presbyopic,myope,no,reduced,no lenses
18,presbyopic,myope,no,normal,no lenses
19,presbyopic,myope,yes,reduced,no lenses
20,presbyopic,myope,yes,normal,hard
21,presbyopic,hyper,no,reduced,no lenses
22,presbyopic,hyper,no,normal,soft
23,presbyopic,hyper,yes,reduced,no lenses
24,presbyopic,hyper,yes,normal,no lenses
ID3:
C4.5:
从以上可以清晰的看见C4.5使用增益率的效果
三. CART决策树
以上两种决策树都是通过计算熵来表现数据的混乱程度
而这里即将介绍的是利用“基尼指数”（Gini index）来选择划分属性
基尼值：随机抽取两个样本，其标识不一样的概率
基尼值越小，代表，随机抽取两个样本，其标识一样的概率越大。因此，数据纯度越高
基尼指数：对应于条件熵，表现在某种分类下的对应的尼基值
相比于以上两种决策树，唯一改变的就是计算方式
因此不再对于代码赘述
四.剪枝(pruning)处理
剪枝处理分为了：预剪枝和后剪枝两种处理方式
- 预剪枝：在建立树之前剪枝
- 后剪枝：在建立树之后剪枝
怎么剪枝？？
剪枝的思想很简单，只要判断如果这个结点作为了子树根结点相比于直接将这个结点处理成叶子结点的准确率是否有提升：
如果有提升：这个结点将会成为子树根结点
如果没有提升：这个结点将会成为该分支下数据集的出现最多的类别
预剪枝：
在即将在这个点上确定结点之前，将这个点是根结点和这个点是叶子结点两种情况分别建立出来。然后分别用测试集判断准确率。比较两种准确率，哪种的准确率高，用哪种。
后剪枝：
在已经建立好的树中，倒着遍历每一个根结点，判断这个结点适合是根结点还是叶子结点，对树做修改
虽然说决策树大多数场合适用于离散值情况，但是并不代表不能应用于连续值情况，一般来说，连续值情况，决策树的处理方式是利用二分将连续值分成两类，进行决策，此类不再赘述
