最简单的分类算法之一：KNN（原理解析+代码实现）

KNN（K- Nearest Neighbor），即K最邻近算法，是数据挖掘分类技术中最简单的方法之一。简单来说，它是根据“最邻近”这一特征来对样本进行分类。

1、大致了解KNN

一提到KNN，很多人都想起了另外一个比较经典的聚类算法K_means，但其实，二者之间是有很多不同的，这两种算法之间的根本区别是，K_means本质上是无监督学习而KNN是监督学习，Kmeans是聚类算法而KNN是分类（或回归）算法。有关K_means的具体思想以及实现可以简单参考：机器学习之K_means（附简单手写代码）

古语说得好，物以类聚，人以群分；近朱者赤，近墨者黑。这两句话的大概意思就是，你周围大部分朋友是什么人，那么你大概率也就是这种人，这句话其实也就是KNN算法的核心思想。

2、原理分析

既然是近朱者赤，近墨者黑，想要衡量二者的差距，我们首先想到的是他们走得近不近，他们之间的距离大概为多少。因此，距离无论是在聚类还是分类中，都具有比较重要的意义， 这里也就拓展讲一下。
在以下数学公式当中，我们认定训练集为：$[(x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3}),...,(x_{n},y_{n})]$[(x1​,y1​),(x2​,y2​),(x3​,y3​),...,(xn​,yn​)]，其中每一个$x_{i}$xi​都具有n个特征即：$x_{i}=(x_{i}^{1},x_{i}^{2},x_{i}^{3},...,x_{i}^{n})$xi​=(xi1​,xi2​,xi3​,...,xin​)，$y_{i}$yi​是类别标签。（这里两个n纯属巧合，应该能理解）

2.1一些数学知识

1. 欧几里得距离（Euclidean Distance）
   欧几里得距离是运用最广的一种计算距离的方式，我们从小在课本上接触到的也是这个东西，它衡量的是多维空间中两点之间的绝对距离，表达式如下：
   
   很好理解，就不做过多解释。

2. 明可夫斯基距离（Minkowski Distance）
   明可夫斯基距离是一种对多种距离的概括性描述，其表达式如下：
   
   为什么说是一种概括性描述，因为当p=2时，明氏距离其实就是欧氏距离。

3. 曼哈顿距离（Manhattan distance）
   当p=1时，得到绝对值距离，也称曼哈顿距离，表达式如下：
   

4. 切比雪夫距离（Chebyshev Distance）
   当p->∞时，得到切比雪夫距离。表达式如下：
   

5. 马氏距离(Mahalanobis distance)
   马氏距离表示点与一个分布之间的距离。 它是一种有效的计算两个未知样本集的相似度的方法。一个均值为μ，协方差矩阵为Σ的多变量向量，它的马氏距离为：
   
   其中-1表示取逆矩阵，斜上方一点表示取转置，其实这个公式有点似曾相识，我们在概率生成模型中推导多维正态分布的极大似然估计时经常看到这个表达式，具体可参考：概率生成模型与朴素贝叶斯

2.2算法思想

总得来说，KNN算法思想可以用一句话概括：如果一个样本在特征空间中的K个最相似（即特征空间中最邻近，用上面的距离公式描述）的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
算法步骤可以大致分为如下几个步骤：

1. 计算想要分类的点到其余点的距离
2. 按距离升序排列，并选出前K（KNN的K）个点，也就是距离样本点最近的K个点
3. 加权平均，得到答案

这里大致解释一下三个步骤，比如我要预测x是属于哪一类，训练集里面有很多数据，我先算出x到其他所有点之间的距离，取前K个距离样本比较小的点，然后我们发现这K个点当中有5个属于class 1，K-5个属于class 2 。那我们就直接比较5与K-5的大小然后判断x属于哪一类吗？这显然是是不合理的。
这里毫无意外也需要体现加权的思想。如果那五个属于class 1的点相比于另外K-5个属于class 2的点，它们距离样本点更近，根据近朱者赤，近墨者黑的原则，毫无疑问样本点x属于class 1的可能性更大，也即是说，这五个点在最终决策当中应当占据更大的比重。
那么怎么来体现这种加权呢？我们很容易想到距离占总距离的比重，但是这样的话距离大的反而权重较大，因此我们需要用1来减去该权重，得到最终的权重。我们把K个点当中属于class 1的权重加起来，再把属于class 2的权重加起来，谁的结果大，x就属于哪一类。

3.代码实现

数据集长这样：（截取了一部分）

源码：

from sklearn.neighbors import KNeighborsClassifier
import numpy as np
import random
import pandas as pd

def knn():
    K = 8
    data=pd.read_csv(r"Prostate_Cancer.csv")
    n = len(data) // 3
    test_set = data[0:n]
    train_set = data[n:]
    train_set = np.array(train_set)
    test_set = np.array(test_set)
    A = [i for i in range(0, len(train_set))]
    B = [i for i in range(2, 10)]
    C = [i for i in range(n)]
    D = [1]
    x_train = train_set[A]
    x_train = x_train[:, B]
    y_train = train_set[A]
    y_train = y_train[:, D]
    x_test = test_set[C]
    x_test = x_test[:, B]
    y_test = test_set[C]
    y_test = y_test[:, D]
    # 训练模型
    model = KNeighborsClassifier(n_neighbors=K)
    model.fit(x_train, y_train)
    score = model.score(x_test, y_test)
    print("准确率为:", score)

if __name__=='__main__':
    knn()