机器学习实践之决策树算法学习

    检测数据集中的每个子项是否属于同一分类:  
          IF so return 类标签  
      
          Else  
                  寻找划分数据集的最好特征  
                  划分数据集  
                   创建分支节点  
                             for 每个划分的子集  
                                     调用函数createBranch()并增加返回结果到分支节点中  
                    return 分支节点  
                    

    def createDataSet():  
        dataSet = [[1,1,‘yes‘],  
                  [1,1,‘yes‘],  
                  [1,0,‘no‘],  
                  [0,1,‘no‘],  
                  [0,1,‘no‘]]  
        labels=[‘no surfacing‘,‘flippers‘]  
        # change to discrete values  
        return dataSet,labels  
    #信息增益  
    #计算给定数据的香农熵  
      
    def calcShannonEnt(dataSet): #the the number of unique elements and their occurance  
        numEntries = len(dataSet)  
        labelCounts = {}  
        for featVec in dataSet:  
            currentLabel=featVec[-1]  
            if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0  
            labelCounts[currentLabel] +=1  
        shannonEnt = 0.00000  
        for key in labelCounts:  
            prob = float(labelCounts[key]) /numEntries  
            shannonEnt -= prob * log(prob,2)   #log base 2  
              
        return shannonEnt  

    def splitDataSet(dataSet, index, value):  
        """splitDataSet(通过遍历dataSet数据集，求出index对应的colnum列的值为value的行) 
            就是依据index列进行分类，如果index列的数据等于 value的时候，就要将 index 划分到我们创建的新的数据集中 
        Args: 
            dataSet 数据集                 待划分的数据集 
            index 表示每一行的index列        划分数据集的特征 
            value 表示index列对应的value值   需要返回的特征的值。 
        Returns: 
            index列为value的数据集【该数据集需要排除index列】 
        """  
        retDataSet = []  
        for featVec in dataSet:   
            # index列为value的数据集【该数据集需要排除index列】  
            # 判断index列的值是否为value  
            if featVec[index] == value:  
                # chop out index used for splitting  
                # [:index]表示前index行，即若 index 为2，就是取 featVec 的前 index 行  
                reducedFeatVec = featVec[:index]  
                ‘‘‘‘‘ 
                请百度查询一下： extend和append的区别 
                list.append(object) 向列表中添加一个对象object 
                list.extend(sequence) 把一个序列seq的内容添加到列表中 
                1、使用append的时候，是将new_media看作一个对象，整体打包添加到music_media对象中。 
                2、使用extend的时候，是将new_media看作一个序列，将这个序列和music_media序列合并，并放在其后面。 
                result = [] 
                result.extend([1,2,3]) 
                print result 
                result.append([4,5,6]) 
                print result 
                result.extend([7,8,9]) 
                print result 
                结果： 
                [1, 2, 3] 
                [1, 2, 3, [4, 5, 6]] 
                [1, 2, 3, [4, 5, 6], 7, 8, 9] 
                ‘‘‘  
                reducedFeatVec.extend(featVec[index+1:])  
                # [index+1:]表示从跳过 index 的 index+1行，取接下来的数据  
                # 收集结果值 index列为value的行【该行需要排除index列】  
                retDataSet.append(reducedFeatVec)  
        return retDataSet  

    def chooseBestFeatureToSplit(dataSet):  
        """chooseBestFeatureToSplit(选择最好的特征) 
     
        Args: 
            dataSet 数据集 
        Returns: 
            bestFeature 最优的特征列 
        """  
        # 求第一行有多少列的 Feature, 最后一列是label列嘛  
        numFeatures = len(dataSet[0]) - 1  
        # 数据集的原始信息熵  
        baseEntropy = calcShannonEnt(dataSet)  
        # 最优的信息增益值, 和最优的Featurn编号  
        bestInfoGain, bestFeature = 0.0, -1  
        # iterate over all the features  
        for i in range(numFeatures):  
            # create a list of all the examples of this feature  
            # 获取对应的feature下的所有数据  
            featList = [example[i] for example in dataSet]  
            # get a set of unique values  
            # 获取剔重后的集合，使用set对list数据进行去重  
            uniqueVals = set(featList)  
            # 创建一个临时的信息熵  
            newEntropy = 0.0  
            # 遍历某一列的value集合，计算该列的信息熵   
            # 遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和。  
            for value in uniqueVals:  
                subDataSet = splitDataSet(dataSet, i, value)  
                # 计算概率  
                prob = len(subDataSet)/float(len(dataSet))  
                # 计算信息熵  
                newEntropy += prob * calcShannonEnt(subDataSet)  
            # gain[信息增益]: 划分数据集前后的信息变化， 获取信息熵最大的值  
            # 信息增益是熵的减少或者是数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。  
            infoGain = baseEntropy - newEntropy  
            print ‘infoGain=‘, infoGain, ‘bestFeature=‘, i, baseEntropy, newEntropy  
            if (infoGain > bestInfoGain):  
                bestInfoGain = infoGain  
                bestFeature = i  
        return bestFeature  

    def createTree(dataSet, labels):  
        classList = [example[-1] for example in dataSet]  
        # 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行  
        # 第一个停止条件：所有的类标签完全相同，则直接返回该类标签。  
        # count() 函数是统计括号中的值在list中出现的次数  
        if classList.count(classList[0]) == len(classList):  
            return classList[0]  
        # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果  
        # 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。  
        if len(dataSet[0]) == 1:  
            return majorityCnt(classList)  
      
        # 选择最优的列，得到最优列对应的label含义  
        bestFeat = chooseBestFeatureToSplit(dataSet)  
        # 获取label的名称  
        bestFeatLabel = labels[bestFeat]  
        # 初始化myTree  
        myTree = {bestFeatLabel: {}}  
        # 注：labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改  
        # 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示‘no surfacing‘ is not in list  
        del(labels[bestFeat])  
        # 取出最优列，然后它的branch做分类  
        featValues = [example[bestFeat] for example in dataSet]  
        uniqueVals = set(featValues)  
        for value in uniqueVals:  
            # 求出剩余的标签label  
            subLabels = labels[:]  
            # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()  
            myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)  
            # print ‘myTree‘, value, myTree  
        return myTree  

    def classify(inputTree, featLabels, testVec):  
        """classify(给输入的节点，进行分类) 
     
        Args: 
            inputTree  决策树模型 
            featLabels Feature标签对应的名称 
            testVec    测试输入的数据 
        Returns: 
            classLabel 分类的结果值，需要映射label才能知道名称 
        """  
        # 获取tree的根节点对于的key值  
        firstStr = inputTree.keys()[0]  
        # 通过key得到根节点对应的value  
        secondDict = inputTree[firstStr]  
        # 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类  
        featIndex = featLabels.index(firstStr)  
        # 测试数据，找到根节点对应的label位置，也就知道从输入的数据的第几位来开始分类  
        key = testVec[featIndex]  
        valueOfFeat = secondDict[key]  
        print ‘+++‘, firstStr, ‘xxx‘, secondDict, ‘---‘, key, ‘>>>‘, valueOfFeat  
        # 判断分枝是否结束: 判断valueOfFeat是否是dict类型  
        if isinstance(valueOfFeat, dict):  
            classLabel = classify(valueOfFeat, featLabels, testVec)  
        else:  
            classLabel = valueOfFeat  
        return classLabel  

young   myope   no  reduced no lenses  
pre myope   no  reduced no lenses  
presbyopic  myope   no  reduced no lenses 

    lecses = [inst.strip().split(‘	‘) for inst in fr.readlines()]  
    lensesLabels = [‘age‘, ‘prescript‘, ‘astigmatic‘, ‘tearRate‘]  

treePlotter.createPlot(lensesTree)  

    >>> lensesTree = trees.createTree(lenses, lensesLabels)  
    >>> lensesTree  

    {‘tearRate‘: {‘reduced‘: ‘no lenses‘, ‘normal‘: {‘astigmatic‘:{‘yes‘:  
    {‘prescript‘:{‘hyper‘:{‘age‘:{‘pre‘:‘no lenses‘, ‘presbyopic‘:  
    ‘no lenses‘, ‘young‘:‘hard‘}}, ‘myope‘:‘hard‘}}, ‘no‘:{‘age‘:{‘pre‘:  
    ‘soft‘, ‘presbyopic‘:{‘prescript‘: {‘hyper‘:‘soft‘, ‘myope‘:  
    ‘no lenses‘}}, ‘young‘:‘soft‘}}}}}