kd tree (k-dimensional tree)

• Assuming that the training set will remain relatively stable it is possible to speed up the prediction speed of a nearest neighbor model by investing in some one-off computation to create an index of the instances that enables efficient retrieval of the nearest neighbors

实例被分到两个子区域；此过程直到子区域内没有实例时终止。 实例将被保存在对应的节点上。
依次选择坐标轴做切分，切分点选择为训练实例在选定坐标轴上的中位数。