クラスタリングとは

クラスタリング (clustering) とは，分類対象の集合を，内的結合 (internal cohesion) と外的分離 (external isolation) が達成されるような部分集合に分割すること [Everitt 93, 大橋 85] です．統計解析や多変量解析の分野ではクラスター分析 (cluster analysis) とも呼ばれ，基本的なデータ解析手法としてデータマイニングでも頻繁に利用されています．

分割後の各部分集合はクラスタと呼ばれます．分割の方法にも幾つかの種類があり，全ての分類対象がちょうど一つだけのクラスタの要素となる場合(ハードなもしくは，クリスプなクラスタといいます)や，逆に一つのクラスタが複数のクラスタに同時に部分的に所属する場合(ソフト，または，ファジィなクラスタといいます)があります．ここでは前者のハードな場合のクラスタリングについて述べます．

---

以下の文章は，[神嶌 03a] からの抜粋に加筆したものです．さらに詳細な事柄については，『解説・講義資料』ページの資料をご覧下さい．

基本的なクラスタリング手法

クラスタリング手法は大きく，最短距離法などの階層的手法 (hierarchical method) と，\(k\)-means法などの非階層的手法 (non-hierarchical method) に分けられますが，これらの基本的手法を紹介します．

階層的手法

階層的手法は，さらに分割型 (divisive) と凝集型 (agglomerative) に分けられますが，ここでは後者のみを扱います．

この手法は，\(N\) 個の対象からなるデータが与えられたとき，1個の対象だけを含む \(N\) 個のクラスタがある初期状態を，まず作ります．この状態から始めて，対象 \(\mathbf{x}_1\) と \(\mathbf{x}_2\) の間の距離 \(d(\mathbf{x}_1,\mathbf{x}_2)\) (非類似度)からクラスタ間の距離 \(d(C_1,C_2)\) を計算し，最もこの距離の近い二つのクラスタを逐次的に併合します．そして，この併合を，全ての対象が一つのクラスタに併合されるまで繰り返すことで階層構造を獲得します．この階層構造は図4(b)のようなデンドログラムによって表示されます．デンドログラムとは，各終端ノードが各対象を表し，併合されてできたクラスタを非終端ノードで表した二分木です．非終端ノードの横軸は，併合されたときのクラスタ間の距離を表します．クラスタ \(C_1\) と \(C_2\) の距離関数 \(d(C_1,C_2)\) の違いにより以下のような手法があります．

最短距離法 (nearest neighbor method) または 単連結法 (single linkage method)

\[\large d(C_1,C_2)=\min_{\mathbf{x}_1\in C_1,\mathbf{x}_2\in C_2}d(\mathbf{x}_1,\mathbf{x}_2)\]

最長距離法 (furthest neighbor method) または 完全連結法 (complete linkage method)

\[\large d(C_1,C_2)=\max_{\mathbf{x}_1\in C_1,\mathbf{x}_2\in C_2}d(\mathbf{x}_1,\mathbf{x}_2)\]

群平均法 (group average method)

\[\large d(C_1,C_2)=\frac{1}{|C_1||C_2|}\sum_{\mathbf{x}_1\in C_1}\sum_{\mathbf{x}_2\in C_2}d(\mathbf{x}_1,\mathbf{x}_2)\]

ウォード法 (Ward’s method)

\[\large d(C_1,C_2)=\mathrm{E}(C_1 \cup C_2) – \mathrm{E}(C_1) – \mathrm{E}(C_2)\]

ただし，\(\mathrm{E}(C_i)=\sum_{\mathbf{x}\in C_i} (d(\mathbf{x},\mathbf{c}_i))^2\) で \(\mathbf{c}_i\) はクラスタ \(C_i\) のセントロイド \(\sum_{\mathbf{x}\in C_i}\mathbf{x}/{|C_i|}\)．

Ward 法は，各対象から，その対象を含むクラスタのセントロイドまでの距離の二乗の総和を最小化する．

