k近邻法算法原理数学公式案例及python代码

k近邻法算法原理数学公式案例及python代码

k近邻法(k-nearest neighbor,k-NN)是一种基本的分类与回归方法，在此主要讨论分类问题中的k近邻法。

k近邻法算法思想： 假设给定一个训练数据集，kNN中输入为实例的特征向量，对应于空间中的点；输出为实例的类别，可以有多类。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，kNN不具有显式的学习过程。kNN实际上是利用训练数据集对特征向量空间进行划分，并作为其分类的"模型"，k值的选择、距离度量及分类决策规则是kNN的三个基本要素。该算法是由Cover和Hart于1968年提出的。

1 k近邻法(kNN)

​ 此处先给出kNN算法，之后再一步步讨论其细节

k近邻法的特殊情况是$k=1$的情况，称为最近邻算法。对于输入的实例点(特征向量)$x$，最近邻法将训练数据集中与$x$最接近的类作为$x$的类。

2 k近邻模型

本节介绍模型中的三个基本要素–距离度量、k值选择和分类决策规则。

​ 特征空间中，对每个训练实例点 x i x_{i} xi​,距离该点比其他点更近的所有点组成一个区域，叫做单元(cell)。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。kNN将实例点 x i x_{i} xi​的类 y i y_{i} yi​作为其单元所有点的类标记(class label)。这样，每个单元的实例点的类别是确定的。如下图所示：

(1)距离度量

​ 特征空间中两个实例点的距离是两个实例点相似程度的反应。$k$近邻模型的特征空间一般是n维实数向量空间 R n R^{n} Rn。使用的距离是欧式距离，也可以是其他距离，如更一般的 L p L_{p} Lp​距离( L p L_{p} Lp​ distance)或Minkowski距离(Minkowski distance)。

​ 设特征空间$\chi$ 是n维实数向量空间 R n R^{n} Rn， x i , x j ∈ χ x_{i},x_{j} \in \chi xi​,xj​∈χ, x i = ( x i ( 1 ) , x i ( 2 ) , . . . , x i n ) ( T ) x_{i}=(x_{i}^{(1)},x_{i}^{(2)},...,x_{i}^{n})^{(T)} xi​=(xi(1)​,xi(2)​,...,xin​)(T), x j = ( x j ( 1 ) , x j ( 2 ) , . . . , x j ( n ) ) x_{j}=(x_{j}^{(1)},x_{j}^{(2)},...,x_{j}^{(n)}) xj​=(xj(1)​,xj(2)​,...,xj(n)​), x i x_{i} xi​和 x j x_{j} xj​的 L p L_{p} Lp​距离定义为
L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p ) L_{p}(x_{i},x_{j})=(\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|^{p})^ \frac{1}{p}) Lp​<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！