机器学习实战：k-近邻算法和决策树

- 日理万妓 2023-06-12 11:29 60阅读 0赞

# 机器学习实战 #

### 文章目录 ###

*  机器学习实战
 *   *  一、k-近邻算法
     *   *  1、kNN 概述
         *  2、KNN 原理
         *   *  工作原理
             *  开发流程
             *  算法特点
         *  3、KNN 项目案例
         *   *  项目案例1: 优化约会网站的配对效果
             *  项目案例2: 手写数字识别系统
         *  4、KNN 小结
     *  二、决策树
     *   *  1、决策树 概述
         *  2、决策树 原理
         *   *  须知概念
             *  工作原理
             *  开发流程
             *  算法特点
         *  3、决策树 项目案例
         *   *  项目案例1: 判定鱼类和非鱼类
             *  项目案例2: 使用决策树预测隐形眼镜类型
         *  4、决策树 小结
     *  三、使用 Matplotlib 注解绘制树形图
 *  资料来源

## 一、k-近邻算法 ##

刚开始机器学习，对于刚学完Python没多久的我稍有些难，但也不是问题，边学边实战，效果更好=。=

### 1、kNN 概述 ###

**k-近邻（kNN, k-NearestNeighbor）算法**是一种基本分类与回归方法，这里只讨论分类问题中的 k-近邻算法。

**简单来说**： 通过距离度量来计算查询点（query point）与每个训练数据点的距离，然后选出与查询点（query point）相近的K个最邻点（K nearest neighbors），使用分类决策来选出对应的标签来作为该查询点的标签。

k 近邻算法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 k值的选择、距离度量以及分类决策规则是k近邻算法的**三个基本要素**。

### 2、KNN 原理 ###

#### 工作原理 ####

*  假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
 *  输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。  
    a.计算新数据与样本数据集中每条数据的距离。  
    b.对求得的所有距离进行排序（从小到大，越小表示越相似）。  
    c.取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
 *  求 k 个数据中出现次数最多的分类标签作为新数据的分类。

#### 开发流程 ####

> 1.  收集数据：任何方法
> 2.  准备数据：距离计算所需要的数值，最好是结构化的数据格式
> 3.  分析数据：任何方法
> 4.  训练算法：此步骤不适用于 k-近邻算法
> 5.  测试算法：计算错误率
> 6.  使用算法：输入样本数据和结构化的输出结果，然后运行 k-近邻算法判断输入数据分类属于哪个分类，最后对计算出的分类执行后续处理

#### 算法特点 ####

>  *  优点：精度高、对异常值不敏感、无数据输入假定
>  *  缺点：计算复杂度高、空间复杂度高
>  *  适用数据范围：数值型和标称型

### 3、KNN 项目案例 ###

完整代码地址：[https://blog.csdn.net/qq\_45556599/article/details/103111984][https_blog.csdn.net_qq_45556599_article_details_103111984]

#### 项目案例1: 优化约会网站的配对效果 ####

**项目概述**  
海伦使用约会网站寻找约会对象。经过一段时间之后，她发现曾交往过三种类型的人:

*  不喜欢的人
 *  魅力一般的人
 *  极具魅力的人

她希望：

1.  工作日与魅力一般的人约会
2.  周末与极具魅力的人约会
3.  不喜欢的人则直接排除掉

现在她收集到了一些约会网站未曾记录的数据信息，这更有助于匹配对象的归类。

**开发流程**

>  *  收集数据：提供文本文件 准备数据：使用 Python 解析文本文件 分析数据：使用 Matplotlib 画二维散点图
>  *  训练算法：此步骤不适用于 k-近邻算法
>  *  测试算法：使用海伦提供的部分数据作为测试样本。  
>     测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
>  *  使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

*收集数据：提供文本文件*

海伦把这些约会对象的数据存放在文本文件 datingTestSet2.txt 中，总共有 1000 行。海伦约会的对象主要包含以下 3 种特征：

*  每年获得的飞行常客里程数
 *  玩视频游戏所耗时间百分比
 *  每周消费的冰淇淋公升数

文本文件数据格式如下：  
![在这里插入图片描述][20191113192836926.png]  
***准备数据：使用 Python 解析文本文件***  
将文本记录转换为 NumPy 的解析程序

def file2matrix(filename):
        """
        Desc:
            导入训练数据
        :param filename:数据文件路径
        :return: 数据矩阵 returnMat 和对应的类别 classLabelVector
        """
    
        fr = open(filename)
        # 获得文件中的数据行的行数
        numberOfLines = len(fr.readlines())
        # 生成对应的空矩阵
        returnMat = zeros((numberOfLines, 3))
        classLabelVector = []
        fr = open(filename)
        index = 0
        for line in fr.readlines():
            line = line.strip()
            listFromLine = line.split('\t')
            # 每列的属性数据
            returnMat[index, :] = listFromLine[0:3]
            # 每列的类别数据，就是 label 标签数据
            classLabelVector.append(int(listFromLine[-1]))
            index += 1
        # 返回数据矩阵returnMat和对应的类别classLabelVector
        return returnMat, classLabelVector

***分析数据：使用 Matplotlib 画二维散点图***

import matplotlib
    import matplotlib.pyplot as plt
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(datingDataMat[:, 0], datingDataMat[:, 1], 15.0*array(datingLabels), 15.0*array(datingLabels))
    plt.show()

下图中采用矩阵的第一和第二列属性得到很好的展示效果，清晰地标识了三个不同的样本分类区域，具有不同爱好的人其类别区域也不同。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]  
***准备数据：归一化数值***

