##Ｋ近邻法

k近邻（k-NN）算法

概念

k近邻算法是一种基本分类和回归方法 即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。（这就类似于现实生活中少数服从多数的思想）

三要素

• K值的选择(在应用中，取一个较小的Ｋ值，通常采用交叉验证法来选取最优的Ｋ值)
• 距离度量（如欧式距离）
• 分类决策规则(如多数表决)

算法

根据样本数量 N(i.e. n_samples) 和维度(例如. n_features).选择算法

• brute-force(暴力搜索)
  • 优点: 简单,快速,小数据集 (N小于30)表现好
  • 缺点:数据量大,需要全部扫描数据
• KD树
  • 优点: 解决效率低下的暴力计算方法, (D<20) 近邻搜索非常快
  • 缺点:高维数据不能胜任
• ball树(球树递归地将数据划分为由质心C和半径r定义的节点)
  • 优点:可以处理高维数据
  • 缺点:构建复杂

查询点的邻居数(k)

• Brute force算法基本不受 k值的影响
• Ball tree and KD tree算法查询时间变慢，随着 k的增大