KDツリー（C ++実装）

Kd Tree

参考資料：

https://blog.csdn.net/dymodi/article/details/46830071

https://github.com/WiseDoge/libkdtree

高次元データにアクセスするためのデータ構造として、k-dツリーは静的なクエリと挿入の点で依然として非常に効率的です。この記事では、ここでk-dツリーの内容を紹介します。また、k-dツリーの使用経験の一部と併せてコメントを付けることもできます。実際、k-dツリーは1975年にスタンフォード大学のベントレーによって提案されました。この記事の内容は、彼の最も独創的な2つの記事[Ben75]と[FBF77]からも引用されています。

K-dツリーの概要と挿入操作（挿入）
まず第一に、kdツリーも一種の二分探索木です。一般的な平衡二分探索木（BST）とは異なり、kd木では、各ノードはIsレコード、またはベクトルで表される多次元空間内の点を格納します。また、k-dツリーでは、この点は空間内の領域も表します。各ノードには2つの子ノードがあり、2つの子ノードのそれぞれによって表される領域は、親ノードの領域の分割です。

1次元の場合、各レコードは1つのキーで表されます。したがって、k-dツリー内の各ノードについて、キー値が現在のノードのキー値以下であるポイントは左側のサブツリーに属し、現在のノードのキー値より大きい値は右側のサブツリーに属します。したがって、ここでのキー値は識別子になります。 k次元の場合、レコードはk個のキー値で表されます。各次元のキー値は、ノードの左右のサブツリーにポイントを分類するための識別子として使用できます。 kdツリーでは、弁別子の選択は、最初の次元のキー値である、ノードに応じて、ノードが配置されているレイヤーの数、つまりルートノード、つまりレイヤー0に関連しています。最初の次元のキー値がルートノードの最初の次元のキー値のルートノードに属する左側のサブツリー以下であり、ルートノードに属する右側のサブツリーが最初の次元のキー値より大きいルートノードの次元。次に、ルートノードの左右の子ノードの位置、つまり第1層の位置で、第2次元のキー値によって区別されます。つまり、k番目の層で比較されるキー値の次元はD = L mod k + 1D = L mod k +1です。ここで、Lは現在のノードが配置されているレイヤーの数であり、ルートノードは0番目のレイヤーです。

kdツリーの規則に従って、（0,0）、（-10、10）、（10、-10）、（-40、-20）、（-20、11）、（20、0）を挿入します。ポイント、下の左の写真に示されているkdツリーを取得できます。右の写真は、平面内のこれらのポイントの概略図です。青い線は、ポイントが1番目の次元のキー値によって区別されることを示し、赤い線は、ポイントが2番目の次元のキー値によって区別されることを示します。

同時に、k-dツリーの各ノードが実際にk次元空間の領域を表していることがわかります。上記の2次元空間の点を例として取り上げましょう。ルートノード（0,0）は、平面全体、つまり（-50、-50、50、50）のような領域を表し、（xmin、ymin、xmax、ymax）（xmin、ymin、xmax、Ymax）を使用します。ルートノード（0,0）が最初の次元（xx軸）で区別されるため、その左の子ノードは左半平面を表し、右の子ノードは右半平面を表すことを示します。点（-10、10）は（-50、-50、0、50）の面積を表し、点（10、-10）は（0、-50、50、50）の面積を表します）。以下同様に、点（-10、10）では、最初の層であるため、2番目の次元で区別され、点（-40、-20）の2番目の次元は点（- 10、10）。 、すぐ左にある点（-20、11）の2番目の次元は、ちょうど右にある点（-10、10）よりも大きくなっています。さらに、左の点（-40、-20）はその親ノードの下半分を表します。つまり、（-50、-50、0、10）は、右の点（-20、11）が表す領域です。親ノードの半分、つまり（-50、10、0、50）の領域です。

検索操作
上記では、k-dツリーの原理とノードを挿入するプロセスを紹介しました。次に、ノードを検索するプロセスを紹介します。 k-dツリーでポイントを検索する方法はたくさんあります。 （1）すべてのディメンションに一致する特定のポイントクエリ（完全一致）（2）部分的なディメンションに一致するクエリ（3）特定の領域内のポイントのクエリ（4）特定のポイントに最も近いいくつかのポイントを検索します。

上記のいくつかの検索アルゴリズムは、[Ben75]および[FBF77]で詳細に説明されています。ここでは主に（3）を紹介します。これは私が自分で使用したリージョンクエリです。エリアクエリの目的は、kdツリーで表されるスペース（つまり、上記の例で説明した2次元平面に長方形のエリア（つまり、（-50、-50、50、50）のスペース）を与えることです。上記の例のように、各次元でこの領域の上限と下限が与えられると、この領域内にあるすべての点を見つけるための領域（-45、-30、-30、-10）を与えることができます。

