検索する

KDツリーアルゴリズムのC ++実装



C Implementation Kd Tree Algorithm



この記事を読む前に、関連情報を参照してKNNアルゴリズムとKDツリーを理解することをお勧めします。

基本知識

図に示すように、点を想定しますa現在の最近傍はb、相対して存在する場合b離れてaより近い点、そしてこの点はaでなければなりません円の中心ですab円の半径です。
aの場合、右側の領域は不明です。分割線までの距離l現在の最近傍距離L（円半径）よりも大きい場合、右側の未知の領域で最近傍を検索し続ける必要はありません（図1）。逆に、検索を続ける必要があります（図2）。
それに応じて、それは多次元空間に投影されます。セグメンテーション境界が最初の場合i次元、分割点の値v（スカラー）、現在の最近傍はy（ベクトル）（ターゲット点の場合x（ベクトル）セグメンテーション境界までの距離） | x [i] -v | 次の関係を満たします

、反対側で検索を続ける必要があります。



1：

二：
一般に、機械学習アルゴリズムはfitに分けられます。 predictで線形探索に基づく2段階KNN怠惰なアルゴリズムであり、すべてのコンピューティングタスクを実行しますpredictステージ、predict時間計算量はO(n)、KDツリーはタスクfit（KDツリーの確立）ステージの一部を配置するため、線形検索よりも高速であり、検索する必要のない多数のノードがあります。検索中は省略できます（時間計算量はO(1)）。
上記は比較的簡単です。 KNNアルゴリズムとKDツリーの詳細については、LiHang博士の「統計的学習方法」を参照してください。



コード

いくつかのキーコードを示します。

基本的なデータ構造

  • トレーニングセットの1次元配列double *dataその長さがn_samples * n_featuresであることを示します。ラベルセットも1次元配列を使用しますdouble *labelsその長さがn_samplesであることを示します。
  • ツリーのノードは、次のデータ構造で表されます。
    cpp
    struct tree_node
    {
    size_t id // represents the i-th data in the training set
    size_t split // The dimension of split
    tree_node *left, *right // left and right subtree
    }
  • KDツリーモデルは次の構造で表すことができます
    cpp
    struct tree_model
    {
    tree_node *root // root node
    const double *datas // X
    const double *labels // y
    size_t n_samples // number of samples
    size_t n_features // The number of features for each sample
    double p // Distance measurement
    }

  • K最近傍法を探す場合、大きなトップヒープが必要です。 C ++優先キューを直接使用して、既存のn(n <= k)を表します。隣人の中で、テストポイントから最も遠いのは山の頂上です

    struct neighbor_heap_cmp { bool operator()(const std::tupledouble> &i, const std::tupledouble> &j) { return std::get<1>(i) <std::get<1>(j) } } typedef std::tupledouble> neighbor typedef std::priority_queuestd::vector, neighbor_heap_cmp> neighbor_heap_ neighbor_heap k_neighbor_heap_

KDツリークラス

クラスを使用しますKDTree関数Contribute with search forを持つ必要があるKDツリークラスを表します。



//(Simplified code, see the end for the complete code) class KDTree { public: // Build a tree KDTree(const double *datas, const double *labels, size_t rows, size_t cols, double p) // return to the tree tree_node *GetRoot() { return root } // Find the k neighbors of a test point std::vector<std::tupledouble>> FindKNearests(const double *coor, size_t k) private: tree_node *root_ }

セグメンテーションディメンションとセグメンテーションポイントを見つける

ツリーを構築する前に、セグメンテーション次元とセグメンテーションポイントを選択する方法を検討する必要があります。セグメンテーションの次元には多くのオプションがあります。一般的には、dim = floor % n_featuresを取ることができます。つまり、現在のツリーのレイヤー数は、フィーチャの数の残りです。ここで使用しますdim = argmax(nmax - nmin)、つまり、現在のノードセットで範囲が最大の次元を選択します。

