class Mapper
method Map(nid n, node N)
p ← N.PageRank/|N.AdjacencyList|
Emit(nid n, N )
for all nodeid m ∈ N.AdjacencyList do
Emit(nid m, p)
class Reducer
method Reduce(nid m, [p1, p2, . . .])
M←∅
for all p ∈ counts [p1,p2,...] do
if IsNode(p) then
M ← p
else
s ← s + p
M.PageRank ← s
Emit(nid m, node M )
node のなかに AdjacencyList が含まれているが、これが疎行列のコラム方向の情報に相当する。
CPSYで提案したReduceのみでMatMulを行うアルゴリズムは、ベクトルがメモリに乗ることを前提としている。
ベクトルとカラムは同じ長さだが、ベクトルは密なのでこちらのほうが強い制約となる。
PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations
で示されている、naiveな方法では行列ベクトル積はMR2回が必要となるが、サイズの制約はない。かと思ったけど、やっぱり1段めのMRのReduceのところで、一度コラム方向を全部オンメモリに持っているから条件は変わらない。データの持ち方の違いだけか?
map-reduce-mergeのmergeがあれば、merge + reduce で非常に素直に書けそう。
2012年5月25日金曜日
Hadoop で行列ベクトル積
PageRankは本質的に疎行列ベクトル積になる。Jimmy Lin のData-Intensive Text Processingに乗っているアルゴリズムは、Mapの入力として、Nodeを用いている。Nodeは他のノードへのリンクを保持している。
行列的に捉えれば、行列のカラムに相当する。つまり、このアルゴリズムは、カラムの非ゼロ要素数が十分小さく、メモリに乗るという前提で考えられている。Page Rankというアプリケーションの特性を考えれば妥当である。
2011年12月30日金曜日
The φ Accrual Failure Detector
The φ Accrual Failure Detector Naohiro Hayashibara, Xavier Défago, Rami Yared1, and Takuya KatayamaPDF。 Cassandraで使われている事で知られる故障検出手法。 古典的にはハートビートを用いた検出手法が知られているが、1か0を返すだけで使いにくい。 これに対してφ Accrual では、やはりハートビートを使うのだが、ノードの状態を0以上の 故障可能性値φで返す。ポイントは、0,1でないため、使う側が故障しているかどうかの 判断を調整できること。 まず、ハートビートの受信間隔の平均と分散を算出しておく。 この二つの値を使って、前回ハートビートを受信してから経過した時間に応じて、 今後ハートビートが来る確率を算出し、そのLog10をφとする(?)。 ハートビートを受信するとファイは0にリセットされる。
2011年7月14日木曜日
Efficient Clustering of High-Dimensional Data Sets with Application to Reference Matching
大規模なデータのクラスタリングの手法としてCanopy法というものを提唱。
仮定として、距離を計算する方法に軽い方法と重い方法があることを想定。
軽い方法でキャノピーを作り、そのなかで重い方法を使う。
キャノピーを作る際はN^2のオーダの計算が必要だが、軽いからOKだという理屈。
キャノピーを作る方法は簡単、
1. 1点を選びそこから半径T1内のものはひとつのキャノピーの中と見なす。
さらにT2< T1内の点は、以降の選択から取り除く
32 これを点が亡くなるまで行う。
後段にはk-meansなどを使うことを想定している。
今考えているアプリケーションは距離行列は所与なので使いようがない。。
仮定として、距離を計算する方法に軽い方法と重い方法があることを想定。
軽い方法でキャノピーを作り、そのなかで重い方法を使う。
キャノピーを作る際はN^2のオーダの計算が必要だが、軽いからOKだという理屈。
キャノピーを作る方法は簡単、
1. 1点を選びそこから半径T1内のものはひとつのキャノピーの中と見なす。
さらにT2< T1内の点は、以降の選択から取り除く
32 これを点が亡くなるまで行う。
後段にはk-meansなどを使うことを想定している。
今考えているアプリケーションは距離行列は所与なので使いようがない。。
Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space
Yaniv Loewenstein1,∗, Elon Portugaly1, Menachem Fromer1 and Michal Linial2,
蛋白を階層クラスタリング。
ポイントは距離がすべての蛋白の間に定義されるわけではないこと。
また、三角形の1辺は2辺の和より短い、という法則が成り立たないこと。
この前提ではcentroidが定義できない。kmeansのような方法も使えなさそう。。。
メモリに乗る範囲で何とかやる方法を提案している。
距離でソートして、短いほうからメモリに乗る範囲で載せて、上限と下限でしばりながら
クラスタリングを行う。これをなんどか繰り返す。
並列化は非常に難しそう。簡単に出来る方法は思いつかない。
2011年7月5日火曜日
An Efficient Hierarchical Clustering Method for Large Datasets with Map-Reduce
Tianyang Sun, Chengchun Shu, Feng Li, Haiyan Yu, and Lili Ma, Yitong Fang
1.2T 1million user 6時間
テキストの分類。前処理とクラスタリングにそれぞれMRを使用。
クラスタリングは3回のMRで。
なんか肝心な部分をmasterノードでon memoryでやっている。
あと、ある程度近いものを有無を言わさずペアにしているようだが、厳密には
これではまずいはず。
A New Agglomerative Hierarchical Clustering Algorithm Implementation based on the Map Reduce Framework
Hui Gao, Jun Jiang, Li She, Yan Fu 中国 uestc.
文書の分類。neuron initialization とか言ってるな。。分割してクラスタリングしたものを
後でアグリゲートしている?ただしその方法については書いてない。
2011年7月4日月曜日
Divisive hierarchical clustering
というのは、上流からどんどん分割していく方法。具体的にはKMeansをつかって2分割し、分割されたモノにまたKMeansを適用して、というようにやるようだ。
KMeans がm段で収束するとして、分割の深さを log2Nとすると m * log2N段のMRをやることになる。
実装的には複数のKMeans を同時にやる用にしないといけなさそうで、割に大変っぽい。まあやればできそうだが。問題はこのようにして求めた階層クラスタが要件にあうのかどうかだ。
登録:
投稿 (Atom)