0

演習として、自分で Spark を使用してk-meansを実装しています。これを行うにはid -> cluster_id、各ステップで の 2 つのマップを比較する必要があります。現在、私はそれらの両方を収集し、2 つの単純なスカラ マップとして比較することでそれを行っています。

これを並行して行う方法はありますか？その価値はありますか？

アップデート：

K-MEANSクラスタリングアルゴリズムから始めて、状況を詳しく説明しましょう（簡単です）

  1. それらを重心にするすべての N ポイントからランダムな K ポイントを選択します。
  2. 各点を最も近い重心に割り当てます（ユークリッド距離に従って）
  3. 重心を再計算し、割り当てられた重心ですべてのポイントをグループ化し、それらの平均を計算します
  4. 再計算によって、前のステップのもの以外のマッピング (obj_id -> centroid_id) が生成された場合は、ステップ 2-3 を繰り返します。

ステップ＃4が問題です。前のステップで持っていたマッピングと現在持っているマッピングを比較する必要があります。これは、ワーカー全体でランダムな読み取りをあまり行わずに、何らかの形で並行して行う必要があります。

4

1 に答える 1

1

それらを「比較する」とはどういう意味かわかりません。あなたの質問への答えは本当にそれに依存します! 詳細を提供していただければ、それに応じて回答を編集しますが、一般的な質問からは一般的な回答しか得られません ^_^

等価性をテストする必要があるだけの場合は、非常に簡単です (マップで期待されるように、順序に依存しません)。

val x = Map[Int, Int](1->2, 2->3)
val y = Map[Int, Int](2->3, 1->2)
(x == y) == true

キーセットが同じでマッピングが異なることのみをテストしたい場合 (おそらく、更新ステップの終了をテストしたいため)、キーをイテレータまたはセットとして直接比較できます。

(x.keys == y.keySet) == true

マップが大きすぎて等価性テストを並行して行いたいという事実から問題が発生した場合、事態は複雑になります。キーに従ってペアを分割し、すべてのスライスを並行してチェックすることができます。小切手が正の場合、平等になります。これを行うには、x AND y をキー値/ハッシュに従ってスライスに分割し、別のアクターに送信する (たとえば、アクターを使用している場合) か、単に x を反復処理して別のアクターで y の値をチェックします。その鍵のために。

どちらの場合も、これは次のいずれかの場合にのみ意味があると思います。a) 2 つのマップが同じプロセスのメモリ内にないため、それらへのアクセスが遅く、ブロックされている。b) 比較が単なる値の等価性ではなく、ある程度の集中力が必要である。非同期パイプラインの恩恵を受けることができる計算。

基本的で一般的なマップ構造を使用しているという前提で回答したことに注意してください。パフォーマンスの制約がある場合は、特定のニーズに合わせて調整された独自のマップ構造を実装することをお勧めしますが、ライブラリのバージョンが最適化されていないため、独自のものよりも優れたパフォーマンスを発揮できないというシナリオを想像することはほとんどありません。

編集 新しい情報を考えると、私の答えはまだほとんど変わっていません。キーのハッシュによって割り当てられた n 個のスライスに x のエントリを分割し、y に同じ値のエントリが含まれているかどうかを確認します。

于 2014-10-23T08:23:57.470 に答える