問題タブ [optics-algorithm]

都市のユーザー生成データなど、密度が変化する領域でクラスターを検出することに興味があり、そのためにOPTICSアルゴリズムを採用しました。

DBSCANとは異なり、OPTICS アルゴリズムは厳密なクラスター パーティションを生成しませんが、データベースの順序付けを拡張します。クラスター パーティションを生成するために、OPTICSxi を使用します。これは、OPTICS の出力に基づいて分類を生成する別のアルゴリズムです。OPTICS の出力からクラスター パーティションを抽出できるライブラリはほとんどなく、ELKIの OPTICSxi 実装はその 1 つです。

DBSCAN の結果をどのように解釈するかは、私には非常に明確です (ただし、「意味のある」グローバル パラメータを設定するのはそれほど簡単ではありません)。DBSCAN は、面積あたりのポイント数 (minpts/epsilon) で表される密度によって特徴付けられるクラスターの「プロトタイプ」を検出します。OPTICSxi の結果は、解釈が少し難しいようです。

OPTICSxi の出力で時々検出する現象が 2 つありますが、説明できません。1 つは、マップの一部をリンクする「スパイク」クラスターの出現です。それらは非常に少数のポイントで構成されているように見え、アルゴリズムがそれらを同じクラスターにグループ化する方法を理解していないため、説明できません。それらは本当に密度変化の「回廊」を表しているのでしょうか? 基礎となるデータを見ると、そのようには見えません。これらの「スパイク」は、次の画像で確認できます。

私が説明できないもう 1 つの現象は、同じ階層レベルの「重複する」クラスターが存在する場合があるという事実です。OPTICSxi は、データベース (樹形図など) の OPTICS 順序付けに基づいており、そのダイアグラムには繰り返しポイントはありません。

これは階層的クラスタリングであるため、下位レベルのクラスターには上位レベルのクラスターが含まれていると見なし、凸包を構築するときにその考えが適用されます。ただし、同じ階層レベルで他のクラスターと交差するクラスターを持つことの正当性はわかりません。これは、実際には、いくつかのポイントが二重のクラスター「メンバーシップ」を持つことを意味します。以下の画像では、同じ階層レベル (0) を持ついくつかの交差するクラスターを見ることができます。

最後に、私があなたに残しておきたい最も重要な考え/質問は、OPTICSxi クラスタリング分類で何が見られると予想されるかということです。この問題は、OPTICSxi をパラメータ化するタスクと密接に関連しています。

特定のクラスター問題に対して OPTICSxi を実行した研究はほとんど見られないため、最適なクラスター分類が何であるかを見つけるのに苦労しています。つまり、意味のある/有用な結果を提供し、DBSCAN クラスタリングに何らかの価値を追加できるものです。その質問に答えるために、さまざまなパラメーターの組み合わせで OPTICSxi を何度も実行し、以下で説明する 3 つを選択しました。

この実行では、大きな値のイプシロン (2Km) を使用しました。この値の意味は、大きなクラスター (最大 2Km) を受け入れることです。アルゴリズムはクラスターを「マージ」するため、非常に大きなクラスターになり、ほぼ確実に密度が低くなります。私はこの出力が好きです。なぜなら、それは分類の階層構造を明らかにするからです。また、実際には、OPTICS の宣伝されている「強み」である、異なるパラメーターの組み合わせ (異なる密度) を使用して DBSCAN をいくつか実行したことを思い出させます。前に述べたように、クラスターが小さいほど、階層スケールのレベルが高くなり、密度が高くなります。

この実行では、「コントラスト」パラメーターが前回の実行と同じであっても、多数のクラスターが見られます。これは主に、少数の minpts を選択したためです。これにより、少数のポイントを持つクラスターを受け入れることが確立されました。この場合のイプシロンは短いため、これらの大きなクラスターがマップの大部分を占めることはありません。この出力は、前の出力ほど興味深いものではないと思います。主な理由は、階層構造を持っていても、同じレベルに多くのクラスターがあり、それらの多くが交差しているためです。解釈的には先ほどと似た全体的な「形」が見えますが、実際には「ノイズ」として見逃されやすい小さなクラスターがたくさん散らばっています。

この実行では、minpts が大きいことを除いて、前の実行と同様のパラメーターの選択があります。その結果、検出されるクラスターが少なくなり、重なりが少なくなるだけでなく、ほとんど同じレベルになります。

DBSCAN に価値を付加する観点から、最初のパラメーターの組み合わせを選択します。これは、データの階層図を提供し、どの領域がより密度が高いかを明確に明らかにするためです。パラメータの最後の組み合わせである私見は、調査地域全体で同様のクラスターを見つけているため、密度のグローバル分布のアイデアを提供できません。私は他の意見を読むことに興味があります。

私は自分のデータで「OPTICS」アルゴリズムを実行しようとしています。私のデータには約 40000 のレコードがあり、それぞれに 3 つの属性と各レコードの ID があります。興味深いことに、「OPTICS」を 3 つの属性だけで実行すると、ELKI は「stackoverflow」に関するエラーを返しますが、4 つの属性を含めて実行すると問題なく実行されます。私のデータに問題はありますか? !

