クラスター分析

クラスター分析（またはクラスタリング）は、一連のオブジェクトをグループに分割することを目的としたデータ分析手法です。このグループ（クラスターと呼ばれる）内のオブジェクトは、他のグループ（クラスター）内のオブジェクトよりも（分析者が定義する特定の意味で）互いに高い類似性を示します。これは探索的データ分析の主要なタスクであり、統計データ分析の一般的な手法であり、パターン認識、画像分析、情報検索、バイオインフォマティクス、データ圧縮、コンピュータグラフィックス、機械学習など、多くの分野で使用されています。

クラスター分析は、特定の 1 つのアルゴリズムではなく、一群のアルゴリズムおよびタスクを指します。これは、クラスターを構成するものについての理解とそれを効率的に見つける方法が大きく異なるさまざまなアルゴリズムによって実現できます。クラスターの一般的な概念には、クラスターメンバー間の距離が短いグループ、データ空間の密な領域、間隔、または特定の統計分布などがあります。したがって、クラスタリングは、多目的最適化問題として定式化できます。適切なクラスタリングアルゴリズムとパラメーター設定 (使用する距離関数、密度しきい値、予想されるクラスターの数などのパラメーターを含む) は、個々のデータセットと結果の使用目的によって異なります。クラスター分析自体は自動タスクではなく、試行錯誤を伴う知識発見または対話型多目的最適化の反復プロセスです。結果が目的の特性を達成するまで、データの前処理とモデルパラメーターを変更する必要があることがよくあります。

クラスタリングという用語以外にも、自動分類、数値分類、植物学（ギリシャ語：βότρυς 「ブドウ」に由来）、類型分析、コミュニティ検出など、似た意味を持つ用語が数多く存在します。これらの用語の微妙な違いは、結果の用途に現れることが多いです。データマイニングでは、結果として得られるグループが重要なのに対し、自動分類では、結果として得られる識別力が重要なのです。

クラスター分析は、1932年にドライバーとクローバーによって人類学で考案され^[1] 、 1938年にジョセフ・ズービン^[2]、1939年にロバート・トライオン^[3]によって心理学に導入され、 1943年からキャッテルによって性格心理学の特性理論の分類に使用されたことで有名になりました^[4]。

意味

「クラスター」という概念は明確に定義できないため、クラスタリングアルゴリズムが数多く存在する理由の一つとなっています。^[5]共通項は、データオブジェクトの集合体です。しかし、研究者によってクラスターモデルは異なり、それぞれのクラスターモデルに対して異なるアルゴリズムが提示されることがあります。異なるアルゴリズムによって発見されるクラスターの概念は、その特性が大きく異なります。これらの「クラスターモデル」を理解することは、様々なアルゴリズムの違いを理解する鍵となります。代表的なクラスターモデルには、以下のものがあります。

接続性モデル:たとえば、階層的クラスタリングは距離の接続性に基づいてモデルを構築します。
重心モデル:たとえば、k-means アルゴリズムは各クラスターを単一の平均ベクトルで表します。
分布モデル:期待最大化アルゴリズムで使用される多変量正規分布などの統計分布を使用してモデル化されます。
密度モデル:たとえば、DBSCANおよびOPTICS は、クラスターをデータ空間内の接続された密な領域として定義します。
サブスペースモデル:バイクラスタリング(共クラスタリングまたは 2 モードクラスタリングとも呼ばれます) では、クラスターはクラスターメンバーと関連属性の両方を使用してモデル化されます。
グループモデル:一部のアルゴリズムでは、結果に対して洗練されたモデルが提供されず、グループ化情報のみが提供されます。
グラフベースモデル：クリーク、グラフ内のノードのサブセットで、そのサブセット内の2つのノードがそれぞれエッジで接続されているものは、クラスターの典型的な形態と見なすことができます。完全な接続要件を緩和したもの（エッジの一部が欠落していても構わない）は、HCSクラスタリングアルゴリズム。
符号付きグラフモデル：符号付きグラフのすべてのパスは、辺の符号の積から得られる符号を持つ。バランス理論の仮定の下では、辺の符号が変化し、分岐したグラフになる可能性がある。より弱い「クラスタリング可能性公理」（どのサイクルにも負の辺が1つだけ存在しない）は、2つ以上のクラスター、つまり正の辺のみを持つサブグラフを生成する。^[6]
ニューラルモデル:最もよく知られている教師なしニューラルネットワーク自己組織化マップであり主成分分析または独立成分分析の形式を実装する場合はサブスペースモデルも含まれます。

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

ハードクラスタリング: 各オブジェクトがクラスタに属するかどうか
ソフトクラスタリング（別名：ファジークラスタリング): 各オブジェクトは、ある程度各クラスターに属します（たとえば、クラスターに属する可能性）。

さらに細かい区別も可能です。たとえば、次のようになります。

厳密なパーティショニングクラスタリング：各オブジェクトは正確に1つのクラスタに属します
外れ値を含む厳密なパーティショニングクラスタリング：オブジェクトはどのクラスタにも属さないこともあり、その場合は外れ値
重複クラスタリング（または、代替クラスタリング、マルチビュークラスタリング）：オブジェクトは複数のクラスタに属する可能性があり、通常はハードクラスタが含まれます。
階層的クラスタリング: 子クラスタに属するオブジェクトは親クラスタにも属する
部分空間クラスタリング：重複クラスタリングでは、一意に定義された部分空間内では、クラスタが重複することは期待されない。

アルゴリズム

