决策树

决策树

---

3.1决策树的构造

决策树

优点:计算复杂度较低,输出易于理解,对中间值的缺失不敏感,可以处理不相关数据
缺点:可能会产生过度匹配的问题
适用数据类型:数值型和标称型

构造决策树的第一个问题,找出当前数据集上对数据划分取决定性因素的特征,这时原始数据被划分成几个数据子集.这些子集分布在各个节点上,如果该节点的数据都是同类型,则结束,如果不是同一类型,继续进行决策树.

---

3.1.1信息增益

在划分数据集之后信息发生的变化称为信息增益.获得信息增益最高的特征就是最好的选择

信息熵概念:一个系统越有序,信息熵就越低,反之一个系统越是胡乱,信息熵就越高.信息熵被认为是信息有序化程度的一个度量.

信息量的定义:如果一个消息x出现的概率为p,则这一个消息所含的信息量是

信息熵:

计算给定数据的信息熵:

from math import log
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 shannoEnt

---

3.1.2划分数据集

基本思路:
遍历列表,将特征值符合value的值提出来,并将对应特征值抽掉,得到抽取后的数据子集,计算该数据子集的信息熵

def spiltDataSet(dataSet,axis,value):
    #创建新的list对象,Python传入的是引用,如果直接使用dataSet会造成全局的dataSet改变
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            #以下三行抽取
            reduceFeatVec = featVec[: axis]
            reduceFeatVec.extend(featVec[axis+1:])   #分辨extend函数和append函数的区别
            retDataSet.append(reduceFeatVec)
    return retDataSet

整理得到一个给定数据集,求出最好当前数据集最好的划分特征的算法

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) -1
    baseEntropy = calcShannonEnt(dataSet)  #基础的熵
    bestInfoGain = 0.0   #信息增益
    bestFeature = -1
    for i in range(numFeatures):
        #(以下两行) 创建唯一的分类标签列表
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)   #取set
        newEntropy = 0.0
        #(以下五行) 计算每种划分方式的信息熵
        for value in uniqueVals:
            subDataSet = spiltDataSet(dataSet,i,value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob*calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if(infoGain > bestInfoGain):
            # 计算最好的信息增益
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

---

3.1.3递归构建决策树

原理:得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分.第一次划分之后,数据将被向下传递到树分支的下一个节点,在这个节点上,我们可以再次划分数据.因此我们可以采用递归的原则来处理数据集
递归结束的条件是:程序遍历完所有划分数据集的属性,或者每个分支下的所有实例都具有相同的分类.如果所有实例具有相同的分类,则得到一个叶子节点或者终止块,任何到达叶子节点的数据必然属于叶子节点的分类

决策树

import opeator
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] +=1
    sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reversed = True)
    return sortedClassCount[0][0]

以上代码:使用分类名称的列表,创建classList中唯一值的数据字典,字典对象存储了classList中每个类的名称和标签出现的次数,返回出现最多次的标签名称和次数