はじめに

前回は、統計学的観点からの情報可視化へのアプローチとして、「⁠階層的クラスタリング」の手法を紹介し、その実装と動作確認を行いました。

今回からは、階層的クラスタリングの実行結果を視覚的に分かりやすく表現する手段として、「⁠ツリーマップ」と呼ばれるテクニックを取り上げます。

ソースコードのダウンロード

今回作成するプログラムのソースコードは、こちらから一括してダウンロードすることができます。ZIPファイルを展開して生成されるフォルダを、プロジェクトとしてNetBeansに読み込むことも可能です。

ツリーマップの概要

ツリーマップ（treemap）とは、二次元平面上の領域を入れ子状に分割することによって、木構造のデータを可視化する手法です。

ツリーマップを利用した情報可視化の有名な例としては、世界のニュース記事をタイル状に並べて閲覧できるnewsmap（図1）があります。

また、著者の開発したHatenarMaps（図2）も、ボロノイツリーマップ（voronoi treemap）と呼ばれるツリーマップの一種を使用しています。

なお、Javaにはjava.util.TreeMapという名前のクラスが存在しますが、これは平衡木を使用した連想配列の実装を指しており、可視化手法のツリーマップとは全く関係がありませんので注意してください。

ツリーマップの長所

ツリーマップは、一般的なツリー記法と比較して、2つの大きな利点を持っています。

1つ目の利点は、空間効率の良い情報可視化を実現できることです。画面を隙間なく利用するため、限られた空間に多くの情報を詰め込むことができます。ツリーマップを使えば、画面上に数百、数千のノードを一度に表示することも可能です。

2つ目の利点は、分割された各領域の面積を自由に決められることです。newsmapとHatenarMapsでは、このツリーマップの性質を活用し、重要なニュース記事や著名なブロガーほど大きな面積で表示されるように工夫を行っています。

二分木のツリーマップ

前回解説した階層的クラスタリングでは、各々のノードがそれぞれ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();
    }

   ...
}

色データに特化したノードクラスの導入

次回のツリーマップの実践では、入力として大量の色データを使用します。そこであらかじめ、色データに特化した末端ノードクラスを用意しておくことにしましょう。Itemクラスを継承したColorItemクラスを、以下のように作成します。

public class ColorItem extends Item {
    private Color color;

    public ColorItem(Color color, double area) {
        super(color.toString(), colorToVector(color), area);
        this.color = color;
    }

    private static MultiVector colorToVector(Color c) {
        return new MultiVector(c.getRed(), c.getGreen(), c.getBlue());
    }

    public Color getColor() { return color; }
}

ColorItemクラスでは、前回の実践に倣って、色が持つ赤・緑・青の3つの成分をベクトル化しています。

Ward法の導入

前回は、階層的クラスタリングの距離関数として「最短距離法」を採用しました。しかし、最短距離法は極めて単純な戦略であることから、データの分類感度がそれほど高くありません。もっと優秀なクラスタリング結果を得るために、より洗練された距離関数である「Ward法」を実装することにしましょう。

Ward法では、以下の式で定義されるd(C1, C2)がクラスタ間の距離となります。

式や言葉で説明するよりも、実際のコードを読んだ方が理解は早いでしょう。以下が、Ward法の距離関数を実装したWardDistanceEvaluatorクラスになります。

public class WardDistanceEvaluator implements DistanceEvaluator {
    public double distance(Node n1, Node n2) {
        double s12 = sumCentroidDistanceSq(new Cluster(n1, n2));
        double s1 = sumCentroidDistanceSq(n1);
        double s2 = sumCentroidDistanceSq(n2);
        return s12 - (s1 + s2);
    }

    private double sumCentroidDistanceSq(Node n) {
        List vectors = n.getVectors();
        // ノードに含まれる全ベクトルの平均値を求め、クラスタの重心とする
        MultiVector center = new MultiVector(vectors.get(0).dimension());
        for (MultiVector vector : vectors) {
            center.add(vector);
        }
        center.divide(vectors.size());

        // ノードに含まれる各ベクトルと重心の距離の二乗の総和を計算
        double sum = 0;
        for (MultiVector vector : vectors) {
            sum += vector.distanceSq(center);
        }
        return sum;
    }
}

後編に続く

今回は、ツリーマップの概要と、そのアルゴリズムの基本的な考え方を説明しました。また、ツリーマップを実践する準備段階として、前回作成した階層的クラスタリングのプログラムに機能追加を行いました。

後編となる次回は、これまでのプログラムを元にして、いよいよツリーマップの描画へと入っていきます。お楽しみに！