初识机器学习之kNN算法

k近邻(k-Nearest Neighbor,简称kNN)学习是一种常用的监督学习方法&＃xff0c;其工作机制非常简单&＃xff1a;给定测试样本&＃xff0c;基于某种距离度量找出训练集中与其最靠近的k个训练样本。然后基于这k个“邻居”的信息进行预测。通常在分类任务中可使用“投票法”&＃xff0c;即选择这k个样本中出现最多的类别标记作为预测结果&＃xff1b;在回归任务中可使用“平均法”&＃xff0c;即将这k个样本中的实值输出标记的平均值作为预测结果&＃xff1b;还可基于距离远近进行加权平均或加权投票&＃xff0c;距离越近的样本权重越大。kNN没有一个显示的训练过程。

如下图所示&＃xff0c;判断测试样本是正例还是反例&＃xff0c;虚线显示出等距线&＃xff1a;

测试样本在k&＃61;1或k&＃61;5时被判别为正例&＃xff0c;k&＃61;3时被判别为反例。可以看出k的选择至关重要。关于k值如何选择现在还有有一个定论。一般做法是多选几个k进行交叉验证。

　　k–近邻算法是一种非参数模型。简单来说&＃xff0c;参数模型(如线性回归、逻辑回归 等)都包含待确定的参数。训练过程的主要目的是寻找代价最小的最优参数。 参数一旦确定&＃xff0c;模型就完全固定了&＃xff0c;进行预测时完全不依赖于训练数据。非参数 模型则相反&＃xff0c;在每次预测中都需要重新考虑部分或全部训练(已知的) 数据。

kNN算法

优点&＃xff1a;
　　(1)简单且有效
　　(2)对数据的分布没有要求
　　(3)训练阶段很快
缺点&＃xff1a;
　　(1)不产生模型
　　(2)分类阶段很慢
　　(3)需要大量的内存
　　(4)名义变量和缺失值需要额外处理

 

遗留问题&＃xff1a;

1:kd树

2:kd树搜索