KNN算法（一）
source link: https://ylhao.github.io/2018/05/04/174/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
- 输入空间 χ⊆Rnχ⊆Rn
- 训练集 T=(x1,y1),(x2,y2),⋯,(xN,yN)T=(x1,y1),(x2,y2),⋯,(xN,yN)
- 输出空间 γ=c1,c2,⋯,ckγ=c1,c2,⋯,ck
K近邻法基本思想
K 近邻法并不具有显式的学习过程，K 近邻法实际上是利用训练集数据对特征空间进行划分，并作为其分类的“模型”。给定一个训练集，对于新的输入实例，首先在训练集中找到与该实例最近的 K 个实例，然后统计这 K 个实例的多数属于哪个类，就把该实例划分为哪个类。
K近邻法的三个要素
经过上面的讨论，我们可以总结出 K 近邻法的三个要素：
- K 值的选择
- 距离的度量
- 分类决策的规则
K 值的选择
首先考虑一个极端情况，当 K 值为 1 时，此时的 K 近邻算法又称为最邻近算法，这种情况下，很容易发生过拟合，很容易将一些噪声学习到模型中（很容易将实例判定为噪声类别）。
我们再考虑另一种极端情况，当 K 值为 N 时，此时不管你输入的实例是什么类别，最终模型都会将该实例判定为模型中实例最多的类别。也就是这种情况下，很容易发生欠拟合。
通过以上两个极端情况，可以理解到 K 值越大，模型越简单，鲁棒性越好（容错率越高），越容易欠拟合。
距离的度量
- 闵可夫斯基距离
- 曼哈顿距离
- 切比雪夫距离
设有两个向量：
xi=(x(1)i,x(2)i,x(3)i,⋯,x(n)i) xj=(x(1)j,x(2)j,x(3)j,⋯,x(n)j)xi=(xi(1),xi(2),xi(3),⋯,xi(n))xj=(xj(1),xj(2),xj(3),⋯,xj(n))
闵可夫斯基距离的定义如下：
d(xi,xj)=(n∑l=1|x(l)i−x(l)j|p)1pd(xi,xj)=(∑l=1n|xi(l)−xj(l)|p)1p
当 p=1p=1 时就是曼哈顿距离，当 p=2p=2 时就是欧式距离，当 p=∞p=∞ 时就是切比雪夫距离，这里我们使用欧式距离进行度量。
分类决策的规则
这里用的是多数表决的决策规则，很直观~，关于对多数表决规则的解释可以参考《统计学习方法》这本书的 3.2.4 小节（多数表决规则等价于经验风险最小化）。
特征归一化
为了让各个特征在分类的时候同等重要，我们需要将各个特征进行归一化。
- 《统计学习方法》——李航
- 一文搞懂k近邻（k-NN）算法（一） —— 忆臻
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以在文章下方的评论区进行评论，也可以邮件至 [email protected]
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK