k近邻模型（k-Nearest Neighbors）

1.三个基本要素：距离度量、k值的选择、分类决策规则

   当基本要素确定后，对于新的输入实例，它所属的类唯一确定

3.单元：对于每个训练点x，距离该点比其他点更近的所有点组成的区域

             每个训练点有一个单元

4.距离度量：n维实数向量空间R^n，使用的距离是欧氏距离，也可以是其他距离（曼哈顿距离、Lp距离等）

  （由不同距离度量所确定的最近邻点是不同的）

   欧氏距离：

 

 

 

5.k值的选择：会对结果产生重大影响

6.分类决策规则：

  多数表决：k近邻多数类决定

构造kd树

kd树是一种二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域

方法：通常选择坐标轴上的中位数为切分点

 

搜索kd树