决策树（四）选取最佳特征划分数据集

我们的目的已经很明确了，就是依次遍历每一个特征，在这里我们的特征只有两个，就是需不需要浮出水面，有没有脚蹼。然后计算出根据每一个特征划分产生的数据集的熵，和初始的数据集的熵比较，我们找出和初始数据集差距最大的。那么这个特征就是我们划分时最合适的分类特征。

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0])-1 # 获取我们样本集中的某一个样本的特征数（因为每一个样本的特征数是相同的，相当于这个代码就是我们可以作为分类依据的所有特征个数）我们的样本最后一列是样本所属的类别，所以要减去类别信息，在我们的例子中特征数就是2
    baseEntropy = calcShannonEnt(dataSet) #计算样本的初始香农熵
    bestInfoGain =0.0 #初始化最大信息增益
    bestFeature = -1 #和最佳划分特征

    for i in range(numFeatures): # range（2）那么i的取值就是0,1。 在这里i表示的我们的第几个特征
        featList = [sample[i] for sample in dataSet]
        # 我们首先遍历整个数据集，首先得到第一个特征值可能的取值，然后把它赋值给一个链表，我们第一个特征值取值是[1,1,1,0,0],其实只有【1,0】两个取值
        uniqueVals = set(featList)#我们使用集合这个数据类型删除多余重复的原始使得其中只有唯一的值。
        #执行的结果如下所示：
        
        In [8]: featList=[1,1,1,0,0]

        In [9]: uniqueVals=set(featList)

        In [10]: uniqueVals
        Out[10]: {0, 1}

        
        newEntropy = 0.0
        for value in uniqueVals: #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