« 読了：Hanley & Lippman-Hand (1983) 調べたい事柄の発生率が0で困っているあなたのための「ルール・オブ・スリー」 | メイン | 読了：赤穂(2013) 正準相関分析入門 »
2018年5月 5日 (土)
Jain, A.K., Murty, M.N., Flynn, P.J. (1999) Data Clustering: A Review. ACM Computing Surveys, 31(3), 264-323.
クラスタリングについてのレビュー論文。Google scholar上の被引用件数が14000件超というすごい奴である。勉強のために読んだ。20年近く前の論文を、なにをいまさらという気もするけれど...
1. イントロダクション
1.1 モチベーション
探索的データ分析であれ検証的データ分析であれ、その手続きにおいて鍵となる要素のひとつにグルーピングがある。パターンの集まりを類似性に基づくクラスタへと組織化することをクラスタ分析という。判別分析(教師つき分類)とは異なり、与えられたパターンにはラベルがついていない(教師なし分類)。いいかえれば、カテゴリのラベルはデータ駆動的である。
本論文ではクラスタ分析におけるコア概念と技法をサーベイする。統計学・決定理論にルーツを持つ分野を中心とするが、機械学習などのコミュニティに関しても言及する。
1.2 クラスタリング課題の構成要素
ふつう、クラスタ分析は次の段階からなる：
- パターンの表現。3章で扱う。
- 近接性の定義。4章で扱う。
- クラスタリング。5章で扱う。
- (必要ならば)データ抽象化。たとえば、クラスタについての記述とか。
- (必要ならば)出力の評価。ふたつにわかれる。
- cluster tendencyの分析。そもそもクラスタ分析していいことがあるのかどうかを調べる。研究分野としてあまり活発でないので本論文では割愛。
- cluster validityの分析。得られたクラスタが偶然の産物だったりアルゴリズムのアーティファクトだったりしないかを調べる。(1)外的評価(アプリオリに与えられた構造を復元できるか)、(2)内的評価(クラスタがデータに対して内在的に適切か)、(3)相対的テスト(2つの構造を比べてどちらが良いか)、に分けられる。
1.3 ユーザのジレンマと熟達の役割
手元の問題に適したアルゴリズムをどうやって選ぶか。Dubes & Jain (1976)はFisher & Van Ness (1971)が定義した許容性基準によってアルゴリズムを比較している。そこでの許容性基準のベースにあるのは、(1)クラスタの形成方法、(2)データの構造、データの構造に影響しない変化への敏感性、である。でも、「データは規準化すべきでしょうか」「どんな類似性指標がどんな状況で適切でしょうか」といった問いには答えてくれない。[←ああなるほど、アルゴリズムのadmissibilityの比較だけでは役に立たんということか]
多次元データセットにおける構造をいつでも明らかにしてくれるという便利な方法はない。ユーザは個々の手法について十分に理解するだけでなく、データ収集過程の詳細についての知識と、ある程度の領域知識を持たねばならない。
データソースに対する適切な制約もクラスタリング手続きの一部である。たとえばmixture resolvingがそうだ。データが未知の数の確率密度の混合から抽出されていると仮定するせいで、混合要素の数と各要素のパラメータを推測することがクラスタリング問題となる。
1.4 歴史(略)
1.5 本論文の構成(略)
2. 定義と表記
あるパターン(特徴ベクトル、観察事例、データ)を$\mathbf{x}$とする。その要素$x_i$を特徴(属性)と呼ぶ。パターンの次元数を$d$とする。
パターン集合を$\mathcal{X} = \{\mathbf{x}_1, \ldots, \mathbf{x}_n\}$とする。通常は$n \times d$行列である。
パターン生成過程を支配する状態ををクラスと呼ぶ。クラスタリングとは、パターンをグルーピングして、異なるパターン生成過程を反映するクラスを手に入れようとすることである。
パターン集合$\mathcal{X}$にラベル$\{l_1, \ldots, l_n\}$を付与することをハード・クラスタリングという。ラベルの種類数(クラスタの数)を$k$とする。
パターン$\mathbf{x}_i$に、それがクラスタ$j$に属する程度$f_{ij}$を付与することをファジー・クラスタリングという。
パターンの類似性を定量化するのに用いる、特徴空間におけるメトリック(ないし準メトリック)を距離指標という。
3. パターン表現、特徴選択、特徴抽出
[良いパターン表現がいかに大事か、という説明が続いて...]
特徴は、量的(連続, 離散, 間隔)、質的(名義, 順序)にわけられる。特徴が木として構造化されている場合もある。
特徴選択は大事。本質的にアドホックで試行錯誤を要する。
PCAなどで特徴抽出することもある。
[この節、期待してたんだけど、ごく短い。がっくり。まあそういう主旨のレビュー論文ではないのだろう]
4. 類似性指標
連続的特徴の場合、一番一般的なメトリックはユークリッド距離である。
$d_2(\mathbf{x}_i, \mathbf{x}_j) = (\sum_k (x_{ik}-x_{jk})^2)^{1/2} = || \mathbf{x}_i - \mathbf{x}_j||_2$
一般化するとミンコフスキー距離。
$d_p(\mathbf{x}_i, \mathbf{x}_j) = (\sum_k (x_{ik}-x_{jk})^p)^{1/p} = || \mathbf{x}_i - \mathbf{x}_j||_p$
良い点：(1)直感的にわかりやすい。(2)「コンパクト」ないし「よく分離されている」クラスならうまく機能する。
悪い点：(1)スケールが大きい特徴が支配的になる(なので、ふつうは事前に規準化する)。(2)特徴間に線形相関があると歪む。そういうときは正規化マハラノビス距離
$d_M(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i - \mathbf{x}_j) \Sigma^{-1} (\mathbf{x}_i - \mathbf{x}_j)^T$
を使うこともある。$\Sigma$は既知の共分散行列または標本共分散行列。これは、各クラスの条件付き密度が単峰で、多次元空間における広がりで特徴づけられるという仮定(つまり多変量正規だという仮定)に基づいている。Mao & Jain (1996 IEEE Trans.Neur.Net.)をみよ。ほかにHausdorff距離というのを使うという提案もある。 Huttenlocker, et al. (1993 IEEE Trans.PatternAnal.Mach.Intell.)をみよ。
クラスタリングアルゴリズムはふつうパターン集合を使い、パターン間の距離を求めるのだが、最初から距離行列を使うアルゴリズムもある。
連続量でない特徴から距離を求めるというのは厄介な問題である。Wilson & Martinez (1997 J.Artif.Intell.Res.), Ichino & Yaguchi (1994 IEEE Trans.PatternAnal.Mach.Intell.)をみよ。
パターンを文字列で表現するというのもある(syntactic clusteringという)。統計的手法に比べるとすべての面で劣っているといわれているので、本稿では割愛。パターンを木構造で表すというのもある。
近隣のデータ点(文脈)の効果を考慮した距離指標もある。たとえば相互近隣距離(MND)。データ点$i$に関して$j$が持っている近隣数を$NN( \mathbf{x}_i, \mathbf{x}_j)$とする。[←よくわからないのだが、$j$からみて$i$より近い点の数、ってことかな？] で、
$MND(\mathbf{x}_i, \mathbf{x}_j) NN( \mathbf{x}_i, \mathbf{x}_j ) + NN(\mathbf{x}_j, \mathbf{x}_i)$
この距離は三角不等性を満たさないのでメトリックでないんだけど、クラスタリングでは良く使われている。このように、距離・類似性は必ずしもメトリックでない。
特徴が十分にたくさんあれば、いかなるふたつのパターンであっても類似性は同程度である。類似性に差をつけるためにはなんらかの付加的な領域情報が必要になる。[ここでconceptual clusteringの例を紹介。3つの事例があって、ユークリッド距離では同程度なんだけど、うちふたつは同一のカテゴリに属しているようにみえて...という話。Michalski & Stepp (1983) というのが引用されているのだけれど、おそらくMichalski, Stepp, & Diday (1983 IEEE Trans. Pattern Anal. Mach. Intell.) の誤りだろう]
5. クラスタリング技法
クラスタリングはとりあえず次のように分類できる。
- 階層(Hierarchical) ... 単一リンク、完全リンク
- 分割(Partitional) ... Square Error(k-meansはここにはいる), Graph Theoretic, Mixture Resolving(EMアルゴリズムがここにはいる)、Mode Seeking
といっても、ほかにもたくさんの分類がありうる。
- agglomerative vs divisive. つまり、くっつけていくか、わけていくか。これはアルゴリズムに関わる分類。
- monothetic vs. polythetic. たいていのアルゴリズムはすべての特徴を同時に使って距離を求めるが(polythetic)、特徴をひとつづつ使って分けていくアルゴリズムもある(monothetic)。
- hard vs. fuzzy.
- deterministic vs. stochastic. これは主に二乗誤差を最適化するpartitionalアプローチの話で、その最適化を決定論的に決めるか、ランダムサーチを通じて決めるか。
- incremental vs. non-incremental. 近年のデータ増大に伴って生まれてきた観点。
5.1 階層クラスタリング・アルゴリズム
[基本的な考え方と、デンドログラムについての説明があって...]
たいていの階層アルゴリズムは、{単一リンク、完全リンク、最小分散}の変形である。[←書いてないけど、Ward法は最小分散アルゴリズムに分類されるのであろう]
一番有名なのは、クラスタ間の距離を、それぞれ1個ずつ事例を出してその距離を調べた時の最小値(単一リンク)ないし最大値(完全リンク)とするやりかた。単一リンクだとchainingしやすい。完全リンクはコンパクトなクラスタになりやすい。実務的にもふつう完全リンクのほうが優れている。
階層アルゴリズムは分割(Partitional)アルゴリズムに比べて使い勝手がよい面がある。たとえばk-meansはデータセットが等方的(isotropic)なクラスタを含んでいないとうまくいかない[←なるほどー]。いっぽう、アルゴリズムは階層アルゴリズムのほうが複雑。両者のハイブリッド案もある。
なお、ここまでの話は全部hierarchicalかつagglomerativeだったけど、hierarchicalかつdivisiveなアルゴリズムもある。
5.2 分割アルゴリズム
この方法の問題点は、クラスタ数を決めなきゃいけないという点。Dubes(1987, Pattern Recogn.)を参考にせよ。
この方法はふつう、なんらかの関数を最適化するクラスタをつくるわけなんだけど、網羅的に探すのは大変なので、初期値を変えながら複数回繰り返し、最良の奴を選ぶことが多い。
5.2.1 二乗誤差アルゴリズム
一番よく使われていて、直感的にもわかりやすい。二乗誤差とは、クラスタ$j$に属する$i$番目のパターンを$x_i^{(j)}$, クラスタ$j$の重心を$c_j$として、
$\sum_j \sum_i || x_i^{(j)} - c_j ||^2$
のこと。
もっとも良く使われているのがk-meansアルゴリズム。問題点は、初期値に対して敏感で、局所最小解に落ちちゃうかもしれない点。[図で説明している。親切...]
k-meansのバリエーションはたくさんある。(1)初期値選択を工夫する。(2)重心の距離が閾値を下回る2クラスタを併合する。例としてISODATAアルゴリズムがある。(3)二乗誤差以外の基準関数を併用する。例としてdynamic clusteringというのがある。
5.2.2 グラフ理論的クラスタリング
いちばんよく知られているのは、データの最小全域木(minimal spanning tree; MST)をつくり、一番長いエッジを消すという手法。
階層クラスタリングはグラフ理論の観点からみることもできて...[略]
非階層、overlapありという手法でドロネーグラフ(Delaunay graph; DG)というのもある。ボロノイ近隣の点をつなぐ。
5.3 mixture-resolvingアルゴリズムとmode-seekingアルゴリズム
mixture-resolvingアルゴリズムは、パターンが複数の分布から抽出されたものだと仮定し、それぞれの分布のパラメータを推定するアルゴリズム。ふつう分布はガウシアンだと仮定される。伝統的にはパラメータを最尤推定する。最近ではEMアルゴリズムを用いることが多い。[←とこのように、有限混合モデルについては意外にそっけない説明である。機械学習系の論文だからかしらん？]
密度ベースのクラスタリングのノンパラメトリックな手法も提案されている。ノンパラ密度推定の方法にParzenウィンドウというのがあるけど、あれと同じようにして、入力パターンセットの多次元ヒストグラムのなかで、カウント数が大きくなるビンを探す。[←ああそうか、これってmodeを探索しているわけか...]
ほかに、ノンパラ密度推定に基づく距離を使った階層手法・分割手法もある。
5.4 最近隣クラスタリング
最近隣距離を使ったクラスタリングもある(Lu & Fu, 1978 IEEE Trans. Syst. Man Cybern.)。距離が閾値を下回る最近隣ペアを探しては、ラベルを一方から他方にコピーするというのを繰り返す。[←ちょ、ちょっと待って、最初のラベルはどうすんの？]
5.5 fuzzyクラスタリング
対象を$N$個、クラスタを$K$個とする。まず$N \times K$の初期メンバーシップ行列$U$をつくる。要素$u_{ij}$は対象$x_i$のクラスタ$c_j$へのメンバーシップを表していて、ふつう$u_{ij} \in [0,1]$。
で、$U$からファジー基準関数の値を求める。たとえば
$\sum_i \sum_k u_{ij} ||x_i - c_k||^2$
というような関数。で、この基準関数が小さくなるように$U$を少しずつ変えていく。
もっともよく用いられているのはfuzzy c-meanアルゴリズム(FCM)。他にもいろいろある。
5.6 クラスタの表現
クラスタリングの最終目的が、データの分割ではなく、むしろデータの抽象化だということもある。クラスタの表現という問題はこれまであまり研究されていない。表現のスキーマとして以下が挙げられる。
- クラスタの重心とか、クラスタのなかで離れている点の集合とかで示す。
- 分類木のノードとして示す。
- 論理表現の結合として示す。
意思決定におけるデータ抽象化は重要である。なぜなら：
- 人間にとってわかりやすくなるから。
- さらなるデータ分析が便利になるから。たとえば、データが大きい時、まずk-meansでたくさんのクラスタにわけ、それらの重心についてやおら単一リンクの階層クラスタリングをやるとか。
- 意思決定の効率が良くなるから。たとえば文書検索とか。
5.7 人工ニューラルネットワークによるクラスタリング
以下の特徴がある：
- 量的特徴しか扱えない
- 並列分散処理アーキテクチャ
- ウェイトを適応的に学習し、パターンを基準化し特徴を選択する。
良く使われているのは、Kohonenの学習ベクトル量子化(LVQ)、自己組織化マップ(SOM)、適応的レゾナンス理論モデル(ART)。これらはアーキテクチャとしては単層。入力ノードと出力ノードのあいだのウェイトを更新する手続きは、実は古典的なクラスタリングとよく似ている。たとえば、LVQはk-meansと深いつながりがある。
SOMは2次元のマップを使うので直感的にわかりやすいけど、初期ウェイトをしくじると局所解に落ちるし、収束に関わるパラメータがいっぱいあって、同じ入力なのに反復回数によっては異なる出力となりうる(つまり安定性がない)。学習率を下げていけば安定性が生じるけどこんどは可塑性がなくなる。
ARTは安定的かつ可塑的といわれているんだけど、パターン入力の順序に依存する。また、クラスタの数とサイズがビジランス閾値と呼ばれる定数に依存する。
SOMもARTも超球になっているクラスタの検出にしか向いていない。これに対して、2層のネットワークで楕円もみつけようという提案がある。
5.8 進化アプローチによるクラスタリング
まず、クラスタリングの解(データの分割)のランダムな母集団をつくる。で、それぞれの解について適合度を求める(通常は二乗誤差に反比例する値)。で、それぞれの解を染色体と見立てて、selection, recombination, mutation操作を行い、第二世代の母集団をつくる。これを繰り返す。
有名な手法として、遺伝的アルゴリズム(GA)、進化方略(ES)、進化プログラミング(EP)がある。GAが一番良く使われている。GAでは解は二値文字列になる。recombination操作にはいろいろあるけど、交差が一番良く使われている。selection, recombination, mutationのいずれも、適合度に基づいて確率的に行われる。
ES, EPとGAとのちがいは解の表現と操作である(EPはrecombination操作を行わない)。要するにいずれも二乗誤差を最小化しているわけである。
たとえばk-meansの場合、「次の反復」で得られる解は今ある解の近傍である。fuzzyクラスタリングもANNもそうだ。こういうのを局所化探索と呼ぶことができる。これに対して、GAでは交差や変異の操作によってとんでもない解が得られるわけで、大域化探索であるといえる。
進化的アプローチによるクラスタリングにはいろいろ拡張案があって...[省略]
GAの問題点としては、母集団サイズや交差・変異確率といったいろいろなパラメータに対する敏感性の高さが挙げられる。問題特有的なヒューリスティクスを組み込んだほうがよいという意見もある。
クラスタリングを最適な分割を見つけるという課題ではなくて、最適な重心の位置を決めるという最適化問題として捉えるなら、ESやEPが使いやすい(GAとちがって、重心を実数ベクトルとして直接符号化できるから)。
5.9 検索ベースのアプローチ
検索テクニックを使って最適な分割を検索するというアプローチ。ここでいう検索は決定論的検索と確率的検索に分かれる。
決定論的検索としては、Branch-and-bound法で最適な分割を探すというアプローチがある。計算が大変。また、決定論的アニーリングを使うという手もある。大域最適解が保証されないというのが欠点。[←なるほどね... データ生成メカニズムは一切問わず、事例にクラスタ番号を付与する整数計画として解いちゃうということだろうか]
確率的アプローチとしては、シミュレーテッド・アニーリング(SA)とか、Tabuサーチとかがある。[説明略]
5.10 手法の比較
各手法の特徴を概観すると、
- たいていの手法は二乗誤差を基準関数としている。
- クラスタはたいてい超球となる。
- 進化アプローチを除き、局所化探索である。
- ANNとGAは本質的に並列的である。
- 進化アプローチを除き、ある時点での解は1個である。
- ANN, GA, SA, Tabuサーチは学習パラメータの選択に敏感である。また、領域知識を明示的に扱うことができない。
- 進化アプローチは基準関数が非連続的でも大丈夫。
実証的な比較研究はいろいろあって...[めんどくさいのでパス]...
要約すると、大データ向きなのはk-meansとKohonen net、あとは小データ用。どの手法でも領域知識をうまく使うことが大事。基準関数を使うアプローチだとクラスタは超球になりやすいので、それが困る場合は、階層アルゴリズムのほうがいいかも。
5.11 領域に基づく制約をクラスタリングに統合する
そもそもクラスタリングは本質的に主観的な課題である。だから主観性をうまく組み込みたい。
どんなクラスタリング・アルゴリズムであっても、なんらかのタイプの知識をつかっている。ただそれが暗黙的か明示的かがちがうだけだ。[←おおお、名文句だ...」
パターンを表現するスキーマの選択、類似性指標の選択、グルーピングのスキーマの選択、ANN, GA, TS, SAにおけるパラメータの選択、いずれにおいても、知識が暗黙的に影響している。もっと明示的に知識を使うこともできる。知識を活かした特徴選択とか。
領域知識の組み込みはアドホックなものなので、事例と先行研究を挙げることしかできない。こういうのに関心がある人は機械学習系の学術誌を読みなさい。
- Michalski & Stepp (1983): 類似性計算のフェイズで概念的知識を明示的に使用した例。[説明が短すぎてよくわからん...パス]
- Srivastava & Murty (1990): パターン表現のフェイズで知識を使っている例。[これもよくわからん]
- Shekar et al.(1987): モノの機能についての知識を使ってより直観的なクラスタ記述を作った例。[全然わからん...参ったな]
実務的には、次の３つの問題が重要。(1)領域知識の表現、利用可能性、完全性。(2)知識を用いた推論の構築。(3)知識の変化への適応。
5.12 巨大なデータセットのクラスタリング
大データに対して使われているのはk-meansとKohonen netである。超球じゃないクラスタが作れるという点では階層アルゴリズムが便利なんだけど、時間とメモリが大変になる。
大データ向き手法もいろいろ開発されている。CLARANS, BIRCHが有名。[いろいろ説明が書いてあるけどパス]
データが大きいとメモリにデータが載りきらなくなる。この問題に対する対処策として以下が挙げられる。
- データをサブセットにわけ、それぞれについてクラスタリングして、あとで結合する。[説明省略]
- 逐次的クラスタリング。メモリにはクラスタ表現しか置かない。leader clustering, shortest spanning path, cobwebなどがある。いずれもパターンの学習順序に依存する。
- 並列処理。
6. 応用
[画像分割、物体と文字の認知、書籍を検索するシステムというような状況検索、原油を掘るというようなデータマイニングでの活用例、を消化。内容も古いと思うし、気力も尽きたのでパス]
7. 要約 [略]
... やれやれ、疲れた。正直、途中から「これ20年前の話だよな...」という思いにかき乱されて、モチベーションが落ちてしまったんだけど、勉強になりましたです。
グルーピングの手続きについて、この論文ではまず大きく階層的手法とそうでない手法という観点から分けていて、前者のほうが使い勝手が良い(versatile)だと何箇所かで述べている。クラスタの形状についての仮定がない分柔軟だ、という意味なのだろうと思う。うーん、それって良し悪しだと思うんですけど、どうなんすかね。
admissibilityについての議論が短いところも、ちょっと意外であった。クラスタリング手法のレビューなんだから、当然Fisherのadmissibility基準で比較するんだろうと思ったのである。著者らが説明していたように、アルゴリズムのadmissibilityだけで形式的に語れる範囲はそう広くない、ってことなんでしょうね。
論文：データ解析(2018-) - 読了：Jain, Murty, Flynn (1999) クラスタリング手法レビュー