Sparsificationとは何ですか？

m個のデータポイントのm行m列の近接行列は、各ノードが他のノードにリンクされ、ノードのグループ間のエッジの重みがペアごとの近接度に従う密グラフとして定義できます。各オブジェクトには互いに類似する方法がありますが、ほとんどのデータセットでは、オブジェクトは少数のオブジェクトと非常に同じであり、他のほとんどのオブジェクトとはほとんど同じではありません。

この機能は、実際のクラスタリングプロセスを開始する前に、いくつかの低類似性（高非類似性）値を0に設定することにより、近接グラフ（行列）をスパース化するために使用できます。スパース化は、たとえば、定義されたしきい値より下（上）に同じ（非類似度）を持つすべてのリンクを分割するか、ポイントのk最近傍へのリンクのみを維持することによって実装できます。この方法は、最近傍グラフと呼ばれるものを作成します。

スパス化のメリットは次のとおりです-

データサイズが削減されます −データをクラスター化するために処理する必要のあるデータの量が大幅に削減されます。スパース化により、近接行列のエントリの99％以上が削除される可能性があります。したがって、管理できる問題のサイズが大きくなります。

クラスタリングの方がうまくいく可能性があります −スパース化メソッドは、オブジェクトの最も近い隣接オブジェクトへのリンクを維持しながら、より明確なオブジェクトへの接続を分割します。これは、オブジェクトの影響の最も近いネイバーがオブジェクト自体と同様のクラス（クラスター）に属するという最も近いネイバーの原則を維持するためです。これにより、ノイズと外れ値の影響が減少し、クラスター間の区別がファイルされます。

グラフ分割アルゴリズムを使用できます −特に並列コンピューティングと集積回路の設計の分野で、スパースグラフの最小カット分割を発見するためのヒューリスティックアルゴリズムに関する多くの作業がありました。近接グラフのスパース化により、オポッサムやカメレオンなどのクラスタリングフェーズでグラフ分割アルゴリズムを使用してグラフ分割を行うことができます。

近接グラフのスパース化は、実際のクラスタリングアルゴリズムが必要になる前の最初のステップと見なす必要があります。最良のスパース化では、近接行列を目的のクラスターに相関する接続された要素に分割したままにすることができますが、実際には、これが表示されます。

個々のエッジが2つのクラスターを接続するか、個々のクラスターが複数の切断されたサブクラスターに分割されるだけです。実際、Jarvis-PatrickとSNNが密度ベースのクラスタリングを使用すると、スパース近接グラフが変更されて新しい近接グラフが生成されることがわかります。この新しい近接グラフはスパース化できます。クラスタリングアルゴリズムは、これらすべての前処理手順の結果である近接グラフで動作します。