“机器学习实战”刻意练习——分类问题：K近邻算法

朴灿烈づ我的快乐病毒、 2023-05-30 09:29 21阅读 0赞

参考：[Python3《机器学习实战》学习笔记（一）：k-近邻算法(史诗级干货长文) - Jack-Cui - CSDN博客][Python3_k-_ - Jack-Cui - CSDN]

# 一、概述 #

简单地说，K-近邻算法就是采用测量不同特征值之间的距离方法进行分类。

其工作原理是：

*  存在一个样本数据集合，也称作**训练样本集**，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的**对应关系**。
 *  输人没有标签的新数据后，将新数据的**每个特征与样本集中数据对应的特征进行比较**，然后算法提取样本集中特征\*\*最相似数据（最近邻）\*\*的分类标签。
 *  一般来说，我们只选择样本数据集中**前K个最相似的数据**，这就是K-近邻算法中K的出处,通常K是不大于20的整数。
 *  最后 ，选择K个最相似数据中出现次数最多的分类，作为**新数据的分类**。

优点和缺点：

*  优点 : 精度高、对异常值不敏感、无数据输入假定。
 *  缺点 : 计算复杂度高、空间复杂度高。

适用数据范围 :

*  **数值型**
 *  **标称型**。

k-近邻算法的一般流程：

1.  **收集数据**：可以使用爬虫进行数据的收集，也可以使用第三方提供的免费或收费的数据。一般来讲，数据放在txt文本文件中，按照一定的格式进行存储，便于解析及处理。
2.  **准备数据**：使用Python解析、预处理数据。
3.  **分析数据**：可以使用很多方法对数据进行分析，例如使用Matplotlib将数据可视化。
4.  **测试算法**：计算错误率。
5.  **使用算法**：错误率在可接受范围内，就可以运行k-近邻算法进行分类。

# 二、代码实现（python3） #

## 1.准备数据集 ##

import numpy as np				#导入科学计算包numpy
    
    def createDataSet():            #创建数据集
        #group:数据集,二维特征
        group=np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
        #labels:labels
        labels=['A','A','B','B']
        return group,labels
    
    if __name__ == "__main__":
        #创建数据集
        group,labels=createDataSet()
        #打印数据集
        print(group)
        print(labels)

输出

[[1.  1.1]
     [1.  1. ]
     [0.  0. ]
     [0.  0.1]]
    ['A', 'A', 'B', 'B']

## 2.从文本文件中解析处理数据 ##

对未知类别属性的数据集中的每个点依次执行以下操作：

(1)**计算**已知类别数据集中的点与当前点之间的**距离**；  
我们使用欧氏距离公式，计算两个向量点之间的距离。即  
 d ( p , q ) = d ( q , p ) = ( q 1 − p 1 ) 2 + ( q 2 − p 2 ) 2 + ⋅ ⋅ ⋅ + ( q n − p n ) 2 d(p,q)=d(q,p)=\\sqrt\{ ( q\_\{1\}-p\_\{1\} )^\{2\}+( q\_\{2\}-p\_\{2\} )^\{2\}+\\cdot \\cdot \\cdot +( q\_\{n\}-p\_\{n\} )^\{2\}\} d(p,q)=d(q,p)=(q1−p1)2\+(q2−p2)2\+⋅⋅⋅\+(qn−pn)2

(2)按照距离**递增**次序排序；

(3)**选取**与当前点**距离最小的K个点**；

(4)**确定**前K个点所在类别的**出现频率**；

(5)返回**前K个点出现频率最高的类别作为当前点的预测分类**。

以下直接给出代码及其作用，一些相关函数的使用方法在代码后补充

import numpy as np				#导入科学计算包numpy
    import operator					#导入运算符模块
    
    def classify0(inX, dataSet, labels, k):
        """ 计算距离并分类 - - - - inX - 用于分类的输入向量 dataSet - 输入的训练样本集(即之前定义的group) labels - 标签向量 k - 表示用于选择最近邻居的数目 注意，标签向量的元素数目和矩阵dataSet的行数相同 （没理解的可以看createDataSet()的输出结果) """
        #获得dataSet中数据的个数
        dataSetSize = dataSet.shape[0]	
        #每个inX都减去dataSet中的数据
        diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
        #每个差值取平方
        sqDiffMat = diffMat**2
        #所有平方相加
        sqDistances = sqDiffMat.sum(axis=1)
        #开方，计算出距离
        distances = sqDistances**0.5
        #距离排序
        sortedDistIndices = distances.argsort()
    
        #定一个记录类别次数的字典
        classCount = { }
        for i in range(k):
            #取出前k个元素的类别
            voteIlabel = labels[sortedDistIndices[i]]
            #在字典中计算类别次数,该类型值加1
            classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        #类型结果排序
        sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    
        #返回次数最多的类别
        return sortedClassCount[0][0]

