决策树

算法思想

• 从数据集中找到一个特征,这个特征在划分数据分类中起决定性作用.为了找到这个特征,就要评估每个特征,找到区分度对好的呢个特征,将数据集分开.
• 划分数据集之前,之后信息发生的变化成为信息增益.每个特征划分数据获取的信息增益,越大的,表示区分效果越好 信息增益(Information Gain)
• 熵定义为信息的期望值. 越不确定的事件的信息熵越大,因为一定的事情没有信息量 (地球绕着太阳转)

---

得了解的信息论基本概念

自信息量：一个事件（消息）本身所包含的信息量，由事件的不确定性决定的。
随机事件Xi发生概率为P(xi)，则随机事件的自信息量定义为：

自信息量计算公式

信息熵(Entropy)：随机变量自信息量I(xi)的数学期望（平均自信息量），用H（X）表示，即为熵的定义：

信息熵计算公式

动手实践

2票同意,3票不同意

同意的占40%,不同意的占60%,此时信息熵是0.970
将一个同意改为不确定的时候
{yes:2,no:3} -> {yes:1,not sure:1,no:3}
同意的占20%,不确定的占20%,不同意的占60%,此时信息熵是1.370

---

划分数据集

通过计算信息熵,可以衡量数据的无序程度
现在要计算,通过每个特征值划分后的数据集的信息熵,然后判断那个特征划分后的数据集
选取信息熵最大的特征值,这相当于让剩下是数据更具确定性

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] # 每一列的值,即一个feature所有的数据
        print featList
        uniqueVals = set(featList)
        print uniqueVals
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet,i,value)
            print "subDataSet : %s" %  subDataSet
            prob = len(subDataSet)/float(len(dataSet))
            print "prob : %f" %  prob
            print "calcShannonEnt: %f" % calcShannonEnt(subDataSet)
            newEntropy += prob * calcShannonEnt(subDataSet)
            print "new entropy : %f" % newEntropy
        infoGain = baseEntropy - newEntropy
        print "infoGain : %f" % infoGain
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

---

动手实现一遍

原始数据

Paste_Image.png

处理为属性和标签的形式

Paste_Image.png

计算该矩阵对应的基准信息熵(Base Entropy) = 0.97

算法开始

1.选取特征A

Paste_Image.png

2.选取特征B

Paste_Image.png

3.因为IG(A) = 0.42 > IG(B) = 0.17,所以对数据集最具有区分度的特征为第0个特征A.以此为依据构建决策树

Paste_Image.png

决策树最终状态

Paste_Image.png