机器学习决策树的Python实现详细流程及原理解读

Alairi70ikx79r 2017-12-10

展开全文

继上一期说完如何选择最优划分属性的原理，这期主要说说划分数据的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 copyDataSet1
2
3
4
5
6
7
8

代码解释： 
        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 bestFeat1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

代码解释：
        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