代码中用到的几个函数：

1.  numpy.array.shape\[0\] —— 返回array的行数(shape()返回行数和列数)
2.  numpy.tile(A,reps) —— 就是将原矩阵A横向、纵向地复制。（详见[图解Numpy的tile函数 - 简书][Numpy_tile_ -]）
3.  numpy.array.sum(axis=1) —— 将一个矩阵的每一**行向量**中元素相加

c = np.array([[0, 2, 1], [3, 5, 6], [0, 1, 1]])
    print c.sum()
    #19
    print c.sum(axis=0)
    #[3 8 8]
    print c.sum(axis=1)
    #[3 14 2]

1.  numpy.array.argsort() —— 返回数组值**从小到大**的**索引值**
2.  dictB=sorted(dictA.items(),key=operator.itemgetter(1),reverse=True)  
    key=operator.itemgetter(1) —— 根据字典的值进行排序  
    reverse=True —— 降序排序

# 三、如何测试分类器 #

分类器并不会得到百分百正确的结果，我们可以使用多种方法检测分类器的正确率。  
此外，分类器的性能也会受到多种因素的影响，如分类器设置和数据集等。不同的算法在**不同数据集上的表现可能完全不同**。

为了测试分类器的效果，我们可以使用已知答案的数据，当然答案不能告诉分类器，检验分类器给出的结果是否符合预期结果。  
通过大量的测试数据，我们可以得到分类器的**错误率**——分类器给出错误结果的次数除以测试执行的总数。  
**错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果**。

# 四、k-近邻算法实战：约会网站配对效果判定 #

## 1.背景 ##

海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她并不是喜欢每一个人。经过一番总结，她发现曾交往过三种类型的人：

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

尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会那些魅力一般的人，而周末则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好地帮助她将匹配对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。

## 2.设想步骤 ##

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

## 3.具体过程 ##

### （1）准备数据：从文本文件中解析数据 ###

海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件[datingTestSet.txt][]中，每个样本数据占据一行，总共有1000行。海伦的样本主要包含以下3种特征：

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

在将上述特征数据输入到分类器之前，必须将待处理数据的格式改变为分类器可以接受的格式。在kNN.py中创建名为file2matrix的函数，以此来处理输入格式问题。该函数的输入为文件名字符串，输出为训练样本矩阵和类标签向量。

def file2matrix(filename):
        """ 读取指定文本中数据集，输出为训练样本矩阵和类标签向量。 - - - - filename - 文件路径 """
        #打开文件并读取，得到其行数
        fr = open(filename)
        arrayOLines = fr.readlines()
        numberOfLines = len(arrayOLines)
        #创建返回的NumPy矩阵
        returnMat = np.zeros((numberOfLines,3))
        #返回的分类标签向量
        classLabelVector = []
        #行的索引值
        index = 0
        for line in arrayOLines:
            #解析文件数据到list
            line = line.strip()
            listFromLine = line.split('\t')
            #将数据前三列提取出来,存放到returnMat的NumPy矩阵中,也就是特征矩阵
            returnMat[index,:] = listFromLine[0:3]
            #根据文本中标记的喜欢的程度进行分类,1代表不喜欢,2代表魅力一般,3代表极具魅力
            if listFromLine[-1] == 'didntLike':
                classLabelVector.append(1)
            elif listFromLine[-1] == 'smallDoses':
                classLabelVector.append(2)
            elif listFromLine[-1] == 'largeDoses':
                classLabelVector.append(3)
            index += 1
        return returnMat,classLabelVector

### (2)分析数据：使用 Matplotlib 创建散点图实现数据可视化 ###

