一. 背景
1. 适合决策树应用的三个条件
- 训练数据记录形式是attr-value pairs
- 数据质量: 数据可能可能有缺失的值, 有噪音
- 离散型: 目标函数y, 以及特征属性字段都是离散类型; 如果是数值型变量, 也可以转化成分类变量
2. 实际应用
决策树生成的if-then规则容易被人理解, 是一种非常清晰明了的知识. 很多情况下被用来做expert system. 很典型的一个例子是医学上的诊断: 依据患者的p个症状, 给出其属于哪个类型病症(离散型)的答案.
3. 算法分类
ID3, 最早的实用算法.
当下最常用的: C4.5, C5.0
二. 决策树的基本
1. 树的结构
叶子层, 规则的结论; 内层, 代表一个判断结点.
顺着一条链路下来是conjunction(&&合取关系), 而同层次之间是disjunction(||析取关系)的关系
2. 注意事项
必须把属性字段收集好, 如果缺失了关键字段, 可能导致做不出一棵比较实用的决策树.
同样一批数据, 可能有不同的正确的决策树.
奥卡姆剃刀: 简单的树更好. 这是因为简单的树, 更能抓住一些容易泛化的关键属性, 通用能力更好, 实用性比较好.
3. 结点分裂算法
1 A = the best decision attr for next node //tricky part, how to get the best attr? use entropy!!
2 Assign A as decision attr for node
3 For each value of A, create new descendant of node
4 sorting traninng example to leaf nodes
5 if trainnning examples perfectly classified: //all records in a node are in the same category
stop
else:
iterate over new leaf nodes
三. ID3: 使用信息增益info gain分裂结点
1. 定义
info gain: how well a given attr separates the training examples according to their target classfication
entropy: purty of a Node, 取值总是正数, 越高代表混乱度越大.
Ent(x) = - Σ pi log pi
note: 可以观察到, pi∈[0, 1], 因此log(pi) <= 0, 所以必须在Σ前面加上负号, 把取值变成正.
2. 如何计算信息熵
我们找信息增益最大(使得信息熵下降最大的)属性字段.
某个字段的信息增益 = 没选这个字段前的信息熵(baseEntropy) - 选了之后的信息熵(newEntropy)
#计算InfoGain的过程
S = [9+, 5-], //S: Sample Set
Value(Wind) = { Weak, Strong } //Unique value set of attribute 'Wind'
Sweak = [6+, 2-] //Samples belongs to 'weak'
Sstrong = [3+, 3-] //Samples belongs to 'strong'
Gain(S;A) = Entropy(S)-(8/14) Entropy(Sweak )-(6/14)Entropy(SStrong ) //记得要写8/14, 6/14, 这代表的是每个部分的weight. 所以, 第一个weight是依据结点的UniqueValue
=[ -(9/14)log(9/14) - (5/14)log(5/14) ] - { (8/14)[ -(6/8)log(6/8) - (2/8)log(2/8) ] } - { (3/6)[ -(3/6)log(3/6) - (3/6)log(3/6) ] }
= 0.940 – (8/14)0.811 – (6/14)1.00
= 0.048
//weight • [ -p1•log(p1) - p2•log(p2) ] 第二个p1, p2等值, 是依据cate类在本结点样本(Sweak比如)上的占比
Python代码
def calcShannonEntropy(dataset):
"""Calcuate Shannon Entropy value for a list-form dataset
:param dataset: a list of vectors, with vec[-1] as each 's category
note: cate = category
"""
num = len(dataset)
cateCount = {}
for vec in dataset:
curCate = vec[-1]
if curCate not in cateCount.keys():
cateCount[curCate] = 0 #create a new entry
cateCount[curCate] += 1
entropy = 0.0
for key in cateCount.keys():
prob = cateCount[key]/num
entropy -= prob * log(prob,2)
return entropy
3. 如何分裂结点
分裂结点的时候, 我们要做的事, 就是选取出那个使得InfoGain最大, 换句话说使得newEntropy最小的字段bestFeatureName
def splitDataset(dataset, axis, value):
"""Split a dataset by a selected feature.
This will delete the feature in the returnDataset.
:param dataset: a list of vectors. Each vector is also a list.
:param axis: a chosen feature to split.
:param value: the chosen value for return dataset.
vector with other value will not be in the returnDataset
"""
retDataset = [];
for vec in dataset:
if vec[axis]==value:
retVec = vec[:axis]
retVec.extend(vec[axis+1:]) #extend a list with another list
retDataset.append(retVec)
return retDataset #returnDataset
#选取出infoGain最大的feature
def chooseBestSplitFeature(dataset):
p = len(dataset[0])-1 #number of properties
minEntropy = calcShannonEntropy(dataset)
bestFeature = -99
for i in range(p): #compute each feature's result entropy
feaList = [vec[i] for vec in dataset] #tricky! get a whole column
uniqueFeaSet = set(feaList)
newEntropy = 0.0
for value in uniqueFeaSet:
aDataset = splitDataset(dataset, i, value)
prob = len(aDataset)/len(dataset)
newEntropy += prob*calcShannonEntropy(aDataset) #别忘了要乘上prob
if newEntropy < minEntropy:
minEntropy = newEntropy
bestFeature = i
if bestFeature == -99:
print('bestFeature not chosen!!!')
return bestFeature #返回feature的index, 比如2
4. ID3算法伪代码与实现
Python
#投票法得出某个叶子节点的最终category
def getMajority(classList):
'''input: a list of class of this node, typically a leaf'''
classCount = {}
for vote in classList: #class关键字得替换成vote, 因为python保留了这个关键字
if vote not in classCount: classCount[vote] = 0
classCount[vote] += 1
aList = list(classCount.items())
sortedClassCount = sorted(aList, key=lambda x:x[1], reverse=True) #key=!
return sortedClassCount[0][0]
#给定list类型的dataset和feats, 创建一棵DecisionTree
def createTree(dataset, feats):
localfeats = list(feats)
classList = [row[-1] for row in dataset]
if classList.count(classList[0])==len(classList):
return classList[0] #return a label as it reaches purity
if len(dataset[0])==1: #no feature left
return getMajority(classList)
#chooseFeature
bestFeat = chooseBestSplitFeature(dataset)
bestFeatKey = localfeats[bestFeat]
del(localfeats[bestFeat]) #delete bestFeat from feats
print('bestFeatureName:',bestFeatKey)
#save the tree
aTree = {bestFeatKey:{}}
#split, create tree for each childnode
uniqueVals = set([row[bestFeat] for row in dataset])
for val in uniqueVals:
subFeats = localfeats[:]
childDataset = splitDataset(dataset, bestFeat, val)
aTree[bestFeatKey][val] = createTree(childDataset, subFeats)
return aTree
4. 从模型空间的角度来评价ID3算法
Hypo space is complete: target function surely in there. 模型假设的空间是完整的, 因此目标函数(函数和模型在这里是同义词)肯定在里面.
Robust to noisy data: statistically based search choices. 统计方法, 因此对噪声抵御能力较强
No back tracking: local minima. 没有回朔的手段, 因此可能陷入局部最优
inductive bias: the shorter, the better. 喜欢最短的决策树路径, 这个是出于实用的考量, 但是却不一定能得到最"精准"的决策树.
note: Restriction Biases & Preferences Biases
Preference bias is more desirable than Restriction biases. Restriction Biases直接把目标函数给排除在了模型空间(Hypothesis Space)之外, 而PreferenceBias是算法使用者的一种倾向性, 比如在决策树中, 算法使用者倾向使用短一些的决策树, 这样可以避免过拟合, 同时也容易理解一些.
一般我们认为保留选择给算法使用者是比较好的.
5. 数据的预先处理
1. 离散化方法
无监督(用的多): 等长(从0~100划分成5个bin), 定数量(每五个一类)
有监督: 人为地, 借助标签地分开数据. 比如看到45岁前没什么得心脏病, 45岁后很多人得了, 人为地设定为分为"年轻人", "老年人"两段.
2. 数据的缺失处理
离散型: 选取最频繁出现的值(众数)来代替, 或者写上缺失, 或者干脆删除这个属性(如果缺的太厉害)
6. 过拟合
解决办法: prun 剪枝
tree size = 一个凸起的函数. 要试图接近最好的点
forward pruning
Orange框架中的规则: (Orange是一个实现了决策树的框架)
如果结点上只有五个example就停止
如果发现这个结点有10个样例, 有至少7个都已经是一类(+/-), 那么可以停了
如果分支下去的两个叶子中, 有一个只有一个或者两个例子, 那么表示太具体了, 应该剪掉叶子
backward pruning
原理和forward类似, 但是会更好用一些.
三. 使用信息增益率改进: c4.5算法
1. ID3算法存在的严重问题: 特征取值越多越容易被选取
极端的例子是用户id, date这种取值极其多的属性, 这样属性的每个独特取值下, 都只有一个y的类别.
这样, id, date这种字段的熵就等于0. 因此, 决策树倾向于直接选取这些取值多的字段作为分裂结点.
而这样在实际业务中几乎没有用的.
2. InfoGain解决特征取值过多问题
C4.5引入了一个SplitInfo的分母来降低取值多的字段的InfoGain.
已知, InfoGain = Ent(S) - Ent(S ; A)
当遇到取值很多的字段的时候, Ent(S; A)急剧下降, 趋近于0. 那么, 我们可以对InfoGain整个值进行缩小, 来缓解这种问题.
我们选用的是SplitInfo(S, A) = –Σpm•logpm, 其中pm = 字段取某个独特值的时候, 所拥有的样本数 ÷ 总的样本数(到达这个分裂结点的样本数)
比如Temp = {cold: 5, normal: 10, hot: 8}
SplitInfo = -5/23•lg5/23 - 10/23•lg10/23 - 8/23•lg8/23
显然, 我们可以看出, 如果一个字段属性下, 独特的取值越多的话, 它的熵SplitInfo的值会越大. 由于SplitInfo被放在了分母的位置, 因此独特取值越多的字段, 会分到一个越小的权重.
GainRatio(S, A) = Gain(S, A) / SplitInfo(S, A)
3. C4.5算法伪代码
1 Check for the above base cases. //边界条件检查
2 For each attribute a, find the normalized information gain ratio from splitting on a.
3 Let a_best be the attribute with the highest normalized information gain.
4 Create a decision node that splits on a_best.
5 Recur on the sublists obtained by splitting on a_best, and add those nodes as children of node.
四. 最后: 决策树的评价
评价: 算法原理? 什么时候用? 优缺点?
1. 优点
健壮性: 统计方法决定了决策树抗噪声.
结果容易被理解: 在医疗等领域应用十分适合, 因为我们需要理解原因.
决策树的这些优点决定了它是一个简单易用的机器学习方法.
2. 缺点
如果使用C4.5算法, 克服了某个特征属性下独特取值过多的问题后,
决策树模型还是可能存在问题:
no backtracking: local optimal solution not global optimal solution 即无法回朔, 可能无法得到全局最优
3. overall
- practical 决策树是一个简单又实用的机器学习方法
- overfitting problem: 是做决策树的时候需要解决的问题;
- id3 searches the whole tree with inductive bias for smaller tree "id3"算法存在着对较小决策树的偏好.
- 由于决策树应用很多, 因此其的实用算法中会有很多很多的改进变种.
遗留一个问题供思考
如果树的结点顺序的不同, 结果会有不同吗?
参考资料
信息增益与信息增益率详解
c4.5为什么使用信息增益比来选择特征?
<机器学习实战> page42
