1

FLANN モジュールでは、KDTree コンストラクターがツリーを作成するための構成パラメーターを受け取ります。デフォルト値は 4 です。最近傍探索に 4 つ以上のツリーが必要な理由を教えてください。

/**
 * KDTree constructor
 *
 * Params:
 *          inputData = dataset with the input features
 *          params = parameters passed to the kdtree algorithm
 */
KDTreeIndex(const Matrix<ElementType>& inputData, const IndexParams& params = KDTreeIndexParams(),
            Distance d = Distance() ) :
    dataset_(inputData), index_params_(params), distance_(d)
{
    size_ = dataset_.rows;
    veclen_ = dataset_.cols;

    trees_ = get_param(index_params_,"trees",4);   <<<<------------------ default 4
    tree_roots_ = new NodePtr[trees_];

    // Create a permutable array of indices to the input vectors.
    vind_.resize(size_);
    for (size_t i = 0; i < size_; ++i) {
4

1 に答える 1

1

木は最後まで検索されないのでしょう。また、構築方法もわずかに異なります。したがって、4 つのツリーが部分的に検索される場合、それらを組み合わせたパフォーマンスは、部分的に検索される 1 つのツリーよりもはるかに優れています。同時に、完全に検索された 1 つのツリーよりも高速に動作します (そして、メモリ効率が向上する可能性があります)。少なくともこれは、この問題に関する私の直感です。

FLANN -おおよその最近傍の高速ライブラリを表します。ここでは近似という言葉が鍵となります。たとえば、ツリー構築のある時点で、ポイントのセットの中央値を見つける必要があります (スペースをほぼ半分に効率的に分割するため)。これには n*log(n) 操作が必要ですが、中央値はより小さなサンプル、たとえば n=min(100, n/100) から概算できます。例を示すためにこれを作成しています。これにより、検索が少し遅くなるというわずかな代償で、構築が約 600 倍高速化されます。また、分散を大きくするためにすべてのディメンションを調べて分割を選択する代わりに、限定されたセットを調べることもあります。これは、ツリーが異なる理由を説明しています。

ここでの別の側面として、標準の kd ツリーは徹底的な検索と比較して効率が低下するため、最近傍への近似は高次元空間でより重要になります。近似する 1 つの方法は、限られた数の葉のみを検査して検索精度を満たすことです。多くの場合、すべてのツリーにわたって優先キューが維持され、距離が長くなるにつれて検索が順序付けられます。つまり、近似と複数のツリーを使用することで、速度とメモリ効率を大幅に向上させることができ、精度はほとんど低下しません。

于 2014-03-18T00:32:57.917 に答える