クラスタ作成に向けた準備

前エントリで期間を空けて〜と言いましたが，完全に放置してしまいました．
3章のクラスタリングをプログラミングしていたのですが，バグバグになってしまい完全にハマってしまっていました．
時間は掛かりましたが，バグも解きほぐれてまともに動くようになったので，掲載します．

今回は階層型クラスタを作成する訳ですが，そのためには必要なデータ構造について準備しておく必要があります．
おおまかな流れはこんな感じになります．

準備
　Rubytreeによる木構造の表現
　SetのようなもののRubyでの表現
本題
　階層型クラスタの作成
　K平均法クラスタの作成

木構造の表現

後ほど作成する階層型クラスタは，最終的に木構造のデータとして表現されます．なので，Ruby上でも木を扱えなければなりません．
ArrayやHashのように標準ライブラリとして実装されていればいいのですが，さすがに日常的に使うやつはいないのか，残念ながら標準ではありません．

幸い，Gemsにいくつか登録されているものがあるので，ありがたく使わせていただきましょう．
今回は名前もそのまんまな「Rubytree」を使います．

Rubytreeの使い方

インストールはgemコマンド一発で，さくっと済ませます．

% sudo gem install rubytree

Rubytreeでは通常の木(Tree::TreeNode)と二分木(Tree::BinaryTreeNode)のどちらも作れます．
階層型クラスタは二分木で作成しますので，ここからは二分木(Tree::BinaryTreeNode)を使うことを前提とします．

基本的な使い方は，以下の通りです．
非常に直感的に操作できるので，使い方に迷うことはないでしょう．
ちなみにRubytreeのメソッドは全てCapitalizeされています．Rubyistにはちょっと違和感ありますね...

require 'rubygems'
require 'tree/binarytree'
include Tree

# ルートノードを作成
root = BinaryTreeNode.new('root')

# 子ノードを作成
left_child = BinaryTreeNode.new('left_child')

# 子ノードに子ノード(ルートから見たら孫)を追加
left_child << BinaryTreeNode.new('left_grand_child')
left_child << BinaryTreeNode.new('right_grand_child')

# ルートに子ノードを追加
root << left_child

# ルートに直接子ノードを追加することもできます
root << BinaryTreeNode.new('right_child')

# 最後に全体を表示
root.printTree

実行すると↓のようになります．

 * root
|---+ left_child
|    |---> left_grand_child
|    +---> right_grand_child
+---> right_child

Rubytreeをちょっと改変

これで二分木を手に入れた訳ですが，この先都合が悪い面もあります．

子ノードとしてBinaryTreeNodeしか受け付けないので，必ずBinaryTreeNode.newして追加しなければならない
　→正直面倒くさい
全ての階層のノードを表示してしまう
　→クラスタにした際には，末端のノード(葉)のみ表示したい

この不満を解消するために，Rubytreeを継承したクラスを作り，一部メソッドをオーバーライドします．

module My
  class Node < Tree::BinaryTreeNode
    # 新しい枝を生成する
    # 葉には何を入れてもOK
    def Node.new_branch(name, left, right)
      branch = Node.new(name)
      left.respond_to?(:name)  ? (branch << left)  : (branch << Node.new(left))
      right.respond_to?(:name) ? (branch << right) : (branch << Node.new(right))
      branch
    end

    # ツリー表示をオーバーライド
    def printTree(level = 0)
      if isRoot?
        print name
      else
        print "|" unless parent.isLastSibling?
        print('  ' * (level - 1) * 2)
        print(isLastSibling? ? "+" : "|")
        print "----"
        print(hasChildren? ? "+" : ">")
      end

      # 枝は名前を表示しない
      isLeaf? ? (puts " #{name}") : puts

      children { |child| child.printTree(level + 1) }
    end
  end
end

先ほどとほぼ同じ結果を得られるコードはこのようになります．

include My

root = Node.new('root')

# いきなり子ノードと孫ノードを作って追加する
root << Node.new_branch('left_child', 'left_grand_child', 'right_grand_child')
root << Node.new('right_child')
root.printTree

上記のクラスを使った場合の結果はこんな感じ．

root
|----+
|    |----> left_grand_child
|    +----> right_grand_child
+----> right_child