0

距離行列を入力として使用できるクラスタリングアルゴリズムを誰かが提案できますか？または、距離行列にも基づいてクラスタリングの「良さ」を評価できるアルゴリズムですか？

現在、クラスカルのアルゴリズム（http://en.wikipedia.org/wiki/Kruskal%27s_algorithm）の変更を使用して、データを2つのクラスターに分割しています。しかし、問題があります。データに個別のクラスターがない場合でも、アルゴリズムは2つのクラスターを作成し、1つのクラスターには1つの要素が含まれ、もう1つのクラスターには残りのすべてが含まれます。この場合、すべての要素を含む1つのクラスターと、空の別のクラスターが必要です。

このタイプのクラスタリングを実行できるアルゴリズムはありますか？

クラスタリングがどの程度うまく行われたか、またはデータにクラスターがいくつあるかをさらに正確に推定できるアルゴリズムはありますか？

アルゴリズムは、入力として距離（類似度）行列でのみ機能する必要があります。

4

3 に答える 3

2

または、距離行列にも基づいてクラスタリングの「良さ」を評価できるアルゴリズムですか？

KNNは、クラスタリング割り当ての「良さ」を評価するのに役立つはずです。方法は次のとおりです。

各ポイントが属するクラスター（その「クラスターラベル」）に従ってラベル付けされた距離行列が与えられます。

  1. 各点のクラスターラベルを、k最近傍分類から暗示されるクラスターラベルに対してテストします。
  2. k最近傍が代替クラスターを意味する場合、その分類された点はクラスターの全体的な「良さ」の評価を下げます。
  3. 各ピクセルからの「良さの評価」の寄与を合計して、クラスター全体の「良さの評価」の合計を取得します

k-meansクラスター分析とは異なり、アルゴリズムは分類が不十分なポイントに関する情報を返します。その情報を使用して、特定のポイントを新しいクラスターに再割り当てし、それによってクラスタリングの全体的な「良さ」を向上させることができます。

アルゴリズムはクラスターの重心の配置について何も知らないため、グローバルクラスター密度についても何も知らないため、ローカルとグローバルの両方の密度が高いクラスターを保証する唯一の方法は、k値の範囲でアルゴリズムを実行することです。 k値の範囲で良さを最大化する配置を見つける。

かなりの量のポイントについては、おそらくこのアルゴリズムを最適化する必要があります。おそらく、各ポイントに関連する最も近いポイントを追跡するためのハッシュテーブルを使用します。そうしないと、このアルゴリズムの計算にかなりの時間がかかります。

于 2010-05-30T17:07:43.117 に答える
1

クラスターの数を見積もるために使用できるいくつかのアプローチは次のとおりです。

于 2010-05-30T17:35:30.890 に答える
0

scipy.cluster.hierarchyMatlab（TM） clusterdataと同じように、3つのステップを実行します。

Y = scipy.spatial.distance.pdist( pts )  # you have this already
Z = hier.linkage( Y, method )  # N-1
T = hier.fcluster( Z, ncluster, criterion=criterion )

linkageこれは、変更されたクラスカル、dunnoである可能性があります。このSO回答 （ahem）は上記を使用しています。
クラスタリングの尺度として、半径=クラスターの中心までのrms距離は、2d/3dポイントの場合は高速で合理的です。

Npt、ndim、ncluster、hier/flatについて教えてください。クラスタリングは大きな領域であり、1つのサイズですべてに対応できるわけではありません。

于 2010-06-10T15:07:20.373 に答える