« 読了: Li, Song, & Gray (2004) マッチングのあるケース・コントロール・デザインの条件付きロジスティック回帰で曝露変数に欠損があったら除去すべきか0埋めしてフラグを立てるべきか | メイン | 読了: Hanson(2007) 文系の君にはわからんだろうがこれがLMSRマーケット・メーカだ »
2015年2月11日 (水)
Jain, A.K. (2010) Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 31(8), 651-666.
魅力的題名に惹かれて、MCMCが止まるまでの時間つぶしに手に取った。雑誌についてはよく知らないが、工学系でIF 1.06というのはきっとマイナー誌であろう。著者のなにかの会議での受賞記念講演をまとめたものらしい。
いくつかメモ:
- k-means法の話。
- k-means法ではふつうユークリッド距離を使う。マハラノビス距離を使うこともあるけど計算コストがかかる。ほかに、板倉-斎藤距離を使う例(音声処理で), L1距離を使う例、Bregman距離を使う例、がある由。[←知らんがな...]
- k-meansの拡張としては ISODATA, FORGY, ファジーc-meansが有名。ほかに、bisecting k-means, kd-tree, Bradleyらの巨大データへの拡張、x-means, k-medoid, カーネルk-means、がある。[←恥ずかしながら、初耳のが多い...]
- そのほかのクラスタリング手法:
- 密度が高い領域を分離するアプローチ: Jarvis-PatrickアルゴリズムとDBSCAN, 混合分布モデル, ベイジアンアプローチ(LDA, Pachinko Allocation, 無向グラフィカルモデル)。高次元に弱い。
- 下位空間クラスタリング: CLIQUE。
- グラフ理論アプローチ: minimum cut, ratio cut, normalized cut, MNCut, Ngらの方法, Laplacian Eigenmap, 決定論的焼きなましアルゴリズム, dominant sets アプローチ。
- 情報理論によるアプローチ。分割のエントロピーを最小化するアプローチ, information bottleneck法,。[←ほとんど理解できない]
- クラスタリングにおける難題:
- 特徴量をどうやって選ぶか。これはグルーピングの目的はなにかという点と密接に関連している。
- クラスタ数をどう決めるか。最小メッセージ長基準、最小記述長基準、AICやBIC、ギャップ統計量、ディリクレ過程でクラスタ数の事前分布を求める[???]、といった方法があるが、決め手はない。
- クラスタの妥当性をどうやって調べるか(仮に一様分布であっても複数のクラスタが得られちゃうわけだから)。3つの基準が挙げられる: 内的妥当性(クラスタ構造とデータの適合)、相対的妥当性(複数の構造を比べる)、外的妥当性(外的基準と比べる)。内的妥当性の指標のひとつに安定性がある。複数のサブサンプルを通じたクラスタリング解の分散のこと。
- クラスタリング手法の比較。
- アルゴリズムを結果の観点からクラスタリングするという試みもあって、やはりアプローチが近いと結果も似てくる。
- 理論的観点からは「手法」と「アルゴリズム」を分けて考える必要がある。たとえば「二乗誤差を最小化する」というのが手法、k-meansというのがアルゴリズム。ちがう手法が結局は等価、ということもある。
- まあとにかく、最良のアルゴリズムなんてない。
- 最近のトレンド:
- アンサンブル。k-meansをいっぱいやって結果を集約するとか。
- 準教師つきクラスタリング。must-linkとかcannot-linkとかを指定する、一部のデータにラベルをつける、などなど。例としてBoostClusterというのがある。
- 大データのクラスタリング。[いろいろ紹介してるけど省略]
- 多元クラスタリング。行列の行と列を同時にクラスタリングするとか。
- heterogeneousなデータ。グラフとして表現されているデータとか、動的データとか...
先生曰く、「たいていの応用場面では、本当に大事なのは最良のクラスタリング・アルゴリズムを選ぶことではない。むしろ、データの背後にあるクラスタリング構造を同定するための、適切な特徴抽出手法を選ぶことのほうがより重要である」とのこと。へへーっ(平伏)。
論文：データ解析(2015-) - 読了： Jain (2010) クラスタリング50年史