[分类] KNN算法

怼烎@ 2023-06-27 11:27 26阅读 0赞

# KNN算法 #

KNN，K-NearestNeighbor——K最近邻(不常用)

## 是什么? ##

是机器学习中有监督机器学习下的一种简单的分类算法.  
K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表.

## 做什么? ##

用来给待测样本分类.

## 怎么做? ##

knn的**核心思想**是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。  
简单地说我们认为’近朱者赤’,一个样本与其最近的几个样本所属类别相同.

所以用knn做分类的时候可以分为以下三步:

1.  设定一个k值(超参数)
2.  计算待测试样本和训练集中所有样本的距离
3.  选出的k个距离最近的样本
4.  统计前k个元素 所属类别的个数
5.  按照服从多数原则来决定样本值的类别

## 优点 ##

*  理论成熟，思想简单，既可以用来做分类也可以用来做回归
 *  可用于非线性分类
 *  训练时间复杂度比支持向量机之类的算法低，仅为O(n)
 *  和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
 *  由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合
 *  该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分

## 缺点 ##

*  计算量大，尤其是特征数非常多的时候
 *  样本不平衡的时候，对稀有类别的预测准确率低
 *  KD树，球树之类的模型建立需要大量的内存
 *  使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢
 *  相比决策树模型，KNN模型可解释性不强

## 实例 ##

### 简单实现 ###

""" knn 样本集 X = [[1,1],[1,1.5],[2,2],[4,3],[4,4]] Y =['A','A','A','B','B'] 测试样本: t=[3,2] 属于哪个类型 设k=3 步骤： 1.计算待测试样本和训练集中所有样本的距离 2.对距离排序 3.选择前k个最近的距离 4.统计前k个元素 所属类别的个数 5.选择类别数最大的类别 做为预测结果 """
    import numpy as np
    import operator
    X = np.array([[1,1],[1,1.5],[2,2],[4,3],[4,4]])
    Y = np.array(['A','A','A','B','B'])
    
    def knn_classify(x,y,k,test_sample):
        """ :param x: 输入数据 :param y: 真实值 :param k: 邻居的个数 :param test_sample: 待测试样本 :return: 待测试样本的类别 """
        # 1.计算待测试样本和训练集中所有样本的距离
        distance = np.sum((x-test_sample)**2,axis=1)**0.5
        #2.对距离排序
        sortedIndex = np.argsort(distance)
        #3.选择前k个最近的距离sortedIndex[:k]
        #4.统计前k个元素 所属类别的个数
        labelCount = { }
        for index in sortedIndex[:k]:
            label=y[index]
            labelCount[label]=labelCount.get(label,0)+1
        return sorted(labelCount.items(),key=operator.itemgetter(1),reverse=True)[0][0]
    
    
    if __name__=="__main__":
        result = knn_classify(X,Y,3,np.array([3,4]))
        print(result)

### sklearn实现 ###

import numpy as np
    from sklearn.neighbors import KNeighborsClassifier
    X = np.array([[1,1],[1,1.5],[2,2],[4,3],[4,4]])
    y = np.array(['A','A','A','B','B'])
    # 创建knn模型对象,给定k值
    knn_classify = KNeighborsClassifier(n_neighbors=3)
    # 训练模型
    knn_classify.fit(X,y)
    # 预测
    pred = knn_classify.predict([[3,4]])
    # 预测结果
    print(pred)
    # 有哪些可能的结果
    print(knn_classify.classes_)
    # 可能结果所对应的概率(预测结果就是概率最大的可能结果)
    print(knn_classify.predict_proba([[3,4]]))

## 知识储备 ##

### 距离公式 ###

距离有多种计算公式,简单的举几种有:  
欧几里得距离(平方和做开方)  
曼哈顿距离(独立计算各特征值差的绝对值再求和)  
切比雪夫距离(独立计算各特征值差的绝对值并取最大值)  
等等,具体可以参考 [机器学习中常见的距离公式 - WingPig - 博客园][- WingPig -]  
最常用的自然就是欧氏距离了.

[- WingPig -]: https://www.cnblogs.com/WingPig/p/9760882.html