Was ist die Zeit-Komplexität von k-means?

Ging ich durch die k-means-Wikipedia-Seite. Basierend auf den Algorithmus, ich denke, die Komplexität ist O(n*k*i) (n = Gesamtzahl der Elemente, die k = Anzahl von cluster-iteration)

So kann sich das jemand erklären mir diese Aussage aus Wikipedia und wie ist das NP hart?

Wenn k und d (die dimension) befestigt sind, das problem exakt zu lösen O(ndk+1 log n), wo n ist die Anzahl der Personen geclustert werden.

InformationsquelleAutor parallel | 2013-09-05

  1. 17

    Es hängt davon ab, was Sie rufen k-bedeutet.

    Das problem der Suche nach dem globalen optimum der k-means Zielfunktion

    Was ist die Zeit-Komplexität von k-means?

    ist NP-schwer, wo Si ist der cluster i (und es gibt k Clustern) xj ist die d-dimensionalen Punkt im cluster Si und μi ist der Schwerpunkt (Durchschnitt der Punkte) der cluster -Si.

    Jedoch, eine Feste Anzahl t von Iterationen der standard-Algorithmus dauert nur O(t*k*n*d) für n (d-dimensionale) Punkte, wo kist die Zahl der centroide (oder Cluster). Das, was praktische Implementierungen (oft mit zufällige Neustarts zwischen den Iterationen).

    Den standard-Algorithmus entspricht nur ungefähr einem lokalen optimum der oben genannten Funktion, und so tun, alle die k-means algorithmen, die ich gesehen habe.

    InformationsquelleAutor Fred Foo

  2. 1

    Das problem ist NP-Schwer, denn es gibt ein weiteres bekanntes NP-hartes problem, das kann reduziert werden (planare) k-means problem. Haben Sie einen Blick auf das Papier die Die Planare k-means Problem NP-schwer (von Mahajan et al.) für mehr info.

    InformationsquelleAutor Dheeraj M Pai

  3. 1

    In diese Antwort, beachten Sie, dass i verwendet in der k-means-objektiven Formel und der i in der Analyse der Zeit-Komplexität von k-Mittel (das heißt, die Anzahl der Iterationen, die benötigt wird, bis Konvergenz) sind unterschiedlich.

    InformationsquelleAutor masec

Schreibe einen Kommentar