归一化定义：消除特征之间量级不同导致的影响，归一化就是要把你需要处理的数据经过处理后（通过某种算法）限制在你需要的一定范围内。首先归一化是为了后面数据处理的方便，其次是保正程序运行时收敛加快。

本次采用的方法：  
线性函数转换，表达式如下：

y=(x-MinValue)/(MaxValue-MinValue)

说明：x、y分别为转换前、后的值，MaxValue、MinValue分别为样本的最大值和最小值。

在统计学中，归一化的具体作用是归纳统一样本的统计分布性。归一化在0-1之间是统计的概率分布，归一化在-1–+1之间是统计的坐标分布。

def autoNorm(dataSet):
        """
        归一化特征值，消除属性之间量级不同导致的影响
        :param dataSet: 数据集
        :return: 归一化后的数据集normDataSet,ranges 和 minVals即范围与最小值（没有用到）
    
        归一化公式：
            Y = (X-Xmin)/(Xmax-Xmin)
            其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。
        """
    
        # 计算每种属性的最大值、最小值、范围
        minVals = dataSet.min(0)
        maxVals = dataSet.max(0)
        # 极差
        ranges = maxVals - minVals
        normDataSet = zeros(shape(dataSet))
        m = dataSet.shape[0]
        # 生成与最小值之差组成的矩阵
        normDataSet = dataSet - tile(minVals, (m, 1))
        # 将最小值之差除以范围组成矩阵
        normDataSet = normDataSet / tile(ranges, (m, 1))
        return normDataSet, ranges, minVals

***训练算法：此步骤不适用于 k-近邻算法***

kNN 算法伪代码：

对于每一个在数据集中的数据点：
        计算目标的数据点（需要分类的数据点）与该数据点的距离
        将距离排序：从小到大
        选取前K个最短距离
        选取这K个中最多的分类类别
        返回该类别来作为目标数据点的预测值

def classify0(inX, dataSet, labels, k):
        """
           inX: 用于分类的输入向量
           dataSet: 输入的训练样本集
           labels: 标签向量
           k: 选择最近邻居的数目
           注意：labels元素数目和dataSet行数相同；程序使用欧式距离公式.
           预测数据所在分类可在输入下列命令
           kNN.classify0([0,0], group, labels, 3)
        """
    
        dataSetSize = dataSet.shape[0]
        # 距离度量 度量公式为欧氏距离
        diffMat = tile(inX, (dataSetSize, 1)) - dataSet
        sqDiffMat = diffMat ** 2  # 取平方
        sqDistances = sqDiffMat.sum(axis=1)  # 将矩阵的每一行相加
        distances = sqDistances ** 0.5  # 开方
        # 将距离排序：从小到大
        # argsort() 是将x中的元素从小到大排列，提取其对应的index（索引），然后输出到y。
        # 例如：y=array([3,0,2,1,4,5]) 则，x[3]=-1最小，所以y[0]=3;x[5]=9最大，所以y[5]=5。
        sortedDistIndicies = distances.argsort()
        # 选取前K个最短距离， 选取这K个中最多的分类类别
        classCount = {
        }
        for i in range(k):
            voteIlabel = labels[sortedDistIndicies[i]]
            classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        return sortedClassCount[0][0]

***测试算法：使用海伦提供的部分数据作为测试样本。如果预测分类与实际类别不同，则标记为一个错误。***

kNN 分类器针对约会网站的测试代码