上記のように、クラスタリングアルゴリズムはクラスタモデルに基づいて分類できます。公開されているクラスタリングアルゴリズムは100種類以上ある可能性があるため、以下の概要では、最も代表的なクラスタリングアルゴリズムのみを取り上げます。すべてのアルゴリズムがクラスタモデルを提供しているわけではないため、簡単に分類することはできません。Wikipediaで説明されているアルゴリズムの概要は、統計アルゴリズムの一覧をご覧ください。

客観的に「正しい」クラスタリングアルゴリズムは存在しませんが、前述のように「クラスタリングは見る人の目次第」です。^[5]実際、クラスタリングに対する公理的なアプローチは、いかなるクラスタリング手法も、スケール不変性（距離の比例スケーリングにおいて結果が変わらない）、リッチネス（データのあらゆる可能な分割が実現可能）、そして距離とクラスタリング構造の一貫性という3つの基本特性を同時に満たすことは不可能であることを示しています。 ^[7]特定の問題に対する最適なクラスタリングアルゴリズムは、あるクラスタモデルを他のクラスタモデルよりも優先する数学的理由がない限り、多くの場合、実験的に選択する必要があります。ある種類のモデル向けに設計されたアルゴリズムは、根本的に異なる種類のモデルを含むデータセットでは、一般的に機能しません。^[5]例えば、k平均法は非凸クラスタを見つけることができません。^[5]従来のクラスタリング手法のほとんどは、クラスタが球面、楕円形、または凸形状を示すと仮定しています。^[8]

接続性ベースのクラスタリング（階層型クラスタリング）

連結性ベースのクラスタリング（階層的クラスタリングとも呼ばれる）は、オブジェクトは遠くにあるオブジェクトよりも近くにあるオブジェクトとより関連しているという基本的な考え方に基づいています。これらのアルゴリズムは、「オブジェクト」を距離に基づいて接続し、「クラスター」を形成します。クラスターは、主にクラスターの各部分を接続するために必要な最大距離によって説明できます。異なる距離では異なるクラスターが形成され、それらはデンドログラムを使用して表すことができます。これが「階層的クラスタリング」という一般名の由来です。これらのアルゴリズムは、データセットを単一のパーティションに分割するのではなく、特定の距離で互いに融合するクラスターの広範な階層を提供します。デンドログラムでは、y軸はクラスターが融合する距離を示し、オブジェクトはクラスターが混ざらないようにx軸に沿って配置されます。

連結性に基づくクラスタリングは、距離の計算方法が異なる一連の手法です。通常の距離関数の選択に加えて、ユーザーは使用する連結基準（クラスターは複数のオブジェクトで構成されるため、距離を計算するための候補は複数存在する）も決定する必要があります。一般的な選択肢としては、単一連結クラスタリング（オブジェクト間の距離の最小値）、完全連結クラスタリング（オブジェクト間の距離の最大値）、UPGMAまたはWPGMA（「加重平均を用いた重み付けなしまたは加重ペアグループ法」、平均連結クラスタリングとも呼ばれる）が挙げられます。さらに、階層的クラスタリングは、凝集型（単一の要素から開始し、それらをクラスターに集約する）または分割型（データセット全体から開始し、それをパーティションに分割する）のいずれかです。

これらの手法はデータセットを一意に分割するのではなく、ユーザーが適切なクラスターを選択できる階層構造を生成します。外れ値に対してはそれほど堅牢ではなく、外れ値は追加のクラスターとして現れたり、他のクラスターの結合を引き起こしたりする可能性があります（特にシングルリンククラスタリングでは「連鎖現象」として知られています）。一般的なケースでは、複雑度は凝集型クラスタリングと分割型クラスタリングであり、^[9]大規模なデータセットでは処理速度が遅くなります。特殊なケースでは、最適かつ効率的な手法（複雑度）が知られています。シングルリンククラスタリングではSLINK ^[10] 、完全リンククラスタリングでは CLINK ^{[11]です。} ${\mathcal {O}}(n^{3})$ ${\mathcal {O}}(2^{n-1})$ ${\mathcal {O}}(n^{2})$

連鎖クラスタリングの例
ガウス分布データにおける単一リンク。クラスター数が35になると、最大のクラスターは小さな部分に細分化し始めますが、それ以前は単一リンク効果により2番目に大きいクラスターとまだつながっていました。
密度ベースのクラスター上の単一リンク。リンククラスタリングには「ノイズ」の概念がないため、20 個のクラスターが抽出されましたが、そのほとんどには単一の要素が含まれています。

重心ベースのクラスタリング

重心ベースのクラスタリングでは、各クラスタは中心ベクトルで表されますが、この中心ベクトルは必ずしもデータセットのメンバーではありません。クラスタ数がkに固定されている場合、k平均法クラスタリングは最適化問題として正式に定義されます。つまり、 k個のクラスタ中心を見つけ、クラスタからの距離の二乗が最小になるように、オブジェクトを最も近いクラスタ中心に割り当てます。

最適化問題自体はNP 困難であることが知られているため、一般的なアプローチでは近似解のみを探索します。特に有名な近似法はロイドのアルゴリズムで、^{[12]単に「}k 平均法アルゴリズム」と呼ばれることもあります(ただし、この名前を導入したアルゴリズムは他にもあります)。ただし、このアルゴリズムでは局所最適値のみが見つかるだけなので、異なるランダム初期化で複数回実行されるのが一般的です。k平均法のバリエーションには、複数回実行して最良のものを選択するなどの最適化が含まれることがよくありますが、その他にも、重心をデータセットのメンバーに制限する ( k -medoids )、中央値を選択する( k -medians clustering )、初期中心をそれほどランダムに選択しない ( k -means++ )、またはあいまいなクラスター割り当てを許可する ( fuzzy c-means ) などの最適化も含まれています。

