[解決済み] k-meansの時間計算量はどの程度ですか？

質問内容

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

そこで、どなたかこのWikipediaの文章を解説してください。また、このNPはどのように難しいのでしょうか？

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

どのように解決するのですか？

をどう呼ぶかによります。 k -を意味します。

の全体最適を求める問題である。 k-means（ケー・ミーンズ 目的関数

はNP困難であり、ここで Si はクラスタ i (そして、そこには k のクラスタ)。 xj は d -クラスター内の次元点 Si そして μi はクラスタのセントロイド（点の平均）です。 Si .

しかし、固定数で実行すると t の繰り返しの 標準アルゴリズム だけで済みます。 O(t*k*n*d) については n ( d -次元）の点で、ここで k はセントロイド(またはクラスタ)の数である。これは、実用的な実装で行われていることです（多くの場合、反復の間にランダムな再スタートがあります）。

標準的なアルゴリズムは、上記の関数の局所最適を近似しているだけであり、すべての k -というアルゴリズムがあります。