Algorithme K-means++
dans Statistiques
Bonjour
Que veut dire la phrase suivante.
Je connais l'algorithme K-means++ c'est le terme scale que je ne comprends pas. Quelqu'un sait ce que ça veut dire et pourquoi c'est important ? (au point de justifier l'introduction de K-means|| en 2012)
Que veut dire la phrase suivante.
Internet a écrit:K-means++ does not scale !
Je connais l'algorithme K-means++ c'est le terme scale que je ne comprends pas. Quelqu'un sait ce que ça veut dire et pourquoi c'est important ? (au point de justifier l'introduction de K-means|| en 2012)
Réponses
-
Bonjour,
C'est une façon de dire que l'algorithme des k-moyennes est sensible au changement d'échelle. -
C'est-à-dire un changement d'échelle ?
-
Je ne connais pas le contexte de ce logiciel particulier, mais l'expression signifie généralement qu'un programme ou algorithme fonctionne de manière satisfaisante avec de petits volumes de données (nombres d'items à gérer, etc.), mais devient pratiquement ou complètement inutilisable quand ceux-ci deviennent importants. Par exemple, un serveur web peut fonctionner parfaitement avec un petit nombre de connexions par seconde, et devenir inutilisable si celui-ci augmente nettement (cf. effet Slashdot). Ou bien un algorithme en $O(n^2)$ par exemple (complexité en temps ou en occupation mémoire, peu importe), peut parfaitement convenir pour des données de petites tailles mais devenir inutilisable avec des données de grande taille. On dit alors qu'il ne « passe pas à l'échelle » (“it doesn't scale well,” ou souvent seulement “it doesn't scale”).
-
En fait le problème c'est le nombre de clusters, K-means ++ passe K fois sur l'ensemble des données. Donc si $K$ est grand et qu'il y a beaucoup de données c'est lourd. Et K-means|| passe aussi sur toutes les données mais moins de fois. Genre $\log(K)$ fois par exemple.
-
Je crois que c'est plutôt le fait que si on fait un changement d'échelle sur les données, alors le partitionnement sur les nouvelles données obtenues ne se fera peut-être pas de la même manière que sur les données initiales.
Enfin, c'est ce que je crois comprendre en lisant ce "K-means does not scale!". :-D
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.1K Toutes les catégories
- 59 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 58 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 337 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 801 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres