|
クラスタリング(clustering)とは，分類対象の集合を，内的結合(internal cohesion)と外的分離(external isolation)が達成されるような部分集合に分割すること [Everitt 93] [大橋 85] です．統計解析や多変量解析の分野ではクラスター分析(cluster analysis)とも呼ばれ，基本的なデータ解析手法としてデータマイニングでも頻繁に利用されています．
分割後の各部分集合はクラスタと呼ばれます．分割の方法にも幾つかの種類があり，全ての分類対象がちょうど一つだけのクラスタの要素となる場合(ハード，または，クリスプなクラスタといいます)や，逆に一つのクラスタが複数のクラスタに同時に部分的に所属する場合(ソフト，または，ファジィなクラスタといいます)があります．ここでは前者のハードな場合のクラスタリングについて述べます．
以下の文章は，文献034 から，クラスタリングについての基本的な事柄を抜粋したものです．クラスタリングの詳細については次の文献をご覧下さい．
私が管理している機械学習関係Wiki「朱鷺の杜Wiki」内の「クラスタリング」の項目にもいろいろな情報をまとめています．
クラスタリング手法は大きく，最短距離法などの階層的手法(hierarchical)と，k-means法などの分割最適化手法(partitioning-optimization)に分けられますが，これらの基本的手法を紹介します．
階層的手法は，さらに分枝型(divisive)と凝集型(agglomerative)に分けられますが，ここでは後者のみを扱います．
この手法は，N 個の対象からなるデータが与えられたとき，1個の対象だけを含む N 個のクラスタがある初期状態を，まず作ります．この状態から始めて，対象 x1 と x2 の間の距離 D(x1,x2) (非類似度)からクラスタ間の距離 D(C1,C2) を計算し，最もこの距離の近い二つのクラスタを逐次的に併合します．そして，この併合を，全ての対象が一つのクラスタに併合されるまで繰り返すことで階層構造を獲得します．この階層構造は図3(b)のようなデンドログラムによって表示されます．デンドログラムとは，各終端ノードが各対象を表し，併合されてできたクラスタを非終端ノードで表した二分木です．非終端ノードの横軸は，併合されたときのクラスタ間の距離を表します． クラスタ C1と C2 の距離関数 D(C1,C2) の違いにより以下のような手法があります．
ただし 
Ward 法は，各対象から，その対象を含むクラスタのセントロイドまでの距離の二乗の総和を最小化する．
なお，最短距離法，最長距離法，及び，群平均法は任意の対象間の距離 D(xi,xj) が与えられている場合に適用できます．もし，対象が数値ベクトルで記述されている場合は，ベクトル間のユークリッド距離などを求めて適用します．Ward 法は対象が数値ベクトルで与えられている場合にのみ適用できます．
分割最適化手法は，非階層的手法の他，partitional や optimization など多くの呼び方があります．この手法は，分割の良さの評価関数を定め，その評価関数を最適にする分割を探索します．可能な分割の総数は N に対して指数的なので，実際は準最適解を求めることになります．代表的な k-means法 (k平均法)は，セントロイド ci (クラスタの重心点)をクラスタの代表点とし，
の評価関数を最小化するように k 個のクラスタを分割します．最適解の探索は下記のように，対象のクラスタへの割り当てと代表点の再計算を交互に繰り返して行います．この手法は山登り法で，局所最適解しか求められないため，ランダムに初期値を変更して，評価関数を最小にする結果を選択するのが一般的です．
|
上記の基本的手法は Weka や R などのソフトウェアを利用して，容易に適用できます．しかし，各手法の特徴や傾向を無視したために，不適切な結果が導かれている利用例がときどきみられます．ここでは，このような問題を回避するための，主な注意点をまとめました．
最も重要な点は，クラスタリングは探索的(exploratory)なデータ解析手法であって，分割は必ず何らかの主観や視点に基づいているということです．よって，クラスタリングした結果は，データの要約などの知見を得るために用い，客観的な証拠として用いてはなりません．この「データの要約」を直観的に理解するのに役立つように，Cutting らの研究 [Cutting 92] を紹介します．
データベースから明確な目的に適合する文書を検索する場合，キーワードを用いた文書検索手法は有効です． しかし，明確な目的がなく，データベース全体の傾向を知りたい場合はどうでしょうか？ この場合，具体的なキーワードを示すことは困難なので，文書検索手法の利用は不適当です．そこで，クラスタリングによって，その要約，すなわち，データベース中の主な話題を表すカテゴリーの一覧を取出します．Cutting らは，ニューヨーク・タイムス紙 1990 年 8 月の約 5,000 件の記事のデータベースの傾向を抽出する問題にクラスタリングを用いました．話題が類似している文書をまとめたクラスタを生成した結果，以下の話題を含むクラスタが発見されました．
教育, 国内, イラク, 芸術, スポーツ, 石油, ドイツ統合, 裁判
利用者は，内容が全く不明であった新聞記事のデータベースのおおまかな内容を，これらのクラスタから知ることができるでしょう．この要約は，一つのクラスタ，例えばイラクをさらに分割して，パキスタンやアフリカといったより詳細な要約を得たり，文書検索のためのキーワードを決める目的にも利用できます．クラスタリングは，このように，未知のデータベースの内容に見当をつける目的で利用できるため探索的であるといえます．
ここで注意すべき点は，この例では 8 個のクラスタに記事を分類し，データベースの「正しい」要約を得ることができました．しかし，イラクと石油はどちらも湾岸戦争に関する話題なので，これらをまとめても，データベースの「正しい」要約といえます．すなわち，どちらにも，それを正当化する視点が存在します．このように，クラスタリングの結果は絶対的でも，普遍的でも，客観的でもないので，分割結果は結論を導く証拠にはなりえません．例えば，教育と国内が違うクラスタに分類されていますが，これは実社会で二つの問題に関連性が皆無であることを意味しません．クラスタリング結果の妥当性は，その分割の利用目的など，外的な知識によ っ て判断するしかありません． 例えば，新聞記事の話題の抽出という目的であれば，国内とドイツ統合を同じクラスタに分類していれば，妥当な要約とはいえないでしょう．ですが，同じ週に起きた事件をまとめるという目的ならば，これらをまとめるのも妥当かもしれません．クラスタリングの結果は，その利用目的などに応じて，妥当性を常に検証する必要があります．
ただし，均一に分布するデータを分割する行為は，多くの場合で妥当ではありません．この観点での妥当性については [Dubes 79] に詳しく議論されています．また，妥当性の問題に関連するものとして，クラスタ数の決定問題があります．本来，このクラスタ数も目的に応じて利用者が決めるべきものですし，「正しい」クラスタ数ということにも上記の議論があてはまるので，利用者が分割結果を解釈できれば「正しい」クラスタ数であるといえます．ですが，視覚的に非常によく分離されたクラスタ構造が存在する条件の下での，クラスタ数の決定基準を比較した研究 [Milligan 85] などはあります．
高次元空間の対象を扱う場合，その高次元性に起因した問題は「次元の呪い」と呼ばれます．クラスタリングでも次元の呪いの問題は存在し，その主な原因は次の球面集中現象 [石井 98] にあります．
 |
