Hatena::ブログ(Diary)

記録用 このページをアンテナに追加 RSSフィード

2012-02-11

機械学習入門のメモ2

| 06:38 | 機械学習入門のメモ2を含むブックマーク 機械学習入門のメモ2のブックマークコメント

  • 2章終わりまで読んだ
    • n グラム作成時,文頭・文末にダミーをつけることをしばしば忘れるのでメモ

2012-02-09

機械学習入門のメモ

| 04:12 | 機械学習入門のメモを含むブックマーク 機械学習入門のメモのブックマークコメント

  • 凸集合と聞くとどうしても,ヘコミがあるような集合が想起されてしまうェ...
    • 凸集合の定義はヘコミの無い集合

2010-11-16

Ruby で Affinity Propagation らしきものを書いた

| 20:49 | Ruby で Affinity Propagation らしきものを書いたを含むブックマーク Ruby で Affinity Propagation らしきものを書いたのブックマークコメント

Affinity Propagation を Ruby で実装.

分割数とか評価関数とかなくて,Message Passing なる実数値を各ノード(データ)間で移動させることによってクラスタの代表点(exemplar)を決定するクラスタリング手法(らしい).


クラスタ数なんてクラスタリングするまで分からないけど,与えないと動かないから仕方なく与えていたタスクで使えそうですね.


クラスタ数はないけど,damping factor とか affinity matrix の対角成分など,クラスタリング結果を調節することのできるパラメータはあるといえばある.


"affinity_propagation.rb"

require 'my_vector'

class AffinityPropagation
  def initialize(data, damping_factor=0.9, iterate_max=1000, convergence=100)
    @data = data
    @damping_factor = damping_factor
    @iterate_max = iterate_max
    @convergence = convergence
    @result = { }
    @similarity_matrix = calc_similarity_of_all_pair
    @responsibility_matrix = initialize_matrix
    @availability_matrix = initialize_matrix
    ap_iterating
    show_result
  end

  def calc_similarity_of_all_pair
    sm = { }
    @data.each_with_index { |a, i|
      sm[i] = { }
      @data.each_with_index { |b, j|
        if i != j
          tmp = a - b
          sm[i][j] = -1.0*tmp.length**2
        end
      }
      sm[i][i] = sm[i].values.sort[(@data.length - 1)/2]
    }
    sm
  end
  
  def initialize_matrix
    mat = { }
    @similarity_matrix.length.times { |i|
      mat[i] = { }
      @similarity_matrix.length.times { |j|
        mat[i][j] = 0
      }
    }
    mat
  end
  
  def ap_iterating
    iterate = 0
    convergence = 0
    while convergence < @convergence && iterate < @iterate_max
      update_responsibility_matrix
      update_availablity_matrix
      convergence += (ap_clustering ? 1 : -1*convergence)
      iterate += 1
    end
    puts "iteration: %d" % iterate
  end

  def ap_clustering    
    result = { }
    @similarity_matrix.length.times { |i|
      @similarity_matrix.length.times { |j|
        result[i] = j if @responsibility_matrix[i][j] + @availability_matrix[i][j] > 0
      }
    }
    if @similarity_matrix.length != result.values.flatten.length
      @result = result
      return false
    elsif result != @result
      @result = result
      return false
    else 
      return true
    end
  end

  def update_responsibility_matrix
    @similarity_matrix.length.times { |i|
      @similarity_matrix.length.times { |j|
        @responsibility_matrix[i][j] = (1 - @damping_factor)*responsibility(i, j) + @damping_factor*@responsibility_matrix[i][j]
      }
    }
  end

  def show_result
    puts "centers: %s" % @result.values.uniq.sort.join(' ')
    tmp = @result.keys.sort.map { |k|
      @result[k]
    }
    puts tmp
    open('idx.txt', 'w') { |f|
      f.puts tmp
    }
  end

  def update_availablity_matrix
    @similarity_matrix.length.times { |i|
      @similarity_matrix.length.times { |j|
        @availability_matrix[i][j] = (1 - @damping_factor)*availability(i, j) + @damping_factor*@availability_matrix[i][j]
      }
    }
  end

  # r(i, k)
  # i -> k
  # k が i の exemplar として振舞うことがどれだけ相応しいか
  def responsibility(i, k)
    if i != k
      tmp = ((0..@similarity_matrix.length - 1).to_a - [k]).map { |kk|
        @availability_matrix[i][kk] + @similarity_matrix[i][kk]
      }.sort # equation (1)
    else
      tmp = ((0..@similarity_matrix.length - 1).to_a - [k]).map { |kk|
        @similarity_matrix[i][kk]
      }.sort
    end
    @similarity_matrix[i][k] - tmp.last
  end
  
  # a(i, k)
  # k -> i
  # i のために k を exemplar として選ぶことがどれだけ適切か
  # 初期値0
  def availability(i, k)
    def max(a, b)
      a > b ? a : b
    end
    
    def min(a, b)
      a < b ? a : b
    end

    sum = ((0..@similarity_matrix.length - 1).to_a - [i, k]).map { |ii|
      max(0, @responsibility_matrix[ii][k])
    }.inject(0) { |s, v| s + v }
    if i != k
      min(0, @responsibility_matrix[k][k] + sum) # equation(2)
    else
      sum # equation(3)
    end
  end
