机器学习（一）：k-近邻算法（kNN）

不念不忘少年蓝@ 2023-07-09 11:23 13阅读 0赞

疫情期间在家办公，利用这富余出的时间，自己学习了机器学习的内容，本博客将自己在学习《机器学习实战》一书的学到的内容纪录下来，记录下自己的学习路径。  
        学机器学习（数据分析)已有一阵子了，从关注[Kesci （和鲸社区）][Kesci]开始，从该数据分析竞赛网站中读了很多优秀的数据分析代码，但是一直感觉自己的基础不扎实，很多机器学习（深度分析）的基本的概念都不是很清晰，所以自己也查找了相关的深度分析的视频去学习，在此我找到了[全栈数据工程师养成攻略][Link 1]，该视频课程老师讲解的很详细，可以让python小白成长很多，但是也不能从浅入深的在机器学习（数据分析）逐渐的提高，因此我目前在慢慢的看[吴恩达：人工智能][Link 2]课程，该课程全英文讲述，但是有字幕，该课程对深度学习的理论讲解的很详细，适合慢慢的多学几遍，但是不能使你很快的从解决问题的角度入们深度分析，因此我找到了《机器学习实战》这本书，希望从中可以清晰我的深度分析的思路。

## 一、数据分析常见步骤 ##

1.  收集数据
2.  准备数据
3.  分析数据
4.  训练数据
5.  测试算法
6.  使用算法

## 二、k-近邻算法（kNN）概述 ##

k-近邻算法即采用不同特征值之间的距离方法进行分类。

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

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

## 三、kNN算法案例 ##

k-近邻算法（kNN）示例代码可以从书籍配套的网站：[https://www.manning.com/downloads/1108][https_www.manning.com_downloads_1108]

#kNN近邻算法
    
    #inX:待确定所属分类属性值(1行n列)
    #dataSet:已确定分类的属性列表(m行n列)
    #labels:已确定分类值
    #k:待分类项与已分类项的距离从小到大排序，取前k个值
    def classify(inX, dataSet, labels, k):
        dataSetSize = dataSet.shape[0]
    
        #diffMat:待确定项与每个dataSet中的元素的差值
        diffMat = tile(inX, (dataSetSize,1)) - dataSet
        #diffMat的平方
        sqDiffMat = diffMat**2
        #sqlDistance:行求和
        sqDistances = sqDiffMat.sum(axis=1)
        #distance:待确定项与已确定分类项的每个点的距离
        distances = sqDistances**0.5
        #sortedDistIndicies:距离数组的index从小到大排序
        sortedDistIndicies = distances.argsort() 
        
        #找寻前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分类算法所使用到的函数概述：
> 
>  *  tile(A,B) 重复A的值B次
> 
>         例：tile(\[0,0\],2) 
> 
>         在列方向上重复2次，输出结果为:\[0,0,0,0\]
> 
>         tile(\[0,0\],(2,1))
> 
>         在行方向上重复2次，列方向上重复一次，输出结果为:
> 
>         \[ \[0,0\]
> 
>           \[0,0\] \]
> 
>  *  argsort()
> 
>         排序后，按排序结果返回排序前数组的该项的下标值。例：
> 
>     import numpy
>     x=numpy.array([5,3,7,2,6])
>     x.argsort()
> 
>         输出结果为 array(\[3, 1, 0, 4, 2\], dtype=int64)
> 
>  *  sorted(排序对象,cmp=None，key=Non，reverse=False)
> 
>         cmp:比较函数，大于返回1，小于返回-1，等于返回0
> 
>         key:用于做比较的元素 
> 
>         revese:True表示从大到小排；False表示从小到大排

### 1）简单分类示例 ###

有四个点\[1.0,1.1\]、\[1.0,1.0\]属于分类A，\[0,0\]、\[0,0.1\]属于分类B，那么\[0.1,0\]属于哪个分类?

import numpy
    
    def createDataSet():
        group=numpy.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
        label=numpy.array(['A','A','B','B'])
        return group,label
    
    group,label=createDataSet()
    
    #输出结果是B
    classify0([0.1,0],datingDataMat,datingLabels,3)

> 上述代码中定义了入下图的四个点
> 
>     import matplotlib
>     import matplotlib.pyplot as plt
>     
>     fig = plt.figure()
>     ax = fig.add_subplot(111)
>     datingDataMat,datingLabels = createDataSet()
>     ax.scatter(datingDataMat[:,0], datingDataMat[:,1])
>     plt.show()
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70][]

### 2）寻找自己喜欢的约会对象 ###