なお，最短距離法，最長距離法，及び，群平均法は任意の対象間の距離 \(d(\mathbf{x}_i,\mathbf{x}_j)\) が与えられている場合に適用でき，クラスタを併合した後の距離の更新は Lance-Williamsの更新式 [Lance 67] により定数時間で可能です．もし，対象が数値ベクトルで記述されている場合は，ベクトル間のユークリッド距離などを求めて適用します．Ward法は対象が数値ベクトルで与えられている場合には上記の式が直接適用でき，対象間の距離のみが与えられている場合では Lance-Williamsの更新式を使って距離の更新をします．

一般の場合の計算量は \(O(N^2\log N)\) ですが，Lance-Williamsの更新式で定数時間で距離の更新が可能な上記の距離更新手法には可約性 (reducibility) という性質があり，再近隣グラフの性質を活用することで \(O(N^2)\) の時間で計算可能なアルゴリズム [Murtagh 83] が知られています．なお，スカラー・並列計算機上での計算量については [Olson 95] にまとめられています．

非階層的手法

非階層的手法は，分割最適化手法の他，partitional や optimization など多くの呼び方があります．この手法は，分割の良さの評価関数を定め，その評価関数を最適にする分割を探索します．可能な分割の総数は \(N\) に対して指数的なので，実際は準最適解を求めることになります．代表的な \(k\)-means法（k平均法）は，セントロイド \(\mathbf{c}_i\) (クラスタの重心点)をクラスタの代表点とし，

\[
\large\sum_{i=1}^k\sum_{x\in C_i}(d(\mathbf{x},\mathbf{c}_i))^2
\]

の評価関数を最小化するように \(k\) 個のクラスタを分割します．最適解の探索は下記のように，対象のクラスタへの割り当てと代表点の再計算を交互に繰り返して行います．この手法は山登り法で，局所最適解しか求められないため，ランダムに初期値を変更するか，適宜互いに離れたデータ点を初期の代表点として選んで，評価関数を最小にする結果を選択するのが一般的です．

クラスタリングの注意点

上記の基本的手法は統計処理ソフト R の stats パッケージに含まれる hclust や kmeans などの関数，対話的データ分析処理ソフト Weka，プログラミング言語Pythonの scikit-learnパッケージ などの統計・データマイニングソフトウェアを利用すれば，容易に利用できます．しかし，各手法の特徴や傾向を無視したために，不適切な結果が導かれている利用例がときどきみられます．ここでは，このような問題を回避するための，主な注意点をまとめました．

クラスタリング結果の解釈

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

---

データベースから明確な目的に適合する文書を検索する場合，キーワードを用いた文書検索手法は有効です．しかし，明確な目的がなく，データベース全体の傾向を知りたい場合はどうでしょうか？ この場合，具体的なキーワードを示すことは困難なので，文書検索手法の利用は不適当です．そこで，クラスタリングによって，その要約，すなわち，データベース中の主な話題を表すカテゴリーの一覧を取出します．Cutting らは，ニューヨーク・タイムス紙 1990 年 8 月の約 5,000 件の記事のデータベースの傾向を抽出する問題にクラスタリングを用いました．話題が類似している文書をまとめたクラスタを生成した結果，以下の話題を含むクラスタが発見されました．

教育, 国内, イラク, 芸術, スポーツ, 石油, ドイツ統合, 裁判

利用者は，内容が全く不明であった新聞記事のデータベースのおおまかな内容を，これらのクラスタから知ることができるでしょう．この要約は，一つのクラスタ，例えばイラクをさらに分割して，パキスタンやアフリカといったより詳細な要約を得たり，文書検索のためのキーワードを決める目的にも利用できます．クラスタリングは，このように，未知のデータベースの内容に見当をつける目的で利用できるため探索的であるといえます．

ここで注意すべき点は，この例では8個のクラスタに記事を分類し，データベースの『正しい』要約を得ることができました．しかし，イラクと石油はどちらも湾岸戦争に関する話題なので，これらをまとめても，データベースの『正しい』要約といえます．すなわち，どちらにも，それを正当化する視点が存在します．このように，クラスタリングの結果は絶対的でも，普遍的でも，客観的でもないので，分割結果は結論を導く証拠にはなりえません．例えば，教育と国内が違うクラスタに分類されていますが，これは実社会で二つの問題に関連性が皆無であることを意味しません．クラスタリング結果の妥当性は，その分割の利用目的など，外的な知識によって判断するしかありません． 例えば，新聞記事の話題の抽出という目的であれば，国内とドイツ統合を同じクラスタに分類していれば，妥当な要約とはいえないでしょう．ですが，同じ週に起きた事件をまとめるという目的ならば，これらをまとめるのも妥当かもしれません．クラスタリングの結果は，その利用目的などに応じて，妥当性を常に検証する必要があります．

