二分木のツリーマップ

前回解説した階層的クラスタリングでは，各々のノードがそれぞれ2つの子ノードを持つ「二分木」のクラスタツリー構造が出力されたことを憶えているでしょうか。今回からは，この二分木を入力として，長方形型のツリーマップを描画することを目標にします。

それでは早速，二分木からツリーマップを作成する手順を見ていきましょう。

1. ツリーマップの各領域の面積を決めるため，二分木の各末端ノードにあらかじめ「サイズ」の数値属性を持たせておく（図3⁠）⁠。

2. ツリー全体を格納する大きな長方形を用意する。

3. 長方形を，ルートノードが持つ2つの子ノードのサイズ比率に従って分割する（図4⁠）⁠。

このとき，長方形のアスペクト比（縦横比）ができるだけ1:1に近づくように，以下の方針で分割する。

• 現在の長方形が横長ならば，左右に分割する
• 現在の長方形が縦長ならば，上下に分割する

4. 分割後の長方形と対応する子ノードについて，同様の処理を再帰的に実行する（図5⁠）⁠。

処理対象のツリー構造を二分木に限定した場合，このように単純なロジックで領域を分割していくことができます。したがって，階層的クラスタリングとツリーマップの相性は非常に良いと言えるでしょう。

階層的クラスタリングの手直し

ツリーマップの描画に先立って，前回作成した階層的クラスタリングのプログラムに機能追加を行います。機能追加の内容は，ノードインターフェイスの拡張と，新しい距離関数の導入です。以下，順に見ていきましょう。

ノードサイズの導入

クラスタリングのノードを示すNodeインターフェイスに，ノードサイズを返すgetArea()メソッドを追加します。

public interface Node {
    List getVectors();
    double getArea();
}

このgetArea()メソッドを，ItemクラスとClusterクラスでそれぞれ実装します。まずItemクラスでは，double型のarea変数をフィールドに用意し，値をそのまま返すようにします。

public class Item {
    private String name;
    private MultiVector vector;
    private double area;

    public Item(String name, MultiVector vector, double area) {
        this.name = name;
        this.vector = vector;
        this.area = area;
    }

    public double getArea() { return area; }
    ...
}

次にClusterクラスでは，左右の子ノードのgetArea()メソッドを呼び出し，その戻り値の合計を返すようにします。

public class Cluster {
    private Node left;
    private Node right;

    public double getArea() {
        return left.getArea() + right.getArea();
    }

   ...
}