文件名称：统计学习方法 kd树实现
文件大小：4KB
文件格式：PY
更新时间：2020-10-19 04:02:30
统计学习方法 kd树 knn
包含kd树的建立以及搜索两部分程序，具体算法过程如下： 给定一个目标点，搜索其最近邻，首先找到包含目标点的叶节点，然后从该叶节点出发，依次退回到其父节点，不断查找是否存在比当前最近点更近的点，直到退回到根节点时终止，获得目标点的最近邻点。如果按照流程可描述如下： 1. 从根节点出发，若目标点x当前维的坐标小于切分点的坐标，则移动到左子节点，反之则移动到右子节点，直到移动到最后一层叶节点。 2. 以此叶结点为“当前最近点” 3. 递归的向上回退，在每个节点进行如下的操作： a.如果该节点保存的实例点距离比当前最近点更小，则该点作为新的“当前最近点” b.检查“当前最近点”的父节点的另一子节点对应的区域是否存在更近的点，如果存在，则移动到该点，接着，递归地进行最近邻搜索。如果不存在，则继续向上回退 4. 当回到根节点时，搜索结束，获得最近邻点