[Ruby]k-means法を実装してみた
こんにちは、しきゆらです。
今回はクラスタリング手法の一つであるk-means法を実装してみたのでまとめてみます。
使用言語は、もちろんRubyです。
なお、ライブラリ等は使わずに実装してみました。
k-means法とは？
簡単に言えば、複数のデータをグルーピングする方法です。
アルゴリズムが単純なのでよく使われるようです。
以下に、参考となるようなページを示しておきます。
中には、どのように処理していくのかをイメージしやすくビジュアライズしてくれているところもあります。
参考
実装
自分なりに作ってみたものを以下に示します。
今回使用したデータは、都道府県の産業に関するものでした。
class RegionData
# 都道府県ごとのデータ数
@@label_num = 29
def initialize(input_data, label)
@data = input_data
@region = label
end
# 距離を求める
def distanse(point)
# それぞれの大きさが異なる時、nilを返す
return nil unless @data.length == point.length
dist = @data.zip(point).map do |item|
# (1,1), (3,5)のとき
# (1,3), (1,5) => (4), (4) となる
item.inject{|result, data| (result - data) ** 2}
end
# 各点同士の和を返す
dist.inject(:+)
end
# 自分の持つ値を返す
def values
@data
end
# 自分の地域を返す
def area
@region
end
end
# クラスタをランダムに配置する
def random_clusterize(data, cluster_num)
data_size = data.length
clusters = []
cluster_num.times do |i|
# __start: 要素全体をデータ数で割った時の最初の要素の位置
__start = (i * data_size / cluster_num).to_i
# __end: __startの次の位置
# 最後の部分の時は、その要素数
__end = if(i != data_size - 1) then
((i + 1) * data_size / cluster_num).to_i
else
data_size
end
clusters[i] = data[__start...__end]
end
return clusters
end
# クラスタの中心を求める
def get_center_point(cluster)
data_cluster = cluster.map{|region| region.values}
data_cluster.transpose.map{|cols| cols.inject(:+).fdiv(cols.length)}
end
# 結果の出力
def print_result(clusters)
num = 1
clusters.each do |cluster|
print("Cluster #{num}: \n")
# クラスターごとに、地域名を出力する
cluster.each_with_index do |region, i|
print("#{region.area}\t")
puts if i % 10 == 9
end
# クラスターラベルを1文字ずらす
num += 1
puts
end
end
# クラスタリングを行う
def clusterize(data, cluster_num)
clusters = random_clusterize(data, cluster_num)
center_points = []
cluster_num.times do |i|
center_points << get_center_point(clusters[i])
end
loop do
temp_clusters = []
cluster_num.times do |i|
temp_clusters[i] = []
end
# 全ての地域データと中心点の距離を求め, 最も小さいものに分類する
data.each do |region|
# p("center_points:", center_points)
minimam_index = 0
minimam_distance = Float::INFINITY
center_points.each_with_index do |point, index|
dist = region.distanse(point)
if(minimam_distance > dist) then
minimam_index = index
minimam_distance = dist
end
end
temp_clusters[minimam_index] << region
end
temp_centers = []
temp_clusters.each_with_index do |cluster, index|
# p cluster.map{|regions| regions.area}
center = get_center_point(cluster)
if center.length.zero? then
center = center_points[index]
end
temp_centers << center
end
# 前回の中心点と今回のものが同じ時、終了
break if temp_centers.eql?(center_points)
# ここまで来た時は、もう一度処理する必要あり
clusters = temp_clusters
center_points = temp_centers
end
print_result(clusters)
end他のサイトを覗くと、数十行程度で実装されているのに対し、私のは130行ほどあります・・・。
ともかく、大まかにみてみきます。
データの形
想定しているデータとして、都道府県毎に産業に関する割合のデータが29個ずつあります。
それを1つの配列に収めて、都道府県名でラベルづけものがRegionDataになります。
大まかな処理の流れ
まずは、データを読み込みRegionDataの配列を作ります。
それらをクラスタリングしたい数で割った小さな配列を作り、クラスタを作ります。(random_clusterize)
次に。それぞれのクラスタの中心座標を求めます。(get_center_point)
すべてのRegionDataと、それぞれのクラスタの中心座標を比較して
距離が最も短いクラスタに振り分けていきます。(clusterizeのloopあたり)
新しいクラスタができたら、そのクラスタの中心座標を求めます。
最終的に、前回の中心点と新しいクラスタの中心点がすべて同じになったときloopが終わります。
中心点を求める
中心点を求める部分は、コード的には2行ですが若干面倒なことをしています。
# クラスタの中心を求める
def get_center_point(cluster)
data_cluster = cluster.map{|region| region.values}
data_cluster.transpose.map{|cols| cols.inject(:+).fdiv(cols.length)}
endそれぞれのRegionData間の中心点を求めるには、各データの平均を求めなければいけません。
例えば、データが以下のような形の場合・・
[table id=4 /]
それぞれのデータの中心は
[(0.5 + 0.4 + 0.2) / 3, (0.1 + 0.3+ 0.8) / 3, (0.9 + 0.2 + 0.03) / 3, (0.1 + 0.3 + 0.2) / 3]
のように上記表の列毎の総和の平均を求める必要があります。
しかし、データ的には都道府県毎の行データの行列しかありません。
そこをなんとかするために、
- RegionDataのデータのみの配列を作る
- それぞれを転置して列毎の総和を求める
という手順で処理しています。
転置を行うことで、列毎のデータを行データとすることができます。
あとは、injectで総和を求めれば良いわけです。
おそらく、Matrixなどのライブラリを使えばもっとスッキリしそうな気はしますが、
今回はできるだけ自力でなんとかしたかったので、無理やりこう処理しました。
さいごに
アルゴリズムとしてはとても単純なので簡単に作ることができました。
久々にちゃんとしたプログラムを書いたような気がします。
今回はここまで。
おわり