ほとんどのk平均法型アルゴリズムでは、クラスターの数（k）を事前に指定する必要があり、これがこれらのアルゴリズムの最大の欠点の一つと考えられています。さらに、これらのアルゴリズムは、常に最も近い重心にオブジェクトを割り当てるため、ほぼ同じサイズのクラスターを優先します。その結果、クラスターの境界が不適切に切断されることがよくあります。これは主に、アルゴリズムがクラスターの境界ではなくクラスターの中心を最適化するためです。重心ベースのクラスタリングアルゴリズムに含まれる手順は以下のとおりです。

k 個の異なるクラスターをランダムに選択します。これらが改善対象となる初期の重心です。
観測値の集合 $(x 1, x 2, ..., x n)$ を仮定します。各観測値を、その観測値から最小の二乗ユークリッド距離を持つ重心に割り当てます。これにより、それぞれが一意の観測値を含むk個の異なるグループが生成されます。
重心を再計算します ( k平均法クラスタリングを参照)。
新しい重心が前回の反復の重心と等しい場合のみ終了します。そうでない場合は、重心がまだ収束していないため、アルゴリズムを繰り返します。

K平均法には、興味深い理論的特性がいくつかあります。まず、データ空間をボロノイ図と呼ばれる構造に分割します。次に、概念的には最近傍分類に近いため、機械学習でよく用いられます。さらに、K平均法はモデルベースクラスタリングの一種と見なすことができ、ロイドのアルゴリズムは、後述するこのモデルにおける期待値最大化アルゴリズムの一種と見なすことができます。

k平均法クラスタリングの例
k平均法はデータを Voronoi セルに分割し、同じサイズのクラスター (ここでは適切ではありません) を想定します。
k平均法では密度ベースのクラスターを表すことはできません。

k平均法やkメドイド法といった重心ベースのクラスタリング問題は、オペレーションズ・リサーチや計算幾何学の分野では標準的な問題である、容量制限のない計量施設配置問題の特殊なケースです。基本的な施設配置問題（より複雑な設定をモデル化する多くのバリエーションがあります）では、与えられた消費者集団に最適なサービスを提供するために最適な倉庫の場所を見つけることが課題となります。「倉庫」をクラスターの重心、「消費者の場所」をクラスター化の対象となるデータと見なすことができます。これにより、施設配置に関する文献で提示されている高度なアルゴリズムによるソリューションを、現在検討されている重心ベースのクラスタリング問題に適用することが可能になります。

モデルベースクラスタリング

統計学に最も関連性の高いクラスタリングフレームワークは、分布モデルに基づくモデルベースクラスタリングです。このアプローチは、データが複数の確率分布の混合から生じるものとしてモデル化します。このアプローチの利点は、クラスターの数、使用するクラスタリング手法またはモデル、外れ値をどのように検出して処理するかといった疑問に対して、原理に基づいた統計的回答を提供できることです。

これらの手法の理論的基盤は優れているものの、モデルの複雑さに制約が課されない限り、過学習の問題が生じます。より複雑なモデルは通常、データをより適切に説明できるため、適切なモデルの複雑さを選択することは本質的に困難です。標準的なモデルベースクラスタリング手法には、共分散行列の固有値分解に基づく、より簡潔なモデルが含まれており、過学習とデータへの忠実性のバランスが取れています。

代表的な手法の一つに、ガウス混合モデル（期待最大化アルゴリズムを使用）があります。この手法では、データセットは通常、過剰適合を避けるため、ランダムに初期化された固定数のガウス分布を用いてモデル化されます。これらの分布のパラメータは、データセットへの適合性を高めるために反復的に最適化されます。この手法は局所最適値に収束するため、複数回実行すると異なる結果が生じる可能性があります。ハードクラスタリングを実現するために、オブジェクトは多くの場合、最も属する可能性の高いガウス分布に割り当てられますが、ソフトクラスタリングではこれは必要ありません。

分布ベースのクラスタリングは、属性間の相関と依存関係を捉えることができる複雑なクラスターモデルを生成します。しかし、これらのアルゴリズムはユーザーに余分な負担をかけます。多くの実際のデータセットでは、簡潔に定義された数学モデルが存在しない場合があります（例えば、ガウス分布を仮定することは、データに関してかなり強い仮定です）。

ガウス混合モデルクラスタリングの例
ガウス分布データでは、EM はクラスターのモデリングにガウス分布を使用するため、うまく機能します。
密度ベースのクラスターは、ガウス分布を使用してモデル化することはできません。

密度ベースのクラスタリング

密度ベースクラスタリング^[13]では、クラスターはデータセットの残りの部分よりも密度の高い領域として定義されます。クラスターを分離するために必要な疎領域内のオブジェクトは、通常、ノイズや境界点とみなされます。

最も普及している^[14]密度ベースクラスタリング手法はDBSCANです^[15]。多くの新しい手法とは対照的に、DBSCANは「密度到達可能性」と呼ばれる明確に定義されたクラスターモデルを備えています。リンクベースクラスタリングと同様に、一定の距離閾値内の点を連結することをベースとしています。ただし、密度基準を満たす点のみを連結します。密度基準は、元の手法では、この半径内に他のオブジェクトの最小数として定義されていました。クラスターは、密度連結されたすべてのオブジェクト（他の多くの手法とは異なり、任意の形状のクラスターを形成できます）と、これらのオブジェクトの範囲内にあるすべてのオブジェクトで構成されます。DBSCANのもう一つの興味深い特性は、その複雑さがかなり低いことです。データベースに対する範囲クエリの回数は線形であり、実行ごとに基本的に同じ結果が得られます（コアポイントとノイズポイントについては決定論的ですが、境界ポイントについては決定論的ではありません）。そのため、複数回実行する必要はありません。OPTICS ^[16]はDBSCANの一般化であり、範囲パラメータに適切な値を選択する必要がなくなり、リンククラスタリングの結果に関連する階層的な結果を生成します。DeLi-Clu ^[17]密度リンククラスタリングは、シングルリンククラスタリングとOPTICSのアイデアを組み合わせ、パラメータを完全に排除し、 Rツリーインデックスを使用することでOPTICSよりもパフォーマンスが向上します。 $\varepsilon$ $\varepsilon$

