Rubyで学習ベクトル量子化

今回はRubyで学習ベクトル量子化をやってみます。
ようやくなんちゃってボロノイ図を使うときがきました…。

ソースコード

今回主な処理をしているのはこのクラスですが、その他図を出力するためのコードなどは
https://gist.github.com/seinosuke/8cd29c69ffd2815a72b7
にあるのでよかったら参考までに。

class LVQ
  attr_accessor :log
  ALPHA = 0.005

  def initialize(learning_patterns, dimension)
    @log = []
    @dimension = dimension
    @class_num = learning_patterns.size
    @learning_patterns = learning_patterns.map do |patterns|
      patterns.map { |pattern| Vector[*pattern.map(&:to_f)] }
    end

    # 各クラスの平均ベクトル
    m = @learning_patterns.map do |patterns|
      patterns.each.inject(Vector[*Array.new(@dimension) { 0.0 }], :+)
      .map { |v| v / patterns.size.to_f }
    end

    # 各クラスの平均ベクトル付近を代表パターンの初期値に
    @representative_patterns = @class_num.times.map do |i|
      Array.new(4) do
        m[i] + Vector[ *@dimension.times.map { rand } ]
      end
    end
  end

  def learn
    50.times do
      correct_errors
    end
  end

  # 代表パターンを修正していく
  def correct_errors
    @learning_patterns.each_with_index do |patterns, i|
      patterns.each do |pattern|
        r_i, r_j = nearest_neighbor(pattern)
        if i == r_i
          @representative_patterns[r_i][r_j] +=
            ALPHA * (pattern - @representative_patterns[r_i][r_j])
        else
          @representative_patterns[r_i][r_j] -=
            ALPHA * (pattern - @representative_patterns[r_i][r_j])
        end
      end
      @log << Marshal.load(Marshal.dump(@representative_patterns))
    end
  end

  # 最近傍の代表パターンは何クラスの何番目のものかを返す
  def nearest_neighbor(l_pattern)
    @representative_patterns.map.with_index do |patterns, i|
      patterns.map.with_index do |r_pattern, j|
        distance = @dimension.times.inject(0) do |sum, k|
          sum + (r_pattern[k] - l_pattern[k])**2
        end
        { :at => [i, j], :distance => distance }
      end
    end.flatten.min_by { |h| h[:distance] }[:at]
  end
end

処理の流れ

学習パターンはラベル付けされていてどのパターンがどのクラスに属しているかわかっている状態です。そこから各クラスの複数の代表ベクトルを求めていきます。代表ベクトルの初期値は適当に設定するとなかなかうまくいかないので、各クラスの平均ベクトル付近を初期値としました。

ある学習パターンxの最近傍の代表ベクトルmがクラスiに属しているとき、

• m' = m + α*(x - m) ← （xもクラスiに属する場合）
• m' = m - α*(x - m) ← （xがクラスiに属さない場合）

という処理を全ての学習パターンに対して繰り返し行い、代表ベクトルを更新していきます。

これにより、xが同じクラスであった場合は同じクラスの代表ベクトルが近づいてきてきて、異なる場合は遠ざかるので代表ベクトルが修正されていきます。

実行結果

図1のような3クラス（色別になってる）の学習パターンに対して処理をします。露骨に線形分離不可能な感じにしてみました。

 

 図1 各クラスの学習パターン

そして先程のリンク先においておいた main.rb を実行すると代表ベクトルが更新されていくgif(図2)と、最終的に求められた代表ベクトルにより境界を引いてみた結果（図3）を出力します。図3に関しては以前書いた記事（【Ruby】 離散ボロノイ図の描画）をよかったらご参照ください。

$ ruby main.rb

 

図2 代表ベクトルが更新されていく様子 

 

図3 求められた境界線

おわりに

相変わらず適当なデータ生成。もう少しいろいろ勉強したら、実際にパターン収集したりとかして現実のデータを扱ってみたいです。