【ML算法】监督学习——KNN算法

系统管理员 2022-06-05 06:19 248阅读 0赞

## 前言 ##

好久没有更新博客啦，罪过罪过，最近生病了，一直在休养，希望广大程序员朋友们一定要注意身体，少熬夜呀～今天又重新温习了一边KNN算法，整理出这篇文章。

## 算法介绍 ##

KNN（k-nearest neighbor，k近邻）是一种基本的分类与回归算法，是监督学习算法，这个算法并不具有显示的学习过程，其输入为特征向量，输出为实例类别，输出的类别可以为多类，最终通过多数表决的方式进行预测。k值的选择、距离测度和分类决策规则是KNN的三个基本要素。  
输入：训练数据集为T

T=\{ (x1,y1),(x2,y2),⋯,(xN,yN)\}  T = \{ ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) \}

其中,  xi∈χ⊆Rn  x i ∈ χ ⊆ R n  为特征向量，  yi∈Y=\{ c1,c2,⋯,cK\}  y i ∈ Y = \{ c 1 , c 2 , ⋯ , c K \}  为实例类别，  i=1,2,3,⋯,N  i = 1 , 2 , 3 , ⋯ , N  。  
输出：实例x所属类y。  
（1）根据距离测度，在训练集T中找到与x最接近的k个点，涵盖这k个点的x的领域记作  Nk(x)  N k ( x )  ;  
（2）在  Nk(x)  N k ( x )  中根据分类决策规则决定x的类别y：

y=argmax∑xi∈N−K(x)I(yi=cj),i=1,2,⋯,N;j=1,2,⋯,K  y = a r g m a x ∑ x i ∈ N − K ( x ) I ( y i = c j ) , i = 1 , 2 , ⋯ , N ; j = 1 , 2 , ⋯ , K

其中，I为指示函数，当  yi=cj  y i = c j  时I为1，否则为0。

## K值的选择 ##

k值的选择会对算法结果产生重大影响。如果选择较小的k值，就意味着仅会选择很小的邻域点进行训练，换句话说，只有与输入较近的训练样本点才会对算法输出有影响，因此这种情况下学习的近似误差会很小，但是模型估计误差会很大，因为模型对距离较近的邻域的点很敏感，如果这些点中存在噪声，那么模型准确率会迅速下降，也就是说，小的k值就意味着较为复杂的模型，输出结果过于依赖邻域中的几个点，这样就容易发生过拟合。  
如果选择的k值较大，就意味着需要很大的邻域点进行训练，模型对于大多数点都具有依赖性，这种情况下，模型的估计误差会减小，但是近似误差会增大，因为训练的邻域中可能会有很多样本点的类别与输入不同，也就是说，大的k值就意味着较为简单的模型，输出结果会受到很多样本点的影响（其中可能有很大一部分样本点与输入并不属于同一类别），这样就容易发生欠拟合。  
特殊情况，如果令k=N，模型未考虑数据的多样性，输出结果永远都是模型中类别频数最大的项。  
在实际应用中，通常会选取较小的k值，然后通过交叉验证来减轻过拟合。

## 距离测度 ##

距离测度在KNN、聚类中经常会遇到，常见的有欧式距离、马氏距离、明氏距离、汉明距离、曼哈顿距离等，本文中介绍其中几种。  
空间中两个实例点的距离是两个点相似程度的反应。KNN中的特征空间一般为n维实数向量空间 Rn  R n  ,最常使用的是欧式距离，也可以使用 Lp  L p  距离。  
设特征空间 χ  χ  是n维实数向量空间 Rn  R n  , xi,xj∈χ,xi=(x1i,x2i,⋯,xni)T,xj=(x1j,x2j,⋯,xnj)T,xi,xj的Lp  x i , x j ∈ χ , x i = ( x i 1 , x i 2 , ⋯ , x i n ) T , x j = ( x j 1 , x j 2 , ⋯ , x j n ) T , x i , x j 的 L p  距离定义为：

Lp(xi,xj)=(∑l=1n|xli−xlj|P)1p,p≥1  L p ( x i , x j ) = ( ∑ l = 1 n | x i l − x j l | P ) 1 p , p ≥ 1

当p=1时，称为曼哈顿距离：

L1(xi,xj)=∑l=1n|xli−xlj|  L 1 ( x i , x j ) = ∑ l = 1 n | x i l − x j l |

当p=2时，称为欧式距离：

Lp(xi,xj)=(∑l=1n|xli−xlj|2)12  L p ( x i , x j ) = ( ∑ l = 1 n | x i l − x j l | 2 ) 1 2

当  p=∞  p = ∞  时，它是各个坐标距离的最大值：

L1(xi,xj)=maxl|xli−xlj|  L 1 ( x i , x j ) = m a x l | x i l − x j l |

## 分类决策规则 ##

KNN算法多采取多数表决原则，即哪个类别投票的频数多，样本点就属于哪个类别，假设分类的损失函数为0-1损失函数，分类函数为：

f:Rn→\{ c1,c2,⋯,cK\}  f : R n → \{ c 1 , c 2 , ⋯ , c K \}

那么，误差概率为：

P(Y≠f(X))=1−P(Y=f(X))  P ( Y ≠ f ( X ) ) = 1 − P ( Y = f ( X ) )