bayonやCLUTOが爆速な理由

クラスタリングツールbayonを使っていて、常々「どうしてこんなに高速に処理できんのかなぁ」と疑問に感じていました。repeated bisectionという手法自体がk-means法などと比べると効率がいいのですが、それにしても、それだけでは説明がつかないほど爆速なわけです。

うまく例えられませんが、自前でk-meansのスクリプトを書いて比べてみると、自転車と新幹線くらいちがうという印象です。はじめてCLUTOを触った時、数万件程規模のクラスタリング処理が本当に「あっ」という間に終わってしまい、びっくりした記憶があります。

きっと実装面でなにか特殊なことがあるんだろうなと思い、mixiエンジニアブログでbayonの記事を改めて読み漁っていたら、以下の部分が目に止まりました。

このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほどクラスタの中心に凝集しているようになり、クラスタ中のデータが似た者同士の集まりである、と考えるわけです。

ふむふむ。cosine類似度の和が大きいほどまとまりがよい、というのは直感的に理解できますね。

ただし、クラスタ中の各要素と中心との類似度をまじめに全て比較するのは計算量も高くなってしまいます。実際には、この値はクラスタ中のベクトルをすべて足した複合ベクトルの長さと同値になり、そのため計算量も少なく評価値を求めることができます。

なぬ！？要するにcosine類似度を全部足すと、全ベクトルを足しこんだもののノルムに等しくなる、ということを言ってます！？ま、まじっすか！

「くわしくはCLUTOの論文読んでね」と書いてあったので、適当にあたりをつけながら斜め読みしてみました。Criterion Function（評価関数）の説明の部分にそれらしき記述がありました。

どうやらこれはComposite Vector（複合ベクトル）の特性のようです。
確かにこの特性を利用すれば計算コストは大幅に削減できそうです。

実験

というわけで簡単なスクリプトを書いて確認してみました。

use strict;
use warnings;

#----------------------------------------------------------
#
# クラスタ中の全ベクトルと重心とのcosine類似度を全部足すと、
# 複合ベクトルのノルムに等しくなるかどうかを確認してみます
#
#----------------------------------------------------------

# 適当なベクトルを準備
my $vec_1 = {
    '日本' => 1,
    '今日' => 3,
    '高校' => 2,
    '国語' => 1,
};

my $vec_2 = {
    '日本' => 2,
    '今日' => 1,
    '高校' => 1,
    '数学' => 1,
    '国語' => 1,
};

my $vec_3 = {
    '今日' => 1,
    '高校' => 1,
    '国語' => 5,
    '英語' => 3,
};

# 単位長に正規化
for ( $vec_1, $vec_2, $vec_3 ) {
    unit_length($_);
}

#------------------------------------------------------------
# 重心とのコサイン類似度を足し込んで行く
#------------------------------------------------------------

# 重心を取得
my $centroid = centroid( $vec_1, $vec_2, $vec_3 );

# 各ベクトルと重心との類似度を足して行く
my $sum;
for ( $vec_1, $vec_2, $vec_3 ) {
    $sum += cosine_similarity( $_, $centroid );
}

#------------------------------------------------------------
# 複合ベクトルのノルムを計算してみる
#------------------------------------------------------------

# 複合ベクトルを計算
my $comp = composite( $vec_1, $vec_2, $vec_3 );

# 複合ベクトルのノルムを取得
my $norm = norm($comp);

#------------------------------------------------------------
# 出力! 結果は同じ値になるか！？
#------------------------------------------------------------

print $sum,  "\n";
print $norm, "\n";

exit;


# 以下サブルーチン

sub centroid {
    my @vec = @_;
    my %cent;
    for (@vec) {
        while ( my ( $key, $value ) = each %$_ ) {
            $cent{$key} += $value;
        }
    }
    while ( my ( $key, $value ) = each %cent ) {
        $cent{$key} /= int @vec;
    }

    return \%cent;
}

sub unit_length {
    my $vec  = shift;
    my $norm = norm($vec);
    while ( my ( $key, $value ) = each %$vec ) {
        $vec->{$key} = $value / $norm;
    }
}

sub norm {
    my $vec = shift;
    my $norm;
    for ( values %$vec ) {
        $norm += $_**2;
    }
    sqrt($norm);
}

sub composite {
    my @vec = @_;
    my %comp;
    for (@vec) {
        while ( my ( $key, $value ) = each %$_ ) {
            $comp{$key} += $value;
        }
    }
    return \%comp;
}

sub cosine_similarity {
    my ( $vector_1, $vector_2 ) = @_;

    my $inner_product = 0.0;
    map {
        if ( $vector_2->{$_} )
        {
            $inner_product += $vector_1->{$_} * $vector_2->{$_};
        }
    } keys %{$vector_1};

    my $norm_1 = 0.0;
    map { $norm_1 += $_**2 } values %{$vector_1};
    $norm_1 = sqrt($norm_1);

    my $norm_2 = 0.0;
    map { $norm_2 += $_**2 } values %{$vector_2};
    $norm_2 = sqrt($norm_2);

    return ( $norm_1 && $norm_2 )
        ? $inner_product / ( $norm_1 * $norm_2 )
        : 0.0;
}

結果。

2.47915597812817
2.47915597812817

おお、本当に一致しましたよ！びっくり。

ちなみに単位長で正規化している部分ですが、これはCLUTOの論文を読んでいたら「unit length」という表現があったので気がつきました。

まとめ

クラスタリングの処理でとにかく時間がかかるのは、重心点との類似度（もしくは距離）の計算を全ポイントの回数繰り返す部分でした。しかもそういった処理を何度も何度も繰り返していく必要があるので、対象データの件数が多くなると、猛烈にループ回数が多くなってしまいます。

でも、「複合ベクトル(composite vector）のノルム」を使ってクラスタの評価関数（Criterion Function）を組んであげれば、この部分の計算コストが圧倒的に節約できます。

つまりは、これがbayonやCLUTOが爆速である理由のようです。

いまさらながら、一つだけ賢くなってしまいました。