0

Mahout K-means を実行すると、奇妙な状況が発生します。事前に選択された初期重心のセットを使用して、lucene.vector によって生成された SequenceFile で K-means を実行します。実行はテスト目的のため、ファイルは小さいです (約 10MB~10000 ベクトル)。

K-means が単一のマッパー (私のクラスターでは 128MB である Hadoop 分割サイズを考慮したデフォルト) で実行されると、2 回の反復で所定のクラスタリング結果に到達します (ケース A)。ただし、より多くのマッピング タスクを起動することで、アルゴリズムの実行速度が改善/低下するかどうかをテストしたかった (Hadoop クラスターには合計 6 つのノードがある)。したがって、-Dmapred.max.split.size パラメーターを 5242880 バイトに設定して、mahout が 2 つのマッピング タスクを起動するようにします (ケース B)。確かに 2 つのマッパーを開始することに成功しましたが、奇妙なことに、ジョブは 2 回ではなく 5 回の反復で終了し、クラスタへのポイントの最初の割り当てでも、マッパーは単一マップの実行とは異なる選択をしました。

この動作は、既存の K-means Mahout 実装によって正当化されるでしょうか?

4

1 に答える 1

1

ソースをざっと見てみると、Mahout の k-means 実装には 2 つの問題があることがわかります。

まず第一に、S0、S1、S2 の統計が保持される方法は、大規模なデータ セットでは数値的に安定していない可能性があります。ああ、k-means は実際には S2 も使用しないため、不必要に遅くなります。良い実装は、このバージョンの k-means を少なくとも 2 ～ 5 倍上回ることができるに違いありません。

複数のマシンに分割された小さなデータ セットの場合、平均を計算する方法にエラーがあるようです。ああ。これは、リデューサーが複数の入力に適用される場合、特にパーティションが小さい場合に増幅されます。より詳細に説明すると、クラスターの平均は、0 ベクトルではなく前の平均で初期化されているようです。その「t」個のコピーを減らすと、結果のベクトルは前の平均の「t」倍ずれます。

の初期化AbstractCluster:

setS1(center.like());

平均の更新:

getS1().assign(x, Functions.PLUS);

クラスターの複数のコピーのマージ:

setS1(getS1().plus(cl.getS1()));

新しいセンターへのファイナライズ:

setCenter(getS1().divide(getS0()));

したがって、このアプローチでは、分割の数とオブジェクトの数でt / nある前の中心時間によって、中心が適切な値からオフセットされます。tn

数値の不安定性 (データ セットが 0 ベクトルを中心としていないときに発生する) を修正するには、S1 統計を S0*平均ではなく真の平均に置き換えることをお勧めします。S1 と S2 はどちらも、MacQueen によるオリジナルの「k-means」出版物で AFAICT が使用された増分平均式を使用して、わずかなコストで増分的に更新できます (これは実際にはオンラインの kmeans ですが、これは Lloyd スタイルのバッチ反復です)。まあ、増分k-meansの場合、とにかく更新可能な平均ベクトルが明らかに必要です...この式は、Knuthによって彼の重要な本でも議論されたと思います。驚いたことに、Mahout はそれを使用していないようです。これはかなり安価で (CPU 命令数が増えるだけで、追加のデータがないため、すべて CPU キャッシュ ラインで行われます)、大きなデータ セットを扱う場合に精度が向上します。

于 2012-09-28T13:27:24.213 に答える