図2 のように，ある対象を中心にした，半径がそれぞれ r と ar (0 < a < 1) の d 次元超球 S1 と S2 があるとします． S1 の体積 V に対する，二つの超球の体積の差 δV (図のグレー部分) の比は δV/V=1-ad となります．ここで，対象が均一分布しているとすると空間中に存在する対象数は体積に比例します．また，δV/V は d の増加にともない 1 に近づくことから，d が大きな場合は S1 中の対象は，ほとんど二つの超球の隙間に存在することが分かります．これは，中心の対象から他の対象までの距離は，次元の増加に従って急速に大きくなることを意味します．すなわち，どの対象も互いに似ていないことになります．クラスタリングは，似ている対象をまとめる操作なので，有意な解を得ることができなくなります．
この次元の呪いに対する抜本的な解決法は，外的な知識によって不要と考えられる属性を排除し，次元数を小さくすることです．しかし，データの性質が不明で，どの属性が不要か判断できない場合も多いため，このような高次元データを処理する手法も研究されていますので，文献035 の9節などをご覧下さい．
階層的手法の注意点について述べます．数学的に優れたある種の性質をもつ最短距離法は，空間濃縮という性質のため，極めて外乱に弱く，実データではあまり良い結果は得られません．空間濃縮とは，併合されてできた新しいクラスタは，以後の併合の対象として選ばれる可能性が加速度的に増加する現象です．図3(a)のデータには，視覚的なまとまりからすれば点線で囲んだ部分に二つのクラスタ見なせる部分と，これらをつなぐ外乱と見なせる対象が存在しています．このデータに最短距離法を適用すると，図3(b) のデンドログラムが得られます．このデンドログラムを用いて，図3(b)の矢印の部分で二つのクラスタに分割すると，一方は 1 個の対象(図3(a)の▲印)，もう一方はそれ以外全てを含むクラスタが生成され，直観に反した結果が得られます．また，この空間濃縮は，繋がった外乱を一つづつ併合することがあるため，チェイニング効果とも呼ばれます．この効果によって図3(b)の点線部分のような階段状構造ができますが，最短距離法の特性のために生じた構造であることが多いので注意してください．
 (a) データ |
 (b) デンドログラム |