ヒストグラム プロットが複数の極大値を示す 1 次元データ セットがあるため、1 次元空間にはデータがより密集している領域が複数あることがわかっています。特定のデータポイントが含まれる密集領域/クラスターを分類できるように、これらの密集領域の境界を決定したいと考えています。これには、比較するクラスター間の異なる密度をより適切に処理できるはずである OPTICS を使用しています。 DBSCANに。

JavaコードでELKI（バージョン0.6.0）を使用しています（ELKIチームがELKIをJavaに埋め込むことを推奨していないことは知っていますが、多くのデータセットに対してワークフローを繰り返す必要があるため、私の場合はこれを自動化することをお勧めします） . 以下のコード スニペットは、クラスターの開始項目と終了項目のインデックスを出力します。OPTICSModelに関するELKI ドキュメントでは、これらのインデックス番号が何に対応するかを明確に定義していませんが、これらはデータベースの拡張クラスター順序付けにおける開始データ項目と終了データ項目のインデックスであると想定しています (OPTICS.run() の ClusterOrderResult オブジェクトなど)。データベース自体の開始データ項目と終了データ項目のインデックス (順不同) とは対照的です。

ここで、1 次元空間のどこでクラスターが開始および終了するかを知りたいと考えています。したがって、上記のコードが既に取得している開始インデックスと終了インデックスに対応するデータ項目を取得したいと思います。取得したインデックスを取得できる ClusterOrderResult オブジェクトが必要になると思います。ただし、ドキュメントでは、optics.run() を呼び出して取得したクラスタリング結果オブジェクトからそのようなものを取得することはできないようです。この順序付けられたデータベースを取得する方法がないように思われたため、上記のコードの println を以下の println に置き換えることにより、代わりに元の入力データセットからインデックスを取得しようと単純に試みました。

ただし、既に予想していたように、インデックスは元の入力ファイルに属していないようです。これは、1 次元空間で終了境界よりも低い値で終了境界を定期的に出力するためです。OPTICS クラスタリングで見つかった開始インデックスと終了インデックスに対応する元の 1 次元データ値を取得する方法を知っている人はいますか? これらの値を後でコードで使用したいと考えています。

ELKI で OPTICS および DeLiClu アルゴリズムを実行すると、結果としてクラスター オブジェクト オーダー ファイルのみが取得されます。クラスターのリストと、ポイントとそれぞれのクラスター間のマッピングを取得するにはどうすればよいですか?

私は ELKI の初心者で、これを使用して .csv ファイルから約 10,000 の緯度経度ポイントをクラスター化しています。設定が正しくなったら、1MM ポイントまでスケールアップしたいと思います。

LngLatDistanceFunction で OPTICSXi アルゴリズムを使用しています

パフォーマンスの大幅な改善を確認するために、「STR 一括読み込みで R* ツリー インデックスを有効にする」について読み続けています。チュートリアルはあまり役に立ちませんでした。

この機能を実装する方法に関するヒントはありますか?

Optics アルゴリズムを実行するためにデータを適切に ELKI に取り込むのに問題がありますが、Optics の R 実装を使用すると、到達可能距離のリストを簡単に取得できます。このようなファイルに書き込むことができます。(指数、距離)

1 情報

2 0.5

3 0.9 ...

極小値で区切られたクラスターを見つけたいです。ELKI ソフトウェアの Optics Xi アルゴリズムがこれを行うと思いますが、データのインポートに問題があるため、使用できません。

Optics 論文の疑似コードを使用して、Optics クラスター抽出アルゴリズムを別の言語で記述する方が簡単でしょうか? 最も基本的なことは、インデックスが互いに隣接しているときにインデックスをクラスター化するだけであり、新しい局所最小値への減少はないと思います。

ありがとう

このアルゴリズムを自分のデータセットで機能させることができないようです。そのため、データの非常に小さなサブセットを取得して機能させようとしましたが、それも機能しませんでした。

事前に計算された距離行列を ELKI に入力し、ポイントの到達可能距離リストを検索させたいのですが、すべてのポイントで到達可能距離が 0 になります。

私の ELKI の主張は次のとおりです。

実行中: -dbc DBIDRangeDatabaseConnection -idgen.start 1 -idgen.count 4 -algorithm clustering.optics.OPTICSList -algorithm.distancefunction external.FileBasedDoubleDistanceFunction -distance.matrix /Users/jperrie/Documents/testfile.txt -optics.epsilon 1.0 -optics .minpts 2 -resulthandler ResultWriter -out /Applications/elki-0.7.0/elkioutputtest

入力ファイルの代わりに DBIDRangeDatabaseConnection を使用してインデックス 1 ～ 4 を作成し、次の形式の距離行列を渡します。ここで、各行には 2 つのインデックスと距離があります。

私が間違っている場所へのポインタをいただければ幸いです。

DBSCAN と OPTICS でロケーション クラスタリングを実行するために、ELKI を使用しています。私のデータセットには 30 人の参加者が含まれていますが、ラベルは付けられていませんが、各参加者の頻繁な場所として座標 (自宅、職場など) のペアがあります。

これらの座標のペアがどのクラスターに属しているかを知りたい (人ごとに)。方法の 1 つは、いくつかの最小距離しきい値を使用して、各クラスターに対して各ペアを手動でチェックすることです。

これを達成するためのより良い方法は何でしょうか?