クラスタリング (クラスター分析、Cluster Analysis)

データから自然なグループやパターンを見つけ出し、視覚化する

クラスタリングは、データセットに隠されたグループやパターンを見つけることを目的とするデータ解析の手法です。探索的なデータ解析によく用いられますが、異常検知や、機械学習の一つである教師あり学習の前処理にも使用されます。

クラスタリングアルゴリズムは、あるグループ (クラスタ) 内のデータが、他のクラスタ内のデータよりも高い類似度を持つようにグループ化します。類似性の尺度には、ユークリッド距離、確率的な距離、コサイン距離、相関係数など、さまざまなものがあります。多くの教師なし学習は、クラスタリングの一種です。

クラスタリングのアルゴリズムは、大きく分けて次の2つのグループに分かれます。

  1. ハードクラスタリング: k平均法のように、各データポイントが1つのクラスタにしか属さないもの。
  2. ソフトクラスタリング: ガウス混合モデルのように、各データポイントが複数のクラスタに属することができるもの。例えば、複数の基音の組み合わせとしてモデル化できる音声の音素や、複数の生物学的プロセスに関与しうる遺伝子など。
K平均法は、各メンバーの平均値である重心でグループを表現するもので、上の図では星で描かれています。

K平均法は、各メンバーの平均値である重心でグループを表現するもので、上の図では星で描かれています。

混合ガウスモデルは、異なるクラスタとの関連性の強さを表すクラスタメンバーシップ確率を割り当てます。

混合ガウスモデルは、異なるクラスタとの関連性の強さを表すクラスタメンバーシップ確率を割り当てます。

クラスタリングは、パターンやシーケンスを識別するためにさまざまなドメインやアプリケーションで使用されています。

  • クラスタは、データ圧縮法において、生の信号の代わりにデータを表現することができます。
  • クラスタは、セグメンテーションアルゴリズムにおいて、画像やLidarの点群領域を示すものです。
  • バイオインフォマティクスでは、遺伝子のクラスタリングや配列解析が用いられます。

クラスタリング技術は、半教師あり学習において、ラベル付きデータとラベルなしデータの間の類似性を確立するためにも使用されます。半教師あり学習では、最小限のラベル付きデータで初期モデルを構築し、元々ラベルがついていないデータにラベルを割り当てるために使用されます。一方、半教師ありクラスタリングでは、いくつかの観測値が同じクラスタに属することがわかっている場合や、いくつかのクラスタが特定の結果変数に関連している場合など、クラスタに関する利用可能な情報をクラスタリングプロセスに組み込みます。

ここから、MATLABがサポートしている一般的なクラスタリングの手法をご紹介します。

 

階層クラスタリング

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

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

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

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

階層クラスタリング

階層クラスタリング

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次元の混合ガウス分布によるクラスタリングの例

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

自己組織化マップ

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

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

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

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

 Deep Learning Toolbox による自己組織化の例

Deep Learning Toolbox による自己組織化の例

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

自己組織化マップの学習

自己組織化マップの学習

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

他にも以下のクラスタリングの手法がよく使われています。

  • Spatial clustering (よく使われる密度ベースのDBSCANなど)は、密度の高い領域では近接した点をグループ化し、密度の低い領域では外れ値を追跡します。任意の非凸形状を扱うことができます。
  • スペクトルクラスタリングは、入力データをグラフベースの表現に変換し、元の特徴空間よりもクラスターがよく分離されるようにします。グラフの固有値を調べることで、クラスターの数を推定することができます。
  • 隠れマルコフモデルは、バイオインフォマティクスにおいて、遺伝子やたんぱく質の配列のパターンを発見するために使用されます。

キーポイント

  • クラスタリングは、探索的なデータ解析、異常検知やセグメンテーション、教師あり学習の前処理などによく用いられます。
  • k平均法や階層型クラスタリングは人気がありますが、非凸形状の場合はDBSCANやスペクトルクラスタリングのようなより高度な技術が必要です。
  • データのグループを発見するために使用できる教師なしの手法には、次元削減技術や特徴量ランク付けがあります。

 

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

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

MATLABによるクラスタリングの例

imsegkmeansコマンド (k平均法を実行する) を使用して、MATLABは元の画像 (ヘマトキシリン・エオジン染色した組織) に3つのクラスタを割り当て、組織の3つのクラス (白、黒、グレーで表現) にセグメンテーションしました。
このコード例では、関連するセグメンテーションアプローチと同様に、ご自身でお試しいただけます。

cluter-analysis-discovery-page-he-image
cluter-analysis-discovery-page-cluster-index-image

参考: Statistics and Machine Learning Toolbox, Deep Learning Toolbox, 機械学習, 教師なし学習, AdaBoost, データ解析, 数理モデリング, 人工知能 (AI)