划分数据集
分类算法除了需要测量信息熵，还需要划分数据集，度量花费数据集的熵，以便判断当前是否正确地划分了数据集。我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。
需要注意：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'}}}}
决策树完成。
网友评论