逆に，最長距離法には，併合されてできたクラスタは，以後，併合されにくくなる空間拡散という性質があり，本来のクラスタから偶然離れてしまった対象があると，過剰に分割される傾向があります．一方，群平均法は，空間濃縮や拡散は生じません．
 |
k-means 法の注意点について述べます．この手法は，クラスタは超球状の形状で，クラスタ中の対象数はどれも等しいということを暗黙のうちに仮定しているので，この仮定に反する構造の抽出は困難です．文献 [Guha 98] では，図4のように三つの密な領域が存在するデータに k-means法を適用した結果を例示しています．直観に反して，クラスタ中の事例数が等しくなるように，対象数の大きな領域は三つに分割されています．クラスタの対象数に差がある場合には，k-means 法の代りに確率モデルをEMアルゴリズムで解く方法(文献034 の7節)などを検討して下さい．また，クラスタが超球形でない場合は，標準偏差で正規化したマハラノビス距離などのスケーリングの変換したり，そのような目的で開発された手法(文献035 の10節)を利用すべきです．
k-means法は欲張り探索で局所解を求める手法であるため，初期状態によって最終結果は大きく影響されます．一般的な対処法は，初期状態をランダムに変更して複数回k-meansを実行して幾つかの分割を獲得し，それらの分割の中で評価関数を最小にするものを選びます．また，同じクラスタにならないことが事前に予測される対象があれば，初期クラスタでそれらの対象を別のクラスタの代表点とするのもよいでしょう．対象数 N が大きく k-means法を何度も適用するのは時間がかかり過ぎる場合もあるので，サンプリングを使って有望な初期値を求める [Bradley 98] のような研究もあります．
最初に適用するクラスタリング手法は一般には以下のようにするのがよいでしょう．まず，対象が属性ベクトルで記述されている場合，計算量が k-means法は O(N k) に対し，階層的手法は O(N2) (ユークリッド距離の場合．一般には O(N2 log N)）なので，k-means法を用いる方がよいでしょう．ただし，階層構造が必要な場合には Ward 法を用います．属性ベクトルではなく，対象間の距離だけが与えられている場合は，群平均法を適用します．最短距離法や最長距離法は群平均法の結果に不満な場合に試してみてもよいでしょう．もちろん，あらゆる状況で最良な手法は存在しないので，必ずこの選択が良いというわけではありません．だが，これらの手法を適用した結果からデータに関する知見を得て，その知見に基づき，文献034 や 文献035 に挙げた他の高度な手法を検討するのが良いでしょう．
|
なる代表点に割り当て