因为有三个数据项，无法在平面表现  
故只选取前两项,即“每年获得的飞行常客里程数”和“玩视频游戏所耗时间百分比”作示范：

from matplotlib.font_manager import FontProperties
    import matplotlib.lines as mlines
    import matplotlib.pyplot as plt
    
    def showdatas(datingDataMat, datingLabels):
        """ 数据可视化 - - - - datingDataMat - 特征矩阵 datingLabels - 分类标签 """
        #设置汉字格式
        font = FontProperties(fname=r'/Users/lql70/Downloads/simsun.ttc', size=16)
        fig=plt.figure()
        ax=plt.subplot(111)
        #分类设置点的颜色
        numberOfLabels = len(datingLabels)
        LabelsColors = []
        for i in datingLabels:
            if i == 1:
                LabelsColors.append('black')
            if i == 2:
                LabelsColors.append('orange')
            if i == 3:
                LabelsColors.append('red')
        ax.scatter(x=datingDataMat[:,0], y=datingDataMat[:,1], color=LabelsColors,s=15, alpha=.5)
        #设置标题和坐标轴标签
        ax_title_text = ax.set_title(u'每年获得的飞行常客里程数与玩视频游戏所消耗时间占比',FontProperties=font)
        ax_xlabel_text = ax.set_xlabel(u'每年获得的飞行常客里程数',FontProperties=font)
        ax_ylabel_text = ax.set_ylabel(u'玩视频游戏所消耗时间占比',FontProperties=font)
        plt.setp(ax_title_text, size=11, weight='bold', color='red') 
        plt.setp(ax_xlabel_text, size=9, weight='bold', color='black') 
        plt.setp(ax_ylabel_text, size=9, weight='bold', color='black')
        #设置图例
        didntLike = mlines.Line2D([], [], color='black', marker='.',markersize=6, label='didntLike')
        smallDoses = mlines.Line2D([], [], color='orange', marker='.',markersize=6, label='smallDoses')
        largeDoses = mlines.Line2D([], [], color='red', marker='.',markersize=6, label='largeDoses')
        #添加图例
        ax.legend(handles=[didntLike,smallDoses,largeDoses])
        #显示图像
        plt.show()

结果如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70]

### （3）准备数据：数据归一化 ###

在计算的过程中，我们会发现对某一组数据，欧氏距离公式如下：  
 ( 0 − 67 ) 2 + ( 20000 − 32000 ) 2 + ( 1.1 − 0.1 ) 2 \\sqrt\{ ( 0-67)^\{2\}+(20000-32000 )^\{2\}+( 1.1-0.1 )^\{2\}\} (0−67)2\+(20000−32000)2\+(1.1−0.1)2

我们很容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响将远远大于其他两个特征——玩视频游戏的和每周消费冰淇淋公升数的影响很大。  
而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值。  
但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。

在处理这种不同取值范围的特征值时，我们通常采用的方法是**将数值归一化**，如将取值范围处理为０到１或者-１到１之间。  
下面的公式可以将任意取值范围的特征值转化为０到１区间内的值：  
*newValue = (oldValue - min) / (max - min)*  
其中min和max分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂度，但为了得到准确结果，我们必须这样做。我们需要在文件kNN.py中增加一个新函数autoNorm()，该函数可以自动将数字特征值转化为0到1的区间。

def autoNorm(dataSet):
        """ 对数据进行归一化 - - - - dataSet - 特征矩阵 """
        #获得数据的最小值
        minVals = dataSet.min(0)
        maxVals = dataSet.max(0)
        ranges = maxVals - minVals
        #shape(dataSet)返回dataSet的矩阵行列数
        normDataSet = np.zeros(np.shape(dataSet))
        #返回dataSet的行数
        m = dataSet.shape[0]
        #原始值减去最小值
        normDataSet = dataSet - np.tile(minVals, (m, 1))
        #除以最大和最小值的差,得到归一化数据
        normDataSet = normDataSet / np.tile(ranges, (m, 1))
        #返回归一化数据结果,数据范围,最小值
        return normDataSet, ranges, minVals

### (4)测试算法：验证分类器 ###

机器学习算法一个很重要的工作就是评估算法的正确率  
通常我们只提供已有数据的**90%作为训练样本来训练分类器，而使用其余的10%数据去测试分类器，检测分类器的正确率。  
需要注意的是，10%的测试数据应该是随机选择**的

