"KDTree" (データ構造)
"KDTree" (データ構造)
"KDTree"
実数座標集合についてのkd木の二分空間細分割を表す．
詳細
- kd木は，次元
での n 座標の集合を細分して，最近傍探索等の探索が素早く行えるようにするので便利である．各ノードには0と1の指標が付けられた2つのデータ要素が含まれる．データ要素は，別のkd木のノードでも，0<ik<=n である点指標のリスト {i1,i2,…}でもよい．各データ要素は固有の機械整数IDを持つ． -
CreateDataStructure["KDTree",coordinates] すべて実数で表せる coordinates から新しい"KDTree"を作成する． CreateDataStructure["KDTree",coordinates, n] 新しい"KDTree"を coordinates から作成し，各下位区分に最高で n 項目を含ませる． Typed[x,"KDTree"] x に"KDTree"型を与える． - "KDTree"型のデータ構造 ds には，以下の演算が使える．
-
ds["DataBounds"] 座標の全体的な境界を返す time: O(1) ds["DataCoordinates"] 座標を返す time: O(1) ds["Graphics"] 2D座標について空間分割を示す time: O(n) ds["ID"] ds のIDを返す time: O(1) ds["ID", b] ds の b（0または1）のデータ要素についてのIDを返す time: O(1) ds["Indexes",b] ds の b（0または1）の葉データ要素で表されるボックスに囲まれた座標について指標を返す time: O(1) ds["LeafQ", b] ds の b（0または1）のデータ要素が葉である場合はTrueを返す time: O(1) ds["Node",b] ds の b（0または1）のノードデータ要素について"KDTree"を返す time: O(1) ds["SplitDimension"] ds の空間分割の次元を返す time: O(1) ds["SplitPosition"] ds の空間分割の位置を返す time: O(1) ds["SubtreeIndexes",sd] ds が表す部分木内の座標の指標をすべて返す time: O(n) ds["SubtreeLength"] ds が表す部分木で囲まれた座標の数を求める time: O(n) ds["TreeSize"] データ要素数を返す time: O(1) ds["Visualization"] ds の可視化を返す time: O(n)
例題
すべて開く すべて閉じる例 (1)
新しい"KDTree"オブジェクトは，CreateDataStructureを使って作成できる：
coordinates = BlockRandom[RandomVariate[NormalDistribution[], {47, 2}], RandomSeeding -> 1234];ds = CreateDataStructure["KDTree", coordinates]dsg = ds["Graphics", Axes -> True]Table[ds["LeafQ", b], {b, 0, 1}]1データ要素の葉に含まれる点を得て，それらをグラフィックス内で赤色でハイライトする：
Show[dsg, Graphics[{Red, Point[ds["DataCoordinates"][[ds["Indexes", 1]]]]}]]left = ds["Node", 0]このグラフィックスでは，部分木に含まれない座標部分はピンクに色付けられる：
left["Graphics"]ds["Visualization"]{sdim = ds["SplitDimension"], spos = ds["SplitPosition"]}{ds["LeafQ", 1], ind = ds["Indexes", 1]}座標がすべて分割次元の分割位置より上にあるかどうかを検証する：
AllTrue[coordinates[[ind, sdim]], (# ≥ spos)&]1要素部分木のkd木について座標指標を得て，それらがすべて分割位置の下にあることを確かめる：
lind = left["SubtreeIndexes"];
AllTrue[coordinates[[lind, sdim]], (# ≤ spos)&]スコープ (3)
情報 (1)
新しい"KDTree"は，CreateDataStructureを使って作成できる：
coordinates = RandomReal[1, {1663, 4}];ds = CreateDataStructure["KDTree", coordinates]Information[ds]葉のサイズ (1)
CreateDataStructureの追加の引数として指定できる，最高で指定数の座標が各ボックスに含まれるまで，分割が行われる．
coordinates = BlockRandom[RandomVariate[NormalDistribution[], {47, 2}], RandomSeeding -> 1234];ds = CreateDataStructure["KDTree", coordinates, 5]ds["Graphics"]デフォルトは，葉に対する構築および走査の費用と演算の費用との間のバランスをよくするように選ばれる：
CreateDataStructure["KDTree", coordinates]["Graphics"]任意精度 (1)
座標にMachinePrecisionの数値よりも高い精度の座標を与えると，適切な精度で計算が行われる：
coordinates = BlockRandom[RandomReal[{-1, 1}, {47, 2}, WorkingPrecision -> 24], RandomSeeding -> 1234];
ds = CreateDataStructure["KDTree", coordinates]ds["SplitPosition"]アプリケーション (2)
最近傍検索 (1)
"KDTree"データ構造を使うプログラムを設定して，与えられた点に最も近い座標集合内の要素を求める：
FindNearestNeighbor[kdTree_, x_] :=
Module[{searchData},
searchData = <|"Point" -> x, "Coordinates" -> kdTree["DataCoordinates"], "Nearest" -> CreateDataStructure["Value", {0, Infinity}]|>;
nodeNearest[kdTree, searchData];
searchData["Nearest"]["Get"]
];各ノードで，点がある，あるいは1つ目に最も近い辺を処理する：
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]
];
];葉のデータ要素についてすべての点を検証し，ノードのデータ構造について再帰的に処理する：
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]
];coordinates = BlockRandom[RandomReal[{-1, 1}, {10 ^ 6, 4}], RandomSeeding -> 1234];ds = CreateDataStructure["KDTree", coordinates]Developer`PackedArrayQ[ds["DataCoordinates"]]FindNearestNeighbor[ds, {0., 0., 0., 0.}]Nearestが返す結果を比べる：
Nearest[coordinates -> {"Index", "Distance"}, {0., 0., 0., 0.}]すべての点のNormだけを計算した場合の計算時間と比べる：
RepeatedTiming[Min[Map[Norm, coordinates]]]RepeatedTiming[FindNearestNeighbor[ds, {0., 0., 0., 0.}]]kd木の構築は，単一探索より時間がかかるが，複数の探索が必要な場合には余分に時間をかける価値がある：
First[RepeatedTiming[CreateDataStructure["KDTree", coordinates]]]RepeatedTiming[ds["DataCoordinates"];]範囲探索 (1)
"KDTree"オブジェクトを使って，与えられた範囲内の座標の集合においてすべての要素を求めるプログラムを設定する：
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"]]
];各ノードにおいて，ノード分割の次元の範囲に合う各辺を処理する：
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]
];
];葉のデータ要素について含める点すべてを検証し，ノードのデータ要素について再帰的に処理する：
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]
]
];選択した特性が分かっている国すべてについてのその特性のデータ集合である：
data = Cases[Table[CountryData[#, prop], {prop, {"Name", "Population", "Area", "GDP"}}]& /@ CountryData[], datum_ /; FreeQ[datum, _Missing, Infinity]];対応する数値データを得て，それから"KDTree"データ構造を作成する：
numericalData = QuantityArray[data[[All, 2 ;; -1]]]["Magnitudes"];
ds = CreateDataStructure["KDTree", numericalData];人口が100万人未満で，国内総生産が100億ドルを超える国を求める：
index = RangeSearch[ds, {{-Infinity, 10 ^ 6}, {-Infinity, Infinity}, {10 ^ 10, Infinity}}];
data[[index, 1]]人口が1000万人を超え，面積が100000km2未満の国を求める：
index = RangeSearch[ds, {{10 ^ 7, Infinity}, {-Infinity, 10 ^ 5}, {-Infinity, Infinity}}];
data[[index, 1]]