内容

1. 信息增益

2. 划分数据集

2.1 按照给定特征划分数据集

2.2 选择最好的数据集划分方式

3. 递归构建决策树

3.1 多数表决的方法

3.2 创建树

1. 信息增益

数据集划分前后的信息变化称为信息增益，获取信息增益最高的特征是最佳选择。聚合信息的度量称为香农熵或简称熵。

此代码的函数公式计算给定数据集的熵：

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)  # 以2为底求对数
    return shannonent

我们可以利用creatdataset（）函数得到简单鱼鉴定数据集：

def creatdataset():
    dataset = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataset, labels

查看数据集：

mydata, labels = creatdataset()
print("mydata:", mydata)
print("labels:", labels)
print("香农熵：", calcshannonent(mydata))

输出结果：

熵越高，则混合数据也越多，这里我们增加第三个名为maybe的分类，测试熵的变化：

mydata[0][-1] = 'maybe'
print("mydata:", mydata)
print("香农熵：", calcshannonent(mydata))

输出结果：

2. 划分数据集

2.1 按照给定特征划分数据集

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

查看划分结果：

mydata, labels = creatdataset()
print(mydata)
print(splitdataset(mydata, 0, 1))
print(splitdataset(mydata, 0, 0))

输出结果：

2.2 选择最好的数据集划分方式

接下来我们将遍历整个数据集，循环计算香农熵和splitdataset（）函数，找到最好的特征划分方式。

def choosebestfeaturetosplit(dataset):
    numfeatures = len(dataset[0])-1
    bestentropy = calcshannonent(dataset)  # 计算整个数据集的原始香农熵
    bestinfogain = 0.0; bestfeature = -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 = bestentropy - newentropy  # 信息增益
        if (infogain > bestinfogain) :
            bestinfogain = infogain
            bestfeature = i
    return bestfeature  # 返回最好特征划分的索引值

查看分区数据集的最佳功能：

mydata, labels = creatdataset()
print("choose best feature to split:", choosebestfeaturetosplit(mydata))

输出结果：

可知第0个特征是最好的用于划分数据集的特征

3. 递归构建决策树

3.1 多数表决的方法

如果数据集已经处理了所有属性，但类标签仍然不唯一，这种情况下，我们通常使用多数票来确定叶子节点的分类

import operator
def majoritycnt(classlist):
    classcount = {}
    for vote in classlist:
        if vote not in classcount.keys(): classcount[vote] = 0
        classcount[vote] += 1
    sortedclasscount = sorted(classcount.iteritems(),\
                              key = operator.itemgetter(1), reverse=True)
    return sortedclasscount[0][0]

3.2 创建树

def createtree(dataset, labels):
    classlist = [example[-1] for example in dataset]  # classlist中包含数据集的所有类标签
    if classlist.count(classlist[0]) == len(classlist):
        return classlist[0]  # 递归的第一个停止条件是所有类标签完全相同，直接返回该类标签
    if len(dataset[0]) == 1:  # 递归的第二个停止条件是使用完了所有特征，仍不能将数据集划分为仅包含唯一类别的分组
        return majoritycnt(classlist)  # 返回挑选次数最多的类别
    bestfeat = choosebestfeaturetosplit(dataset)  # 当前数据集选取的最好特征存储在变量bestfeat中
    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

查看树结构信息：

mydata, labels = creatdataset()
mytree = createtree(mydata, labels)
print("my tree:", mytree)

输出结果：