K-平均法

データを分類する為のアルゴリズム。

データの分類にはデンドログラムというアルゴリズムが有名。

デンドログラムとは

何らかの評価関数で、全ての要素間の類似度を計算する。
最も類似していると判定される二つをまとめて、平均値を持った１要素とする
「全要素 - 2の処理でまとめられた2要素 + 2の処理で作られた平均値要素」のデータ集合で１からやり直す
１要素になるまで続けたら完成

こうしてできた2分木のツリーをデンドログラムといい、性質のグループを抽出できる。

そのツリーのノードを見て、ノードに「これは○○の分類か…」とか意味を持たせるのは人の仕事だ。

これは事前にデータグループの数が予測できない場合に有効な処理だと言える。

デンドログラムの最大の欠点は、計算回数が多すぎるという話だ。

何しろ !N * N の計算回数がかかるのだから、冗談ではない。

で、本題の K 平均法だが、これは事前に含まれるグループ数が予測できる場合、もしくは K 個の種類に分類したい場合に、最悪ケースでも N² 位の計算数で分類できる。

手順が下記の通り。

適当な値を持った K 個のクラスタ with 代表データ(初回はランダム)を用意する
実データセットを、K 個の代表データのうち、最も類似性の高かったクラスタに振り分ける
K 個のクラスタ内で、データの平均を取り、それを代表データとしてセットし直す
上記 2-3 をデータセットの変化が無くなるまで繰り返す

たまに空っぽになるクラスタも出るが、そいつはどうすれば良いか解らんからとりあえず保留で良いかもしれない。

そうすると最終的に K 個のデータセットに分類される…と。

以前やったランダムフォレストを実装する - 謎言語使いの徒然の iris.dat を分類するプログラムを、昨日のわんくま勉強会中に書いてみた。

package iris

import scala.util.Random
import scala.io.Source

case class Line(id: Long, field: List[Double], result: String)

object Resource {

  /**
   * ファイルを開く
   * @return
   */
  def read() = {
    val resource = this.getClass.getResource("../iris.dat")
    val file = Source.fromFile(resource.getPath, "utf-8")

    file.getLines().filterNot(_.isEmpty).map(s => {
      val splits = s.split("\t")
      Line(
        splits(0).toInt,
        List(
          splits(1).toDouble,
          splits(2).toDouble,
          splits(3).toDouble,
          splits(4).toDouble
        ),
        splits(5)
      )
    }).toList
  }
}

object KMeans {

  /**
   * 初期条件としてランダム３つのクラスタを作り、適当にデータを割り振る
   * @param lines
   * @return
   */
  def randomCluster(lines: List[Line]) = {
    val field1Max = lines.map(_.field(0)).max
    val field2Max = lines.map(_.field(1)).max
    val field3Max = lines.map(_.field(2)).max
    val field4Max = lines.map(_.field(3)).max

    def randomList() = List(
      Random.nextDouble() * field1Max,
      Random.nextDouble() * field2Max,
      Random.nextDouble() * field3Max,
      Random.nextDouble() * field4Max
    )

    // 適当に三等分
    val splitSize = lines.size / 3

    (0 to 2).map(i => {
      val from  = i * splitSize
      val until = (i + 1) * splitSize
      Cluster(randomList, lines.slice(from, until))
    })
  }
}

