机器学习之决策树

算法 阅读量

顾名思义，决策树是基于树结构进行决策的。一个决策树包含一个根节点、若干个内部结点和若干个叶结点构成的，叶结点对应于决策结果，其他每个结点则对应一个属性测试，每个结点包含的样本集根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一颗泛化能力前，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”策略。

基本算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
输入：训练集D={(x1,y1).(x1,y2)...,(xm,ym)};
  	 属性集A={a1,a2,...,ad}
过程：函数TreeGenerate(D，A)
 1.生成结点node;
 2.if D中样本全属于同一类别C then
 3.   将node标记为C类叶结点; return
 4.end if
 5.if A=null or D中赝本在A上取值相同 then
 6.   将node标记为叶结点，其类别标记为D中样本书最多的类; return
 7.end if
 8.从A中划分最优划分属性a*;
 9.for a* 的每个一直a*v do
10.    为node生成一个分支;令Dv表示D中在a*上取值为a*v的样本子集;
11.    if Dv为空 then
12.		 将分支结点标记为叶结点，其类别标记为D中样本最多的类; return
13.	   else
14.		 以TreeGenerate(Dv,A\{ax})为分支结点
15.    end if
16.end for
输出： 以node 为根结点的一颗决策树

划分选择

参照上述算法的第8行代码，即如何选择最优划分属性。我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的”纯度”越来越高。

信息熵

信息熵：”信息熵“是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为pk(k=1,2,3,….|y|)，D的信息熵定义为

可见，Ent(D)的值越小，样本的纯度越高。接下来编写代码计算信息熵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from math import log
def createDataSet():
    dataSet = [[0, 0, 0, 0, 'no'],  # 数据集
               [0, 0, 0, 1, 'no'],
               [0, 1, 0, 1, 'yes'],
               [0, 1, 1, 0, 'yes'],
               [0, 0, 0, 0, 'no'],
               [1, 0, 0, 0, 'no'],
               [1, 0, 0, 1, 'no'],
               [1, 1, 1, 1, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [2, 0, 1, 2, 'yes'],
               [2, 0, 1, 1, 'yes'],
               [2, 1, 0, 1, 'yes'],
               [2, 1, 0, 2, 'yes'],
               [2, 0, 0, 0, 'no']]
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况']  # 特征标签
    return dataSet, labels
# 计算信息熵
def calcShannonEnt(dataSet):
    numEntries = len(dataSet)      # 记录数据集中实例的总数
    labelCounts = {}               # 保存每个标签出现次数的字典
    for featVec in dataSet:
        currentLabel = featVec[-1] # 保存数据最后一列所表示表示的类别（标签的信息）
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0   # 如果标签中没有放入统计次数的字典，就添加进去
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0               # 信息熵
    for key in labelCounts:        # 计算信息熵
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

信息增益

条件熵： 学习信息增益之前，我们有必要先了解条件熵，条件熵H(Y|X)表示已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵H(Y|X)。用通俗的话来说，就是不同的分支结点包含的样本数不同，我们给分支结点赋予权重||Dv|/|D|，即样本数越多的分支结点结点的影响越大。

于是可以计算出用属性a对样本即D进行划分所获得的”信息增益”

信息增益越大，则意味着使用属性a来进行划分所获得的”纯度提升”越大。这样，通过这种方式计算得出的信息增益，我们会取最高值作为划分属性。下面给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 按照给定的特征划分数据集
def splitDataSet(dataSet, axis, value):
    retDataSet= []
    for featVec in dataSet:                   # 遍历数据集
        if featVec[axis]  == value:
            reducedFeatVec = featVec[:axis]   # 去掉axis特征
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec) # 将符合条件的添加到返回的数据集
    return retDataSet
# 选择最优特征
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1           # 特征数量
    baseEntropy = calcShannonEnt(dataSet)       # 计算数据集的特征熵
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        # 获取dataSet的第i个所有特征
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)              # 创建set集合{}，元素不可重复
        newEntropy = 0.0                        # 经验条件熵
        for value in uniqueVals:                # 计算信息增益
            subDataSet = splitDataSet(dataSet, i, value)  # subDataSet划分后的子集
            prob = len(subDataSet) / float(len(dataSet))  # 计算子集的概率
            newEntropy += prob * calcShannonEnt(subDataSet)# 根据公式计算经验条件熵
        infoGain = baseEntropy - newEntropy               # 计算信息增益
        print("第%d个特征的增益为%.3f" % (i,infoGain))
        if (infoGain > bestInfoGain):           # 找出最大的信息增益及索引
            bestInfoGain = infoGain
            bestFeature = i
    return  bestFeature                         # 返回最大的信息增益的特征索引
if __name__ == '__main__':
    dataSet, features = createDataSet()
    print("最优特征索引值：" + str(chooseBestFeatureToSplit(dataSet)))

splitDataSet()函数用来划分数据，即将符合条件的数据从数据集中划分出来，chooseBestFeatureToSplit()函数可以计算出每个特征的信息增益，最后返回信息增益最大的特征索引。程序输出如下：

第0个特征的增益为0.083
第1个特征的增益为0.324
第2个特征的增益为0.420
第3个特征的增益为0.363
最优特征索引值：2

