マイノート

いろいろ勉強したことをまとめていきます

MENU

k-means

k-means概要

k-meansとは教師なし非階層クラスタリング手法の一つである。

下記の最適化問題を解くアルゴリズム

\begin{equation} * argmin_{C_1 ,\centerdot \centerdot \centerdot, C_k} \sum_{i=1}^{n} argmin_{j} ||v_i - C_j||^2 \end{equation}

$C_i$はクラスタ、 $v_j$はデータ

* は初期値に依存するからかな?

図で表したほうがわかりやすい。

まず、分類したいデータがある。

f:id:ttt242242:20170417084017j:plain:w200

この各点の座標情報からK_meansを使って分類すると、以下の図のようになる。ここではK=3とする。

f:id:ttt242242:20170417084020j:plain:w200

アルゴリズム

1. 適当にクラスタを割り振る

2. クラスタの中心 $C_i$ を計算する

  基本的には算術平均で求める。

\begin{equation} C_i = (\frac{v_{x1} + v_{x2} \centerdot \centerdot \centerdot v_{xn}}{n}, \frac{v_{y1} + v_{y2} \centerdot \centerdot \centerdot v_{yn}}{n}) \end{equation}

3. 各 $v_j$ と 各$C_i$ との距離を再計算し、 $v_j$ を一番近いクラスタに割り当てる

4. 1、2、3を $c_j$が属するクラスタの変化がなくなる、もしくは各 $c_j$ と $V_i$ との距離の変化がなくなるまで繰り返す。

プログラム

githubにあげた。 GitHub - Tcom242242/K_Means

今回は2次元のデータを200個作成し、分類した。

#!/usr/bin/ruby
# -*- encoding: utf-8 -*-

$LOAD_PATH.push(File::dirname($0)) ;
require "pry"
require "yaml"

#
# == k_means 
#
class K_Means

  attr_accessor :datas, :k, :c_list
  def initialize(datas: [[2, 3],[2, 8],[2, 3],[3, 5],[6, 3],[5, 3]], k: 2, dim: 2)
    @datas = datas
    sliced_datas = @datas.each_slice(k).to_a
    @k = k 
    @cluster_list = @k.times.map {|n| Cluster.new(n, nil,sliced_datas[n] , dim)}
    @dim = dim 
  end
  
  
  def fit()
    loop {
      @cluster_list.each{|c| c.reset_v_list()}
      @datas.each {|d|
        min_dist = 100000
        min_cluster_id = -1
        @cluster_list.each {|c|
          dist = calc_dist(d, c)
          if dist < min_dist 
            min_cluster_id = c.id 
            min_dist = dist
          end
        }
        @cluster_list[min_cluster_id].add_v(d)
      }

      @cluster_list.each{|c| c.calc_center()}
      break if !change_clusters_center?
    }

    formated_cluster_list = format_for_log()

    open("result.yaml", 'w') do |io|
      YAML.dump(formated_cluster_list, io)
    end
  end

  def format_for_log()
    result = @cluster_list.map {|c| c.format_hash()}
  end

  def calc_dist(v, cluster)
    dist_sum = 0.0
    v.each_with_index { |v_x, i|
      dist_sum += (cluster.vec[i] - v_x).abs
    } 
    return dist_sum/v.size
  end
 
  def change_clusters_center?()
    @cluster_list.each {|c|
      return true if(c.change_center?) 
    } 
    return false
  end 

  #
  # cluster 
  # cluster has id, vec, and v_list
  #
  class Cluster
    attr_accessor :id, :vec, :v_list, :last_vec

    def initialize(id, vec=nil, v_list=nil, dim=1)
      @id = id
      @v_list= v_list
      @vec = dim.times.map{0.0} if vec == nil
      @dim = dim
      calc_center()
    end

    def calc_center() 
      @last_vec = Marshal.load(Marshal.dump(@vec))
      vec_sum = Array.new
      @v_list.each { |v|
        v.each_with_index { |v_x, i| 
          vec_sum[i] ||= 0.0
          vec_sum[i] += v_x 
        } 
      }
      vec_sum.each_with_index { |new_vec, i| @vec[i] = new_vec/@v_list.size.to_f } 
    end 

    def add_v(v)
      @v_list.push(v)
    end

    def reset_v_list()
      @v_list = []
    end

    def change_center?
      @dim.times { |i|
        return true if @vec[i] != @last_vec[i]
      }
      return false
    end

    def format_hash()
      cluster_hash = {}
      cluster_hash[:id] = @id
      cluster_hash[:vec] = @vec
      cluster_hash[:v_list] = @v_list
      return cluster_hash
    end
  end
end

#
# for experiment
#
if($0 == __FILE__) then
  dim, data_num = 2, 200
  datas = data_num.times.map { |t|
    data = dim.times.map { rand()*10 }
  }
  # datas=[[10, 4],[2, 8],[7, 3],[3, 5],[6, 3],[5, 3],[2, 4],[2, 3], [1, 4], [1, 3], [6, 6], [10, 1],[1, 1], [8, 1], [1, 6], [10, 6]]
  # datas=[[2, 3],[2, 8],[2, 3],[3, 5],[6, 3],[5, 3]]
  k_means = K_Means.new(datas: datas, k: 3, dim: dim) 
  puts "calculating..."
  k_means.fit() 
  puts "finish"
end

結果をプロットしてみると、

f:id:ttt242242:20170417085521p:plain:w300

参考

k平均法 - Wikipedia

ITエンジニアのための機械学習理論入門

ITエンジニアのための機械学習理論入門