軽量データクラスタリングツールbayon

逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。

クラスタリングとは

クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。

例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。


様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下のページが詳しいため、そちらをご参照下さい。


●クラスタリングとは (クラスター分析とは)

●Wikipedia: データ・クラスタリング

軽量データクラスタリングツールbayon

シンプルなデータクラスタリングツールとして、bayonというツールを作成しました。名前は、筆者が好きなアンコール・ワット遺跡のバイヨン寺院から拝借したもので、特にクラスタリングには関係ありません。


●fujimizu/bayon · GitHub

●bayon - simple and fast clustering tool (旧リポジトリ, 更新終了)


bayonはシンプルな構成で、かつ大規模なデータでも実用的なスピードで実行できるようにすることを目標に作成しています。手元の環境でいくつかのデータセットを用意して簡単に実行時間を測ってみたところ、以下の結果が得られました。50万件のデータでも12分程度で完了できており、用途にもよるとは思いますが、実用に耐えるだけの速度は得られていると思います。

データ数	クラスタ数	実行時間(秒)
1000	10	0.17
50000	1000	36
500000	10000	720

bayonはクラスタリング手法として、後述するRepeated Bisection法を採用しているのですが、これは他のクラスタリングツールCLUTOで使用されている手法です。CLUTOは高速かつ精度もよいクラスタリングツールで、GUIでの利用や様々なオプションなどを利用することができる非常に便利なツールです。じゃあそもそもCLUTOを使えばいいのでは？となりそうですが、CLUTOは商用で利用する場合は事前許可が必要となり、使用の際はライセンスに注意しなければなりません。その点bayonはライセンスにGPL2を採用しているため、商用のサービスでの利用も問題ありません。

また手元の環境で試した限りでは、クラスタリングの実行速度はCLUTOよりもbayonの方が上回っています。ただCLUTOは精度向上のためにさらに複雑なことをしているので、単純な比較はできないのですが、さくっと傾向を確認したい場合等にはbayonも一つの選択肢として考慮していただければ幸いです。

実行方法

実際にbayonでクラスタリングを行う際は、まず入力として以下のようなタブ区切りのテキストファイルを用意してください。1行に1つのドキュメントの情報を表し、行の先頭にドキュメントのID、それ以降はそのドキュメントの特徴を表すキーとポイントをペアで記入します。

% cat input.tsv
阿佐田  J-POP      10  J-R&B     6   ロック4小島    ジャズ8レゲエ9古川    クラシック4ワールド4田村    ジャズ9メタル2レゲエ6青柳    J-POP       4  ロック    3   HIPHOP   3
三輪    クラシック8ロック1

例えば上記の例では、1ユーザの情報を1つのドキュメントと考え、ユーザが聞く音楽のジャンルによってそのユーザの特徴を表しています。﹁阿佐田﹂﹁小島﹂﹁古川﹂が各ユーザのID(名前)で、﹁阿佐田﹂の特徴を表すキーとして﹁J-POP﹂﹁J-R&B﹂﹁ロック﹂が挙げられています。

次にこの入力ファイルを使って、クラスタリングを実行します。以下ではクラスタ数を3に指定して実行しています。

% bayon -n 3 input.tsv > output.tsv

クラスタリング結果は、以下のようなタブ区切りのテキストになります。1行が1つのクラスタを表し、行の先頭がクラスタのID、それ以降はそのクラスタに所属するドキュメントのIDのリストです。

% cat output.tsv
1       小島    田村2阿佐田  青柳3古川    三輪

それぞれ、ジャズ好き、J-POP・ロック好き、クラシック好きのクラスタに分割できていることが分かります。

より詳しく知りたい方は、チュートリアルを用意してありますので、そちらをご参照下さい。

クラスタリング手法

bayonでは、Repeated Bisectionと呼ばれるクラスタリング手法を採用しています。Repeated BisectionはクラスタリングツールCLUTOで使用されているクラスタリング手法で、データ集合を繰り返し2分割することでクラスタリングを実行します。K-means法などと比較して、高速に実行でき、また精度も良好なようです。

Repeated Bisectionではまずすべてのデータを1つのクラスタに格納し、その後は以下の1-4の処理を実行して、繰り返してクラスタを2分割してクラスタリングを行います。


(一)分割するクラスタを1つ選択する(一番クラスタ内のまとまりが悪いものを選択)

(二)クラスタ中からランダムに2つ要素を選択し、それぞれが格納したクラスタを2つ作成する

(三)元のクラスタ中の全ての要素に対し、2で選んだ要素との類似度を求め、類似度が高い方のクラスタに要素を追加する

(四)2クラスタ間で要素の移動を行い、分割結果の洗練を行う(移動できる要素がなくなるまで続ける)



ここで、2-4のプロセスだけに注目してみると、これはクラスタの中心を2つとしてK-means法を実行しているのと同じことをしています。つまりRepeated BisectionはK-meansを繰り返し実行しているだけなのです。

プロセス1でまとまりの悪いクラスタを選択するとき、プロセス4で要素を移動してクラスタの洗練を行うときは、クラスタのまとまり具合を評価する必要があります。このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほどクラスタの中心に凝集しているようになり、クラスタ中のデータが似た者同士の集まりである、と考えるわけです。ただし、クラスタ中の各要素と中心との類似度をまじめに全て比較するのは計算量も高くなってしまいます。実際には、この値はクラスタ中のベクトルをすべて足した複合ベクトルの長さと同値になり、そのため計算量も少なく評価値を求めることができます。評価値についてはCLUTOの論文に詳しく書かれているため、そちらをご参照下さい。

また、既存のクラスタリング手法には、確率・統計な枠組みを使用したより精度が高いと思われる手法が存在します。今回はシンプルさと実用的なスピードを主な目的としたためそれらは採用しませんでしたが、今後は他の手法も組み込み、実行時に自由に切り替えられるようにできればと考えています。

まとめ

軽量クラスタリングツールbayonのご紹介をさせていただきました。 bayonは容易に使用することができ、また実用に耐えられるだけのスピードを備えています。精度・機能面や、汚いソースコードなどまだまだ改善の余地がたくさんありますが、データの特徴をサッと調べたいときなどには皆様のお役に立てるかもしれません。もしご興味がある方がいらっしゃいましたら、ぜひご利用下さい！