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

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

この記事を読むのに必要な時間:およそ 6 分

距離関数クラスの作成

さて,先のページで説明した階層的クラスタリングの手順の中に,最も距離の近いクラスタまたはデータ項目の対を検索する処理がありました。ここで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に集約されるまで繰り返しています。

著者プロフィール

浜本階生(はまもとかいせい)

1981年生まれ。栃木県出身。東京工業大学情報工学科卒業。技術やアイデアの組み合わせから面白いソフトウェアを生み出したいと日々考えている。現在,ブログの解析および視覚化の試みとして「TopHatenar」「Blogopolis」を開発,運用中。

URLhttp://d.hatena.ne.jp/kaiseh/