問題タブ [dbscan]

R で DBSCAN アルゴリズムを実装しました。クラスターの割り当てをfpc ライブラリの DBSCAN 実装と一致させています。テストは、fpc ライブラリ dbscan の例で指定されているように生成された合成データで行われます。

クラスタリングは、以下のパラメーターを使用して行われます。

のクラスタ割り当てを のfpc::dbscan実装と比較していますdbscan。実行の最大値は、すべてのポイントが両方の実装で同じように分類されたことを示しています。

ただし、fpc 実装とは異なるクラスタに、私の実装では 1 ～ 2 ポイント、まれに 5 ～ 6 ポイントが割り当てられる場合があります。境界点の分類のみが異なることに気付きました。プロット後、クラスターのメンバーシップが実装で一致しないポイントが、最初に発見されたクラスターのシード ポイントに応じて、周囲のクラスターのいずれかに割り当てることができるような位置にあることがわかりました。

1ポイントの分類が異なる150ポイントの画像を表示しています（混乱を避けるため）。私の実装では、fpc 実装よりも常にミスマッチ ポイント クラスタ番号が大きいことに注意してください。

クラスターのプロット。

上の挿入図は fpc::dbscan、下の挿入図は私の dbscan 実装です

注: 私の実装と異なる点は、感嘆符 (!) でマークされています。不一致セクションの拡大画像もアップロードしています。

私の dbscan 実装の出力

+コアポイントです

o境界点です

-ノイズポイントです

!異なる点を強調する

fpc::dbscan 実装の出力

三角形はコア ポイントです。色付きの円は境界点です。黒い円はノイズ ポイントです。

もう一つの例：

私の dbscan 実装の出力

fpc::dbscan 実装の出力

編集

等しい xy スケールの例

Anony-Mousse のリクエストに応じて

場合によっては、私の実装が不一致点を正しく分類しているように見えることもあれば、fpc 実装が不一致を正しく分類しているように見えることもあります。下記参照：

fpc::dbscan (三角形のプロットのもの) は、不一致点を正しく分類しているようです

私のdbscan実装（+プロットのもの）は、不一致点を正しく分類したようです

質問

• 私はクラスター分析が初めてなので、別の質問があります。これらのタイプの違いは許容されますか?

• 私の実装では、最初のポイントから最後のポイントまでスキャンしています。またfpc::dbscan、ポイントは同じ順序でスキャンされます。!このような場合、両方の実装で、同じクラスタ センターから不一致ポイント ( でマーク) が検出されているはずです。また、ポイントをノイズとしてマークするいくつかのケースを生成しましたfpc::dbscanが、私の実装ではそれをいくつかのクラスターに割り当てます。この場合、なぜこの違いが生じるのでしょうか?

要求に応じてコード セグメント。

DBSCAN アルゴリズムを使用して類似の URL をグループ化する方法。私は多くのデータセットを見てきましたが、どれも url にありませんでした。同様のタイプの URL を取得してグループ化したいと考えています。ここでは、距離 (eps) を知ることができず、minpoints はグループ化する URL の数にすることができます。

重複の可能性:
同様の URL のグループ化に DBSCAN アルゴリズムを適用する方法

プロジェクトはDBSCANを使用して同様の文字列をクラスタリングすることに関係しているため、最終的なsemでプロジェクトを実行するように言われました。DBSCAN を使用してこれを実行できるかどうかを知りたいです。そうであれば、どうすれば同じことを実装できますか。

こんにちは私はNeo4j用のDBSCANアルゴリズムを実装しようとしていますが、深刻なパフォーマンスのボトルネックに直面しています。実装について説明してから、助けを求めます。

1つのクエリですべてのコアノードを取得できるように、可能なイプシロン値を離散化し、各ノードの各離散化の下にあるネイバーの数をカウントしました。

この部分は高速ですが、高速でない部分はフォローアップクエリです：