DBSCANとOPTICSの主な欠点は、クラスター境界を検出するために何らかの密度低下を想定することです。例えば、人工データでよく見られる重なり合うガウス分布を持つデータセットでは、クラスター密度が連続的に減少するため、これらのアルゴリズムによって生成されるクラスター境界はしばしば恣意的に見えます。ガウス分布の混合からなるデータセットでは、これらのアルゴリズムは、この種のデータを正確にモデル化できるEMクラスタリングなどの手法よりもほぼ常に優れた性能を示します。

平均シフト法は、カーネル密度推定に基づいて、各オブジェクトを近傍の最も密度の高い領域に移動させるクラスタリング手法です。最終的に、オブジェクトは密度の局所的最大値に収束します。k-meansクラスタリングと同様に、これらの「密度アトラクター」はデータセットの代表として機能しますが、平均シフト法はDBSCANと同様に任意の形状のクラスターを検出できます。反復処理と密度推定にコストがかかるため、平均シフト法は通常、DBSCANやk-meansよりも遅くなります。さらに、カーネル密度推定の不均一な挙動がクラスターの末端の過剰な断片化につながるため、平均シフト法の多次元データへの適用は困難です。^[17]

密度ベースクラスタリングの例
DBSCANによる密度ベースクラスタリング
DBSCAN は同様の密度のクラスターを想定するため、近くのクラスターを分離する際に問題が発生する可能性があります。
OPTICS は DBSCAN のバリアントであり、異なる密度のクラスターの処理を改善します。

グリッドベースのクラスタリング

グリッドベースの手法は、多次元データセットに用いられます。^[18]この手法では、グリッド構造を作成し、比較はグリッド（セルとも呼ばれます）上で行われます。グリッドベースの手法は高速で、計算量も少なくて済みます。グリッドベースのクラスタリング手法には、STINGとCLIQUEの2種類があります。グリッドベースのクラスタリングアルゴリズムの手順は以下のとおりです。

データ空間を有限の数のセルに分割します。
セル 'c' をランダムに選択します。ただし、c は事前に走査しないでください。
'c'の密度を計算する
'c'の密度が閾値密度より大きい場合
1. セル「c」を新しいクラスターとしてマークします
2. 'c'のすべての近傍の密度を計算する
3. 隣接セルの密度が閾値密度より大きい場合は、そのセルをクラスターに追加し、閾値密度より大きい密度を持つ隣接セルがなくなるまで手順 4.2 と 4.3 を繰り返します。
すべてのセルを通過するまで手順 2、3、4 を繰り返します。
停止。

評価と査定

クラスタリング結果の評価（または「検証」）は、クラスタリング自体と同じくらい難しい。^[35]一般的な評価手法には、クラスタリングを単一の品質スコアにまとめる「内部」評価、クラスタリングを既存の「グラウンドトゥルース」分類と比較する「外部」評価、人間の専門家による「手動」評価、そして意図されたアプリケーションにおけるクラスタリングの有用性を評価する「間接」評価などがある。 ^[36]

内部評価尺度は、それ自体がクラスタリングの目的関数とみなせる関数を表すという問題を抱えています。例えば、シルエット係数を用いてデータセットをクラスタリングすることは可能ですが、これを効率的に行うアルゴリズムは知られていません。このような内部評価尺度を評価に用いると、最適化問題の類似性を比較することになり、^[36]必ずしもクラスタリングの有用性を比較するわけではありません。

外部評価にも同様の問題がある。このような「グラウンドトゥルース」ラベルがあればクラスタリングは不要であり、実際のアプリケーションでは通常そのようなラベルは存在しない。一方、ラベルはデータセットの可能な分割方法の一つを反映しているに過ぎず、異なる、あるいはより優れたクラスタリングが存在しないことを意味するわけではない。

したがって、どちらのアプローチもクラスタリングの実際の品質を最終的に判断することはできませんが、そのためには人間による評価が必要であり^[36] 、これは非常に主観的です。しかしながら、このような統計は、質の低いクラスタリングを特定する上で非常に有益であり得ますが^[37]、人間の主観的な評価を無視すべきではありません^{[37] 。}

内部評価

クラスタリング結果がクラスタリングされたデータ自体に基づいて評価される場合、これは内部評価と呼ばれます。これらの手法では通常、クラスター内の類似性が高く、クラスター間の類似性が低いクラスターを生成するアルゴリズムに最高のスコアが割り当てられます。クラスター評価に内部基準を使用することの欠点の1つは、内部基準で高いスコアが得られても、必ずしも効果的な情報検索アプリケーションにつながるわけではないことです。^[38]さらに、この評価は、同じクラスターモデルを使用するアルゴリズムに偏りが生じます。例えば、k-meansクラスタリングはオブジェクト間の距離を自然に最適化するため、距離に基づく内部基準は、結果として得られるクラスタリングを過大評価する可能性があります。