end

AP で使っているオレオレ Vector クラス

"my_vector.rb"


# オレオレ実装
# ベクトルクラス
class MyVector < Hash
  def initialize(hash)
    self.default = 0
    hash.each { |k, v|
      self[k] = v unless v == 0
    }
  end
  
  def + (arg)
    union_key = self.keys | arg.keys
    tmp = Hash.new(0)
    union_key.each { |k| 
      tmp[k] = self[k] + arg[k]
    }
    MyVector.new(tmp)
  end

  def * (arg)
    tmp = { }
    self.each { |k, v|
      tmp[k] = v*arg
    }
    MyVector.new(tmp)
  end

  def - (arg)
    arg = arg*(-1)
    self + arg
  end

  def / (arg)
    self*(1.0/arg)
  end

  def inner_product(arg)
    intersection = self.keys & arg.keys
    tmp = { }
    intersection.map { |k|
      self[k]*arg[k]
    }.inject(0) { |s, v| s + v}    
  end

  def length
    ip = self.inner_product(self)
    Math.sqrt(ip)
  end

  def cosine(arg)
    ip = self.inner_product(arg)
    ip/self.length/arg.length
  end
end

ファイルから similarity と preference を読むクラスを作って,

Affinity Propagation Web Applicationから

toy problem の similarity と preference をダウンロードして実行などする

require 'affinity_propagation'

class AffinityPropagation_for_file < AffinityPropagation
  def initialize(similarity, preference, damping_factor=0.9, iterate_max=1000, convergence=100)
    similarity_matrix_from_file(similarity, preference)
    @damping_factor = damping_factor
    @iterate_max = iterate_max
    @convergence = convergence
    @result = { }
    @responsibility_matrix = initialize_matrix
    @availability_matrix = initialize_matrix
    ap_iterating
    show_result
  end

  def similarity_matrix_from_file(similarity, preference)
    @similarity_matrix = { }
    # similarity matrix
    open(similarity) { |f|
      f.each { |l|
        i, j, v = l.split
        i = i.to_i - 1
        @similarity_matrix[i] = { } unless @similarity_matrix.key?(i)
        @similarity_matrix[i][j.to_i - 1] = v.to_f
      }
    }
    # preference
    open(preference) { |f|
      f.each_with_index { |v, i|
        @similarity_matrix[i][i] = v.to_f
      }
    }
  end
end

左がAffinity Propagation Web Applicationの結果で,

右がオレオレ AP の結果

% paste idx.txt idx2.txt
3       2
3       2
3       2
3       2
3       2
3       2
7       6
7       6
7       6
7       6
3       2
7       6
3       2
7       6
7       6
20      19
20      19
20      19
20      19
20      19
20      19
3       2
20      19
20      19
7       6

exemplar の番号が-1になっているけど結果としては同じになる.


単純,いや,ナイーブな実装かつ Ruby なのでとても実用的ではない.

なので,普通に使う分には C++ 実装とか R 実装とかを使用すべきだと思う.

2010-11-14

Complement Naive Bayes らしきものをRubyで書いた

| 10:33 | Complement Naive Bayes らしきものをRubyで書いたを含むブックマーク Complement Naive Bayes らしきものをRubyで書いたのブックマークコメント

#!/usr/bin/ruby -Ku

