深入淺出Mahout K-means (PART 3)- 系統化的產生k-means的中心點

k-means如何"決定k"的值一直是一個無解問題,是研究生口試前想辦法找理由回答委員的必問問題,到底k要取多少,基本上需要給予一些限制或是指標,來動態決定,然而這不是這篇說明的範圍內。

我們這邊要討論的是在Mahout的k-means框架下,要如何給予"k值"?過去在Weka裡面,我們直接設定k等於多少即可,而在Mahout裡面,k值設定的方法比較間接,需要從初始中心點有幾個,就代表k-means演算法的k值是多少,所以如何產生群聚的中心點就是一個很重要的議題。

如果你想隨機產生中心點,那可以借重Mahout in Action第九章的範例,這段code沒有列在課本裡,但有包含在課本的範例程式中,可以在這個網址找到code,基本上這段code非常的實用。

https://github.com/tdunning/MiA/blob/master/src/main/java/mia/clustering/ch09/RandomPointsUtil.java

在上面這段程式裡面,我們發現如果要產生4維的向量空間的中心點,他提供兩種方法,第一種static的方法是 public static void generateSamples(List<Vector> vectors, int num, double mx, double my, double sd),第二種static方法是 public static List<Vector> chooseRandomPoints(Iterable<Vector> vectors, int k)。

  • 第一種方法的概念是,給予一個空白的List<Vector> call back 物件,依照給予各個維度的期望值,以及變異數,產生num個隨機點,作為中心點,基本上,這些中心點與資料集裡面的點是不一樣的,是額外產生的。其中要留意,以IRIS資料集四個屬性而言,應該要把:

vectors.add(new DenseVector(new double[] {UncommonDistributions.rNorm(mx,       
      sd), UncommonDistributions.rNorm(my, sd) }));
改為:
vectors.add(new DenseVector(new double[] {
UncommonDistributions.rNorm(mx, 
sd),
UncommonDistributions.rNorm(my, sd),
              UncommonDistributions.rNorm(mz, sd),
              UncommonDistributions.rNorm(mw, sd)
        }));

使用方法:
List<Vector> vectors = new List<Vector>();
RandomPointsUtil.chooseRandomPoints(vectors,3,5,5,5,5,0.8)

這邊要說明一下何謂是UncommonDistributions.rNorm(mx, sd)?這在Mahout 0.5中的一個隨機值產生的方式,依照的是org.apache.mahout.clustering.dirichlet套件中的UncommonDistributions類別,在產生的時候,以這個例子,需要設定期望值與變異數,就可以隨間產生希望的值。

  • 第二種方法是在原本的資料集中,隨機選k個點作為中心點,基本上這種方式對於概念簡單得多,然而,此種問題在於若原先的資料分佈不夠均勻,會造成之後運算收斂較久的狀況。使用此種方法產生中心點非常容易,可參考下面的語法,裡面sampleData是List<Vector>(如何產生List<Vector>類型的sampleData,請見補充說明)

List<Vector> randomPoints = RandomPointsUtil.chooseRandomPoints(sampleData, k);

補充說明

假設給予矩陣double[][] data ={{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}},期望轉換為ArrayList<Vector>的result集合物件,因此可以參考下做法。

ArrayList<Vector> result = new ArrayList<Vector>();

for(double[] d:data){

     Vector v = new RandomAccessSparseVector(data.length);

v.assign(d);

result.add(v);

}

發表迴響

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

WordPress.com 標誌

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

Google+ photo

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

Twitter picture

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

Facebook照片

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

連結到 %s