具体例で学ぶ!情報可視化のテクニック

第2回階層的クラスタリングによる特徴抽出

はじめに

前回は、情報可視化の基本的な考え方について、HatenarMapsなどの実例を示しながら説明しました。第2回以降は、Java言語を使用して実際にプログラムを作成することで、情報可視化の実践例を示していきたいと思います。

目標

本連載では、はてなブックマークの人気エントリーのデータを可視化することを最終的な目標にします。可視化にあたっては、統計学的観点から「階層的クラスタリング⁠⁠、視覚的観点から「ツリーマップ」の手法をそれぞれ用いることにします。

Java開発環境のセットアップ

手元にJavaの開発環境がなく、本連載のプログラムを試したい場合には、Sun Microsystemsが提供している統合開発環境、NetBeansの導入をおすすめします。 NetBeansはオールインワン型のIDEですので、インストールするだけで特別な設定の必要もなく、一通りの開発環境を整えることができます。

NetBeansのインストール時にはJDK(Java Development Kit)が必要になりますので、あらかじめインストールしておきましょう。また、NetBeansのダウンロードページには何種類ものパッケージが用意されていますが、⁠Java SE」または「すべて」のパッケージを選択すれば良いでしょう。

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

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

階層的クラスタリングの概要

今回は、データを可視化しやすくするための「前処理」として、統計学的手法を使ってデータの特徴を抽出する過程を取り上げます。統計学的手法には様々なものがありますが、本連載では「階層的クラスタリング」を扱うことにします。

階層的クラスタリングとは、類似性の高いデータ同士をグループ化し、さらにそのグループ同士をまとめて親グループ化するという作業を繰り返すことで、グループの階層構造を作り出す手法です図1⁠。

階層的クラスタリングのアルゴリズムの手順を示すと、次のようになります。

  1. データ集合の中から、互いの距離が最も近くなるデータ項目の対を探す。
  2. その項目対を、1つのクラスタに統合する。
  3. そのクラスタと残りのデータ集合の中から、互いの距離が最も近くなる要素対を探して統合する。
  4. 上記の処理を、データ全体が1つのクラスタに統合されるまで繰り返す。
図1
図1 clustering

以上の手順によって、ツリー状のクラスタ構造が形成されます図2⁠。

各クラスタのノードが常に2つの子ノードを持つことから、このツリーは二分木(binary tree)となります。

図2
図2 clustering_tree

本連載では、多次元ベクトルの集合を対象とした階層的クラスタリングを行います。基礎的なベクトル演算のみを使用しますので、ベクトルの知識がなくても、内容を理解する上で特に問題はありません。

ベクトルクラスの作成

Javaの標準ライブラリには、多次元ベクトルを扱うクラスが存在しません。そこでまず、独自のベクトルクラスを用意することにします。クラス名は「Vector」でも良いのですが、Java標準のjava.util.Vectorクラスとの混同を避けるため、MultiVectorとしました。

MultiVectorクラスは、double型の実数を成分とし、任意の次元を持つベクトルを表現します。以下に、クラスの一部を示します。完全なソースコードはこちらをご覧ください。

リスト1 MultiVector.java(部分)
public class MultiVector {
    private double[] data;

    // 指定された次元数でゼロベクトルを作成
    public MultiVector(int dimension) {
        data = new double[dimension];
    }

    // 次元数チェック
    private void checkDimension(MultiVector v) {
        if (dimension() != v.dimension()) {
            throw new IllegalArgumentException("Dimension mismatch."); 
        }
    }

    // 指定されたベクトルを加算
    public void add(MultiVector v) {
        checkDimension(v);
        for (int i = 0; i < dimension(); i++) {
            data[i] += v.data[i];
        }
    }

    ...
}

MultiVectorには、以下のような初等的な演算メソッドが実装されています。

