数据挖掘-KNN-K最近邻算法

小咪咪 2022-05-20 20:35 250阅读 0赞

### 1. 算法核心思想： ###

通过计算每个训练样本到待分类样本的距离，选取和待分类样本的距离最近的 K 个训练样本，K个样本中那个类别的训练样本占据着多数， 则表明待分类的样本就属于哪一个类别。

KNN算法在类别的决策中， 只与极少数的相邻样本相关。因此，对于类别的样本交叉或重叠较多的待分类样本集来说， KNN较其他算法较为适合。KNN算法的结果很大程度取决于K的选择。

K值得取值一般低于训练数据样本数的平方根

1.1：欧式距离，曼哈顿距离和余弦距离：

![70][]

上图分别为 欧式距离， 曼哈顿距离和余弦距离

1.欧式距离又称**欧几里得距离**或**欧几里得度量**（Euclidean Metric），以空间为基准的两点之间最短距离 ：![70 1][]

2.曼哈顿距离又称**马氏距离**（Manhattan distance），还见到过更加形象的，叫出租车距离的。

![70 2][]

余弦距离，也称为余弦相似度，是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量。

向量，是多维空间中有方向的线段，如果两个向量的方向一致，即夹角接近零，那么这两个向量就相近。而要确定两个向量方向是否一致，这就要用到余弦定理计算向量的夹角。

![70 3][]

采用哪种距离度量方法对最终结果有很大影响。例如，你的数据集有很多特征，但是如果任  
意一对个体之间的欧氏距离都相等，那么你就没法通过欧氏距离进行比较了！曼哈顿距离在某些  
情况下具有更高的稳定性，但是如果数据集中某些特征值很大，用曼哈顿距离的话，这些特征会  
掩盖其他特征间的邻近关系。最后，再来说说余弦距离，它适用于特征向量很多的情况，但是它  
丢弃了向量长度所包含的在某些场景下可能会很有用的一些信息。 [from：blog][from_blog]

>  **对于k值的选择**，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值。
> 
> 　　选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；  
> 　　选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

### 2.其算法的描述为： ###

1）计算测试数据与各个训练数据之间的距离；

2）按照距离的递增关系进行排序；

3）选取距离最小的K个点，选择 k 个样本点；

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

5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。

### 3.算法实现 ###

#coding=gbk
    import numpy as np
    import operator
    import pandas as pd
    import matplotlib.pyplot as plt
    def createDateset():    #创建数据集
        dataset =np.array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
        labels = ['A','A','B','B']
        return dataset,labels 
    
    # dataset =array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
    # print(dataset.shape)    #(4, 2)
    # print(dataset.shape[0])     #4    输出有4组数据,shape[1]返回数组的列数
    
    a = np.array([0,1,2])
    b = np.tile(a,(2,2))
    print(b)
    # [[0 1 2 0 1 2]        #将a 看做是一个整体，打印出2行2列的数据
    #  [0 1 2 0 1 2]]
    print(b.sum(axis = 1))  #[6 6] 输出每一列的和
    
    #定义一个函数KNN
    def classify(input, dataset, labels, k):
        datasize = dataset.shape[0]
        #计算欧式距离
        diffMat = np.tile(input, (datasize,1)) - dataset    #将输入的数据与样本数据相减
        sqdmax = diffMat ** 2
        
        #计算每个样本与输入数据的距离的平方和，按列求和
        sqdDistance = sqdmax.sum(axis =1 )
        #取根号.得到一列的数组，得到每个数据点与输入数据点的欧式距离
        distances = sqdDistance ** 0.5
        print('distances:', distances)
        
        sortDistances = distances.argsort() #依据元素的大小按索引进行排序，
        print('sortDistances:',sortDistances)
        
        classCount = {} #创建字典
        for i in range(k):
            #取出前k项的类别
            voteLabel = labels[sortDistances[i]]
            print('第%d个的类别是：',i,voteLabel)  #找出输入点距离最近点的label
            
            #计算类别的次数
            #    dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
            classCount[voteLabel] = classCount.get(voteLabel, 0)+ 1
            
            #key=operator.itemgetter(1)根据字典的值进行排序
            #key=operator.itemgetter(0)根据字典的键进行排序
            sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
            
            print('sortedClassCount:',sortedClassCount)
            return  sortedClassCount[0][0]
    
    #if __name__ == '__main__':
    
    # labels = np.array(labels).reshape(4,1)
    # print(dataset)
    # print(labels)
    # data = np.concatenate([dataset,labels],axis = 1)
    # print(data)
    # plt.axis([0,3,0,3])
    # plt.scatter(data[:2,0],data[:2,1],color ='red', marker='o', label='A')
    # plt.scatter(data[2:,0],data[2:,1],color ='green', marker='+', label='B')
    # plt.legend(loc =2)
    # plt.show()
    dataset,labels = createDateset()
    input = [1.1,2.4]
    test_class = classify(input, dataset, labels, 3)
    print(test_class)  
    # distances: [0.41231056 2.30217289 1.41421356 1.36014705]
    # sortDistances: [0 3 2 1]
    # 第%d个的类别是： 0 A
    # sortedClassCount: [('A', 1)]
    # A        #代表新的样本是属于A类的
    
    print('---------')
    print("dict.get()方法和operator.itemgetter()方法的练习")        
    demo_k =['a','b','a','a']
    d = {}
    for i in demo_k:
       d[i] = d.get(i,0)+1
    print(d)    # 输出 {'a': 3, 'b': 1}   ,可用于计算，类别的次数  
    sorted_d = sorted(d.items(), key = operator.itemgetter(1),reverse =False)   #将值按从小到大进行排序
    print(sorted_d)  #[('b', 1), ('a', 3)]
    print(sorted_d[0][0]) #b  得到类别

