クラスタリング

クラスタリングとは

クラスタリングは、データ同士の類似度をもとにデータをグループ化するデータ解析の手法です。この手法を使うことで、データ自身がどのようなクラスター(塊)から構成されているのかがわかり、データの構造に関するさまざまな知見を得ることができます。下の散布図では、データが2次元と低次元であるため、人の目でも概ね2つのグループからなることが見て取れますが、データが高次元の場合には、こうしたデータの構造を調べることはそれほど容易とは言えなくなります。

2つのクラスターからなるデータ(散布図)

クラスタリングと呼ばれるデータ解析の手法を使うことで、こうしたデータのグループ分けを人の目ではなく、コンピュータによる処理として実現することができます。クラスタリングにも幾つかの手法がありますが、まずは代表的な階層クラスタリングK平均クラスタリングについてご紹介しましょう。

階層クラスタリング

階層クラスタリングでは、データの類似度を元にデータをグループ化していきます。この類似度の近いデータを順番にグループ化していく過程で自然な階層構造が出来上がりますが、この階層構造をグラフとして表したものが樹形図(デンドログラム)です。

樹形図(デンドログラム)

この樹形図を見ることで、それぞれのグループがどのように結合していったのかを知ることができます。

階層クラスタリング

MATLAB®で階層クラスタリングを実行する手順としては、データの類似度に関する情報をpdist 関数で算出した後で、関数linkageによりクラスタリングを実行します。クラスタリングの結果は、dendrogram関数により樹形図として可視化することができます。

K平均クラスタリング

K平均法(k-means)とも呼ばれるこのアルゴリズムにおいては、データがいくつのクラスターに分割されるのかを予め定めた上で、それぞれのクラスターの代表点を求め、これらの代表点からの距離によって、各サンプルがどのクラスターに属するのかを決定します。ただし、こうした代表点は、勝手に決めていい訳ではなく、全てのサンプルに対する以下の距離 d の合計が最小になるような場所に定められます。

各サンプルと代表点の間の距離

この最適化の問題は、一般には次のような反復計算により解を求めます。クラスターの個数をK個とした場合、まずK個のクラスターの中心として、K個のサンプルをランダムに選び出します。(K平均++と呼ばれるアルゴリズムにより選ばれることもあります)。次に、このK個の代表点を使って、サンプルがどこのクラスターに属するかを決定していきます。つまり、各サンプルから最も近いところに代表点があるクラスターを、そのサンプルが属するクラスターとして決定します。そして、次に各クラスターの代表点をサンプルの平均から作り直します。具体的な手順は次のようになります。

  1. 各クラスターの代表点をランダムに(あるいはK平均++を利用して)決定する
  2. 代表点までの距離をもとに、各サンプルがどのクラスターに属するかを決定する
  3. 代表点をそのクラスターに属するサンプルの平均値として算出する
  4. 収束していなければ2に戻る

この操作が収束するまで繰り返すことで、データをクラスタリングするのがK平均法です。「K平均法」という名前は、このK個の平均値を使うことにその語源があります。なお、クラスターの個数Kの決定には、シルエット値というものが用いられることがあります。シルエット値については、関数 silhouette に詳しい解説にありますので、そちらをご覧下さい。

混合ガウスモデルによるクラスタリング

K平均法によるクラスタリングでは、あるサンプルが特定のクラスターに属するかどうかはクラスターの中心までの距離によって、かなりはっきりと決まっていました。例えば、クラスターAの中心までの距離とクラスターBの中心までの距離がほぼ同じくらいであったとしても、少しでもどちらかに近ければ近い方に属するとして、反復計算を進めていました。

しかし、あるサンプルのクラスターAへの距離とクラスターBへの距離が同じくらいということであれば、このサンプルがそれぞれに属する確率は同じくらいだと言えるかもしれません。そこで、こうしたサンプルのクラスターへの帰属を0か1かの断定的なやり方で決めるのではなく、確率値として表現することで柔軟にクラスタリングを行う手法が生み出されました。これが混合ガウスモデルを使ったクラスタリングです。混合ガウスモデルによるクラスタリングでは、各クラスターをガウス分布により近似します。つまり、各クラスターをガウス分布でモデル化することで、各サンプルがどのクラスターに帰属するのかという情報を0か1かではなく、確率値(スコア)として柔軟に表現することができるようになります。

サンプルの各クラスターへの「帰属」を確率値として表現できる

具体的には、次のような手順に沿って、各サンプルのスコアの算出と各クラスターのガウス分布としてのパラメータ(平均と分散共分散行列)の推定を繰り返します。

  1. 各クラスターの平均と分散協分散行列を初期化する(K平均++等のアルゴリズム)
  2. 各サンプルがどのクラスターに属するかの確率値(スコア)を算出する
  3. サンプルのスコアをもとに、各クラスターの平均と分散共分散行列を算出する
  4. 収束していなければ2に戻る

この計算を収束するまで繰り返すことで、最終的に各サンプルのスコアと各クラスターのガウス分布としての平均と分散共分散行列が決定されます(EMアルゴリズム)。これが混合ガウスモデルによるクラスタリングです。

2次元の混合ガウス分布によるクラスタリングの例

自己組織化マップ

クラスタリングにニューラルネットの枠組みを利用したものが、自己組織化マップと呼ばれる手法です。この手法では、平面上のユニット上にサンプルを配置することでクラスタリングを実現させます。それぞれのユニットは、クラスタリング対象のデータと同じ次元のベクトルデータを保持しており、隣接するグリッド同士が保持するベクトルが似たものであるか、そうでないかによって領域を分割できますが、この分割を利用してクラスタリングを実現します。

ユニットの保持するベクトルがクラスター同士の境界を定める

サンプルがどのユニットに配置されるのかがわかれば、そのユニットの属するクラスターから最終的にサンプルの属するクラスターが判明します。以下の図は、MATLABのNeural Network Toolbox™ を使って、自己組織化マップを実行した例です。

Neural Network Toolbox による自己組織化の例

このグラフでは、ユニット自身と隣接するユニット同士の距離が同時に可視化されています。ユニットは紫色で表現され、ユニットが保持するベクトル同士の距離は黄色から黒の間の色で表現されています(色が濃くなるほどにユニット同士が保持するベクトルが乖離していることを意味する)。この図を見ると、概ねユニットが4つのエリアに分割されていることがわかります。ユニットが保持するベクトルデータは最初ランダムにセットされますが、その後はサンプルが配置される毎に少しずつ修正されます。

自己組織化マップの学習

つまり、ある特定のユニットにサンプルが配置されると、そのユニットと周辺のユニットが保持するデータは配置されたデータに合せて少しずつ修正されます。このようにすることで、自動的に隣接するユニット同士は自然に同じようなベクトルデータを保持するようになります。しかし、場合によっては隣接するユニット同士であってもどうしても保持するデータの差異が大きくなることがあります。こうした差異の大きいユニットの同士の境目がクラスターを分割する境界として利用できることになります。

MATLABによる統計解析・機械学習

Statistics and Machine Learning Toolbox™ および Neural Network Toolbox を使うことで、クラスタリングを含むさまざまな統計解析・機械学習の手法を簡単に試してみることができます。教師なし学習の代表とも言えるクラスタリングだけでなく、教師あり学習としての分類・回帰なども幅広くサポートしています。また、近年はGUIベースの各種ツールも提供され、各種のアルゴリズムもさらに使いやすくなっています。



ソフトウェア リファレンス

参考 : Statistics and Machine Learning Toolbox, Neural Network Toolbox, 機械学習, 教師なし学習, AdaBoost, データ解析, 数理モデリング