エリア検索の主な方法は次のとおりです。ルートノードから開始して、ノードのキー値で表されるポイントが検索エリア内にあるかどうかを調査し、チェックエリア内にある場合はノードはグローバルリストに配置されます。その後、ノードの左右の子ノードで表される領域が、クエリ対象の領域と交差しているかどうかを調べ、交差している場合は、子ノードをルートノードとして再帰的に使用します。上記の操作を実行し、実行しない場合は戻ります。すべての再帰関数の実行が終了すると、検索する領域に格納されているポイントのグローバルリストを取得できます。上記の説明からわかるように、検索アルゴリズムの複雑さは、検査する領域のサイズと大きな関係があります。 [LW77]によると、最悪の場合の領域検索の複雑さはO（kN1-1k）O（kN1-1k）に達します。ここで、kkはデータポイントの次元であり、NNはkd内のノードの総数です。木。ただし、[Ben75、FB74]の多数のシミュレーションでは、超長方形領域を検索する場合、kdツリーでの領域検索が非常にうまく（かなりうまく）実行されることが示されています。

削除操作（削除）
実際、k-dツリー自体にはバランスがなく、動的な挿入および削除操作によってk-dツリーが線形テーブルに劣化する可能性があるため、k-dツリーは削除操作を十分にサポートしていません。 [Rob81]などのk-d木のバランスに関する研究が実際にあります。しかし、おそらく実装の複雑さのために、K-D-Bツリーは多くのアプリケーションを取得していないようです。

以下では、主に削除操作について説明します。kdツリー内のノードを削除する原則は、後続ノードのない外部ノードの場合、後続ノードを持つ内部ノードPPに対して直接削除操作を実行できるということです。実行する必要があるのは、子ノードから適切なノードQQを見つけて、削除する必要のあるノードの場所に配置することです。いわゆる適切なノード、つまり、PPノードがJJ次元で区切られている場合、QQは、PPの左側のサブツリーのJJ次元で最大のノード、またはPPの右側のサブツリーで最小のJJ次元です。ノード、両方できます。 QQノードをPPノードの場所に置き換えるには、QQノードを元の場所から削除する必要があるため、上記の削除操作も再帰的な実装プロセスです。

自分で作成した削除操作は、他のアプリケーションと組み合わせる必要があるため非常に冗長であったため、ここではリリースしませんでした。

操作の最適化（最適化）
最適化操作は、k-dツリーのオフライン操作です。二分木が挿入操作を進めるときに、木のバランスが保証できない場合、二分木の操作の複雑さが徐々に悪化することは誰もが知っています。極端な場合、二分木は線形テーブルに縮退します。不均衡なk-dツリーの場合、最適化された操作によってバランスを取り、後続のルックアップ操作の効率を確保できます。

いわゆる最適化操作は、実際には次元の順序に従ってノードをソートしています。たとえば、最適化が必要なkdツリーの場合、すべてのノードが最初の次元要素に従って昇順で並べ替えられ、次に中央のノードがルートノードとして使用され、ノードの左半分がメインサブツリーのノードであり、ノードの半分があります。サブツリーのノードとして。次に、上記の処理がそれぞれ左と右のサブツリーのノードで実行されますが、参照の次元はそれぞれ2番目の次元、3番目の次元です。

上記の処理の後、任意のk-dツリーをバランスの取れたk-dツリーにすることができます。

ここでは、kdツリーの内容の要約を作成します。既存のN個のデータポイントの場合、各ポイントはk次元データで表されます。 kdツリーの構築の複雑さはO（NlogN）O（Nlog⁡N）です。既存のkdツリーの最適化の複雑さはO（NlogN）O（NlogN）、ノードの挿入の複雑さはO（logN）O（log⁡N）、ノードの削除の複雑さはO（logN））Oです。 （log⁡N）、完全一致を実行する複雑さはO（logN）O（log⁡N）であり、特定の領域を見つけるための最悪の場合の複雑さはO（kN1-1k）O（kN1-1k）ですが、領域ルックアップの複雑さは領域のサイズに関連しており、平均的な意味での効果は良好です。

コードは次のように表示されます。

kdtree.h

