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

クラスタリングとは クラスタリング (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 … Continue reading クラスタリング (クラスター分析)