database - 查找一组中最相似的匹配项

Question

我有一个动物数据库，每个动物都有许多属性，范围从 0 到 1——这些属性是大小、速度、毛羽等。给定一组输入属性和每种属性的权重，我需要在一组动物中找到“最接近”的匹配项。是否有一种算法可以在优于 O(n) 的时间内完成此操作？

我特别想做的是通过将游戏中的遗传算法与已经存在的动物相匹配，为游戏中的“动物”找到合适的纹理。 “最接近”是指属性差异的加权和最小的动物。数据库和权重在应用程序启动时已知，因此可以投入大量时间来准备数据。

我找到了根据用户偏好进行字符串匹配和产品匹配的算法，但要么我没有找到我要找的东西，要么我不明白如何将这些概念重新应用到我的困境中。也许有来自图论世界的东西可以帮助我？

如有任何帮助，我们将不胜感激!

Answer 1

您可以将项目视为高维空间中的点，并将它们全部插入到 BSP 树中，例如 k-d tree .要使用属性权重，只需将它们乘以相应的坐标:(w1*x, w2*y, ...)

准备:(来自wikipedia，python代码)

def kdtree(point_list, depth=0):

    if not point_list:
        return None

    # Select axis based on depth so that axis cycles through all valid values
    k = len(point_list[0]) # assumes all points have the same dimension
    axis = depth % k

    # Sort point list and choose median as pivot element
    point_list.sort(key=lambda point: point[axis])
    median = len(point_list) // 2 # choose median

    # Create node and construct subtrees
    node = Node()
    node.location = point_list[median]
    node.left_child = kdtree(point_list[:median], depth + 1)
    node.right_child = kdtree(point_list[median + 1:], depth + 1)
    return node

搜索:(来自 gist，基于 wikipedia algorithm)

# method of the Node-class

def closest_point(self, target, point, best=None):
    if target is None:
        return best

    if best is None:
        best = target

    # consider the current node
    if distance(target, point) < distance(best, point):
        best = target

    # search the near branch
    best = self.child_near(point).closest_point(point, best)

    # search the away branch - maybe
    if self.distance_axis(point) < distance(best, point):
        best = self.child_away(point).closest_point(target, point, best)

    return best

---

阅读更多:

• High Dimensional Search and the NN Problem (博客文章)
• Closest Point Search in High Dimensions由 Nene 和 Nyar 撰写。
• Nearest Neighbor Search in Multidimensional Spaces通过查帕拉斯