#ifndef KDTREE_H #define KDTREE_H // set dynamic link library #if defined(_MSC_VER) #define DLLExport __declspec(dllexport) #else #define DLLExport #endif // set c++ #ifdef __cplusplus extern 'C' { #endif #include struct DLLExport tree_node { size_t id size_t split tree_node *left, *right } struct DLLExport tree_model { tree_node *root const float *datas const float *labels size_t n_samples size_t n_features float p } DLLExport void free_tree_memory(tree_node *root) DLLExport tree_model* build_kdtree(const float *datas, const float *labels, size_t rows, size_t cols, float p) DLLExport float* k_nearests_neighbor(const tree_model *model, const float *X_test, size_t len, size_t k, bool clf) DLLExport void find_k_nearests(const tree_model *model, const float *coor, size_t k, size_t *args, float *dists) #ifdef __cplusplus } #endif #endif

kdtree.cpp

#include 'kdtree.h' #include #include #include #include #include #include #include #include #include #include // Example: // int x = Malloc(int, 10) // int y = (int *)malloc(10 * sizeof(int)) #define Malloc(type, n) (type *)malloc((n)*sizeof(type)) // If you need to use Intel MKL to accelerate, // you can cancel the next line comment. //#define USE_INTEL_MKL #ifdef USE_INTEL_MKL #include #endif // Clang does not support OpenMP. #ifndef __clang__ #include #endif / / Release a binary tree memory non-recursive algorithm DLLExport void free_tree_memory(tree_node *root) { std::stack node_stack tree_node *p node_stack.push(root) while (!node_stack.empty()) { p = node_stack.top() node_stack.pop() if (p->left) node_stack.push(p->left) if (p->right) node_stack.push(p->right) free(p) } } class KDTree { public: KDTree(){} KDTree(tree_node *root, const float *datas, size_t rows, size_t cols, float p) KDTree(const float *datas, const float *labels, size_t rows, size_t cols, float p, bool free_tree = true) ~KDTree() tree_node *GetRoot() { return root } std::vector FindKNearests(const float *coor, size_t k) std::tuple FindNearest(const float *coor, size_t k) { return FindKNearests(coor, k)[0] } void CFindKNearests(const float *coor, size_t k, size_t *args, float *dists) private: // The sample with the largest distance from point `coor` // is always at the top of the heap. struct neighbor_heap_cmp { bool operator()(const std::tuple &i, const std::tuple &j) { return std::get(i) neighbor_heap // Search for the heap of the K-nearest neighbor (large top heap), the top of the heap is always the farthest point of the sample point in the K-nearest neighbor neighbor_heap k_neighbor_heap_ // p when looking for distance, dist(x, y) = pow((x^p + y^p), 1/p) float p // Whether to release the memory of the tree when destructing bool free_tree_ // tree root node tree_node *root // Training set const float *datas // The number of samples in the training set size_t n_samples // the dimensions of each sample size_t n_features // The label of the training set const float *labels // The cache pool used to find the median std::tuple *get_mid_buf_ // Search for the cache pool for K nearest neighbors, if you have searched for point i, make visited_buf[i] = True bool *visited_buf_ #ifdef USE_INTEL_MKL // Cache when using the Intel MKL library float *mkl_buf_ #endif // Initialize the cache void InitBuffer() // Building a tree tree_node *BuildTree(const std::vector &points) // Find the median of a set of numbers std::tuple MidElement(const std::vector &points, size_t dim) // into the heap void HeapStackPush(std::stack &paths, tree_node *node, const float *coor, size_t k) // Get the value of the dim of the sample point in the training set float GetDimVal(size_t sample, size_t dim) { return datas[sample * n_features + dim] } // Find the distance from the coor to the i-th point of the training set float GetDist(size_t i, const float *coor) // Find the cut point size_t FindSplitDim(const std::vector &points) } // Find the K nearest neighbor of a tree. The id of Ki and the distance between Ki and coor are stored in args and dists respectively. DLLExport void find_k_nearests(const tree_model *model, const float *coor, size_t k, size_t *args, float *dists) { KDTree tree(model->root, model->datas, model->n_samples, model->n_features, model->p) std::vector k_nearest = tree.FindKNearests(coor, k) for (size_t i = 0 i datas = datas model->labels = labels model->n_features = cols model->n_samples = rows model->root = tree.GetRoot() model->p = p return model } // Find the average for regression problems float mean(const float *arr, size_t len) { float ans = 0.0 for (size_t i = 0 i = cur_max) { cur_arg_max = static_cast(i.first) cur_max = i.second } } return cur_arg_max } DLLExport float * k_nearests_neighbor(const tree_model *model, const float *X_test, size_t len, size_t k, bool clf) { float *ans = Malloc(float, len) size_t *args float *dists, *y_pred size_t arr_len int i, j #ifdef USE_INTEL_MKL int n_procs = omp_get_num_procs() assert(n_procs <100) KDTree *trees[100] for (size_t i = 0 i root, model->datas, model->n_samples, model->n_features, model->p) arr_len = k * n_procs #else arr_len = k KDTree tree(model->root, model->datas, model->n_samples, model->n_features, model->p) #endif args = Malloc(size_t, arr_len) dists = Malloc(float, arr_len) y_pred = Malloc(float, arr_len) #ifdef USE_INTEL_MKL #pragma omp parallel for for (i = 0 i CFindKNearests(X_test + i * model->n_features, k, args + k * thread_num, dists + k * thread_num) for (j = 0 j labels[args[j + k * thread_num]] if (clf) ans[i] = vote(y_pred + k * thread_num, k) else ans[i] = mean(y_pred + k * thread_num, k) } for (size_t i = 0 i n_features, k, args, dists) for (j = 0 j labels[args[j]] if (clf) ans[i] = vote(y_pred, k) else ans[i] = mean(y_pred, k) } #endif free(args) free(y_pred) free(dists) return ans } inline KDTree::KDTree(tree_node *root, const float *datas, size_t rows, size_t cols, float p) : root(root), datas(datas), n_samples(rows), n_features(cols), p(p), free_tree_(false) { InitBuffer() labels = nullptr } inline KDTree::KDTree(const float *datas, const float *labels, size_t rows, size_t cols, float p, bool free_tree) : datas(datas), labels(labels), n_samples(rows), n_features(cols), p(p), free_tree_(free_tree) { std::vector points for (size_t i = 0 i KDTree::FindKNearests(const float *coor, size_t k) { std::memset(visited_buf_, 0, sizeof(bool) * n_samples) std::stack paths tree_node *p = root while (p) { HeapStackPush(paths, p, coor, k) p = coor[p->split] id, p->split) ? p = p->left : p = p->right } while (!paths.empty()) { p = paths.top() paths.pop() if (!p->left && !p->right) continue if (k_neighbor_heap_.size() left) HeapStackPush(paths, p->left, coor, k) if (p->right) HeapStackPush(paths, p->right, coor, k) } else { float node_split_val = GetDimVal(p->id, p->split) float coor_split_val = coor[p->split] float heap_top_val = std::get(k_neighbor_heap_.top()) if (coor_split_val > node_split_val) { if (p->right) HeapStackPush(paths, p->right, coor, k) if ((coor_split_val - node_split_val) left) HeapStackPush(paths, p->left, coor, k) } else { if (p->left) HeapStackPush(paths, p->left, coor, k) if ((node_split_val - coor_split_val) right) HeapStackPush(paths, p->right, coor, k) } } } std::vector res while (!k_neighbor_heap_.empty()) { res.emplace_back(k_neighbor_heap_.top()) k_neighbor_heap_.pop() } return res } void KDTree::CFindKNearests(const float *coor, size_t k, size_t *args, float *dists) { std::vector k_nearest = FindKNearests(coor, k) for (size_t i = 0 i left = nullptr node->right = nullptr node->id = arg_mid_val node->split = dim std::vector left, right for (auto &i : points) { if (i == arg_mid_val) continue if (GetDimVal(i, dim) left = BuildTree(left) if (!right.empty()) node->right = BuildTree(right) return node } std::tuple KDTree::MidElement(const std::vector &points, size_t dim) { size_t len = points.size() for (size_t i = 0 i id if (visited_buf_[id]) return visited_buf_[id] = true float dist = GetDist(id, coor) std::tuple t(id, dist) if (k_neighbor_heap_.size()

main.cpp

#include 'kdtree.h' #include #include int main() { float datas[100] = {1.3, 1.3, 1.3, 8.3, 8.3, 8.3, 2.3, 2.3, 2.3, 1.2, 1.2, 1.2, 7.3, 7.3, 7.3, 9.3, 9.3, 9.3, 15, 15, 15, 3, 3, 3, 1.1, 1.1, 1.1, 12, 12, 12, 4, 4, 4, 5, 5, 5} float labels[100] for(size_t i = 0 i <12 ++i) labels[i] = (float)i tree_model *model = build_kdtree(datas, labels, 12, 3, 2) float test[6] = {3, 3, 3, 4, 4, 4} size_t args[100] float dists[100] Find_k_nearests(model, test, 5, args, dists) // This only searches for K neighbors of (3,3,3) printf('K-Nearest: ') for (size_t i = 0 i root free(ans) free_tree_memory(model->root) return 0 }

運転結果