Cluster de la dimension des données de façon optimale?
Quelqu'un aurait-il un document qui explique comment le Ckmeans.1d.dp algorithme fonctionne?
Ou: quelle est la manière la plus optimale pour faire de clustering k-means dans une dimension?
- Google retourne la technologie. rapport Knops, Maintz, Pluim & Viergever (2004), l'optimisation unidimensionnelle de clustering k-means à l'aide de la programmation dynamique de l'Université d'Utrecht, qui n'est pas disponible en ligne. Malheureusement, le code C++ de ce module est très illisible. +1 pour une question intéressante.
- Je pense que c'est le papier que vous êtes à la recherche de: Ckmeans.1d.dp: l'optimisation des k-means dans Une Dimension Dynamique de la Programmation par Haizhou Wang et Mingzhou Chanson.
Vous devez vous connecter pour publier un commentaire.
Univariée de clustering k-means peut être résolu en O(kn) moment (déjà triés à l'entrée) basé sur des résultats théoriques sur les Monge, les matrices, mais l'approche n'est pas populaire, probablement dû à l'instabilité numérique et aussi peut-être des problèmes d'encodage.
Une meilleure option est un O(knlgn) méthode qui est maintenant mis en œuvre dans Ckmeans.1d.dp version 3.4.6. Cette mise en œuvre est aussi rapide que heuristique k-means, mais offre une garantie d'optimalité, les ordres de grandeur de mieux que heuristique k-means en particulier pour les gros k.
Le générique de la programmation dynamique de la solution par Richard Bellman (1973) ne touche pas sur les détails de la k-means problème et l'implicite d'exécution est O(kn^3).