クラスタリング - yuuk1's Digital Garden

# クラスタリング ## 定義クラスタリング(clustering、クラスタ分析)は、対象間の非類似度(dissimilarity)を手がかりに、同一クラスタ内の対象が異クラスタ間の対象より互いに似ているように観測を群へ分割する教師なし学習の課題である。手法は大きく3系統に分かれる: (1) 確率モデルを介さず観測を直接群へ割り当てる**組合せ的アルゴリズム**(K-means・K-medoids・階層的クラスタリング)、(2) データを密度関数の混合としてモデル化し最尤推定/ベイズ推定で当てはめる**混合モデル**(ガウス混合とEMアルゴリズム)、(3) 確率密度のモード(峰)を直接推定する**モード探索**(PRIMなどのバンプハンティング)である。組合せ的アルゴリズムでは、within-cluster点散布 $W(C)=\frac{1}{2}\sum_k\sum_{C(i)=k}\sum_{C(i')=k} d(x_i,x_{i'})$ の最小化(あるいは等価にbetween-cluster散布 $B(C)$ の最大化)が目的関数となる。K-meansはEuclid距離のもとでこれを反復的な割当・重心更新で局所最適化し(Algorithm 14.1)、K-medoidsはクラスタ中心を実データ点に限定することで任意の非類似度に一般化する(Algorithm 14.2)。階層的クラスタリングは凝集型・分割型のいずれかで、群間非類似度の定義(単連結法・完全連結法・群平均法)によりデンドログラムの形が変わる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.3) ## 横断的知見 - **同一データセットが教師なし学習の「導入例」と「本論での実演」の両方に使われる**: ch.1(序論)は、ヒト腫瘍マイクロアレイデータ(6830遺伝子×64サンプル)を教師なし学習の動機付け例として、「目的変数がないので回帰ではなくクラスタリングの課題になる」とだけ紹介する。ch.14 はこの同じデータセットに実際にK-means(§14.3.8)と階層的クラスタリング(§14.3.12)を適用し、乳がんの2検体が実は転移したメラノーマの誤診断だったことをクラスタリング結果から発見する、という具体的な実演にまで踏み込む。本書全体の構成として「概念だけ先出しし、手法確立後に同じデータで実演する」という教育的パターンが確認できる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 1 Introduction]] Example 4, [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.3.8, §14.3.12) - **距離ベース(組合せ的)クラスタリングと密度ベースクラスタリングは、クラスタ数の事前知識という前提が根本的に異なる**: ch.14 のK-means/K-medoids/階層的クラスタリングはいずれも(階層的クラスタリングを除き)クラスタ数 $K$ を事前に指定するか、Gap統計量のような事後的な推定手続きを要する。一方 [[密度ベースクラスタリング]](DBSCAN/HDBSCAN)は密度の閾値・階層のみからクラスタ数を自然に導出し、事前指定を必要としない。ch.14 の組合せ的手法は球状・凸状のクラスタを仮定する(K-meansが非凸クラスタを扱えない弱点はスペクトラルクラスタリングの導入動機そのものである、§14.5.3)のに対し、密度ベース手法は任意形状のクラスタを扱える点でも対照的である。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.3.11, §14.5.3, [[密度ベースクラスタリング]]) - **教師なしクラスタリング(第14章)と、教師ありプロトタイプ法としてのK-means(第13章)は、同じアルゴリズムをラベル情報の有無で全く異なる目的に転用する**: 第14章のK-meansはラベルを持たないデータにクラスタ構造を発見する教師なし学習の手法だが、[[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.2.1は同じK-meansアルゴリズムを各クラスの訓練データへ個別に適用し、得られた重心にクラスラベルを付けてプロトタイプとして流用する教師ありの応用へ転用する。この転用は弱点を伴う: 各クラスの内部だけで独立にクラスタリングするため他クラスのデータが一切プロトタイプの配置に関与せず、結果として一部のプロトタイプが決定境界付近に置かれ誤分類を招く(図13.1上段)。第13章のLVQ(§13.2.2)はこの弱点への対処として、決定境界という教師あり情報を使い、全クラスの点を見ながらプロトタイプをオンラインで境界から遠ざける。すなわちLVQは「K-meansがクラス内だけで最適化してしまう」という限界を、ラベル情報の活用範囲を広げることで補う関係にある。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.3, [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.2.1-13.2.2) - **ディープラーニング入門書(ch.2)は、クラスタリングを教師なし学習の最も基本的な例として、類似度に基づくグループ化という1文で定義し、ESL第14章が展開する組合せ的アルゴリズム(K-means等)の技術的詳細には立ち入らない**: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.4は「データ間の類似度を元に、データセットを似ているデータ同士にまとめ上げる」とクラスタリングを導入し、外れ値検出・表現変換(PCA等)と並ぶ教師なし学習の代表例として位置づける。これは本ページがESL第14章から蓄積してきたK-means・K-medoids・階層的クラスタリングという具体的アルゴリズムの技術的な違いには触れず、「教師なし学習は何をするものか」を示す最小限の導入として機能する。ch.1(序論)がヒト腫瘍マイクロアレイデータを教師なし学習の動機付け例として先出しし第14章で技術的に実演するという2段階の教育パターンを本ページは既に確認しているが(横断的知見参照)、ch.2はこれとは別に、より一般向けの入門書という第3の抽象度で同じ教育的先出しパターンを反復している。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.3, [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.4) ## 未解決の問い - Gap統計量(ch.14 §14.3.11)とHDBSCANの相対超過質量に基づくクラスタ安定性([[クラスタ安定性]])は、どちらも「最適なクラスタ数/分割」を決める基準だが、両者を同一データで直接比較した実証結果は本書・関連ソースのいずれにも見当たらない。前提(球状クラスタ vs. 密度レベルセット)が異なる状況でどちらが頑健かは未検証。 - ch.14 の群平均法の統計的一貫性の議論(§14.3.12)は、[[時系列クラスタリング]]で示された「10年間の進歩の幻想」(k-Shapeを統計的に上回る手法が長年出現しなかった)のような、ベンチマーキング方法論の落とし穴とどう関係するか。階層的クラスタリングの理論的性質の良さが実務上のベンチマークでの優位性に直結するとは限らない可能性がある。 - K-means の「非凸クラスタを扱えない」という限界(§14.5.3)は、高次元データ(遺伝子発現データ等)でどの程度深刻か。ch.14 の腫瘍マイクロアレイ例では明示的な非凸性の検証がなされていない。 - 第13章のGap統計量に相当する「プロトタイプ数Rの選び方」の指針(交差検証等)は、教師ありプロトタイプ法(K-means・LVQ)に対しては第14章のGap統計量ほど体系立てて論じられていない。教師あり設定でのプロトタイプ数選択は、教師なしのクラスタ数選択の基準とどこまで共有できるか。 ## 関連 - ソース: [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]](教師ありプロトタイプ法としてのK-means・LVQ) / [[@2009__Springer__The Elements of Statistical Learning - Chapter 1 Introduction]] / [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]](教師なし学習の最小限の例示) - 概念: [[密度ベースクラスタリング]](事前クラスタ数不要・任意形状という対照的パラダイム)/ [[時系列クラスタリング]](時系列領域での特化)/ [[クラスタ安定性]](HDBSCANにおけるクラスタ数決定基準)/ [[スペクトラルクラスタリング]](K-meansの非凸性の限界を克服する拡張)/ [[主成分分析]](K-means初期化やSOMの初期配置に利用)/ [[最近傍法]](K-means・LVQをプロトタイプ法として位置づける文脈) ## 出典 - [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]](§14.3) - [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]](§13.2) - [[@2009__Springer__The Elements of Statistical Learning - Chapter 1 Introduction]](Example 4) - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, 第2章, §2.4.