---

ただし，均一に分布するデータを分割する行為は，多くの場合で妥当ではありません．この観点での妥当性については [Dubes 79] に詳しく議論されています．また，妥当性の問題に関連するものとして，クラスタ数の決定問題があります．本来，このクラスタ数も目的に応じて利用者が決めるべきものですし，『正しい』クラスタ数ということにも上記の議論があてはまるので，利用者が分割結果を解釈できれば『正しい』クラスタ数であるといえます．ですが，視覚的に非常によく分離されたクラスタ構造が存在する条件の下での，クラスタ数の決定基準を比較した研究 [Milligan 85] などはあります．

次元の呪い

高次元空間の対象を扱う場合，その高次元性に起因した問題は「次元の呪い」と呼ばれます．クラスタリングでも次元の呪いの問題は存在し，その主な原因は次の球面集中現象 (concentration on the sphere) [石井 98] にあります．

図3 のように，ある対象を中心にした，半径がそれぞれ \(r\) と \(ar,\ (0 \lt a \lt 1)\) の \(d\) 次元超球 \(S_1\) と \(S_2\) があるとします． \(S_1\) の体積 \(V\) に対する，二つの超球の体積の差 \(\delta V\) (図のグレー部分) の比は \(\delta V/V=1-a^d\) となります．ここで，対象が均一分布しているとすると空間中に存在する対象数は体積に比例します．また，\(\delta V/V\) は \(d\) の増加にともない1に近づくことから，\(d\) が大きな場合は \(S_1\) 中の対象は，ほとんど二つの超球の隙間に存在することが分かります．これは，中心の対象から他の対象までの距離は，次元の増加に従って急速に大きくなることを意味します．すなわち，どの対象も互いに似ていないことになります．クラスタリングは，似ている対象をまとめる操作なので，有意な解を得ることができなくなります．

この次元の呪いに対する抜本的な解決法は，外的な知識によって不要と考えられる属性を排除し，次元数を小さくすることです．しかし，データの性質が不明で，どの属性が不要か判断できない場合も多いため，このような高次元データを処理する手法も研究されていますので，[神嶌 03b] の9節などをご覧下さい．

手法固有の注意点

階層的手法の注意点について述べます．数学的に優れたある種の性質をもつ最短距離法は，空間濃縮という性質のため，極めて外乱に弱く，実データではあまり良い結果は得られません．空間濃縮とは，併合されてできた新しいクラスタは，以後の併合の対象として選ばれる可能性が加速度的に増加する現象です．図4(a)のデータには，視覚的なまとまりからすれば点線で囲んだ部分に二つのクラスタ見なせる部分と，これらをつなぐ外乱と見なせる対象が存在しています．このデータに最短距離法を適用すると，図4(b) のデンドログラムが得られます．このデンドログラムを用いて，図4(b)の矢印の部分で二つのクラスタに分割すると，一方は 1 個の対象（図4(a)の▲印），もう一方はそれ以外全てを含むクラスタが生成され，直観に反した結果が得られます．また，この空間濃縮は，繋がった外乱を一つづつ併合することがあるため，チェイニング効果とも呼ばれます．この効果によって図4(b)の点線部分のような階段状構造ができますが，最短距離法の特性のために生じた構造であることが多いので注意してください．

逆に，最長距離法には，併合されてできたクラスタは，以後，併合されにくくなる空間拡散という性質があり，本来のクラスタから偶然離れてしまった対象があると，過剰に分割される傾向があります．一方，群平均法は，空間濃縮や拡散は生じません．

---

