クラスタリング

クラスタリング（クラスター分析とも呼ばれる）は、分析者が定義した特定の類似度または距離尺度に基づいて、オブジェクトの集合をグループ（クラスター）に分割するデータ分析手法であり、同じクラスター内のオブジェクトは、他のクラスターのオブジェクトよりも互いに類似している。これは探索的データ分析の主要なタスクであり、統計的データ分析の一般的な手法として、パターン認識、画像解析、情報検索、バイオインフォマティクス、データ圧縮、コンピュータグラフィックス、機械学習などの分野で使用されている。教師なし学習法として、クラスタリングはラベル付きデータに依存せず、クラスラベルの事前知識なしにデータ内の固有の構造やグループを発見する。

「クラスタリング」という用語は、単一の特定アルゴリズムではなく、アルゴリズムとタスクのファミリーを包含する。異なるアルゴリズムは、クラスターを構成するものの理解と、クラスターを効率的に特定する方法において大きく異なる。クラスターの一般的な概念には、メンバー間の距離が小さいグループ、データ空間の高密度領域、区間、特定の統計分布などが含まれる。その結果、クラスタリングは多目的最適化問題として定式化でき、適切なアルゴリズムとパラメータ設定（距離関数、密度閾値、期待クラスター数など）は、個々のデータセットと結果の意図された使用法に依存する。クラスター分析は自動タスクではなく、知識発見または対話型多目的最適化の反復プロセスであり、結果が望ましい特性を達成するまでデータ前処理とモデルパラメータを調整する試行錯誤をしばしば必要とする。

クラスタリングという用語の他に、自動分類、数値分類学、ボトリオロジー（ギリシャ語のβότρυς「ブドウ」から）、類型分析、コミュニティ検出など、いくつかの類似用語が存在する。微妙な違いは結果の使用法にあることが多い：データマイニングでは結果のグループ自体が関心の対象であるのに対し、自動分類では結果の識別力が関心の対象である。

歴史

クラスター分析は、1932年のDriverとKroeberの研究により人類学で始まった。1938年にJoseph Zubin、1939年にRobert Tryonによって心理学に導入され、1943年以降、Raymond Cattellが人格心理学の特性理論分類に有名に使用した。それ以来、クラスタリングは多くの科学分野で基本的なツールへと進化し、数十年にわたって数百の公開アルゴリズムが開発されてきた。

クラスターモデル

「クラスター」の概念は正確に定義できず、これがクラスタリングアルゴリズムの多様性の主な理由である。共通の分母は、データオブジェクトのグループである。しかし、異なる研究者は異なるクラスターモデルを採用し、各モデルは様々なアルゴリズムで実装できる。これらのクラスターモデルを理解することは、アルゴリズム間の違いを理解するために不可欠である。典型的なクラスターモデルには以下が含まれる：

• 接続性モデル：階層的クラスタリングは距離接続性に基づくモデルを構築し、オブジェクトを近接性に基づいてリンクすることでクラスターを形成する。
• セントロイドモデル：k-meansアルゴリズムは各クラスターを単一の平均ベクトル（セントロイド）で表現し、オブジェクトを最も近いセントロイドに割り当てる。
• 分布モデル：クラスターは統計分布を使用してモデル化され、期待値最大化（EM）アルゴリズムで使用される多変量正規分布などがある。
• 密度モデル：DBSCAN、OPTICS、HDBSCANなどのアルゴリズムは、クラスターをデータ空間内の疎な領域で分離された接続された高密度領域として定義する。
• 部分空間モデル：バイクラスタリング（共クラスタリングまたは二モードクラスタリングとも呼ばれる）では、クラスターはクラスターメンバーと関連属性の両方でモデル化され、クラスターがデータの異なる部分空間に存在できるようにする。
• グループモデル：一部のアルゴリズムは結果に洗練されたモデルを提供せず、単にグループ情報を提供する。
• グラフベースモデル：グラフ内のすべての2つのノードがエッジで接続されているノードのサブセットであるクリークは、クラスターの典型的な形態と見なすことができる。完全接続要件の緩和である準クリークは、HCSクラスタリングアルゴリズムなどのアルゴリズムで使用される。
• 符号付きグラフモデル：符号付きグラフでは、すべてのパスはエッジ上の符号の積から符号を持つ。バランス理論の仮定の下では、エッジは符号を変える可能性があり、二分グラフが生じる。より弱い「クラスタリング可能性公理」（サイクルがちょうど1つの負のエッジを持たない）は、2つ以上のクラスターまたは正のエッジのみを持つ部分グラフを持つ結果をもたらす。
• ニューラルモデル：最もよく知られた教師なしニューラルネットワークは自己組織化マップであり、これらのモデルは通常、上記のモデルの1つ以上に類似していると特徴付けることができ、ニューラルネットワークが主成分分析または独立成分分析の形態を実装する場合の部分空間モデルも含まれる。

クラスタリングの種類

