0

品質しきい値クラスタリング アルゴリズムを実装しようとしています。その概要(ここから取得)を以下に示します。

  1. クラスターに許可されるしきい値距離と最小クラスター サイズを初期化する
  2. クラスターの距離がしきい値を超えるまで、最も近いポイント、次に近いポイントなどを含めて、各データ ポイントの候補クラスターを構築します。
  3. 最も多くのポイントを持つ候補クラスターを最初の真のクラスターとして保存し、クラスター内のすべてのポイントを以降の検討対象から除外します
  4. 最小のクラスター サイズを持つクラスターが形成されなくなるまで、削減された点のセットで繰り返します。

最近傍探索アルゴリズムと空間分割データ構造について読んでいますが、それらは必要なもののようですが、どれを使用するか、または他の何かを見ているかどうかを判断できません.

教育目的でデータ構造を自分で実装したいのですが、あるポイントの最も近いポイントを連続して返すことができるものが必要です。ただし、クエリを実行する必要がある回数がわからないため (つまり、しきい値を超えるまで)、k 最近傍アルゴリズムを使用できません。私は主に四分木とkdツリーを見てきました。

さらに、アルゴリズムは常に新しい候補クラスターを構築するため、キャッシュされた情報を使用して後続のクエリを高速化する変更されたデータ構造を使用することは興味深いでしょう (ただし、ポイントの削除も考慮に入れます)。

4

1 に答える 1

2

このアルゴリズムは、 R*-Tree インデックス (Wikipedia)で非常にうまく機能することが知られているDBSCAN (Wikipedia)の前身のように思えます。もちろん、kd-trees もオプションです。これら 2 つの主な違いは、R* ツリーがデータベースでの使用を意図していることです。オンラインでの挿入と削除を非常によくサポートし、ブロック指向です。一方、kd ツリーは、バイナリ分割に基づくメモリ内データ構造に近いものです。R* ツリーはリバランスを実行しますが、kd ツリーは徐々にバランスが崩れ、再構築が必要になります。境界矩形が非常に直感的であるため、kd ツリーよりも R* ツリーでの最近傍検索の方がはるかに理解しやすいと思います。

DBSCAN は、ポイントをさらに検討することからも「削除」しますが、単に割り当て済みとしてマークするだけです。そうすれば、インデックスを更新する必要はありません。最初に 1 回一括読み込みするだけで十分です。QTでもこれを行うことができるはずです。したがって、私が間違っていない限り、DBSCAN をQT クラスタリングにepsilon設定して実行することで、QT クラスタリングを効率的に取得できますminPts=2(ただし、適切な DBSCAN ではより高い値を使用することをお勧めします)。

DBSCAN の実装は数多くあります。Weka のものは非常にくだらないので、近づかないでください。R でのfpc実装は問題ありませんが、それでもはるかに高速になる可能性があります。インデックスを完全にサポートしているのはELKIだけのようで、速度の差は非常に大きいです。彼らのベンチマークは、このデータ セットのインデックスを使用することで 12 倍の速度向上を示しており、603 (インデックスなし) ではなく 50 秒でクラスター化できます。Weka は驚異的な 37917 秒、R fpc は 4339 秒かかりました。それは私の経験と一致しています.Wekaは非常に遅いという評判があり、Rはベクトル化された操作でのみ尻を蹴ります.Rインタープリターが動作するようになると、ネイティブよりも大幅に遅くなります. しかし、これは、同じアルゴリズムが異なる人によって実装された場合に、どのように異なるパフォーマンスを発揮できるかを示す良い例です。これは 2 倍から 5 倍になると予想していましたが、明らかに、同じアルゴリズムを実装しているプログラマーと別のプログラマーとでは、違いは簡単に 50 倍になる可能性があります。

于 2012-12-17T07:37:59.940 に答える