空間データマイニングのクラスタリング手法は何ですか？

クラスター分析は、数年にわたって広く研究されてきた統計の一分野です。この手法を使用する利点は、概念階層などの背景知識を利用せずに、データから直接興味深い構造またはクラスターを発見できることです。

PAMやCLARAなどの統計で使用されるクラスタリングアルゴリズムは、計算の複雑さの観点から非効率的であると報告されています。効率性の懸念から、クラスター分析のためにCLARANS（ランダム化検索に基づく大規模アプリケーションのクラスタリング）と呼ばれる新しいアルゴリズムが開発されました。

PAM（メドイド周辺のパーティショニング） − n個のオブジェクトがあると想定し、PAMは最初に各クラスターの代表的なオブジェクトを見つけることによってk個のクラスターを見つけます。クラスターの中心に位置するこのような代表は、medoidとして知られています。

k個のメドイドを選択した後、アルゴリズムは、1つのオブジェクトがメドイドであり、もう1つのオブジェクトがメドイドではないように、実行可能なすべてのオブジェクトのペアを分析して、最良のメドイドの選択を繰り返し作成しようとします。クラスタリング品質の尺度は、そのような組み合わせごとに計算されます。

1回の反復での適切なポイントの選択が、次の反復のメドイドとして選択されます。 1回の反復のコストはO（k（n-k） ² です。 ）。したがって、nとkの値が大きい場合、計算上非常に非効率的です。

CLARA（大規模アプリケーションのクラスタリング） − PAMアルゴリズムとCLARAアルゴリズムの違いは、次のアルゴリズムはサンプリングに基づいていることです。データの代表として実際のデータのごく一部が選択され、PAMを使用してこのサンプルからメドイドが選択されます。

サンプルがかなりランダムな方法で選択された場合、それはデータセット全体を正しく表すため、選択された代表的なオブジェクト（medoid）は、データセット全体から選択された場合と同様になるという考え方です。

CLARAはいくつかのサンプルを抽出し、これらのサンプルから適切なクラスタリングを出力します。 CLARAは、PAMよりも高いデータセットを処理できます。各反復の複雑さはO（kS ² になります + k（n-k））、ここで、Sはサンプルのサイズです。

CLARANS（ランダム化された検索に基づく大規模なアプリケーションのクラスタリング） − CLARANSアルゴリズムは、データセットのサブセットのみを検索することでPAMとCLARAの両方を組み合わせ、任意の時点で一部のサンプルに制約されません。 CLARAは検索の各フェーズで一定のサンプルを持っていますが、CLARANSは検索のすべてのフェーズである程度のランダム性を持つサンプルを描画します。

クラスタリングフェーズは、各ノードが可能な解決策、つまりk個のメドイドのセットであるグラフを検索することとして提示できます。単一のメドイドを置き換えた後に得られたクラスタリングは、現在のクラスタリングのネイバーと呼ばれます。