机器学习之决策树

决策树 也是用来给 数据做分类。

人物 :克劳德·艾尔伍德·香农

熵（entropy）指的是体系的混乱的程度，它在控制论、概率论、数论、天体物理、生命科学等领域都有重要应用，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。熵由鲁道夫·克劳修斯（Rudolf Clausius）提出，并应用在热力学中。后来在，克劳德·艾尔伍德·香农（Claude Elwood Shannon）第一次将熵的概念引入到信息论中来

分类问题

比如有一个盒子中 有三个球 那么到底怎么 分组 比较合适？

第一种分法：

1组 : 1 红 1 黑

2组： 1黑 。

第二种分法：

1组 : 1 红

2组： 2黑 。

那么到底哪种分类更科学呢 ？ 所以我们得有一个衡量标准。 香农 就提成了 信息熵 来衡量 。

信息熵

信息熵是用来评估样本集合的纯度的一个参数，就是说，给出一个样本集合，这个样本集合中的样本可能属于好多不同的类别，也可能只属于一个类别，那么如果属于好多不同的类别的话，我们就说这个样本是不纯的，如果只属于一个类别，那么，我们就说这个样本是纯洁的。
　　而信息熵这个东西就是来计算一个样本集合中的数据是纯洁的还是不纯洁的。下面上公式：
　　

其中 Pk 表示 某一个分类的概率
k表示有几种分类 。

比如上图第一种分类：

1组 : 1 红 1 黑
2组： 1黑 。
信息熵 就用公式可以这么表示：

E(红黑) = - 1/2 * log( 1/2, 2) - 1/2 * log (1/2, 2)

E(黑)= - 1 * log( 1, 2)

E(红黑|黑) = E(红黑) + E(黑) = - 1/2 * log( 1/2, 2) - 1/2 * log (1/2, 2) - 1 * log( 1, 2) = 1

其中： log (1/2, 2) 表示 1/2 为 Pk 2 为底数的 log公式。

上图 第二种分法：
1组 : 1 红
2组： 2黑 。

E(红) = - 1 * log( 1, 2)
E(黑黑) = - 1 * log( 1, 2)
E(红|黑黑) = E(红) + E(黑黑) = - 1 * log( 1, 2) - 1 * log( 1, 2) = 0

信息熵越小的话，表明这个数据集越纯粹

跟我们自己用眼睛的分类的一样，第二种分法 更合理 更纯粹 。所以这个公式 很神奇 吧！！

信息熵增益

最原始 没有分类的时候 的信息熵：

E(三个球) = - 1/3 * log(1/3, 2) - 2/3 * log(2/3,2) = 0.918

那么 ：

第一种分类的信息增益 我们就定义：

红黑混合的信息增益 G(红黑|黑) = E(三个球) - E(红黑|黑) = 0.918 - 1 = -0.02

第二种分类的信息增益 我们就定义：
红黑分开的信息增益 G(红|黑黑) = E(三个球) - E(红|黑黑) = 0.918 - 0 = 0.918

故增益较大的红|黑黑分组较好.

信息熵增益 越大越好。

注: 规定了 log ( 0, 2) = 0, 虽然这在数学上不成立

复杂点的实例

比如我们有以下 数据：

图形表示 这样：

那么 我们应该按哪种特征分类呢？

我们先计算 没有分类之前的 基本信息熵：

E( 4蓝| 2红) = - 4/6 * log( 4/6, 2) - 2/6 * log( 2/6, 2) = 0.918

如果第一次按形状分类：

三个蓝色 概率 ： -log(1,2） =0
0 个红色的概率： - log(0,2) 无穷小 接近0 也为0
E( 3个圆形 N1)= -log(1,2) - log(0,2) = -0 -0 =0

一个蓝色三角形和 两个红色三角形的信息熵：

E(N2) = - 2/3 * log( 2/3,2) - 1/3 * log( 1/3, 2) = 0.918

所以按 形状分类的信息熵增益：

G (形状) = E( 4蓝| 2红) - E(N2) - E(N1) = 0.918- 0.918=0

根据表情分类, 结果是这样的(请始终把焦点集中在红蓝两个颜色上):

E(N1 ) = 0

E(N2) = -1/2 * log( 1/2, 2) - 1/2 * log( 1/2, 2) = 1

信息增益 G(Shape) = 0.918 - 1 - 0 = -0.02

如果选择线条(粗细)分类, 结果是这样的(请始终把焦点集中在红蓝两个颜色上):

E(N1) = -1/2 * log( 1/2, 2) - 1/2 * log( 1/2, 2) = 1

E(N2) = -1/4 * log( 1/4, 2) - 3/4 * log( 3/4, 2) = 0.811

信息增益 G(Bold) = 0.918 - 1 - 0.811 = - 0.893

故, 首选按形状分类。

由此也可以看出，极端情况下，使用信息增益选取特征有向节点熵为0倾斜的趋势，然而这未必就是最佳选择,但是大多情况下,它工作得不错.

得到目前的结果：

N1 左边 继续分类：

基本熵 = 0

按照 苦笑 分类：
E（苦笑）=0

按照线条粗细分类也是： 0 因为都是 蓝色。

所以不用划分了。

N 2 右边的继续分类：

粗细分类：

前面计算的初始的结果是：E= 0.918
E (粗细)=-Log(0.5,2) -Log(0.5,2) =1.2
信息熵增益 G(粗细) = 0.918-1.2= -0.282

哭笑分类：

E (哭笑)=-log(1,2) -log(1,2) =0

信息熵增益 G(粗细) = 0.918-0= 0.918

所以按照 苦笑分类更合理。

最终的分类：

python 代码实现：

from math import log
import operator

def calcShannonEnt(dataSet):  # 计算数据的熵(entropy)
    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
    for key in labelCounts:
        prob=float(labelCounts[key])/numEntries # 计算单个类的熵值
        shannonEnt-=prob*log(prob,2) # 累加每个类的熵值
    return shannonEnt


def  CreateData():
    dataSet = [[1,1,1,'blue'],
                [0,1,1,'blue'],
               [0,0,1,'blue'],
               [1,1,0,'blue'],
               [0,1,0,'red'],
               [0,0,0,'red']
               ]
    lables = ['motion','Bold','Shape']

    return  dataSet,lables
def splitDataSet(dataSet,axis,value): # 按某个特征分类后的数据
    retDataSet=[]
    for featVec in dataSet:
        if featVec[axis]==value:
            reducedFeatVec =featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

def chooseBestFeatureToSplit(dataSet):  # 选择最优的分类特征
    numFeatures = len(dataSet[0])-1
    baseEntropy = calcShannonEnt(dataSet)  # 原始的熵
    bestInfoGain = 0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 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

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]

def createTree(dataSet,labels):
    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]
    myTree={bestFeatLabel:{}} #分类结果以字典形式保存
    del(labels[bestFeat])
    featValues=[example[bestFeat] for example in dataSet]
    uniqueVals=set(featValues)
    for value in uniqueVals:
        subLabels=labels[:]
        myTree[bestFeatLabel][value]=createTree(splitDataSet\
                            (dataSet,bestFeat,value),subLabels)
    return myTree


if __name__=='__main__':
    dataSet, labels=CreateData()  # 创造示列数据
    print(createTree(dataSet, labels))  # 输出决策树模型结果

参考文献

https://blog.csdn.net/u012351768/article/details/73469813
https://www.cnblogs.com/okokok/p/6117333.html
https://www.cnblogs.com/luozeng/p/8604997.html

git