Clustering continu

9

J'ai donc un problème auquel je suis confronté en ce qui concerne le clustering avec des données en direct et en continu. Étant donné que j'ai un ensemble de données en constante augmentation, je ne sais pas quelle est la meilleure façon d'exécuter un clustering efficace et efficace. J'ai trouvé quelques solutions possibles, notamment:

  1. Définir une limite sur le nombre de points de données à autoriser, donc chaque fois que la limite est atteinte lorsqu'un autre point de données arrive dans le point le plus ancien, il est supprimé. Essentiellement, cela suggérerait que les données plus anciennes ne sont plus suffisamment pertinentes pour nous pour nous soucier de ce que nous perdons en les jetant.

  2. Une fois qu'il y a suffisamment de données pour faire un bon regroupement, considérez cette "configuration" et à mesure que de nouveaux points arrivent, plutôt que de regrouper toutes les données, déterminez simplement à quel centre de cluster le nouveau point est le plus proche et ajoutez-le à cela. L'avantage ici est que vous pourriez éviter d'avoir à recluster sur chaque nouveau point et vous n'auriez pas à stocker tous les autres points, juste les centres de cluster, considérant ce cluster "assez bien". L'inconvénient est que la réexécution de l'algorithme avec tous les points de données depuis le début peut être plus précise.

Bien que ce soient des solutions potentielles que j'ai réfléchies, j'aimerais savoir s'il existe des techniques mieux connues pour faire face à ce problème. Je suppose que des sites comme Google ont dû y faire face (et j'espère que "ajouter plus de RAM, de serveurs et de processeurs" ou "étendre continuellement vos centres de données" ne sont pas les seules réponses disponibles).

Suresh Venkat
la source

Réponses:

9

Il y a beaucoup de travail sur le clustering de flux (ce qui est légèrement différent des méthodes en ligne, mais c'est essentiellement ce que vous voulez). La référence ci-dessus de Guha et al est très bonne, et pour une perspective plus générale sur quels types de techniques fonctionnent et quelles méthodes ont été utilisées dans le passé (à la fois heuristiques et précises), vous voudrez peut-être regarder mon enquête sur le clustering sur les flux .

Suresh Venkat
la source
7

Vous pouvez également consulter les notes des cours 14 et 15 de mon cours sur les algorithmes de flux de données.

Piotr
la source
4

J'aime l'enquête de Suresh ci-dessus et résume les différentes approches du clustering de flux. Vous ne l'avez pas demandé, mais il est possible dans certains cas, le problème est que les données continues soient vues par des serveurs distribués, il faut maintenir un clustering au centre et ne pas avoir à déplacer beaucoup de données. Voyez ici .

moi aussi
la source
bienvenue, Muthu!
Suresh Venkat