【机器学习实战】学习笔记 | K-近邻算法

今天药忘吃喽~ 2022-12-18 10:58 257阅读 0赞

k-近邻算法采用测量不同特征值之间的距离方法进行分类。knn算法不需要经过训练就可以直接计算测试集。knn算法并不一定完全正确，错误率为输出错误的次数除以总的执行次数。

**优缺点：**

*  优点：
    
     *  精度高
     *  对异常值不敏感
     *  无数据输入假定
 *  缺点：
    
     *  计算复杂度高
     *  空间复杂度高
     *  样本可能不平衡
     *  无法给出数据的内在含义
 *  适用数据范围：数值型和离散型数据；

**原理：**

*  每个训练数据集中的每个数据都有相应的标签，输入没有标签的新数据之后，将新数据每个特征与样本集中每个数据对应的特征进行比较。
 *  然后算法提取出样本集中最相似的前k个数据分类标签。
 *  再计算这k个标签中每类出现的概率，将新样本划分为概率最大的那个标签中。
 *  k的由来：只选择样本数据集中最相似的前k个数据，k通常是不大于20.

**K-近邻算法的一般流程**：

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

**案例：**  
输入一个二维测试集，算出它与所有训练集的距离，取前k个距离最近的点并统计这k个点类别的频率，输出频率最大的类别即为测试集最可能的类别。

import numpy as np
    import operator
    ''' group-数据集 labels-分类标签 '''
    def createDataSet():
        #四组二维特征
        group=np.array([[1,101],[5,89],[108,5],[115,8]])
        #四组特征的标签
        labels=['A','A','B','B']
        return group,labels
    ''' kNN算法，分类器 inX-用于分类的数据（测试集） dataSet-用于训练的（训练集） labels-分类标签 k-kNN算法参数，选择距离最小的k个点 返回分类结果： sortedClassCount[0][0] '''
    def classify0(inX,dataSet,labels,k):
        #numpy函数shape[0]返回dataSet行数
        dataSetSize=dataSet.shape[0]
        #在列向量方向上重复inX共1次（横向），行向量方向上重复inX共dataSetSize次（纵向）
        diffMat=np.tile(inX,(dataSetSize,1))-dataSet
        #二维特征相减后平方
        sqDiffMat=diffMat**2
        #sum()所有元素相加，sum(0)列相加，sum(1)行相加
        sqDistances=sqDiffMat.sum(axis=1)
        #开方 计算出距离
        distances=sqDistances**0.5
        #返回distances中元素从小到大排序后的索引值
        sortedDisIndices=distances.argsort()
        #定一个记录类别次数的字典
        classCount={ }
        for i in range(k):
            #取出前k个元素的类别
            voteIlabel=labels[sortedDisIndices[i]]
            #dict.get(key，default=None)，字典的get（）方法，返回指定键的值，如果值不在字典中返回默认值
            #计算类别次数
            classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
        #python3中用items（）替换python2中的iteritems()
        #key=operator.itemgetter(1) 根据字典值排序
        #key=operator.itemgetter(0)根据字典的键进行排序
        #reverse降序排序字典
        sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
        #返回次数最多的列别，即所要分类的类别
        return sortedClassCount[0][0]
    
    if __name__=='__main__':
        #创建数据集
        group,labels=createDataSet()
        #测试集
        test=[101,20]
        #knn分类
        test_class=classify0(test,group,labels,3)
        print(test_class)

输出结果为`'B'`

当数据为n维的时候，可以用欧式距离计算：  
![在这里插入图片描述][20201026203225999.png_pic_center]

参考文献：

*  主要是看《机器学习实战》和《统计学习方法》
 *  代码参考这个[牛逼哄哄的博主][Link 1]，他基本上把上面两本书的理论和代码都总结到他的网站里面，特别详细，超级棒！

[20201026203225999.png_pic_center]: /images/20221122/ea07d75ac341484b8f4a1010ca97eddd.png
[Link 1]: https://cuijiahua.com/blog/2017/11/ml_1_knn.html