クラスタリング手法について

どうもこんばんは、south37です。最近は「集合知プログラミング」を読み進めています。前回までは第二章の「協調フィルタリングによる推薦」について説明をしていた訳ですが、今回からは第三章の「クラスタリング」について説明をしていきたいと思います。

ある特定の集合に対して、その集合内の要素同士を比較する方法を与えてやる事で、集合は類似のサブグループに分割する事が出来ます。これが「クラスタリング」と呼ばれるものです。

要素同士の比較方法としては、類似度が見積もれれば何でも良くて、例えば前回や前々回に使用していたjaccard相関関数なんかも使えます。その為、はてなブックマークを例にとれば、自分のブックマークしたURLをクラスタリングするといった事も可能です。

集合知プログラミング」では、クラスタリング手法として「階層的クラスタリング」と「K平均法によるクラスタリング」という手法が紹介されていました。この二つのクラスタリング手法について簡単に説明してみたいと思います。

階層的クラスタリング

階層的クラスタリングにおいては、「もっとも似ている2つのグループをあたらしいグループとしてまとめる」といった操作を繰り返す事で、グループの階層を作り上げます。階層構造は最終的にはbinary treeの形で表現される事になります。

具体的な手順を見てみましょう。

  1. 最初のステップは個々の要素同士の類似度を見積もる事で、その中で最も類似度の高いペアをまとめて、一つのサブグループを作ります。
  2. 作ったサブグループの持つ属性はそれを構成するペアの属性の平均として算出します。
  3. ペアが1つ新しく出来て全体の要素(サブグループ)数が1つ減った状態で、再び1-2を行います。以後それを繰り返します。

このような手順をとる事で、1サイクルごとにサブグループの数が1つずつ減って行き、最終的に目的の数にまでサブグループの数を減らす事が出来ます。各サブグループはその要素として2つのサブグループを持つ事になる為、集合全体の階層構造はbinary treeの形で表現される事になります。

単純な方法でイメージしやすいのですが、計算量が大きくなりがちなのが難点です。

K平均法によるクラスタリング

K平均法においては、集合の個々の要素が配置された多次元空間上にk個の点を配置し、それをクラスタの中心の出発点とします。集合内の全ての要素において、どのクラスタの中心点と一番近いかが調べられ、クラスタの新しい中心点の属性はその中心点に一番近い要素達の属性の平均として表現されます。このステップを繰り返す事によって、クラスタリングが行われます。

階層的クラスタリングにおいてはN個の集合に対して最も類似度の高いペアを見つける為にO(N2)の計算量が必要であるのに対して、K平均法では個々の要素のクラスタ平均点との距離を見積もるのにO(N)の計算量で十分となります。その為、K平均法によるクラスタリングの方が小さな計算量となります。

まとめ

要素間の類似度を見積もる方法が存在すれば、目的の集合においてクラスタリングを行う事が出来ます。クラスタリング手法にはいくつか種類が存在し、階層的クラスタリングにおいてはサブグループの階層構造を完璧に求められる一方、大きな計算量が必要となります。K平均法によるクラスタリングにおいては、より少ない計算量でクラスタリングを行う事が出来ます。

集合知プログラミング

集合知プログラミング