(Here is incomplete code, please refer to the complete source code for the definition of some tool functions) size_t KDTree::FindSplitDim(const std::vector &points) { if (points.size() == 1) return 0 size_t cur_best_dim = 0 double cur_largest_spread = -1 double cur_min_val double cur_max_val for (size_t dim = 0 dim 0], dim) cur_max_val = GetDimVal(points[0], dim) for (const auto &id : points) { if (GetDimVal(id, dim) > cur_max_val) cur_max_val = GetDimVal(id, dim) else if (GetDimVal(id, dim) if (cur_max_val - cur_min_val > cur_largest_spread) { cur_largest_spread = cur_max_val - cur_min_val cur_best_dim = dim } } return cur_best_dim }

フラクタル次元の選択kその後、最初に設定された現在のノードでノードを選択する必要がありますk寸法の中央値xカットポイントの値として、ポイントを除いて、最初のkディメンションの値がx以下です、左のサブツリーに配置します。それ以外の場合は、右のサブツリーに配置します。
中央値を見つけるときは、すべてを並べ替えるのではなく、中間点を取ります。高速並べ替えと同様の方法を使用して、中央値が見つかったら並べ替えを停止できます。ここではアルゴリズムを記述しません。ここで、C ++関数を直接使用します。

std::tupledouble> KDTree::MidElement(const std::vector &points, size_t dim) { size_t len = points.size() for (size_t i = 0 i std::make_tuple(points[i], GetDimVal(points[i], dim)) std::nth_element(get_mid_buf_, get_mid_buf_ + len / 2, get_mid_buf_ + len, [](const std::tupledouble> &i, const std::tupledouble> &j) { return std::get<1>(i) <std::get<1>(j) }) return get_mid_buf_[len / 2] }

助ける

ツリーを構築するには、バイナリツリーを構築する方法に直接従ってください

tree_node *KDTree::BuildTree(const std::vector &points) { size_t dim = FindSplitDim(points) std::tupledouble> t = MidElement(points, dim) size_t arg_mid_val = std::get<0>(t) double mid_val = std::get<1>(t) tree_node *node = Malloc(tree_node, 1) node->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) <= mid_val) left.emplace_back(i) else right.emplace_back(i) } if (!left.empty()) node->left = BuildTree(left) if (!right.empty()) node->right = BuildTree(right) return node }

K最近傍を検索するためのルール

一般に、本が話しているのは最近傍を検索することですが、ここではK最近傍を検索しているため、本のアルゴリズムを少し拡張する必要があります。
最近傍を検索するときは、通常2つの変数を設定しますcur_min_id cur_min_distを使用して、現在検索されているポイントからテストポイントまでの距離がl の場合時間、上記の2つの変数を新しいポイントに更新しますid distで。
同様に、K最近傍を検索する場合、a kを設定できます。要素の大きな上部の山。検索時に山がいっぱいになったときに、現在の検索ポイントを比較するだけで済みますdistヒープの頂点よりも小さいですかdist、より小さい場合、ヒープの上部がヒープから排出され、現在の検索ポイントが押し込まれます。それ以外の場合、ヒープがいっぱいでない場合、検索ポイントは直接プッシュされます。

K最近傍を検索するためのアルゴリズム

二分木深さ優先走査の非再帰的アルゴリズムを直接使用します（詳細については、「統計的学習方法」の43ページのアルゴリズム3.3を参照してください）。

std::vector<std::tupledouble>> KDTree::FindKNearests(const double *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() if (p->left) HeapStackPush(paths, p->left, coor, k) if (p->right) HeapStackPush(paths, p->right, coor, k) } else { double node_split_val = GetDimVal(p->id, p->split) double coor_split_val = coor[p->split] double heap_top_val = std::get<1>(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<std::tupledouble>> res while (!k_neighbor_heap_.empty()) { res.emplace_back(k_neighbor_heap_.top()) k_neighbor_heap_.pop() } return res }

完全なコード

見る https://github.com/WiseDoge/libkdtree
KD-Treeコードに加えて、完全なコードは、テストコードとPythonインターフェイスコード、およびサードパーティライブラリを呼び出して高速化するためのいくつかの手段も提供します。

元の住所

http://www.jianshu.com/p/80e41da2a397