NCDで何でもクラスタリング

正規化圧縮距離という概念がある。英語では Normalized Compression Distance、略してNCDという。この概念は情報の距離を測るメジャーとして使うことができる。では情報の距離とは何か。それはデータの類似度で測る距離である。データXとデータYという2つのデータがあったとき、XとYの類似度を考えてみよう。類似度すなわち「似ている度合い」を距離に見立て、XとYが似ていれば「近い」、そしてXとYがかけ離れたデータであって全く似ていなければ「遠い」というわけだ。

NCDでは、データの類似度を計算するために、そのデータが持つ情報量を使う。 NCDの凄いところは、基本的にデータの情報量のみに依存しているので「その対象は何でも構わない」という点にある。すなわち、テキスト文書だろうが、画像や音楽のデータだろうが、はたまたDNAシーケンスだろうが、システムログだろうが、データの種類を問わず何でも距離を測ることができる。大量データの解析や分類、データマイニングを行う際に、分析のカギとなる特徴量をどうやって定めるかは悩ましい問題だが、NCDを使えば、特徴量の定義に関してアレコレと試行錯誤を重ねる必要はない。いかなるデータに対しても使える汎用のツール、なんとも頼もしい道具である。

NCDの原理

NCDの考え方を説明するために、冒頭で述べた2つのデータXとYに、もう一度、登場を願おう。 XとYに関するNCDの計算では、情報の圧縮率に関する性質が巧みに使われている。すなわち「Xの圧縮率」に比べて「Yを知っているときのXの圧縮率」はとても小さくなるということを利用して、類似度から距離の値を導き出しているのである。

全てのビットが同じ、つまり”11111….1″というように極端なケースを除けば、一般的にはデータが何であれ、それ単独でデータ圧縮をかけたときに圧縮後のファイルサイズがほぼ0に近くなることはあり得ない。しかし、どんな大きなファイルサイズのデータXであっても、もしXとYが同じデータであってYが既知であるならば、「Yと同じ」という4文字までデータXを圧縮することができる。あるいはYをコピーすればXを複製できるのであるから、Xは消してしまってもよい。0バイトまで圧縮可能ともいえよう。一方、XとYが何ら関係のないデータであれば、Yを知っていたからといってXの圧縮率が下がることはない。

また、2つのデータに共通のクセがあれば、情報圧縮の原理から、それらはまとめて圧縮後のデータにコーディングされることになる。したがってXとYに何らかの共通性があれば、それぞれを単独に圧縮したときと比べて圧縮率の向上を見込むことができるだろう。

このような情報圧縮の性質を利用し、「それぞれの圧縮率」や「一方を知っているときの他方の圧縮率」によって定義される距離として、NCDの値が計算される。なお、実際にはデータの長さに依存しないように正規化処理が加えられるため、NCDの値は0.0(データが同じとき)から1.0(データがかけ離れているとき。ただし圧縮過程の誤差から1.0をわずかに越えることもある)までの値をとる。

クラスタリングしてみよう

さて、NCDはどれだけ使えるものだろうか。 NCDを用いた情報の整理手法として、クラスタリングを考えてみる。ここでは、具体的にNCDで階層的クラスタリングを行ってみた例を2つ紹介しよう。階層的クラスタリングとは、距離が近いものを見つけてはクラスタ化するという作業を全体で1つのクラスタとなるまで順次進めていくことで、データ全体を分類する手法だ。

次の図(クリックで拡大)は、テキストデータを対象としてNCDによる階層的クラスタリングを適用した結果を示している。分析対象のテキストには、ここ1年以内に執筆された記事から15本を選んだ。具体的には、本コラムの執筆陣から5名を無作為に選び、それぞれ直近の記事を3本ずつ抽出、合計15本の記事を選ぶという手順を経て分析対象のデータを用意した。

抽出したテキストデータから著者名を削除、タイトルと本文のみを切り出してから、NCDによるクラスタリングを適用した結果が次の図である。

グラフの葉ノード(末端の楕円)は、著者ごとに色分けされている。それぞれの記事が著者ごとに分類されている傾向を見て取ることができるだろう。テーマ選びだけでなく、文体のクセまでも、思った以上に著者ごとの偏りがあるということか。

また次の図(こちらもクリックで拡大)は、筆者が台北を訪問したときに撮影したスナップショットの画像データを、同じようにNCDを用いて分類してみたものである。台北101の展望台から撮影した夜景は隅にまとめられていたり(左上)、似たような構図の写真や新幹線の写真が近いところに置かれていたり(右端)、人間が目視で並べ替えた結果に近い分類結果が得られている点に着目されたい。

期待されるアプリケーション

2つの例を見て、「NCD、それなりに使えそうでは?」という感じは掴めたのではないだろうか。あとはこれを何に活用するか。いずれも研究レベルではあるが、製品・サービスの価値評価や、英作文のピアレビュー効果測定などに応用した例が報告されている。

大量の画像データから類似画像を検出したり、ビデオデータから特定のシーンを検出したりといった「類似した○○を検出する」マイニング技術にも応用が効くだろう。直近で思いつく具体的なアプリケーションとしては、著作物の権利侵害を検出するツールへの応用が考えられる。パラグラフの順番を入れ替えたり、若干の編集を加えたりした程度の文章であれば、元文書との距離は極端に近くなる。それを利用すれば、コピペや盗用を検知することも簡単にできる。

NCDは数年前に提唱された技術ながら、日本ではまださほど普及が進んでいない。しかし、なにしろ対象とするデータは何でもよいのだから、アプリケーションの範囲は幅広く、大きな可能性を秘めている技術である。

本文中のリンク・関連リンク：

藤原らによる「コルモゴロフ複雑性に基づく製品・サービスの価値評価」
吉澤らによる「英作文授業におけるピアリヴュー活動」