次に、開始するコアノードを選択し、コアノードのネイバーがまだ存在する限り、上記のクエリを実行してネイバーにラベルを付けます。

問題は、私のグラフのスパース性のレベルが非常に異なることだと思います。類似性が弱いことから始めて、ほぼ完全に接続されており、ノード間で約5,000万の関係がありますが、類似性が高い場合は、約10,000の間にわずか20kの関係があります。ノード（またはそれ以下）。何があっても、それは常に本当に遅いです。これを処理するための最良の方法は何ですか？関係タイプと開始ノードのインデックスを作成するのですか？この問題に関するリソースを見つけることができませんでした。驚くべきことに、これはかなり標準的なグラフアルゴリズムであるため、実装はまだありません。scikit.learnを使用することもできますが、メモリ内の距離行列のみに制限されます:(

私はこの質問に対する答えをかなり前から探していたので、誰かが私を助けてくれることを願っています。Rのfpcライブラリのdbscanを使用しています。たとえば、USArrestsデータセットを見て、次のようにdbscanを使用しています。

この場合、epsの選択は試行錯誤によるものでした。ただし、最適なeps/minptsの選択を自動化するために使用できる関数またはコードがあるかどうか疑問に思っています。いくつかの本が、最も近い隣人までのk番目にソートされた距離のプロットを作成することを推奨していることを知っています。つまり、x軸は「k番目に近い隣接距離に従ってソートされたポイント」を表し、y軸は「k番目に近い隣接距離」を表します。

このタイプのプロットは、epsとminptsの適切な値を選択するのに役立ちます。誰かが私を助けてくれるのに十分な情報を提供したことを願っています。自分の言いたいことの写真を投稿したかったのですが、まだ初心者なので、まだ画像を投稿できません。

ELKI環境でのOPTICS実装の使用に問題があります。私はDBSCANの実装に同じデータを使用しましたが、それは魅力のように機能しました。おそらく私はパラメータで何かが欠けていますが、それを理解することはできません、すべてが正しいようです。

データは単純な300х2行列であり、それぞれに100ポイントを持つ3つのクラスターで構成されます。

DBSCANの結果：

DBSCANのクラスタリング結果

MinPts = 10、Eps = 1

光学結果：

OPTICSのクラスタリング結果

MinPts = 10

最近は、DBSCAN matlab コードの速度を向上させるために、C-mex コードに取り組んでいました。実際、現時点では、C-mex で DBSCAN を終了しました。しかし、代わりに、マトリックス 3 x 14414 であるテスト データを使用すると、より多くの時間がかかります (matlab で 14.64 秒、C-Mex で 53.39 秒)。これはmxRealloc、コードのいくつかの部分で関数を使用しているためだと思います。より良い結果を得るために、誰かが私にいくつかの提案をしてくれるとうれしいです。

コード DBSCAN1.c は次のとおりです。

https://www.dropbox.com/sh/mxn757a2qmniy06/PmromUQCbO

このコードを使用すると、個々のクラスターをプロットできることがわかります。

上記のコードでは、次の出力が得られます。

11個のクラスターすべてを取得しています。

特定のクラスター内のデータを表示したい場合、そのためにどの R スクリプトを作成する必要があるか。

私は論文に WEKA を使用しており、1000 行以上のデータがあります。データベースには、人口統計情報 (年齢、場所、ステータスなど) の後に製品名 (1 または 0 の値) が含まれます。最終結果は推薦システムです。クラスタリングの 2 つの方法を使用K-MeansしDBScanました。

使用K-means時に 3 つの異なる数のクラスターを試し、使用DBscan中に 3 つの異なるイプシロンを選択しました (イプシロン 3 = データの 17% が無視された 48 クラスター、イプシロン 2.5 = 19 クラスター、クラスター 0 は無視された 6% の 229 アイテムを保持します)。同じデータに対する 6 つの異なるクラスタリング結果。

自分のデータに最適なものを選択するにはどうすればよいですか?