Dovremmo usare k-means ++ invece di k-means?

Question

Il k-means++ algoritmo aiuta in due punti seguenti dell'originale algoritmo k-means:

1. Il k-mezzi originale algoritmo ha il caso peggiore tempo di super-polinomiale dimensioni ingresso esecuzione, mentre k-means ++ ha rivendicato essere O (log k).
2. L'approssimazione trovata può produrre un risultato non così soddisfacente rispetto alla funzione obiettivo rispetto al clustering ottimale.

Ma ci sono degli inconvenienti di k-means ++? Dovremmo usarlo sempre al posto di k-significa d'ora in poi?

Answer 1

nessuno rivendica k-means++ ore in O (lg k) orario; la qualità della soluzione è O (lg k) -competitive con la soluzione ottimale. Entrambi k -means ++ e il metodo comune, chiamato algoritmo di Lloyd, sono approssimazioni a un problema di ottimizzazione NP-hard.

Non sono sicuro di quale sia il peggior tempo di esecuzione di k -means ++ is; si noti che nella descrizione originale di Arthur & Vassilvitskii's, i passaggi 2-4 dell'algoritmo si riferiscono all'algoritmo di Lloyd. Dicono che funziona in modo migliore e più veloce nella pratica perché parte da una posizione migliore.

Gli inconvenienti di k -Mezzi ++ sono quindi:

1. anch'esso può trovare una soluzione non ottimale (è ancora un'approssimazione).
2. Non è sempre più veloce dell'algoritmo di Lloyd (vedi Arthur & tabelle di Vassilvitskii).
3. È più complicato dell'algo di Lloyd.
4. È relativamente nuovo, mentre Lloyd's ha dimostrato che vale più di 50 anni.
5. Potrebbero esistere algoritmi migliori per spazi metrici specifici.

Detto questo, se la libreria k -Mezzi supporta k -Mezzi ++, quindi con tutti i mezzi provare.

Answer 2

Non

tua domanda, ma un facile aumento di velocità a un modo Kmeans per la grande N:

1) in primo luogo fare Kmeans su un campione casuale di dire sqrt (N) dei punti
2) quindi eseguire k pieno significa da quei centri.

Ho trovato questo 5-10 volte più veloce di kmeans ++ per N 10000, k 20, con risultati simili.
come funziona per voi dipenderà da quanto bene uno sqrt (N) del campione approssima il tutto, così come su N, dim, k, nInit, delta ...

Quali sono i tuoi N (numero dei punti dati), debole (numero di funzioni) e k?
L'enorme intervallo in N, dim, k, dati, metriche dei dati degli utenti ... per non parlare della mancanza di parametri di riferimento pubblici, rende difficile confrontare i metodi.

Aggiunto: codice Python per kmeans() e kmeanssample() è here su SO; i commenti sono ben accetti