Qualcuno ha un foglio che spiega come funziona l'algoritmo Ckmeans.1d.dp?Raggruppa i dati unidimensionali in modo ottimale?
Oppure: qual è il modo più ottimale per fare k-significa il clustering in una dimensione?
penso che questo sia il documento che state cercando:
Esistono wrapper Python scritti per l'algoritmo Wang e Song? Indicano nel documento che la loro "implementazione" R è solo un wrapper su un'implementazione C++. –
È molto vecchia tecnica Bellman: Una nota sulla analisi dei cluster e programmazione dinamica http://www.sciencedirect.com/science/article/pii/0025556473900072
www.informationgeometry.org
Salve e benvenuti allo Stack Overflow. Si prega di notare che mentre la risposta rimane qui, il link e il suo contenuto potrebbero cambiare o essere rimosso. Si prega di modificare il codice per includere le informazioni rilevanti da quel collegamento. – Noich
Univariata k-means può essere risolto in O (kn) Tempo (su input già ordinati) in base ai risultati teorici sulle matrici Monge, ma l'approccio non era molto popolare molto probabilmente a causa dell'instabilità numerica e forse anche delle sfide di codifica.
Un'opzione migliore è un metodo O (knlgn) che è ora implementato in Ckmeans.1d.dp versione 3.4.6. Questa implementazione è veloce quanto l'euristica k-significa, ma offre l'ottimalità garantita, ordini di grandezza migliori di euristici k-significati specialmente per k di grandi dimensioni.
La soluzione di programmazione dinamica generica di Richard Bellman (1973) non tocca le specifiche del problema di k-means e il runtime implicito è O (kn^3).
Google rivela la tecnologia. report Knops, Maintz, Pluim & Viergever (2004), Optimal unidimensionale k-means clustering utilizzando la programmazione dinamica dell'Università di Utrecht, che non è disponibile online. Sfortunatamente, il codice C++ di questo modulo è molto illeggibile. +1 per una domanda interessante. –