2

私は最近、k-Means記事のシングル パス シード選択アルゴリズムを読みましたが、次のようなアルゴリズムをよく理解していません。

  1. からまでの距離DistをDist (i,j)表す距離行列を計算しますij
  2. 番目の点から他のすべての点までの距離の合計でSumvあるを見つけます。Sumv (i)i
  3. iある点を見つけてmin (Sumv)設定するIndex = i
  4. CFirst を最初の重心として追加します
  5. 各点について、 と の最も近い点の間の距離xiに設定します。D (xi)xiC
  6. からの最初の最も近い点yの距離の合計として見つけますn/kIndex
  7. 一意の整数を見つけてi、D(x1)^2+D(x2)^2+...+D(xi)^2 >= y > D(x1)^2+D(x2)^2+...+D(x(i-1))^2
  8. xiに追加C
  9. k中央になるまで手順 5 ～ 8 を繰り返します

特にステップ 6 では、同じIndex(同じポイント) を何度も使用しますか、それとも から新しく追加されたポイントを使用しCますか? ステップ 8 については、iよりも大きくする必要があり1ますか?

4

2 に答える 2

4

正直なところ、その論文を理解することについて心配する必要はありません。あまり良くありません。

  • アルゴリズムの説明が不十分です。
  • 実際には単一のパスではなく、n^2/2 のペアワイズ計算 + データを介した 1 つの追加パスを実行する必要があります。
  • おそらく O(n^2) の作業が非常に悪いため、シード選択スキームの実行時間を報告しません。
  • 彼らは、k-Means が陥る悪い解が多くない非常に単純なデータ セットを評価しています。
  • 「より良い」指標の 1 つは、シード選択が与えられた場合に k-means を実行するのに必要な反復回数です。これは興味深いメトリックですが、報告されている小さな違いは無意味です (k-means++ シードはより多くの反復になる可能性がありますが、反復ごとに行われる作業は少なくなります)、実行時間や使用する k-means アルゴリズムは報告されません。

彼らが比較している k-means++ アルゴリズムを学習して理解し、そこから履歴を読み取ることで、より多くのメリットが得られます。

彼らが何をしているのか本当に理解したいのなら、私はあなたのmatlabをブラッシュアップして、提供されたmatlabコードを読んでください. しかし、それだけの価値はありません。分位数シード選択アルゴリズムを調べると、基本的に非常に似たようなことを行っています。ポイントをソートするために最初のシードまでの距離を使用する代わりに、ペアごとの距離の合計を使用しているように見えます (つまり、最初のシードが必要ないため、一意のソリューションになります)。

于 2013-07-03T03:11:58.427 に答える
-1

シングル パス シード選択アルゴリズムは、新しいアルゴリズムです。シングルパスとは、反復なしで最初のシードを選択できることを意味します。k-means++ のパフォーマンスは最初のシードに依存します。それはSPSSで克服されます。同じ著者の論文「k-means のロバスト シード選択アルゴリズム」を参照してください。

ジョン・J・ルイス

于 2014-02-12T06:24:53.770 に答える