Brevet FR2895110A1 — publié le 20070622

PROCEDE DE CLASSIFICATION NON SUPERVISEE LINEAIRE ET STABLE SUR L'ORDRE DES OBJETS L'invention concerne un procede de classification non supervisee Iineaire et stable sur I'ordre des objets. Elie concerne de maniere plus generale des techniques de classifications automatiques connues sous le terme anglais >. Elie est notamment utilisee dans les domaines du Data Mining >> et du Text Mining >> pour la decouverte, sans a priori, de connaissances (ou ) dans de grandes bases de donnees. Ces donnees peuvent titre de type structure lorsqu'il s'agit de donnees comportementales ou demographiques par exemple, ou de type non structure lorsqu'il s'agit de donnees textuelles. Partant d'une base de donnees constituee d'un ensemble (ou population) 15 de n objets decrits par un ensemble de m descripteurs (ou variables), la classification automatique consiste a structurer ces objets sous forme de classes (ou groupes) tres homogenes. Cette homogeneite traduit le fait que deux objets d'une meme classe doivent titre plus similaires (ou ressemblants) entre eux que deux objets appartenant a deux classes distinctes. 20 La constitution de ces classes permettra de detecter facilement des groupes d'objets a profils ou thematiques similaires selon qu'il s'agisse de donnees structurees ou non structurees. Ce probleme est hautement combinatoire pour titre resolu par une methode exacte. A cet effet, des heuristiques moins couteuses en temps de 25 traitements et en ressources machines ont ete elaborees pour lui trouver des solutions approchees. Certaines de ces heuristiques proposent des solutions en fixant arbitrairement le nombre de classes, tandis que d'autres, proposent une hierarchie de partitions a nombre variable de classes. 30 On peut citer, par exemple, les heuristiques suivantes : • Les methodes de type > tels que les k-means >>, les nuees dynamiques... • Les methodes de classification hierarchiques (ascendantes ou descendantes) • Les methodes de type premier representant >> ou en anglo-saxon > . Des exemples pour differentes methodes de classification non supervisee sont donnees dans les references suivantes : 1) Saporta G. (1990), Probabilites, Analyse de donnees et Statistique, Technip ; 2) Lebart et al (1995), Statistique exploratoire multidimensionnelle, Dunod ; 3) Hartigan, J. (1975), Clustering Algorithms, John Wiley and Sons, New York, NY, US. to Les methodes de type > et classification hierarchique fixent arbitrairement un nombre de classes. Quant aux methodes de type ), elles necessitent la fixation d'un seuil de similarite et sont tributaires de I'ordre dans lequel les objets sont pris en compte. En effet, elles peuvent aboutir a des resultats completement differents selon I'ordre dans lequel les objets sont 15 ranges. Neanmoins, elles permettent de traiter, dans des temps raisonnables, de grandes quantites de donnees. Cependant, pour obtenir ces performances, ces methodes necessitent la fixation d'un nombre maximal de classes tres faible par rapport au nombre d'objets. 20 Parmi les problemes majeurs rencontres, pour repondre au probleme de la classification automatique, on peut citer : • la determination du nombre de classes sous-jacent a la population consideree, • les performances en temps de traitements selon les volumetries a traiter et 25 en terme de qualite de I'homogeneite des classes obtenues, • le pouvoir d'interpretation des resultats obtenus ; definition d'indicateurs statistiques pour la mesure de I'homogeneite des classes ainsi que du pouvoir discriminant des descripteurs participants a la formation de ces classes. 30 L'idee de la presente invention repose notamment sur la theorie de ('analyse relationnelle. Pour rappel, cette theorie, telle que decrite dans rune des references suivantes : 1) P. Michaud et JF Marcotorchino, >, Mathematiques et Sciences Humaines n 67, 1979, p7-38 ; 2 ; JF Marcotorchino et P Michaud, Agregation des similarites en classification automatique >>, Revue de statistique appliquee, Vol 30, n 2, 1981, permet de repondre aux problematiques de la fixation du nombre de classes et de ('interpretation du resultat obtenu. Cependant le modele theorique sous-jacent, est extremement couteux en terme de ressources machine des que le nombre d'objets est superieur a 100. L'invention utilise une heuristique de cette theorie qui permet d'approximer tres finement le resultat theorique sur de grandes bases de donnees. L'invention concerne un procede de classification non supervisee to lineaire permettant de structurer une base de donnees composee d'objets et de descripteurs, qui est stable sur I'ordre des objets comprenant une etape prealable de transformation des donnees qualitatives, quantitatives ou textuelles en donnees binaire de presence-absence caracterise en ce qu'il comporte au moins les etapes suivantes : 15 a) determiner un seuil structure) as fonction des n2 accords entre les objets a classifier, le seuil structurel definissant un critere d'optimisation adapte aux donnees, b) utiliser les descripteurs comme generateurs de structuration et de construction d'une partition P ou ensemble de classes, 20 c) fusionner progressivement une classe engendree par un descripteur et une partition (40, 41, 42), d) pour un critere d'optimisation faisant intervenir une fonction f(C,,,G.,.) = Min(C,,lineariser des sommes de fonctions Minimums. Le procede peut comporter une etape ou I'on regroupe Ies classes de la 25 partition entre elles. L'etape de fusion c) comporte, par exemple, une etape ou I'on determine a partir de deux classes en intersection la meilleure operation (au sens de ('optimisation du critere) parmi les 4 suivantes : • Cassage ,> de la premiere classe et formation de deux classes; 30 • Cassage >> de la deuxieme classe et formation de deux classes; • Cassage >, des deux classes pour former trois classes ; • Reunion des deux classes en intersection pour former une unique classe. Le regroupement des classes d'une partition est, par exemple, effectue sur plusieurs niveaux hierarchiques et comporte les etapes suivantes : • diminuer a chaque niveau la valeur du seuil structurel de sorte que les contributions faiblement negatives puissent devenir positives, • maximiser des liens entre les classes constituees oia les liens sont determines en utilisant la contribution d'une paire d'objets Lien (Cq , Cq. )= l Contribii' = 1 Cii' ù a'x f IECgi'ECq' ieCq,ECy' avec a' la nouvelle valeur de a • regrouper deux classes dont le lien est positif, et reiterer ce processus sur tous les niveaux. L'invention concerne aussi un dispositif de classification non supervisee to lineaire permettant de structurer une base de donnees composees d'objets et de descripteurs, qui est stable sur I'ordre des objets comprenant une etape prealable de transformation des donnees qualitatives, quantitatives ou textuelles en donnees binaires de presence-absence caracterise en ce qu'il comporte au moins les elements suivants : un calculateur comprenant une memoire, une base de donnees 15 et un processeur adapte a mettre en eeuvre les Mapes du procede presentant rune des caracteristiques precedemment enoncees. L'invention possede notamment les avantages suivants : • la possibilite de detecter automatiquement le nombre de classes au cours du 20 classement, • la possibilite de traiter de grandes quantites de donnees dans des temps raisonnables, • I'independance vis a vis de I'ordre des objets de la base. Elie est naturellement stable visa vis de I'ordre de traitement des objets, 25 • le procede permet de definir et de calculer tres rapidement (complexite lineaire) des indicateurs mesurant la qualite des resultats obtenus, • le procede est stable visa vis de la duplication des objets. En d'autres termes, si on demultiplie la base plusieurs fois, on retrouve la meme solution initiale avec les objets dupliques au sein d'une meme classe. 30 D'autres caracteristiques et avantages de la presente invention apparaitront mieux a la lecture de la description ci-dessous et annexee des figures qui representent : • La figure 1, un schema correspondant a un systeme generique d'un systeme supportant le procede selon !'invention, • La figure 2, un schema fonctionnel decrivant le fonctionnement general de la chaine de traitement du domaine de la fouille de donnees appliquee a un corpus de documents ou a une base de donnees numeriques, • La figure 3, un schema fonctionnel qui montre les etapes de la phase de pretraitement qui est effectuee en amont du procede de classification automatique, • La figure 4, un schema fonctionnel qui represente I'ordonnancement des etapes constituant le procede de cette invention, • La figure 5, un schema fonctionnel qui detaille les differentes operations effectuees tors du traitement 41 de la figure 4, • La figure 6, ('operation de base qui consiste a determiner la partition locale optimale (en une, deux, ou trois classes) issue de deux classes en intersection, • La figure 7, les quantites evaluees !ors de !'operation de base decrite dans la figure 6, • La figure 8, un schema fonctionnel qui represente les etapes du procede d'agregation hierarchique des classes. La figure 1 illustre, a titre non limitatif, un exemple d'application du procede selon ('invention, permettant de generer automatiquement differentes actions a mener a partir du resultat de classification. Le systeme sur lequel fonctionne le procede comprend, par exemple, un calculateur 1 comprenant une memoire 2, un processeur 3 associe au procede de classification 5. Le calculateur 1 est en liaison avec une base de donnees 4. Le resultat de classification, se presente, par exemple, sous la forme d'un ensemble de classes memorise dans un dispositif approprie 6. Le dispositif 6 est, par exemple, en liaison avec un serveur 7 d'envoi de courrier electronique par exemple. Le serveur est pourvu de moyens de traitement appropries et connus de I'Homme du metier pour traiter ('information de classes revues et declencher des mecanismes d'envoi eventuel de messages aux personnes des classes concernees. Tout dispositif permettant de conduire et/ou de piloter des actions en fonction des resultats de la classification peut titre utilise. La description qui suit est donnee a titre illustratif dans un contexte general d'instructions executables dans un programme d'ordinateur, tels que des modules de programme executes par un ordinateur ou tout autre calculateur. L'invention peut titre mise en ceuvre sur tout type d'ordinateurs, d'agenda electronique, etc .... Dans la figure 2, le point de depart peut titre soit une base de donnees quelconque (ensemble d'individus decrits par un ensemble de variables numeriques), soit un corpus de documents quelconque. Ces deux types de donnees sont representes respectivement par les blocs arrondis 20 et 25. Dans le cas de donnees numeriques, it peut exister une phase de pretraitements facultative 21 qui consiste en des traitements statistiques classiques tels que le centrage ou la reduction des donnees ou encore des transformations... etc. Ces pre-traitements conduisent au tableau de donnees 22. C'est ce tableau qui constitue la source des traitements d'analyse de !'information 23. En ce qui concerne un corpus de documents, au cours d'une phase de pre-traitements 26 on transforme chaque texte en un vecteur dont les dimensions correspondent a des descripteurs obtenus par un procede linguistique qui peut titre une analyse morpho-syntaxique, une extraction de concepts, une extraction de co-occurrences..., des traitements linguistiques et semantiques etc. On obtient alors une matrice de presence-absence (binaire) ou de frequences 27 qui constitue la source des traitements representes par le bloc 23. Le bloc 23 correspond notamment a la phase de traitements et d'analyses des donnees. Ces traitements peuvent titre de plusieurs types (classification supervisee, classification non supervisee, notation statistique ou scoring >>, regression...). Dans le cadre de ('invention, it s'agit de classification non supervisee de donnees connue aussi sous !'appellation de classification automatique ou encore de > (terme anglo-saxon). L'invention concerne notamment un procede de classification non supervisee dont le resultat est, par exemple, une hierarchie de partitions des objets 24 ou des documents 28 selon le type de donnees initial. Les donnees d'entree de la figure 3 se presentent sous la forme d'un tableau T, 22 ou 27, designant respectivement les cas de donnees numeriques et le cas de corpus de documents, croisant ('ensemble I, constitue de n objets 01,02,...,0, (des individus ou des documents), et I'ensemble V constitue de m variables (ou descripteurs), VI , V 2,..., V m mesures sur I . I ={OI,O2,..., On} V =V"'} Le tableau T a comme terme general tik qui represente la valeur prise par la 5 variable Vk sur ('objet 0, et se presente sous la forme suivante : lm im T= Le terme general tik , des donnees en entree, represente : • la modalite de la variable k prise par I'objet i dans le cas d'une variable qualitative, 10 • la valeur de la variable k prise par I'objet i s'iI s'agit d'une variable quantitative, • Ia presence ou I'absence de ('unite lexicale k dans le document i , s'il s'agit de donnees textuelles. 15 Dans le cas des donnees qualitatives et quantitatives, le procede applique sur ce tableau des traitements de re-codage 30 decrits ci-apres, par exemple la discretisation des variables quantitatives ou le recodage des variables qualitatives en descripteurs de presence/absence. Les variables qualitatives et quantitatives sont transformees en variables binaires qui constitueront un tableau 20 K de presence-absence. Dans le cas des variables qualitatives, la transformation consiste, par exemple, en un re-codage des modalites en des vecteurs descripteurs de presence-absence. Pour des variables quantitatives, it s'agit de discretisations qui consistent 25 a transformer les variables quantitatives en variables qualitatives ou chaque modalite correspond a un intervalle. Par exemple, soit la variable quantitative taille >> exprimee en cm et mesuree sur un ensemble d'individus. Supposons que dans la population consideree, la taille des individus la constituant soit comprise entre 140 cm et 210 cm, une discretisation possible serait de decouper la variable en trois intervalles suivants [140,160[ ; [160,180[ ; [180,210]. Ces trois intervalles correspondent alors respectivement aux trois modalites suivantes : petite, moyenne et grande. Par consequent, un individu qui aura la taille 175 cm par exemple, aura apres discretisation la modalite moyenne. Le tableau K, 31, de terme general k,1 obtenu apres ces transformations sera de la forme suivante : 1ku k1, k1 K = kn ku kin k k k n1 n~ ... nn Son terme general k,1 peut avoir deux significations selon qu'il s'agisse initialement de variables qualitatives ou de variables quantitatives : Dans le cas d'une variable qualitative, k,1 a la definition suivante : k.. = 1 si l'objet i possede la modalite j l.1 0 sinon Dans le cas d'une variable quantitative, ku a la definition suivante : k.. = 1 si 1'objet i appartient au segment j ZJ 0 sinon Dans le cas des donnees textuelles, it n'y a pas d'etape de recodage puisqu'a ('issue de I'etape de pre-traitement, 26, nous obtenons deja un tableau binaire de presence-absence K dont le terme general k,1 a pour signification : 1 si le document i possede 1'unite lexicale j k`' _ 0 sinon Chaque variable du tableau T, qu'elle soit qualitative ou quantitative, engendrera plusieurs vecteurs descripteurs de presence-absence. En effet, les tableaux T et K sont de dimensions differentes. Considerons la variable (Categorie Socio-Professionnel) et supposons que I'on soit en presence de quatre individus (I1, 12, 13, 14). Supposons que les modalites possibles de la variable CSP soient : cadre, ouvrier, profession liberate. Supposons de plus, que ces quatre individus ont les modalites suivantes : Individus CSP I1 cadre 12 cadre 13 ouvrier 14 profession liberate Apres recodage des modalites de la variable qualitative CSP, on obtient le resultat suivant : CSP Individus cadre ouvrier profession liberate I1 1 0 0 12 1 0 0 13 0 1 0 14 0 0 1 Chaque modalite de la variable consideree devient donc un descripteur de presence-absence. Par consequent, le tableau des donnees transformees K sera de dimensions (nxp) avec p > m ou m est le nombre de variable de I'ensemble V. A partir du tableau K , 31, on effectue des calculs statistiques, 32 (moyennes, ecart-types, coefficients de discrimination, etc.), qui permettent notamment, dune part de parametrer le filtrage des descripteurs, 33 (elimination des descripteurs peu discriminants), d'autre part, de calculer un indicateur appele seuil structurel, 34, qui permet de s'affranchir de tout parametrage du procede de classification (non fixation ni d'un nombre de classes ni d'un nombre maximal de classes). L'indicateur est detaille par la suite. Le filtrage permet d'eliminer les descripteurs peu discriminants. 20 L'elimination des descripteurs sera differente suivant le type de ces derniers. Dans le cas de donnees numeriques on se base sur un indicateur de pertinence du descripteur. Dans le cas des documents, on utilise la frequence d'apparition d'un descripteur dans I'ensemble du corpus ou tout autre indicateur de mesure de discrimination tel que I'entropie... et on elimine ceux qui sont, a priori, peu discriminants. A Tissue de I'etape de filtrage, on a un nouveau tableau binaire reduit, 35, qui contient un nombre restreint de colonnes. C'est ce nouveau tableau qui sert de donnees en entree au procede de classification automatique decrit par le bloc 36 et detaille dans les figures 4 et 5. Seuil structure) et critere adapte aux donnees Le procede selon ('invention utilise un seuil structurel ou indicateur qui a notamment pour fonction de definir un critere d'optimisation adapte aux donnees. Pour mieux comprendre son role, on rappelle la theorie de ('analyse relationnelle qui se base sur la maximisation du critere de Condorcet simplifie suivant : n 1 cm =I Cii 2 x f (C, C1, ) i=1 i'=1 ou C , represente le degre de ressemblance entre les deux objets i et i' . Par exemple : C, = .f(C,C,1)=Min( C11, etc... X,,, est par ailleurs donne par : X, ) 11 x = 1 si les objets 1 et 1 sont dans la meme classe 11 0 sinon Le procede selon ('invention est de complexite lineaire dans la mesure ou les formules du type 1E CH, et 1 E f (C , Ci..) sont calculables lineairement. Les fonctions citees en exemple precedemment sont toutes Iinearisables. En effet, la mesure de similarite utilisee est un produit scalaire possedant des proprietes de Iinearite connues, la fonction f(C,,,C,,,,) = 2 (C,, +est lineaire, par contre, la fonction f (Ci; , C,,;,) = Min(C,, C1..) n'est pas lineaire. Cependant, on peut lineariser les i o calculs du type El Min(C, , C;..) . i L'invention a titre illustratif decrit le cas particulier f (C;; ,C,,,,) = Min(C,, , C,.,.) particulierement adapte aux bases contenant un nombre important de donnees manquantes et les procedures qui permettent de calculer avec une complexite lineaire les calculs du type El Min(C,, , C,.,.) . 15 Le procede selon ('invention met par exemple en oeuvre le critere suivant : n n Ca(~ = 1 E[Cil ùax f (C,,) i n n = Contrib i' =I 20 ou a est un seuil et la quantite Contrib,,, la contribution unitaire des deux objets i et i' au critere Ca(X). Selon ('invention, le parametre seuil structurel ac est calcule automatiquement. II s'agit d'un indicateur qui est une fonction des nz accords entre les objets a classifier : 25 ac = ) On peut donner comme exemple, sa formulation lorsqu'il represente le rapport entre la moyenne arithmetique des accords entre tous les objets sur la 5 moyenne arithmetique de leurs accords maximaux. : n n zXIlCii, n 1=1 i'=1 1x.~(Cii,C;; ) n' -1 i'=I Cette formule est linearisable lorsque I'on se place dans les memes conditions que celles evoquees precedemment. 10 Le critere Ca (X) utilise dans ('invention consiste, par exemple, a comparer les accords entre deux objets quelconques au produit du seuil as par leur accord maximal (ce qui represente un pourcentage de ('accord maximal). Ainsi, deux objets seront a priori dans une meme classe des tors que leur similarite est superieure ou egale au pourcentage d'accord maximal calcule 15 (contribution positive). Procede de classification automatique de I'invention Le procede de classification 36 est decrit en detail dans la figure 4. Le point de depart est le tableau de donnees binaires 35 dont les descripteurs ont ete 20 filtres. La premiere etape du procede de classification qui consiste a trier les descripteurs, 40, repose sur une mesure de la contribution au critere de chaque descripteur (qualite d'un descripteur). On utilise, par exemple, les descripteurs comme de structuration de la population des objets a classifier. Un 25 descripteur est represents par un vecteur colonne de 1 et de 0 (presence-absence). On associe a ce descripteur une classe qui est composee des objets dont la valeur prise est 1. On peut alors calculer pour chaque classe d'objets Cq sa mesure de contribution Contrib(Cq) au critere global : Contrib(Cq) = E I Contribir = E 1C,,, û a x l E f (C,, , Ci,i,) [ 1] ;ECq;'ECq ;Kgi'Kq i ('qi Cq 12 a. = 13 L'evaluation de la contribution d'une classe est de complexite polynomiale. En effet, supposons que tous les objets constituent une seule classe, it faudrait alors calculer n2 contributions unitaires afin de determiner la valeur du critere. Dans le cas ou C,,, est un produit scalaire, la premiere partie de la formule de droite, 1 IC,,. , se simplifie de la maniere suivante : ieCq i'eCg XCir = ieCgi'ECy oia Rg = (r,g, r2 , • • •, r1) est appele representant de la classe Cq dont les termes sont donnes par la somme en colonne de chaque modalite du tableau K pour les objets de la classe : r,g = kä . ieCg Chaque valeur r" , j=1,...,p , represente le nombre d'objets de la classe Cq qui possede la modalite 1. Dans le cas ou f (Cä , C,,,) = Min(C,,, C,.,) , la deuxieme partie de la formule de droite de I'equation [1] vaut C,,,,) . Nous donnons ci-dessous la ie Cg i'K'g procedure permettant de calculer avec une complexite Iineaire cette quantite. ************************************************************************** ********************* Procedure MinCC (Classe C ) Necessite : CardC > 0 Necessite : Liste thee d'individus pour la classe C Entier : resultat = 0 Entier : j = prochain element de C Entier : i = 0 Tant que la classe C n'est pas parcourue Faire resultat = resultat + [(CardC ù i) x 2 -1] x C j = prochain element de C i=i+1 Fin tant que ************************************************************************** ********************* On a ainsi pour chaque descripteur q la valeur de la contribution de la classe engendree par ce dernier ou encore une mesure de la qualite du descripteur vis a vis du critere. On procede alors a un tri, par exemple, par ordre decroissant de ces contributions af in d'obtenir un ordre de prise en compte des descripteurs. Le choix de cet ordre a tres peu d'influence sur la qualite du resultat (il peut y avoir quelques differences locales minimes). Cependant, prendre les classes engendrees par les descripteurs de meilleures contributions en premier, permet d'avoir une solution stable plus rapidement et donc d'accelerer le processus de calcul de la meilleure partition 41 issue de ('intersection entre la partition courante et celle engendree par un descripteur. Ce processus 41 consiste notamment a fusionner >> progressivement 42, une classe engendree par un descripteur 40, et une partition courante (composee de plusieurs classes). Cette operation de > consiste a determiner a partir de deux classes en intersection la meilleure operation (au sens du critere) parmi les 4 suivantes : • Cassage >> de la premiere classe et formation de deux classes; • Cassage >> de la deuxieme classe et formation de deux classes; • Cassage >> des deux classes pour former trois classes ; • Reunion des deux classes en intersection pour former une unique classe. Ces operations sont illustrees dans la figure 6 et les calculs permettant de decider de la meilleure operation dans la figure 7. Ce processus revient a construire pas a pas une partition qui optimise localement et progressivement le critere global. Une fois que tous les descripteurs sont utilises, on considere la partition 25 obtenue Po comme une premiere partition finalisee des objets 43. Pendant la phase de > (40, 41, 42) des classes, on essaie de fusionner >> uniquement les classes qui possedent des intersections. L'objet du traitement 44 est de fusionner, c'est-a-dire reunir des classes qui n'ont pas d'intersection si cette operation permet d'optimiser le critere (test de fusion des classes de la partition 30 obtenue entre elles). Ceci conduit a une partition modifiee 45, pu partition de niveau 1, qui constitue la partition finale du procede de classification. Cette partition 45 constitue ('entree du processus d'agregation des classes, 46, qui est decrit dans la figure 8. La figure 5 represente un exemple de schema fonctionnel du traitement 41. Ce dernier consiste notamment a fusionner une nouvelle classe engendree par un descripteur X notee Cy, 50, avec la partition courante P constituee de K classes 51. Le processus est le suivant : • Calcul des intersections entre les classes de la partition P et la classe CY , 52, • Tri de ('ensemble A des classes Cy de la partition P en intersection avec la classe CX dans I'ordre decroissant du cardinal de leur intersection, 53, par exemple, • Pour chaque classe Cy , 55, de I'ensemble A, fusionner les deux classes Cy et CX , 54. On parcourt toutes les intersections entre CX et P et une fois que toutes les classes Cy de A ont ete fusionnees avec Cx , 55, on obtient une nouvelle partition des objets qui ameliore le critere global et qui devient alors la nouvelle partition 15 courante 51. L'etape suivante consiste a passer a un nouveau descripteur, 42, et on repete ce processus jusqu'a ce que tous les descripteurs aient ete parcourus. Le cardinal des elements de ('ensemble des intersections d'une classe Cz avec les classes d'une partition P, 52, peut titre obtenu lineairement de la 20 maniere decrite ci-apres. On considere la classe Cx comme la classe dont on desire evaluer I'intersection avec une partition P. A cette classe, on associe une liste thee, par exemple, par ordre croissant des indices des objets qu'elle contient. En effet chaque 25 objet est identifie par un entier unique qui est son indice. Pour trier les objets, on utilise par exemple un tri lineaire (par exemple le tri par base dont une reference est la suivante : Cormen et al (2002), Introduction a I'algorithmique, Dunod) puisque I'on connait la borne superieure des valeurs a trier. Pour ('operation de calcul du cardinal des intersections, on utilise un vecteur A de dimension n pour lequel chaque dimension i represente I'indice de Ia classe ou est stocke I'individu 0, . Exemple de calcul de cardinaux d'intersections Si on prend une population de 6 objets 01,02, 06 et une partition courante de ces objets P, 51, constituee de trois classes = {01 , 03 } c2 = {O, , 04 , 06 } C3 = {05 } Le vecteur A est egal a : Ainsi si on > Ia partition existante avec une classe C, ={02,03,04,06} 50, on est capablede trouver rapidement le cardinal de ('ensemble intersection de la classe CX avec les classes de la partition existante, en ('occurrence Card (Inter(C1 CX )) =1, Card (Inter(C2 CX )) = 3 et Card (Inter(C3 C,,)) = 0 . 15 Le nombre d'operations effectuees lors du calcul des intersections 52 est egal au nombre d'objets dans la classe Ca. a fusionner avec la partition P. En effet, on regarde pour chaque objet de la nouvelle classe s'il appartient a une classe de la partition P , si oui on incremente le compteur d'intersection de cette classe. S'il existe plusieurs intersections entre une classe Cx et une partition 20 P , on calcule comme indique ci-dessus, le cardinal des differentes intersections entre Cx et les differentes classes Cy de la partition P afin d'avoir un ordre de prise en compte. A partir de I'intersection de Cx et d'une classe Cv de la partition P, on evalue quelle est la meilleure configuration parmi celles presentes dans la figure 6. 25 Pour cela, on evalue Ies quantites identifiees dans la figure 7. Les figures 6 et 7 expliquent donc un exemple d'operations de base de ('invention qui sont representees par le traitement 54.10 Le processus de construit les vecteurs R , Rh et R` definis par : R = Ry ù R` Rb = Rx ù R` oi] Cc, =CC n Cy est la classe definie par ('intersection de Cx et Cy (les objets a la fois dans la classe Cx et dans Cy,) et R' son representant. R'' represente donc les objets qui sont uniquement dans Cy et Rb ceux qui sont uniquement dans Cx . Au definira respectivement CardA, CardB et CardC comme les cardinaux des classes representees par R , Rb et R` . Les deux listes d'objets contenus dans les classes Cy et Cx sont triees par ordre croissant de leur indice. On peut donc appliquer la procedure classique suivante pour calculer rapidement les trois vecteurs : ************************************************************************** ********************* Procedure de Calcul vecteurs (Classe Cx , Classe Cy ) R = Ry Rh = Rx R` = 0 CardA = CardB = CardC = 0 L, = liste des objets de Cy e = tete de la liste L, L2 = liste des objets de Cx f = fete de la Iiste L2 Tant que la liste LI n'est pas parcourue Faire Tant que la liste L2 n'est pas parcourue Faire Si e = f Faire Re =0 Ra = R ù R` h = Rh ù R`" R R` = R` +R` e = tete de la liste L1 f = fete de la Iiste L2 cardC = cardC +1 Sinon Si e > la classe Cy, pour former les deux classes suivantes : Cy ùC., et CX • > la classe Cz pour former les deux classes suivantes : CX ûCy, et Cy • casser >> la classe CX et > la classe Cy pour former les trois classes suivantes : CX ùCy , Cy ù CX et Cy n Cx • fusionner les deux classes pour former une unique classe : Cy u CX . Le choix de la meilleure des quatre solutions se base, par exemple, sur ('evaluation des > entre les 3 differentes sous-classes mises en evidence ci- 18 19 dessus. Le calcul general du ' entre deux classes Cq et Cy, est donne par la formule suivante : Lien(Cq , Cq,) = 1 Contrib,,, =E (Cu. ù a x f (Cä , C,,,,)) IE{'g1'ecy, lEy'Ecy, Lorsque la mesure de similarite est un produit scalaire, et lorsque 5 f(C,,,C,,.) = Min(C,,,C,,,,), on peut comme precedemment, lineariser le calcul du lien entre deux classes distinctes. Le procede utilise pour cela les proprietes de linearite du produit scalaire, ce qui donne la simplification suivante : Lien(Cq,C ,) _ ùax ,ECq i'eCy' On peut aussi utiliser la procedure suivante qui permet d'evaluer avec une 10 complexite lineaire la quantite 1 Min(C,,,) : iECyi'eCq Procedure MinCC' (Classe C , Classe C' ) Necessite : CardC > 0 Necessite : CardC'> 0 15 Necessite : Liste triee d'individus pour les classes C et C' Entier : resultat = 0 Entier : nb_lignes = CardC Entier : nb cols = CardC' Entier : j = prochain element de C 20 Entier : j' = prochain element de C' Tant que la classe C n'est pas parcourue et la classe C' n'est pas parcourue Faire Si j resultat = resultat + nb _ cols x C11 25 j = prochain element de C nb _ lignes = nb _ lignes -1 Sinon Si j' Sinon resultat = resultat + (nb _cols + nb _ lignes -1) x C11 j = prochain element de C j' = prochain element de C' nb lignes = nb _ lignes -1 nb cols = nb cols -1 Fin Si Fin Si Fin tant que ************************************************************************** ********************* Dans le cadre de ('intersection entre deux classes, le procede evalue les 15 trois quantites suivantes qui sont representees sur un exemple dans la figure 7 : Lien, = Lien(Cy ù Ce,Cx ùCc) = ùax f(C,,,C,.i.) iECynioCc i'E('xni'ECc Lien2 = Lien(Cy ùCc.,Cc) _ ùax E f (Cii,Ci'i') iECyniCc i'ECc Lien3 =Lien(CxùCc,C)= ùax E f(Cii,Ci'p) iECxnieCC i'e('c 20 Ainsi, pour maximiser localement le critere global : • Si Lien, + Lien2 + Lien3 est la plus grande, on choisit la solution 4 (fusion des deux classes) ; • Si Lien2 est la plus grande, on choisit la solution 2 ( > de Cx) ; • Si Lien3 est la plus grande, on choisit la solution 1 ( > de Cy) ; 25 • Si 0 est la plus grande, autrement dit que Lien, + Lien2 + Lien3 > de Cx et de Cy ). 10 Une fois que la classe Cx , 50, est fusionnee avec la premiere classe Cy, on continue le traitement avec les autres classes de la partition P en intersection avec la classe CC , 55,. Pour cela, la classe Cx sera transformee en classe Cx, • Si la solution 1 est choisie, Cx, = Cx • Si la solution 2 est choisie, Cx, = Cx ùCy • Si la solution 3 est choisie, Cx, = Cx ùCy • Si la solution 4 est choisie, Cx, = Cx u Cy Dans tous les cas, la nouvelle classe Cx, contient les objets qui peuvent to appartenir aux autres classes de la partition P puisqu'on sait, par avance, qu'aucun objet de la classe Cy ne peut appartenir a une autre classe de la partition P. Procedure de retrait d'objets a une classe Pour retirer un ensemble d'objets A d'une classe, it suff it de retirer A de 15 la liste d'objets de la classe et de retrancher le representant R du representant de Ia dite classe. Par exemple, fors de I'operation Cx, = Cx ùCy , R est egal a R` . En effet, on retranche a la classe Cx , les objets en intersection representee par le representant Rc . Ainsi Rx' = Rx R` De cette maniere, les operations de > ne necessitent pas de 20 temps de calcul importants puisque la quantite retranchee au representant de la classe est toujours egale au vecteur R` qui est deja calcule. D'autre part, le retrait des objets de la liste est une operation simple et lineaire. Procedure de Reunion de deux classes 25 Dans cette procedure, on connait le representant de I'intersection de C, et C2 (defini par R` ci-dessus) et le cardinal de I'intersection (defini par CardC cidessus). On cherche donc a creer la classe C, u C2 , sans effectuer de tri lineaire complet. ************************************************************************** ********************* Procedure Reunion (Classe C, , Classe C2 , Representant Inter, Entier Cardlnter ) Vecteur temporaire de taille (CardC + CardC 2 ù Cardlnter) Entier position = 0 L, = Iiste des objets de C, e = tete de la Iiste L, L2 = Iiste des objets de C2 f = tete de la liste L2 Tant que la liste L, n'est pas parcourue Faire Tant que la liste L2 n'est pas parcourue Faire Si e = f Faire el = e e = tete de la liste L, f = tete de la liste L2 Sinon Si e x Pour toutes les valeurs de Lien positives de S , on va fusionner les classes 10 correspondantes. L'ensemble de ces classes seront marquees comme affectees et ne pourront plus etre fusionnees par la suite. On itere le processus avec ('ensemble K' des classes non marquees. Procede d'agregation hierarchique des classes de ('invention 15 Dans la figure 8, est represents un exemple d'architecture du procede d'agregation hierarchique des classes en meta-classes. Ce procede consiste, notamment, a regrouper sur plusieurs niveaux (le nombre de niveaux est a fixer par I'utilisateur) les classes entre elles. L'optimisation du critere global passe, par exemple, par la maximisation des liens entre les classes 20 constituees. En d'autres termes, les classes obtenues doivent, in fine, avoir des liens negatifs. Or, le calcul des liens est fonds sur la definition de la contribution Contrib,,. d'une paire (i,i') d'objets. On rappelle ci-dessous la definition de la contribution d'une paire d'objets lorsque la fonction f est la fonction Minimum : Contribä. = C;;, ù a x Min(C,,, C,.,. ) 25 Le procede d'agregation des classes, propose par ('invention, consiste alors a diminuer a chaque niveau, la valeur du seuil structurel 80, de sorte que les contributions faiblement negatives puissent devenir positives. De cette maniere, le lien entre deux classes peut devenir positif ce qui permet de les regrouper 81, et de mettre en evidence des relations entre les classes d'une partition. On repete ce 30 processus autant de fois qu'il y a de niveaux 82. On obtient alors un ensemble de partitions emboitees 83, qui permet de detecter des relations hierarchiques et conceptuelles (sur plusieurs niveaux) entre les classes considerees initialement dans la partition 45. L'invention, par ce principe, permet ainsi de faire de la decouverte de connaissances. La procedure d'agregation hierarchique des classes d'un niveau j a un niveau j +1 est similaire a la procedure Regrouper decrite ci-dessus. Calculs permettant ('evaluation de la qualite des resultats de classification de !'invention On donne ici les formules theoriques des indices de mesure de la qualite de la solution obtenue qui s'expriment en pourcentage. Plus I'indice est proche de 100%, plus la qualite de la solution etudiee (qualites partition, classe ou individu) est bonne. On introduit tout d'abord quelques notations : L'accord entre deux classes : Acc., = E Cä. 'EC !'EC' L'accord maximal entre deux classes : AMcc' = E f(GäCl,,,) 'EC IEC' Le desaccord entre deux classes : Acc' = AMcc' ûAcc. 20 La qualite finale de la partition obtenue est donnee par : K K K K K E A. + E Acc.. E A. ù E E Acc, + E E AMcc. _ C=1 C=l C'#C 7=1 C=1 C'xC C=l C'≠C K K K K E E AMcc. E E AMcc., C=1 C'=l C=l C'=l ou x est le nombre de classes de la partition. 25 La qualite d'une classe C est donnee par : Ac.c. + 2x EA-cc, (:'≠c Qc MCI AMcc + 2x E AMcc' c'≠c Acc -2x E Acc. +2x E AMcc' c'c C'-c NbCI AMcc + 2x E AMcc' c'~c La qualite d'un objet i appartenant a une classe C est donnee par : ~C +EC_. ûEC--. + f(C, C ) = i'E(' iv.? f(C,, , ) J ) oia C,,. = f(C,,,C,,.)ûC,,, est le desaccord entre I'individu i et I'individu i'. Les sommes sur les termes A(.(ä sont Iinearisables lorsque les similarites sont des produits scalaires grace aux proprietes de Iinearite de ces derniers. On donne ci-dessous des exemples de procedures permettant de calculer lineairement les 10 quantites suivantes intervenant dans les differentes formules de qualites lorsque f(Cii,C, .) = Min(C: • EAMc(. _ 1~Min(C ,C. ) c c C C '\ iEC ,'E C / • E AMcc = 1 E Min(C,, , G.,. ) C~ C \ EEC i'EC" • EMin(C rEc 15 On note respectivement ces quantites SS'MinCC', S'MinC' et MiniC : ************************************************************************** ********************* Procedure SS'MinCC' (Classe C , Classe C) Necessite : K.> 0 20 Entier : resultat = 0 Pour i = 1 jusqu'a n par increment de 1 Faire resultat = resultat + ((n û i + 1) x 2 -1) x C,, Fin Pour ************************************************************************** ********************* 25 20 26 Procedure S'MinCC' (Classe C , Classe C' ) Necessite : CardC > 0 Necessite : K > 0 Necessite : Liste triee d'individus pour Ies classes C Entier : resultat = 0 Entier : nb _lignes = CardC Entier : nb cols = n Entier : j = prochain element de C Entier : i =1 Tant que la classe i n et C n'est pas parcourue Faire Si i = j faire resultat = resultat + (nb _ cols + nb _ lignes -1) x C,, nb _ lignes = nb _ lignes -1 nb cols = nb cols -1 i=i+1 j = prochain element de C' Sinon resultat = resultat + nb _ lignes x C,, i=i+1 nb cols = nb cols -1 Fin Si Fin tant que 25 ************************************************************************** ********************* Procedure MiniC (Classe C ) Necessite : CardC > 0 Necessite : Liste triee d'individus pour la classe C Entier : resultat = 0 Entier : nb cols = CardC Entier : j = prochain element de C Tant que la classe C n'est pas parcourue et nb cols j Faire 10 Si i = j Faire resultat = resultat + nb _ cols x C,1, Sinon resultat = resultat + j = prochain element de C 15 nb cols = nb cols -1 Fin Si Fin Tant que ************************************************************************** ********************* 20 REVENDICATIONS 1 ù Procede de classification non supervisee lineaire permettant de structurer une base de donnees composee d'objets et de descripteurs, qui est stable sur I'ordre des objets comprenant une etape prealable de transformation des donnees qualitatives, quantitatives ou textuelles en donnees binaire de presence-absence caracterise en ce qu'il comporte au moins les etapes suivantes : • determiner un seuil structurel as fonction des n2 accords entre les objets a classifier, le seuil structurel definissant un critere d'optimisation adapte aux to donnees, • utiliser les descripteurs comme generateurs de structuration et de construction d'une partition ou ensemble de classes, • fusionner progressivement une classe engendree par un descripteur et une partition (40, 41, 42), 15 • pour un critere d'optimisation faisant intervenir une fonction f(C,,,C,.,.) = Min(C,,,C,,,.) Iineariser des sommes de fonctions Minimums. 2 ù Procede selon la revendication 1 caracterise en ce qu'il comporte une etape oia I'on regroupe les classes de la partition entre elles. 20 3 ù Procede selon la revendication 1 caracterise en ce que I'etape de fusion comporte une etape of I'on determine a partir de deux classes en intersection la meilleure operation (au sens de ('optimisation du critere) parmi les 4 suivantes : 25 • > de la premiere classe et formation de deux classes; • Cassage >, de la deuxieme classe et formation de deux classes; • > des deux classes pour former trois classes ; • Reunion des deux classes en intersection pour former une unique classe. 30 4 ù Procede de classification selon la revendication 2 caracterise en ce que le regroupement des classes d'une partition est effectue sur plusieurs niveaux hierarchiques et comporte les etapes suivantes :• diminuer a chaque niveau la valeur du seuil structurel (70) de sorte que les contributions faiblement negatives puissent devenir positives, • maximiser des liens entre les classes constituees ou les liens sont determines en utilisant la contribution d'une paire d'objets Lien(Cq,Cq.) = E l Contribii. = E ùa'xf(C, ,C ) iECyi'eCy eCyi'K'q' avec a' la nouvelle valeur de a • regrouper (71) deux classes dont le lien est positif, et reiterer ce processus sur tous les niveaux. 5 û Dispositif permettant la classification non supervisee lineaire permettant de structurer une base de donnees composees d'objets et de descripteurs, qui est stable sur I'ordre des objets comprenant une etape prealable de transformation des donnees qualitatives, quantitatives ou textuelles en donnees binaires de presence-absence, caracterise en ce qu'il comporte au moins les elements suivants : un calculateur (1) comprenant une memoire (2), une base de donnees (4) et un processeur (3) adapte a mettre en oeuvre les etapes du procede selon rune des revendications 1 a 4. 6 û Dispositif selon la revendication 2 caracterise en ce qu'il comporte un moyen (7) 20 de conduite d'actions en fonction des resultats de la classification.