深入淺出Mahout K-means (PART 5) 如何決定群聚的數量 Conopy

決定群聚數量其實是一個不太容易的事情,往往需透過經驗或是對於資料預先的瞭解。不只是如何找群聚的數量,通常在分析一堆網誌資料的時候,對於不同類型、來源、作者的資料,我們都無法輕易預先瞭解在裡面到底有哪些群,例如:我們到mobile01的攝影方面的版,這裡面就至少有三種主題,包含為開箱文、攝影技巧文與比較文,但是到別的論壇可能就有其他不同的主題,如何在大量的資料中找出群聚的數量,是一個很挑戰的事情。

這件事情在資料探勘領域也有許多討論,在2000年的時候,不約而同在ICML與KDD有兩篇論文都提出如何自動給予K值的演算法,在ICML2000中,當時在卡內基梅隆大學的Andrew Moore與Dan Pelleg提出了一篇叫做X-Means[1],大家很容易可以透過google找到這篇論文,我對這個方法的本質不太瞭解,但過去有很多實驗室的學弟妹都尋求這個方法的協助,因為這個方法在Weka裡面有實作,而且,他不用給K值,每次他們報告的時候都會被大家詢問K值怎麼取,索性就用一個不用給K值的群聚演算法,但關鍵在於,不是不給K值,而是間接給了其他限制,讓演算法在取群聚數的時候能夠有一個參考。

在2000年的KDD,Andrew McCallum、Kamal Nigam與Lyle H. Ungar提出了Canopy cluster algorithm[2],我想McCallum的有名程度就不多提,現在是MIT的教授,Nigam的著作,我過去拿著他的co-training文章念了好久,老實說Canopy cluster algorithm是這幾天有機會坐捷運,在捷運上好好的瞭解他,為什麼會對他有興趣?因為,Mahout有實作Canopy cluster algorithm。透過翻譯,了解Canopy是罩棚的意思,在一堆資料裡面,你可以拿著一些罩棚去涵蓋這些資料,若重疊性太高,就把這兩個罩棚合併成一個更大的罩棚,最後罩棚的數量就是前在群聚的數量,透過這樣的方法決定群聚的數量,今天這篇文章會針對這個Canopy Cluster在Mahout上的應用做一些說明。

(過去Christos Faloutsos建議我透過Singular Value Decomposition所分解出的對角矩陣,透過n%的 Energy Spectrum的涵蓋程度決定涵蓋n%的eigen value的數量,剛剛Kobe也提醒了我當初Prof. Pao建議我們去評估Intra與Inter群聚的差來決定群數,這不在此次探討範圍囉,只是要說明,如何決定群數的方法實在是太多太多了。)

Canopy有兩個參數需要決定,分別是t1與t2距離,t1會小於t2,這個演算法會從每個點透過MapReduce的Map開始從每個點開始當中心點開始運算在其t1與t2範圍內包含的群,t1是一個比較小的棚子,t2是一個比較大的棚子。在t1棚子裡的點是不會被搶走的,然而在t2棚子中的點是會被別的棚子搶走,經過這樣不斷的運算過程,最終透過Reduce運算,聚出結果。

如果你打算用Canopy來產生群聚結果,那可能不是一個好主意,因為他為了很有效率找到群數,其實在距離運算上做了很多經濟的考量,他試著用最簡單的距離運算公式快速的找出Canopy。然而,如果你把它當做一個判斷群數k的功能,那就非常好用了!

概念講完,開始看怎麼用了!

Canopy Cluster與K-means Cluster一樣分為In-Memory與MapReduce版本,In-Memory版本的叫做CanopyClusterer,用法如下:

List<Canopy> canopies = CanopyClusterer.createCanopies(sampleData,

new EuclideanDistanceMeasure(), 3.0, 1.5);

這裡面的sampleData只要是符合List<Vector>即可(強調,這邊的Vector是Mahout的Vecotr)。

另外一個版本是MapReduce版本-CanonpyDriver

CanopyDriver.run(new Configuration(), data, output, new EuclideanDistanceMeasure(), 10, 15, true, false);

其中data是放在HDFS裡已經序列化後的資料,在CanonpyDriver的實作中,input的序列資料需要符合(WritableComparable<?>, VectorWritable),要符合WritableComparable其實不難,例如在之前的Part2所用的LongWritable就有實作WritableComparable,因此只要延續之前產生放入K-means的資料先放入Canonpy。輸出的ouput為群聚結果,並且可從裡面抓取中心點直接放入K-means演算法中:

KMeansDriver.run(conf, vectorsFolder, new Path(output, “clusters-0″), clusterOutput, new TanimotoDistanceMeasure(), 0.01, 20, true, false);

所以整體而言,我們就輕易透過Mahout實作的Canopy Cluster幫忙K-means預先找到中心點以及群數,進行後續的群聚分析了

參考資料(第三篇網頁寫的很不錯喔)

[1] Dan Pelleg, Andrew W. Moore: X-means: Extending K-means with Efficient Estimation of the Number of Clusters. In: Seventeenth International Conference on Machine Learning, 727-734, 2000.

[2] McCallum, A.; Nigam, K.; and Ungar L.H. (2000) “Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching", Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 169-178


發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s