K-signifie: combien d'itérations dans des situations pratiques?

10

Je n'ai pas d'expérience dans l'industrie de l'exploration de données ou des mégadonnées, donc j'aimerais vous entendre partager votre expérience.

Les gens exécutent-ils réellement k-means, PAM, CLARA, etc. sur un très grand ensemble de données? Ou bien ils en choisissent simplement un échantillon au hasard? S'ils ne prennent qu'un échantillon de l'ensemble de données, le résultat serait-il fiable si l'ensemble de données n'est pas normalement distribué?

Dans des situations pratiques lors de l'exécution de ces algorithmes, pouvons-nous dire combien d'itérations cela prendrait normalement jusqu'à ce que la convergence se produise? Ou le nombre d'itérations augmente toujours avec la taille des données?

Je pose cette question car je pense à développer une approche pour terminer les algorithmes itératifs avant la convergence, et pourtant les résultats sont toujours acceptables. Je pense que cela vaut la peine d'essayer si le nombre d'itérations est, disons, supérieur à 1 000, afin que nous puissions économiser du temps et des coûts de calcul. Qu'est-ce que tu penses?

clustering data-mining k-means convergence large-data foo
la source
number of iterations always grow with the data sizePas nécessairement.
ttnphns
Il existe différents critères pour arrêter les itérations dans K-means. Fait intéressant, il suffit de définir le nombre d'itérations sur une valeur fixe (par exemple, 10 ou 20) parmi les moyens raisonnables. K-means est dédié à être une méthode rapide, donc si vous voulez qu'un critère de convergence soit vérifié après chaque itération, ce critère doit être facile / rapide à calculer.
ttnphns
1
Existe-t-il un moyen "scientifique" de déterminer le nombre maximum d'itérations à exécuter?
foo
Votre dernier commentaire est une bonne question. Honnêtement, je ne sais pas. peut-être que d'autres personnes y répondent.
ttnphns

Réponses:

6

  1. K-means est bon marché. Vous pouvez vous permettre de l'exécuter pour de nombreuses itérations.

  2. Il y a de mauvais algorithmes (le standard) et de bons algorithmes. Pour de bons algorithmes, les itérations ultérieures coûtent souvent beaucoup moins de 1% de la première itération.

  3. Les implémentations sont vraiment lentes. Ne les utilisez pas.

  4. K-means sur les "big" data n'existe pas. Parce que cela ne fonctionne que sur des données vectorielles de faible dimension. Vous ne dépasserez pas la mémoire d'un serveur moderne avec de telles données. oui, des données plus importantes existent - mais vous ne pouvez pas utiliser k-means sur un mois de données Twitter, par exemple, car cela ne vous donnera rien d'utile.

Avec une bonne implémentation, sur un serveur moderne, le plus grand ensemble de données que vous pouvez trouver où k-means donne toujours un résultat utile a probablement besoin de moins d'une minute pour calculer jusqu'à la convergence. Alors pourquoi s'embêter à penser à une limite d'itération?

A QUIT - Anony-Mousse
la source
1
Se mettre d'accord. Dans cet article ( Scalable K-Means par classement retrieval ), les auteurs ont déclaré que K-means converge après 20 à 50 itérations dans toutes les situations pratiques, même sur des ensembles de données de grande dimension comme ils l'ont testé. Donc, à part K-means, connaissez-vous un algorithme qui prend un grand nombre d'itérations jusqu'à la convergence?
foo
Peut-être la formation d'un SVM? Je pense que c'est itératif, en essayant de trouver le meilleur (et le plus petit, car la prédiction dépend de cela!) Ensemble de vecteurs de support.
A QUIT - Anony-Mousse
La solution évidente pour exécuter k-means sur des ensembles de données de haute dimension est d'exécuter d'abord PCA ou une autre méthode de réduction de dimensionnalité, puis d'exécuter k-means
nico