决策树实例——预测隐形眼睛类型

眼科医生是如何判断患者需要佩戴隐形眼镜的类型的？隐形眼镜数据集一共有24组数据，数据的Labels依次是age、 prescript、 astigmatic、 tearRate、 class, 也就是第一列是年龄，第二列是症状，第三列是是否散光，第四列是眼泪数量，第五列是最终的分类标签。隐形眼镜分类标签包括硬材质(hard)、软材质(soft)以及不适合佩戴隐形眼镜(no lenses)。如下表所示：

age	prescript	astigmatic	tearRate	class
young	myope	no	reduced	no lenses
young	myope	no	normal	soft
young	myope	yes	reduced	no lenses
young	myope	yes	normal	hard
young	hyper	no	reduced	no lenses
young	hyper	no	normal	soft
young	hyper	yes	reduced	no lenses
young	hyper	yes	normal	hard
pre	myope	no	reduced	no lenses
pre	myope	no	normal	soft
pre	myope	yes	reduced	no lenses
pre	myope	yes	normal	hard
pre	hyper	no	reduced	no lenses
pre	hyper	no	normal	soft
pre	hyper	yes	reduced	no lenses
pre	hyper	yes	normal	no lenses
presbyopic	myope	no	reduced	no lenses
presbyopic	myope	no	normal	no lenses
presbyopic	myope	yes	reduced	no lenses
presbyopic	myope	yes	normal	hard
presbyopic	hyper	no	reduced	no lenses
presbyopic	hyper	no	normal	soft
presbyopic	hyper	yes	reduced	no lenses
presbyopic	hyper	yes	normal	no lenses

示例：使用决策树预测隐形眼镜类型

收集数据：读入提供的文本文件数据。
分析数据：快速检查数据，确保正确地解析数据内容。
训练算法：使用理论文章的createTree()函数。
测试算法：编写测试函数验证决策树可以正确分类给定的数据实例。
使用算法：存储树的数据结构，以便下次使用时无需重新构造树。

收集数据：从文本文件中读入

对于一个csv文件，可以使用pandas的read_csv()函数将数据读入。

函数说明：从csv中读入数据，并且初始化特征标签。


def createDataSet():
    data = pd.read_csv('lenses.csv')
    dataSet = data.iloc[:, :].values.tolist()
    labels = ['age', ' prescript', ' astigmatic', 'tearRate']
    return dataSet, labels

做出以上处理后，大致的结果如下：

Parameters:
无
Returns:
dataSet – 数据集
labels – 分类属性

计算给定数据集的香农熵

首先，计算数据集中实例的总数。我们也可以在需要时再计算这个值，但是由于代码中多次用到这个值，为了提高代码效率，我们显式地声明个变量保存实例总数。然后，创建一个数据字典，它的键值是最后一列的数值。如果当前键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。最后，使用所有类标签的发生频率计算类别出现的概率。我们将用这个概率计算香农熵,统计所有类标签发生的次数。

函数说明：计算给定数据集的经验熵(香农熵)


def calcShannonEnt(dataSet):
    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.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

Parameters:
dataSet – 数据集
Returns:
shannonEnt – 经验熵(香农熵)

按照给定特征划分数据集

创建splitDataSet(dataSet, axis, value)函数来按照给定特征划分数据。splitDataSet函数是用来选择各个特征的子集的，比如选择年龄(第0个特征)的青年(用0代表)的子集，我们可以调用splitDataSet(dataSet,0,0)这样返回的子集就是年龄为青年的5个数据集。需要注意的是，Python语言不用考虑内存分配问题。Python语言在函数中传递的是列表的引用，在函数内部对列表对象的修改，将会影响该列表对象的整个生存周期。为了消除这个不良影响，我们需要在函数的开始声明一个新列表对象。因为该函数代码在同一数据集上被调用多次，为了不修改原始数据集，创建一个新的列表对象。数据集这个列表中的各个元素也是列表，我们要遍历数据集中的每个元素，一旦发现符合要求的值，则将其添加到新创建的列表中。在if语句中，程序将符合特征的数据抽取出来。