def datingClassTest():
        """
        对约会网站的测试方法
        :return: 错误数
        """
    
        # 设置测试数据的的一个比例（训练数据集比例=1-hoRatio）
        hoRatio = 0.1  # 测试范围,一部分测试一部分作为样本
        # 从文件中加载数据
        datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')  # load data setfrom file
        # 归一化数据
        normMat, ranges, minVals = autoNorm(datingDataMat)
        # m 表示数据的行数，即矩阵的第一维
        m = normMat.shape[0]
        # 设置测试的样本数量， numTestVecs:m表示训练样本的数量
        numTestVecs = int(m * hoRatio)
        print('numTestVecs=', numTestVecs)
        errorCount = 0.0
        for i in range(numTestVecs):
            # 对数据测试
            classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
            print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
            if classifierResult != datingLabels[i]:
                errorCount += 1.0
        print("the total error rate is: %0.3f" % (errorCount / float(numTestVecs)))
        print("the total number of errors is: %0.1f" % errorCount)

![在这里插入图片描述][20191113195637223.png]  
***使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。***

def classifyPerson():
        resultList = ['not at all', 'in small doses', 'in large doses']
        percentTats = float(input('percentage of time spent playing video games?'))
        ffMiles = float(input('frequent filer miles earned per year?'))
        iceCream = float(input("liters of ice cream consumed per year?"))
        datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
        normMat, ranges, minVals = autoNorm(datingDataMat)
        inArr = array([ffMiles, percentTats, iceCream])
        classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)
        print("You will probably like this person: ", resultList[classifierResult - 1])

![在这里插入图片描述][201911131957552.png]

#### 项目案例2: 手写数字识别系统 ####

**项目概述**  
构造一个能识别数字 0 到 9 的基于 KNN 分类器的手写数字识别系统。

需要识别的数字是存储在文本文件中的具有相同的色彩和大小：宽高是 32 像素 \* 32 像素的黑白图像。

**开发流程**  
收集数据：提供文本文件。  
准备数据：编写函数 img2vector(), 将图像格式转换为分类器使用的向量格式  
分析数据：在 Python 命令提示符中检查数据，确保它符合要求  
训练算法：此步骤不适用于 KNN  
测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误  
使用算法：本例没有完成此步骤，若你感兴趣可以构建完整的应用程序，从图像中提取数字，并完成数字识别，美国的邮件分拣系统就是一个实际运行的类似系统

***收集数据: 提供文本文件***

目录 trainingDigits 中包含了大约 2000 个例子，每个例子内容如下图所示，每个数字大约有 200 个样本；目录 testDigits 中包含了大约 900 个测试数据。

***准备数据:将图像文本数据转换为向量***

为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量。我们将把一个32 × 32的二进制图像矩阵转换为1×1024的向量，这样前两节使用的分类器就可以处理数字图像信息了。  
我们首先编写一段函数img2vector，将图像转换为向量：该函数创建1×1024的NumPy数组，然后打开给定的文件，循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组。

def img2vector(filename):
        """
        将图像文本数据转换为向量
        :param filename:数据文件路径
        :return:数据矩阵 一维矩阵
        该函数将图像转换为向量：该函数创建 1 * 1024 的NumPy数组，然后打开给定的文件，
        循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组。
        """
    
        returnVect = zeros((1, 1024))
        fr = open(filename)
        for i in range(32):
            lineStr = fr.readline()
            for j in range(32):
                returnVect[0, 32 * i + j] = int(lineStr[j])
        return returnVect

***分析数据：在 Python 命令提示符中检查数据，确保它符合要求***

在 Python 命令行中输入下列命令测试 img2vector 函数，然后与文本编辑器打开的文件进行比较:  
![在这里插入图片描述][20191113200446413.png]  
***训练算法：此步骤不适用于 KNN***

因为测试数据每一次都要与全量的训练数据进行比较，所以这个过程是没有必要的。

***测试算法：编写函数使用提供的部分数据集作为测试样本，如果预测分类与实际类别不同，则标记为一个错误***

def handwritingClassTest():
        # 导入训练数据
        hwLabels = []
        trainingFileList = listdir('trainingDigits')
        m = len(trainingFileList)
        trainingMat = zeros((m, 1024))
        for i in range(m):
            fileNameStr = trainingFileList[i]
            fileStr = fileNameStr.split('.')[0]
            classNumStr = int(fileStr.split('_')[0])
            hwLabels.append(classNumStr)
            trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
    
        # 导入测试数据
        testFileList = listdir('testDigits')
        errorCount = 0.0
        mTest = len(testFileList)
        for i in range(mTest):
            fileNameStr = testFileList[i]
            fileStr = fileNameStr.split('.')[0]
            classNumStr = int(fileStr.split('_')[0])
            vectorUnderTest = img2vector('testDigits\%s' % fileNameStr)
            classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
            print('the classifier came back with:%d,the real answer is:%d' % (classifierResult, classNumStr))
            if classifierResult != classNumStr:
                errorCount += 1.0
        print('\n the total number of errors is:%d' % errorCount)
        print('\n the total error rate is:%f' % (errorCount / float(mTest)))