したがって、内部評価尺度は、あるアルゴリズムが他のアルゴリズムよりも優れたパフォーマンスを発揮する状況をある程度把握するのに最適ですが、これは、あるアルゴリズムが他のアルゴリズムよりも有効な結果を生成することを意味するものではありません。^[5]このような指標によって測定される有効性は、データセットにこの種の構造が存在するという主張に依存します。データセットに根本的に異なるモデルのセットが含まれていたり、評価が根本的に異なる基準を測定したりする場合には、ある種のモデル用に設計されたアルゴリズムにはチャンスがありません。^{[5]たとえば、k-means クラスタリングでは凸クラスターしか見つけられず、多くの評価指標は凸クラスターを前提としています。非凸クラスターを含むデータセットでは、}k -meansの使用も、凸性を前提とする評価基準の使用も適切ではありません。

内部評価尺度は12種類以上存在し、通常は同じクラスター内のアイテムは異なるクラスター内のアイテムよりも類似しているはずだという直感に基づいています。^[39]^{: 115–121}たとえば、内部基準に基づいてクラスタリングアルゴリズムの品質を評価するには、次の方法を使用できます。

デイヴィス・ボールディン指数

Davies –Bouldin 指数は次の式で計算できます。ここで、 nはクラスターの数、はクラスターの重心、はクラスター内のすべての要素から重心までの平均距離、は重心との間の距離です。クラスター内距離が小さく (クラスター内類似度が高い)、クラスター間距離が大きい (クラスター間類似度が低い) クラスターを生成するアルゴリズムは Davies–Bouldin 指数が低くなるため、この基準に基づくと、 Davies–Bouldin 指数が最小のクラスターのコレクションを生成するクラスタリングアルゴリズムが最適なアルゴリズムであると見なされます。 $DB={\frac {1}{n}}\sum _{i=1}^{n}\max _{j\neq i}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)$ $c_{i}$ $i$ $\sigma _{i}$ $i$ $c_{i}$ $d(c_{i},c_{j})$ $c_{i}$ $c_{j}$

ダン指数

ダン指数は、密集したクラスターと十分に分離されたクラスターを識別することを目的としています。これは、最小クラスター間距離と最大クラスター内距離の比として定義されます。各クラスター区分について、ダン指数は次の式で計算されます。^[40]

D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,

ここで、 d ( i , j ) はクラスターiとj間の距離を表し、d '( k ) はクラスターkのクラスター内距離を表します。2つのクラスター間のクラスター間距離d ( i , j ) は、クラスターの重心間の距離など、さまざまな距離尺度で表すことができます。同様に、クラスター内距離d '( k ) は、クラスターk内の任意の要素ペア間の最大距離など、さまざまな方法で測定できます。内部基準は、クラスター内類似度が高く、クラスター間類似度が低いクラスターを探すため、ダン指数の高いクラスターを生成するアルゴリズムがより望ましいです。

シルエット係数

シルエット係数は、同じクラスター内の要素との平均距離と、他のクラスター内の要素との平均距離を対比する指標です。シルエット値の高いオブジェクトはクラスタリングが良好であるとみなされ、シルエット値が低いオブジェクトは外れ値である可能性があります。この指標はk平均法クラスタリングと相性が良く、最適なクラスター数を決定する際にも用いられます。^[41]

クラスタリング曲線の下の領域（AUCC）

この指標は、オブジェクトのペアを考慮します。ペア間の距離をスコアリング関数として用い、ペアが同じクラスターに属しているかどうかを考慮して、真陽性、真陰性、偽陰性、真陰性として定義されるパーティクルペアを評価します。この指標は、教師ありシナリオにおけるAUCと同じ特性を持ち、期待値は0.5であり、結果の視覚化が可能です^[42]。

外部評価

外部評価では、クラスタリング結果は、既知のクラスラベルや外部ベンチマークなど、クラスタリングに使用されなかったデータに基づいて評価されます。このようなベンチマークは、事前に分類された項目の集合で構成されており、多くの場合、（専門家の）人間によって作成されます。したがって、ベンチマークセットは評価のゴールドスタンダードと考えることができます。 ^[35]これらの評価方法は、クラスタリングが事前に設定されたベンチマーククラスにどれだけ近いかを測定します。しかし、クラスには内部構造が含まれる場合があり、存在する属性によってクラスタを分離できない場合や、クラスに異常が含まれる場合があるため、これが実際のデータに適切であるか、それとも事実に基づいたグラウンドトゥルースを持つ合成データセットにのみ適切であるかについては、最近議論されています。^[43]さらに、知識発見の観点からは、既知の知識の再現が必ずしも意図した結果とは限りません。^[43]制約付きクラスタリングの特殊なシナリオでは、メタ情報（クラスラベルなど）がクラスタリングプロセスで既に使用されているため、評価目的での情報の保持は容易ではありません。^[44]

いくつかの指標は、分類タスクの評価に用いられる手法から派生したものである。単一のデータポイントにクラスが正しく割り当てられた回数（真陽性と呼ばれる）を数える代わりに、このようなペアカウント指標は、実際に同じクラスターに属するデータポイントの各ペアが、同じクラスターに属すると予測されるかどうかを評価します。^[35]

内部評価と同様に、外部評価の尺度もいくつか存在する。^[39]^{: 125–129}例えば、

純度

純度とは、クラスターが単一のクラスをどの程度含むかを示す尺度である。^[38]計算方法は以下の通りである。各クラスターについて、そのクラスター内で最も一般的なクラスのデータポイントの数を数える。次に、すべてのクラスターの合計を取り、データポイントの総数で割る。正式には、クラスターの集合とクラスの集合（どちらもデータポイントを分割する）が与えられた場合、純度は以下のように定義される。 $M$ $D$ $N$

{\frac {1}{N}}\sum _{m\in M}\max _{d\in D}{|m\cap d|}

