品質しきい値クラスタリング アルゴリズムを実装しようとしています。その概要(ここから取得)を以下に示します。
- クラスターに許可されるしきい値距離と最小クラスター サイズを初期化する
- クラスターの距離がしきい値を超えるまで、最も近いポイント、次に近いポイントなどを含めて、各データ ポイントの候補クラスターを構築します。
- 最も多くのポイントを持つ候補クラスターを最初の真のクラスターとして保存し、クラスター内のすべてのポイントを以降の検討対象から除外します
- 最小のクラスター サイズを持つクラスターが形成されなくなるまで、削減された点のセットで繰り返します。
最近傍探索アルゴリズムと空間分割データ構造について読んでいますが、それらは必要なもののようですが、どれを使用するか、または他の何かを見ているかどうかを判断できません.
教育目的でデータ構造を自分で実装したいのですが、あるポイントの最も近いポイントを連続して返すことができるものが必要です。ただし、クエリを実行する必要がある回数がわからないため (つまり、しきい値を超えるまで)、k 最近傍アルゴリズムを使用できません。私は主に四分木とkdツリーを見てきました。
さらに、アルゴリズムは常に新しい候補クラスターを構築するため、キャッシュされた情報を使用して後続のクエリを高速化する変更されたデータ構造を使用することは興味深いでしょう (ただし、ポイントの削除も考慮に入れます)。