凝集型階層的クラスタリングとは何ですか？

凝集型階層的クラスタリングは、クラスターにサブクラスターがあり、連続してサブクラスターがあるなどのボトムアップクラスタリングアプローチです。クラスター内のすべてのオブジェクトを見つけることから始め、いくつかのオブジェクトが単一のクラスター内で、または明確な終了条件が必要になるまで。このタイプには、いくつかの階層的クラスタリング手法が使用されます。それらは、クラスター間の類似性の説明のみが異なります。

たとえば、AGNES（Agglomerative Nesting）と呼ばれるメソッドには、シングルリンク手法が必要であり、次のように動作します。長方形に配置されたオブジェクトのグループがあると考えてください。最初に、各オブジェクトは独自のクラスターに配置されます。したがって、クラスターは、クラスター内の最も近いオブジェクト間の最小ユークリッド距離でクラスターをマージすることを含むいくつかの原則に従って、段階的に結合されます。

階層的クラスタリングは、樹状図と呼ばれるツリーのような図を使用してグラフィカルに表示されます。この図は、クラスターとサブクラスターの関連付けと、クラスターが結合（集約ビュー）または分割（分割ビュー）された順序の両方を示します。

基本的な凝集型階層的クラスタリングアルゴリズム。

• 必要に応じて、近接行列を計算します。

• 繰り返す

• 最も近い2つのクラスターをマージします。

• 近接行列を更新して、新しいクラスターと最初のクラスター間の近接を反映します。

• クラスターが1つだけ残るまで。

クラスターの近接性は、通常、特定のタイプのクラスターで定義されます。たとえば、MIN、MAX、グループ平均など、いくつかの凝集型階層的クラスタリング手法は、クラスターのグラフベースのビューから得られます。

MINは、クラスターの近接性を、複数のクラスター内にある2つのポイントを閉じる間の近接性、またはグラフメソッドを使用して、ノードのいくつかのサブセット内の2つのノード間の最短エッジとして定義します。

または、MAXは、複数のクラスター内の最も遠い2つのポイント間の近接度をクラスター近接度と見なすか、グラフメソッドを使用して、ノードの異なるサブセット内の2つのノード間の最も高いエッジを取得します。

提示された概念凝集型階層的クラスタリングアルゴリズムには、近接行列が必要です。これには、$ \ mathrm {\ frac {1} {2} m ^ 2} $近接の倉庫が必要でした（近接行列が対称であると見なされます）。ここで、mは複数のデータポイントです。クラスターの追跡を維持するために必要なスペースは、シングルトンクラスターを除く複数のクラスター（m-1）に比例します。したがって、スペースの複雑さの合計は$ \ mathrm {O（m ^ 2）}$です。

基本的な凝集型階層的クラスタリングアルゴリズムの分析も、計算の複雑さに関して簡単です。 $ \ mathrm {O（m ^ 2）} $は、近接行列を計算するために必要です。そのステップの後、開始時にm個のクラスターがあり、すべての反復中に2つのクラスターがマージされるため、ステップ3と4を含むm-1回の反復があります。