「クラスタリング」は本質的にクラスターの集合であり、通常はデータセット内のすべてのオブジェクトを含む。また、互いに埋め込まれたクラスターの階層など、クラスター間の関係を指定することもある。クラスタリングは大まかに次のように区別できる：

• ハードクラスタリング：各オブジェクトはクラスターに属するか属さないかのいずれかである。
• ソフトクラスタリング（ファジークラスタリングとも呼ばれる）：各オブジェクトは各クラスターに属する可能性などの程度で属する。

より細かい区別には以下が含まれる：

• 厳密分割クラスタリング：各オブジェクトはちょうど1つのクラスターに属する。
• 外れ値付き厳密分割クラスタリング：オブジェクトはどのクラスターにも属さない場合があり、その場合外れ値と見なされる。
• 重複クラスタリング（代替クラスタリング、マルチビュークラスタリングとも呼ばれる）：オブジェクトは複数のクラスターに属する場合があり、通常はハードクラスターを含む。
• 階層的クラスタリング：子クラスターに属するオブジェクトは親クラスターにも属し、ツリー状の構造を作成する。
• 部分空間クラスタリング：重複クラスタリングであるが、一意に定義された部分空間内では、クラスターが重複することは期待されない。

アルゴリズム

クラスタリングアルゴリズムは、そのクラスターモデルに基づいて分類できる。公開されているクラスタリングアルゴリズムはおそらく100以上あり、すべてがクラスターのモデルを提供するわけではないため、分類は困難である。客観的に「正しい」クラスタリングアルゴリズムは存在せず、前述のように「クラスタリングは見る人の目にある」。実際、公理的なアプローチは、任意のクラスタリング手法が3つの基本特性を同時に満たすことは不可能であることを示している：スケール不変性（距離の比例スケーリングの下で結果が不変のままであること）、豊富さ（データのすべての可能な分割を達成できること）、および距離とクラスタリング構造の間の一貫性。特定の問題に最も適したアルゴリズムは、数学的な理由で1つのクラスターモデルを優先しない限り、実験的に選択する必要があることが多い。

代表的なクラスタリングアルゴリズムには以下が含まれる：

• K-means：セントロイドベースのアルゴリズムで、クラスター内平方和を最小化することによりデータをk個のクラスターに分割する。シンプルで効率的だが、クラスター数を指定する必要があり、外れ値に敏感である。
• 階層的クラスタリング：凝集的（ボトムアップ）または分割的（トップダウン）にクラスターの階層を構築する。事前定義されたクラスター数を必要とせず、デンドログラムを生成する。
• DBSCAN：密度ベースのアルゴリズムで、クラスターを疎な領域で分離された高密度領域として識別する。任意の形状のクラスターを発見し、外れ値を処理できるが、イプシロンや最小点数などのパラメータ調整が必要である。
• 期待値最大化（EM）：分布ベースのアルゴリズムで、クラスターをガウス分布としてモデル化し、尤度を最大化するためにパラメータを反復的に推定する。
• OPTICS：DBSCANの拡張で、クラスター順序を生成し、様々な密度に対してより堅牢にする。
• 自己組織化マップ（SOM）：高次元データを低次元グリッドにマッピングし、位相関係を保存するニューラルネットワークモデル。

応用

クラスタリングは多くの領域で広く使用されている。パターン認識では、分類タスクのデータ内のグループを識別するのに役立つ。画像解析では、画像セグメンテーションとオブジェクト検出に使用される。情報検索では、クラスタリングは検索とレコメンデーションのためにドキュメントをトピックごとに整理する。バイオインフォマティクスでは、類似した発現パターンを持つ遺伝子やタンパク質をグループ化する。データ圧縮では、クラスタリングはプロトタイプでグループを表現することによりデータサイズを削減する。コンピュータグラフィックスでは、色量子化とメッシュ簡略化に役立つ。人工知能では、クラスタリングは教師なし学習の核となる手法であり、ラベル付き例なしでパターンを発見することを可能にする。

課題と考慮事項

クラスタリングにはいくつかの課題がある。最適なクラスター数の決定はしばしば困難であり、ドメイン知識やヒューリスティックを必要とする場合がある。距離メトリックの選択は結果に大きく影響し、一般的なメトリックにはユークリッド距離、マンハッタン距離、コサイン類似度がある。高次元データは次元の呪いに悩まされる可能性があり、距離の意味が薄れる。クラスタリング結果は初期化とパラメータ設定に敏感であり、普遍的な解決策はない。さらに、クラスタリングの反復的な性質は、結果が望ましい特性を満たすことを保証するために、シルエットスコアやランド指数などの内部または外部評価メトリックを使用して検証する必要があることを意味する。

関連概念

クラスタリングは、次元削減や異常検出などの他の教師なし学習手法と密接に関連している。合成サンプルを生成するためのデータ拡張と組み合わせて使用されることが多く、教師あり学習の前処理にも使用される。深層学習の文脈では、クラスタリングは表現学習のためにニューラルネットワークアーキテクチャに統合できる。クラスタリングの原理は、ネットワーク分析におけるコミュニティ検出やビジネス分析における市場セグメンテーションの基盤でもある。