8

言語K meansで実装しようとしhadoop-1.0.1ています。java私は今イライラしています。but の完全実装のgithubリンクをもらいk meansましたが、初心者なHadoopので他人のコードをコピペせずに習得したいです。hadoopで利用できる基本的な知識mapとreduce機能があります。誰かが私に実装してクラス化するアイデアを提供してくれますか? 反復が必要ですか？k means mapperreducer

4

1 に答える 1

11

それでは、MapReduce で k-means を実装するときに私が考えたことをお話しします。この実装は Mahout の実装とは異なります。主な理由は、アルゴリズムが分散セットアップでどのように機能するかを示すためです (実際の運用では使用されません)。また、k-means がどのように機能するかを本当に知っていると思います。

そうは言っても、アルゴリズム全体を 3 つの主要な段階に分割する必要があります。

  1. 職務レベル
  2. マップレベル
  3. レベルを下げる

ジョブレベル

ジョブ レベルは非常に単純です。入力 (キー = 呼び出されるクラスClusterCenter、値 =呼び出されるクラスVectorWritable) を書き込み、Hadoop ジョブで反復を処理し、ジョブ全体の出力を読み取ります。

VectorWritableこの場合は私自身の数学ライブラリからのベクトルのシリアル化可能な実装ですが、実際には単純な double 配列に他なりません。

はClusterCenter主にVectorWritableですが、センターが通常必要とする便利な機能 (平均化など) を備えています。

k-means では、最初の中心である k-vector のシードセットと、クラスター化するいくつかの入力ベクトルがあります。MapReduce でもまったく同じですが、2 つの異なるファイルに書き込んでいます。最初のファイルにはベクトルといくつかのダミー キー センターのみが含まれ、もう 1 つのファイルには実際の初期センター (つまりcen.seq) が含まれます。

すべてがディスクに書き込まれた後、最初のジョブを開始できます。Mapperもちろん、これは次のトピックであるa を最初に起動します。

マップレベル

MapReduce では、(オブジェクトに関して) 入ってくるものと出ていくものを知ることは常に賢明です。したがって、ジョブ レベルから入力としてClusterCenterandがあることがわかりますが、は現在のところ単なるダミーです。map ステージは通常の k-means からの有名な割り当てステップであるため、出力と同じにしたいのは確かです。VectorWritableClusterCenter

入力ベクトルとセンターを比較するために、ジョブ レベルで作成した実際のセンター ファイルをメモリに読み込んでいます。したがって、この距離メトリックが定義されています。マッパーでは、にハードコードされていManhattanDistanceます。もう少し具体的に言うと、マップ段階で入力の一部を取得し、各入力の「キーと値のペア」(キーと値で構成されるペアまたはタプル) を各センターと比較して反復処理します。 . ここでは、どの中心が最も近いかを追跡し、最も近いClusterCenterオブジェクトを入力ベクトル自体とともにディスクに書き込むことで、中心に割り当てます。

次に、出力は次のとおりです。n-ベクトルと、割り当てられた中心 (キーとして)。Hadoop はキーでソートおよびグループ化するようになったため、reduce タスクで単一の中心に割り当てられたすべてのベクトルを取得します。

リデュース レベル

上で述べたように、reduce 段階ではClusterCenterとそれに割り当てられた があります。VectorWritableこれは、通常の k-means で行う通常の更新手順です。したがって、すべてのベクトルを単純に繰り返し処理し、それらを合計して平均しています。

これで、以前に割り当てられた平均と比較できる新しい「平均」が得られました。ここでは、中心がどれだけ移動したかを示す 2 つの中心の差を測定できます。理想的には動かなかっただろうし、converged.

Hadoop のカウンターは、この収束を追跡するために使用されます。この名前は、最終的な点に収束していないセンターの数を実際に追跡するため、少し誤解を招く可能性があります。

基本的に、次の反復のために、新しい中心とすべてのベクトルを再びディスクに書き込んでいます。さらに、クリーンアップ ステップでは、新しく収集されたすべての中心をマップ ステップで使用されるパスに書き込むので、新しい反復には新しいベクトルが含まれます。

ジョブ ステージに戻ると、MapReduce ジョブを実行する必要があります。現在、そのジョブのカウンターを調べて、まだ収束していないセンターの数を取得しています。このカウンターは、while ループで使用され、アルゴリズム全体が終了できるかどうかを判断します。そうでない場合は、再びマップ レベルの段落に戻りますが、前のジョブからの出力を入力として使用します。

実際、これはVooDoo全体でした。

明らかな理由から、これはパフォーマンスがひどいため、本番環境では使用しないでください。より調整されたバージョンの Mahout を使用することをお勧めします。しかし、教育目的では、このアルゴリズムは問題ありません;)

他にご不明な点がございましたら、メールまたはコメントでお気軽にお問い合わせください。

于 2012-05-18T18:38:52.193 に答える