***使用算法：本例没有完成此步骤，若你感兴趣可以构建完整的应用程序，从图像中提取数字，并完成数字识别，美国的邮件分拣系统就是一个实际运行的类似系统。***

### 4、KNN 小结 ###

> k-近邻算法是分类数据最简单最有效的算法，本章通过两个例子讲述了如何使用k-近邻算法 构造分类器。k-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数 据。k-近邻算法必须保存全部数据集，如果训练数据集的很大，必须使用大量的存储空间。  
> 此外， 由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。 k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均 实例样本和典型实例样本具有什么特征。

## 二、决策树 ##

### 1、决策树 概述 ###

**决策树（Decision Tree）算法**是一种基本的分类与回归方法，是最经常使用的数据挖掘算法之一。这里只讨论用于分类的决策树。

决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

决策树学习通常包括 **3 个步骤**：特征选择、决策树的生成和决策树的修剪。

**决策树的定义**：  
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。

用决策树对需要测试的实例进行分类：从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。

### 2、决策树 原理 ###

#### 须知概念 ####

**熵（entropy）**： 熵指的是体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。（大多数学过物理化学的人应该很熟悉这个概念，没什么变化。）

**信息论（information theory）中的熵（香农熵）**： 是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。（说白了也是讲信息的混乱程度，我的理解是：一堆信息中不同的类很多，说明混乱程度高，熵就高；一堆信息中只有一两种类，那熵就比较低。）

**信息增益（information gain）**： 在划分数据集前后信息发生的变化称为信息增益。（就是划分数据到不同子集前后，熵的变化。）  
计算方法如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 1]

#### 工作原理 ####

使用 createBranch() 方法，如下所示：

def createBranch():
    '''
    此处运用了迭代的思想。 感兴趣可以搜索 迭代 recursion， 甚至是 dynamic programing。
    '''
        检测数据集中的所有数据的分类标签是否相同:
            If so return 类标签
            Else:
                寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
                划分数据集
                创建分支节点
                    for 每个划分的子集
                        调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
                return 分支节点

#### 开发流程 ####

> 1.  收集数据：可以使用任何方法。
> 2.  准备数据：树构造算法 (这里使用的是ID3算法，只适用于标称型数据，这就是为什么数值型数据必须离散化。 还有其他的树构造算法，比如CART)
> 3.  分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
> 4.  训练算法：构造树的数据结构。
> 5.  测试算法：使用训练好的树计算错误率。
> 6.  使用算法：此步骤可以适用于任何监督学习任务，而使用决策树可以更好地理解数据的内在含义。

#### 算法特点 ####

>  *  优点：计算复杂度不高，输出结果易于理解，数据有缺失也能跑，可以处理不相关特征。
>  *  缺点：容易过拟合。
>  *  适用数据类型：数值型和标称型。

### 3、决策树 项目案例 ###

