5

私が抱えている問題は、長方形の中に長方形があることです。マップを考えてみてください。ただし、重要なポイントは次のとおりです。同様の密度を持つ長方形は、多くの場合、他の長方形と同様の寸法と x 軸上の同様の位置を共有しますが、これらの長方形間の距離は大きい場合がありますが、通常は小さい場合があります。x 軸上の位置または寸法が明らかに大きくずれている場合、それらは似ていません。

  • 長方形は交差せず、小さな長方形は大きな長方形の中に完全に入っています。

  • 長方形は、多くの場合、x 位置と寸法が類似しており (高さと幅が類似)、その中に小さな長方形があります。長方形自体は、それ自体のクラスターと見なされます。

  • これらのクラスターから別のクラスターまでの距離が非常に大きい場合があります (島について考えてみてください)。多くの場合、これらのクラスターは、同じまたは類似の寸法と、同じまたは類似のサブ長方形の密度を共有します。その場合、2 つのクラスター間の距離に関係なく、同じクラスターの一部と見なす必要があります。

  • 長方形の密度が高い (内部の長方形が小さい) ほど、近くに同じまたは類似の次元を共有する類似または同じ密度の長方形が存在する可能性が高くなります。

状況をより明確に説明する図を添付しました。

ここに画像の説明を入力

  • 赤い境界線は、これらのグループが外れ値であり、クラスターの一部ではなく、無視されることを意味します。

  • 青い境界線には多くのクラスターがあります (黒い実線の長方形を含む黒い境界線)。それらは、上記の基準 (同様の幅、同様の X 位置、同様の密度) により類似したクラスターのグループを形成します。基準 (類似の幅、類似の X 位置、類似の密度) により、右下隅に向かうクラスターでさえ、このグループの一部と見なされます。

  • ターコイズの境界線には多くのクラスターがあります (黒い実線の長方形を含む黒い境界線)。ただし、これらのクラスターは、次元、x 位置、および密度が青い境界線のものとは異なります。それらは独自のグループと見なされます。

これまでのところ、DBSCAN などの密度クラスタリングは、ノイズ (外れ値) を考慮に入れているため完璧と思われますが、事前にクラスターの数を知る必要はありません。

ただし、クラスターを形成するために必要なポイントの最小数と距離のしきい値を定義する必要があります。これら 2 つを知らず、上記の問題によって異なる場合はどうなるでしょうか。

別の一見もっともらしい解決策は、階層的 (凝集) クラスタリング (r ツリー) ですが、それがクラスターであるかどうかを判断するには、ツリーの深さレベルのカットオフ ポイントを知る必要があるのではないかと心配しています。

4

1 に答える 1

4

確かに、すべての制約を考慮する必要があります。

一般的に、あなたのタスクは、クラスタリングよりも制約充足のように見えます。

いくつかの制約クラスタリングアプローチが役に立つかもしれませんが、それらがあなたの種類の制約を許容するかどうかはわかりません。通常、リンク必須制約とリンク禁止制約のみをサポートします。

しかしもちろん、DBSCAN (特に、一般化された DBSCAN、一般化により制約を追加できる可能性があるため) と R ツリー (実際にはクラスタリング アルゴリズムではなく、データ インデックス) を試す必要があります。

R ツリーは、最小の塗りつぶしを確保するために、「外れ値」をいくつかの葉に入れることに注意してください。

上記のスケッチからでも、制約が明確に定義されていないため、これ以上詳細な推奨事項を提供することはできません。それらを疑似コードに入れてみてください。おそらく少数の長方形 (たとえば 100 個) しかありません。そのため、カスタマイズされたリンケージ基準を使用したリンケージ クラスタリングなど、非常に高価なアルゴリズムを実行する余裕があります。基準をコードに入れる作業は、すでに 99% の労力を費やしている可能性があります。

于 2013-12-27T10:13:44.460 に答える