作者RockLee (Now of all times)
看板Prob_Solve
標題[問題] Canopy-Clustering using Map-Reduce
時間Thu Sep 20 14:44:31 2012
小弟最近剛開始看一些 Map-Reduce 相關的東西.
在 Google 的 Cluster Computing and MapReduce 的 Lecture 4 中提到的應用是,
將 Canopy-Clustering 用 Map-Reduce 來做分散運算.
不過 Lecture 4 講得很簡略, 後來找到 K-Means Clustering in Map Reduce 這個網頁,
有 Canopy-Clustering using Map-Reduce 演算法的 pseudo-code.
不過小弟對該網頁的 pseudo-code 有兩點疑問:
(1) Reduce Part of Round 1 檢查為何是 if dist(canopy, finalCanopy) < 0.5 * T2?
這樣似乎違反一個 canopy center 範圍 T2 內不會再有另一個 canopy center 的描述.
是否應像小弟改的那樣, 改為 if dist(canopy, finalCanopy) < T2,
然後距離過近的話, 繼續檢查 listOfCanopies 的下一個.
(2) 要做分散運算的話, 是否應該滿足 T1 > 2 * T2 的條件,
才能保證任何一個 data point,
至少被一個 Round 1 找出來的 canopy center 範圍 T1 包含?
相關連結:
(1) Google: Cluster Computing and MapReduce
http://code.google.com/intl/en/edu/submissions/mapreduce-minilecture/listing.html
(2) K-Means Clustering in Map Reduce
http://horicky.blogspot.tw/2011/04/k-means-clustering-in-map-reduce.html
(3) Canopy-Clustering Paper
http://www.kamalnigam.com/papers/canopy-kdd00.pdf
Paper 中對 Canopy Creation 的描述:
Start with a list of the data points in any order,
and with two distance thresholds, T1 and T2, where T1 > T2.
Pick a point off the list and approximately measure its distance to all other
points.
Put all points that are within distance threshold T1 into a canopy.
Remove from the list all points that are within distance threshold T2.
Repeat until the list is empty.
/* Reduce Part of Round 1: Identify Canopies, modified by me */
finalCanopyList = {}
reduce(key, listOfCanopies)
{
scanCanopy:
for canopy in listOfCanopies
{
for finalCanopy in finalCanopyList
{
if dist(canopy, finalCanopy) < T2
{
continue scanCanopy
}
}
finalCanopyList.add(canopy)
}
writeToS3(finalCanopyList)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.30.95
※ 編輯: RockLee 來自: 59.126.30.95 (09/20 14:49)