void add(MultiVector v)
ベクトルにvを加算します。
void subtract(MultiVector v)
ベクトルからvを減算します。
void multiply(double d)
ベクトル成分をd倍します。
void divide(double d)
ベクトル成分をdで除算します。
double norm()
ベクトルのノルム(長さ)を計算します。
void normalize()
ベクトルを正規化します(ノルムが1になるように調整します⁠⁠。
double distanceSq(MultiVector v)
このベクトルとvの距離の二乗を計算します。

ノードクラスの作成

次に、クラスタのツリー構造をJavaで表現してみましょう。

まず、末端のデータ項目ノードとクラスタノードを統一的に扱うため、共通インターフェイスとなるNodeインターフェイスを作成します。Nodeには、ノードが含む全てのベクトルを返すgetVectorsメソッドを定義します。

リスト2 Node.java
public interface Node {
    List<MultiVector> getVectors();
}

次に、これを実装する形で、データ項目のノードを表現するItemクラスを作成します。Itemクラスは個々のベクトルに対応するので、getVectorsメソッドの戻り値は、そのベクトルだけを含む長さ1のリストになります。

リスト3 Item.java
public class Item implements Node {
    private String name; // 結果出力用のプロパティ
    private MultiVector vector;

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

    public String getName() { return name; }
    public MultiVector getVector() { return vector; }

    public List<MultiVector> getVectors() {
        // ベクトル自身をリスト化して返す
        return Collections.singletonList(vector);
    }
}

同様に、Nodeインターフェイスを実装するClusterクラスを作成します。Clusterクラスは、2つの子ノードleftとrightを持ちます。getVectorsメソッドの戻り値は、leftノードとrightノードの同メソッドの呼び出し結果を連結したものになります。

リスト4 Cluster.java
public class Cluster implements Node {
    private Node left;
    private Node right;
    private List<MultiVector> cachedVectors;

    public Cluster(Node left, Node right) {
        this.left = left;
        this.right = right;
    }

    public Node getLeft() { return left; }
    public Node getRight() { return right; }

    public List<MultiVector> getVectors() {
        // 高速化のため結果をキャッシュする
        if (cachedVectors == null) {
            cachedVectors = new ArrayList<MultiVector>();
            // leftノードとrightノードのベクトル集合を連結
            cachedVectors.addAll(left.getVectors());
            cachedVectors.addAll(right.getVectors());
        }
        return cachedVectors;
    }
}

距離関数クラスの作成

さて、先のページで説明した階層的クラスタリングの手順の中に、最も距離の近いクラスタまたはデータ項目の対を検索する処理がありました。ここで1つの疑問が浮かびます。末端のデータベクトル間の距離は自明ですが、複数のベクトルを含んでいるクラスタ間の距離はどのように計算すれば良いのでしょうか。

この距離の計算には、いくつかの戦略があります。どの戦略を用いるかによって、クラスタリングの結果も変わってきます。今回は、最も単純な戦略の1つである最短距離法(nearest neighbor method)を使用することにします。最短距離法は、双方のクラスタが含むベクトル同士の組み合わせの中で、最も近接しているベクトル間の距離を採用する手法です図3⁠。

図3
図3 nearest_neighbor_method

戦略を後で簡単に切り替えられるように、距離計算に特化したDistanceEvaluatorインターフェイスを用意することにしましょう。DistanceEvaluatorは、ノード間の距離を実数で返すdistanceメソッドを持ちます。

リスト5 DistanceEvaluator.java
public interface DistanceEvaluator {
    double distance(Node n1, Node n2);
}

このインターフェイスを実装し、最短距離法に基づくNearestDistanceEvaluatorクラスを作成します。

リスト6 NearestDistanceEvaluator.java
public class NearestDistanceEvaluator implements DistanceEvaluator { 
    public double distance(Node n1, Node n2) {
        double minDistSq = Double.MAX_VALUE;
        for (MultiVector v1 : n1.getVectors()) {
            for (MultiVector v2 : n2.getVectors()) {
                // 全てのベクトルの組み合わせに対して距離を計算
                double distSq = v1.distanceSq(v2);
                // 最小となる距離を採用
                if (distSq < minDistSq) {
                    minDistSq = distSq;
                }
            }
        }
        return Math.sqrt(minDistSq);
    }
}

このdistanceメソッドでは、n1とn2に含まれるベクトルの組み合わせを順に全て試し、最小となる距離を求めています。計算量が非常に大きくなりますので、大量のデータを扱う場合には、途中の計算結果を再利用するなどの工夫が必要になるでしょう。

階層的クラスタリングの実装

ベクトル、ノード、距離関数と材料が揃ったところで、階層的クラスタリングの本体部分となるClusterBuilderクラスを記述してみます。

リスト7 ClusterBuilder.java
public class ClusterBuilder {
    private DistanceEvaluator distanceEvaluator;

    public ClusterBuilder(DistanceEvaluator distanceEvaluator) {
        this.distanceEvaluator = distanceEvaluator;
    }

    public Node build(List<? extends Node> nodes) {
        // ノードが1つに集約されるまで繰り返す
        while (nodes.size() > 1) {
            Node merge1 = null;
            Node merge2 = null;
            double minDist = Double.MAX_VALUE;
            // 距離が最小となるノード対を探す
            for (int i = 0; i < nodes.size(); i++) {
                Node n1 = nodes.get(i);
                for (int j = i + 1; j < nodes.size(); j++) {
                    Node n2 = nodes.get(j);
                    double dist = distanceEvaluator.distance(n1, n2); 
                    if (dist < minDist) {
                        merge1 = n1;
                        merge2 = n2;
                        minDist = dist;
                    }
                }
            }
            // 次ステップ用のノードリストを作成
            List<Node> nextNodes = new ArrayList<Node>();
            for (Node node : nodes) {
                // 統合対象にならなかったノードを追加
                if (node != merge1 && node != merge2) {
                    nextNodes.add(node);
                }
            }
            // 統合対象のノード対をクラスタ化して追加
            nextNodes.add(new Cluster(merge1, merge2));
            nodes = nextNodes;
        }
        return nodes.get(0);
    }
}

上のbuildメソッドは、1ページ目に示した階層的クラスタリングのアルゴリズム手順をそのまま踏襲しています。ノードリストの中から距離が最小となるノード対を探し、クラスタ化します。この処理を、ノード数が1に集約されるまで繰り返しています。

色集合の階層的クラスタリング

それでは、ClusterBuilderに実際にデータを入力して、動作を確認してみることにしましょう。テストデータとして、私たちに馴染みの深い「色」を使用します。モニタの表示色は、赤・緑・青の3つの成分を持っていますので、これを3次元のベクトルとして表現することが可能です。ここでは、次に示す6色をそれぞれベクトル化し、クラスタリングを実行してみます。なお、各色の色見本は図4の通りです。

図4
図4 color
  • ブルー(java.awt.Color.BLUE)
  • シアン(java.awt.Color.CYAN)
  • マゼンタ(java.awt.Color.MAGENTA)
  • オレンジ(java.awt.Color.ORANGE)
  • ピンク(java.awt.Color.PINK)
  • レッド(java.awt.Color.RED)

クラスタリングの実行結果は、何らかの形で画面上に表示する必要があります。今回は視覚的表現にはこだわらず、クラスタのツリー構造をそのままコンソールへ出力することにします。

以上を行うDemoクラスは、次のようになります。

リスト8
public class Demo {
    public static void main(String[] args) {
        new Demo().run();
    }

    public void run() {
        // 入力データを作成
        List<Item> input = new ArrayList<Item>();
        input.add(new Item("BLUE", colorToVector(Color.BLUE)));
        input.add(new Item("CYAN", colorToVector(Color.CYAN)));
        input.add(new Item("MAGENTA", colorToVector(Color.MAGENTA))); 
        input.add(new Item("ORANGE", colorToVector(Color.ORANGE)));
        input.add(new Item("PINK", colorToVector(Color.PINK)));
        input.add(new Item("RED", colorToVector(Color.RED)));

        // 最短距離法に基づく階層的クラスタリングを準備
        DistanceEvaluator evaluator = new NearestDistanceEvaluator();
        ClusterBuilder builder = new ClusterBuilder(evaluator);

        // クラスタリングを実行
        Node result = builder.build(input);

        // クラスタリング結果を表示
        output(result, 0);
    }

    private MultiVector colorToVector(Color c) {
        // 色成分を3次元のベクトルに変換
        return new MultiVector(c.getRed(), c.getGreen(), c.getBlue());
    }

    private void output(Node node, int depth) {
        // インデントを表示
        for (int i = 0; i < depth; i++) {
            System.out.print("  ");
        }
        if (node instanceof Item) {
            // 末端ノードなら項目名を表示
            System.out.println(((Item) node).getName());
        } else if (node instanceof Cluster) {
            // クラスタなら"+"を表示し、子ノードを再帰的に表示
            System.out.println("+");
            Cluster cluster = (Cluster) node;
            output(cluster.getLeft(), depth + 1);
            output(cluster.getRight(), depth + 1);
        }
    }
}

Demoクラスを実行すると、以下の出力が得られます。

図5
+
    +
        RED
        +
            MAGENTA
            +
                ORANGE
                PINK
    +
        BLUE
        CYAN

いかがでしょうか。ブルーとシアン、オレンジとピンクがそれぞれ統合され、オレンジとピンクのクラスタはさらにマゼンタと統合されています。類似性の強い色同士がグルーピングされている様子が良く分かると思います。

今回作成した階層的クラスタリングのプログラムは、より次元数の多いベクトルデータにも、そのまま適用が可能です。本連載の最終回では、はてなブックマークのエントリーをベクトル化し、クラスタリングすることが目標になります。

まとめと次回予告

今回は、統計学的な観点からの情報可視化へのアプローチとして、階層的クラスタリングの手法を紹介しました。また、実際に階層的クラスタリングを行うプログラムを作成し、動作確認を行いました。

次回は視覚的な観点にフォーカスを移し、ツリー構造を平面上にマッピングして可視化する「ツリーマップ」の手法を取り上げる予定です。ご期待ください。

おすすめ記事

記事・ニュース一覧