机器学习--决策树(ID3)算法及案例
1基本原理
决策树是一个预测模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，每个分支路径代表某个可能的属性值，每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。一般情况下，决策树由决策结点、分支路径和叶结点组成。在选择哪个属性作为结点的时候，采用信息论原理，计算信息增益，获得最大信息增益的属性就是最好的选择。信息增益是指原有数据集的熵减去按某个属性分类后数据集的熵所得的差值。然后采用递归的原则处理数据集，并得到了我们需要的决策树。
2算法流程
检测数据集中的每个子项是否属于同一分类：
If 是，则返回类别标签；
Else
计算信息增益，寻找划分数据集的最好特征
划分数据数据集
创建分支节点（叶结点或决策结点）
for 每个划分的子集
递归调用，并增加返回结果到分支节点中
return 分支结点
算法的基本思想可以概括为：
1）树以代表训练样本的根结点开始。
2）如果样本都在同一个类．则该结点成为树叶，并记录该类。
3）否则，算法选择最有分类能力的属性作为决策树的当前结点．
4 ）根据当前决策结点属性取值的不同，将训练样本根据该属性的值分为若干子集，每个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到的一个子集，重复进行先前步骤，递归形成每个划分样本上的决策树。一旦一个属性只出现在一个结点上，就不必在该结点的任何后代考虑它，直接标记类别。
5）递归划分步骤仅当下列条件之一成立时停止：
①给定结点的所有样本属于同一类。
②没有剩余属性可以用来进一步划分样本．在这种情况下．使用多数表决，将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布[这个主要可以用来剪枝]。
③如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类生成叶子节点。
算法中2)步所指的最优分类能力的属性。这个属性的选择是本算法种的关键点，分裂属性的选择直接关系到此算法的优劣。
一般来说可以用比较信息增益和信息增益率的方式来进行。
其中信息增益的概念又会牵扯出熵的概念。熵的概念是香农在研究信息量方面的提出的。它的计算公式是：
Info(D)=-p1log(p1)/log(2.0)-p2log(p2)/log(2.0)-p3log(p3)/log(2.0)+...-pNlog(pN) /log(2.0) (其中N表示所有的不同类别)
而信息增益为：
Gain(A)=Info(D)-Info(Da) 其中Info(Da)数据集在属性A的情况下的信息量(熵)。
3算法的特点
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题
适用数据范围：数值型和标称型。
4python代码实现
1、创建初始数据集，用于测试
######################################
#功能：创建数据集
#输入变量：空
#输出变量：data_set, labels 数据集，标签
######################################
def create_data_set():
data_set = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']] # 数据集最后一列表示叶结点，也称类别标签labels = ['no surfacing', 'flippers'] # 表示决策结点，也称特征标签return data_set, labels
2、计算给定数据集的信息熵
#############################
#功能：计算信息熵
#输入变量：data_set 数据集
#输出变量：shannon_ent 信息熵
#############################
def calc_shannon_ent(data_set):
num_entries = len(data_set)
label_counts = {}
for feat_vec in data_set:
current_label = feat_vec[-1]
# get相当于一条if...else...语句
# 如果参数current_label不在字典中则返回参数0，
# 如果current_label在字典中则返回current_label对应的value值label_counts[current_label] = label_counts.get(current_label, 0) + 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
3、按照给定特征划分数据集。分类算法除了需要测量信息熵，还需要划分数据集，这就需要对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。
#################################
#功能：划分数据集
#输入变量：data_set, axis, value
# 数据集，数据集的特征，特征的值
#输出变量：ret_data_set, 划分后的数据集
#################################
def split_data_set(data_set, axis, value):
ret_data_set = []
for feat_vec in data_set:
if feat_vec[axis] == value:
# 把axis特征位置之前和之后的特征值切出来
# 没有使用del函数的原因是，del会改变原始数据
reduced_feat_vec = feat_vec[:axis]
reduced_feat_vec.extend(feat_vec[axis+1:])
ret_data_set.append(reduced_feat_vec)
return ret_data_set
4、遍历整个数据集，循环划分数据并计算信息熵，通过计算最大信息增益来找到最好的特征划分方式。
