Pythonで始める情報検索 文書クラスタリング

なぜクラスタリングが必要か

検索エンジンの結果は「関連度が高い順」に並びますが、これは必ずしも使いやすいとは限りません。たとえば「環境問題」で検索すると、地球温暖化の話もあれば、酸性雨、騒音、ゴミ問題、さらには「プログラミング環境」のような別分野の話題まで混ざって出てきます。関連度順にそのまま読んでいくと、興味のある話とそうでない話が交互に出てきて効率が悪くなります。

あらかじめ「温暖化・環境汚染グループ」「まちづくりグループ」「プログラミング関連グループ」のように仕分けされていれば、興味のあるグループだけを選んで読むことができます。この「似たもの同士をグループ分けする」処理がクラスタリング、できあがったグループがクラスタです。

k平均法 ― 先にグループ数を決めるやり方

k平均法は、最初にグループの数（k個）を決めてから、データをそのグループに振り分けていく手法です。

1. データを適当にいくつかのグループに分けます
2. 各グループの平均位置を計算します
3. 各データを、より近い平均位置を持つグループへ移動します
4. グループの中身が変化しなくなるまで2〜3を繰り返します

本の中では、「環境」というキーワードで検索して集めた書籍12冊の紹介文を材料に、k=4で分類しています。結果は次の4グループにきれいに分かれました。

• 都市に関するグループ（都市計画、まちづくりなど）
• 情報処理・プログラミングに関するグループ
• エネルギー・工学に関するグループ
• 自然・生態系に関するグループ

手順がシンプルで扱いやすい一方、グループ数を先に人間側で決める必要がある点が制約となります。

凝集型階層的クラスタリング ― 近いもの同士を合体させるやり方

凝集型階層的クラスタリングは、k平均法と異なり、先にグループ数を決める必要がない手法です。

1. 最初は1個1個のデータがそれぞれ独立したクラスタです
2. 最も距離が近い2つのクラスタを結合します
3. 結合後のクラスタと他のクラスタとの距離を計算し直します
4. すべてが1つのクラスタになるまで2〜3を繰り返します

この結合の順番を木の枝のような図にしたものがデンドログラム（樹形図）です。早い段階で結合したペアほど似ており、遅い段階で結合したペアほど似ていません。

デンドログラムの例

5件のブログ記事タイトルをクラスタリングする場合を考えます。

• 東京の桜の名所
• 大阪の桜の名所
• 犬のしつけ方
• 猫のしつけ方
• 初心者向けプログラミング入門

内容の近さをもとに結合していくと、次のような順番になります。

1. 「東京の桜の名所」と「大阪の桜の名所」が結合します（どちらも桜の名所紹介で内容が近いため）
2. 「犬のしつけ方」と「猫のしつけ方」が結合します（どちらもペットのしつけ方で内容が近いため）
3. 桜グループとペットグループが結合します（どちらも生活・趣味の話題という点でやや近いため）
4. 上記グループと「初心者向けプログラミング入門」が結合します（技術的な話題で他とはあまり関連がないため、最後に結合）

これを樹形図として表すと、次のような階層構造になります。

• 全体（最後に1つに統合）
  • 生活・趣味グループ
  • 桜の名所グループ
    • 東京の桜の名所
    • 大阪の桜の名所
  • ペットのしつけグループ
    • 犬のしつけ方
    • 猫のしつけ方
  • 初心者向けプログラミング入門（他とは大きく離れて最後に結合）

ネストが深い組み合わせほど早い段階で結合された＝似ている関係、ネストが浅い組み合わせほど遅い段階で結合された＝似ていない関係を表しています。

color_thresholdという値を変えることで、後から「大まかに2グループで見る」「細かく4グループで見る」と粒度を調整できる点が大きな利点です。

グループ同士の「距離」の測り方

1対1の距離はシンプルですが、複数の要素からなるクラスタ同士の距離をどう定義するかにはいくつかの方式があります。代表的なものは以下の2つです。

• 群平均法: クラスタAとクラスタBの、全要素間の距離をすべて計算して平均を取る方式
• ウォード法: 2つのクラスタを結合したときに、クラスタ内のばらつきがどれだけ増えるかを基準にする方式。まとまりの良いクラスタを作りやすい方式です

同じデータでも、距離の測り方を変えると結果が変わることがあります。たとえば先ほどの5件の記事集合の場合、群平均法では「桜の名所グループ」「ペットのしつけグループ」「プログラミング記事」という3グループに分かれたのに対し、ウォード法では「生活・趣味系（桜＋ペット）」と「プログラミング記事」という、より大きな2グループにまとまる、といったことが起こり得ます。

同じデータでも測り方を変えると結果が変わるのは、データに複数の側面があり、どこに注目するかによって見え方が変わるためです。どちらが正解というものではなく、データの見方の一つとして使い分けるのが適切な向き合い方です。

手法の妥当性を測る：コーフェン相関係数

複数の距離の測り方を試すと結果もばらつくため、どの方法が元のデータの距離関係を最も正しく表現できているかを比較する指標が必要になります。

コーフェン相関係数はこのための指標で、元データ間の距離と、デンドログラム上の結合距離との相関を見ます。値が1に近いほど元の距離関係を歪めずに表現できていることを意味します。

本の例（書籍12冊のデータ）では群平均法が最も高い値となり、重心法（centroid）はマイナスの値になりました。このデータに関しては、群平均法が最も元の距離関係を保っていたことになります。

k平均法と階層的クラスタリングの比較

グループ数がすでに決まっている場合はk平均法が、グループ数が未定で全体構造も把握したい場合は階層的クラスタリングが適しています。

まとめ

• クラスタリングはデータの解釈を与えるものであり、唯一の正解があるわけではありません
• k平均法は、先にグループ数を決め、平均位置を基準にデータを寄せていく手法です
• 階層的クラスタリングは、近いもの同士から順に結合し、デンドログラムで全体像を把握できる手法です
• 同じデータでも手法によって結果が変わるのは、注目する側面が異なるためであり、優劣ではなく使い分けの問題です
• 検索結果をクラスタリングすることで、ランキングだけでは見えない全体構造を把握でき、関心の近い文書群を効率よく見つけられるようになります

参考文献

佐藤進也『Pythonではじめる 情報検索プログラミング』森北出版

• 近刊紹介記事（note・森北出版）