4

300 個のオブジェクトのクラスターを決定するために k-means クラスタリングを実装しました。私のオブジェクトにはそれぞれ約 30 の次元があります。距離は、ユークリッド メトリックを使用して計算されます。

私は知る必要がある

  1. アルゴリズムが正しく機能しているかどうかを判断するにはどうすればよいですか? 私のアルゴリズムの正しさについて何らかの考えを与えるようなグラフを持つことはできません。
  2. ユークリッド距離は距離を計算するための正しい方法ですか? 次元が 30 ではなく 100 の場合はどうなりますか?
4

4 に答える 4

11

OP の 2 つの質問は別々のトピックです (つまり、回答に重複はありません)。そのため、リストの項目 1 から順番に 1 つずつ回答していきます。

[クラスタリング] アルゴリズムが正しく機能しているかどうかを判断するにはどうすればよいですか?

k-means は、他の教師なし ML 手法と同様に、「k-means によって返されるクラスター割り当ては、k=3 または k=5 の場合により意味がありますか?」などの質問に答える診断テストの適切な選択がありません。

それでも、直感的な結果が得られ、簡単に適用できる、広く受け入れられているテストが 1 つあります。この診断指標は、まさにこの比率です。

重心間分離 /クラスター内分散

この比率の値が増加すると、クラスタリング結果の品質が向上します。

これは直感的です。これらのメトリクスの最初のものは、各クラスターが他のクラスターからどれだけ離れているかです (クラスターの中心に従って測定)。

しかし、重心間分離だけでは全体像がわかりません。なぜなら、2 つのクラスタリング アルゴリズムが同じ重心間分離を持つ結果を返す可能性があるからです。つまり、クラスターのエッジはより分離されています。2 番目のメトリックであるクラスター内分散は、これを説明します。これは、クラスターごとに計算された単なる平均分散です。

要約すると、クラスタ内分散に対する重心間分離の比率は、異なるクラスタリング アルゴリズムからの結果を比較するため、または異なる変数パラメータの下で実行された同じアルゴリズムからの結果を比較するための、迅速で一貫性のある信頼性の高い手法です。反復回数、距離メトリックの選択、重心の数 (k の値)。

望ましい結果は、密集した (小さな) クラスターであり、それぞれが他のクラスターから離れています。

計算は簡単です。

重心間分離の場合:

  • クラスター中心間のペアごとの距離を計算します。それから

  • それらの距離の中央値を計算します。

クラスター内分散の場合:

  • クラスターごとに、クラスターの中心から特定のクラスター内のすべてのデータ ポイントの距離を計算します。次

  • （クラスタごとに）上記のステップからの一連の距離の分散を計算します。それから

  • これらの分散値を平均します。

それが最初の質問に対する私の答えです。2 番目の質問は次のとおりです。

ユークリッド距離は距離を計算するための正しい方法ですか? 次元が 30 ではなく 100 の場合はどうなりますか?

まず、簡単な質問です。ユークリッド距離は、次元/機能が増加するにつれて有効なメトリックですか?

ユークリッド距離は完全にスケーラブルです。2 次元または 2000 次元で機能します。データポイントの任意のペアについて:

  • それらの特徴ベクトルを要素ごとに減算し、

  • その結果ベクトルの各項目を二乗し、

  • その結果を合計し、

  • そのスカラーの平方根を取ります。

この一連の計算のどこにもスケールが関係していません。

ただし、ユークリッド距離が問題の適切な類似度メトリックであるかどうかは、データによって異なります。たとえば、純粋に数値 (連続) ですか? または、個別の (カテゴリ) 変数も含まれていますか (たとえば、性別? M/F) ディメンションの 1 つが「現在の場所」で、200 人のユーザーのうち 100 人の値が「サンフランシスコ」で、他の 100 人の値が「」の場合ボストン"、平均して、ユーザーがカンザス州のどこかから来ているとは言えませんが、それはユークリッド距離が行うことのようなものです.

いずれにせよ、私たちはそれについて何も知らないので、データに適用して適切な類似性メトリックを特定できるように、簡単なフロー図を示します。

与えられたデータから適切な類似性指標を特定するには:

ここに画像の説明を入力

于 2011-11-14T12:33:16.823 に答える
1

合計|xi--yi|を試してみませんか 代わりに、コードで（xi --yi）^ 2の場合、それが大きな違いを生むかどうかを確認しますか？

アルゴリズムの正しさについてのアイデアを与えるグラフを作成することはできません。

いくつかの可能性：

ちなみに、scipy.spatial.cKDTree を使用すると、p = 2（ユークリッド）またはp = 1（マンハッタン、L1）で、各点の3つの最近傍を簡単に確認できます。最大20dまで高速で、128dでも早期カットオフが機能します。

追加：高次元のコサイン距離が 好きです。理由については、euclidean-distance-is-usually-not-good-for-sparse-dataを参照してください。

于 2011-11-23T10:52:15.353 に答える
1

  1. ユークリッド距離は、次元が同等で同じ縮尺である場合に適しています。1 つの次元が長さを表し、別の次元 (アイテムの重量) を表す場合、ユークリッドは加重に置き換える必要があります。

  2. 2D で作成し、画像を表示します。これは、機能するかどうかを視覚的に確認するのに適したオプションです。または、クラスターの中心を見つけて、クラスター内のすべてのアイテムがそこから離れすぎていないことを確認するなど、いくつかの健全性チェックを使用することもできます。

于 2011-11-13T06:52:38.737 に答える