0

ここに画像の説明を入力k-means アルゴリズムの複雑さはO( n * K * I * d ) であることは誰もが知っています。

  1. n = ポイント数
  2. K = クラスタ数
  3. I = 反復回数
  4. d = 属性の数

しかし、私の質問は、動的計画法で K-means を適用するときに、その複雑さを理解できないということです。

一言で言えば、 DPを使用したK-meansのアイデアは次のとおりです。

  • 近接行列を計算する
  • 各データポイントをクラスターにする
  • 繰り返す
    • 最も近い 2 つのクラスターをマージする
    • 近接行列を更新する
  • クラスターが1つになるまで

疑似コードを見つけようとしたので、複雑さを見つけようとしましたが、できませんでした。

では、どうすればその複雑さを見つけることができますか? そしてそれは何でしょうか？

回答をいただきありがとうございます。

4

1 に答える 1

1

あなたが説明しているアルゴリズムは、動的計画法の k-means ではなく、むしろagglomerative clusteringと呼ばれる階層的クラスタリングの一種です。通常、凝集クラスタリングの実装には時間 (IIRC) O(n 3 d) がかかります。ここで、n はデータ ポイントの数、d は特徴の数です。ウィキペディアは、これがどのように機能するかについてもう少し詳しく説明しています。

この方法で見つかったクラスターは、k-means で得られるクラスターと同じではないことに注意してください。凝集クラスタリングは、異なるプロパティ セットを持つ非常に異なるクラスターを生成する傾向があります。

お役に立てれば！

于 2013-01-06T04:20:10.520 に答える