case class Cluster(field: List[Double], var irises: List[Line]) {
  
  val currentSum:   Double = field.sum
  val currentSqSum: Double = field.map(Math.pow(_, 2.0)).sum

  /**
   * このクラスタの中身を表示する
   */
  def dispCluster() {
    val result = irises.groupBy(_.result).map(v => v._1 -> v._2.size).toSeq.sortBy(_._2)
    println(s"Cluster result  : ${result.last._1}")
    println(s"Cluster fields  : $field")
    println(s"Cluster summary : $result")
  }

  /**
   * 対象とのピアソン相関を計算する
   * @param right
   * @return
   */
  def piasson(right: List[Double]) = {
    // 全ての値を合計
    val rightSum = right.sum

    // 平方和
    val rightSqSum = right.map(Math.pow(_, 2.0)).sum

    // 積
    val pSum = (0 to 3).map(i => field(i) * right(i)).sum

    // 統計量の計算
    val n   = 4.0
    def num = pSum.toDouble - (currentSum * rightSum / n)
    def den = Math.sqrt((currentSqSum - Math.pow(currentSum, 2) / n) * (rightSqSum - Math.pow(rightSum, 2) / n))

    if (den == 0.0) {
      0.0
    } else {
      num / den
    }
  }

  /**
   * 要素追加しますねん
   * @param line
   */
  def append(line: Line) {
    irises = irises :+ line
  }

  /**
   * ID セットを返す
   * @return
   */
  def ids(): List[Long] = irises.map(_.id).sorted

  /**
   * 平均を計算して次の空クラスタを作る
   */
  def mean() = {
    def average(datas: List[Double]): Double = datas.sum / datas.size
    Cluster(
      List(
        average(irises.map(_.field(0))),
        average(irises.map(_.field(1))),
        average(irises.map(_.field(2))),
        average(irises.map(_.field(3)))
      ),
      List.empty
    )
  }
}

/**
 * K平均法でデータクラスタを求める。
 * クラスタを見て、分類するのは人間の仕事。
 * Created by azalea on 2014/07/26.
 */
object KMeansIris extends App {

  // データソース
  val all = Resource.read()

  // K 平均法に基づいて、初期クラスタを割り振る
  def shuffled = Random.shuffle(all) // データが既にソートされてたら意味がないので…
  var clusters: List[Cluster] = KMeans.randomCluster(shuffled).toList

  // 終了条件で利用する変数
  var loopCount = 0
  var idSets: List[List[Long]] = _
  var newIds: List[List[Long]] = _

  do {
    loopCount += 1
    println(s"Loop : $loopCount")

    // まずは ID のセットを取得しておく(後で比較する)
    idSets = clusters.map(_.ids())

    // Clister の平均をとって、新しいクラスタを作る
    clusters = clusters.map(_.mean())

    // データソースを newCluster に割り振る
    all.foreach(v => {
      // 相関を求めて
      val piassons = clusters.map(_.piasson(v.field)).zipWithIndex.sortBy(_._1)

      // 最も相関の高いクラスタに追加する
      val last = piassons.last

      // 最も相関の高いものに所属させる
      clusters(last._2).append(v)
    })

    // 新しいIDセットを取得して
    newIds = clusters.map(_.ids())

    // IDセットが変化する間はループする
  } while(idSets != newIds)

  println("Learn exit")

  clusters.foreach(_.dispCluster())
}

で、へなっと実行してみると

[info] Running iris.KMeansIris 
Loop : 1
Loop : 2
Loop : 3
Loop : 4
Loop : 5
Loop : 6
Loop : 7
Learn exit
Cluster result  : setosa
Cluster fields  : List(5.005999999999999, 3.428000000000001, 1.4620000000000002, 0.2459999999999999)
Cluster summary : ArrayBuffer((setosa,50))
Cluster result  : versicolor
Cluster fields  : List(5.953999999999999, 2.8080000000000003, 4.27, 1.3559999999999999)
Cluster summary : ArrayBuffer((virginica,3), (versicolor,47))
Cluster result  : virginica
Cluster fields  : List(6.569999999999998, 2.9359999999999995, 5.541999999999999, 1.996)
Cluster summary : ArrayBuffer((versicolor,3), (virginica,47))

うん、若干の誤差はあれど、いい感じに分類出来てるね。

比較アルゴリズムが、ピアソン相関比較(植物の種類で、葉や茎の大きさは同じ比率であると想定)で作ってみたが、もしかしたらユークリッド距離(単純に各値が似ているかどうか)比較の方が今回はいい結果が出るのかもしれない。