Spark-KMeansクラスタリング分析

4601 ワード
アルゴリズム
目次
Sparkマシンラーニングライブラリの概要
K-meansクラスタリングアルゴリズムの原理
K-means実装
実行例
K値の選択
Sparkマシンラーニングライブラリの概要
MLlibはSparkのマシンラーニング(ML)ライブラリです.実用的な機械学習を拡張し、簡単にすることを目標としている.より高いレベルでは、次のツールが用意されています.
  • MLアルゴリズム:分類、回帰、クラスタリング、協同フィルタリングなどの一般的な学習アルゴリズム
  • 特徴化:特徴抽出、変換、降下および選択
  • 配管:ML配管を構築、評価、調整するためのツール
  • 持続性:アルゴリズムの保存とロード、モデルとパイプ
  • ユーティリティ:線形代数、統計、データ処理など
    • Sparkマシンラーニングライブラリを使用してマシンラーニングを行うことは,非常に簡単であり,通常は元のデータを処理した後,対応するAPIを直接呼び出すだけで実現できる.しかし、適切なアルゴリズムを選択し、データを効率的に正確に分析するには、アルゴリズムの原理と、対応するSpark MLlib APIが実現するパラメータの意味を深く理解する必要があります.
    K-meansクラスタリングアルゴリズムの原理
    クラスタリングとは、クラスタリングとは、データを異なるクラスまたはクラスタに分類するプロセスを指すため、同じクラスタ内のオブジェクトには大きな類似性があり、異なるクラスタ間のオブジェクトには大きな相異性があり、クラスタリングと分類の違いは、クラスタリングが区分を要求するクラスが未知であることである.
    クラスタリング分析は無監視学習(Unsupervised Learning)プロセスであり、一般的にデータオブジェクトをその特徴属性に従ってグループ化するために用いられ、顧客グループ化、詐欺検出、画像分析などの分野によく応用されている.K-meansは最も有名で最もよく使われるクラスタリングアルゴリズムであるべきで、その原理は比較的に理解しやすく、クラスタリング効果は良好で、広く使われている.
    多くの機械学習アルゴリズムと同様に、K-meansアルゴリズムも反復式のアルゴリズムであり、その主なステップは以下の通りである.
  • 最初のステップは、K個の点を初期クラスタリング中心として選択する.
  • の第2のステップでは、残りのすべての点からクラスタリング中心までの距離を計算し、各点を最も近いクラスタリング中心にあるクラスタリングに分割します.ここで、距離を測るには一般的に複数の関数が選択でき、最もよく使われるのはユークリッド距離(Euclidean Distance)であり、ユークリッド距離とも呼ばれる.
  • 第3のステップでは、各クラスタ内のすべての点の平均値を再計算し、新しいクラスタ中心点として使用します.
  • 第4のステップは、クラスタリング中心が変更されないまで、またはアルゴリズムが所定の反復回数に達するまで、またはクラスタリング中心の変化が予め設定されたバルブ値よりも小さくなるまで、(2)、(3)ステップのプロセスを繰り返す.

    • 実際の応用では,K‐meansアルゴリズムには直面し克服しなければならない2つの問題がある.
  • クラスタ個数Kの選択.Kの選択は比較的学問的で洗練されたステップであり,Sparkが提供するツールを用いてKを選択する方法を後述する.
  • 初期クラスタリング中心点の選択.異なるクラスタリングセンターを選択すると、クラスタリング結果の違いが生じる可能性があります.

    • Spark MLlib K-meansアルゴリズムの実装初期クラスタリング点の選択において,K-means‖というクラスK-means++実装を参考にした.K-means++アルゴリズムは初期点選択において基本原則に従う:初期クラスタリング中心点相互間の距離はできるだけ遠くなければならない.基本手順は次のとおりです.
  • 最初のステップは、データセットXから最初の初期点としてランダムに1つの点を選択する.
  • 第2のステップは、データセットのすべての点と最新に選択された中心点との距離D(x)を計算する.
  • の第3のステップでは、次の中心点を選択して最大にします.
  • 第4部は、K個の初期点選択が完了するまで(2)、(3)ステッププロセスを繰り返す.

    • K-means実装
    Spark MLlibにおけるK-meansアルゴリズムの実装クラス(KMeans.scala)は、以下のパラメータを有する.具体的には、class KMeans private(private var k:Int,private var maxIterations:Int,private var runs:Int,private var initializationMode:String,private var initializationStep s:Int,private var epsilon:Double,private var seed:Long)extends Serializable with Logging
  • kは、所望のクラスタの個数を表す.
  • maxInterationsは、メソッドが単一で実行される最大反復回数を表します.
  • runsは、アルゴリズムが実行された回数を表す.K-meansアルゴリズムは、グローバルで最適なクラスタリング結果を返すことを保証しないため、ターゲットデータセット上でK-meansアルゴリズムを複数回走ることで、最適なクラスタリング結果を返すのに役立ちます.
  • initializationModeは初期クラスタリング中心点の選択方式を表し、現在はランダム選択またはK-means‖方式をサポートしている.デフォルトはK-means|.
  • initializationStep sはK-means‖メソッドの部数を表します.
  • epsilonはK-meansアルゴリズム反復収束のバルブ値を表す.
  • seedはクラスタ初期化時のランダムシードを表す.

    • 実行例
    import org.apache.spark.mllib.clustering.KMeans
import org.apache.spark.mllib.linalg
import org.apache.spark.{SparkConf, SparkContext}
import org.apache.spark.mllib.linalg.Vectors
import org.apache.spark.rdd.RDD

object KmeansSpark {

  def main(args: Array[String]): Unit = {

    //     Spark
    val sparkConf = new SparkConf().setMaster("local[2]").setAppName("KmeansSpark")
    val sc = new SparkContext(sparkConf)

    //          RDD
    val data = sc.textFile("file:///root/test.txt")
    val parsedData: RDD[linalg.Vector] = data.map(s=>{
      val values: Array[Double] = s.split(" ").map(x => x.toDouble)
      Vectors.dense(values)
    })

    //      
    val numClusters = 8
    //      
    val numIterations = 20
    //      
    val runs = 10
    //KMeans  
    val kmeansModel = KMeans.train(parsedData, numClusters, numIterations, runs)

    //      ID
    kmeansModel.clusterCenters.foreach(x=>{
     println(x)
    })
    //            ID
    parsedData.map(v => v.toString + " belong to cluster: " +kmeansModel.predict(v))
    ss.foreach(x=>
      println(x)
    )
    sc.stop()
  
  }
}

    K値の選択
    前述したKの選択はK-meansアルゴリズムの鍵であり,Spark MLlibはKMeansModelクラスにcomputeCost法を提供し,この方法はすべてのデータ点からその最近の中心点への二乗和を計算することによってクラスタリングの効果を評価する.一般に,同じ反復回数とアルゴリズムが走る回数は,この値が小さいほどクラスタリングの効果を表す.しかし,実際にはクラスタリング結果の解釈性も考慮し,computeCost結果値を最小にするKをひたすら選択することはできない.
    val ks:Array[Int] = Array(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
ks.foreach(cluster => {
 val model:KMeansModel = KMeans.train(parsedData, cluster,30,1)
 val ssd = model.computeCost(parsedData)
 println("sum of squared distances of points to their nearest center when k=" + cluster + " -> "+ ssd)
})

     
    並列調査セット(等価クラス)ADT学習分析
    ネクタイネットワークアルゴリズム学習ノート-88