机器学习实战之决策树解析

机器学习实战之决策树解析，KNN算法无法给出数据内部的联系，而决策树算法通过提取一系列的规则，从而了解数据之间的内部联系。

决策树算法适用于数值型和标称型。数值型表示无限数据中，数据较为具体化，通常用于回归分析。标称型表示一般在有限的数据中取得，而且只存在是和否两种结果。

构造决策树时，首先需要知道哪个特征在划分数据分类时会起决定化的作用。这里我们就需要划分数据集。决策树的一般流程包括：收集数据，准备数据（树构造算法只适用于标称型的数据，数值型的数据必须离散化），分析数据，训练数据（构造树的数据结构），测试算法（使用经验树计算错误率），使用算法。

下面将以海洋生物数据表作为测试数据

………….不浮出水面是否可以生存 ………. 是否有脚蹼 ……… 属于鱼类
1…………………..是………………………………是………………..是
2…………………..是………………………………是………………..是
3…………………..是………………………………否………………..否
4…………………..否………………………………是………………..否
5…………………..否………………………………是………………..否

所以利用createDataSet() 得到表的鉴定集

def createDataSet():
    dataSet = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
    label = ['no sufacing','flippers']
    return dataSet,label

测试一下

>>> import chosetree as ct
>>> dataset,label = ct.createDataSet()
>>> dataset
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> label
['no sufacing', 'flippers']

在说下面内容时，先谈一谈几个概念(公式写的都比较粗糙，别介意啊）
信息增益：在划分数据集之前之后信息发生的变化。在这里我们可以认为是特征熵和数据集熵的差值；
熵（香农熵）：集合信息的度量方式，是信息的期望值。
第i分类的信息公式为l(xi) = log2P(xi)
以上表（第三列）为例：
p(x)=2/5 表示‘是‘的比例，p(x)=3/5表示否的比例
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，
公式为 H ＝ －∑i=1p(xi)log2p(xi)
以上表（第三列）为例：
H＝ －（2／5）＊log2(2/5) - (3/5)*log2(3/5)=0.97095….

计算给定数据集的香农熵：

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 shannonEnt

测试一下

>>> shannonEnt = ct.calcShannonEnt(dataset)
>>> shannonEnt
0.9709505944546686

说明； 熵越大说明类别越多，即混合的数据较为多

划分数据集
先放代码
这里使用了三个输入参数：带划分的数据集，划分数据集的特征（在这里实际上就是选择第几列特征），需要返回的特征的值

def splitDataSet(dataSet,axis,value):
#创建空列表，存放划分后的数据集
    retDataSet = []
    for featVec in dataSet:
    ＃判断axis所对应的数据与要求的value是否相同，如果相同则将每一行除featVec[axis]之外的所有数据放在reduceFeatVec中
        if featVec[axis]==value:
            reduceFeatVec = featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reduceFeatVec)
    return retDataSet

测试

>>> retDataSet = ct.splitDataSet(dataset,0,1)
>>> retDataSet
[[1, 'yes'], [1, 'yes'], [0, 'no']]

上述测试表示第0列的数据是否等于1 ，等于1就将符合条件的列表输出

选出最好的数据集划分方式

代码：

def chooseBestFeatureToSplit(dataSet):
＃计算所有的特征数
    numFeatures = len(dataSet[0])-1
    ＃调用函数获得数据集的香农熵
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bastFeature = -1
    for i in range(numFeatures):
        ＃获得该列特征的所有数值，并去重
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0.0
        ＃计算该列的香农熵
        for value in uniqueVals:
            subDataSet = splitDataSet(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

测试

>>> bestFeature = ct.chooseBestFeatureToSplit(dataset)
>>> bestFeature
0

bestFeature所代表的意思：

>>> label[0]
'no sufacing'

递归构建决策树

先思考一个问题：如果数据集已经处理列所有的属性，但类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法决定该叶子节点的分类。

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
        #@classCount.items 列表对象
    #@key=operator.itemgetter(1) 获取列表对象的第一个域的值
    #@reverse=true 降序排序，默认是升序排序
    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

创建树的函数代码

def createTree(dataSet,labels):
＃获得所有的类标签
    classList = [example[-1] for example in dataSet]
    ＃当所有的类标签为同一个时，直接返回该类标签
    if classList.count(classList[0]) == len(classList):
        return classList[0]
     ＃当使用完所有特征值仍然不能将数据集划分为仅包含唯一类别的分组，即调用majorityCnt函数
    if len(dataSet[0]) ==1:
        return majorityCnt(classList)
        ＃选择最好的特征值
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatlabel = labels[bestFeat]
    ＃构建决策树
    myTree = {bestFeatlabel:{}}
    ＃删除以使用过的标签，防止对后面迭代产生影响
    del(labels[bestFeat])
    featvalues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featvalues)
    for value in uniqueVals:
            #采用递归的方法利用该特征对数据集进行分类
        #@bestFeatLabel 分类特征的特征标签值
        #@dataSet 要分类的数据集
        #@bestFeat 分类特征的标称值
        #@value 标称型特征的取值
        #@subLabels 去除分类特征后的子特征标签列表
        subLabels = labels[:]
        myTree[bestFeatlabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree

测试代码：

>>> mytree = ct.createTree(dataset,label)
>>> mytree
{'no sufacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

好啦，暂时先写这么多，下一节我在放上测试算法和使用决策树预测隐形眼镜类型的例子。