1. 引言
决策树(decision tree)学习的目的是产生一课泛化能力强的树，在非叶节点进行属性测试，每个叶结点对应了一个判定测试序列。其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）的策略。
2. 算法流程
决策树算法流程
根据算法流程图可知，决策树的生成就是一个递归的过程，三种情形会导致递归返回。其中，最重要的一个步骤是从属性集A中选择一个最优划分属性，下面介绍如何选择最优划分属性。
3. 划分选择
3.1信息增益
在进行介绍之前，首先说明一下熵的概念。
- 热力学熵：熵是一种不可逆性。温度只能自发的从高到低，熵增意味着所能使用的能量的减少。从一种有序的状态到一种无序的状态，无法利用的能量越来越多。老子有一句话，“天之道，损有余而补不足”。
- 信息熵：反应了对一件事物的了解程度。了解的越少，熵越大。
- 构象熵：反映了对一件东西的不确定性。越不确定，熵越大。
进入正题……
信息熵（information entropy）是度量样本集合纯度最常用的一种指标。
信息熵和信息增益 - Ent(D)的值越小，则D的纯度越高。
- 信息增益的值越大，意味着使用属性a进行划分获得的“纯度提升”越大。则选择最优属性时计算出信息增益，然后选择出增益最大的那一个属性作为这个结点的划分属性。
3.2 增益率
信息增益对取值较多的属性有所偏好，这样导致的结果是分支过多，而每个分支结点的样本数较少。因此提出了增益率的概念，C4.5决策树算法使用增益率进行度量。
增益率
增益率可能对取值较少的属性友好。所以，作为一个权衡，使用一个
启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
3.3 基尼指数
CART决策树使用基尼指数（Gini index）来选择划分属性。
基尼值和基尼指数
Gini(D)表示从数据集D中随机抽取两个样本，其类别标记不一致的概率。Gini（D）越小，数据集的纯度越高。
在进行选择时，选择基尼指数最小的作为最优划分属性。
4. 防过拟合——剪枝处理
-
预剪枝（prepruning）：指在决策树生成过程中，对每个结点在划分前先进进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点。
预剪枝虽然降低了过拟合的风险，但带来了欠拟合的可能。基于“贪心”本质禁止展开分支，可能会导致暂时不能提高泛化性能但对之后有帮助的展开无法继续。 -
后剪枝（postpruning）：先从训练集中训练出一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
后剪枝带来的欠拟合风险很小，泛化性能优于预剪枝。但是，由于后剪枝是在决策树生成之后进行操作，因此训练时间开销比未剪枝决策树和预剪枝决策树大得多。
采用“留出法”（留出一部分数据集用来验证能否带来泛化性能的提升），用信息增益进行最优划分属性的选择。
5. 连续与缺失值
5.1 连续值
简言之，就是寻找连续属性的最佳分割点，使取该点时获得的信息熵是最大的。
连续属性的处理
5.2 缺失值的划分
-
在属性值缺失的情况下进行划分属性的选择
在进行最优划分属性的选择时，增加未缺失样本的比重，用未缺失样本计算类、属性的比重。
属性值缺失时的处理 -
划分时属性值缺失
将该样本划分到所有子结点中，但是所占的比重不同，这个比重根据完整值样本中的比重决定。
属性值缺失的划分
6. 多变量决策树
决策树的分类边界由若干与坐标轴平行的分段组成。
决策树分类边界
每次划分只对应一个属性的选择会有很大的开销，多面量决策树（multivariate decision tree）进行了简化。非叶结点不止针对一个属性，而是对属性进行线性组合，构建一个线性组合分类器。比如通过OCI贪心的寻找到每个属性的最有权值，在局部优化的基础上对分类边界进行随机扰动以找到更好的边界。或者使用最小二乘法、感知机树等构造神经网络的方法。
多变量决策树
另外，决策树的学习也可以使用增量学习，接收到新样本之后在已学得的样本上进行调整，主要机制是通过调整分支路径上的划分属性次序对树部分进行重构。
7. 基于决策树进行西瓜好坏的分类
- 数据来源：西瓜书上的西瓜数据
A.加载数据集
def loadExcel(dataPath):
#返回的数据类型为dataFrame,导入的数据是存在标题行的
ori_data = pd.read_excel(dataPath)
#转化为numpy的展示方式，转化之后第一行消失
ori_data = ori_data.values
#增加标签栏
label = ["编号","色泽","根蒂","敲声","纹理","脐部","触感","密度","含糖率","好瓜"]
label_exist = [0,0,0,0,0,0,0,0,0,0]
temp_data = []
for i in range(len(ori_data)):
temp_data.append([])
for j in range(len(label)):
temp_data[i].append(ori_data[i][j])
#将数据转化到列表中
ori_data = temp_data
return ori_data, label,label_exist
数据集
B.创建树模型
这是主函数
if __name__ == "__main__":
train_path = "/home/stardream/DDML/MachineLearning/dataSet/watermelon3.0.xlsx"
#加载表格中的数据
dataSet, labels,l_exist = loadExcel(train_path)
#创建树模型
decisionTree = createTree(dataSet,labels,l_exist)
print(decisionTree)
C.createTree()
这是中间涉及的相关函数。
def mostClass(result):
#创建一个字典
className = {}
for name in result:
#字典中的键值不存在，增加一个新的
if name not in className.keys():
className[name] = 0
className[name] += 1
#依据键值对进行排序
sortedClass = sorted(className.iteritems(), reverse = True)
#返回最多的类别
return sortedClass[0][0]
def calEnt(ori_data):
result = {}
#得带对应类别的数目
for data in ori_data:
if data[-1] not in result.keys():
result[data[-1]] = 0
result[data[-1]] += 1
Ent = 0.0
#依据公式进行熵的计算
for key in result:
Pk = float(result[key]/len(ori_data))
Ent -= Pk* math.log(Pk,2)
return Ent
#若使用属性划分，则划分出来的子集整理为小数据集
def spiltSet(value, i, ori_data, seq):
sub_set = []
if i==7 or i==8:
if seq == 0:
for j in ori_data:
if j[i] < value:
temp = j[:i]
temp.extend(j[i + 1:])
sub_set.append(temp)
elif seq == 1:
for j in ori_data:
if j[i] >= value:
temp = j[:i]
temp.extend(j[i + 1:])
sub_set.append(temp)
else:
# 对应属性下的数据集
for j in ori_data:
if j[i] == value:
temp = j[:i]
temp.extend(j[i + 1:])
sub_set.append(temp)
return sub_set
def continue_value(sum_en,index,ori_data):
conGain = 0.0
classEnt = 0.0
bestGain =0.0
conFlag = 0
feature = [example[index] for example in ori_data]
sorted(feature)
for i in range(len(feature)-1):
midVal = float((feature[i]+feature[i+1])/2.0)
for j in range(2):
subSet = spiltSet(midVal,index,ori_data,j)
# 总增益
classEnt -= float(calEnt(subSet) * len(subSet) / len(ori_data))
conGain = sum_en + classEnt
if bestGain < conGain:
bestGain = conGain
conFlag = midVal
return conGain, conFlag
def gain_choose(ori_data):
#计算熵
sum_enropy = calEnt(ori_data)
temp_enropy = 0.0
flag2 = -1
#跳过编号，从第1个开始。因为编号的增益是最大的，使用编号之后算法停止，然而类别太多
#不考虑最后一列的好瓜列表
for i in range(1,len(ori_data[0])-1):
feature = [example[i] for example in ori_data]
feature = set(feature)
classEnt = 0.0
if i==7 or i==8:
Gain_data, conFlag = continue_value(sum_enropy,i,ori_data)
else:
for value in feature:
#将属性的每一个值进行计算对应的增益
subSet = spiltSet(value, i, ori_data,-1)
#总增益
classEnt -= float(calEnt(subSet)*len(subSet)/len(ori_data))
Gain_data = sum_enropy + classEnt
#选出最大的增益
if Gain_data>temp_enropy:
flag = i;
temp_enropy = Gain_data
print("2flag")
print (flag)
print(flag2)
if flag ==7 or flag == 8:
flag2 = conFlag
#返回最大增益属性
return flag,flag2
#构建决策树
def createTree(ori_data,label,lEx):
subLabels = []
print(label)
#每一组数据的结果保存在temp_result中
temp_result = [result[-1] for result in ori_data]
#如果只有一种结果，那么直接返回这一种结果，无需继续构建决策树
if len(set(temp_result)) == 1:
return temp_result [0]
#若每组数据中的属性值都相同，则无须继续构建，直接返回所占比重最大的结果;或者没有属性值是无须构建
#取除结果以外的数据进行对比
temp_result2 = [result[:len(label)-1] for result in ori_data]
flag = 1
for i in range(len(temp_result2)):
for j in range(len(temp_result2[0])):
if temp_result2[i][j] != temp_result2[i+1][j]:
flag=0
break;
if flag == 0:
break;
if flag == 1 or len(ori_data[0]) == 1:
return mostClass(temp_result)
#计算增益，返回增益最大的对应的属性
best_Feature,flag2 = gain_choose(ori_data)
bestLabel = label[best_Feature]
decision_tree = {bestLabel:{}}
lEx[best_Feature] = 1
#del(label[best_Feature])
print(bestLabel,flag2)
if best_Feature == 7 or best_Feature==8:
for j in range(2):
for p in range(len(lEx)):
if lEx[p] == 0:
subLabels.append(label[p])
#递归进行划分
decision_tree[bestLabel][flag2] = createTree(spiltSet(flag2, best_Feature, ori_data, j), subLabels, lEx)
else:
featValues = [example[best_Feature] for example in ori_data]
# 得到属性下的各个值
uniqueVals = set(featValues)
for value in uniqueVals:
for p in range(len(lEx)):
if lEx[p] == 0:
subLabels.append(label[p])
#递归进行划分
decision_tree[bestLabel][value] = createTree(spiltSet(value, best_Feature, ori_data,-1), subLabels, lEx)
return decision_tree
数据集在这里
编号 色泽 根蒂 敲声 纹理 脐部 触感 密度 含糖率 好瓜
1 青绿 蜷缩 浊响 清晰 凹陷 硬滑 0.697 0.46 是
2 乌黑 蜷缩 沉闷 清晰 凹陷 硬滑 0.774 0.376 是
3 乌黑 蜷缩 浊响 清晰 凹陷 硬滑 0.634 0.264 是
4 青绿 蜷缩 沉闷 清晰 凹陷 硬滑 0.608 0.318 是
5 浅白 蜷缩 浊响 清晰 凹陷 硬滑 0.556 0.215 是
6 青绿 稍蜷 浊响 清晰 稍凹 软粘 0.403 0.237 是
7 乌黑 稍蜷 浊响 稍糊 稍凹 软粘 0.481 0.149 是
8 乌黑 稍蜷 浊响 清晰 稍凹 硬滑 0.437 0.211 是
9 乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑 0.666 0.091 否
10 青绿 硬挺 清脆 清晰 平坦 软粘 0.243 0.267 否
11 浅白 硬挺 清脆 模糊 平坦 硬滑 0.245 0.057 否
12 浅白 蜷缩 浊响 模糊 平坦 软粘 0.343 0.099 否
13 青绿 稍蜷 浊响 稍糊 凹陷 硬滑 0.639 0.161 否
14 浅白 稍蜷 沉闷 稍糊 凹陷 硬滑 0.657 0.198 否
15 乌黑 稍蜷 浊响 清晰 稍凹 软粘 0.36 0.37 否
16 浅白 蜷缩 浊响 模糊 平坦 硬滑 0.593 0.042 否
17 青绿 蜷缩 沉闷 稍糊 稍凹 硬滑 0.719 0.103 否
代码放在(决策树)[https://github.com/RuiDream/simpleAl]，很遗憾运行不正确，原因是加入了连续值的处理，而没有处理好。如果把连续值的那一部分去了对离散值来说是对的，本想改一改，一个国庆假期间隔太久，改不动了。意思到就行，以后不能写这样的半吊子代码了。
