Abstract - Hal

Classification dynamique d'un flux documentaire : une évaluation statique
préalable de l'algorithme GERMEN. Alain Lelu*, Pascal Cuxac**, Joel Johansson*
*LASELDI / Université de Franche-Comté 30 rue Mégevand - 25030 Besançon cedex prénom.nom@univ-fcomte.fr **INIST / CNRS 2 Allée du Parc de Brabois - CS 10310 - 54514 Vandoeuvre-lès-Nancy Cedex cuxac@inist.fr Abstract Data-stream clustering is an ever-expanding subdomain of knowledge
extraction. Most of the past and present research effort aims at efficient
scaling up for the huge data repositories. Our approach focuses on
qualitative improvement, mainly for "weak signals" detection and precise
tracking of topical evolutions in the framework of information watch -
though scalability is intrinsically guaranteed in a possibly distributed
implementation. Our GERMEN algorithm exhaustively picks up the whole set of
density peaks of the data at time t, by identifying the local perturbations
induced by the current document vector, such as changing cluster borders,
or new/vanishing clusters. Optimality yields from the uniqueness 1) of the
density landscape for any value of our zoom parameter, 2) of the cluster
allocation operated by our border propagation rule. This results in a
rigorous independence from the data presentation ranking or any
initialization parameter. We present here as a first step the only
assessment of a static view resulting from one year of the CNRS/INIST
Pascal database in the field of geotechnics. Résumé. 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 induites par le document présenté,
et les modifications de frontières de classes en résultant. 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
par notre règle de propagation à partir des maxima) qui la rend
indépendante de tout paramètre d'initialisation et de l'ordre d'arrivée des
données. Nous évaluerons dans un premier temps cet algorithme sous son
aspect statique, pour l'année 2003 du corpus documentaire « 10 ans de
géotechnique dans la base Pascal » (CNRS/INIST). Mots-clés : data-stream clustering, classification incrémentale. 1. Introduction
La classification automatique non supervisée (clustering) forme un domaine
de recherche en soi, avec une longue histoire, et de très nombreuses
méthodes constituant autant de variations autour de questions, parmi
d'autres, telles que : . quel(s)paramètre(s) : nombre de classes ? ou valeur d'un paramètre de
finesse d'analyse ? Seuil(s) ? . classification sur les lignes et/ou sur les colonnes d'un tableau
individus × descripteurs ? . classes strictes ? floues ? recouvrantes ? ou noyaux stricts + zones
d'influence recouvrantes + outliers ? . efficacité informatique ? passage possible à l'échelle des gisements et
flux de données actuels ? . robustesse, résistance au « bruit » ? Pour rendre compte avec exactitude des évolutions temporelles, cruciales
dans beaucoup de domaines d'application, en particulier ceux de la veille
d'information, il est nécessaire à notre avis : 1) de partir d'une base stable, c'est-à-dire d'une classification : . indépendante de l'ordre de présentation des données (exigence n°1), . indépendante des conditions initiales, que ce soit d'un choix de «
graines de classes » arbitraires ou dépendantes des données (exigence n°2), . impliquant un minimum de paramètres, un seul si possible (paramètre de «
zoom »), pour réduire l'espace des choix et tendre vers un maximum de
vérifiabilité et de reproductibilité (exigence n°3). 2) d'ajouter aux contraintes d'une bonne classification celle de
l'incrémentalité (exigence N°4), afin de saisir les évolutions au fil de
l'eau : rectifications de frontières entre classes, apparition de nouvelles
classes, voire de « signaux faibles »... Le caractère dynamique est
intrinsèquement présent dans les analyses utilisant les liens de citation
entre articles scientifiques (ou les liens hypertexte du Web). Pour qu'on
puisse parler véritablement d'incrémentalité, il faut que le résultat de la
classification soit indépendant de l'ordre des données présentées
antérieurement (exigence N°5), tout en découlant des données antérieures
par un historique pouvant faire l'objet d'interprétations. Notre démarche a donc été de concevoir une méthode où la contrainte
d'incrémentalité participerait à un tout cohérent, en vue d'aboutir à tout
instant à une classification qui ait du sens, et dont la différence de
représentation par rapport à l'instant précédent ne proviendrait que des
effets du temps, et non du mélange de ceux-ci avec la variabilité propre de
l'algorithme, ce qui n'est pas le cas avec les principales méthodes de
classification non supervisée. 2. Etat de l'art
Nous passerons rapidement en revue les principales familles de méthodes de
clustering, afin de les situer par rapport à nos exigences. Nous
signalerons au passage certains de nos travaux plus anciens qui
s'inscrivent dans ces cadres. 2.1. Méthodes hiérarchiques
Ces méthodes, divisives ou agglomératives, le plus souvent conviviales et
efficaces, satisfont à nos exigences 1 à 3 d'unicité des résultats. Mais au
regard de la qualité des partitions obtenues à un niveau donné de l'arbre,
un consensus existe pour leur préférer les méthodes à centres mobiles
(Lebart et al., 1982). Les déformations qu'impose un modèle hiérarchique de
partitions emboîtées à une réalité ayant toutes chances de se rapprocher
d'une organisation en treillis de partitions (par ex. treillis de Galois,
pour des descripteurs binaires) expliquent sans doute ce constat. 2.2. Méthodes à centres mobiles
Les méthodes procédant par agrégation autour de centres mobiles, comme les
K-means et leurs nombreuses variantes, font partie d'une famille basée sur
l'optimisation d'un indicateur numérique global de qualité de la partition,
dans laquelle prennent place les méthodes à mélanges de lois probabilistes
explicites, utilisant la procédure EM (Expectation Maximization) - pour une
revue, cf. (Buntine, 2002). Ce problème d'optimisation étant NP-difficile,
on ne sait que les faire converger vers un optimum local qui dépend de leur
initialisation (par ex. positions initiales des centres choisies
arbitrairement, ou en fonction des données), voire de l'ordre des données.
Ce qui les disqualifie vis-à-vis de notre exigence N°2 en théorie comme en
pratique - notre méthode des K-means axiales, (Lelu, 1994), fait partie de
cette famille - ; les optima locaux, à nombre de classes donné, révèlent à
peu près les même classes principales souvent triviales, mais peuvent faire
apparaître / disparaître / fusionner / éclater les classes d'effectifs
moyens ou faibles souvent les plus intéressantes. Un bon nombre de variantes incrémentales de ces méthodes ont été proposées,
dont on trouvera une revue partielle dans (Gaber et al., 2005). Beaucoup
sont issues de l'action DARPA « Topic Detection and Tracking », comme
(Binztock, Gallinari, 2002), (Chen et al., 2003). Mais toutes se
concentrent sur l'efficacité informatique pour traiter des flux de dizaines
ou centaines de milliers de dépêches d'agences, ou d'enregistrements issus
d'entrepôts de données ou d'Internet. C'est aussi dans ce cadre
d'efficacité que Simovici et al. (2005) proposent un algorithme glouton
pour optimiser un critère de qualité de partition original propre aux
descriptions par variables nominales, qui évite d'introduire (ou de faire
calculer de façon heuristique) le paramètre de nombre de classes propre à
la plupart des méthodes de cette famille. A signaler la proposition de (Saint Léger 1997) d'isoler les « descripteurs
remarquables » caractérisant globalement une période de temps, donc les
évolutions entre périodes (« termes émergents » et documents les
contenant). L'auteur construit pour chaque période un indicateur de
« pouvoir d'attraction » de chaque terme par agrégation de résultats
obtenus par une classification des termes. Mais cette classification, basée
sur plusieurs paramètres de seuil, ne présente pas de garantie d'optimalité
ou reproductibilité pratique. 2.3. Méthodes basées sur la densité
A notre connaissance, seules les méthodes basées sur la densité satisfont à
notre exigence d'unicité des résultats. Elles s'appuient sur la notion de
densité d'un nuage de points, locale par définition puisque caractérisant
le voisinage d'un point défini par un seuil de distance ou un nombre de
plus proches voisins : étant donné 1) un nuage de points multidimensionnel,
2) une définition de la densité en chaque point de cet espace, 3) la valeur
du paramètre de localité de c