この指標はクラスター数が多いことを不利にするものではなく、クラスター数が多いほど高い純度を実現しやすくなります。各データポイントを独自のクラスターに配置することで、常に純度スコア1を実現できます。また、不均衡なデータでは純度はうまく機能しません。不均衡なデータでは、パフォーマンスの低いクラスタリングアルゴリズムでも高い純度値が得られるからです。例えば、サイズ1000のデータセットが2つのクラスで構成され、一方のクラスには999個のポイントが含まれ、もう一方のクラスには1個のポイントが含まれる場合、すべてのパーティションの純度は少なくとも99.9%になります。

ランド指数

ランド指数^[45]は、クラスタリングアルゴリズムによって返されるクラスタがベンチマーク分類にどの程度類似しているかを計算する。これは以下の式で計算できる。

RI={\frac {TP+TN}{TP+FP+FN+TN}}

ここで、は真陽性の数、は真陰性の数、は偽陽性の数、は偽陰性の数です。ここでカウントされるインスタンスは、正しいペアワイズ割り当ての数です。つまり、は予測パーティションと真実パーティションで一緒にクラスター化されているポイントのペアの数、は予測パーティションでは一緒にクラスター化されているが真実パーティションでは一緒にクラスター化されていないポイントのペアの数、などです。データセットのサイズが N の場合、となります。Rand指標の問題の 1 つは、偽陽性と偽陰性に同等の重み付けがされることです。これは、一部のクラスタリングアプリケーションでは望ましくない特性となる可能性があります。F 値^[^{引用が必要}^]は、チャンス補正調整 Rand 指標と同様に、この問題に対処します。 $TP$ $TN$ $FP$ $FN$ $TP$ $FP$ $TP+TN+FP+FN={\binom {N}{2}}$

F値

F値は、パラメータによって再現率に重み付けすることで、偽陰性の寄与を均衡化するために使用できます。適合率と再現率（どちらも外部評価尺度）を次のように定義します。ここで、は適合率、は再現率です。F値は次の式を使用して計算できます。^[38]、の場合。言い換えると、のときは再現率はF値に影響を与えず、を増やすと最終的なF値で再現率に割り当てられる重みが増加します。また、は考慮されず、0から無制限に変化できます。 $\beta \geq 0$ $P={\frac {TP}{TP+FP}}$ $R={\frac {TP}{TP+FN}}$ $P$ $R$ $F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}$ $\beta =0$ $F_{0}=P$ $\beta =0$ $\beta$ $TN$

ジャカード指数

Jaccard指数は、2つのデータセット間の類似性を定量化するために使用されます。Jaccard指数は0から1の間の値を取ります。指数が1の場合、2つのデータセットは同一であり、指数が0の場合、データセットに共通要素がないことを示します。Jaccard指数は次の式で定義されます。これは、両方のデータセットに共通する一意の要素の数を、両方のデータセットの一意の要素の総数で割った値です。ただし、は考慮されません。 $J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {TP}{TP+FP+FN}}$ $TN$

ダイスインデックス

ダイスの対称測定では、次の点を無視しながら、の重みを 2 倍にします。 $TP$ $TN$ $DSC={\frac {2TP}{2TP+FP+FN}}$

フォークス・マロウズ指数

Fowlkes–Mallows 指数^[46]は、クラスタリングアルゴリズムによって返されたクラスターとベンチマーク分類との類似性を計算します。Fowlkes–Mallows 指数の値が高いほど、クラスターとベンチマーク分類の類似性が高くなります。この指数は次の式で計算できます。ここで、は真陽性の数、は偽陽性の数、は偽陰性の数です。指数は適合率と再現率、の幾何平均であるためG 値とも呼ばれ、F 値はそれらの調和平均です。^[47]^[48]さらに、適合率と再現率は Wallace の指数、とも呼ばれます。^[49]再現率、適合率、G 値の確率正規化バージョンは、情報量、有識性、およびMatthews の相関に対応し、 Kappaと強く関連しています。^[50] $FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}$ $TP$ $FP$ $FN$ $FM$ $P$ $R$ $B^{I}$ $B^{II}$

カイ指数

カイ二乗指数^[51]は、カイ二乗統計量を適用してクラスタリング結果を測定する外部検証指標です。この指標は、クラスター間でラベルが可能な限り疎であること、つまり各クラスターの異なるラベルが可能な限り少ないことを正に評価します。カイ二乗指数の値が高いほど、結果として得られるクラスターと使用されたラベルの関係性が強くなります。

相互情報

相互情報量とは、クラスタリングとグラウンドトゥルース分類の間でどれだけの情報量が共有されているかを示す情報理論的指標であり、2つのクラスタリング間の非線形類似性を検出できる。正規化相互情報量は、偶然性を補正したこの手法の一種であり、クラスタ数の変化に対するバイアスを低減している。^[35]

混同行列

混同行列は、分類（またはクラスタリング）アルゴリズムの結果を素早く視覚化するために使用できます。混同行列は、あるクラスターがゴールドスタンダードのクラスターとどの程度異なるかを示します。

妥当性測定

妥当性尺度（略してv-measure）は、クラスターの均質性と完全性を組み合わせた尺度である^[52]

クラスター傾向

クラスター傾向の測定とは、クラスター化の対象となるデータにどの程度のクラスターが存在するかを測定することであり、クラスタリングを試みる前に初期テストとして実行することができます。これを行う方法の一つは、データをランダムデータと比較することです。平均的には、ランダムデータにはクラスターは存在しないはずです^{[検証が必要]}。

ホプキンス統計

ホプキンス統計量には複数の定式化がある。^[53]代表的なものは以下の通りである。^[54]を次元空間におけるデータ点の集合とする。要素を持つデータ点の無作為標本（非置換）を考える。また、一様ランダムに分布するデータ点の集合を生成する。ここで、 Xにおける最も近い近傍からの距離を、Xにおける最も近い近傍からの距離をとする2つの距離尺度を定義する。そして、ホプキンス統計量を以下のように定義する。

