背景介绍：根据患者眼部状况的观察条件，利用决策树来向患者推荐隐形眼镜的类型。

1. 收集数据

数据集来自于UCI数据库的隐形眼镜数据集。

数据格式

2. 准备数据

解析tab键分割的数据行。

def read2DataSet(filename):

    fr= open(filename,'r')

    dataSet= [example.strip().split('\t') for example in fr.readlines()]

    lenseLabels= ['age','prescript','astigmatric','tearRate']#特征名称

    return dataSet, lenseLabels

3. 分析数据

快速检查数据，确保正确地解析数据内容，绘制最后的决策树型图。

4. 训练算法-生成决策树

思想（伪代码）：

检测数据集中的每个子项是否属于同一分类：

    If    so    return    类标签

    Else

            寻找划分数据集的最好特征（--基于信息增益）

            划分数据集

            创建分支结点

                    for    每个划分的子集

                            调用自己，并增加返回结果到分支结点中

            return    分支结点

4.1 划分数据

def splitDataSet(dataSet, axis, value):

    """

    对数据集进行划分

    :param dataSet:数据集

    :param axis: 选择的特征，在该特征上对数据集进行划分;

    :param value: 特征的取值；划分依据（这种划分是多分支划分，依赖于每个标称属性的取值个数）

    :return: 划分后的子集（删除特征axis后的数据集）；；方便进行下一次划分；；递归执行"""

    retDataSet= []

    for featVecin dataSet:

        if featVec[axis] == value:

            reducedFeatVec= featVec[:axis]

            reducedFeatVec.extend(featVec[axis+1:])

            retDataSet.append(reducedFeatVec)

    return retDataSet

4.2 选取最佳的划分方式

标准是 信息增益（Information Gain）：

计算公式

香农熵：

香农熵计算公式

香农熵计算实现：

def calcShannonEnt(dataSet):

    numEntries= len(dataSet)

    labelCounts= {}

    for featVecin dataSet:

        currentLabel= featVec[-1]

        labelCounts[currentLabel] = labelCounts.get(currentLabel,0) + 1

    shannonEnt= 0.0

    for key in labelCounts:

        prob= labelCounts[key]/float(numEntries)

        shannonEnt-= prob*log(prob,2)

    return shannonEnt

以信息增益为评价指标，选出最佳的划分方式（穷举）：

def chooseBestFeatureToSplit(dataSet):

    numFeatures= len(dataSet[0]) - 1#dataSet 数据格式：每一行最后为类标签

    baseEntropy= calcShannonEnt(dataSet)

    bestInfoGain= 0.0; bestFeature= -1

    for i in range(numFeatures):

        featList= [example[i] for examplein 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

            bestFeature= i

    return bestFeature

4.3 生成决策树

决策树的生成过程是一个递归的过程。那么，必须有终止条件，才能结束运行。

终止条件：

（1）结点中所有实例都是一个类别；

（2）结点中没有可供选择的特征（即，属性已经遍历完）；此时，依据多数表决原则，返回该节点的分类标签。

针对情况二，多数表决函数：

def majorityCnt(classList):

    classCnt= {}

    for vote in classList:

        classCnt[vote] = classCnt.get(vote,0) + 1

    sortedClassCount= sorted(classCnt.items(),key=lambda a:a[1],reverse=True)

    return sortedClassCount[0][0]

千呼万唤始出来，重头戏---生成决策树：

def createTree(dataSet, labels):

    classList= [example[-1] for examplein dataSet]

    if classList.count(classList[0]) == len(classList):#结束条件1：结点中所有实例都是一个类别；

        return classList[0]

    if len(dataSet[0]) == 1:#结束条件2：结点中没有特征，只剩下类别标签---多数表决

        return majorityCnt(classList)

    bestFeat= chooseBestFeatureToSplit(dataSet)

    bestFeatLabel= labels[bestFeat]#特征的名称，eg：工资、性别等等----中间结点，进行判断

    myTree= {bestFeatLabel:{}}#对子节点进行划分

    del labels[bestFeat]#针对选定的特征--取不同的值，进行划分

    featValues= [example[bestFeat] for example in dataSet]

    uniqueValues= set(featValues)

    for value in uniqueValues:

        subLabels= labels[:]

        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)

    return myTree

生成的决策树，结果如下：

决策树

为了更加形象直观，使用matplotlib工具画图。决策树的形状如下：

隐形眼镜决策树

5. 测试算法

编写测试函数可以验证决策树可以正确分类给定的数据实例。

6. 使用算法

def classify(inputTree, featLabels, testVec):

    firstStr= inputTree.keys()[0]

    secondDict= inputTree[firstStr]

    featIndex= featLabels.index(firstStr)

    for key in secondDict.keys():

        if testVec[featIndex] == key:

            if is instance(secondDict[key],dict):

                classLabel= classify(secondDict[key],featLabels,testVec)

            else:

                classLabel= secondDict[key]

    return classLabel

比如：一个测试用例：pre + myope + no + normal = soft

调用函数

输出结果为：

运行结果

7. 后续

为了方便下次使用，而不必重新生成决策树，我们使用pickle来进行保存。

def storeTree(inputTree, filename):

    import pickle

    fw= open(filename,'w')

    pickle.dump(inputTree,fw)

    fw.close()

下次读取时，使用：

def grabTree(filename):

    import pickle

    fr= open(filename)

    return pickle.load(fr)

其中：

pickle：

The pickle module implements a fundamental, but powerful algorithm for serializing and de-serializing a Python object structure. 该模块实现对python 数据对象的序列化和反序列化（保存和读取）。

pickle.dump(obj, file[, protocol])

Write a pickled representation of obj to the open file object file. 将python数据对象写到文件中；即保存。

pickle.load(file)

Read a string from the open file object file and interpret it as a pickle data stream, reconstructing and returning the original object hierarchy.从文件中读取信息，反序列化形成原来的数据对象，并返回。

8. 小结

决策树

优点：计算复杂度不高。输出结果易于理解，对中间值缺失不敏感；能方便理解数据中所蕴含的知识信息。

缺点：可能会过度匹配（overfitting）--剪枝；提前停止

适用数据类型：数值型和标称型。