### 4.算法的优缺点： ###

![70 4][]

[更完整的KNN 的优缺点：][KNN]

> **KNN的主要优点有：**
> 
> 　　　　1） 理论成熟，思想简单，既可以用来做分类也可以用来做回归
> 
> 　　　　2） 可用于非线性分类
> 
> 　　　　3） 训练时间复杂度比支持向量机之类的算法低，仅为O(n)
> 
> 　　　　4） 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
> 
> 　　　　5） 由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合
> 
> 　　　　6）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分
> 
> **KNN的主要缺点有：**
> 
> 　　　　1）计算量大，尤其是特征数非常多的时候
> 
> 　　　　2）样本不平衡的时候，对稀有类别的预测准确率低
> 
> 　　　　3）KD树，球树之类的模型建立需要大量的内存
> 
> 　　　　4）使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢
> 
> 　　　　5）相比决策树模型，KNN模型可解释性不强

scikit-learn 中KNN 的参数：

neighbors.KNeighborsClassifier(n_neighbors=5,
     weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, 
    metric=’minkowski’, metric_params=None, n-jobs=1)

1. n\_neighbors 就是 kNN 里的 k，就是在做分类时，我们选取问题点最近的多少个最近邻。

2.weights 是在进行分类判断时给最近邻附上的加权，默认的 'uniform' 是等权加权，

'distance' 选项是按照距离的倒数进行加权，也可以使用用户自己设置的其他加权方法。

3.algorithm 是分类时采取的算法，有 'brute'、'kd\_tree' 和 'ball\_tree'。kd\_tree 的 kd 树，而 ball\_tree 是另一种基于树状结构的 kNN 算法，brute 则是最直接的蛮力计算。根据样本量的大小和特征的维度数量，不同的算法有各自的优势。默认的 'auto' 选项会在学习时自动选择最合适的算法，所以一般来讲选择 auto 就可以。

4.leaf\_size 是 kd\_tree 或 ball\_tree 生成的树的树叶（树叶就是二叉树中没有分枝的节点）的大小。在 kd 树文章中我们所有的二叉树的叶子中都只有一个数据点，但实际上树叶中可以有多于一个的数据点，算法在达到叶子时在其中执行蛮力计算即可。对于很多使用场景来说，叶子的大小并不是很重要，我们设 leaf\_size=1 就好。

5.metric 和 p，是距离函数的选项，如果 metric ='minkowski' 并且 p=p 的话，计算两点之间的距离就是

d((x1,…,xn),(y1,…,yn))=(∑i=1n|xi−yi|p)1/p

一般来讲，默认的 metric='minkowski'（默认）和 p=2（默认）就可以满足大部分需求。其他的 metric 选项可见[说明文档][Link 1]。metric\_params 是一些特殊 metric 选项需要的特定参数，默认是 None。

6.n\_jobs 是并行计算的线程数量，默认是 1，输入 -1 则设为 CPU 的内核数。

函数方法：

neighbors.KNeighborsClassifier.fit(X,y)

对数据集进行预测

neighbors.kNeighborsClassifier.predict(X)

输出预测概率：

neighbors.kNeighborsClassifier.predict_proba(X)

正确率打分

neighbors.KNeighborsClassifier.score(X, y, sample_weight=None)

--------------------

![20200423152314655.PNG][]

![70 5][]

#coding=gbk
    #KNN算法实现对电影类型的分类
    import numpy as np
    from sklearn import neighbors
    knn = neighbors.KNeighborsClassifier()
    data = np.array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]])
    labels = ['A','A','A','B','B','B']
    labels = np.array(labels)
    knn.fit(data,labels)
    c= knn.predict([[18,90]])  #看清楚括号的顺序
    print(c)        
    print(knn.predict_proba([[18,90]]))
    # ['A']预测为浪漫的电影
    # [[0.6 0.4]]

[70]: /images/20220521/1336251a9cc74bf2b212db0b07b3bffe.png
[70 1]: /images/20220521/212c22599dac4b3492fc1ab013d0989f.png
[70 2]: /images/20220521/027720b12f6e4de2828f01c7af06b0d2.png
[70 3]: /images/20220521/c80aa858ec57414583e5233c4ea938f1.png
[from_blog]: https://blog.csdn.net/qingyang666/article/details/61919381
[70 4]: /images/20220521/d9a063d11f92472d90c8316c93c65d81.png
[KNN]: http://www.cnblogs.com/pinard/p/6061661.html
[Link 1]: http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html
[20200423152314655.PNG]: /images/20220521/c848e298f749464b8a1a09d1f06dbc68.png
[70 5]: /images/20220521/7b39edfdb77b4db7af07c9699680993c.png