继上一期说完如何选择最优划分属性的原理，这期主要说说划分数据的Python实现
1. 划分数据集
def splitDataSet (dataSet, divFeat,
value)
copyDataSet = []
for featVec
in dataSet :
if featVec[divFeat] ==
value :
reducedFeatVec[:divFeat]
reducedFeatVec.extend(featVec[divFeat+
1:])
copyDataSet.append(reducedFeatVec)
return copyDataSet
代码解释：
line 1：输入参数为 需要划分的数据集，划分特征，返回的特征值
line 2：由于Python传递的是引用而不是原数据复制，为了保证不改变原数据我扪新建立一个列表
line 3：遍历数据集中的没个元素
line 4：抽取符合的特征值
line 5：将该特征前的所有元素，除了该特征全部放入reducedFeatVec列表中（举例：a = [5,6,7,8,9] : a[:3] -> [5,6,7]）
line 6：.extend()使Python列表类型自带的方法，其与append()有相似但结果截然不同的效果（举例：a = [5,6,7] b=[8,9] : a.extend(b) -> [5,6,7,8,9]; a.append(b) -> [5,6,7, [8,9] ]） append() 会将其元素作为一个列表整体放入到a中，a的最后一个元素是一个列表，列表中包含了b中的所有元素。 同时 featVec[divFeat+1:] 意思为 将divFeat 后的所有元素都放入到reducedFeatVec 里表中，+1 的原因是不同于向前，向后是包含的该特征的（举例 a = [5,6,7,8,9] : a[3:] -> [8,9]）
line 7：将获得的reducedFeatVec 按照一个一个列表形式存入copyDataSet中
结果展示：
>>>dataSet
[ [1,1,y], [1,0,y], [1,1,n], [0,0,n], [0,1,n] ]
>>>tree.splitDataSet(dataSet,0,1)
[1,1,y], [1,0,y], [1,1,n]
2. 找到最好的划分属性
def bestFeatSplit(dataSet) :
numFeats = len(dataSet[
0]) -
1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain =
0.0; bestFeat = -
1
for i
in range(numFeats) :
featList = [featValue[i]
for featValue
in dataSet]
uniqueVals = set(featureList)
newEntropy =
0.0
for value
in uniqueVals :
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = beseEntropy - newEntropy
if (infoGain > bestEntropy) :
bestInfoGain = infoGain
bestFeat = i
return bestFeat
代码解释：
line 1：输入参数为 需要划分的数据集
line 2：计算列表所具有的特征数，-1 的原因时最后一项是类标签，不是特征属性（特别注意的是，所有的数据列表必须具有相同的数据长度，同时最后一项必须是类别标签）
line 3：通过上一期的代码计算出初始的熵
line 5：range() 是Python函数，其效果是取 0~numFeats-1 的所有值（举例：range(4) -> [0,1,2,3]），需要特别注意的是，在for之外的地方更改 i 的值不会影响到 for 循环
(举例： for i in range(3)
print i
i +=2
print i
打印结果为：0 2
1 3
2 4）
line 6：使用列表推导来创建新的列表，将数据集中所有第 i 个特征值或者所有可能存在的值写入新的列表中
line 7：set() 取集合，集合中各个值各不相同
line 9：遍历所有唯一的属性值
line 10~12：计算新的熵，原理见上一期
line 13：计算信息增益
line 14~17：找打最大的信息增益，并返回索引值
结果展示：
>>>tree.bestFeatSplit(dataSet)
0
可以看出 如果按照0划分，最后结果有一个n 被错误的分到 y 组，如果按照1划分，将有一个y被错误分到 n 组同时剩下的一组分别是一个 y 和一个 n。由此可见按照 0 划分最佳
下一期将会更新如何使用Python构建决策树
3. 参考
1.《Modern Information Retrieval The Concepts and Technology behind Search》Second Edition – Ricardo Baeza-Yates Berthier Ribeiro-Neto 2.《Machine learning in Action》 – Peter Harrington 3.《Data Mining Concepts and Techniques》 – Jiawei Han, Micheline Kamber, Jian Pei
转载请注明原文地址: https://ju.6miu.com/read-16044.html
