Rubyで『集合知プログラミング』(4)

Ruby アルゴリズム 書籍

第3章「グループを見つけ出す」

3.4 デンドログラムを描く

"clusters.rb"の続きです。

描画ライブラリにはcairoを使用します。
cairoのインストールは

gem i cairo
で行いました。

クラスタの高さを計算します。
ここで言う「高さ」は，文字通り画像のy軸方向の高さになります。

def get_height(clust)
  # 終端であれば1，枝であれば子クラスタの高さの合計
  if clust.leaf? then 1
  else get_height(clust.left) + get_height(clust.right) end
end

クラスタの深さを計算します。
ここでは，子クラスタ間の距離の累積値になるんでしょうか？

def get_depth(clust)
  # 終端であれば0，枝であれば子クラスタの深さの最大値＋子クラスタ間の距離
  if clust.leaf? then 0
  else [get_depth(clust.left), get_depth(clust.right)].max + clust.distance end
end

デンドログラムを描画します。
画像のサイズなど，書籍とは異なります。

def draw_dendrogram(clust, labels, png='clusters.png')
  h = get_height(clust) * 20
  w = 1400
  depth = get_depth(clust)

  # 深さに応じて縮尺 この300は最右のラベルを表示するための余白
  scaling = ((w-300)/depth.to_f)

  # 白を背景とする画像を作成
  surface = Cairo::ImageSurface.new(w, h)
  context = Cairo::Context.new(surface)
  context.set_source_rgb(1,1,1)
  context.rectangle(0, 0, w, h)
  context.fill

  # 描画色，フォントなど
  context.set_source_rgb(0,0,0)
  context.select_font_face('serif')
  context.set_font_size(12)

  # ルートクラスタの横線
  context.move_to(0, h/2)
  context.line_to(10, h/2)
  context.stroke

  # ルートクラスタから描画
  draw_node(context, clust, 10, h/2, scaling, labels)

  # pngで保存
  surface.write_to_png(png)
end

クラスタを描画します。
top,bottomの意味が書籍と異なります。

def draw_node(context, clust, x, y, scaling, labels)
  unless clust.leaf?
    # 子クラスタの高さ
    h_l = get_height(clust.left) * 20
    h_r = get_height(clust.right) * 20

    # ここで書籍では
    # top = y - (h1 + h2) / 2
    # bottom = y + (h1 + h2) / 2
    # とし，子クラスタまで含めた上下端をtop，bottomとしているが，
    # 無駄な計算のような気がしたので，以下のようにした

    # 縦線の上端と下端
    # leftのクラスタは上，rightのクラスタは下に描画する
    # 各クラスタの高さの逆比で描画位置を設定する
    # そうしないと，画像の高さ内にうまく収まらない
    top = y - h_r / 2
    bottom = y + h_l / 2

    # 水平線の長さ 長いほどクラスタ同士は似ていない
    horiz_len = clust.distance * scaling

    # [ 型に線を描画
    context.move_to(x+horiz_len, top)
    context.line_to(x, top)
    context.line_to(x, bottom)
    context.line_to(x+horiz_len, bottom)
    context.stroke

    # 子クラスタの描画
    draw_node(context, clust.left, x+horiz_len, top, scaling, labels)
    draw_node(context, clust.right, x+horiz_len, bottom, scaling, labels)
  else
    # 終端であればアイテムのラベルを描画
    context.move_to(x+5, y+5)
    context.show_text(labels[clust.id])
  end
end

実行します。
前回同様，'blogdata.txt'は，ダウンロードした本家サンプルにあったものを使いました。

blognames, words, data = read_file('blogdata.txt')

clust = hcluster(data)

draw_dendrogram clust, blognames
以下，生成されたデンドログラムです。

参考