用ID3算法构造决策树

　　简单例子

（1）计算信息熵

　　ID3算法用信息增益来寻找最优划分特征：计算每个特征划分数据集的信息增益，选择信息增益最大的特征
　　什么是信息增益？ 划分数据集后，增加了多少信息？不确定性降低了多少？有序性增加了多少？这些都是信息增益。
　　如何计算信息增益？ 用划分前后信息的增量计算，样本x的信息=$-\log_2p(x_i)$，i是样本属于的类别。一个数据集的信息可以用熵来表示，熵是信息的期望，公式为，一共有k个类别。
　　信息增益 = ① - ②
　　　　①划分前，计算数据集的信息熵
　　　　②划分后，计算出每个子集的信息熵，再求它们的加权和（权重是子集数/总数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#熵
import numpy as np
from math import log
def entropyFunc(data):
    m = len(data)
    labelCount = {}       #统计每一类别出现的次数
    for feature_vec in data:       #遍历样本
        labelvalue = feature_vec[-1]       #该样本的类别
        labelCount[labelvalue] = labelCount.get(labelvalue,0)+1

    shannonEnt = 0.0
    for k in labelCount:
        prob = labelCount[k] / m
        shannonEnt -= prob * log(prob,2)
    return shannonEnt

1
2
3
4
#测试
>> a = [[1,1,'no'],[1,1,'no'],[1,0,'yes'],[0,1,'yes'],[0,1,'yes']]
>> entropyFunc(a)
0.9709505944546686

（2）按不同的特征值，划分出相应的子集

1
2
3
4
5
6
7
8
9
#划分特征是'A'，用该特征划分能得到2个子树
def splitData(data, featindex, value):
    subdata = []
    for sample in data:
        if sample[featindex] == value:
            featvec = sample[:featindex]
            featvec.extend(sample[featindex+1:])
            subdata.append(featvec)
    return subdata
1
2
>> splitData(a,0,1)
[[1, 'no'], [1, 'no'], [0, 'yes']]

（3）找到划分数据集的最优特征

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#选择最优划分特征
def chooseBestFeature(data):
    feat_num = len(data[0])         #特征数
    before_entropy = entropyFunc(data)        #数据集划分前的熵
    best_info_gain = 0.0
    best_feature = -1

    for i in range(feat_num - 1):       #遍历每个特征，只剩一个特征就不用划分了
        feat_list = [sample[i] for sample in data]       #该特征的所有值(有重复)
        feat_unique = set(feat_list)

        later_entropy = 0.0       #不声明的话,下面的for循环外的区域就不能使用该变量
        for val in feat_unique:
            subdata = splitData(data, i, val)
            prob = len(subdata)/len(data)
            later_entropy += prob * entropyFunc(subdata)       ##数据集划分后的熵

        info_gain = before_entropy - later_entropy       #计算每个特征的信息增益
        if(info_gain > best_info_gain):
                best_info_gain = info_gain
                best_feature = i
    return best_feature        #返回最优特征的索引
1
2
>> chooseBestFeature(a)
0      #说明第1个特征A(索引是0)是最好的划分数据集的特征

（4）构造树

　　当一个节点遇到以下情况时不分裂：
　　　　①数据集中的数据属于同一类别
　　　　②遍历完所有的特征（注意C4.5和CART每次划分数据时,不会减少特征），采用多数表决的方法决定该数据集的类别
　　其它情况时递归调用自己，继续按照相同的方式分裂

