数据挖掘面试题之KNN
KNN模型引入
与决策树功能类似，既可以针对离散因变量做分类，又可以对连续因变量做预测，其核心
思想就是比较已知y值的样本与未知y值样本的相似度，然后寻找最相似的k个样本用作未知样
本的预测。
K最近邻算法，顾名思义就是搜寻最近的k个已知类别样本用于未知类别样本的预测。“最
近”的度量就是应用点之间的距离或相似性。距离越小或相似度越高，说明它们之间越近，关
于样本间的远近度量在后面会介绍。“预测”，对于离散型的因变量来说，从k个最近的已
知类别样本中挑选出频率最高的类别用于未知样本的判断；对于连续型的因变量来说，则是
将k个最近的已知样本均值用作未知样本的预测。
KNN模型步骤
- 确定未知样本近邻的个数k值。
- 根据某种度量样本间相似度的指标（如欧氏距离）将每一个未知类别样本的最近k个已
- 知样本搜寻出来，形成一个个簇。
- 对搜寻出来的已知样本进行投票，将各簇下类别最多的分类用作未知样本点的预测。
最佳k值选择
1、是设置k近邻样本的投票权重，假设读
者在使用KNN算法进行分类或预测时设置的k值比较大，担心模型发生欠拟合的现象，一个简
单有效的处理办法就是设置近邻样本的投票权重，如果已知样本距离未知样本比较远，则对
应的权重就设置得低一些，否则权重就高一些，通常可以将权重设置为距离的倒数；
2、另一种是
采用多重交叉验证法，该方法是目前比较流行的方案，其核心就是将k取不同的值，然后在每
种值下执行m重的交叉验证，最后选出平均误差最小的k值。当然，还可以将两种方法的优点相
结合，选出理想的k值
相似度的度量方法
欧式距离
曼哈顿距离
余弦相似度
杰卡德相似系数
近邻样本的搜寻方法
1，暴力搜寻法
针对某未知样本，计算它与所以已知样本之间的距离，然后从中挑选出最近的k个样本，再基于这k个样本进行投票，将票数最多的类别作为预测结果
2，k-d树搜寻法
3，球形搜寻法
参数
最重要的两个参数：n_neighbors 和 weights