\(k\)-means法の注意点について述べます．この手法は，クラスタは超球状の形状で，クラスタ中の対象数はどれも等しいということを暗黙のうちに仮定しているので，この仮定に反する構造の抽出は困難です．文献 [Guha 98] では，図5のように三つの密な領域が存在するデータに \(k\)-means法を適用した結果を例示しています．直観に反して，クラスタ中の事例数が等しくなるように，対象数の大きな領域は三つに分割されています．クラスタの対象数に差がある場合には，\(k\)-means法の代りに確率モデルをEMアルゴリズムで解く方法（[神嶌 03a] の7節）などを検討して下さい．また，クラスタが超球形でない場合は，標準偏差で正規化したマハラノビス距離などのスケーリングの変換したり，そのような目的で開発された手法（[神嶌 03b] の10節）を利用すべきです．

\(k\)-means法は欲張り探索で局所解を求める手法であるため，初期状態によって最終結果は大きく影響されます．一般的な対処法は，初期状態をランダムに変更して複数回 \(k\)-meansを実行して幾つかの分割を獲得し，それらの分割の中で評価関数を最小にするものを選びます．また，同じクラスタにならないことが事前に予測される対象があれば，初期クラスタでそれらの対象を別のクラスタの代表点とするのもよいでしょう．対象数 \(N\) が大きく \(k\)-means法を何度も適用するのは時間がかかり過ぎる場合もあるので，有望な初期値を確率的に求める \(k\)-means++法 [Arthur 07] のような研究もあります．

---

最初に適用するクラスタリング手法は一般には以下のようにするのがよいでしょう．まず，対象が属性ベクトルで記述されている場合，計算量が \(k\)-means法は \(O(Nk)\) に対し，上記の階層的手法は \(O(N^2)\) なので，\(k\)-means法を用いる方がよいでしょう．ただし，階層構造が必要な場合には群平均法かWard 法を用います．最短距離法や最長距離法は群平均法の結果に不満な場合に試してみてもよいでしょう．もちろん，あらゆる状況で最良な手法は存在しないので，必ずこの選択が良いというわけではありません．だが，これらの手法を適用した結果からデータに関する知見を得て，その知見に基づき，[神嶌 03a, 神嶌 03b] に挙げた他の高度な手法を検討するのが良いでしょう．

参考文献

[Arthur 07]

D. Arthur and S. Vassilvitskii: \(k\)-means++: The Advantages of Careful Seeding, in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithm, pp.91-99 (2007)

[Cutting 92]

D.R.Cutting, D.R.Karger, J.O.Pedersen, and J.W.Tukey: Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections, in Proceedings of the 15th Annual ACM SIGIR Conference on Research and Development in Information Retrieval, pp.318-329 (1992)

[Dubes 79]

R.Dubes and A.K.Jain: Validity Studies in Clustering Methodologies, Pattern Recognition, Vol.11, pp.235-254 (1979)

[Everitt 93]

B.S.Everitt: Cluster Analysis, Edward Arnold, third edition (1993)

[Guha 98]

S.Guha, R.Rastogi, and K.Shim: CURE: An Efficient Clustering Algorithm for Large Databases, in Proc. of the ACM SIGMOD International Conference on Management of Data, pp.73-80 (1998)

[石井 98]

石井 健一郎, 上田 修功, 前田 英作, 村瀬 洋: わかりやすいパターン認識, オーム社 (1998)

[Lance 67]

G.N.Lance and W.T.Williams, A General Theory of Classificatory sSorting sStrategies, The Computer Journal, vol.9, pp.373-380 (1967)

[Milligan 85]

G.W.Milligan and M.C.Cooper: An Examination of Procedures for Determining The Number of Clusters in A Data Set, Psychometrika, Vol.50, No.2, pp.159-179 (1985)

[Murtagh 83]

F.Murtagh: A Survey of Recent Advances in Hierarchical Clustering Algorithms, The Computer Journal, vol.26, pp.354-359 (1983)

[大橋 85]

大橋 靖雄: 分類手法概論, 計測と制御, Vol.24, No.11, pp.999-1006 (1985)

[Olson 95]

C.F.Olson: Parallel Algorithms for Hierarchical Clustering, Parallel Computing, Vol.21, pp.1313-1325 (1995)