增益率

从算法中可以看出，信息增益算法对可取值较多的特征有所偏好，为了解决这种偏好带来的不利影响，著名的C4.5决策树算法不直接用信息增益，而是使用”增益率”来区分最优特征。

增益率对取值较少的特征有所偏好，它的算法思想是：先从候选划分属性中找出信息增益高出平均水平的属性，再从中选择增益率最高的。

构建决策树

由于需要划分最好的属性构建数据集，而且特征属性不唯一，所以可能存在多个分支的数据集划分。第一次划分时，数据集向下传递到树分支的下一个结点，然后再次划分，所以我们采用递归的思想构建决策树。

递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下所有实例都具有相同的分类。如果所有与的实例拥有相同的分类，则得到一个叶子结点或终止。任何到达数据结点的数据必然属于叶子结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 统计classList中出现次数最多的元素(类标签)
def majorityCnt(classList):
    classCount = {}
    for vote in classList:  # 统计每个元素出现的次数
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    # 根据字典的值降序排列
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]
"""
函数说明：递归构建决策树
Parameters:
    dataSet - 训练数据集
    labels  - 分类训练属性
    featLabels - 存储选择的最优特征标签
"""
def createTree(dataSet, labels, featLabels):
    classList = [example[-1] for example in dataSet]        # 取分类标签(最后一个属性：是否放贷)
    if classList.count(classList[0]) == len(classList):     # 类别完全相同则停止继续划分
        return classList[0]
    if len(dataSet[0]) == 1:                                # 遍历完所有特征,返回出现次数最多的类标签
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)            # 根据信息增益，算出最优特征索引
    bestFeatLabel = labels[bestFeat]                        # 取出最优标签索引
    featLabels.append(bestFeatLabel)
    myTree = {bestFeatLabel: {}}                            # 建立以该特征为结点的枝干（根）
    del (labels[bestFeat])                                  # 删除该标签
    featValues = [example[bestFeat] for example in dataSet]
    uniquevalues = set(featValues)                          # 取出该标签下的特征数量（去重复）
    for value in uniquevalues:                              # 遍历所有特征进行递归，创建决策树
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), labels, featLabels)
    return myTree
if __name__ == '__main__':
    dataSet, features = createDataSet()
    # print("最优特征索引值：" + str(chooseBestFeatureToSplit(dataSet)))
    featLabels = []
    myTree = createTree(dataSet, features, featLabels)
    print(myTree)

建立决策树的函数有两种情况返回值，一是类别相同时，如果该数据集标签完全相同则以意味着已到叶子结点，该种类型分类完毕。二是在遍历完所有特征后，相当于特征不够用，决策树建立失败，所以返回出现最多的类标签（递归建立决策树过程中，会去除已经使用过的类标签，所以如果特征不够用，分割下来的数据集只有类标签而没有其他属性，所以len(dataSet[0]) = 1）。程序输出如下：

{‘有自己的房子’: {0: {‘有工作’: {0: ‘no’, 1: ‘yes’}}, 1: ‘yes’}}

存储决策树

对于庞大的数据量来说，不可能在每次分类都要构建决策树，这样就需要将样本存储起来，为了节省时间，最好能在每次执行分来是调用已经构造好的决策树。我们使用pickle模块序列化对象。

1
2
3
4
5
6
7
8
9
# 存储决策树
def storeTree(inputTree,filename):
    with open(filename,'wb') as fw:
        pickle.dump(inputTree,fw)
# 读取决策树
def grabTree(filename):
    fr = open(filename,'rb')
    return pickle.load(fr)

使用决策树算法进行分类

在使用决策树算法对数据分类时，同样使用递归的思想，具体方法见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
说明：根据给出的决策树进行分类
Parameters：
    inputTree:已经生成的决策树
    featLabels:存储选择的最优特征标签（决策树中存在的标签）
    testVec:测试数据
Returns:
    classLabels:分类结果
"""
def classify(inputTree,featLabels,testVec):
    firstStr = next(iter(inputTree))          # 取字典中的键为先判断的条件
    secondDict = inputTree[firstStr]          # 取以该决策树的键值为字典
    featIndex = featLabels.index(firstStr)    # 取该判断条件在最优特征标签的位置
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]).__name__ == 'dict':  # 当该分支下还有分支时，继续向下递归，否则就取该值
                classLabel = classify(secondDict[key],featLabels,testVec)
            else:
                classLabel = secondDict[key]
    return classLabel
  
if __name__ == '__main__':
    dataSet, features = createDataSet()
    # print("最优特征索引值：" + str(chooseBestFeatureToSplit(dataSet)))
    featLabels = []
    myTree = createTree(dataSet, features, featLabels)
    print(myTree)
    testVec = [0,1]                                        #测试数据
    result = classify(myTree, featLabels, testVec)
    if result == 'yes':
        print('放贷')
    if result == 'no':
        print('不放贷')

需要注意的是，输入的测试数据要满足得出的最优特征集，而且索引要一一对应。输入测试数据[0,1]，它代表没有房子，但是有工作，分类结果为放贷。

Powered by Hexo and Hexo-theme-hiker

Copyright © 2016 - 2019 Dreaouth All Rights Reserved.

访客数 : | 访问量 :