WOLFRAM

Wolfram 语言与系统参考资料中心

"KDTree" （数据结构）

"KDTree"

表示实数坐标组的 k-d 树二进制空间分割.

更多信息

  • A k-d 树在维度 时可高效分割 n 个坐标的坐标组，这样可以快速进行搜索，如最近邻搜索. 每个节点有两个数据元素，索引参数为 0 和 1. 数据元素既可以是另一个 k-d 树节点或点索引参数的列表 {i1,i2,…} 其中 0<ik<=n. 每个数据元素都有唯一的机器整数 ID.
  • CreateDataStructure["KDTree",coordinates]从 coordinates 中创建一个都可由实数表示的新 "KDTree".
    CreateDataStructure["KDTree",coordinates, n]从 coordinates 中创建一个每个分支中至多有 n 个条目的新 "KDTree".
    Typed[x,"KDTree"]赋予 x 类型 "KDTree".
  • 对于类型 "KDTree" 的数据结构 ds 而言，可使用下列运算：
  • ds["DataBounds"]返回坐标的总体边界时间：O(1)
    ds["DataCoordinates"]返回坐标时间：O(1)
    ds["Graphics"]在二维空间中显示坐标的空间分割时间：O(n)
    ds["ID"]返回 ds 的 ID时间：O(1)
    ds["ID", b]返回 ds 的 b（0 或 1）数据元素的 ID时间：O(1)
    ds["Indexes",b]返回 ds 的 b（0 或 1）叶片数据元素表示的边框内包含的坐标索引时间：O(1)
    ds["LeafQ", b]若 ds 的 b（0 或 1）数据元素为叶片则返回 True时间：O(1)
    ds["Node",b]为 ds 的 b（0 或 1）节点数据元素返回 "KDTree"时间：O(1)
    ds["SplitDimension"]为 ds 的空间分割返回维度时间：O(1)
    ds["SplitPosition"]为 ds 的空间分割返回位置时间：O(1)
    ds["SubtreeIndexes",sd]返回 ds 表示的子树中的所有坐标索引时间：O(n)
    ds["SubtreeLength"]求 ds 表示的子树包围的坐标数量时间：O(n)
    ds["TreeSize"]返回数据元素的数量时间：O(1)
    ds["Visualization"]返回 ds 的可视化表示时间：O(n)

范例

打开所有单元 关闭所有单元

基本范例  (1)

可用 CreateDataStructure 创建一个新的 "KDTree" 对象：

Wolfram Language code: coordinates = BlockRandom[RandomVariate[NormalDistribution[], {47, 2}], RandomSeeding -> 1234];ds = CreateDataStructure["KDTree", coordinates]

为二维数据显示图形：

Wolfram Language code: dsg = ds["Graphics", Axes -> True]

检验 0 和 1 数据元素中是否有叶片：

Wolfram Language code: Table[ds["LeafQ", b], {b, 0, 1}]

获取 1-数据元素叶片中包含的点，并在图形中以红色点的形式高亮：

Wolfram Language code: Show[dsg, Graphics[{Red, Point[ds["DataCoordinates"][[ds["Indexes", 1]]]]}]]

获取 0-数据元素表示的 k-d 树：

Wolfram Language code: left = ds["Node", 0]

不包括在子树中的坐标的部分在图形中以粉色表示：

Wolfram Language code: left["Graphics"]

可视化 k-d 树的树结构：

Wolfram Language code: ds["Visualization"]

获取 k-d 树的分割维度和位置：

Wolfram Language code: {sdim = ds["SplitDimension"], spos = ds["SplitPosition"]}

获取 k-d 树的 1-元素数据的坐标索引：

Wolfram Language code: {ds["LeafQ", 1], ind = ds["Indexes", 1]}

检验坐标是否都位于分割维度中分割位置之上：