完整代码地址：[https://blog.csdn.net/qq\_45556599/article/details/103315815][https_blog.csdn.net_qq_45556599_article_details_103315815]

#### 项目案例1: 判定鱼类和非鱼类 ####

**项目概述**

根据以下 2 个特征，将动物分成两类：鱼类和非鱼类。

特征：  
1、不浮出水面是否可以生存  
2、是否有脚蹼

**开发流程**

> 收集数据：可以使用任何方法  
> 准备数据：树构造算法（这里使用的是ID3算法，因此数值型数据必须离散化。）  
> 分析数据：可以使用任何方法，构造树完成之后，我们可以将树画出来。  
> 训练算法：构造树结构  
> 测试算法：使用习得的决策树执行分类  
> 使用算法：此步骤可以适用于任何监督学习任务，而使用决策树可以更好地理解数据的内在含义

*收集数据：可以使用任何方法*  
![在这里插入图片描述][20191115201353465.png]  
我们利用 createDataSet() 函数输入数据：

def createDataSet():
        dataSet = [
            [1, 1, 'yes'],
            [1, 1, 'yes'],
            [1, 0, 'no'],
            [0, 1, 'no'],
            [0, 1, 'no']
        ]
        labels = ['no surfacing', 'flippers']
        return dataSet, labels

![在这里插入图片描述][20191115201559740.png]  
*准备数据：树构造算法*

此处，由于我们输入的数据本身就是离散化数据，所以这一步就省略了。

*分析数据：可以使用任何方法，构造树完成之后，我们可以将树画出来。*

划分数据集（也就是按照一种特征来分类）的大原则是：将无序的数据变得更加有序。我们可以使用多种方法划分数据集， 但是每种方法都有各自的优缺点。这时我们计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。  
![在这里插入图片描述][20191115201728860.png]  
首先需要计算给定数据集的香农熵的函数

def calcShannonEnt(dataSet):
        """
        计算给定数据集的香农熵
        :param dataSet:数据集
        :return:每一组feature下的某个分类下，香农熵的信息期望
        """
        # 第一种实现方法
        # 求list的长度，表示计算参与训练的数据量
        numEntries = len(dataSet)
    
        # 计算分类标签label出现的次数
        labelCounts = {
        }
        for featVec in dataSet:
            # 将当前实例的标签存储，即每一行数据的最后一个数据代表的是标签
            currentLabel1 = featVec[-1]
            # 为所有可能的分类创建字典，如果当前的键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。
            if currentLabel1 not in labelCounts.keys():
                labelCounts[currentLabel1] = 0
            labelCounts[currentLabel1] += 1
    
        # 对于label标签的占比，求出label标签的香农熵
        shannonEnt = 0.0
        for key in labelCounts:
            # 使用所有类标签的发生频率计算类别出现的概率。
            prob = float(labelCounts[key]) / numEntries
            # 计算香农熵，以 2 为底求对数
            shannonEnt -= prob * log(prob, 2)
        # 第一种实现方式end
    
        # 第二种实现方式start
        # # 统计标签出现的次数
        # label_count = Counter(data[-1] for data in dataSet)
        # # 计算概率
        # probs = [p[1] / len(dataSet) for p in label_count.items()]
        # # 计算香农熵
        # shannonEnt = sum([-p * log(p, 2) for p in probs])
        # 第二种实现方式end
    
        return shannonEnt

![在这里插入图片描述][2019111520201213.png]  
可以看到当我们修改第一个元素的类别后（即集合中由两种类变成了三种类），信息熵变大了，混乱程度变大了。

按照给定特征划分数据集的函数

def splitDataSet(dataSet, index, value):
        """
        就是依据index列进行分类，如果index列的数据等于 value，就要将 index 划分到我们创建的新的数据集中
        说白了就是通过index特征分类，并将特征从数据中消除
        :param dataSet:数据集                  待划分的数据集
        :param index:表示每一行的index列        划分数据集的特征
        :param value:表示index列对应的value值   需要返回的特征的值。
        :return:index列为value的数据集【该数据集需要排除index列】
        """
    
        retDataSet = []
        for featVec in dataSet:
            if featVec[index] == value:
                # [:index]表示前index行，即若 index 为2，就是取 featVec 的前 index 行
                reducedFeatVec = featVec[:index]
                # 1、使用append的时候，是将object看作一个对象，整体打包添加到music_media对象中。
                # 2、使用extend的时候，是将sequence看作一个序列，将这个序列和music_media序列合并，并放在其后面。
                reducedFeatVec.extend(featVec[index + 1:])
                retDataSet.append(reducedFeatVec)
        return retDataSet

下面的例子是按照第一个特征划分了数据集：  
![在这里插入图片描述][20191115202802790.png]  
选择最好的数据集划分方式

def chooseBestFeatureToSplit(dataSet):
        """
        选择最好的特征
        :param dataSet:数据集
        :return:最优的特征列
        """
        # 求第一行有多少列的 Feature, 最后一列是label列
        numFeatures = len(dataSet[0]) - 1
        # 数据集的原始信息熵
        baseEntropy = calcShannonEnt(dataSet)
        # 最优的信息增益值, 和最优的Featurn编号
        bestInfoGain, bestFeature = 0.0, -1
        for i in range(numFeatures):
            # 获取对应的feature下的所有数据
            featList = [example[i] for example in dataSet]
            # 获取剔重后的集合，使用set对list数据进行去重
            uniqueVals = set(featList)
            # 创建一个临时的信息熵
            newEntropy = 0.0
            # 遍历某一列的value集合，计算该列的信息熵
            # 遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和。
            for value in uniqueVals:
                subDateSet = splitDataSet(dataSet, i, value)
                # 计算概率
                prob = len(subDateSet) / float(len(dataSet))
                # 计算信息熵
                newEntropy += prob * calcShannonEnt(subDateSet)
            # gain[信息增益]: 划分数据集前后的信息变化， 获取信息熵最大的值
            # 信息增益是熵的减少或者是数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。
            infoGain = baseEntropy - newEntropy
            if infoGain > bestInfoGain:
                bestInfoGain = infoGain
                bestFeature = i
        return bestFeature
    
        # # -----------选择最优特征的第二种方式 start------------------------------------
        # # 计算初始香农熵
        # base_entropy = calcShannonEnt(dataSet)
        # best_info_gain = 0
        # best_feature = -1
        # # 遍历每一个特征
        # for i in range(len(dataSet[0]) - 1):
        #     # 对当前特征进行统计
        #     feature_count = Counter([data[i] for data in dataSet])
        #     # 计算分割后的香农熵
        #     new_entropy = sum(feature[1] / float(len(dataSet)) * calcShannonEnt(splitDataSet(dataSet, i, feature[0])) \
        #                    for feature in feature_count.items())
        #     # 更新值
        #     info_gain = base_entropy - new_entropy
        #     print('No. {0} feature info gain is {1:.3f}'.format(i, info_gain))
        #     if info_gain > best_info_gain:
        #         best_info_gain = info_gain
        #         best_feature = i
        # return best_feature
        # # -----------选择最优特征的第二种方式 end------------------------------------

![在这里插入图片描述][20191115203144686.png]  
代码运行结果告诉我们，第0个特征是最好的用于划分数据集的特征。如果不相信目测结果，读者可以使用calcShannonEntropy()函数测试不同特征分组的输出结果。

*训练算法：构造树的数据结构*  
写完了从数据集构造决策树算法所需要的子功能模块，之后写构造树的函数，其工作原理如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于 两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。  
递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 2]  
如果数据集已经处理了所有属性，但是类标签依然不是唯一 的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法决 定该叶子节点的分类。

