一. 背景

1. 适合决策树应用的三个条件

• 训练数据记录形式是attr-value pairs
• 数据质量: 数据可能可能有缺失的值, 有噪音
• 离散型: 目标函数y, 以及特征属性字段都是离散类型; 如果是数值型变量, 也可以转化成分类变量

2. 实际应用

决策树生成的if-then规则容易被人理解, 是一种非常清晰明了的知识. 很多情况下被用来做expert system. 很典型的一个例子是医学上的诊断: 依据患者的p个症状, 给出其属于哪个类型病症(离散型)的答案.

3. 算法分类

ID3, 最早的实用算法.
当下最常用的: C4.5, C5.0

二. 决策树的基本

1. 树的结构

叶子层, 规则的结论; 内层, 代表一个判断结点.
顺着一条链路下来是conjunction(&&合取关系), 而同层次之间是disjunction(||析取关系)的关系

example of a decision tree

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)

如何计算信息熵Entropy

#计算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)

计算GainRatio

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