Wolfram Language code: AllTrue[coordinates[[ind, sdim]], (# ≥ spos)&]

获取 1-元素子树 k-d 树的所有坐标索引，并检查它们是否都位于分割位置之下：

Wolfram Language code: lind = left["SubtreeIndexes"]; AllTrue[coordinates[[lind, sdim]], (# ≤ spos)&]

范围  (3)

信息  (1)

可使用 CreateDataStructure 创建新的 "KDTree"：

Wolfram Language code: coordinates = RandomReal[1, {1663, 4}];ds = CreateDataStructure["KDTree", coordinates]

数据结构 ds 的信息：

Wolfram Language code: Information[ds]

叶片尺寸  (1)

每个可在 CreateDataStructure 中可指定为附加参数的箱中有至多给定数量的坐标之前，分支会继续计算：

将坐标数量限制在至多 5 个：

Wolfram Language code: coordinates = BlockRandom[RandomVariate[NormalDistribution[], {47, 2}], RandomSeeding -> 1234];ds = CreateDataStructure["KDTree", coordinates, 5]
Wolfram Language code: ds["Graphics"]

默认设置是在构建与叶片上的遍历成本和运算成本之间选择一个平衡点：

Wolfram Language code: CreateDataStructure["KDTree", coordinates]["Graphics"]

任意精度  (1)

如果赋予坐标的精度大于 MachinePrecision 位数，那么计算会在合适的精度下进行：

Wolfram Language code: coordinates = BlockRandom[RandomReal[{-1, 1}, {47, 2}, WorkingPrecision -> 24], RandomSeeding -> 1234]; ds = CreateDataStructure["KDTree", coordinates]
Wolfram Language code: ds["SplitPosition"]

应用  (2)

最近邻搜索  (1)

设置程序使用 "KDTree" 数据结构寻找离给定点最近的坐标组中的元素：

Wolfram Language code: FindNearestNeighbor[kdTree_, x_] := Module[{searchData}, searchData = <|"Point" -> x, "Coordinates" -> kdTree["DataCoordinates"], "Nearest" -> CreateDataStructure["Value", {0, Infinity}]|>; nodeNearest[kdTree, searchData]; searchData["Nearest"]["Get"] ];

在每个节点处，处理该点所在或离第一个点最近的一边：

Wolfram Language code: nodeNearest[node_, searchData_] := Module[{spos, xd, sdist, first, second, ndist}, spos = node["SplitPosition"]; xd = searchData["Point"][[node["SplitDimension"]]]; If[xd ≤ spos, sdist = spos - xd; {first, second} = {0, 1}, sdist = xd - spos; {first, second} = {1, 0} ]; sideNearest[first, node, searchData]; ndist = searchData["Nearest"]["Get"][[2]]; If[ndist ≥ sdist, sideNearest[second, node, searchData] ]; ];

对于叶片数据元素，检验所有点；对于节点数据元素，则递归：

Wolfram Language code: sideNearest[side_, node_, searchData_] := If[node["LeafQ", side], (* Compute min distance to included points *) Module[{nind, ndist, dist}, {nind, ndist} = searchData["Nearest"]["Get"]; Do[ dist = Norm[searchData["Coordinates"][[ind]] - searchData["Point"]]; If[dist < ndist, {nind, ndist} = {ind, dist}; ], {ind, node["Indexes", side]} ]; searchData["Nearest"]["Set", {nind, ndist}] ], nodeNearest[node["Node", side], searchData] ];

在三维空间中用一百万个坐标的坐标组测试函数：

Wolfram Language code: coordinates = BlockRandom[RandomReal[{-1, 1}, {10 ^ 6, 4}], RandomSeeding -> 1234];ds = CreateDataStructure["KDTree", coordinates]
Wolfram Language code: Developer`PackedArrayQ[ds["DataCoordinates"]]
Wolfram Language code: FindNearestNeighbor[ds, {0., 0., 0., 0.}]

对比由 Nearest 返回的结果：

Wolfram Language code: Nearest[coordinates -> {"Index", "Distance"}, {0., 0., 0., 0.}]

与仅计算所有点的 Norm 的用时进行比较：

Wolfram Language code: RepeatedTiming[Min[Map[Norm, coordinates]]]
Wolfram Language code: RepeatedTiming[FindNearestNeighbor[ds, {0., 0., 0., 0.}]]

k-d 树的构建会比单次扫描更耗时，但如果在需要多次搜索的情况下这个时间是值得的：

Wolfram Language code: First[RepeatedTiming[CreateDataStructure["KDTree", coordinates]]]
Wolfram Language code: RepeatedTiming[ds["DataCoordinates"];]

范围搜索  (1)

设置一个程序，其会使用 "KDTree" 对象在给定范围内寻找坐标组中所有元素：

Wolfram Language code: RangeSearch[kdTree_, ranges : {{_, _}..}] := Module[{searchData}, searchData = <|"LowerLimits" -> ranges[[All, 1]], "UpperLimits" -> ranges[[All, 2]], "Coordinates" -> kdTree["DataCoordinates"], "InRange" -> CreateDataStructure["DynamicArray"]|>; nodeRangeSearch[kdTree, searchData]; Normal[searchData["InRange"]] ];

在每个节点上，处理匹配每个节点分割维度范围的边：

Wolfram Language code: nodeRangeSearch[node_, searchData_] := Module[{spos, sdim, ll, ul}, sdim = node["SplitDimension"]; spos = node["SplitPosition"]; ll = searchData["LowerLimits"][[sdim]]; ul = searchData["UpperLimits"][[sdim]]; If[ll ≤ spos, sideRangeSearch[0, node, searchData] ]; If[ul ≥ spos, sideRangeSearch[1, node, searchData] ]; ];

对于叶片数据元素，检验包含的所有点；对于节点数据元素，则递归：

Wolfram Language code: sideRangeSearch[side_, node_, searchData_] := Module[{x, ll, ul}, If[node["LeafQ", side], (* Determine index of points in range *) ll = searchData["LowerLimits"]; ul = searchData["UpperLimits"]; x = searchData["Coordinates"]; Do[ If[AllTrue[MapThread[LessEqual, {ll, x[[ind]], ul}], Identity], searchData["InRange"]["Append", ind] ], {ind, node["Indexes", side]} ], nodeRangeSearch[node["Node", side], searchData] ] ];

我们精选了一些属性，下面是所有这些属性都已知的国家的数据集：

Wolfram Language code: data = Cases[Table[CountryData[#, prop], {prop, {"Name", "Population", "Area", "GDP"}}]& /@ CountryData[], datum_ /; FreeQ[datum, _Missing, Infinity]];

获取相应数字数据，并根据它创建 "KDTree" 数据结构：

Wolfram Language code: numericalData = QuantityArray[data[[All, 2 ;; -1]]]["Magnitudes"]; ds = CreateDataStructure["KDTree", numericalData];

查找人口低于一百万但 GDP 高于 100 亿美元的国家：

Wolfram Language code: index = RangeSearch[ds, {{-Infinity, 10 ^ 6}, {-Infinity, Infinity}, {10 ^ 10, Infinity}}]; data[[index, 1]]

查找人口高于一千万且面积小于十万 km2 的国家：

Wolfram Language code: index = RangeSearch[ds, {{10 ^ 7, Infinity}, {-Infinity, 10 ^ 5}, {-Infinity, Infinity}}]; data[[index, 1]]