def splitDataSet(dataSet, axis, value):
    retDataSet= []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

Parameters:
dataSet – 待划分的数据集
axis – 划分数据集的特征
value – 需要返回的特征的值
Returns:
retDataSet – 划分后的数据集

选择最优特征

在开始划分数据集之前，第3行代码计算了整个数据集的原始香农嫡，我们保存最初的无序度量值，用于与划分完之后的数据集计算的熵值进行比较。第1个for循环遍历数据集中的所有特征。使用列表推导( List Comprehension )来创建新的列表，将数据集中所有第i个特征值或者所有可能存在的值写人这个新list中。然后使用Python语言原生的集合( set )数据类型。集合数据类型与列表类型相似，不同之处仅在于集合类型中的每个值互不相同。从列表中创建集合是Python语言得到列表中唯一元素值的最快方法。

遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，然后计算数据集的新熵值，并对所有唯一特征值得到的熵求和。信息增益是熵的减少或者是数据无序度的减少，大家肯定对于将熵用于度量数据无序度的减少更容易理解。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。


def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        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
            bestFeature = i
    return bestFeature

Parameters:
dataSet – 数据集
Returns:
bestFeature – 信息增益最大的(最优)特征的索引值

构造决策树

目前我们已经知道了从数据集构造決策树算法所需要的子功能模块。其工作原理如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。

majorityCut()函数使用分类名称的列表，然后创建键值为classList中唯一值的数据字典，字典对象存储了classList中每个类标签出现的频率，最后利用operator操作键值排序字典，并返回出现次数最多的分类名称。


def majorityCut(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
            classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(),
                              key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

下一步程序开始创建树，这里使用Python语言的字典类型存储树的信息，当然也可以声明特殊的数据类型存储树，但是这里完全没有必要。当前数据集选取的最好特征存储在变量bestFeat中，得到列表包含的所有属性值。

最后代码遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()，得到的返回值将被插人到字典变量myTree中，因此函数终止执行时，字典中将会嵌套很多代表叶子节点信息的字典数据。在解释这个嵌套数据之前，我们先看一下循环第一行的subLabels = labels.copy()，这行代码复制了类标签，并将其存储在新列表变量subLabels中。为了保证每次调用函数createTree ()时不改变原始列表的内容，使用新变量subLabels代替原始列表。


def createTree(dataSet, labels, featLables):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    if len(labels) == 0:
        return majorityCut(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLable = labels[bestFeat]
    featLables.append(bestFeatLable)
    myTree = {bestFeatLable: {}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels.copy()
        myTree[bestFeatLable][value] = createTree(splitDataSet
                        (dataSet, bestFeat, value),subLabels, featLables)
    return myTree

做出以上处理后，大致的结果如下：

至此，我们已经成功地构造了一棵决策树。

使用决策树执行分类

靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要使用决策树以及用于构造决策树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进人叶子节点；最后将测试数据定义为叶子节点所属的类型。


def classify(inputTree, featLabels, testVec):
    firstStr = next(iter(inputTree))
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    classLabel = ''
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]).__name__ == 'dict':
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:
                classLabel = secondDict[key]
    return classLabel

Parameters:
inputTree – 已经生成的决策树
featLabels – 存储选择的最优特征标签
testVec – 测试数据列表，顺序对应最优特征标签
Returns:
classLabel – 分类结果

输入以下代码：


dataSet, labels = createDataSet()
featLabels = []
myTree = createTree(dataSet, labels, featLabels)
testVec = ['presbyopic', 'myope', 'yes', 'normal']
labels = ['age', ' prescript', ' astigmatic', 'tearRate']
classLabel = classify(myTree, labels, testVec)
print(classLabel)

做出以上处理后，大致的结果如下：

写在最后

至此，我们完成了构造决策树和使用决策树执行分类的基本完整步骤，我们可以从控制台很清晰的看到我们构造的决策树，另外，将在下一篇文章中列出绘制决策树的代码。

人工智能分类器算法