由于海伦提供的数据并没有按照特定目的来排序，所以我们可以随意选择10%数据而不影响其随机性。

def datingClassTest():
        """ 验证分类器 - - - - """
        dateDataMat, dateLabels = file2matrix('Machine_Learning/datingTestSet.txt')
        #取所有数据的百分之十
        hoRatio = 0.10
        #数据归一化,返回归一化后的矩阵,数据范围,数据最小值
        normMat, ranges, minVals = autoNorm(dateDataMat)
        #获得normMat的行数
        m = normMat.shape[0]
        #百分之十的测试数据的个数
        numTestVecs = int(m * hoRatio)
        #分类错误计数
        errorCount = 0.0
    
        for i in range(numTestVecs):
            #前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集
            classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:],
                dateLabels[numTestVecs:m], 4)
            print("the classifier came back with:%d\tthe real answer is:%d" % (classifierResult, dateLabels[i]))
            if classifierResult != dateLabels[i]:
                errorCount += 1.0
        print("the total error rate is:%f%%" %(errorCount/float(numTestVecs)*100))

我运行的结果如下：

the classifier came back with:3 the real answer is:3
    the classifier came back with:2 the real answer is:2
    the classifier came back with:1 the real answer is:1
    ......
    the classifier came back with:1 the real answer is:1
    the total error rate is:4.000000%

分类器处理约会数据集的错误率是4%，这是一个可以接受的结果。

我们可以改变函数datingClassTest内变量hoRatio和变量k的值，检测错误率是否随着变量值的变化而增加。  
依赖于分类算法、数据集和程序设置，分类器的输出结果可能有很大的不同。

这个例子表明我们可以正确地预测分类，错误率仅是4%。  
海伦完全可以输入未知对象的属性信息，由分类软件来帮助她判定某一对象的可交往程度：讨厌、一般喜欢、非常喜欢。

### （5）使用算法：构建完整可用系统 ###

上面我们已经在数据上对分类器进行了测试，现在终于可以使用这个分类器为海伦来对人们分类。我们会给海伦一小段程序，通过该程序海伦会在约会网站上找到某个人并输入他的信息。程序会给出她对对方喜欢程度的预测值。

上述程序清单中的大部分代码我们在前面都见过。唯一新加入的代码是函数input()。  
注意，要将输入后的字符串格式转为浮点数

def classifyPerson():
        """ 输入约会对象的三维特征,判断喜欢度，输出 - - - - """
        #输出结果
        resultList = ['not at all','in small doses1','in large doses']
        #三维特征用户输入
        ffMiles = float(input("freguent flier miles earned per year?"))
        precentTats = float(input("percentage of time spent playing video games?"))
        iceCream = float(input("iters of ice cream consumed per week?"))
        #打开并处理数据
        datingDataMat, datingLabels = file2matrix('Machine_Learning/datingTestSet.txt')
        #训练集归一化
        normMat, ranges, minVals = autoNorm(datingDataMat)
        #生成NumPy数组,测试集
        inArr = np.array([ffMiles, precentTats, iceCream])
        #训练集归一化
        normMat, ranges, minVals = autoNorm(datingDataMat)
        #生成NumPy数组,测试集
        inArr = np.array([precentTats, ffMiles, iceCream])
        #测试集归一化
        norminArr = (inArr - minVals) / ranges
        #返回分类结果,k=3
        classifierResult = classify0(norminArr, normMat, datingLabels, 3)
        #打印结果
        print("You will probably like this person:" ,resultList[classifierResult-1])

运行结果：

freguent flier miles earned per year?15000
    percentage of time spent playing video games?10
    iters of ice cream consumed per week?0.5
    You will probably like this person: in large doses

# 五、K-近邻算法小结 #

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

[Python3_k-_ - Jack-Cui - CSDN]: https://blog.csdn.net/c406495762/article/details/75172850
[Numpy_tile_ -]: https://www.jianshu.com/p/9519f1984c70
[datingTestSet.txt]: https://github.com/Jack-Cherish/Machine-Learning/blob/master/kNN/2.%E6%B5%B7%E4%BC%A6%E7%BA%A6%E4%BC%9A/datingTestSet.txt
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191111222619417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70