カメレオンとは何ですか？

カメレオンは、動的モデリングを使用してクラスターのペア間の類似性を判断する階層的クラスタリングアルゴリズムです。これは、ROCKやCUREなどの2つの階層的クラスタリングアルゴリズムで観察された弱点に基づいて変更されました。

ROCKおよび関連する設計では、クラスターの近接性に関するデータを無視しながら、クラスターの相互接続性を強調しています。 CUREおよび関連する設計では、クラスターの近接性を考慮していますが、クラスターの相互接続性は無視しています。カメレオンでは、クラスターの類似性は、クラスター内の適切に接続されたオブジェクトの程度とクラスターの近接性に応じて評価されます。特に、相互接続性が高く、近接している場合、2つのクラスターが結合されます。

静的なユーザー提供モデルに基づくものではなく、結合されるクラスターの内部機能に自動的に適応できます。マージプロセスは、自然で均質なクラスターの検出をサポートし、類似度関数を定義できることを考慮して、すべてのタイプのデータに使用されます。

Chameleonは、スパースグラフを作成するためにk-nearest-neighborグラフ手法を必要とします。ここで、グラフの各頂点はデータオブジェクトを定義し、1つのオブジェクトがk-他の最も類似したオブジェクト。エッジは、オブジェクト間の類似性を反映するように重み付けされています。

Chameleonは、グラフ分割アルゴリズムを使用して、k最近傍法を多数の比較的小さなサブクラスターに分割します。これは、類似性に基づいてサブクラスターを繰り返しマージする凝集型階層クラスタリングアルゴリズムを使用できます。最も類似したサブクラスターのペアを判別でき、相互接続性とクラスターの近さの両方を考慮に入れます。

k最近傍グラフは、近傍のアプローチを動的にキャプチャします。オブジェクトの近傍半径は、オブジェクトが存在する領域の密度によって決定されます。密集したエリアでは、近隣が狭く表されます。疎領域では、より広く表現されます。

この影響により、世界中の近隣を使用するDBSCANのような密度ベースの方法と比較して、より自然なクラスターが得られます。さらに、領域の密度はエッジの重みとして記録されます。特に、密集した領域のエッジは、疎な領域のエッジよりも重くなる傾向があります。

グラフ分割アルゴリズムは、エッジカットを小さくするようにk最近傍グラフを分割します。つまり、クラスターCはサブクラスターC _iに細分されます。 およびC_j カットできるエッジの重量を最小限に抑えるために、CをC _iに二等分する必要があります およびC_j 。エッジカットはEC（C _i 、C _j ）そしてクラスターC _i間の絶対相互接続性を決定します およびC_j 。