アルゴリズムを探す： '類似性'によるクラスタリング

私は 'ベクトル'のセットを持っており、それらを '類似性'に基づいて並べ替える必要があります。アルゴリズムを探す： '類似性'によるクラスタリング

このように、ベクトル{1,0,0} {1,1,0} {0,1,0} {1,0,1}はかなりシンプルで、最後には互いに接近していなければなりません。ベクトル{1、0、0} {8、0、0} {0、5、0} - はそうではありません。

AとBの間のメトリックはmax（abs（A [i] -B [i]））ですが、どのようなアルゴリズムが相対比較に基づいてソートできるのですか？

UPD：入力：Nベクトルのアレイ
ouputを：Nベクトル、インデックスベクトルによって最寄り（ARR [I] ARR [I + 1]など）されている '似' =メトリックのARRとの間の配列i]とarr [i + 1]は任意のi、jに対して可能な限り低い。
メトリック - ベクトル成分の最大差

UPD2：それは今思えるようは、@jogojapanは正しかった - 私はだグループ

出典

2012-04-16 ShPavel

「ソート」とは何を意味するのですか...メトリックはありますか？隣接するベクトル間の距離の和を最小にしたいですか？ –

ソートではなく[クラスタリング]（http://en.wikipedia.org/wiki/Cluster_analysis）（つまりグループ化）を意味するのでしょうか？ – jogojapan

私のコメントを言い換えることができます：2つの注文がある場合、どちらが良いかをどのように決定できますか？ "それぞれに近いはずです"という定義はありません... –

により、グループのベクトルをクラスタ化し、後に、いくつかの線形順序でそれらを印刷する必要があります距離はmax norm (aka sup norm or l-infinity norm)によって誘導されます。シーケンス内のordringをソートすることによって、線形順序を作成するには距離が足りません。

出典

2012-04-16 12:53:20 Memming

原点からの距離で注文できなかった理由はありません。 @Marcin可能です。 – Marcin

しかし、私はそれがuser286215が望んでいるものだとは思わない。彼は「相対比較」と言った。 – Memming

-1

任意のソートアルゴリズムによって、必要な結果が得られます。

質問はどのようにベクトルを比較するかです。規模だけで比較したいですか？または、他の何か？

出典

2012-04-16 12:54:13 Marcin

それは問題です、私はベクトルを比較することはできませんが、任意のペアについて私はどのように 'シンプリア'であるかを伝えることができます – ShPavel

@ user286215だから、問題はありません。それらがより大きい、より小さい、または同等であるかどうかをテストできる限り、どのソートアルゴリズムも機能します。 – Marcin

「より大きい、小さい、または等しいかどうかをテストできれば、それは比較の定義です。彼はちょうど彼がそれらを比較することはできないと言った..または他の視点から：彼がそれらを比較する場合、彼は間違いなく彼の目標に到達しません。 –

ソートは、本質的に1次元の問題です。あなたがここで説明していることは、加重グラフのように聞こえるが、あなたの目標が何であるかははっきりしない。 Hamming Distanceなどの情報理論から、既知のベクトルに「最も近い」ベクトルを特定しようとする場合に役立つ概念もあります。

出典

2012-04-16 12:56:33

まあ、明白なアプローチは、（IMHO悪名高い）「階層型クラスタリング」です。これらのクラスタリングは、常に最小の距離でそれらのクラスタをマージします。メトリックをそこに差し込むことができます。ほとんどの実装はO（n^3）にあり、大規模なデータセットには役に立ちません。加えて、読みにくい巨大な樹状図が得られます。

OPTICSを試してみてください。それをWikipediaで見てください。実際にはのタイプのがあるので、それはあなたのニーズをかなり満足させるかもしれません。あるクラスターから別のクラスターに移動し、実際には階層型（ネストされた）クラスター化を生成することができます。良い実装は、インデックス構造を持たないO（n^2）と、インデックスアクセラレーションを持つO（n log n）で実行する必要があります。

出典

2012-04-18 04:31:43

アルゴリズムを探す： '類似性'によるクラスタリング

答えて

関連する問題