1
2
3
4
5
6
7
#投票表决器
def majorityClass(classlist):
    classCount = {}
    for vote in classlist:
        classCount[vote] = classCount.get(vote, 0) + 1
        sortedCount = sorted(classCount.items(), key = lambda x:x[1], reverse = True)
    return sortedCount[0][0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#构造树
def createTree(data, labels):
    classlist = [sample[-1] for sample in data]
    if classlist.count(classlist[0]) == len(classlist):    #如果类别完全相同(数据集只有一个类别)，则停止递归
        return classlist[0]       #直接返回叶子节点
    if len(data[0]) == 1:       #如果遍历完所有特征(只剩下标签列)，则停止递归
        return majorityClass(classlist)       #直接返回投票表决结果

    best_feature = chooseBestFeature(data)       #划分数据集的最好特征索引
    best_feature_label = labels[best_feature]       #该特征的名称
    myTree = { best_feature_label:{} }        #生成根结点
    del(labels[best_feature])

    feat_list = [sample[best_feature] for sample in data]
    feat_unique = set(feat_list)       #该特征的值
    for val in feat_unique:
        sublabels = labels[:]
        myTree[best_feature_label][val] = createTree(splitData(data,best_feature,val), sublabels)
    return myTree
1
2
3
4
>> labels = ['A','B']
>> myTree = createTree(a,labels)
>> myTree
{'A': {0: 'yes', 1: {'B': {0: 'yes', 1: 'no'}}}}

（5）绘制树

　　点击查看代码：treePlotter.py

1
2
import treePlotter
treePlotter.createPlot(myTree)

　　例子图

（6）用决策树分类

　　在存储带有特征的数据会面临一个问题：程序无法确定特征在数据集中的位置，需要传入一个标签列表（位置与数据集的特征位置一致）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#myTree = {'A': {0: 'yes', 1: {'B': {0: 'yes', 1: 'no'}}}}
#labels = ['A','B']
#x_test = [1,1]
#输出的类别应该是'no'
def classify(myTree, labels, x_test):
    first_str = list(myTree.keys())[0]       # 'A'
    feature_index = labels.index(first_str)       # 特征A在标签的哪个位置

    second_dict = myTree[first_str]        # {0: 'yes', 1: {'B': {0: 'yes', 1: 'no'}}}
    for key in second_dict.keys():       #遍历0、1（是特征A的值）
        if x_test[feature_index] == key:       #如果测试向量的A特征值是key
            if type(second_dict[key]).__name__ == 'dict':       #如果该特征值对应的节点不是叶子
                classlabel = classify(second_dict[key], labels, x_test)
            else:
                classlabel = second_dict[key]
    return classlabel

1
2
3
4
5
>> myTree = {'A': {0: 'yes', 1: {'B': {0: 'yes', 1: 'no'}}}}
>> labels = ['A','B']
>> x_test = [1,1]
>> classify(myTree, labels,x_test)
'no'

（7）保存决策树

　　构造决策树非常耗时，而用创建好的决策树解决问题会很快。用pickle序列化对象，每次执行分类时就调用已构造好的决策树即可(k近邻算法就无法持久化分类器)

1
2
3
4
5
6
7
8
9
10
def storeTree(myTree,filename):      #保存
    import pickle
    fw = open(filename, 'wb')      #以二进制读写方式打开文件
    pickle.dump(myTree, fw)         #序列化对象
    fw.close()

def grabTree(filename):      #读取文件，反序列化
    import pickle
    fr = open(filename, 'rb')
    return pickle.load(fr)

1
2
3
4
>> storeTree(myTree,'classifierStorage.txt')
>> myTree2 = trees.grabTree('classifierStorage.txt')
>> myTree2
{'A': {0: 'yes', 1: {'B': {0: 'yes', 1: 'no'}}}}

预测隐形眼镜的类型

　　隐形眼镜数据集来源于UCI数据库，包含很多患者眼部状况的观察条件，以及医生推荐的隐形眼镜类型（分为硬材质、软材质、不适合佩戴隐形眼镜）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>> fr = open('lenses.txt')
>> lenses = [inst.strip().split('\t') for inst in fr.readlines()]    #用\t分割数据行
>> lensesLabels = ['age','prescript','astigmatic','tearRate']
>> lensesTree = createTree(lenses, lensesLabels)    #构造树
>> lensesTree
{'tearRate': {'normal': {'astigmatic': {'no': {'age': {'pre': 'soft',
      'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}},
      'young': 'soft'}},
    'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses',
        'presbyopic': 'no lenses',
        'young': 'hard'}},
      'myope': 'hard'}}}},
  'reduced': 'no lenses'}}

>> import treePlotter
>> treePlotter.createPlot(lensesTree)

　　决策树
　　ID3算法的优点：计算复杂度不高，输出的结果易于理解，对缺失值不敏感，可以处理不相关特征数据。
　　ID3算法的缺点： ①上图所示的决策树非常好地匹配了实验数据，但是而这些匹配选项可能太多了（即可能产生过拟合问题），为了降低过拟合问题，我们可以裁剪决策树，去掉一些不必要的叶子节点（如果叶子节点只能增加少许信息,则可以删除该节点,将它并人到其他叶子节点中）；②ID3算法只能处理分类型或离散数值型数据，处理连续型数据可以用CART回归树算法。