クラスタリングについて

概要

ものすごくざっくりまとめると、

教師なし学習手法
多変量のサンプルデータが大量にある場合で
どういう傾向のクラスタに分割できるかがわからないときに
ひとまずクラスタリングしてみることによって、全体のサンプルの中でのクラスタをなんとなく分割することができるよ、という手法
結論ありきでやるものではなく、まずはやってみてそこから考えよう、という使い方をする…のか？
モデルを推定していくときの元ネタとして使う？

分類対象の集合を，内的結合(internal cohesion)と外的分離(external isolation)が達成されるような部分集合に分割すること．

教師なし

性質が近い観測データ点をひとまとまり（これを「クラスタ」と呼ぶ）にまとめる

3つのキーポイント

「性質が近い」ということを定量的に表すために観測データ点間の距離を定義する

距離の近いものをどのようにまとめるかというアルゴリズム

いくつのまとまり（＝クラスタ）があるのか

ただし、クラスタ数はまとめるアルゴリズムと密接に関連すると距離ないし類似度が大切なので、まずはそれから。

神嶌先生 - クラスタリング (クラスター分析)

定番の神嶌先生の記事。

階層型クラスタリング

Ｒとクラスター(1)

階層的クラスター分析とは、個体間の類似度あるいは非類似度(距離)に基づいて、最も似ている個体から順次に集めてクラスターを作っていく方法である。

　①距離(あるいは類似度)を求める方法を選択し、個体間の距離(類似度)を計算する。
　　②クラスター分析の方法（最近隣法、最遠隣法など）を選択する。
　　③選択された方法のコーフェン（Cophenetic）行列を求める。
　　④コーフェン行列に基づいて樹形図を作成する。
　　⑤結果について検討を行う。

　階層的クラスター分析の方法はクラスター間の距離をどのように求めるかで、最近隣法、最遠隣法、群平均法、メディアン法、重心法、ウォード法などに分かれる。

非階層型クラスタリング（k-means法について）

ノード間の距離計算

ユークリッド距離、マハラノビス距離など

K means Clustering Algorithm

シンプソンズの例が分かりやすい。

k-means 法の注意点とオレオレベストプラクティス

k-means 法を実際に利用する際の注意点がまとまった記事。

「分析で k-means 法を使わなくちゃいけない＞＜」ってなったときは、次のような運用が安全だと言えます。

ループはできる限り収束するまで回す

ある k においてはランダムで初期値を変えて複数回実行し、クラスタ内距離平均のような KPI で最適なクラスの分け方をみつける

いくつかの k について上記を試し、おさまりの良さそうな k を決定する

ベストプラクティスとか書きましたが、k-means の性質が分かっていればまあ普通は上記のような方法になるんじゃないの。

デモ

k-means クラスタリングのデモ
k-means 系クラスタリング可視化ツール
派生版
K-means 法を D3.js でビジュアライズしてみた
** ステップ単位でポチポチ動かしていくならこちら

k-means 派生系手法

k-means++

初期値の適切な設定プラスアルファな手法。

まず、kmeans++の前研究として、「KKZ」という初期クラスタ中心生成手法があるらしいです。

一見これで初期化問題は万事解決に思えたのですが、文献によると外れ値がある場合に良くないらしい。そこで提案されたのがkmeans++というわけです

結論から言うとkmeans++では次のクラスタ中心を確率的に選びます。
すでにあるクラスタ中心との最短距離が大きいデータが次のクラスタ中心により選ばれやすくなるようにするのですが、確率的に選ぶことで必ずしも最大のものが選ばれなくなります。すると、外れ値問題にも対応できるというわけです。

k-means++のデモ

付随トピック

評価尺度

クラスタリング結果の評価の尺度基準

クラスタリング結果の定量評価尺度について記述されている記事。

クラスタ内距離二乗和、Pseudo F、CCC （Cubic Clustering Criterion）、Dunn’s Index、DB's Index、Pseudo T-squareなど。

クラスタリングの注意点

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

最も重要な点は，クラスタリングは探索的 (exploratory) なデータ解析手法であって，分割は必ず何らかの主観や視点に基づいているということです．よって，クラスタリングした結果は，データの要約などの知見を得るために用い，客観的な証拠として用いてはなりません．

次元の呪い

#02 位置と集団を見抜く / 4. クラスタ生成の統計アルゴリズム | Antecanis

あまりに次元の数が多くなってくると、人間の直感では把握しきれない事態が生じます。そこで問題になることがあるのが、多次元空間では距離の差がつきにくくなるという性質です。

100次元空間では、ほとんどの「隣接している点」が100次元のうち数十次元で中心点からずれているので、距離を計算した値の違いが小さくなってきてしまうのです。この傾向は、1,000次元、10,000次元など数が増えれば増えるほど顕著になってきてしまいます。

この問題を解決するためには、もともと100次元だった情報を、より少ない次元の情報に集約する手法が用いられます。主成分分析(Principal Component Analysis; PCA)を使えば、100個の軸の情報を合成して、なるべく多くの情報を維持して10個や20個の軸に再編することができます。このプロセスを次元削減(dimension reduction)と呼びます。

PCA、FA などについては別途。

階層型、非階層型の比較

#02 位置と集団を見抜く / 4. クラスタ生成の統計アルゴリズム | Antecanis

階層型 < 非階層型

「階層的クラスタリング」では、一度の繰り返しに必要な計算量は、全サンプルのペアの間の距離の比較を計算しますから、サンプル数の二乗に比例します。
「k-meansクラスタリング」では、一度の繰り返しに必要な計算量は、サンプル数の一乗に比例します。

さらに、数百万サンプルを取り扱う場合、「k-means」であれば、まずは数千サンプルで繰り返し計算を行って「クラスタ中心点」を定義したうえで、「クラスタ中心点」は固定された状態で残りのサンプルはクラスタの割り当てだけを行うこともできます。数百万人～数千万人を対象としたone-to-oneマーケティングでのクラスタの適用は、「k-means」アルゴリズムの効率性がなければほとんど不可能です。

階層型 > 非階層型

逆に、「階層的クラスタリング」が有意な点を挙げましょう、まずは、「一意性」。

これは、「k-meansクラスタリング」の代表的な欠点の一つです。最初に乱数を使って「種」を生成していますから、同じデータに基づいてもう一度行った場合、多くの場合には全く同じクラスタにはなりません。

それから、「階層性」。

「k-meansクラスタリング」では、k（クラスタ数）=5でのクラスタとk=15でのクラスタを生成した時、k=15でのあるクラスタはk=5でのクラスタに属する、という関係は作られません。