Loading article…
クラスタ分析（またはクラスタリング）とは、一連のオブジェクトをグループに分割することを目的としたデータ分析手法であり、同じグループ（クラスタと呼ばれる）内のオブジェクトは、他のグループ（クラスタ）内のオブジェクトよりも互いに（分析者が定義する特定の意味で）高い類似性を示すようにするものです。これは探索的データ分析の主要なタスクであり、統計的データ分析の一般的な手法でもあり、パターン認識、画像解析、情報検索、バイオインフォマティクス、データ圧縮、コンピュータグラフィックス、機械学習など、多くの分野で使用されています。
クラスタ分析とは、特定のアルゴリズムではなく、アルゴリズムとタスクの集合を指します。クラスタを構成する要素や効率的な検出方法の理解が大きく異なる様々なアルゴリズムによって実現されます。クラスタの一般的な概念としては、クラスタメンバー間の距離が小さいグループ、データ空間の密集領域、区間、特定の統計分布などが挙げられます。したがって、クラスタリングは多目的最適化問題として定式化できます。適切なクラスタリングアルゴリズムとパラメータ設定（使用する距離関数、密度閾値、期待されるクラスタ数などのパラメータを含む）は、個々のデータセットと結果の用途によって異なります。クラスタ分析自体は自動的なタスクではなく、試行錯誤を伴う知識発見または対話型多目的最適化の反復プロセスです。結果が望ましい特性を達成するまで、データの前処理とモデルパラメータを修正する必要がある場合がよくあります。
クラスタリングという用語の他に、自動分類、数値分類、植物学（ギリシャ語のβότρυς 「ブドウ」に由来）、類型分析、コミュニティ検出など、類似の意味を持つ用語が数多く存在する。微妙な違いは、結果の利用方法にあることが多い。データマイニングでは、結果として得られるグループ自体が関心の対象となるのに対し、自動分類では、結果として得られる識別力が関心の対象となる。
クラスター分析は、1932年にドライバーとクローバーによって人類学で始まり[ 1 ] 、 1938年にジョセフ・ズービン[ 2 ]、1939年にロバート・トライオン[ 3 ]によって心理学に導入され、 1943年からキャッテル[ 4 ]によって性格心理学における特性理論の分類に有名に使用されました。
「クラスター」という概念は厳密に定義できないため、クラスタリングアルゴリズムが多数存在する理由の一つとなっています。[ 5 ]共通の要素は、データオブジェクトのグループです。しかし、研究者によって採用されるクラスターモデルは異なり、それぞれのクラスターモデルに対して異なるアルゴリズムが存在します。異なるアルゴリズムによって発見されるクラスターの概念は、その特性において大きく異なります。これらの「クラスターモデル」を理解することが、様々なアルゴリズム間の違いを理解する鍵となります。代表的なクラスターモデルには、以下のようなものがあります。
「クラスタリング」とは、基本的にそのようなクラスターの集合であり、通常はデータセット内のすべてのオブジェクトを含みます。さらに、クラスタ間の関係、例えば、互いに埋め込まれた階層構造などを指定することもできます。クラスタリングは、おおまかに次のように分類できます。
さらに細かい区別も可能です。例えば、以下のようなものがあります。
上記のように、クラスタリングアルゴリズムはクラスタモデルに基づいて分類できます。公開されているクラスタリングアルゴリズムは100種類以上あるため、以下の概要では最も代表的な例のみを紹介します。すべてのアルゴリズムがクラスタモデルを提供しているわけではないため、簡単に分類できるとは限りません。Wikipediaで説明されているアルゴリズムの概要は、統計アルゴリズムの一覧で確認できます。
客観的に「正しい」クラスタリングアルゴリズムは存在しませんが、指摘されているように、「クラスタリングは見る人の目次第」です。[ 5 ]実際、クラスタリングに対する公理的アプローチは、どのクラスタリング手法も、スケール不変性（距離の比例スケーリングの下で結果が変化しないこと）、豊富さ（データの可能なすべての分割が達成できること）、および距離とクラスタリング構造の一貫性という3つの基本的な特性を同時に満たすことは不可能であることを示しています。[ 7 ]特定の問題に最も適したクラスタリングアルゴリズムは、あるクラスタモデルを別のクラスタモデルよりも優先する数学的な理由がない限り、多くの場合、実験的に選択する必要があります。ある種類のモデル用に設計されたアルゴリズムは、根本的に異なる種類のモデルを含むデータセットでは一般的に失敗します。[ 5 ]例えば、k-meansは非凸クラスタを見つけることができません。[ 5 ]ほとんどの従来のクラスタリング手法は、クラスタが球形、楕円形、または凸形を示すことを前提としています。[ 8 ]
接続性に基づくクラスタリング（階層型クラスタリングとも呼ばれる）は、オブジェクトは遠くにあるオブジェクトよりも近くにあるオブジェクトとより関連性が高いという考えに基づいています。これらのアルゴリズムは、オブジェクト間の距離に基づいてオブジェクトを接続することでクラスタを形成します。クラスタは、その要素を接続するために必要な最大距離という観点から理解することができます。
距離の閾値が異なると、異なるクラスターグループが出現します。これらのグループは、距離が増加するにつれてクラスターがどのように統合されるかを示す樹状図であるデンドログラムを使用して視覚化できます。これが「階層的クラスタリング」という用語の由来です。つまり、データセットを単一のパーティションに分割するのではなく、アルゴリズムは異なる距離で統合されるクラスターの階層構造を構築します。デンドログラムでは、y軸はクラスターが統合される距離を示し、x軸はクラスターが連続した枝のように見えるようにオブジェクトを配置します。
接続性に基づくクラスタリングは、クラスタ間の距離の計算方法が異なる一連の手法です。ユーザーは距離関数を選択するだけでなく、クラスタ間の距離の計算方法を決定する連結基準も選択する必要があります。一般的な連結基準には、単連結クラスタリング（点間の最小距離）、完全連結クラスタリング（最大距離）、UPGMAまたはWPGMA（平均距離に基づく平均連結）などがあります。階層的クラスタリングは、凝集型（個々の要素から始めてそれらをマージする）または分割型（データセット全体から始めてそれを分割する）のいずれかになります。
凝集型階層クラスタリングでは、アルゴリズムは通常、次のように進行します。
このプロセスでは、単一の最終結果ではなく、考えられるクラスタリングの完全な階層構造が生成されます。デンドログラムでカットレベルを選択することで、形成されるクラスタの数を決定することができ、特定のクラスタリングを得ることができます。
これらの手法はデータセットの一意な分割を生成するのではなく、ユーザーが適切なクラスターを選択する必要のある階層構造を生成します。また、外れ値にも敏感で、外れ値は別のクラスターとして現れたり、他のクラスターを結合させたりする可能性があります。この効果は、特に単連結クラスタリングにおいて、「連鎖現象」として知られています。一般的に、複雑さは凝集クラスター化と分割型クラスタリングの場合、[ 10 ]大規模データセットでは計算コストが高くなります。いくつかの特殊なケースでは、より効率的な方法（計算量は少ない）単連結クラスタリングにはSLINK [ 11 ] 、完全連結クラスタリングにはCLINK [ 12 ]など、既知の手法がある。
重心ベースのクラスタリングでは、各クラスタは中心ベクトルで表されますが、この中心ベクトルは必ずしもデータセットの要素であるとは限りません。クラスタ数をkに固定した場合、k平均クラスタリングは最適化問題として正式に定義されます。すなわち、 k個のクラスタ中心を見つけ、クラスタからの二乗距離が最小になるように、オブジェクトを最も近いクラスタ中心に割り当てます。
最適化問題自体はNP困難であることが知られており、そのため一般的なアプローチは近似解のみを探索することです。特に有名な近似法はロイドのアルゴリズム[ 13 ]で、単に「 k-meansアルゴリズム」と呼ばれることが多い（ただし、この名前を導入したのは別のアルゴリズムである）。しかし、これは局所最適解しか見つけることができず、通常は異なるランダムな初期化で複数回実行されます。k-meansのバリエーションには、複数回の実行で最良のものを選択するなどの最適化だけでなく、重心をデータセットのメンバーに制限する（k -medoids ）、中央値を選択する（k -mediansクラスタリング）、初期中心をよりランダムに選択する（k -means++）、またはファジークラスタ割り当てを許可する（ファジーc-means）などのものも含まれます。
ほとんどのk平均法アルゴリズムでは、クラスタ数kを事前に指定する必要があり、これはこれらのアルゴリズムの最大の欠点の1つと考えられています。さらに、これらのアルゴリズムは、常に最も近い重心にオブジェクトを割り当てるため、ほぼ同じサイズのクラスタを好みます。その結果、クラスタの境界が不適切に分割されることがよくあります。これは主に、アルゴリズムがクラスタ境界ではなくクラスタ中心を最適化するためです。重心ベースのクラスタリングアルゴリズムの手順は次のとおりです。
K平均法には、いくつかの興味深い理論的特性があります。まず、データ空間をボロノイ図と呼ばれる構造に分割します。次に、概念的には最近傍分類に近く、そのため機械学習で広く用いられています。さらに、モデルベースクラスタリングの一種と見なすことができ、ロイドのアルゴリズムは、後述するこのモデルに対する期待値最大化アルゴリズムの一種と見なすことができます。
以下の擬似コード[ 14 ]は、 k -meansの標準的な反復改良形式を説明しています。このアルゴリズムは、各点を最も近い重心でラベル付けする割り当てステップと、割り当てられた点の平均として各重心を再計算する更新ステップを交互に繰り返します。有限回の反復で収束が保証されますが、結果は局所最適解になる可能性があります。
入力:データセット重心の初期化最大反復回数 のために # クラスタ割り当て のために # 重心位置を更新 のために # 最終的なクラスタ割り当てを更新します のために出力:最適な重心と割り当て [ 14 ]
k - means法やk -medoids法などの重心ベースのクラスタリング問題は、オペレーションズリサーチや計算幾何学の分野でよく知られている、容量制約のない計量的な施設配置問題の特殊なケースです。基本的な施設配置問題（より複雑な設定をモデル化した多くのバリエーションが存在します）では、与えられた顧客群に最適なサービスを提供する倉庫の最適な場所を見つけることが課題となります。「倉庫」をクラスタの重心、「顧客の位置」をクラスタリング対象のデータと見なすことができます。これにより、施設配置に関する文献で確立されたアルゴリズムによる解決策を、今回検討する重心ベースのクラスタリング問題に適用することが可能になります。
統計学に最も密接に関連するクラスタリング手法は、分布モデルに基づくモデルベースクラスタリングです。この手法では、データは複数の確率分布の混合から生じるものとしてモデル化されます。クラスタの数、使用するクラスタリング手法やモデル、外れ値の検出と対処方法など、様々な疑問に対して、原理に基づいた統計的な回答が得られるという利点があります。
これらの手法の理論的基盤は優れているものの、モデルの複雑さに制約を設けない限り、過学習の問題を抱えています。より複雑なモデルは通常、データをより良く説明できるため、適切なモデルの複雑さを選択することは本質的に困難です。標準的なモデルベースのクラスタリング手法には、共分散行列の固有値分解に基づく、より簡潔なモデルが含まれており、過学習とデータへの忠実性のバランスが取れています。
代表的な手法の一つに、ガウス混合モデル（期待値最大化アルゴリズムを使用）があります。この手法では、データセットは通常、固定数（過学習を避けるため）のガウス分布でモデル化されます。これらの分布はランダムに初期化され、パラメータはデータセットによく適合するように繰り返し最適化されます。この最適化は局所最適解に収束するため、複数回実行すると異なる結果が得られる場合があります。ハードクラスタリングを行うには、オブジェクトが最も属する可能性の高いガウス分布に割り当てられることがよくありますが、ソフトクラスタリングの場合は、この処理は不要です。
分布ベースのクラスタリングは、属性間の相関関係や依存関係を捉えることができる、複雑なクラスタモデルを生成します。しかし、これらのアルゴリズムはユーザーに余分な負担をかけます。多くの実際のデータセットでは、簡潔に定義された数学モデルが存在しない場合があります（例えば、ガウス分布を仮定することは、データに対するかなり強い仮定です）。
密度ベースのクラスタリングでは、[ 15 ]クラスタはデータセットの残りの部分よりも密度が高い領域として定義されます。クラスタを分離するために必要な疎な領域のオブジェクトは、通常、ノイズと境界点とみなされます。
最も一般的な密度ベースのクラスタリング手法はDBSCANです[ 16 ] [ 17 ]。多くの新しい手法とは異なり、DBSCANは「密度到達可能性」と呼ばれる明確に定義されたクラスタモデルを特徴としています。リンケージベースのクラスタリングと同様に、特定の距離閾値内の点を接続することに基づいています。ただし、密度基準を満たす点のみを接続します。元のバリアントでは、この半径内の他のオブジェクトの最小数として定義されています。クラスタは、密度で接続されたすべてのオブジェクト（他の多くの手法とは異なり、任意の形状のクラスタを形成できます）と、これらのオブジェクトの範囲内にあるすべてのオブジェクトで構成されます。DBSCANのもう1つの興味深い特性は、その複雑さがかなり低いこと（データベースに対する範囲クエリの線形数が必要）と、各実行で基本的に同じ結果（コア点とノイズ点については決定論的ですが、境界点についてはそうではありません）が発見されるため、複数回実行する必要はありません。OPTICS [ 18 ]はDBSCANの一般化であり、範囲パラメータの適切な値を選択する必要性を排除しています。、そしてリンケージクラスタリングの結果に関連する階層的な結果を生成します。DeLi-Clu、[ 19 ] Density-Link-Clusteringは、単連結クラスタリングとOPTICSのアイデアを組み合わせ、パラメータを完全に最適化し、 Rツリーインデックスを使用することでOPTICSよりもパフォーマンスを向上させています。HDBSCAN [ 20 ]は、DBSCANを階層型クラスタリングアルゴリズムに変換し、クラスタの安定性に基づいてフラットクラスタリングを抽出する手法を使用することで、DBSCANを拡張しています。
DBSCANとOPTICSの主な欠点は、クラスタ境界を検出するために何らかの密度低下を前提としている点です。例えば、人工データでよく見られるような、重なり合うガウス分布を持つデータセットでは、クラスタ密度が連続的に減少するため、これらのアルゴリズムによって生成されるクラスタ境界はしばしば恣意的に見えます。ガウス分布の混合からなるデータセットでは、これらのアルゴリズムは、このようなデータを正確にモデル化できるEMクラスタリングなどの手法にほぼ常に劣ります。
平均シフトは、カーネル密度推定に基づいて各オブジェクトをその近傍で最も密度の高い領域に移動させるクラスタリング手法です。最終的に、オブジェクトは密度の局所最大値に収束します。k-meansクラスタリングと同様に、これらの「密度アトラクター」はデータセットの代表として機能しますが、平均シフトはDBSCANと同様に任意の形状のクラスタを検出できます。反復手順と密度推定のコストが高いため、平均シフトは通常、DBSCANやk-Meansよりも低速です。さらに、カーネル密度推定の滑らかでない挙動によりクラスタの裾が過度に断片化されるため、平均シフトアルゴリズムの多次元データへの適用が妨げられます。[ 19 ]
グリッドベースの手法は、多次元データセットに使用されます。[ 21 ]この手法では、グリッド構造を作成し、グリッド（セルとも呼ばれる）上で比較を実行します。グリッドベースの手法は高速で、計算複雑度が低いのが特徴です。グリッドベースのクラスタリング手法には、STINGとCLIQUEの2種類があります。グリッドベースのクラスタリングアルゴリズムの手順は以下のとおりです。
ビッグデータの処理ニーズが高まるにつれ、生成されたクラスタの意味を犠牲にしてパフォーマンスを向上させる意欲が高まっています。そのため、既存のアルゴリズムのパフォーマンス向上に力が注がれてきました。[ 22 ] [ 23 ]その中には、CLARANS[24]やBIRCH[25]などがあります。これにより、巨大なデータセットを効率的に処理できるキャノピークラスタリングなどの事前クラスタリング手法が開発されましたが、結果として得られる「クラスタ」は、k-meansクラスタリングなどの既存の低速な手法でパーティションを分析するためのデータセットの粗い事前分割にすぎません。
高次元データの場合、多くの手法は次元の呪いによって失敗します。これは、高次元空間では特定の距離関数が問題となるためです。このため、高次元データ用のクラスタリングアルゴリズムでは、部分空間クラスタリング（一部の属性のみが使用され、クラスタモデルにはクラスタに関連する属性が含まれる）と、属性の相関を与えることでモデル化できる任意の回転（「相関」）部分空間クラスタも探す相関クラスタリングに重点が置かれています。 [ 26 ]このようなクラスタリングアルゴリズムの例としては、CLIQUE [ 27 ]とSUBCLU [ 28 ]があります。
密度ベースのクラスタリング手法（特にDBSCAN/OPTICSアルゴリズムファミリー）のアイデアは、部分空間クラスタリング（HiSC、[ 29 ]階層的部分空間クラスタリングおよびDiSH [ 30 ]）および相関クラスタリング（HiCO、[ 31 ]階層的相関クラスタリング、「相関接続性」を使用する4C [ 32 ]および階層的密度ベースの相関クラスタを探索するERiC [ 33 ]）に適用されています。
相互情報量に基づくいくつかの異なるクラスタリングシステムが提案されている。1つはMarina Meilăの情報メトリックの変種である[ 34 ] 。もう1つは階層的クラスタリングを提供する[ 35 ] 。遺伝的アルゴリズムを使用すると、相互情報量を含むさまざまな適合関数を最適化できる[ 36 ] 。また、コンピュータサイエンスと統計物理学の最近の発展である信念伝播は、新しいタイプのクラスタリングアルゴリズムの作成につながった[ 37 ] 。
クラスタリング結果の評価（または「検証」）は、クラスタリング自体と同じくらい難しい。[ 38 ]一般的なアプローチには、クラスタリングを単一の品質スコアにまとめる「内部」評価、クラスタリングを既存の「正解」分類と比較する「外部」評価、人間の専門家による「手動」評価、および意図されたアプリケーションでのクラスタリングの有用性を評価する「間接」評価がある。 [ 39 ]
内部評価尺度は、それ自体がクラスタリング目的と見なせる関数を表しているという問題を抱えている。たとえば、シルエット係数でデータセットをクラスタリングすることはできるが、これを行うための効率的なアルゴリズムは知られていない。このような内部尺度を評価に使用すると、最適化問題の類似性を比較することになり、[ 39 ]必ずしもクラスタリングがどれほど有用かを比較するわけではない。
外部評価にも同様の問題点があります。もし「正解」ラベルがあればクラスタリングは不要になりますが、実際のアプリケーションでは通常そのようなラベルは存在しません。一方で、ラベルはデータセットの可能な分割方法の一つを反映しているに過ぎず、別の、あるいはより優れたクラスタリングが存在しないとは限りません。
したがって、これらのアプローチのいずれも、クラスタリングの実際の品質を最終的に判断することはできませんが、これには人間の評価が必要です[ 39 ]。これは非常に主観的です。それにもかかわらず、このような統計は悪いクラスタリングを特定するのに非常に役立つ可能性があります[ 40 ]が、主観的な人間の評価を軽視すべきではありません[ 40 ] 。
クラスタリング結果がクラスタリングされたデータ自体に基づいて評価される場合、これは内部評価と呼ばれます。これらの方法は通常、クラスタ内の類似性が高く、クラスタ間の類似性が低いクラスタを生成するアルゴリズムに最高のスコアを割り当てます。クラスタ評価で内部基準を使用する欠点の1つは、内部尺度で高いスコアが必ずしも効果的な情報検索アプリケーションにつながるわけではないことです。[ 41 ]さらに、この評価は同じクラスタモデルを使用するアルゴリズムに偏っています。たとえば、k-meansクラスタリングは自然にオブジェクト間の距離を最適化するため、距離ベースの内部基準では結果として得られるクラスタリングを過大評価する可能性があります。
したがって、内部評価尺度は、あるアルゴリズムが別のアルゴリズムよりも優れたパフォーマンスを発揮する状況を把握するのに最適ですが、これはあるアルゴリズムが別のアルゴリズムよりも有効な結果を生成することを意味するものではありません。[ 5 ]このような指標によって測定される妥当性は、データセットにこの種の構造が存在するという主張に依存します。データセットに根本的に異なるモデルのセットが含まれている場合、または評価が根本的に異なる基準を測定する場合、ある種のモデル用に設計されたアルゴリズムは機能しません。[ 5 ]例えば、k-meansクラスタリングは凸クラスタしか見つけることができず、多くの評価指標は凸クラスタを前提としています。非凸クラスタを含むデータセットでは、k -meansの使用も、凸性を前提とする評価基準の使用も適切ではありません。
多くの内部評価尺度は、同じクラスター内の項目は、異なるクラスター内の項目よりも類似しているはずだという直感に基づいている。[ 42 ]： 115-121例えば、内部基準に基づいてクラスタリングアルゴリズムの品質を評価するために、次の方法を使用できます。
デイビス・ボールディン指数は、以下の式で計算できます。 ここでnはクラスターの数であり、はクラスターの中心です、は、クラスター内のすべての要素の平均距離です。重心へ、 そして重心間の距離そしてクラスター内距離が小さく（クラスター内類似度が高い）、クラスター間距離が大きい（クラスター間類似度が低い）クラスターを生成するアルゴリズムは、Davies–Bouldin 指数が低くなるため、Davies–Bouldin 指数が最小のクラスターの集合を生成するクラスタリング アルゴリズムが、この基準に基づく最良のアルゴリズムとみなされます。
Dunn 指数は、密で十分に分離されたクラスターを識別することを目的としています。これは、最小クラスター間距離と最大クラスター内距離の比として定義されます。各クラスター分割について、Dunn 指数は次の式で計算できます。[ 43 ]
ここで、d ( i , j ) はクラスターiとjの間の距離を表し、d '( k ) はクラスターk内のクラスター間距離を表します。2 つのクラスター間のクラスター間距離d ( i , j )は、クラスターの重心間の距離など、任意の距離尺度で表すことができます。同様に、クラスター内距離d '( k ) は、クラスターk内の任意の要素のペア間の最大距離など、さまざまな方法で測定できます。内部基準はクラスター内類似度が高く、クラスター間類似度が低いクラスターを求めるため、Dunn 指数が高いクラスターを生成するアルゴリズムの方が望ましいです。
シルエット係数は、同じクラスター内の要素までの平均距離と、他のクラスター内の要素までの平均距離を比較します。シルエット値が高いオブジェクトは適切にクラスタリングされているとみなされ、値が低いオブジェクトは外れ値である可能性があります。この指標はk平均クラスタリングでうまく機能し、最適なクラスター数を決定するためにも使用されます。[ 44 ]
クラスタリングにおける曲線下面積（AUCC）
このマトリックスはオブジェクトのペアを考慮します。ペア間の距離をスコアリング関数とし、ペアが同じクラスターにあるかどうかを考慮して、ペアを分割して真陽性、真陰性、偽陰性、真陰性を定義します。この指標は、期待値が0.5であることや結果の視覚化など、教師ありシナリオのAUCと同じ特性を借用しています[ 45 ]。
外部評価では、クラスタリングの結果は、既知のクラスラベルや外部ベンチマークなど、クラスタリングに使用されなかったデータに基づいて評価されます。このようなベンチマークは、事前に分類されたアイテムのセットで構成され、これらのセットは多くの場合、（専門家である）人間によって作成されます。したがって、ベンチマークセットは評価のゴールドスタンダードと考えることができます。[ 38 ]これらのタイプの評価方法は、クラスタリングが事前に決定されたベンチマーククラスにどれだけ近いかを測定します。しかし、クラスには内部構造が含まれる可能性があり、存在する属性がクラスタの分離を許可しない可能性があり、クラスに異常が含まれる可能性があるため、これが実際のデータに適切であるか、事実のグラウンドトゥルースを持つ合成データセットにのみ適切であるかどうかが最近議論されています。[ 46 ]さらに、知識発見の観点からは、既知の知識の再現が必ずしも意図した結果ではない可能性があります。 [ 46 ]メタ情報（クラスラベルなど）がクラスタリングプロセスですでに使用されている制約付きクラスタリングの特殊なシナリオでは、評価目的で情報をホールドアウトすることは自明ではありません。[ 47 ]
分類タスクを評価するために使用される変種から、いくつかの指標が採用されています。単一のデータポイントにクラスが正しく割り当てられた回数（真陽性として知られる）を数える代わりに、このようなペアカウント指標は、実際に同じクラスターに属する各データポイントのペアが同じクラスターに属すると予測されるかどうかを評価します。[ 38 ]
内部評価と同様に、外部評価の尺度もいくつか存在する。[ 42 ]： 125-129、例えば：
純度は、クラスターが単一のクラスをどの程度含んでいるかの尺度です。[ 41 ]その計算は次のように考えることができます。各クラスターについて、そのクラスター内で最も一般的なクラスのデータポイントの数を数えます。次に、すべてのクラスターについて合計を取り、データポイントの総数で割ります。正式には、あるクラスターのセットが与えられた場合、そしていくつかのクラスパーティショニングもデータポイントの純度は、次のように定義できます。
この指標はクラスター数が多いことを不利にせず、クラスター数が多いほど純度を高くすることが容易になります。各データポイントをそれぞれ独自のクラスターに入れることで、純度スコア1を常に達成できます。また、純度は不均衡データには適していません。不均衡データの場合、性能の低いクラスタリングアルゴリズムでも高い純度値が得られます。例えば、サイズ1000のデータセットが2つのクラスで構成され、一方のクラスに999ポイント、もう一方のクラスに1ポイントが含まれている場合、考えられるすべての分割において純度は少なくとも99.9%になります。
ランド指数[ 48 ]は、クラスタリングアルゴリズムによって返されたクラスタがベンチマーク分類とどれだけ類似しているかを計算します。これは、次の式を使用して計算できます。
どこは真陽性の数です。は真の陰性の数です。は偽陽性の数であり、は偽陰性の数です。ここでカウントされているインスタンスは、正しいペアワイズ割り当ての数です。つまり、は、予測されたパーティションとグラウンドトゥルースパーティションの両方で一緒にクラスタリングされている点のペアの数です。は、予測されたパーティションでは一緒にクラスタリングされているが、グラウンドトゥルースパーティションではそうではない点のペアの数などです。データセットのサイズが N の場合、ランド指数の問題点の1つは、偽陽性と偽陰性が等しく重み付けされていることです。これは、一部のクラスタリングアプリケーションでは望ましくない特性となる可能性があります。F値はこの懸念に対処しており、偶然補正調整済みランド指数も同様です。
F値は、パラメータによって再現率に重み付けすることで、偽陰性の影響をバランスさせるために使用できます。精度と再現率（いずれもそれ自体が外部評価指標である）を以下のように定義する 。 どこ精度率とはリコール率です。F値は次の式を使用して計算できます。[ 41 ] いつ、言い換えれば、リコールはF値に影響を与えない。、そして増加最終的なF値において、想起にますます大きな重みを割り当てる。または考慮されておらず、0から無限に変化する可能性があります。
ジャッカード係数は、2つのデータセット間の類似性を定量化するために使用されます。ジャッカード係数は0から1の間の値をとります。係数が1の場合は2つのデータセットが同一であることを意味し、係数が0の場合はデータセットに共通要素がないことを示します。ジャッカード係数は次の式で定義されます。 これは、両方のセットに共通する固有要素の数を、両方のセットに含まれる固有要素の総数で割ったものです。考慮されていません。
ダイス対称尺度は、無視しながら: 。
ファウルクス・マロウズ指数[ 49 ]は、クラスタリングアルゴリズムによって返されたクラスタとベンチマーク分類との類似性を計算します。ファウルクス・マロウズ指数の値が高いほど、クラスタとベンチマーク分類の類似性が高いことを示します。この指数は、次の式を使用して計算できます。 どこは真陽性の数です。は偽陽性の数であり、は偽陰性の数です。インデックスは、精度と再現率の幾何平均です。そして、また、G 尺度としても知られており、F 尺度はそれらの調和平均です。[ 50 ] [ 51 ]さらに、精度と再現率は、ウォレスの指標としても知られています。そして[ 52 ]再現率、精度、G尺度の偶然正規化バージョンは、情報量、顕著性、マシューズ相関に対応し、カッパと強い相関関係があります。[ 53 ]
カイ指数[ 54 ]は、カイ二乗統計量を適用してクラスタリング結果を測定する外部検証指標です。この指標は、ラベルがクラスタ全体で可能な限り疎であること、つまり各クラスタが異なるラベルを可能な限り少なく持つことを肯定的に評価します。カイ指数の値が高いほど、結果として得られるクラスタと使用されるラベルとの関係が強くなります。
相互情報量は、クラスタリングと正解分類の間でどれだけの情報が共有されているかを示す情報理論的な尺度であり、2 つのクラスタリング間の非線形類似性を検出できます。正規化相互情報量は、この値の偶然性を補正したバリアントのファミリーであり、クラスタ数の変化に対するバイアスが軽減されています。[ 38 ]
混同行列は、分類（またはクラスタリング）アルゴリズムの結果を素早く視覚化するために使用できます。これは、あるクラスターがゴールドスタンダードとなるクラスターとどれだけ異なるかを示します。
妥当性尺度（短縮v尺度）は、クラスターの均質性と完全性を組み合わせた指標である[ 55 ]。
クラスタ傾向を測定するとは、クラスタリング対象のデータにどの程度クラスタが存在するかを測定することであり、クラスタリングを試みる前に初期テストとして実行できます。その方法の一つは、データをランダムデータと比較することです。平均的に、ランダムデータにはクラスタは存在しないはずです。
企業や政府機関が、実世界のデータを用いて人口を分類し、意思決定を自動化するためにクラスタリングアルゴリズムをますます活用するようになるにつれ、アルゴリズムの偏りに関する懸念が高まっている。クラスタリングは教師なし学習の一種であるため、既存のデータ内のパターンを識別する。その結果、これらのモデルは、トレーニングデータセットに既に存在する歴史的な不平等を意図せず強化してしまう可能性がある。
実世界のデータに基づく教師なし学習において公平性を達成することは不可能である。なぜなら、「正しい」ものをラベル付けする真の方法がないからである。クラスタリングアルゴリズムは数学的な性質を持つが、基となるデータが歴史的および社会的な偏見を反映しているため、体系的なバイアスを受けやすい。 [ 58 ]これに対し、研究者らは、各クラスタが全体人口に対して保護対象グループのバランスの取れた表現を維持することを保証するFairletアプローチなどの「公平クラスタリング」フレームワークを開発してきた。[ 59 ]
差別的影響の法的原則の下では、アルゴリズムが表面上中立的であっても（つまり、人種や性別などの属性を明示的に使用していなくても）、保護対象集団に対して不均衡に不利な結果をもたらすプロセスは差別的であるとみなされます。[ 60 ]不公平は代理変数を通じて発生することがよくあります。たとえば、データセットから人種が取り除かれていても、クラスタリングアルゴリズムは郵便番号や学歴を特徴として使用する可能性があります。これらの変数は経済状況や民族性と密接に関連していることが多いため、結果として得られるクラスターは、これらの特性によって個人を効果的に分離することになります。
予測型警察活動におけるクラスタリングの応用は、データにおける過去の偏りがどのようにフィードバックループを生み出すかを示している。
クラスター分析は、幅広い分野におけるデータ分析に用いられている。
自然科学分野では、階層的クラスタリング、k平均法、次元削減、主成分分析（PCA）、t-SNEなどの手法が、密なデータを理解するために頻繁に用いられる。
コンピューティングおよびテクノロジーアプリケーションでは、クラスタリングは機械学習の教師なし学習の原動力であり、検索エンジンから推薦プラットフォームまで、さまざまなシステムに組み込まれています。この分野で一般的なアルゴリズムには、 k -means、DBSCAN、mean shift、スペクトルクラスタリングなどがあり、多くの場合、テキスト、画像、センサーログなどの生データを距離ベースのグループ化に適したベクトル空間にマッピングするステップである特徴抽出または埋め込みの後に実行されます。[ 70 ]
ビジネスや社会科学の分野では、クラスタリングは表形式の調査データや取引データに最もよく適用され、その目的は、人口を消費者グループに分類したり、詳細な市場分析の洞察を得たり、有権者の嗜好を明らかにしたりすることにある。
{{citation}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)