def majorityCnt(classList):
        """
        选择出现次数最多的一个结果
        :param classList:列的集合
        :return:bestFeature 最优的特征列
        """
        # -----------majorityCnt的第一种方式 start------------------------------------
        classCount = {
        }
        for vote in classList:
            if vote not in classCount.keys():
                classCount[vote] = 0
            classCount[vote] += 1
        # 倒叙排列classCount得到一个字典集合，然后取出第一个就是结果（yes/no），即出现次数最多的结果
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        return sortedClassCount[0][0]
        # -----------majorityCnt的第一种方式 end------------------------------------
    
        # # -----------majorityCnt的第二种方式 start------------------------------------
        # major_label = Counter(classList).most_common(1)[0]
        # return major_label
        # # -----------majorityCnt的第二种方式 end------------------------------------

创建树的函数代码如下：

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)
        return myTree

![在这里插入图片描述][20191115204244739.png]  
变量myTree包含了很多代表树结构信息的嵌套字典，从左边开始，第一个关键字no surfacing是第一个划分数据集的特征名称，该关键字的值也是另一个数据字典。第二个关键字 是no surfacing特征划分的数据集，这些关键字的值是no surfacing节点的子节点。这些值 可能是类标签，也可能是另一个数据字典。如果值是类标签，则该子节点是叶子节点；如果值是 另一个数据字典，则子节点是一个判断节点，这种格式结构不断重复就构成了整棵树。本节的例 子中，这棵树包含了3个叶子节点以及2个判断节点。

*测试算法：使用决策树执行分类*

def classify(inputTree, featLabels, testVec):
        """
        给输入的节点，进行分类
        :param inputTree:决策树模型
        :param featLabels:Feature标签对应的名称
        :param testVec:测试输入的数据
        :return:classLabel 分类的结果值，需要映射label才能知道名称
        """
        # 获取tree的根节点对于的key值
        firstStr = list(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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 3]  
*使用算法：决策树的储存*

构造决策树是很耗时的任务，即使处理很小的数据集，如前面的样本数据，也要花费几秒的 时间，如果数据集很大，将会耗费很多计算时间。然而用创建好的决策树解决分类问题，则可以 很快完成。因此，为了节省计算时间，好能够在每次执行分类时调用已经构造好的决策树。为 了解决这个问题，需要使用Python模块pickle序列化对象。

def storeTree(inputTree, filename):
        import pickle
        fw = open(filename, 'wb')
        pickle.dump(inputTree, fw)
        fw.close()
        # -------------- 第二种方法 start --------------
        # with open(filename, 'wb') as fw:
        #     pickle.dump(inputTree, fw)
        # -------------- 第二种方法 start --------------
    
    
    def grapTree(filename):
        import pickle
        fr = open(filename, 'rb')
        return pickle.load(fr)

![在这里插入图片描述][20191115205023511.png]  
通过上面的代码，我们可以将分类器存储在硬盘上，而不用每次对数据分类时重新学习一遍， 这也是决策树的优点之一，像k-近邻算法就无法持久化分类器。

#### 项目案例2: 使用决策树预测隐形眼镜类型 ####