X

n

d

m\ll n

x_{i}

Y

m

u_{i}

y_{i}\in Y

w_{i}

x_{i}\in X

H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}}}\,,

この定義によれば、均一ランダムデータは 0.5 に近い値を持つ傾向があり、クラスター化データは 1 に近い値を持つ傾向があります。

ただし、この統計は、多峰性ではなく均一分布からの偏差を測定するため、ガウス分布を 1 つだけ含むデータもスコアが 1 に近くなり、この統計はアプリケーションではほとんど役に立たなくなります (実際のデータは決して均一ではないため)。

アプリケーション

生物学、計算生物学、バイオインフォマティクス

植物と動物の生態学: クラスター分析は、異質な環境における生物群集（集団）を記述し、空間的および時間的に比較するために使用されます。また、植物系統学においては、種、属、あるいはより高次のレベルで、複数の属性を共有する生物（個体）の人工的な系統樹やクラスターを作成するためにも使用されます。
トランスクリプトミクス: クラスタリングは、HCSクラスタリングアルゴリズム^[55]^[56]のように、関連する発現パターンを持つ遺伝子（共発現遺伝子とも呼ばれる）のグループを構築するために使用されます。このようなグループには、特定のパスウェイの酵素など、機能的に関連するタンパク質や、共制御される遺伝子が含まれることがよくあります。発現配列タグ（EST）やDNAマイクロアレイを用いたハイスループット実験は、ゲノミクスの一般的な側面であるゲノムアノテーションのための強力なツールとなり得ます。
配列解析: 配列クラスタリングは、相同配列を遺伝子ファミリーにグループ化するために使用されます。^{[57]これは}バイオインフォマティクス、そして進化生物学全般において非常に重要な概念です。遺伝子重複による進化を参照してください。
ハイスループットジェノタイピングプラットフォーム: クラスタリングアルゴリズムは遺伝子型を自動的に割り当てるために使用されます。^[58]
ヒト遺伝子のクラスタリング: 遺伝子データの類似性は、集団構造を推測するためのクラスタリングで使用されます。

薬

医療画像: PETスキャンでは、クラスター分析を使用して、さまざまな目的で3次元画像内の異なる種類の組織を区別することができます。 ^[59]
抗菌活性の分析: クラスター分析は、抗生物質耐性のパターンを分析し、抗菌化合物をその作用機序に応じて分類し、抗生物質をその抗菌活性に応じて分類するために使用できます。
IMRTセグメンテーション: クラスタリングを使用すると、フルエンスマップを個別の領域に分割し、MLC ベースの放射線療法で配信可能なフィールドに変換できます。

ビジネスとマーケティング

市場調査: クラスター分析は、市場調査において、アンケートやテストパネルから得られた多変量データを扱う際に広く利用されています。市場調査担当者は、クラスター分析を用いて、一般消費者集団を市場セグメントに分割し、異なる消費者／潜在顧客グループ間の関係性をより深く理解します。また、市場セグメンテーション、製品ポジショニング、新製品開発、テスト市場の選定にも活用されます。
買い物アイテムのグループ化: クラスタリングは、Web上で入手可能なすべてのショッピングアイテムを、固有の製品セットにグループ化するために使用できます。例えば、eBayのすべてのアイテムを固有の製品にグループ化できます（eBayにはSKUの概念はありません）。

ワールドワイドウェブ

ソーシャルネットワーク分析: ソーシャルネットワークの研究では、クラスタリングは大規模なグループ内のコミュニティを認識するために使用されることがあります。
検索結果のグループ化: ファイルとウェブサイトをインテリジェントにグループ化するプロセスにおいて、クラスタリングは、Googleのような通常の検索エンジンと比較して、より関連性の高い検索結果セットを作成するために使用される場合があります^{[要出典] 。現在、}ClustyなどのWebベースのクラスタリングツールが多数存在します。また、検索語句が全く異なるものを指す場合に、より包括的な結果セットを返すためにも使用されます。検索語句のそれぞれの使用は、固有の結果クラスターに対応しており、ランキングアルゴリズムは各クラスターから上位の結果を選択することで、包括的な結果を返すことができます。^[60]
滑りやすいマップの最適化: Flickrの写真マップやその他のマップサイトでは、クラスタリングを使用してマップ上のマーカーの数を減らしています。^{[引用が必要]}これにより、処理が高速化され、視覚的な乱雑さが軽減されます。

コンピュータサイエンス

ソフトウェアの進化

クラスタリングは、分散化した機能を改革することでコード内のレガシー特性を削減するのに役立つため、ソフトウェアの進化に役立ちます。これは再構築の一形態であり、直接的な予防保守の手段となります。

画像セグメンテーション

画像セグメンテーションとは、デジタル画像を複数の意味のある領域またはセグメントに分割するプロセスです。これにより、画像の表現を簡素化または変更し、分析を容易にします。これらのセグメントは、異なるオブジェクト、オブジェクトの一部、または背景領域に対応する場合があります。目的は、画像内のすべてのピクセルにラベルを割り当て、類似した属性を持つピクセルをグループ化することです。

このプロセスは、医用画像、コンピュータービジョン、衛星画像などの分野や、顔検出や写真編集などの日常的なアプリケーションで使用されます。

画像セグメンテーションにおけるクラスタリング:

クラスタリングは画像のセグメンテーションにおいて重要な役割を果たします。ラベル付けされたデータを用いることなく、類似性に基づいてピクセルをクラスターにグループ化します。そして、これらのクラスターによって画像内のセグメントが定義されます。

