5

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

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

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

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

イプシロン=1000; xi=0.05; minpts=100;

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

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

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

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

イプシロン=2000; xi=0.025; minpts=100;

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

イプシロン=250; xi=0.035; minpts=10

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

イプシロン=250; xi=0.035; minpts=100

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

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

4

1 に答える 1

2

OPTICS プロットからクラスターを抽出する際の問題は、クラスターの最初と最後の要素です。プロットだけでは、(私の理解では) 最後の要素が前のクラスターに属すべきかどうかを判断できません。

このようなプロットを考えてみましょう

*
*        *
*        *
*       **
**************
A B C D EF G H

これは、A が真ん中にあり、BE が近くにあり、F が完全に異なるクラスター内の最も近い要素であるクラスターである可能性があります。たとえば、データセットは次のようになります。

  *   D           *
B   A     E     F   G 
  *   C           H   *

または、A は最初のクラスターの縁にあり、BD はクラスターの一部ですが、E はクラスター FH へのギャップを埋める外れ値要素です。このような効果を引き起こすデータ セットは、次のようになります。

  D   *                 *
*   C   B  A    E     F   G 
  E   *                 H   *

OpticsXi は視覚的に動作します。F は分割する「より急な」ポイントであるため、Eはいずれの場合も最初のクラスターの一部になります。これは文字通り、OpticsXi がデータ ポイントを見ずに行うことができる最良の推測です。

これは、あなたが観察しているスパイクを引き起こしている可能性があります。

次の 4 つのオプションが表示されます。

  1. OpticsXi を自分で改善してください。興味があれば、上記の 2 つのケースを区別するためのヒューリスティックについて説明できます。

  2. 変曲点などの他の抽出方法の1つを実装します（ただし、プロットAFAICTにあるため、同じ影響を受ける可能性があります）

  3. HDBSCAN を使用します (申し訳ありませんが、ELKI にはまだ含まれていませんが、動作しているように見えるバージョンがあります) - おそらく 0.7.0 で

  4. クラスタに後処理を適用します。特に、最初と最後のいくつかのポイントをクラスターの順序でテストします。それらをクラスターに含める場合は、次のポイントに移動するか、親クラスターに移動します。たぶん、クラスターからの平均距離で...

于 2014-06-23T17:49:45.417 に答える