孫其功陪你學之——Spark MLlib之K-Means聚類算法

轉自 程式員的自我修養 – SelfUp.cn

由于在學習 spark mllib 但是如此詳細的資料真的很難找，在此分享。

聚類算法

聚類，Cluster analysis，有時也被翻譯為簇類，其核心任務是：将一組目标object劃分為若幹個簇，每個簇之間的object盡可能的相似，簇與簇之間的object盡可能的相異。聚類算法是機器學習（或者說是資料挖掘更合适）中重要的一部分，除了最為簡單的K-Means聚類算法外，較常見的還有：層次法（CURE、CHAMELEON等）、網格算法（STING、WaveCluster等）等等。

較權威的聚類問題定義：所謂聚類問題，就是給定一個元素集合D，其中每個元素具有n個可觀察屬性，使用某種算法将D劃分成k個子集，要求每個子集内部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高。其中每個子集叫做一個簇。

與分類不同，分類是示例式學習，要求分類前明确各個類别，并斷言每個元素映射到一個類别，而聚類是觀察式學習，在聚類前可以不知道類别甚至不給定類别數量，是無監督學習的一種。目前聚類廣泛應用于統計學、生物學、資料庫技術和市場營銷等領域，相應的算法也非常的多。

K-Means

K-Means屬于基于平方誤差的疊代重配置設定聚類算法，其核心思想十分簡單：

1. 随機選擇K個中心點
2. 計算所有點到這K個中心點的距離，選擇距離最近的中心點為其所在的簇
3. 簡單的采用算術平均數（mean）來重新計算K個簇的中心
4. 重複步驟2和3,直至簇類不在發生變化或者達到最大疊代值
5. 輸出結果

K-Means算法的結果好壞依賴于對初始聚類中心的選擇，容易陷入局部最優解，對K值的選擇沒有準則可依循，對異常資料較為敏感，隻能處理數值屬性的資料，聚類結構可能不平衡。

這裡有一個K-Means的示範，需要安裝Java Applet。

Spark實作K-Means算法

測試資料

1 2 3 4 5 6 7 8 9

0.0 0.0 0.0 0.1 0.1 0.1 0.2 0.2 0.2 9.0 9.0 9.0 9.1 9.1 9.1 9.2 9.2 9.2 15.1 16.1 17.0 18.0 17.0 19.0 20.0 21.0 22.0

如前文所述，測試資料不用帶标簽，資料分為3個次元。

代碼示例

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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

private static final Pattern SPACE = Pattern . compile ( " " ) ;   public static void main ( String [ ] args ) {      SparkConf sparkConf = new SparkConf ( )            . setAppName ( "K-Means" )            . setMaster ( "local[2]" ) ;      JavaSparkContext sc = new JavaSparkContext ( sparkConf ) ;      JavaRDD < String > data = sc . textFile ( "/home/yurnom/data/kmeans_data.txt" ) ;      JavaRDD < Vector > parsedData = data . map ( s -> {          double [ ] values = Arrays . asList ( SPACE . split ( s ) )                . stream ( )                . mapToDouble ( Double :: parseDouble )                . toArray ( ) ;          return Vectors . dense ( values ) ;      } ) ;        int numClusters = 3 ; //預測分為3個簇類      int numIterations = 20 ; //疊代20次      int runs = 10 ; //運作10次，選出最優解      KMeansModel clusters = KMeans . train ( parsedData . rdd ( ) , numClusters , numIterations , runs ) ;        //計算測試資料分别屬于那個簇類      print ( parsedData . map ( v -> v . toString ( )            + " belong to cluster :" + clusters . predict ( v ) ) . collect ( ) ) ;      //計算cost      double wssse = clusters . computeCost ( parsedData . rdd ( ) ) ;      System . out . println ( "Within Set Sum of Squared Errors = " + wssse ) ;        //列印出中心點      System . out . println ( "Cluster centers:" ) ;      for ( Vector center : clusters . clusterCenters ( ) ) {          System . out . println ( " " + center ) ;      }      //進行一些預測      System . out . println ( "Prediction of (1.1, 2.1, 3.1): "            + clusters . predict ( Vectors . dense ( new double [ ] { 1.1 , 2.1 , 3.1 } ) ) ) ;      System . out . println ( "Prediction of (10.1, 9.1, 11.1): "            + clusters . predict ( Vectors . dense ( new double [ ] { 10.1 , 9.1 , 11.1 } ) ) ) ;      System . out . println ( "Prediction of (21.1, 17.1, 16.1): "            + clusters . predict ( Vectors . dense ( new double [ ] { 21.1 , 17.1 , 16.1 } ) ) ) ; }   public static < T > void print ( Collection < T > c ) {      for ( T t : c ) {          System . out . println ( t . toString ( ) ) ;      } }

結果

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

[ 0.0 , 0.0 , 0.0 ] belong to cluster : 0 [ 0.1 , 0.1 , 0.1 ] belong to cluster : 0 [ 0.2 , 0.2 , 0.2 ] belong to cluster : 0 [ 9.0 , 9.0 , 9.0 ] belong to cluster : 1 [ 9.1 , 9.1 , 9.1 ] belong to cluster : 1 [ 9.2 , 9.2 , 9.2 ] belong to cluster : 1 [ 15.1 , 16.1 , 17.0 ] belong to cluster : 2 [ 18.0 , 17.0 , 19.0 ] belong to cluster : 2 [ 20.0 , 21.0 , 22.0 ] belong to cluster : 2   Within Set Sum of Squared Errors = 38.533333333333815 Cluster centers : [ 0.10000000000000002 , 0.10000000000000002 , 0.10000000000000002 ] [ 9.1 , 9.1 , 9.1 ] [ 17.7 , 18.033333333333335 , 19.333333333333332 ] Prediction of ( 1.1 , 2.1 , 3.1 ) : 0 Prediction of ( 10.1 , 9.1 , 11.1 ) : 1 Prediction of ( 21.1 , 17.1 , 16.1 ) : 2

人為捏造的測試資料所想表現出來的簇類完全被k-means算法體會到了，若是人工将測試資料分成3個簇類，結果也會與上面一樣。

最後

K-Means屬于無監督學習，最大的特别和優勢在于模型的建立不需要訓練資料。在日常工作中，很多情況下沒有辦法事先擷取到有效的訓練資料，這時采用K-Means是一個不錯的選擇。但K-Means需要預先設定有多少個簇類（K值），這對于像計算某省份全部電信使用者的交往圈這樣的場景就完全的沒辦法用K-Means進行。對于可以确定K值不會太大但不明确精确的K值的場景，可以進行疊代運算，然後找出cost最小時所對應的K值，這個值往往能較好的描述有多少個簇類。

參考資料

• MLlib - Clustering
• k-means clustering
• K-means聚類算法
• 算法雜貨鋪——k均值聚類(K-means)