简单理解k近邻(kNN)算法：理论讲解+实战操作以及KNeighborsClassifier参数深度剖析 - 从入门到精通(第1部分：k-NN基本概念)

k近邻法是基本且简单的分类与回归方法，这里只讨论分类方法，利用数据集对特征向量空间进行划分，可以进行多分类。如下图：
三角形与矩形分别代表两类数据，标签已知。现要对新输入的为分类点(绿色)进行分类，k-NN的做法是寻找与该绿点相邻最近的k个点(k-NN算法的k的含义，图中的距离为欧式距离)，然后通过多数表决的方式把绿点划分到这k个最近点出现频数最高的类。例如如果k取3，则绿点最近的3个点中频数最高为三角形类，所以归为三角形类；若k取5，则距离绿点最近的5个点中频数最高为矩形类，所以归绿点为矩形类。

1.1 模型

输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}, 实例特征向量$x$
总共N个样本，$x_i\in \mathcal{X}\subseteq R^n$为实例的特征向量， y i ∈ Y = { c 1 , c 2 , . . . , c K } 为 实 例 的 类 别 , i = 1 , 2 , . . . , N y_i \in \mathcal{Y}=\{c_1,c_2,...,c_K\}为实例的类别, i=1,2,...,N yi​∈Y={c1​,c2​,...,cK​}为实例的类别,i=1,2,...,N
输出：实例$x$所属的类$y$
step1:根据给定的距离度量，在训练集T中找出与$x$最近的k个点，涵盖这k个点的x的邻域记为$N_k(x);$
step2:在$N_k(x)$中根据决策规则（如多数表决）决定$x$的类别$y$
$$y=\underset{c_j}{\mathrm{argmax}}\sum _{x_i\subseteq N_k(x)}I(y_i=c_j)，i=1,2,...,N,j=1,2,...,K；$$
其中I为指示函数

1.2 学习策略

$$\underset{c_j}{\max }\sum _{x_i\subseteq N_k(x)}I(y_i=c_j)，i=1,2,...,N,j=1,2,...,K；$$

1.3 学习算法

学习算法即如何求出以上的学习策略的最大值，用的是多数表决法，即将$c_1到c_K$得到的指示函数和的值排序，选择最大值对应的类别$c^{\ast }$作为输出。假设$c^{\ast }$为最大值对应的类别，那么得到的最终模型为：
$$y=c^{\ast }$$

1.4 距离度量

从以上公式可以看出，关键是确定输入实例$x$的邻域$N_k(x)$，而这个邻域又由两个方面决定，一个就是如何计算各点与输入实例$x$的距离（怎么判断离某些点近不近)？
$$L_p\left(x_i,x_j\right)={\left(\sum _{i=1}^n{\left|x_i^{(i)}-x_j^{(l)}\right|}^p\right)}^{\frac{1}{p}}$$

• $p=1$ 曼哈顿距离
• $p=2$ 欧氏距离
• $p=\infty$ 切比雪夫距离
  一般使用欧式距离。

1.5 k值选择

知道了怎么判断点之间离的近不近，那么要确定邻域还得需要知道该邻域包含多少个“最近”点,这就是k值决定的，该邻域会包含k个离输入实例最近的点。k值越小，模型越复杂，过拟合的风险越大，当k=1时成为最近邻模型。而k值越大，模型越简单，最极端情况就是k=N，这时直接把样本中出现频数最高的类当成所有输入实例的类。

距离的度量以及k值作为超参数，可以通过验证集来选择合适的超参数。