4

ポイントがプロットされ、一部またはすべてにラベルが付いているグラフィカルな xy プロットからセマンティクスを抽出しようとしています。ラベルは「ポイントの近く」にプロットされるため、人間は通常、どのラベルがどのポイントに対応しているかを理解できます。たとえば、このプロットでは、どのラベル (番号) がどのポイント (*) に属しているかが明確であり、ユークリッド距離に基づくアルゴリズムが機能します。(ラベルとポイントには意味的な順序付けはありません - 散布図など)

 *1
    *2

        *3

      *4

混雑したプロットでは、オーサリング ソフトウェア/人間は、重複を避けるためにラベルを異なる方向に配置する場合があります。たとえば、

1**2
 **4
 3

人間のリーダーは通常、どのラベルがどのラベルに関連付けられているかを判断できます。

私が受け入れる1つの解決策は、ユークリッド距離行列を作成し、行をシャッフルして関数の最小値を取得することです(たとえば、対角線または他のヒューリスティック上の距離の合計二乗)。2 番目の例 (北西の角から時計回りに a、b、c、d のラベルが付いた点) では、(1 dp までの) 距離行列があります。

             a   b   c   d
 1ab2    1  1.0 2.0 2.2 1.4    
  dc4    2  2.0 1.0 1.4 2.2
  3      3  2.0 2.2 1.4 1.0
         4  2.2 1.4 1.0 2.0

ラベルを付ける必要がありa1 b2 c4 d3ます。行 3 と 4 を入れ替えると、対角線の最小和が得られます。最も近いものを選択するだけでは失敗する可能性がある、より複雑な例を次に示します。

 *1*2*5
  **4
  3 *6

これが解決された場合、ラベルの数がポイントの数よりも少ないか多い場合に行く必要があります。

アルゴリズムが標準である場合は、オープン ソース Java (JAMA や Apache maths など) へのポインタをいただければ幸いです。

注: この SO の回答ポイントを通るパスが指定されているため、近くのポイントをパスに関連付けることは回答としては機能しません。

4

3 に答える 3

6

1 つの部分が数値で、もう 1 つの部分が点である完全な 2 部グラフがあります。このグラフのエッジの重みは、数値と点の間のユークリッド距離です。そして、あなたの仕事は、最小の重みでマッチングを見つけることです。

これは既知の問題であり、次の名前のよく知られたアルゴリズムがありますHungarian Algorithm。

ウィキから：

非負の n×n 行列が与えられます。ここで、i 番目の行と j 番目の列の要素は、j 番目の点を i 番目の数に割り当てるコストを表します。最小コストを持つ数字へのポイントの割り当てを見つけなければなりません。目標が最大コストを生み出す割り当てを見つけることである場合、各コストを最大コストからコストを引いたものに置き換えることで、設定に合うように問題を変更できます。

二部グラフを使用して問題を定式化すると、アルゴリズムの記述が容易になります。n 個の頂点 (S) と n 個の点頂点 (T) を持つ完全な 2 部グラフ G=(S, T; E) があり、各エッジには非負のコスト c(i,j) があります。最小限のコストで完璧なマッチングを見つけたいと考えています。ハンガリアン法は、多項式時間で代入問題を解く組み合わせ最適化アルゴリズムであり、後の主双対法を予期していました。へ

詳細なアルゴリズムとコードについては、トップコーダーの記事 とこのpdfを参照してください。

それを説明するメディアファイルがあります。(このビデオでは、ハンガリーのアルゴリズムが機能する理由を説明しています)

アルゴリズム : ステップ 1:- コスト マトリックスを準備します。コスト マトリックスが正方マトリックスでない場合は、コスト要素がゼロのダミーの行 (列) を追加します。

ステップ 2:- 各行のすべての要素から各行の最小要素を減算します。

ステップ 3:- それぞれの列のすべての要素から各列の最小要素を減算することにより、結果の行列をさらに変更します。こうして、変更された行列を取得します。

ステップ 4:- 次に、水平線と垂直線の最小数を描画して、結果の行列のすべてのゼロをカバーします。最小行数を N とします。2 つの可能なケースがあります。

ケース 1 - N=n の場合 (n は行列の次数)、最適な割り当てを行うことができます。そのため、必要な解を得るために割り当てを行います。

ケース 2 - N が n 未満の場合、ステップ 5 に進みます

ステップ 5: 行列内の最小のカバーされていない要素 (N 行でカバーされていない要素) を決定します。すべてのカバーされていない要素からこの最小要素を減算し、水平線と垂直線の交点に同じ要素を追加します。したがって、2 番目の変更された行列が取得されます。

ステップ 6:- ステップ 4 のケース (1) が得られるまで、ステップ (3) と (4) を繰り返します。

ステップ 7:- (ゼロ割り当てを行うため) 行単位で正確に単一のゼロが見つかるまで、行を連続的に調べます。割り当てを行うために、このゼロに丸 (o) を付けます。すべてのゼロが調べられるまで、この方法を続けます。列についても同じ手順を繰り返します。

ステップ 8:- 次のいずれかの状況が発生するまで、ステップ 6 を連続して繰り返します。次に、マークされていないゼロの1つを任意に丸で囲み、その行または列に残っているゼロのセルに十字をマークします。マークされていないゼロが行列に残らなくなるまで、このプロセスを繰り返します。

ステップ 9:- したがって、行列の各行と各列でマークされた丸で囲まれたゼロが 1 つだけ取得されます。これらのマークされた円のゼロに対応する割り当てにより、最適な割り当てが得られます。

詳細については、wiki およびhttp://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdfを参照してください。

于 2012-04-20T01:31:01.820 に答える
1

この場合の一般的なアルゴリズムは見たことがありません。したがって、私はこの問題を実用的に解決します。

ポイントに属するラベルが常に最も近くにあると仮定すると（おそらく他のラベルと一緒に）、領域成長アルゴリズムに方向付けることができます（アニメーションGIFを参照）。成長ステップごとにすべてのポイント (赤) を反復処理します (番号ラベルを囲む円)。成長ステップは、ポイントとラベルの間の最小距離によって決まります。

地域の成長

ポイントとラベルには一時リストを使用します。明確なペアを見つけるたびに、対応するポイントとラベルを削除します。最も近い点が複数ある場合は、ラベルをスキップしてください (ここではラベル 2)。他のポイントとラベルの組み合わせ (ここではラベル 3) を解決することにより、別の反復でマッピングする必要があります。

全体的にあいまいな状況が原因で何の進歩も見られない反復の後、それらを解決するための選択方法を定義できます (たとえば、下より上、右より左を優先)。

于 2012-04-19T17:29:31.820 に答える