画像セグメンテーションに最も一般的に使用されるクラスタリングアルゴリズムは次のとおりです。

K平均法クラスタリング：最も一般的でシンプルな手法の一つです。ピクセルは特徴空間（通常は色または輝度で定義されます）内のデータポイントとして扱われ、k個のクラスターにグループ化されます。各ピクセルは最も近いクラスターの中心に割り当てられ、中心は反復的に更新されます。
平均シフトクラスタリング：事前にクラスター数を指定する必要のないノンパラメトリックな手法。特徴空間におけるデータポイントの密集領域を特定することでクラスターを識別します。
ファジーC平均法:ピクセルを 1 つのクラスターに割り当てるk平均法とは異なり、ファジーc平均法では、各ピクセルがさまざまなメンバーシップ度を持つ複数のクラスターに属することができます。

進化アルゴリズム

クラスタリングは、進化アルゴリズムの個体群内のさまざまなニッチを識別するために使用でき、進化する種または亜種の間で生殖機会をより均等に分配することができます。

レコメンデーションシステム

レコメンデーションシステムは、個人の過去の行動や現在の嗜好に基づいて、アイテム、製品、または他のユーザーを提案します。これらのシステムは、クラスタリングアルゴリズムを使用して、同じクラスタ内の他のユーザーの嗜好や活動を分析することで、ユーザーの未知の嗜好を予測することがあります。クラスタ分析はレコメンデーションシステムの唯一のアプローチではありません。例えば、グラフ理論を活用したシステムもあります。クラスタ分析を活用したレコメンデーションアルゴリズムは、協調フィルタリング、コンテンツベースフィルタリング、そして協調フィルタリングとコンテンツベースフィルタリングのハイブリッドという3つの主要なカテゴリのいずれかに分類されることが多いです。

協調フィルタリング推奨アルゴリズム

協調フィルタリングは、ユーザーの行動、嗜好、活動に関する膨大なデータを分析し、他のユーザーとの類似性に基づいてユーザーが好むものを予測することで機能します。ユーザーがアイテムを評価するパターンを検出し、類似したユーザーまたはアイテムを明確な「近隣地域」にグループ化します。そして、同じ近隣地域内の他のユーザーによるコンテンツの評価を活用して、推奨コンテンツを生成します。このアルゴリズムは、状況に応じてユーザーベースまたはアイテムベースのいずれかのグループ化に重点を置くことができます。^[61]

コンテンツベースのフィルタリング推奨アルゴリズム

コンテンツベースフィルタリングは、アイテムの説明とユーザーの嗜好プロファイルを用いて、ユーザーが以前に好んだアイテムに類似した特徴を持つアイテムを推薦します。このフィルタリングでは、アイテムクラスター（「近隣」）の特徴ベクトル間の距離を評価します。ユーザーの過去のインタラクションは重み付けされた特徴ベクトルとして表され、これらのクラスターと比較されます。推薦は、ユーザーの嗜好との距離が最も近いと評価されたクラスターを特定することで生成されます。^[61]

ハイブリッド推奨アルゴリズム

ハイブリッド型推薦アルゴリズムは、協調フィルタリングとコンテンツベースフィルタリングを組み合わせることで、特定のユースケースの要件をより適切に満たします。場合によっては、このアプローチはより効果的な推薦につながります。一般的な戦略としては、(1)協調フィルタリングとコンテンツベースフィルタリングを別々に実行し、その結果を組み合わせる、(2)一方のアプローチにもう一方のアプローチの特定の機能を追加する、(3)両方のハイブリッド手法を1つのモデルに統合する、などが挙げられます。^[61]

マルコフ連鎖モンテカルロ法: クラスタリングは、ターゲット分布の極値を見つけて特徴付けるためによく利用されます。
異常検出: 異常/外れ値は通常、明示的または暗黙的に、データのクラスタリング構造に関して定義されます。
自然言語処理: クラスタリングは語彙の曖昧さを解決するために使用できる。^[60]
デブオプス: クラスタリングはDevOpsチームの有効性を分析するために使用されてきました。^[62]

社会科学

社会科学におけるシーケンス分析: クラスター分析は、たとえば、家族生活の軌跡、職業上のキャリア、毎日または毎週の時間の使い方のパターンを識別するために使用されます。
犯罪分析: クラスター分析は、特定の種類の犯罪の発生率が高い地域を特定するために使用できます。一定期間内に類似の犯罪が発生した地域、つまり「ホットスポット」を特定することで、法執行機関のリソースをより効果的に管理することが可能になります。
教育データマイニング: クラスター分析は、たとえば、類似した特性を持つ学校や生徒のグループを識別するために使用されます。
類型: ピュー研究所が行っているようなプロジェクトでは、世論調査データからクラスター分析を使用して、政治やマーケティングに役立つ可能性のある意見、習慣、人口統計の類型を識別します。

その他

フィールドロボティクス: クラスタリングアルゴリズムは、ロボットの状況認識に使用され、物体を追跡し、センサーデータ内の外れ値を検出します。^[63]

数理化学: 例えば、構造の類似性などを見つけるために、3000の化合物が90の位相指標の空間にクラスター化されました。^[64]

気候学: 気象条件や好ましい海面気圧の大気パターンを見つけるため。^[65]

ファイナンス: クラスター分析は株式をセクターごとに分類するために使われてきました。^[66]

石油地質学: クラスター分析は、貯留層特性を評価するために、欠落した底穴コアデータまたは欠落したログ曲線を再構築するために使用されます。

地球化学: 異なるサンプル位置における化学特性のクラスタリング。

参照

ウィキメディアコモンズには、クラスター分析に関連するメディアがあります。

特殊なタイプのクラスター分析