performance - kmeanがいつ終了するかを概算することはできますか？

Question

奇妙な質問で申し訳ありませんが、問題は、 Yaelライブラリを使用してkmeansを実行していることです。

私は128次元の約9,000,000のベクトルを取得し、1,000,000の重心を取得します。24コアのCPUで実行されており、現在何時間も実行されています。この膨大な量のデータを使用してkmeansを実行するのはこれが初めてであり、終了して後で知るのではなく、いつ終了するかを知りたいと思います。

したがって、問題は、kmeanがいつ終了するかを概算することは可能ですか？

Answer 1

よろしいですか

A）アルゴリズムはあなたの問題に適していますか？k-meansは、特にクラスターのサイズが同じであるという多くの仮定に基づいて構築されています。

B）あなたのパラメータは意味がありますか？「クラスタリング」は「1000000」に使用できますか？それは意味がありますか？これらのクラスターのうち、0個または1個の観測値のみが含まれるクラスターはいくつありますか？

ナイーブなk-means実装（および99％はナイーブ）は、を使用しますO(n*k*i)。ここnで、は観測k数、はクラスターの数、はi収束までに必要な反復の数です。したがって、明らかに1000000クラスターに大きくスケーリングします。しかし、さらに悪いことに、k-meansは、最悪の場合、テストO(k^n)割り当てになります。通常ははるかに少ないですが、明らかにこの数はクラスターの数に大きく依存します。したがって、クラスターが多いほど、収束するまで通常必要な反復回数が多くなります。