algorithm - k-means の時間計算量はどれくらいですか?

Question

k-means ウィキペディアのページを調べていました。O(n*k*i)アルゴリズムに基づいて、複雑さは( n= 要素の総数、k= クラスターの反復回数) であると思います

それで、誰かがウィキペディアからのこの声明を説明してもらえますか?このNPはどのように難しいのですか?

kと(次元) が固定されている場合d、問題は時間内に正確に解決できます。ここで、はクラスター化されるエンティティの数です。O(ndk+1 log n)n

Answer 1

それは、あなたがkと呼ぶものに依存します。

k-means目的関数の大域的最適解を求める問題

は NP 困難です。ここで、 はクラスター(およびクラスターがあります)、はクラスター内の次元の点、 はクラスターの重心 (点の平均) です。SiikxjdSiμiSi

ただし、標準アルゴリズムの固定回数tの反復を実行すると、 (次元の) ポイントに対してのみかかります。ここで、 は重心 (またはクラスター) の数です。これは実際の実装で行われることです (多くの場合、反復の間にランダムな再起動があります)。O(t*k*n*d)ndk

標準アルゴリズムは、上記の関数の局所最適を近似するだけであり、私が見たすべてのk平均法アルゴリズムも同様です。

Answer 2

この回答iでは、k-means 目的の式でi使用されるものと、k-means の時間計算量 (つまり、収束までに必要な反復回数) の分析で使用されるものは異なることに注意してください。