python K近邻算法的kd树实现

k近邻算法的介绍

k近邻算法是一种基本的分类和回归方法，这里只实现分类的k近邻算法。

k近邻算法的输入为实例的特征向量，对应特征空间的点；输出为实例的类别，可以取多类。

k近邻算法不具有显式的学习过程，实际上k近邻算法是利用训练数据集对特征向量空间进行划分。将划分的空间模型作为其分类模型。

k近邻算法的三要素

下面对三要素进行一下说明：

1.欧氏距离即欧几里得距离，高中数学中用来计算点和点间的距离公式；

2.k值选择：k值选择会对k近邻法结果产生重大影响，如果选择较小的k值，相当于在较小的邻域中训练实例进行预测，这样有点是“近似误差”会减小，即只与输入实例较近（相似）的训练实例才会起作用，缺点是“估计误差”会增大，即对近邻的实例点很敏感。而k值过大则相反。实际中取较小的k值通过交叉验证的方法取最优k值。

3.k近邻法的分类决策规则往往采用多数表决的方式，这等价于“经验风险最小化”。

k近邻算法的实现：kd树

实现k近邻法是要考虑的主要问题是如何退训练数据进行快速的k近邻搜索，当训练实例数很大是显然通过一般的线性搜索方式效率低下，因此为了提高搜索效率，需要构造特殊的数据结构对训练实例进行存储。kd树就是一种不错的数据结构，可以大大提高搜索效率。

本质商kd树是对k维空间的一个划分，构造kd树相当与使用垂直于坐标轴的超平面将k维空间进行切分，构造一系列的超矩形，kd树的每一个结点对应一个这样的超矩形。

kd树本质上是一棵二叉树，当通过一定规则构造是他是平衡的。

下面是过早kd树的算法：

以下是kd树的python实现

准备工作

#读取数据准备def file2matrix(filename):  fr = open(filename)  returnMat = []     #样本数据矩阵  for line in fr.readlines():    line = line.strip().split('/t')    returnMat.append([float(line[0]),float(line[1]),float(line[2]),float(line[3])])  return returnMat  #将数据归一化，避免数据各维度间的差异过大def autoNorm(data):  #将data数据和类别拆分  data,label = np.split(data,[3],axis=1)  minVals = data.min(0)   #data各列的最大值  maxVals = data.max(0)    #data各列的最小值  ranges = maxVals - minVals  normDataSet = np.zeros(np.shape(data))  m = data.shape[0]  #tile函数将变量内容复制成输入矩阵同样大小的矩阵  normDataSet = data - np.tile(minVals,(m,1))      normDataSet = normDataSet/np.tile(ranges,(m,1))  #拼接  normDataSet = np.hstack((normDataSet,label))  return normDataSet