問題タブ [dbscan]

ELKI の OPTICS アルゴリズムを使用してクラスター化したい 100,000 点があります。このポイント セットには、約 50 億エントリの上三角距離行列があります。ELKI がマトリックスを希望する形式では、約 100 GB のメモリが必要になります。ELKI はその種のデータ ロードを処理するのでしょうか? 以前にこの作業を行ったことがあるかどうか、誰でも確認できますか?

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

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

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

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

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

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

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

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

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

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

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

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

ドメインにさまざまなレベルのパスの深さと類似性を持つ URL のリストがあるとします。

密度 (スラッシュの数) と類似性 (テキストの距離、レーベ​​ンシュタイン) に基づいて URL 文字列をクラスター化するために使用できるアルゴリズムは何ですか?

したがって、出力はグループにクラスター化されます。

いくつかの特徴: - URL 文字列の密度が高い (または深い) ほど、関連性が高くなり、連続して繰り返される可能性が高くなります。- 同様の URL のチャンクが次々と繰り返されます。似ていない URL は、似たような URL の塊から離れているように見えます。

DBSCAN はここで適切ですか?

(濃度、LV距離)

スラッシュまでの最後の文字を消去してから、後続の文字列で一致を検索することを考えました。一致がリスト内の次の URL である場合、それらはチャンクである可能性があります。一致がリストのさらに下にある場合は、チャンクの一部ではない可能性があります。

これはほとんどどこにでもあるため、チャンクの一部ではありません。

候補の直後に見つかった 2 つの後続の一致を検索します。

連続して発生する 3 つの一致を検索します。そのため、それらはまとめられています。

ウェイの一番下でもう 1 つの一致を見つけます。距離があるため、どちらもチャンクの一部ではありません。このアプローチの名前またはこれに沿った何かはありますか?

ユーザーが入力パラメーター (minPts および Eps) を入力する必要がない、DBSCAN アルゴリズムの何らかの改善を実装したいと考えています。私の考えは、K 距離プロットを使用することですが、このプロットの「膝」を計算する最良の方法は何ですか? プロットに 2 つ以上の膝がある場合、どのように数えますか?

AUTODBSCAN、VDBSCAN、PDBSCAN、DBSCAN-DLP など、DBSCAN を改善するためのソース コードはどこにありますか? いくつかの基本を探していますが、適切なヘルプがどこにも見つかりません。サンプルソースコードをどこかで見たことがありますか?

http://scikit-learn.orgで DBSCAN アルゴリズムの例がわかりにくいことがわかりました。緯度と経度のリストがあり、ここで DBSCAN アルゴリズムの入力を準備する方法に興味がありました。