1. 算法:用kd树的k近邻搜索
输出:
已构造的kd树
目标点x
输出:
x的最近邻
在kd树中找出包含目标点x的叶结点:从根结点出发,递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标,则移动到左子节点,否则移动到右子节点。直至子结点为叶结点为止。
以此结点为当前最近点
递归地向上回退,在每个结点进行以下操作:
a) 如果该结点保存的实例点比当前最近点距离目标点更近,则以该实例点为“当前最近点”。
b) 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一个子结点对应的区域是否有更近的点。具体地,检查另一个子结点对应的区域是否以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交,可能在另一个子结点对应的区域内存在距目标点更近的点,移动到另一个子结点。接着,递归的进行最近邻搜索。如果不相交,向上回退。
当回退到根结点时搜索结束。最后的“当前最近点”即为x的最近邻点。
代码:
def isLeaf(node):
return True
# 在kd树中找出包含目标点x的叶结点
def findLeaf(node, depth, x):
# 从根结点出发,递归地向下访问kd树
while True:
feature = node['feature']
# 若目标点x当前维的坐标小于切分点的坐标
if x[feature] < node['data'][feature]:
# 则移动到左子节点
subnode = node['left']
# 否则移动到右子节点
else:
subnode = node['right']
# 直至子结点为叶结点为止
if subnode['data'].shape[0] == 0:
return node
node = subnode
def distance(A, B):
return np.linalg.norm(A - B)
def check(feature, value, x):
return np.abs(x[feature] - value[feature])
def isSame(a, b):
return a[0] == b[0] and a[1] == b[1]
def findAnother(node):
parent = node['parent']
if isSame(node['data'], parent['left']['data']):
return parent['right']
else:
return parent['left']
def search(root, x):
# 在kd树中找出包含目标点x的叶结点
current = findLeaf(root, 0, x)
# 以此结点为当前最近点
nearest = current['data']
currentDistance = distance(nearest, x)
# 递归地向上回退,在每个结点进行以下操作
# 当回退到根结点时搜索结束
while not isSame(current['data'], root['data']):
parent = current['parent']
dis = distance(parent['data'], x)
# 如果该结点保存的实例点比当前最近点距离目标点更近
if dis < currentDistance:
# 则以该实例点为“当前最近点”
nearest = parent['data']
currentDistance = dis
# 检查该子结点的父结点的另一个子结点对应的区域是否有更近的点
# 即目标结点到平面feature=value的距离
# 如果相交,可能在另一个子结点对应的区域内存在距目标点更近的点
if check(parent['feature'], parent['data'], x) < currentDistance:
# 递归的进行最近邻搜索
newnode, dis = search(findAnother(current), x)
if dis < currentDistance:
nearest = newnode
currentDistance = dis
current = parent
return nearest, currentDistance