3

これらはhttp://elki.dbs.ifi.lmu.de/ からの引用です:

「本質的に、抽象距離クエリをデータベースにバインドし、この距離の最近傍検索を取得します。この時点で、ELKI は自動的に最も適切な kNN クエリ クラスを選択します。距離関数に適切なインデックスが存在する場合 (すべてのインデックスがすべての距離を加速できるわけではありません!)、ここでは自動的に使用されます。"

「getKNNForDBID メソッドは、低速の線形スキャンに要約される可能性がありますが、データベースに適切なインデックスがある場合、インデックス クエリが使用されます。その後、アルゴリズムは O(nk log n) または O(nk) 時間で実行できます。」

問題は、どのような基準で ELKI がインデックス クエリを実行するかどうかを選択するかということです。

「データベースに適切なインデックスがある場合」とはどういう意味ですか?どうすればそれを保証できますか?

「run」メソッドの署名に関する別の無関係な質問ですが、1 つではなく 3 つの署名があるのはなぜですか? それらの違いは何ですか?また、使用する署名を決定する基準は何ですか?

4

2 に答える 2

1

これは主に @Anony-Mousse の投稿のフォローアップであり、かなり的を射ています。

インデックスは、ユーザーがデータベースに追加する必要があります。現在、自動インデックス作成はありません (インデックスには追加のメモリと構築時間が必要になるため)。-db.indexこのためのパラメーターです。自動インデックス作成のサポートはウィッシュ リストにありますが、慎重に調整されたコスト モデルが必要です。小さなデータセットや高次元のデータ、またはユーザーがこのタイプのクエリをまったく必要としない場合、インデックスを追加するとコストがかかります。

データベースはクエリ要求を各インデックスに順番に転送します。加速を提供する最初のインデックスが勝ちます。高速化されたクエリを返すインデックスがない場合、ヒントDatabaseQuery.HINT_OPTIMIZED_ONLYが与えられていない限り、データベースは線形スキャンにフォールバックします。この場合、null返品されます。を介して線形スキャンを強制できQueryUtilます。これは、インデックスの単体テストに最も役立ちます。

M-Tree は任意の数値距離で機能しますが、距離がメトリックでない場合、結果が正しくない可能性があります。距離関数が true として報告されない場合、エラーが報告isMetric()されます。

R ツリーは、 を実装する任意の距離関数で機能しますSpatialPrimitiveDistanceFunction。これは、基本的に、下限の点から四角形までの距離を実装することを意味します。下限は多くの距離関数で見つけることができますが、有効性はさまざまです。たとえば、角度距離は、R ツリーが使用する四角形のページからはあまりメリットがありません。

方法としてはrun。通常のベクトル空間メソッドの推奨シグネチャは次のとおりです。

 YourResultType run(Database database, Relation<V> relation)

現在のところ、データベースは実際には 経由relation.getDatabase()で取得できますが、これは将来変更される可能性があります。これが問題となる状況は数多くありますが、残念ながら、現時点では簡単に取り除くことができない状況もあります。とにかく、これは Java コードからアルゴリズムを実行するのに便利な明示的な形式です。つまり、これが唯一の適切なリレーションであるデータベースを使用する代わりに、どのリレーションを使用するかを指定することができます (したがって、自動的に選択されます)。 ）。

長期的にはこれをさらに明確にし、処理するデータ サブセットを選択するための明示的なサポートを追加する計画があります。また、おそらくクエリも追加する予定です。抽象親runメソッドがこれを処理します。自動オプティマイザはこれに依存します。最初に、クエリ要件を含む要件に対して実行するすべてのアルゴリズムをクエリします。クエリ、データ セット、使用可能なメモリなどに基づいて、オプティマイザは適切なインデックスを選択し、アルゴリズムに適切なクエリ メソッドを渡すことができます。runシグネチャをシンプルに保つために、おそらくいくつかのInstanceクラスを介して処理され、代わりにファクトリ パターンがより多く使用されます。しかし、今は心配しないでください。

なぜこれが必要なのかを理解したい場合は、地理空間的外れ値検出アルゴリズムなどをご覧ください。SLOMたとえば、によって使用される署名は次のとおりです。

OutlierResult run(Database database, Relation<N> spatial, Relation<O> relation)

つまり、2 つの 2つの関係SLOMを使用します。第 1 の関係は、インスタンスの空間的な関係 (地理的な位置など) です。2 番目の関係は、測定値などの実際のデータです。地理的位置は、どのインスタンスが類似していると予想されるかを判断するために使用されます (ただし、これらはポリゴンなどの可能性もあります)。

于 2013-10-14T10:53:00.983 に答える