【Python机器学习】决策树的构造——划分数据集

分类算法除了需要测量信息熵，还需要划分数据集，度量划分数据集的熵，以便判断当前是否正确划分了数据集。

我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。

想象一个分部在二维空间的数据散点图，需要再数据之间画条线，将他们分成两部分。

按照给定的特征划分数据集：

def splitDataSet(dataSet,axis,value):#创建新的list对象reDataSet=[]for featVec in dataSet:if featVec[axis]==value:#抽取数据resuceFeatVec=featVec[:axis]resuceFeatVec.extend(featVec[axis+1:])reDataSet.append(resuceFeatVec)return reDataSet

上述代码有3个输入参数：待划分的数据集、划分数据集的特征、需要返回的特征的值。

需要注意的是，Python语言不用考虑内存分配的问题。Python语言在函数中传递的是列表的引用，在函数内部对列表的修改，将会影响该列表对象的整个生存周期。

为了消除这一不良影响，我们需要在函数的开始声明一个新列表对象。因为该函数代码在同一数据集上被调用多次，为了不修改原始数据集，创建一个新的列表对象；数据集这个列表中的各个元素也是列表，我们要遍历数据集中的每个元素，一旦发现符合要求的值，则将其添加到新创建的列表中。在if语句中，程序将符合特征的数据抽取出来。

代码中使用了Python自带的extend()和append()方法。

利用鱼类分类数据进行测试

myDat,labels=createDataSet()
print(splitDataSet(myDat,0,1))
print(splitDataSet(myDat,0,0))

接下来，遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。熵计算将会告诉我们如何划分数据集是最好的数据组织方式。

def chooseBestFeatureToSplit(dataSet):numFeatures=len(dataSet[0])-1baseEntropy=calcShannonEnt(dataSet)bestInfoGain=0.0bestFeature=-1for i in range(numFeatures):featList=[example[i] for example in dataSet]uniqueVals=set(featList)newEntropy=0.0for value in uniqueVals:subDataSet=splitDataSet(dataSet,i,value)prod=len(subDataSet)/float(len(dataSet))newEntropy=newEntropy+prod*calcShannonEnt(subDataSet)infoGain=baseEntropy-newEntropyif (infoGain>bestInfoGain):bestInfoGain=infoGainbestFeature=ireturn bestFeature

上述代码实现了选取特征、划分数据集、计算得出最好的划分数据集特征。

在函数chooseBestFeatureToSplit()使用了calcShannonEnt()、splitDataSet()，在函数中调用的数据需要满足一定的要求：第一个要求是，数据必须是一种由列表元素组成的列表，而且所有的列表元素都要具有相同的长度；第二个要求是，数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签。数据集一旦满足上述要求，我们就可以在函数的第一行判定当前数据集包含多少特征属性。我们无需限定list中的数据类型，它们既可以是数字也可以是字符串，并不影响计算。

在开始划分数据集之前，chooseBestFeatureToSplit()函数的第2行代码计算了整个数据集的原始香农熵，我们保存最初的无需度量值，用于与划分完之后的数据集计算的熵值进行比较。第1个for循环遍历数据集中的所有特征。使用列表推导来创建新的列表，将数据集中的所有第i个特征值或者所有可能存在的值写入这个新list中。然后使用Python原生的集合（set）数据类型。集合数据类型与列表类型相似，不同之处仅在于集合类型中的每个值互不相同。从列表中创建集合是Python语言得到列表中唯一元素值的最快方法。

遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，然后计算数据集的新熵值，并对所有唯一特征值得到的熵求和。信息增益是熵的减少或者数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。

现在，测试代码：

myDat,labels=createDataSet()
print(chooseBestFeatureToSplit(myDat))
print(myDat)

结果告诉我们，第0个特征是最好的用于花粉数据集的特征。