**项目概述**

隐形眼镜类型包括硬材质、软材质以及不适合佩戴隐形眼镜。眼科医生是如何判断患者需要佩戴的镜片类型；一旦理解了决策树的工作原理，我们甚至也可以帮助人们判断需要佩戴的镜片类型。

**开发流程**

> 收集数据: 提供的文本文件。  
> 解析数据: 解析 tab 键分隔的数据行  
> 分析数据: 快速检查数据，确保正确地解析数据内容，使用createPlot() 函数绘制最终的树形图。  
> 训练算法: 使用 createTree() 函数。 测试算法:  
> 编写测试函数验证决策树可以正确分类给定的数据实例。  
> 使用算法: 存储树的数据结构，以便下次使用时无需重新构造树。

*收集数据：提供的文本文件*

文本文件数据格式如下：

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

*解析数据：解析 tab 键分隔的数据行*

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

*分析数据：快速检查数据，确保正确地解析数据内容，使用 createPlot() 函数绘制最终的树形图。*

![在这里插入图片描述][20191115210034304.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 4]  
如图所示的决策树非常好地匹配了实验数据，然而这些匹配选项可能太多了。我们将这种 问题称之为过度匹配（overfitting）。为了减少过度匹配问题，我们之后会讨论裁剪决策树，去掉一些不 必要的叶子节点。

*训练算法：使用 createTree() 函数*

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

*使用算法: 存储树的数据结构，以便下次使用时无需重新构造树。*

### 4、决策树 小结 ###

决策树分类器就像带有终止块的流程图，终止块表示分类结果。开始处理数据集时，我们首 先需要测量集合中数据的不一致性，也就是熵，然后寻找优方案划分数据集，直到数据集中的所有数据属于同一分类。ID3算法可以用于划分标称型数据集。构建决策树时，我们通常采用递 归的方法将数据集转化为决策树。一般我们并不构造新的数据结构，而是使用Python语言内嵌的数据结构字典存储树节点信息。  
使用Matplotlib的注解功能，我们可以将存储的树结构转化为容易理解的图形。Python语言的 pickle 模块可用于存储决策树的结构。隐形眼镜的例子表明决策树可能会产生过多的数据集划分， 从而产生过度匹配数据集的问题。我们可以通过裁剪决策树，合并相邻的无法产生大量信息增益的叶节点，消除过度匹配问题。

## 三、使用 Matplotlib 注解绘制树形图 ##

说实话，没看懂，代码先摆着吧。。。（有些地方出错，稍微改了一下）