目前有约会对象的相应行为的样本数据1000行，包含的特征为：

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

部分样本数据截图如下（kNN需要的数据都需是数字类型的，所有将喜欢程度修改为数字）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 1][]     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 2][]

下面将以datingTestSet2.txt的样本数据为依据来演示kNN算法的使用

from numpy import *
    import operator
    
    #将datingTestSet2.txt中的内容转换成m行n列的矩阵（1000，3）
    def file2matrix(filename):
        fr = open(filename)
        numberOfLines = len(fr.readlines())         #get the number of lines in the file
        returnMat = zeros((numberOfLines,3))        #prepare matrix to return
        classLabelVector = []                       #prepare labels return   
        fr = open(filename)
        index = 0
        for line in fr.readlines():
            line = line.strip()
            listFromLine = line.split('\t')
            returnMat[index,:] = listFromLine[0:3]
            classLabelVector.append(int(listFromLine[-1]))
            index += 1
        return returnMat,classLabelVector
    
    #由于里程数与玩游戏时间占比和冰激凌公升数数值差距太大，
    #不对数据进行统一的归一化处理，里程数的距离将会极大影响计算结果
    #该函数即是对数据即进行归一化处理
    #该处理算法是：
    #newValue=(oldValue-min)/(max-min)    
    def autoNorm(dataSet):
        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))   #element wise divide
        return normDataSet, ranges, minVals
    
    #由于仅有datingTestSet2.txt，我们来看kNN的测试错误率仅能将数据集进行按比例划分
    #本次将50%的数据作为训练数据，50%的数据作为验证数据，最后计算错误率   
    def datingClassTest():
        hoRatio = 0.50      #hold out 10%，该比例也可以调整成其他的比例
        datingDataMat,datingLabels = file2matrix('./Documents/AI/machinelearninginaction/Ch02/datingTestSet2.txt')       #load data setfrom file
        normMat, ranges, minVals = autoNorm(datingDataMat)
        m = normMat.shape[0]
        numTestVecs = int(m*hoRatio)
        errorCount = 0.0
        for i in range(numTestVecs):
            classifierResult = classify(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 ("错误率: %f" % (errorCount/float(numTestVecs)))
        print ("预测错误个数%d" %errorCount)
        
    datingClassTest()

上述代码输出结果为：错误率: 0.066000\\n  预测错误个数33

### 3）手写识别 ###

本案里的样本数据是已处理好的32\*32像素的0到9的数字图像，图像示例如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 3][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 5][]

示例代码如下：

from numpy import *
    import operator
    from os import listdir
    
    #将图像存储为1行1024列的数据
    def img2vector(filename):
        imgFile = open(filename)
        vector=zeros((1,1024))
        for i in range(32):
            line = imgFile.readline()
            for j in range(32):
                vector[0,i*32+j]=int(line[j])
        return vector
    
    #将数字文件加下的所有文件进行处理
    def dir2TrainingVar(dirname):
        dirlist = listdir(dirname)
        fileCount = len(dirlist)
        trainVector=zeros((fileCount,1024))
        trainLabel = []
        for i in range(fileCount):
            filename = dirlist[i]
            filelabel = int(filename.split('.')[0].split('_')[0])
            trainLabel.append(filelabel)
            trainVector[i]=img2vector(dirname+filename)
        return trainVector,trainLabel
    
    #数字识别kNN错误率计算
    def testClassify():
        trainVector,trainLabel = dir2TrainingVar("./Documents/AI/machinelearninginaction/Ch02/trainingDigits/")
        testVector,testLabel = dir2TrainingVar("./Documents/AI/machinelearninginaction/Ch02/testDigits/") 
        errorCount = 0
        for i in range(len(testVector)):
            predictRtn = classify(testVector[i],trainVector,trainLabel,5)
            #print("预测结果%d,实际结果%d" %(predictRtn,testLabel[i]))
            if predictRtn!=testLabel[i]:
                errorCount +=1
        print("失误率%f" %(errorCount/len(testVector)))
    
    testClassify()

上述代码输出结果为:失误率0.017970

[Kesci]: https://www.kesci.com/
[Link 1]: https://study.163.com/course/courseMain.htm?courseId=1003520028
[Link 2]: https://mooc.study.163.com/smartSpec/detail/1001319001.htm
[https_www.manning.com_downloads_1108]: https://www.manning.com/downloads/1108
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200228212143683.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200229095426967.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200229095717110.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200229102046283.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200229102153307.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200229103141627.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdzaHVpeXVl,size_16,color_FFFFFF,t_70