class CNB  
  def initialize(smoothing_parameter = 1)
    @frequency_of_word_by_class = { }
    @number_of_training_data_of_class = Hash.new(0)
    @smoothing_parameter = smoothing_parameter
  end
  
  def training(label, sosei)
    @frequency_of_word_by_class[label] = Hash.new(0) unless @frequency_of_word_by_class.has_key?(label)
    sosei.each { |k, v|
      @frequency_of_word_by_class[label][k] += v
    }
    @number_of_training_data_of_class[label] += 1
  end

  def total_number_of_word_in_other_class(c)
    all_words = @frequency_of_word_by_class.values.map { |h| h.keys }.flatten.sort.uniq
    other_classes = @frequency_of_word_by_class.keys - [c]
    other_classes.map { |c|
      all_words.map { |w|
        @frequency_of_word_by_class[c][w]
      }
    }.flatten.inject(0) { |s, v| s + v }
  end

  def number_of_word_in_other_class(c, i)
    other_classes = @frequency_of_word_by_class.keys - [c]
    other_classes.map { |c| @frequency_of_word_by_class[c][i] }.inject(0) { |s, v| s + v }
  end

  def classifier(sosei)
    all_class = @frequency_of_word_by_class.keys
    all_training_data = @number_of_training_data_of_class.values.inject(0) { |s, v| s + v }
    all_class.map { |c|
      n_c = total_number_of_word_in_other_class(c)
      alpha = @smoothing_parameter*sosei.length
      term2nd = sosei.to_a.map { |e|
        k = e[0]
        v = e[1]
        v*Math.log((number_of_word_in_other_class(c, k) + @smoothing_parameter).to_f/(n_c + alpha))
      }.inject(0) { |s, v| s + v }

      theta_c = @number_of_training_data_of_class[c].to_f/all_training_data
      [c, Math.log(theta_c) - term2nd]
    }.sort { |x, y| x[1] <=> y[1] }.last.first
  end
end

cnb = CNB.new

open(ARGV[0]) { |f|
  f.each { |l|
    label, sosei = l.strip.split(' ', 2)
    sosei = sosei.split(' ').map { |v| k, v = v.split(':'); [k, v.to_i] }.flatten
    sosei = Hash[*sosei]
    cnb.training(label, sosei)
  }
}

open(ARGV[1]) { |f|
  f.each { |l|
    label, sosei = l.strip.split(' ', 2)
    sosei = sosei.split(' ').map { |v| k, v = v.split(':'); [k, v.to_i] }.flatten
    sosei = Hash[*sosei]
    puts cnb.classifier(sosei)
  }
}

p(¥theta_{c})は訓練データ中のクラスcが出現した頻度に設定している.

各ラベルに対する事例数は,

% grep ^1 -c train
2305
% grep ^2 -c train
81
% grep ^3 -c train
211

事例数が異なるデータに対して分類し,

各クラスに対するprecision, recall, fscoreを計算すると次のようになる.

label=1, accuracy=0.770833, precision=0.953917, recall=0.903930, fscore=0.928251
label=2, accuracy=0.770833, precision=0.333333, recall=0.007220, fscore=0.014134
label=3, accuracy=0.770833, precision=0.200000, recall=0.057522, fscore=0.089347

libsvm(線形)だと

label=1, accuracy=0.854671, precision=0.916667, recall=0.964143, fscore=0.939806
label=2, accuracy=0.854671, precision=0.125000, recall=0.003663, fscore=0.007117
label=3, accuracy=0.854671, precision=0.250000, recall=0.015504, fscore=0.029197

今回使ったデータ

http://dl.dropbox.com/u/226917/train

http://dl.dropbox.com/u/226917/test

素性がBag of Wordsなので,素性を改良することでsvmもよくなるかもしれないけど,

CNBもありだよねと思った

2010-06-13

OAuth で Streaming API

| 22:06 | OAuth で Streaming APIを含むブックマーク OAuth で Streaming APIのブックマークコメント

GitHub - yayugu/Ruby-Twitter-Streamno title を利用して,Streaming API を使う際にも OAuth 認証する,6月で Basic 認証が終わりらしいので.


やることは,Net::HTTRequest#basic_auth から OAuth の Net::HTTPRequest#oauth! に変更するという簡単なお仕事.


できたものが GitHub - laughing/Ruby-Twitter-Stream: Simple library to access the Twitter Streaming API. It only needs pure-ruby and rubygems.


TwitterStream#new に Hash の形で Consumer_Key とか渡してあげて,

TwitterStream#sample とかして,後は適当にステータスを処理してあげると.