Clustering dynamique d'un flot de données : un algorithme incrémental et optimal de détection des maxima de densité
Abstract
L'extraction non supervisée et incrémentale de classes sur un flot de
données (data stream clustering) est un domaine en pleine expansion. La plupart
des approches visent l'efficacité informatique. La nôtre, bien que se prêtant
à un passage à l'échelle en mode distribué, relève d'une problématique
qualitative, applicable en particulier au domaine de la veille informationnelle :
faire apparaître les évolutions fines, les « signaux faibles », à partir des thématiques
extraites d'un flot de documents. Notre méthode GERMEN localise de
façon exhaustive les maxima du paysage de densité des données à l'instant t,
en identifiant les perturbations locales du paysage à t-1 et modifications de
frontières induites par le document présenté. Son caractère optimal provient de
son exhaustivité (à une valeur du paramètre de localité correspond un ensemble
unique de maxima, et un découpage unique des classes qui la rend indépendante
de tout paramètre d'initialisation et de l'ordre des données.