划分数据集

分类算法除了需要测量信息熵，还需要划分数据集，度量花费数据集的熵，以便判断当前是否正确地划分了数据集。我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。

需要注意：python语言不用考虑内存分配问题。python语言在函数中传递的是列表的引用，在函数内部对列表对象的修改，将会影响该列表对象的整个生存周期。为了消除这个不良影响，需要在函数的开始声明一个新列表对象。

#按照给定特征划分数据集
#通过遍历dataSet数据集，求出axis对应的colnum列的值为value的行
        # dataSet 数据集                 待划分的数据集
        # axis 表示每一行的axis列        划分数据集的特征
        # value 表示axis列对应的value值   需要返回的特征的值。
# dataSet数据集，axis是对应的要分割数据的列，value是要分割的列按哪个值分割，即找到含有该值的数据
def splitDataSet(dataSet,axis,value):
    # 定义要返回的数据集
    retDataSet=[]
    # 遍历数据集中的每个特征，即输入数据
    for featVec in dataSet:
        # 如果列标签对应的值为value，则将该条(行)数据加入到retDataSet中
        if featVec[axis]==value:
            # 取featVec的0-axis个数据，不包括axis，放到reducedFeatVec中
            reducedFeatVec=featVec[:axis]
            # 取featVec的axis+1到最后的数据，放到reducedFeatVec的后面
            reducedFeatVec.extend(featVec[axis+1:])
            # 将reducedFeatVec添加到分割后的数据集retDataSet中，同时reducedFeatVec，retDataSet中没有了axis列的数据
            retDataSet.append(reducedFeatVec)
    # 返回分割后的数据集
    return retDataSet

python语言列表类型自带的extend()和append()方法的区别：

a=[1,2,3]
b=[4,5,6]
a.append(b)
print(a)
a=[1,2,3]
a.extend(b)
print(a)

输出：

[1, 2, 3, [4, 5, 6]]
[1, 2, 3, 4, 5, 6]

#结果输出:
print(trees.splitDataSet(myDat,0,1))
print(trees.splitDataSet(myDat,0,0))

输出：

[[1, 'yes'], [1, 'yes'], [0, 'no']]
[[1, 'no'], [1, 'no']]

#选择最好的数据集划分方式
# 选择使分割后信息增益最大的特征，即对应的列
def chooseBestFeatureToSplit(dataSet):
    # 获取特征的数目，从0开始，dataSet[0]是一条数据
    numFeatures=len(dataSet[0])-1
    # 计算数据集当前的信息熵
    baseEntropy=calcShannonEnt(dataSet)
    # 定义最大的信息增益
    bestInfoGain=0.0
    # 定义分割后信息增益最大的特征
    bestFeature=-1
    # 遍历特征，即所有的列，计算每一列分割后的信息增益，找出信息增益最大的列
    for i in range(numFeatures):
        # 取出第i列特征赋给featLis
        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
            # 分割的最好特征列赋为i
            bestFeature=i
    # 返回分割后信息增益最大的特征列
    return bestFeature

#输出结果：
print(trees.chooseBestFeatureToSplit(myDat))

输出：

0

递归构建决策树

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

# 对类标签进行投票 ，找标签数目最多的标签
def majorityCnt(classList):
    # 定义标签元字典，key为标签，value为标签的数目
    classCount={}
    # 遍历所有标签
    for vote in classList:
        # 如果标签不在元字典对应的key中
        if vote not in classCount.keys():
            # 将标签放到字典中作为key，并将值赋为0
            classCount[vote]=0
        # 对应标签的数目加1
        classCount+=1
    # 对所有标签按数目排序
    sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    # 返回数目最多的标签
    return sortedClassCount[0][0]

#创建决策树
def createTree(dataSet,labels):
    # 将dataSet的最后一列数据(标签)取出赋给classList，classList存储的是标签列
    classList=[example[-1] for example in dataSet]
    # 判断是否所有的列的标签都一致
    if classList.count(classList[0])==len(classList):
        # 直接返回标签列的第一个数据
        return classList[0]
    # 判断dataSet是否只有一条数据
    if len(dataSet[0])==1:
        # 返回标签列数据最多的标签
        return majorityCnt(classList)
    # 选择一个使数据集分割后最大的特征列的索引
    bestFeat=chooseBestFeatureToSplit(dataSet)
    # 找到最好的标签
    bestFeatLabel=labels[bestFeat]
    # 定义决策树，key为bestFeatLabel，value为空
    myTree={bestFeatLabel:{}}
    # 删除labels[bestFeat]对应的元素
    del(labels[bestFeat])
    # 取出dataSet中bestFeat列的所有值
    featValues=[example[bestFeat] for example in dataSet]
    # 将特征对应的值放到一个集合中，使得特征列的数据具有唯一性
    uniqueVals=set(featValues)
    # 遍历uniqueVals中的值
    for value in uniqueVals:
        # 子标签subLabels为labels删除bestFeat标签后剩余的标签
        subLabels=labels[:]
        # myTree为key为bestFeatLabel时的决策树
        myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    # 返回决策树
    return myTree

#输出结果
myTree=trees.createTree(myDat,labels)
print(myTree)

输出:

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

决策树完成。