6

地理的なポイントをクラスター化する必要があるプロジェクトを実装しています。OPTICS アルゴリズムは非常に優れたソリューションのようです。入力として 2 つのパラメーター (MinPts と Epsilon) が必要です。これらはそれぞれ、クラスターと見なすために必要なポイントの最小数であり、2 つのポイントが同じクラスターに配置できるかどうかを比較するために使用される距離値です。

私の問題は、ポイントが非常に多様であるため、固定のイプシロンを設定できないことです。下の画像を見てください。

問題

ポイント構造は同じでもスケールが異なると、結果は大きく異なります。MinPts=2 および epsilon = 1Km に設定するとします。左側では、アルゴリズムは 2 つのクラスター (赤と青) を作成しますが、右側ではすべてのポイント (赤) を含む 1 つのクラスターを作成しますが、右側でも 2 つのクラスターを取得したいと考えています。

だから私の質問は: この結果を得るためにイプシロン値を動的に計算する方法はありますか?

EDIT 2012 年 6 月 5 日午後 3 時 15 分: javaml ライブラリの OPTICS アルゴリズム実装を使用していると思っていましたが、実際には DBSCAN アルゴリズム実装のようです。ここでの質問は、OPTICS アルゴリズムの Java ベースの実装を知っている人はいますか?

どうもありがとうございました。私の下手な英語をお許しください。

マルコ

4

4 に答える 4

4

OPTICS のイプシロン値は、インデックス構造を使用する際の実行時の複雑さを制限するためだけのものです。加速のインデックスがない場合は、infinityに設定できます。

OPTICS に関するウィキペディアを引用するには

パラメータ \varepsilon は、厳密に言えば不要です。最大値に設定できます。ただし、空間インデックスが利用できる場合、複雑さに関しては実用的な役割を果たします。

あなたが持っているように見えるものは、OPTICS よりも DBSCAN のように見えます。OPTICS では、epsilon を選択する必要はありません (作成者は max-epsilon と呼んでいたはずです!) が、クラスター抽出メソッドがそれを処理します。OPTICS 論文で提案されている Xi 抽出を使用していますか?

minPts ははるかに重要です。2 ではなく、少なくとも 5 または 10 の値を試す必要があります。2 では、基本的に単一結合クラスタリングを実行しています。

上記の例は、minPts を増やすと正常に動作するはずです!

Re: edit:ウィキペディアの記事でもわかるように、ELKI には適切な OPTICS 実装があり、それは Java です。

于 2012-06-04T20:20:10.047 に答える
1

最小スパニングツリーを試してから、最長のエッジを削除できます。残りのスパニングツリーとその中心は、OPTICSに最適な中心であり、その周囲のポイント数を数えることができます。

于 2012-07-01T20:37:39.620 に答える
1

囲む長方形の合計サイズでイプシロンをスケーリングしようとすることができます。たとえば、左のデータは約 4km x 6km (Mark I 眼球を使用して測定) で、右のデータは約 2km x 2km です。したがって、右側のイプシロンは約 2.5 倍小さくなります。

もちろん、これは確実に機能しません。右手のデータに、右に 4 km、下に 2 km の追加の単一ポイントがあった場合、右を囲む四角形は左と同じになり、同様の (間違った) 結果が得られます。

于 2012-06-04T19:02:58.293 に答える
0

上記の説明では、不確実性を生み出すのは規模の変化です。スケールが大きくなると、それに応じてイプシロンが変化するはずです。それらは2つの非常に異なる縮尺であるため、提示した2つの画像は同じポイントのセットではありません。パラメータを変更しないと、OPTICSアルゴリズムと同じように応答することはありません。

要するに、違います。この結果を得るためにイプシロンを動的に計算する方法はありません。このようなクラスタリングはすでにNP困難であり、これらのクラスタリングアルゴリズム（光学、k-means、veroni）は最適解を近似することしかできません。

于 2012-06-04T17:36:56.760 に答える