import matplotlib.pyplot as plt
    
    # 定义文本框 和 箭头格式 【 sawtooth 波浪方框, round4 矩形方框 , fc表示字体颜色的深浅 0.1~0.9 依次变浅，没错是变浅】
    decisionNode = dict(boxstyle="sawtooth", fc="0.8")
    leafNode = dict(boxstyle="round4", fc="0.8")
    arrow_args = dict(arrowstyle="<-")
    
    
    def plotNode(nodeTxt, centerPt, parentPt, nodeType):
        createPlot.ax1.annotate(nodeTxt, xy=parentPt,
                                xycoords='axes fraction',
                                xytext=centerPt, textcoords='axes fraction',
                                va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)
    
    
    def createPlot(inTree):
        # 创建一个figure的模版
        fig = plt.figure(1, facecolor='green')
        fig.clf()
    
        axprops = dict(xticks=[], yticks=[])
        # 表示创建一个1行，1列的图，createPlot.ax1 为第 1 个子图，
        createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
    
        plotTree.totalW = float(getNumLeafs(inTree))
        plotTree.totalD = float(getTreeDepth(inTree))
        # 半个节点的长度；xOff表示当前plotTree未遍历到的最左的叶节点的左边一个叶节点的x坐标
        # 所有叶节点中，最左的叶节点的x坐标是0.5/plotTree.totalW（因为totalW个叶节点在x轴方向是平均分布在[0, 1]区间上的）
        # 因此，xOff的初始值应该是 0.5/plotTree.totalW-相邻两个叶节点的x轴方向距离
        plotTree.xOff = -0.5 / plotTree.totalW
        # 根节点的y坐标为1.0，树的最低点y坐标为0
        plotTree.yOff = 1.0
        # 第二个参数是根节点的坐标
        plotTree(inTree, (0.5, 1.0), '')
        plt.show()
    
    
    def getNumLeafs(myTree):
        numLeafs = 0
        firstStr = list(myTree.keys())[0]  # 这里原来的代码稍有问题，变为list就好
        secondDict = myTree[firstStr]
        # 根节点开始遍历
        for key in secondDict.keys():
            # 判断子节点是否为dict, 不是+1
            if type(secondDict[key]) is dict:
                numLeafs += getNumLeafs(secondDict[key])
            else:
                numLeafs += 1
        return numLeafs
    
    
    def getTreeDepth(myTree):
        maxDepth = 0
        firstStr = list(myTree.keys())[0]
        secondDict = myTree[firstStr]
        # 根节点开始遍历
        for key in secondDict.keys():
            # 判断子节点是不是dict, 求分枝的深度
            if type(secondDict[key]) is dict:
                thisDepth = 1 + getTreeDepth(secondDict[key])
            else:
                thisDepth = 1
            # 记录最大的分支深度
            if thisDepth > maxDepth:
                maxDepth = thisDepth
        return maxDepth
    
    
    # 函数retrieveTree()主要用于测试，返回预定义的树结构。
    def retrieveTree(i):
        listOfTrees = [
            {
        'no surfacing': {
        0: 'no', 1: {
        'flippers': {
        0: 'no', 1: 'yes'}}}},
            {
        'no surfacing': {
        0: 'no', 1: {
        'flippers': {
        0: {
        'head': {
        0: 'no', 1: 'yes'}}, 1: 'no'}}}}
        ]
        return listOfTrees[i]
    
    
    # 在父子节点间填充文本信息
    def plotMidText(cntrPt, parentPt, txtString):
        xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]
        yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]
        createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
    
    
    def plotTree(myTree, parentPt, nodeTxt):
        # 获取叶子节点的数量
        numLeafs = getNumLeafs(myTree)
        # 获取树的深度
        # depth = getTreeDepth(myTree)
    
        # 找出第1个中心点的位置，然后与 parentPt定点进行划线
        # x坐标为 (numLeafs-1.)/plotTree.totalW/2+1./plotTree.totalW，化简如下
        cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)
        # print cntrPt
        # 并打印输入对应的文字
        plotMidText(cntrPt, parentPt, nodeTxt)
    
        firstStr = list(myTree.keys())[0]
        # 可视化Node分支点；第一次调用plotTree时，cntrPt与parentPt相同
        plotNode(firstStr, cntrPt, parentPt, decisionNode)
        # 根节点的值
        secondDict = myTree[firstStr]
        # y值 = 最高点-层数的高度[第二个节点位置]；1.0相当于树的高度
        plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
        for key in secondDict.keys():
            # 判断该节点是否是Node节点
            if type(secondDict[key]) is dict:
                # 如果是就递归调用[recursion]
                plotTree(secondDict[key], cntrPt, str(key))
            else:
                # 如果不是，就在原来节点一半的地方找到节点的坐标
                plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW
                # 可视化该节点位置
                plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
                # 并打印输入对应的文字
                plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
        plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD

# 资料来源 #

https://github.com/apachecn/AiLearning  
https://github.com/apachecn/AiLearning/tree/master/docs/ml  
机器学习实战（作者: Peter Harrington 出版社: 人民邮电出版社原作名: Machine Learning in Action译者: 李锐 / 李鹏 / 曲亚东 / 王斌 ）

[https_blog.csdn.net_qq_45556599_article_details_103111984]: https://blog.csdn.net/qq_45556599/article/details/103111984
[20191113192836926.png]: https://img-blog.csdnimg.cn/20191113192836926.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191113193135998.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[20191113195637223.png]: https://img-blog.csdnimg.cn/20191113195637223.png
[201911131957552.png]: https://img-blog.csdnimg.cn/201911131957552.png
[20191113200446413.png]: https://img-blog.csdnimg.cn/20191113200446413.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191115200741466.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[https_blog.csdn.net_qq_45556599_article_details_103315815]: https://blog.csdn.net/qq_45556599/article/details/103315815
[20191115201353465.png]: https://img-blog.csdnimg.cn/20191115201353465.png
[20191115201559740.png]: https://img-blog.csdnimg.cn/20191115201559740.png
[20191115201728860.png]: https://img-blog.csdnimg.cn/20191115201728860.png
[2019111520201213.png]: https://img-blog.csdnimg.cn/2019111520201213.png
[20191115202802790.png]: https://img-blog.csdnimg.cn/20191115202802790.png
[20191115203144686.png]: https://img-blog.csdnimg.cn/20191115203144686.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191115203516320.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[20191115204244739.png]: https://img-blog.csdnimg.cn/20191115204244739.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191115204703838.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[20191115205023511.png]: https://img-blog.csdnimg.cn/20191115205023511.png
[20191115210034304.png]: https://img-blog.csdnimg.cn/20191115210034304.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191115210049303.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70