Ministre de lEnseignement Suprieur et de la Recherche Scientifique UNIVERSITE MHAMED BOUGUERRA - BOUMERDES FACULTE DES SCIENCES DEPARTEMENT DINFORMATIQUE

THESE DE DOCTORAT
Spcialit : INFORMATIQUE Prsente par : AT EL HADJ ALI

Thme
Modle de reprsentation et dappariement de documents XML selon une indexation structurelle

Soutenue le 10 / 12 / 2011

Devant le jury compos de : Mr Ahmed Nacer Mohamed; Professeur, U.S.T.H.B, Alger; Mme Alimazighi Zaia; Professeur, U.S.T.H.B, Alger; Mr Hacid Mohand Said; Professeur; Universit Claude Bernard, Lyon 1; Mr Boughanem Mohand; Professeur; Universit Paul Sabatier, Toulouse; Mr Mezghiche Mohamed; Professeur; UMBB, Boumerdes; Prsident Examinatrice Examinateur Co-encadreur Encadreur

Rsum
Ce travail est motiv par la construction dun modle de reprsentation et dappariement de documents XML. Notre approche consiste reprsenter chaque document XML par sa structure et utiliser celle-ci comme modle de reprsentation en vue de la classication structurelle du document XML correspondant. La classication structurelle a pour rle de regrouper des documents XML structurellement similaires dans des clusters (ou classes). Ceci aiderait, dune part, mieux organiser les documents XML et, dautre part, mieux rpondre, en termes decience et decacit, aux requtes contenant des conditions structurelles. Lide est que, si les documents partagent des structures similaires, ils sont plus mme de correspondre la partie structurelle dune mme requte. Par ailleurs, une nouvelle mesure de similarit qui prend en considration certaines relations hirarchiques entre les nuds de chaque structure arborescente ainsi quun nouvel algorithme de clustering (classication non supervise), ont t proposs. Pour valider notre approche, des exprimentations ont t menes sur deux collections XML. A cet eet, nous avons utilis le corpus rel ACM SIGMOD Record et une collection XML synthtique, qui nous ont permis dvaluer la performance de notre algorithme de clustering et la abilit de notre modle de reprsentation, ainsi que lecacit de notre mesure de similarit. Ces dirents tests ont montr lintrt de notre approche.

Abstract
This work is motivated by the construction of a model for representing and matching XML documents based on their structure. Our approach is two-step. We rst automatically extracted the structure from each XML document to be classied. This extracted structure is then used as a representation model to classify the corresponding XML document. The structural classication consists in grouping similarly structured XML documents in classes (or clusters). This would help to better organize XML documents on the one hand and, on the other hand, to better answer, in terms of eciency and eectiveness, queries containing structural conditions. The idea behind the classication is that if XML documents share similar structures, they are more likely to correspond to the structural part of the same query. Furthermore, an algorithm for unsupervised classication (or clustering) and a similarity measure that takes into account certain hierarchical relationships between nodes of each tree structure have been proposed. To validate our approach, experiments were conducted on two XML collections. To this end, we used both real (ACM SIGMOD Record corpus) and synthetic XML collection, which allowed us to evaluate the performance of our clustering algorithm, the reliability of our representation model, and the eectiveness of our similarity measure. These tests have shown the viability of our approach.


XML . . XML XML . XML . . . ) (. .XML XML ACM Sigmod XML . . .

Remerciements
Je remercie trs respectueusement et trs sincrement, Mr Mohamed Ahmed Nacer, Professeur au dpartement dInformatique, USTHB (Alger), davoir accept, sans dtour, de prsider ce jury. Quil trouve ici lexpression de ma profonde gratitude. Que Mme Zaia Alimazighi, Professeur au dpartement dInformatique et Doyenne de la Facult dElectronique et dInformatique, USTHB (Alger), trouve ici lexpression de mon profond respect. Je la remercie trs sincrement davoir rpondu favorablement, trs rapidement, pour honorer ce jury. Je voudrais galement adresser mes vifs remerciements Mr Mohand Said Hacid, Professeur lUniversit Claude Bernard de Lyon, davoir accept trs gentiment de donner son accord et, tout particulirement, de stre dplac pour la circonstance. Cest avec un immense plaisir que je laccueille dans mon jury. Et bien sr, cette soutenance est aussi pour moi loccasion pour ritrer ma profonde reconnaissance mon codirecteur de thse, Mr Mohand Boughanem, Professeur lIRIT, Universit Paul Sabatier de Toulouse, pour mavoir permis de travailler ses cts, en acceptant de maccueillir au sein de son quipe durant les deux stages eectus lIRIT. Ses conseils judicieux et ses remarques pertinentes, mont fortement et favorablement inspir, et aid tout au long de cette thse. Quil sache que je ne suis pas rest insensible la grande conance quil a place en moi, en me laissant une large marge de manuvre dans mes investigations. De mme, je dirais un grand merci mon directeur de thse, Mr Mohamed Mezghiche, Professeur lUMBB (Boumerdes), davoir accept de mencadrer. Malgr les contraintes gographiques, il a su tre lcoute de mes proccupations, en maidant me ressaisir dans des moments de doute et de lassitude, par ses prcieux encouragements et son grand optimisme, dont lui seul, connait le secret. Quil trouve ici lexpression de ma profonde gratitude. Jaimerais tout particulirement dire Mr Mohand Sad Souam, Professeur lUniversit Paris Ouest Nanterre La dfense que, je noublierai pas laide apprciable quil ma apporte. Quil trouve ici, lexpression de mon profond respect et le remercie trs fraternellement pour lintrt constant quil na cess de tmoigner mon gard durant ces quatre longues annes de thse. Enn, je ne saurais clore ce volet sans adresser toute mon aection et mon admiration mon pouse, pour avoir non seulement support mes humeurs durant ces quatre ans, mais galement, pour avoir particip activement laboutissement de ce travail de thse.

iii

Table des matires

Introduction gnrale Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Contexte de travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problmatque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Plan du rapport de thse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Prsentation de XML 1.1 1.2 9 9 1 1 2 4 6

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 1.2.2

Historique des langages de balisage . . . . . . . . . . . . . . . . . . . . . . 10 Gense des langages de balisages . . . . . . . . . . . . . . . . . . . 10 Langages de balisage . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 1.4 1.5 1.6 1.7 1.8 1.9

Spcication XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Dnition dun document XML . . . . . . . . . . . . . . . . . . . . . . . . 13 Type de document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Document bien form, document valide . . . . . . . . . . . . . . . . . . . . 15 Association dune DTD un document XML . . . . . . . . . . . . . . . . . 15 XML-Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Quest ce que le parsing en XML ? . . . . . . . . . . . . . . . . . . . . . . . 18

1.10 DOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.11 SAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.12 Fichiers XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 Indexation de linformation structurelle de documents XML 2.1 23

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 v

Table des matires 2.2 2.3 Le processus dindexation . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Approches dindexation de linformation structurelle de documents XML . 26 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5 2.3.6 2.3.7 3 Classsication 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 41 Dnitions prliminaires . . . . . . . . . . . . . . . . . . . . . . . . 26 Indexation base sur les sous-arbres frquents . . . . . . . . . . . . 29 Indexation base sur les arbres et rsums darbres . . . . . . . . . 32 Indexation base sur les vecteurs structurs . . . . . . . . . . . . . 34 Indexation base sur les chemins (paths) . . . . . . . . . . . . . . . 35 Indexation base sur les niveaux . . . . . . . . . . . . . . . . . . . . 37 Indexation base sur les bitmaps . . . . . . . . . . . . . . . . . . . 38

Inroduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Notion de classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Dnition formelle de la classication . . . . . . . . . . . . . . . . . . . . . 43 Le ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Contextes de classication . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Paramtres dvaluation des performances dun systme de classication . . 47 valuation dun classieur bi-classe . . . . . . . . . . . . . . . . . . . . . . 48 valuation de classieurs multi-classes . . . . . . . . . . . . . . . . . . . . 50

3.10 valuation dun systme de clustering . . . . . . . . . . . . . . . . . . . . . 52 4 Classication structurelle de documents XML 4.1 4.2 4.3 4.4 4.5 55

Inroduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Mthodes spciques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Approches de classication structurelle de documents XML . . . . . . . . . 57 Approche des arbres frquents . . . . . . . . . . . . . . . . . . . . . . . . . 61 Approche des rsums darbres 4.5.1 4.5.2 . . . . . . . . . . . . . . . . . . . . . . . . 63 Dnitions prliminaires et notions de base . . . . . . . . . . . . . . 65 Calcul de la distance ddition . . . . . . . . . . . . . . . . . . . . . 68 Reprsentation des DTDs . . . . . . . . . . . . . . . . . . . . . . . 71 Calcul de la similarit . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.6

Approche des DTDs : cas Xclust . . . . . . . . . . . . . . . . . . . . . . . . 71 4.6.1 4.6.2

vi

4.7 4.8 5

Approche des bitmaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Approche des noyaux darbres (tree kernels) . . . . . . . . . . . . . . . . . 81

Modle de clustering incrmental bas sur des rsums darbres 5.1 5.2

85

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Classication base sur la similarit structurelle . . . . . . . . . . . . . . . 86 5.2.1 5.2.2 5.2.3 5.2.4 Prsentation gnrale de lapproche . . . . . . . . . . . . . . . . . . 86 Extraction du rsum darbre structurel . . . . . . . . . . . . . . . 87 Approche de clustering . . . . . . . . . . . . . . . . . . . . . . . . 89 Similarit structurelle . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6 Exprimentation 6.1 97

Implmentation du systme de classication . . . . . . . . . . . . . . . . . 97 6.1.1 6.1.2 Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.2 6.3

Collections XML utilises 6.3.1 6.3.2 6.3.3 F-mesure

Mtriques dvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Puret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Mesure des performances du clustering . . . . . . . . . . . . . . . . 100 Mesure de similarit propose vs. distance ddition . . . . . . . . . 102 Intert de la reprsentation des documents XML par des rsums darbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.4.4 6.4.5 Comparaison de nos rsulats avec ceux obtenus avec dautres mthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Exprience de timing . . . . . . . . . . . . . . . . . . . . . . . . . . 110 113

6.4

Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.4.1 6.4.2 6.4.3

Conclusion gnrale 1 2

Mthode propose vs. tat de lart . . . . . . . . . . . . . . . . . . . . . . . 113 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 vii

Table des matires Publications dans le cadre de la thse Bibliographie 117 119

viii

Table des gures

1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20 3.1 3.2 Document XML . . . . . . . . . . . . . . . . . . . . . . . . Document XML une autre version . . . . . . . . . . . . . . Structure arborescente dune page XML . . . . . . . . . . Page XML avec attributs . . . . . . . . . . . . . . . . . . . Document XML dcrivant une famille . . . . . . . . . . . . Document XML dcrivant une personne . . . . . . . . . . XML-Schema associ au document XML de la FIGURE 1.6 Modle darbre DOM . . . . . . . . . . . . . . . . . . . . . Document XML dcrivant un tudiant . . . . . . . . . . . Modle darbre DOM du document de la FIGURE 1.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 12 13 14 16 18 18 19 20 20 27 27 27 28 28 28 29 30 31 31 32 32 33 33 35 35 36 37 38 38

Inclusion stricte exacte ordonne . . . . . . . . . . . . . . . . . . . Inclusion stricte exacte non ordonne . . . . . . . . . . . . . . . . . Inclusion stricte ordonne non exacte . . . . . . . . . . . . . . . . . Inclusion stricte non ordonne non exacte . . . . . . . . . . . . . . . Inclusion stricte faible non ordonne, non exacte . . . . . . . . . . . Inclusion non stricte, mais exacte et ordonne . . . . . . . . . . . . Un document XML simple et larbre des balises associ [95] . . . . . Arbre frquent selon linclusion stricte exacte ordonne . . . . . . . Arbre frquent selon linclusion stricte exacte et ordonne indirecte Arbre frquent selon linclusion stricte ordonne non exacte . . . . . Arbre frquent par subsumption (inclusion stricte non ordonne non Extraction darbres frquents selon la subsumption [95] . . . . . . . Extraction de rsums darbres [27] . . . . . . . . . . . . . . . . . . Approche de reprsentation dun document XML [5, 6] . . . . . . . Arbre XML bas sur les notations SVM . . . . . . . . . . . . . . . . Modle SVM dun arbre XML . . . . . . . . . . . . . . . . . . . . . Document test.xml [102, 103] . . . . . . . . . . . . . . . . . . . . . . Arbre XML (avec contenu) associ au document de la FIGURE 2.17 Exemple dindexation base sur les niveaux des arbres . . . . . . . . Exemple de documents XML . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . exacte) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Exemple de systme de classication demails [30] . . . . . . . . . . . . . . 42 Dirents types de mthodes de classication . . . . . . . . . . . . . . . . 46 ix

Table des gures 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 5.1 5.2 5.3 5.4 5.5 5.6 6.1 6.2 6.3 6.4 6.5 6.6 6.7 Extraction de rsums darbres selon [27] . . . . . . . . . . Extraction de sous-arbres frquents selon [95] . . . . . . . Approche de dtection de sous-arbres frquents [30] . . . . Rsums darbres selon lapproche [27] . . . . . . . . . . . Rsums darbres selon lapproche [5] . . . . . . . . . . . . Inclusion stricte ordonne non exacte . . . . . . . . . . . . Oprations ddition sur deux arbres T1 et T2 . . . . . . . Graphe ddition pour comparer les squences A et B . . . Graphe ddition pour comparer les arbres A et B . . . . . Calcul de la distance ddition (version Chawathe) [20] . . Squence doprations ddition pour transformer T1 en T2 Calcul de la distance ddition (version Dalamagas) [27] . . DTD dcrivant des articles . . . . . . . . . . . . . . . . . . Reprsentation en arbre de la DTD de la FIGURE 4.13 . . Contextes utiliss dans XClust [57] . . . . . . . . . . . . . Exemple de document XML . . . . . . . . . . . . . . . . . Exemple de documents XML . . . . . . . . . . . . . . . . . Noyau darbre . . . . . . . . . . . . . . . . . . . . . . . . . Approche de classication structurelle . . . . . . . . . . Approche de representation dun document XML . . . Algorithme dextraction dun rsum darbre XML . . Un document XML et son rsum darbre structurel Algorithme de clustering . . . . . . . . . . . . . . . . . Algorithme de calcul de la similarit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 58 62 63 64 64 66 67 67 68 70 70 71 72 74 77 78 83 86 87 88 89 90 93 103 104 108 109 109 111 111

Distance de Levenshtein . . . . . . . . . . . . . . . . . . . . Comparaison de deux arbres XML . . . . . . . . . . . . . . . Courbe de la prcision . . . . . . . . . . . . . . . . . . . . . Courbe du rappel . . . . . . . . . . . . . . . . . . . . . . . . Courbe de la F-mesure . . . . . . . . . . . . . . . . . . . . . Rsulats de timing avec les hauteurs h dans lintervalle [5,10] Rsulats de timing avec la hauteur h = 1 : O(N 2 ) . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . : O(N 2 h2 ) . . . . . .

Liste des tableaux

2.1 2.2 2.3 2.4 3.1 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 Tableau rcapitulatif des types dinclusion voqus . . . . . . . . . . Notations utilises pour le SVM (arbre et/ou vecteur) . . . . . . . . Les paths (chemins) de longueur 3 avec leurs frquences respectives Un index bitmap des documents XML de la FIGURE 2.20 . . . . . . . . . . . . . . . . . . . . . . 28 34 37 39

Matrice de contingence [30] . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Rgles de transformation dun arbre DTD . . . . . . . . . . . . . . . . . . Table des similarits cardinales . . . . . . . . . . . . . . . . . . . . . . . . Matrice de similarit ontologique . . . . . . . . . . . . . . . . . . . . . . . Un index bitmap de la FIGURE 4.17 . . . . . . . . . . . . . . . . . . . . . . Un index bitmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Un index bitmap aprs dcalage des colonnes (epaths) populaires gauche Index bitmap partitionn en deux avant llimination des bits 0 . . . . . . Index bitmap de la TABLE 4.6 partitionn . . . . . . . . . . . . . . . . . . Noyeau : reprsentation du 2-spectrum Kernel . . . . . . . . . . . . . . . . Matrice des noyeaux dans lespace du 2-spectrum kernel . . . . . . . . . . . 73 74 75 78 80 81 81 81 82 82

Repartition du corpus ACM SIGMOD . . . . . . . . . . . . . . . . . . . . 98 Nombres de clusters gnrs avec leurs eectifs pour chaque seuil . . . . 101 Resultats du test de clustering . . . . . . . . . . . . . . . . . . . . . . . . . 101 Mesure propose vs. distance ddition (clustering et timing) . . . . . . . . 104 Mesure de similarit propose vs. distance ddition (rsultats de clustering)105 Repartition du sous-ensemble du corpus ACM SIGMOD . . . . . . . . . . 106 Rsums darbres XML vs. arbres XML originaux . . . . . . . . . . . . . . 107 Rsums darbres XML vs. arbres XML originaux (P , R et F1 ) . . . . . . . 107 Comparaison de nos rsultats avec ceux de [20, 27, 74, 94] . . . . . . . . . . 110

xi

Introduction gnrale
Introduction
Internet est la mise en rseau mondiale des ordinateurs, constituant un nouvel espace social dchanges en perptuelle expansion, permettant ainsi dirents utilisateurs de communiquer par courrier lectronique, de publier des informations sur le Web, de transfrer des donnes, de travailler distance, de discuter par forums ou messageries instantanes, etc. En eet, le Web est considr aujourdhui comme une gigantesque source dinformations et de connaissances, trs diversie et en pleine expansion. Le nombre de documents qui y sont dissmins est dune dimension earante, le nombre de sites rpondant des besoins trs varis, est dune immensit telle que des annes entires ne suraient jamais les consulter, pas mme les visiter, dans leur globalit. Par ailleurs, le nombre demails envoys chaque anne, galerait en volume dinformation les environs million de traoctets ; et la masse totale en information, rien que pour la seule andu 1 2 ne 2002, ne serait pas loin du million de traoctets [85]. Aujourdhui, il y a 3,4 millions demails qui sont envoys dans le monde, chaque seconde, soit 107 billions (107 000 mil3 sont des Spams [79]. liards) par an, dont plus des 4 Ces chires abstraits, si on essayait de les ramener la ralit des objets de la vie courante, on se rend mieux compte de leur ampleur et de lextrme complexit quils dissimulent. 1 traoctet, soit 1012 octets, approcherait les environs de 700.000 ouvrages de 400 pages de format A4. Lnormit et la varit des volumes dinformations stockes et diuses sur les rseaux sont une premire justication de la ncessit de dvelopper des outils adquats pour leur gestion [4].

Contexte de travail
Les collections de documents ont considrablement volu ces dernires annes. Tandis quon distinguait traditionnellement nettement deux types de donnes : les donnes fortement structures prises en charge par la communaut des BD (Bases de Donnes), et les donnes non structures (texte) prises en charge par la communaut de la RI (Recherche dInformation). Aujourdhui, les donnes dites semi-structures ouvrent une troisime voie dans la gestion de linformation, car orant un bon compromis et un format dchange entre direntes applications pour lintgration de donnes en provenance de sources htrognes. Avec cette tendance, acclre notamment par lexpansion du Web, les documents semi-structurs de type HTML (HyperText Markup Language) ou XML (eXtensible Mar1

Introduction gnrale kup Language), sont sur le point de former la majorit des documents numriques mis disposition des utilisateurs. An dexploiter au mieux lensemble de ces informations, les modles conventionnels existants de RI [85] doivent tre tendus ou bien de nouveaux modles doivent tre proposs. Nous nous plaons dans le contexte de la RI. Plus prcisment, cest dans le cadre de la RIS (Recherche dInformation Structure), que se situe notre travail. Notre objectif consiste dabord proposer un modle de reprsentation de documents XML et ensuite utiliser cette reprsentation comme modle pour tablir une classication de ces documents. Nous avons particulirement orient notre investigation sur un modle de classication structurelle non supervise. A cet eet, nous nous intressons aux documents semi-structurs XML du point de vue structurel. Nous nous focalisons donc plus spcialement sur leurs composantes structurelles, cest--dire les structures arborescentes dont les nuds sont les balises et attributs qui dnissent les structures logiques de ces documents.

Problmatique
Contrairement aux documents plats (textuels) qui sont par nature non structurs et aux bases de donnes qui sont caractrises par des donnes simples et des structures fortes, les documents XML se prsentent comme une alternative caractrise par un double aspect. Dune part, ce format possde les caractristiques de structures fortes, permettant ainsi de bonnes performances daccs et de stockage, et un traitement de linformation textuelle par les SRI avec une autre granularit que le document tout entier. Dautre part, il permet de dlimiter des donnes de type htrogne (texte ou multimdia), qui sont par nature des donnes non structures [30, 85]. Cependant, avec les outils actuellement disponibles, la recherche dinformations dans ce type de documents est une tche non triviale. Les documents XML sont caractriss par un contenu (du texte) et une structure (balises). Ce type de documents ne peut cependant tre exploit ecacement par les mthodes conventionnelles de RI. En eet, ces dernires sont bases sur des modles orients contenu, tandis que le format XML permet dajouter des contraintes structurelles (balises). De mme, les approches traditionnelles de traitement des donnes telles que les bases de donnes relationnelles se sont avres inecaces. Celles-ci sont principalement ddies la gestion des donnes fortement structures, alors que les documents XML sont classs dans la catgorie des donnes semi-structures [36]. En somme, lutilisation de plus en plus croissante de ce nouveau format sur le Web, a soulev un certain nombre de questions, lies linterrogation, lindexation [23, 42, 47, 59, 65, 73, 80, 85, 107, 115], et/ou la classication [3, 7, 1214, 16, 27, 30, 32, 36, 37, 44, 46, 57, 70, 72, 74, 89, 112, 122], de ces documents. La classication a pour rle de regrouper des documents XML similaires dans des clusters (ou classes), an de rduire le temps de rponse et augmenter la prcision des moteurs de recherche. Cette classication peut tre thmatique ou structurelle. Dans cette thse nous nous intressons particulirement la classication de documents XML sur la base de leur similarit structurelle. Cette similarit permettra de regrouper des documents XML partageant les mmes structures. Ceci aiderait, dune part, mieux organiser ces 2

documents et, dautre part, mieux rpondre, en termes decience et decacit, aux requtes contenant des conditions structurelles. Notons que dans la RIS avec XML, les requtes peuvent tre formules en utilisant des mots cls seulement ou des mots cls et des conditions structurelles. En bref, cette classication vise regrouper les documents XML structurellement similaires an dacclrer le processus de recherche dinformation. En eet, la recherche dune information pertinente dans une grande collection, revient alors interroger des classes de taille rduite. Ceci est bas sur lide que si des documents XML partagent des structures similaires, ils sont plus mme de correspondre la partie structurelle dune mme requte. Notre problmatique de classication se situe donc essentiellement au cur de linformation structurelle. A cet eet, les questions primordiales que nous aborderons sont : Comment regrouper structurellement des documents XML quand leur DTD (Document Type Denition) nest pas connue ? Comment peut-on mesurer leur similarit structurelle ? Cette similarit soulve dautres questions lies notamment au degr de similarit des structures, en particulier : A partir de quel seuil de similarit pourrait-on considrer que deux documents sont structurellement similaires ? Une problmatique vidente et rcurrente concerne les duplications des lments XML. La question est Comment doit-on traiter ces duplications ? Considrons titre dexemple les squences abstraites abbbc , abc et abbbbbbbc . Alors, si ctait en RI classique avec des documents plats o les b sont des mots, la solution serait de pondrer par exemple b sa frquence dapparition dans le document. En revanche, en RIS avec des documents semi-structurs comme XML, de nouvelles considrations peuvent entrer en jeu. En eet, de par la structure hirarchique de ces documents, le mot b constituant un nud de la structure, peut se dupliquer plusieurs niveaux et, ce titre, dirents cas peuvent se prsenter. Dans le cas o la duplication de b concerne des nuds frres, elle doit tre limine an dobtenir abc comme structure cible minimale reprsentative. Par consquent, les documents XML reprsents respectivement par les squences abbbc , abc et abbbbbbbc peuvent tre considrs comme tant structurellement similaires la squence abc . Mais si cette duplication apparait en profondeur, il faut la conserver de sorte viter une perte dinformation. En eet, la suppression de duplications en profondeur entraine systmatiquement la destruction de la hirarchie de la structure et, de ce fait, produit des rsultats incohrents vis--vis de la classication structurelle envisage. Une autre problmatique tout aussi importante que sensible concerne linclusion des structures XML entre elles. En eet, si lon part du principe que la structure dun document peut tre incluse partiellement ou compltement dans celle dun autre document, il convient de caractriser cette inclusion. Il existe plusieurs types dinclusion qui ont plus ou moins un certain impact sur les similarits structurelles des documents correspondants et, en consquence, sur la classication structurelle qui en dcoule. Cette inclusion, quelle soit induite, incruste ou une subsumption, elle a t utilise pour intgrer des sous-structures frquentes en vue de construire un (ou plusieurs) schma(s) mdiateur(s) XML [28, 95]. 3

Introduction gnrale Il y a des cas o lon favorise linclusion induite [28], an de ne valider dans le processus dintgration que les sous-structures les plus frquentes rpondant linclusion induite, cest--dire des sous-structures de documents XML homognes. Dans dautres cas, cest souvent la subsumption [95] qui est adopte, car elle est plus gnrale et permet, de ce fait, de cibler des documents XML htrognes. Considrons prsent la problmatique de la similarit structurelle qui a t aborde de deux manires direntes : Dans les approches de construction de schmas mdiateurs la problmatique a t aborde en termes de dtection de sous-arbres (ou sous-structures) apparaissant sufsamment frquemment dans des corpus darbres. Un document XML est constitu gnralement de plusieurs sous-arbres distincts mais un sous-arbre lui mme peut apparaitre au niveau de plusieurs documents XML. Autrement dit, au lieu de parler de similarit directement entre structures compltes de documents XML, on parle de celle de leurs sous-structures. La tche se prsente, par contre, diremment dans les approches classiques de classication. En eet, par exemple une structure s1 peut tre incluse dans une autre structure s2 , telle que la longueur de s1 soit nettement infrieure celle de s2 . Alors le problme est Comment doit-on dans ce cas mesurer leur similarit ? En dautres termes : Doit-on tenir compte de la distance qui les spare ou bien occulter cette dernire ? Les rponses ces questions dpendent de plusieurs paramtres lis notamment la nature des corpus tudis, le domaine dapplication abord, etc. Il va donc falloir que, toute mesure de similarit structurelle propose soit paramtrable et vite au maximum la perte dinformation. Notons cependant que, quelle que soit la stratgie adopte, schma mdiateur ou classication, la problmatique de comparaison de structures arborescentes est connue pour tre une tche caractrise souvent par des complexits algorithmiques particulirement leves. Toute tentative de rduction de ces complexits, sest gnralement solde par une perte dinformation. En eet, par exemple une classication darbres qui considre ces arbres comme des vecteurs, prendrait videmment moins de temps sexcuter, mais aurait cependant moins de crdibilit vis--vis de la tche. Les relations hirarchiques sont perdues, et on se trouve comme dans le cas de documents plats.

Contribution
Notre contribution consiste en plusieurs propositions et tente de rpondre aux questions souleves dans la section prcdente : 1. Concernant lindexation de documents XML, nous proposons un modle de reprsentation bas sur leur structure arborescente. Les nuds de la structure correspondent aux noms des balises (tags XML) et attributs apparaissant au niveau des lments des documents XML considrs. Mais, an de minimiser les traitements, les documents XML sont reprsents par des rsums darbres . Autrement dit, ce nest pas toute linformation structurelle qui est utilise pour reprsenter structurellement un 4

document XML. Lide est que les rptitions des tags et/ou la possibilit davoir des tags optionnels (et leurs sous-arbres par voie de consquence), sont parmi les principales raisons qui font que des documents XML peuvent tre structurellement dirents mme sils partagent la mme DTD. Un rsum darbre peut alors tre considr comme une structure arborescente gnrique dans le sens o lorsque les nuds (tags) frres sont dupliqus, il nest pas ncessaire de rpercuter cette duplication dans la structure reprsentative que nous voudrions obtenir. Notons cependant que par souci de non perte dinformation et de non destruction de la hirarchie de la structure XML, les duplications des nuds imbriqus ne sont pas limines. Dans le mme contexte, supprimer ou ignorer des attributs peut entrainer une perte dinformation. Alors un moyen de contourner cet inconvnient, serait de considrer les attributs comme des nuds descendants directs des lments auxquels ils sont rattachs dans les documents XML. 2. Concernant la similarit structurelle de ces documents, nous proposons une mesure de similarit qui prend en considration la hirarchie de la structure XML. A cet eet, le calcul de la similarit entre deux termes (nuds) ncessite non seulement dutiliser un dictionnaire (quand il le faut), mais aussi, de considrer chaque nud dans son tendue contextuelle. Lide est que mme si deux nuds sont reprsents par le mme nom ou des noms synonymes, cela nimplique pas quils demeurent ncessairement identiques ou similaires dans le contexte de leurs anctres respectifs, qui peuvent tre compltement dirents. Ainsi, la similarit de deux nuds dpend non seulement de leur similarit ontologique (les termes peuvent tre similaires parce quils sont reprsents par la mme chaine de caractres, ou bien peuvent tre synonymes, daprs le dictionnaire), mais aussi, de celle de leurs anctres respectifs. 3. Enn, pour tendre notre modle de reprsentation de documents XML, nous proposons un algorithme de clustering (classication) qui consiste regrouper les documents XML partageant la mme structure ou des structures similaires. Notre algorithme est caractris par un certain nombre de points importants. En eet, notre clustering est incrmental et non supervis. De plus, contrairement au clustering classique, o le nombre de documents est xe, dans notre cas, de nouveaux documents peuvent tre ajouts, et leur nombre dans un cluster est une fonction du temps. Ainsi, notre clustering demeure ouvert et peut donc traiter de nouveaux documents tout moment. Par ailleurs, notre clustering est caractris par la mobilit des centrodes. Un centrode est larbre le plus pertinent reprsenter tous les arbres dun cluster, cest en quelque sorte, le centre de gravit du cluster. Cette mobilit garantit un clustering de qualit, cest--dire augmente la similarit intra-clusters et diminuerait, par voie de consquence, la similarit inter-clusters. Une autre caractristique intressante de ce clustering est le seuil de similarit que lon pourrait modier loisir en fonction des besoins. Une consquence trs importante de ce modle est que, au del de la classication qui constitue un des objectifs de cette thse, les clusters (ou classes) peuvent jouer le rle dinterface avec un utilisateur et permettront ainsi un accs ecace aux documents XML quils reprsentent.

Introduction gnrale Pour valider exprimentalement lintrt de notre approche et vrier la faisabilit des propositions qui la sous-tendent, nous avons ralis plusieurs types de tests. Les expriences ont t menes sur deux ensembles de donnes, savoir, une collection de documents XML relle (ACM SIGMOD Record corpus), ainsi quune collection de documents XML synthtique. Le premier test eectu consiste utiliser certaines mtriques bien connues comme la puret, lentropie et la F-mesure pour valuer les performances de notre clustering. Le deuxime test consiste comparer la mesure de similarit propose la mesure de similarit base sur la distance ddition. Le troisime test consiste vrier la faisabilit et la abilit de notre approche de reprsentation des documents XML. Le quatrime test a pour objectif de comparer nos rsultats avec ceux de certaines approches existantes. Enn, un test de timing est eectu sur une collection synthtique de documents XML et a permis de situer notre approche par rapport certains travaux existants. La conclusion que lon peut tirer de cette exprimentation est que les performances de notre systme sont comparables aux meilleurs rsultats obtenus recemment [94] par les travaux sur la classication structurelle de documents XML.

Plan du rapport de thse

Ce rapport est organis comme suit : Un rsum gnral (Rsum) dans lequel nous avons dni le cadre de notre travail en montrant quelle est lapproche propose, ainsi que la dmarche suivie pour atteindre les objectifs assigns. Une introduction (Introduction gnrale) dans laquelle on a dlimit le contexte de notre tude et identi les direntes problmatiques engendres par le format XML, en nous focalisant particulirement sur la structure des documents XML. Nous avons ensuite mis en valeur les objectifs viss travers le modle de reprsentation de documents XML envisag. Nous avons dans ce contexte trac quelques brins de pistes qui donnent une ide sur lobjectif principal assign. Nous avons au passage donn un aperu gnral sur notre contribution dont la dmarche est dtaille au chapitre 5. Nous avons galement trac les grandes lignes de la mise en uvre et des exprimentations ralises pour valider notre approche. Enn, nous terminons par le plan du rapport de thse. Dans le premier chapitre (Prsentation de XML), nous avons commenc par une section introductive (1.1 Introduction), an davoir une ide sur lvolution des donnes, et voir ainsi comment lon est pass de la catgorie des donnes non structures et fortement structures celle des donnes semi-structures. La section (1.2 Historique des langages de balisage) raconte un peu lhistoire des langages de balisage et les circonstances de la naissance de XML. Les sections (1.3 XML en tant que spcication de base), (1.4 Structure dun document XML), (1.5 Type de document), (1.6 Document bien form, document valide), (1.7 Association dune 6

DTD un document XML) et (1.8 XML-Schema), sont consacres lessentiel sur la spcication de base XML. Nous avons particulirement insist sur la notion de DTD (Document Type Denition), car elle couvre plus ou moins laspect structurel dun document XML, chose qui intresse la problmatique que nous tudions dans cette thse. Nous avons aussi expliqu la tche de parsing (1.9 Quest ce que le parsing ?), en nous appuyant sur lexemple classique dun compilateur et, au passage, nous avons dcrit succinctement les deux API (Application Programming Interface) existantes, en loccurrence le DOM (Document Object Model) (1.10 DOM) et SAX (Simple API for XML) (1.11 SAX). Enn, nous avons montr (1.12 Fichiers XML), comment peut-on crer, modier, sauvegarder un chier ayant lextension .xml, et mis laccent sur le fait quun document XML possde une version texte exploitable sur nimporte quelle plate forme. Dans le second chapitre (Indexation de linformation structurelle de documents XML), nous avons prsent un tat de lart sur lindexation base sur la structure des documents XML. Pour se placer dans le contexte (2.1 Introduction), nous avons au pralable montr lintrt de la structure dans le cadre de la classication structurelle de documents XML. En section 2 (2.2 Le processus dindexation), nous avons introduit quelques concepts de base sur lindexation an de pouvoir situer le modle dindexation envisage dans cette thse. Dans la section 3 (2.3 Approches dindexation de linformation structurelle de documents XML), comme prconis, nous avons prsent les approches dindexation de linformation structurelle de documents XML. Nous nous sommes focaliss uniquement sur celles qui ont t utilises dans le cadre de la classication structurelle ou de lintgration de schmas XML. Mais avant cela, nous avons introduit au pralable certains concepts et dnitions utiles sur les arborescences. Le troisime chapitre (Classication) a pour objectif de stendre sur la classication en gnral. Une premire section introductive (3.1 Introduction) met en avant lvolution de cette tche par rapport lvolution des besoins et met en exergue les objectifs viss travers la classication dans la RI. Les autres sections (3.2 Notion de classe), (3.3 Dnition formelle de la classication), (3.4 Le ranking), (3.5 Le clustering) (3.6 Contextes de classication), expliquent certaines notions gnrales sur la classication. Les autres sections (3.7 Paramtres dvaluation des performances dun systme de classication), (3.8 valuation dun classieur bi classes), (3.9 valuation de classieurs multi classes) et (3.10 valuation dun systme de clustering) sont consacres entirement ltude des mesures et danalyse des performances des systmes de classication dans la RI. Le quatrime chapitre (Classication structurelle de documents XML) donne un aperu sur la classication de documents semi-structurs en gnral et un tat de lart sur la classication structurelle de documents XML en particulier. Le cinquime chapitre (Modle de clustering incrmental bas sur des rsums darbres) a t consacr entirement la description de notre approche qui consiste en plusieurs propositions : la reprsentation de documents XML base sur leur structure, la mesure de leur similarit structurelle et, enn, leur classication sur la base de leur similarit structurelle. Le sixime chapitre (Exprimentation) est ddi lexprimentation des di7

Introduction gnrale rentes propositions concernant notre apport dans cette thse. Enn, une conclusion (Conclusion gnrale), o nous avons rcapitul les points essentiels de notre contribution en la situant par rapport certains travaux connexes et, en perspective, nous indiquons les pistes suivre pour le perfectionnement de notre approche.

Chapitre 1 Prsentation de XML

1.1 Introduction

Historiquement les donnes sur supports informatiques taient, soit des donnes simples et bien structures, stockes dans des bases de donnes, soit des donnes purement textuelles non structures, stockes dans des documents sous forme de chiers format libre. Il tait alors nettement facile de distinguer entre deux principaux formats, en loccurrence, celui des donnes fortement structures qui est pris en charge par la communaut des BD et celui des donnes non structures, qui est pris en charge par la communaut de la RI. Aujourdhui cependant, avec lapparition des donnes semi-structures de type HTML ou XML, les documents traditionnellement plats ne contenant que du texte senrichissent dinformation structurelle et dinformation multimdia [85]. A linverse des formats traditionnels (donnes fortement structures et donnes non structures), le format XML apparat comme un compromis orant une solution raisonnable pour lintgration de donnes en provenance de sources htrognes. En eet, aujourdhui nous demandons nos documents dtre achables sur nos PDA (Assistants Digitaux Personnels), dtre intgrs des bases de donnes ou dtre manipuls par des applications spciques. De plus, non seulement les informations quils contiennent sont rutilises, mais le volume de leurs changes saccrot continuellement. Les volumes dinformations que nous sommes appels traiter sont immenses, et ces informations ne peuvent plus tre lies une plate-forme spcique. De la mme manire que Java a mis notre disposition un langage indpendant de toute plate-forme, nous avons galement besoin de la mme indpendance lorsquil sagit de lchange de donnes. XML nous en ore le moyen [34]. Lutilisation de plus en plus croissante de ce nouveau format sur le Web a provoqu une explosion dans le dveloppement doutils permettant notamment le stockage, lindexation et la recherche dinformation dans ce type de donnes. Cet engouement pour XML est en soi un tmoignage et une premire justication de son ecacit pour la reprsentation et lchange de donnes sur lInternet. 9

Chapitre 1. Prsentation de XML

1.2
1.2.1

Historique des langages de balisage

Gense des langages de balisages

Avant de prsenter les langages de balisages, il convient dabord de comprendre comment les donnes sont stockes et rcupres sur un ordinateur. A ce propos, on peut considrer lexemple de deux types de chiers de donnes : les chiers binaires et les chiers texte [43]. Fichier binaire Dans sa forme la plus simple, un chier binaire correspond des suites de bits. Ces dernires ne sont, en gnral, interprtables que par lapplication propritaire (celle qui les a gnres). Les codes insrs (invisibles lachage du chier source) sont considrs comme des mtadonnes (des donnes propos de donnes). Ces mtadonnes correspondent des instructions de mise en forme du genre : Cette sentence doit tre centre , Ce mot doit tre gras ou color , etc. Lavantage est quil est facile un ordinateur de comprendre ces codes binaires, quils peuvent tre traits plus vite, et quils sont parfaitement adapts au stockage de mtadonnes. Linconvnient est quil nest pas possible de modier ce format en dehors de lapplication propritaire, ou dacher ces chiers sur des appareils dirents comme des PDA. Il est mme parfois impossible douvrir un chier binaire cr par une application dans une autre, voire dans la mme, mais sur une autre plate-forme [43]. Fichier texte Un chier texte est form galement de suites de bits, mais sans adjonction dinstructions de mise en forme (mtadonnes). Ces suites de bits sont regroupes de faon standardise an de reprsenter des nombres. Ces derniers sont mis en correspondance avec les caractres quils sont censs reprsenter, en utilisant une table de codes ASCII. Les chiers texte peuvent alors tre lus par de nombreuses applications en utilisant un simple diteur de texte ou mme des bases de donnes. Il est galement possible de les manipuler laide de scripts [34]. Lavantage du format texte est quil a grandement contribu la monte en che dadoption dInternet, notamment ses dbuts, et la gnralisation dapplications comme le courrier lectronique, le World Wide Web, etc. Cependant, linconvnient avec le format texte, est quil est dicile dinsrer des mtadonnes. Par consquent, il nest possible de sauvegarder ou de rcuprer ce type de chier que sous forme de texte brut sans aucune autre mise en forme [43].

1.2.2

Langages de balisage

Lidal serait de possder un format combinant luniversalit du format texte avec lecacit et les puissantes capacits de stockage de formats binaires. Cette ide de luniversalit des donnes nest pas nouvelle. En fait, depuis que les ordinateurs existent, les programmeurs ont toujours tent de trouver des moyens pour changer des informations entre dirents programmes informatiques [43]. 10

1.3. Spcication XML SGML (Standard Generalized Markup Language), tant la premire tentative de combinaison dun format de donnes universellement changeables avec une importante capacit de stockage dinformations. Historiquement, ce langage est issu dun projet dmarr chez IBM dans les annes 1970 par C. Goldfarb, E. Mosher et R. Lorie, avant dtre rejoint et dvelopp par de nombreuses quipes de travail, avant son adoption comme standard ISO-8879 en 1986. SGML correspond un langage de type texte conu pour tre un standard de balisage de donnes multi-usages et sest vite impos, essentiellement dans les gros systmes de gestion de documents. Cependant, lorsque dnormes quantits de donnes sont concernes, une multitude de considrations entrent en jeu. Cela explique lextrme complexit de ce langage [43]. Lapplication la plus populaire du SGML qui a connu un grand succs, est incontestablement le langage HTML (HyperText Markup Language). Apparu en 1993, il est considr comme un langage universel de balisage destin particulirement lachage des informations, ainsi qu la liaison de dirents morceaux dinformation. Initialement conu par Tim Berners-Lee au CERN (Conseil Europen pour la recherche Nuclaire), en dcembre 1990 pour aider les chercheurs en Physique communiquer entre eux et avec les autres, est devenu par la suite le premier standard de dveloppement Web, en partie grce sa simplicit dapprentissage. Il a notamment contribu au dveloppement rapide de linfrastructure technique ncessaire pour rendre ecace lInternet, rendant ainsi accessible de faon quasi instantane la plus gigantesque masse dinformations jamais ralise. Tout document HTML ou page Web, doit pouvoir tre prsent dans toute application capable de comprendre HTML. Un navigateur Web recevant des pages HTML doit pouvoir interprter le code quelles contiennent. Autrement dit, un navigateur doit pouvoir acher un document, mais si la page contient des liens hypertextes vers dautres documents, il doit pouvoir les rcuprer avec facilit [15, 26, 43]. Cependant, avec lvolution des besoins, le HTML apparat comme une solution inadquate, de porte limite, car incapable de satisfaire certaines exigences telles que la rutilisation dun document HTML dans dautres formats (autres que HTML), lintgration et la connectivit aux bases de donnes, ladaptabilit aux PDA ou tlphones mobiles, etc. ; sa seule fonction demeure lachage des informations dans un navigateur, et ne va pas au del. XML (eXtended Markup language) a t cr, dune part, pour combler les limitations de HTML, dautre part, pour orir une solution adquate ayant les mmes objectifs que SGML (balisage de tout type de donnes), dbarrasse toutefois de toute complexit superue [15, 34, 43]. Lide de se servir du meilleur du HTML et du SGML a germ au sein du groupe de travail XML Working Group sous lgide de W3C (World Wide Web Consortium). XML a t mis au point ds 1996, la premire version XML 1.0, est apparue au mois de fvrier 1998, depuis, ses spcications sont passes au stade de recommandation. Aujourdhui, il est considr commme le format de rfrence de la publication et des changes, et joue notamment un rle crucial dans la diusion de documents sur Internet.

1.3

Spcication XML

XML ore une syntaxe de balisage qui permet de dnir un langage, ce qui en fait un outil capable de produire des documents primaires dont la structure conceptuelle se 11

Chapitre 1. Prsentation de XML prsente comme une suite hirarchique dlments enchsss les uns aux autres. En consquence, le document devient un ensemble dinformations structures, un conteneur dinformations plus quune unit de base, ce qui permet aux outils de gestion de se concentrer sur le contenu du document plus que sur le document lui-mme, de mettre en relation le texte lui-mme et sa structure, puis dexploiter ces relations [43, 61]. La syntaxe de XML, dnit un langage balises personnalisables permettant ainsi chaque utilisateur de concevoir ses propres balises. Ces dernires permettent de sparer le contenu de la mise en forme (structure) dans chaque document cr. En dautres termes, XML nest pas seulement un langage, mais un mtalangage, qui dcrit une syntaxe permettant chacun de crer ses propres langages [43]. Si lon considre par exemple le document XML de la FIGURE 1.1 <nom>, <prenom> et <famille> sont les balises, elles correspondent linformation structurelle (ou la structure) du document, tandis que la partie complmentaire correspond ce quon appelle, contenu. XML permet de dcrire ainsi le mme contenu dun document en adoptant, soit le format de la FIGURE 1.1, soit celui de la FIGURE 1.2. Cet exemple, aussi simple soit-il, nous permet de comprendre pourquoi les langages de balisage tels que SGML et XML sauto dcrivent. En eet, en regardant les donnes de ces deux documents, on comprendra facilement quil sagit dinformations propos dun <nom>, dun <prenom> et dautres nommes <famille>, <prenom1> et <prenom2>. Il est possible dattribuer aux donnes nimporte quelle appellation, mais si on doit utiliser XML, autant le faire dans les rgles de lart, donner aux entits des noms signicatifs [43]. Cette question a t aborde par lintroduction de certains vocabulaires XML spciques [4]. Parmi les applications XML concernes, nous pouvons citer MathML, VML, WML, PGML, etc.

Figure 1.1 Document XML

Figure 1.2 Document XML une autre version 12

1.4. Dnition dun document XML

1.4

Dnition dun document XML

Un document XML est compos dun corps (body) et, ventuellement, dun entte (prologue), qui est la partie dclarative o sont rpertories les dclarations comme la version, la DTD rfrence, ainsi que dautres types de dclarations. Cependant, il faut signaler que, hormis la dclaration formelle dune DTD (lorsquelle existe), qui doit apparatre dans lentte (une seule fois uniquement), les autres dclarations, les instructions etc., ne sont soumises aucune contrainte et, donc, peuvent apparatre nimporte quel niveau du document. XML laisse une grande libert aux utilisateurs de crer leurs documents comme ils le souhaitent, pour peu quils respectent sa syntaxe. Le corps dun document XML consiste essentiellement en un arbre dlments. La racine de cet arbre correspond llment racine (Document Element) du document. Les autres nuds de larbre correspondent aux lments descendants de llment racine du document. Les lments dun document XML possdent des relations de type (parent, enfant). Les parties de larbre, possdant un enfant sont nommes branches, tandis que les parties dpourvues denfants, sont nommes feuilles ou nuds terminaux. Chaque document ne possde quun seul lment racine qui contient tous les autres [43]. Par exemple, la FIGURE 1.3 donne une ide sur la structure logique dun document XML.

Figure 1.3 Structure arborescente dune page XML En gnral, les lments XML peuvent contenir du texte et dautres lments qui sont leurs sous-lments ou leurs descendants. Les lments sont dcrits comme ayant un contenu mixte. En eet, sur le document de lexemple de la FIGURE 1.3 <parent> possde deux descendants : un descendant qui est la balise <nom> un autre descendant contenant le texte du texte dans mon lment On peut restructurer le document de la FIGURE 1.3 notre guise, en introduisant des attributs comme sur la FIGURE 1.4. Les attributs apportent des informations sur llment qui les contient (ils ne sont pas appropris pour contenir des donnes). Il ny a pas de limite sur le nombre dattributs utilisables dans un lment ; il faut cependant trouver un compromis entre utilisation dattributs ou emploi dun nouvel lment et garder lesprit que les lments dcrivent les donnes alors que les attributs dnissent les lments qui les contiennent.

13

Chapitre 1. Prsentation de XML

Figure 1.4 Page XML avec attributs Notons que le document de la FIGURE 1.4 est smantiquement quivalent celui de la FIGURE 1.3, ce qui a chang, cest uniquement la conception de sa structure. Cette mallabilit dans la manire de structurer un document est une richesse qui permet aux utilisateurs de XML, de crer leurs documents selon leur prfrence. En fait, le format XML permet de produire aussi bien des documents structurs que des documents semi-structurs. Les documents structurs possdent une structure rgulire, cest dire ne contiennent pas dlments mixtes, et lordre des lments quils contiennent est gnralement indirent. Les documents semi-structurs possdent une structure exible et des contenus htrognes. La mise jour dune donne entrane une modication de la structure de lensemble. Dans [1], Abiteboul donne la dnition suivante : Par semi-structure nous signions que mme si les donnes possdent une structure, celle-ci nest que la structure requise par les systmes de gestion de bases de donnes traditionnels [85]. Une autre dnition rencontre dans [66] est : Nous appelons donnes semi-structure la donne qui nest (dun certain point de vue) ni une donne brute ni une donne strictement type [85]. Nous nous intressons dans cette thse aux documents semi-structurs reprsents par XML. Par abus de langage, nous sous entendons par RIS (Recherche dInformation Structure), la RI avec des documents semi-structurs. A lissue de cet aperu gnral sur les langages de balisage et du format XML en particulier, nous poursuivons notre description de XML, en essayant de dnir succinctement la DTD (Document Type Denition) et le XML-Schema. Nous donnerons ensuite un aperu gnral sur certains standards tels que DOM et SAX, qui ont t dvelopps conjointement XML an de faciliter laccs ce type de documents.

1.5

Type de document

La spcication de base dnit les DTDs, bien que celles-ci soient parfois considres comme une technique apparente. Par exemple, lorsque nous avons cr le code XML 14

1.6. Document bien form, document valide de lexemple de la FIGURE 1.1, nous avons conu une donne structure. Non seulement toutes les informations concernant un nom ont t incluses, mais la hirarchie comporte galement des informations implicites sur la faon dont certains morceaux de donnes sont lis dautres : comme par exemple, <nom> contient <prenom>. Encore mieux : nous avons galement cr un ensemble particulier dlments, appel vocabulaire. Dans la pratique, nous avons dni un ensemble dlments XML fonctionnant conjointement pour former le nom dune personne : <nom>, <prenom> et <famille>. Mais, la plus intressante cration, est un type de document. Bien que cela ne soit pas explicitement dni, les lments du vocabulaire doivent rpondre certaines rgles, an que le document soit conforme au type de document [43]. Par exemple : llment de plus haut niveau doit tre <nom> ; les lments <prenom> et <famille> doivent tre les descendants de cet lment ; les lments <prenom> et <famille> doivent se prsenter dans cet ordre ; il doit forcment y avoir des informations dans les lments <prenom> et <famille>.

1.6

Document bien form, document valide

Un document XML doit respecter certaines rgles grammaticales prsentes dans la spcication XML. Les documents XML doivent obir ces rgles pour tre considrs comme tant bien forms Well formed document . Par consquent, sil y a non-respect dune de ces rgles, dans un document, il sera dit non bien form. Tandis quun document XML sera dit valide sil est bien form et satisfait, en outre, aux rgles dune grammaire exprime par une DTD ou un XML-schema. Par exemple, si on oublie de fermer une balise, un message derreur sera ach. Cependant, si le document est bien form (sans erreurs syntaxiques), et quon omet dassocier un schma validant (par exemple une DTD), le parseur XML de base nenvoie aucun message derreur au navigateur. Nanmoins, si lon sollicite les services dun parseur validant, cest--dire qui intgre la DTD dans le parsing, une erreur sera systmatiquement signale au navigateur qui sera charg de lacher. Il convient prsent de montrer comment pourrait-on associer une DTD un document XML, et de quel type de DTD il sagit. XML ore plusieurs manires dassocier une DTD un document (DTD interne au document XML, externe mais dclare dans le document XML, etc.). Nous nous limitons dans ce rapport loption, o lon dclare une DTD dans le document XML. Autrement dit, cette dernire est dnie dans un chier externe portant lextension DTD.

1.7

Association dune DTD un document XML

Comme il est possible une personne de concevoir sa propre structure et ses noms dlments pour ses documents, les DTDs permettent de crer des modles pour ces types de documents. On peut eectuer une vrication pour tre sr que dautres documents respectent ces modles, tandis que dautres dveloppeurs peuvent produire des documents compatibles [43]. 15

Chapitre 1. Prsentation de XML

Un document XML est dit valide sil est bien form et obit, en plus, aux rgles grammaticales exprimes par une DTD ou un XML-Schema. La conformit du document ces rgles garantit sa validit. Mentionnons cependant, quil nest pas rare de rencontrer des documents XML sans DTD. Contrairement SGML, la dclaration dune DTD nest pas obligatoire en XML. Un document XML peut exister et tre ach travers un navigateur, sans pour autant que lui soit associe une DTD. Pour illustrer, considrons le document de la FIGURE 1.5 dcrivant une famille.

Figure 1.5 Document XML dcrivant une famille Aucune rgle ne contrle la structure de ce document. Si on supprime llment <pere>, ou si lon ajoute dautres lments <enfant>, cela nempche pas le document dtre ach par un Navigateur. Le but dune DTD est de dnir les lments qui peuvent tre utiliss dans un document XML et de spcier les relations entre ces lments. Chaque balise correspond un lment de la DTD. Dans le document de la FIGURE 1.5, nous avons un lment racine nomm <famille> dont la dnition est : < !ELEMENT famille (pere, mere, enfants ?)>. Cet lment contient les lments <pere>, <mere> et <enfants>. Ces lments sont lists selon lordre dans lequel ils doivent apparatre logiquement dans le document. Le symbole ? signie que llment <enfants> est optionnel. Une famille peut tre valide avec seulement les deux lements <pere> et <mere>. Les lments <pere> et <mere> sont dnis par : < !ELEMENT pere( PCDATA)> < !ELEMENT mere( PCDATA)> PCDATA correspond du texte qui sera analys par le parseur XML. Le troisime lment <enfants>, ne contiendra pas de texte, mais un ou plusieurs lments <enfant>. Ajoutons les lments <enfants> et <enfant> : < !ELEMENT enfants(enfant +)> 16

1.7. Association dune DTD un document XML < !ELEMENT enfant( PCDATA)> Llment <enfants> peut contenir des lments <enfant>. Le signe + signie quil y a au moins un lment <enfant>, et que cet lment peut tre rpt autant de fois que ncessaire. Llment <enfant> contiendra du texte comme les lments <pere> et <mere>. En rsum la DTD associe est la suivante : < ?xml version=1.0 encoding=ISO-8859-1 ?> < !ELEMENT famille (pere, mere, enfants ?)> < !ELEMENT pere( PCDATA)> < !ELEMENT mere( PCDATA)> < !ELEMENT enfants(enfant +)> < !ELEMENT enfant( PCDATA)> Pour dcrire les lments de la DTD, on emploie un formalisme emprunt la thorie des langages, en loccurrence, celui des expressions rgulires. Par exemple : enfant +, signie que llment <enfant> apparat au moins une fois. enfant *, signie que llment <enfant> peut ne pas apparatre du tout ou apparatre une ou plusieurs fois. Si on a (pere, mere), les lments <pere> et <mere>, doivent apparatre simultanment dans cet ordre, cest comme si nous avions crit (pere et mere). enfants ? signie que llment <enfants> est optionnel, cest--dire apparaissant une fois ou pas du tout. Si on crit (pere|mere), choix entre <pere> et <mere>, lordre dapparition na pas dimportance. Retenons quune DTD, quoique non impose dans la spcication de base, garantit la validit, facilite lchange et la rutilisation de documents XML. Une caractristique essentielle est quune mme DTD (externe) peut tre rfrence par plusieurs documents XML trs proches structurellement. Le fait, dans lexemple prcdent, que llment <enfants> soit optionnel, et/ou <enfant> apparait une ou plusieurs fois, prouve que lon peut associer un nombre potentiellement inni de documents XML structurellement similaires, tous engendrs par cette DTD. Nous pouvons alors assimiler cette dernire une classe. Notons cependant, que du point de vue de lchange des donnes, lutilisation de DTDs nest pas rellement pleinement satisfaisant pour les raisons suivantes : Une DTD ne permet pas de prciser le type des donnes (numrique, boolen, date, etc.) reprsentant le contenu textuel dun lment ou attribut. Elle ne dcrit que vaguement les cardinalits par les symboles ( ?, +, *). Elle nutilise pas le mme formalisme que les documents XML, ce qui rend le parseur validant plus compliqu. Pour pallier ces insusances, W3C a introduit en 2001 le XML-schema qui est une nouvelle forme de grammaire permettant de dnir des lments plus complexes avec un typage plus riche 17

Chapitre 1. Prsentation de XML

1.8

XML-Schema

Le XML-Schema adopte une syntaxe proche de XML et permet de dcrire la structure dun document XML de faon beaucoup plus complte que la DTD. Il est possible de prciser les types complexes, les cardinalits et types des attributs, mais cela engendre gnralement un document (XML-Schema) plus volumineux et plus dicile lire quune DTD. Lexemple suivant sur la FIGURE 1.6 et FIGURE 1.7 illustre ces caractristiques.

Figure 1.6 Document XML dcrivant une personne

Figure 1.7 XML-Schema associ au document XML de la FIGURE 1.6 Il importe prsent de dcrire succinctement quelques standards qui ont merg conjointement la spcication de base XML. Nous nous limitons SAX (Simple API for XML), dont nous nous sommes servis dans cette thse, et DOM (Document Object Model), juste titre informatif, pour le situer par rapport SAX. Mais avant cela, il convient de rappeler en quoi consiste le parsing dans le contexte XML.

1.9

Quest ce que le parsing en XML ?

Le parsing est ralis par un analyseur syntaxique appel encore parser en Anglais qui se lit parseur en Franais [15]. Cest la notation parseur que nous adoptons tout au long de ce rapport de thse. Typiquement un compilateur possde deux attributions [15] : 18

1.10. DOM Il ralise le parsing dun programme source et signale les ventuelles erreurs de compilation. Il fournit en sortie une traduction du programme source analys en langage machine, an que ce dernier puisse tre excut. De la mme manire que le compilateur, le parseur XML va sassurer dabord que le document XML analys est bien form (il avertira, lapplication en cas de malformation). Il va lui aussi remplacer les entits contenues dans le document XML par leur valeur eective. Certains parseurs dits validants sont capables de vrier galement que le chier (document XML) pars est conforme au schma XML (DTD ou XML-Schema) qui lui est associ. Ensuite, l o le compilateur gnre un arbre puis un excutable utilisable par la machine, le parseur sarrte la construction de larbre. Il laisse lapplication le soin deectuer les traitements ncessaires sur cet arbre via lAPI (Application Programming Interface) [15]. Le parseur est un utilitaire de bas niveau : on ne peut pas accder directement au rsultat du parsing. Cest lapplication qui utilisera ce rsultat pour eectuer ses traitements [15]. Un exemple trs simple est celui du parseur intgr au navigateur Microsoft Internet Explorer. Lorsquun document XML est ach par ce navigateur, on voit apparatre sa structure arborescente. LAPI est une interface de programmation que lon peut considrer comme une couche supplmentaire situe entre le parseur et lapplication [15].

1.10

DOM

DOM (Document Object Model) est lAPI standardise par le W3C. Cest une norme depuis le 1er octobre 1998. Le parseur DOM compile le chier XML et produit un arbre dobjets comme celui de la FIGURE 1.8.

Figure 1.8 Modle darbre DOM Le parsing du chier est valable si le document XML est bien form et seulement sil est valide dans le cas dun parseur validant [15]. Si le chier XML ne rpond pas ces critres le parseur DOM refuse de crer larborescence dobjets en mmoire. 19

Chapitre 1. Prsentation de XML Mais une fois larbre cr en mmoire, il devient accessible lapplication grce des mthodes daccs en consultation et en modication, fournies par lAPI DOM [15]. Pour mieux comprendre la porte des nuds (objets) de cet arbre en mmoire on donne un deuxime exemple concret illustr par la FIGURE 1.9 et FIGURE 1.10. Le chier XML de la FIGURE 1.9 dcrivant des tudiants, a pour arbre DOM en mmoire, celui de la FIGURE 1.10.

Figure 1.9 Document XML dcrivant un tudiant

Figure 1.10 Modle darbre DOM du document de la FIGURE 1.9 Ce mcanisme est coteux en termes de temps et de performance. De plus, il a un cot 20

1.11. SAX de stockage trs lev car il est trs vorace en mmoire, il engendre en moyenne 5 6 fois la taille dun document source [109]. En revanche, il autorise des traitements en profondeur du document XML, puisque larbre dobjets est entirement charg en mmoire centrale. Il existe un autre type dAPI dnomme SAX compltement dirente du DOM laquelle on fait appel, notamment dans des situations o lon na pas vraiment besoin de charger compltement larbre en mmoire, ou dans des cas dapplications spciques o le modle darbre que lon veut crer, serait trs dirent de larbre gnr par lAPI DOM.

1.11

SAX

SAX (Simple API for XML) a t dveloppe sur le modle des logiciels libres. Bien que nayant pas t normalise par le W3C, cette API a t implmente par la plupart des diteurs. Elle est considre ds lors comme un standard de facto. Contrairement DOM, le parseur SAX ne produit pas un arbre en mmoire pour un document XML. Il se contente dmettre des vnements de parsing, comme la rencontre dune balise ouvrante, dune balise fermante, dun commentaire, dune dclaration, etc. Ces vnements sont capts par lapplication pour eectuer ses traitements. LAPI met la disposition de lapplication un nombre ni de mthodes daccs au document. Ces mthodes correspondent aux vnements que le parseur est susceptible dinterprter au cours de sa lecture [15]. SAX permet de parcourir le document XML sans toutefois le conserver en mmoire. Ceci dit, donc une application utilisant SAX ncessitera peu de ressources en mmoire. En outre, les traitements sont plus rapides que DOM puisque la phase de stockage de larbre en mmoire nexiste pas. De ce fait, lusage de SAX est prconis, par exemple dans des applications serveurs charges de transmettre des informations rapidement entre des sources de donnes et des clients [15]. Il est galement fortement recommand dutiliser SAX lorsque les traitements auront lieu seulement sur la structure du document ou sur des sous-ensembles particuliers de la structure comme les sous-arbres. Cependant, si lon souhaite eectuer des traitements en profondeur sur un document XML, lusage du DOM savre plus pertinent et plus ecace. Nous ne pouvons aller au del de ce rsum que lon considre trs concis et largement susant pour comprendre les principes de base des deux API, ainsi que leurs caractristiques essentielles et les dirences quelles prsentent. Mais tant donn le caractre essentiel du parsing relativement la thmatique aborde dans cette thse, il convient de donner galement une ide sur la nature des chiers utiliss pour reprsenter des documents XML.

1.12

Fichiers XML

Un des points forts de XML est que son format est universellement admis par toutes les plates-formes [34, 43]. En eet, quel que soit le systme sur lequel on travaille, un document XML est cr initialement partir dun chier texte (comme par exemple 21

Chapitre 1. Prsentation de XML chier Bloc-notes ou WordPad sous Windows), que lon sauvegarde sous lextension xml. Ds quun tel chier est sauvegard, un document XML est systmatiquement cr. Ce dernier peut tre, bien ou mal form, mais il devient accessible un parseur XML. Le parseur en question, peut analyser syntaxiquement le texte du document et lacher sous forme arborescente travers un navigateur, en respectant la mise en forme, lindentation des dirents lments, etc. Lavantage est que, tout document XML possde une version texte telle quelle a t cre la base. Actuellement il existe des diteurs XML permettant aux utilisateurs de crer trs rapidement leurs documents. Il existe mme des gnrateurs de documents comme Altova XMLSpy 1 permettant de crer des documents XML partir de DTDs ou inversement des DTDs partir de documents XML. Parmi ces outils, on peut citer galement XTRACT [40] qui est un sytme qui extrait automatiquement des DTDs partir de documents XML. Mais quel que soit loutil utilis pour crer un document XML, celui-ci possde toujours une version texte (chiet texte) accessible en utilisant un simple diteur de texte. Lexistence de la version texte permet ainsi un utilisateur daccder toutes les informations appartenant au document XML, et de pouvoir les manipuler bon escient. En dautres termes, si on veut extraire la partie structurelle dun document XML, il sut de construire un parseur ad-hoc, qui fait appel par exemple SAX, pour analyser la version texte du document et gnrer en sortie un autre document XML sans contenu. Cest typiquement de cette manire que nous allons procder dans notre approche pour extraire par parsing, la structure dun document XML, qui sera ensuite utilise dautres ns. Cette structure peut, au besoin, subir dautres traitements tels que par exemple supprimer les balises redondantes inutiles ou considrer les eventuels attributs comme des nuds-ls des lments (balises) auxquels ils sont rattachs dans le document XML source, etc.

1. http ://www.altova.com/xmlspy.html

22

Chapitre 2 Indexation de linformation structurelle de documents XML

2.1 Introduction

Les SRI classiques travaillant habituellement sur des collections de documents plats, se focalisent uniquement sur les contenus, ignorant totalement la notion de structure et de liens pouvant ventuellement exister entre les documents. Mais avec lvolution des corpus documentaires, notamment avec lmergence des donnes semi-structures sur le Web, la donne a compltement chang [30]. En eet, les documents XML, de par leur format, imposent aux SRI de prendre en considration, aussi bien la structure que le contenu, an de cibler relativement avec une meilleure prcision, les units dinformation spciques et exhaustives correspondant au besoin de lutilisateur. Ainsi, un SRI, grce la composante structurelle de ce type documents, devrait pouvoir se focaliser sur les units dinformation pertinentes rpondant ce besoin. La composante structurelle peut par ailleurs servir tablir au pralable une classication structurelle de ces documents. Cette dernire a pour objectif doptimiser le processus de recherche dinformation. En dautres termes, au lieu de se borner, comme avec les SRI standards, une recherche dinformation sur une grande masse de documents, la classication structurelle permettra daner cette recherche, et la diriger slectivement vers une certaine classe rduite de documents. Le bnce ici, est double : rduire eectivement, la quantit de documents traiter, mais aussi, arriver regrouper des documents qui ont des structures similaires et, du coup, augmenter le nombre de documents pertinents retourns.

2.2

Le processus dindexation

Le processus dindexation eectue le transfert de linformation contenue dans le texte dun document vers un autre espace de reprsentation traitable par un systme informatique [84]. Lindexation joue un rle prpondrant dans la construction dun SRI. Sa nalit est doptimiser les procdures daccs aux bases documentaires. Il convient alors danalyser chaque document de la collection an de slectionner un ensemble restreint de 23

Chapitre 2. Indexation de linformation structurelle de documents XML mots reprsentatifs. Ces derniers seront plus facilement exploitables par le systme lors du processus de recherche dinformation. Lindexation permet ainsi de crer une reprsentation des documents dans le systme. Son rle est alors de trouver les concepts les plus importants du document (ou de la requte), qui formeront le descripteur du document [85]. Lindexation peut tre : Manuelle : chaque document est analys par un spcialiste du domaine ou par un documentaliste ; Automatique : le processus dindexation est entirement informatis ; Semi-automatique : le choix nal revient au spcialiste ou au documentaliste, qui intervient souvent pour choisir dautres termes signicatifs [85]. Lindexation manuelle permet dassurer une meilleure pertinence dans les rponses apportes par le SRI. Elle prsente toutefois plusieurs inconvnients : deux indexeurs dirents peuvent prsenter des termes dirents pour caractriser un mme document, et un indexeur deux moments dirents peut prsenter deux termes distincts pour reprsenter le mme concept. De plus, le temps ncessaire sa ralisation est trs important [85]. Dans le cas dune indexation semi-automatique [11, 63], les indexeurs utilisent un thesaurus ou une base terminologique, qui est une liste organise de descripteurs (mots cls) obissant des rgles terminologiques propres, et relis entre eux par des relations smantiques. Enn, lindexation automatique [64], regroupe un ensemble de traitements automatiss sur un document. On distingue : lextraction automatique des mots des documents ; llimination des mots vides ; la lemmatisation (radicalisation ou normalisation) ; le reprage de groupes de mots ; la pondration des mots ; la cration de lindex. Le choix et lintrt dune mthode par rapport aux autres dpendent dun certain nombre de paramtres, dont le plus dterminant est le volume des collections. On trouvera une tude comparative de ces mthodes dans [9]. Le rsultat de ltude montre que les avantages et inconvnients de chacune des approches squilibrent : le choix dune mthode doit tre fait en fonction du domaine, de la collection et de lapplication considre. En bref, lindexation constitue la description du document et de son contenu en vue de faciliter son exploitation. On distingue ce titre deux catgories dindexation : Lindexation par type : elle ore une description formelle du document en utilisant ses mtadonnes (type, auteur, titre, source, date, etc.), dont le vocabulaire est standardis an de permettre lutilisation de ces mtadonnes par le plus grand nombre doutils de recherche. Des documents semi-structures de type XML se prtent particulirement bien ce genre dindexation. Dans ce cas, la structure (balises et attributs), peut jouer le rle de mtadonnes : on parle alors dindexation structurelle de documents. Lindexation par concepts ou mots-cls : elle vise plutt le contenu du document pour faciliter les oprations de recherche. Il peut sagir ici, pour le concepteur du systme, de recenser les termes qui apparaissent le plus souvent ; on parle alors dindexation statistique. Il peut aussi sagir dun systme plus volu o le concepteur slectionne 24

2.2. Le processus dindexation les termes dans un thsaurus (liste de mots lis par des relations de hirarchie ou dquivalence) en rapport avec le document. On peut parler principalement de deux catgories dindexation dans le cadre de documents structurs ou semi-structurs : lindexation base sur la structure et lindexation base sur les contenus. Mais au vu de la problmatique de la classication structurelle tudie dans cette thse, nous nous intressons uniquement ici lindexation de documents XML sur la base de leurs structures. Ainsi, nous dcrirons sous peu certaines approches dindexation structurelle et donnerons ce titre, les caractristiques qui les distinguent.

Linformation structurelle est eectivement exploite pour reprsenter structurellement des collections de documents XML. Mais l aussi, on peut parler de deux genres ou plutt de deux niveaux dindexation structurelle. En eet, dune part, la composante structurelle peut tre utilise pour reprsenter (ou indexer) structurellement les documents en vue dtablir leur classication structurelle, dautre part, elle peut aussi fournir un index de deuxime niveau permettant dinterroger ecacement ces documents. Nous nous intressons, plus particulirement dans cette thse, lindexation permettant dtablir une classication structurelle de ces documents.

La structure tant la cl principale qui permettra alors dindexer structurellement les documents XML et donc dy accder plus facilement lors de sessions dinterrogation ou de recherche dinformation. La structure permet ainsi de dtecter la classe approprie dun groupe de document partageant la mme structure ou ayant des structures similaires. Par consquent, laccs un ensemble de documents dune mme classe, se fera sur la base dune structure commune reprsentant lensemble des documents de cette classe. Pour accder aux documents XML, il va donc falloir y accder par le biais dune requte qui permettra au systme de slectionner au pralable la classe approprie. Les classes qui seront priori de tailles rduites doivent donc garantir un accs rapide et une pertinence leve des rponses retournes par les moteurs de recherche. Lide est que, si des documents XML partagent des structures similaires, ils sont plus mme de correspondre la partie structurelle dune mme requte.

En somme, lorsquon veut interroger des documents XML, le systme de classication structurelle permettra travers lensemble des classes, laccs ces documents. Contrairement aux modles classiques de la RI dont laccs aux documents est eectu sur la base dune indexation des documents par mots-cls, laccs aux documents au format XML doit tre assur en partie dabord par les classes qui sont censes contenir ces documents. On peut en loccurrence assimiler ces classes des interfaces ou une forme dindex entre le moteur de recherche et les documents que lon souhaite interroger. Autrement dit, le reprsentant de chaque classe peut servir dinterface avec un utilisateur pour lui permettre dinterroger les documents qui sy trouvent. 25

Chapitre 2. Indexation de linformation structurelle de documents XML

2.3

Approches dindexation de linformation structurelle de documents XML

Comme prconis, nous prsentons les approches dindexation de linformation structurelle de documents XML. Nous nous focalisons uniquement sur celles qui ont t utilises dans le cadre de la classication structurelle ou de lintgration de schmas XML. Mais avant cela, il convient dintroduire au pralable certains concepts et dnitions utiles sur les arborescences.

2.3.1

Dnitions prliminaires

Dnition 2.1 (Arbre) Un arbre est un graphe orient, connexe sans cycle tel que : Il existe un nud et un seul o il narrive aucun arc. Ce nud sappelle la racine. Il arrive un arc et un seul en tout autre nud. Dnition 2.2 (Chemin) Un chemin dans larbre est une liste C = (x1 , x2 , ..., xk ) de nuds telle quil existe un arc entre chaque paire de nuds successifs i = 1, ..., k 1 (xi , xi+1 ) lensemble des arcs. La longueur du chemin correspond au nombre darcs parcourus, cest--dire k 1. Dnition 2.3 (Arbre ordonn) Un arbre est dit ordonn si les ls de chacun de ses nuds (non feuilles), sont lis par une relation dordre totale de gauche droite. Dnition 2.4 (Arbre tiquet) Soit E un ensemble dtiquettes. Un arbre T tiquet par E est dni par (T, ) tel que est une application qui associe chaque nud de T une tiquette de E . Denition 2.5 (Sous-arbre frquent) Un sous-arbre frquent est un sous-arbre apparaissant dans la plupart des arbres dune fort considre. Dnition 2.6 (Inclusion) Il existe de nombreuses manires de dnir linclusion entre deux arbres T1 et T2 . Toutes ces dnitions se basent sur lexistence dune application de mapping (correspondance) des nuds de T1 vers les nuds de T2 . Ce mapping prserve de manire faible ou forte les tiquettes des nuds et la structure de larbre. Les dirences proviennent des proprits de prservation qui sont considres, ainsi que de linjectivit ou non du mapping [95]. Lauteur dans [51] a dni 10 relations dinclusion darbres direntes [95]. Pour simplier, nous exprimons les dirents types dinclusion par des exemples concrets. Nous nous limitons cependant celles qui sont les plus largement employes. Dans la FIGURE 2.1 est donn lexemple dun arbre T1 inclus dans T2 selon linclusion stricte exacte ordonne. Mais les arbres T3 T7 ne sont pas inclus dans T2 selon cette dnition. Cependant, il existe une relation dinclusion stricte exacte entre T3 et T2 (FIGURE 26

2.3. Approches dindexation de linformation structurelle de documents XML 2.2), et une relation dinclusion stricte ordonne entre T4 et T2 (FIGURE 2.3). Entre T5 et T2 , il ya une relation dinclusion stricte (FIGURE 2.4). Et entre T6 et T2 , on peut trouver une relation dinclusion stricte faible (FIGURE 2.5). Enn, entre T7 et T2 , il existe une relation dinclusion exacte ordonne (FIGURE 2.6).

Figure 2.1 Inclusion stricte exacte ordonne

Figure 2.2 Inclusion stricte exacte non ordonne

Figure 2.3 Inclusion stricte ordonne non exacte 27

Chapitre 2. Indexation de linformation structurelle de documents XML

Figure 2.4 Inclusion stricte non ordonne non exacte

Figure 2.5 Inclusion stricte faible non ordonne, non exacte

Figure 2.6 Inclusion non stricte, mais exacte et ordonne Dans la TABLE 2.1 sont rcapituls les types dinclusion voqus ci-dessus. Stricte OUI OUI OUI OUI OUI NON Faible NON NON NON NON OUI Exacte OUI OUI NON NON NON OUI Ordonne OUI NON OUI NON NON OUI

FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE

2.1 2.2 2.3 2.4 2.5 2.6

Table 2.1 Tableau rcapitulatif des types dinclusion voqus 28

2.3. Approches dindexation de linformation structurelle de documents XML Les documents informatiques structurs se prtent particulirement bien la mise sous forme arborescente, comme cest notamment le cas de documents XML, qui ont t conus an de stocker linformation sous une forme structure [95]. La FIGURE 2.7 montre un exemple de document XML et la structure arborescente associe.

Figure 2.7 Un document XML simple et larbre des balises associ [95] Notons que cette structure correspond un arbre tiquet ordonn. En eet, chaque nud a comme tiquette une balise du document XML. En outre, lordre squentiel des balises dans le document XML se traduit par lordre des nuds-ls dun nud donn dans larbre correspondant. Il est donc possible de considrer cette structure arborescente comme un index de linformation structurelle du document XML source. Notons cependant que ce nest pas toute linformation structurelle qui est utilise pour former un index. Trs souvent, cest une forme gnrique trs reprsentative o lon limine toute forme de redondance en vitant autant que possible la perte dinformation.

2.3.2

Indexation base sur les sous-arbres frquents

La motivation lorigine de la recherche de sous-arbres frquents dans des collections darbres vient notamment de lanalyse de documents lectroniques. Ainsi, les approches prsentes dans [10, 119] ont pour donnes dentre des traces de navigation dans des sites Web, ou encore des documents informatiques mis sous forme arborescente comme les documents XML. Dans [95], lauteur a abord la mme problmatique sous langle dextraction darbres frquents dans un corpus htrognes de donnes semi-structures XML. Lauteur dans [28] a, quant lui, tudi la mme thmatique, mais pour des sousarbres ordonnes frquents, en vue dintgrer des documents XML homognes. Dans ce contexte, tant donn une fort darbres XML, cest--dire une base de structures arborescentes associes une collection de documents XML, un sous-arbre frquent est inclus dans la plupart des arbres XML de cette fort, tandis quun arbre XML peut contenir un ou plusieurs sous-arbres frquents. Autrement dit, plusieurs documents XML peuvent tre structurellement indexs par un mme sous-arbre frquent (intgration), tout comme il est galement possible de voir un mme document XML index par plusieurs sous-arbres frquents (recouvrement). Lindex de linformation structurelle dun document XML peut donc tre compos dun ou plusieurs sous-arbres frquents. Cependant, ces derniers peuvent tre distingus selon quils soient ordonns ou non et/ou exacts ou non. Dans le contexte du traitement de documents XML homognes, il savre ncessaire de traiter lordre si celui-ci est spci par une DTD ou un schma XML.

29

Chapitre 2. Indexation de linformation structurelle de documents XML Ainsi, les approches [10, 95, 119], ont toutes en commun la dcouverte de sous-arbres frquents, mais elles dirent sur la dnition de linclusion dun arbre dans un autre. En eet, pour [10, 28], les sous-arbres frquents apparaissent selon une inclusion induite, cest--dire une inclusion stricte et exact, mais ncessairement ordonne, comme cest le cas de la FIGURE 2.1 et FIGURE 2.8. Notons cependant que lordre peut tre indirect comme sur la FIGURE 2.9. Par contre, [119] est plus permissif, cest--dire quil considre quun arbre est inclus dans un autre, comme cest le cas pour larbre T4 de la FIGURE 2.3 et pour linclusion entre les arbres T1 et T2 de la FIGURE 2.10, mme si limbrication des nuds nest pas exactement la mme que celle de linclusion induite. Ceci permet de retrouver des sous-arbres frquents malgr une certaine htrognit dans les structures des arbres XML de la fort considre. Toutefois, les approches [10, 28, 119] se retrouvent sur un point : les ls/descendants dun nud doivent toujours se trouver dans le mme ordre, pour faire partie dun sous-arbre frquent. Quant lapproche [95], elle gnralise les travaux prcdents et permet une plus grande exibilit dans linclusion, cest--dire quelle considre, comme sur la FIGURE 2.4 et FIGURE 2.11, quun arbre est inclus dans un autre sans tenir compte de lordre des frres, et en autorisant au besoin des variations dans limbrication des nuds comme dans lapproche [119]. En somme, les approches [10, 28] sont bases sur linclusion stricte, exacte et ordonne travaillant sous les contraintes de DTDs ou de schmas XML. De ce fait, elles ne sintressent quaux documents XML homognes. Lapproche [119], quant elle, est lgrement moins contraignante, cest--dire quelle autorise davoir les sous-arbres frquents non exacts. En revanche, [95] en permettant une plus grande exibilit dans linclusion, permet de traiter des documents XML htrognes.

Figure 2.8 Arbre frquent selon linclusion stricte exacte ordonne Lindexation de linformation structurelle de documents XML base sur le formalisme des arbres frquents considre que deux documents XML sont dautant plus proches structurellement quils possdent des sous-arbres frquents communs. Linconvnient est que la dirence de taille entre les structures arborescentes associes na aucun impact sur la proprit dinclusion. En dautres termes, il sut que la relation dinclusion, au sens 30

2.3. Approches dindexation de linformation structurelle de documents XML

Figure 2.9 Arbre frquent selon linclusion stricte exacte et ordonne indirecte

Figure 2.10 Arbre frquent selon linclusion stricte ordonne non exacte sous-arbre frquent, soit satisfaite entre plusieurs documents XML, mme de direntes longueurs, que ceux-ci deviennent accessibles via un mme index (ou sous-arbre frquent commun). Rappelons ce titre que, plusieurs documents XML peuvent tre reprsents (indexs) structurellement par un mme sous-arbre frquent et que, par ailleurs, la structure dun mme document XML peut galement tre partage (recouvrement) entre plusieurs autres documents XML qui peuvent tre faiblement structurellement similaires (linformation structurelle commune peut tre ngligeable devant celle qui les distingue). La FIGURE 2.12 illustre schmatiquement cette situation. En eet, T1 et T2 sont des sousarbres frquents distincts inclus dans larbre T3 . Mais le fait quils partagent la structure T3 ensemble suppose que chacun deux est similaire T3 (indpendamment lun de lautre). Autrement dit, les documents XML correspondant respectivement T1 et T3 seront regroups ensemble (il en est de mme pour T2 et T3 ), car partageant la mme structure, ou retourns ensemble par le systme pour une mme requte quand bien mme ils renfermeraient des informations inutiles (ou non signicatives) par rapport la requte formule, comme cest le cas du document XML correspondant T3 , lorsquil est retourn par le systme conjointement avec celui de T1 (ou T2 ). En eet, T2 (ou T1 ) tant, bien entendu, 31

Chapitre 2. Indexation de linformation structurelle de documents XML

Figure 2.11 Arbre frquent par subsumption (inclusion stricte non ordonne non exacte) inclus dans T3 , mais il est distinct de T1 (T2 ) ; il sera donc considr comme une information inutile par rapport T1 (T2 ).

Figure 2.12 Extraction darbres frquents selon la subsumption [95] Outre, cet inconvnient qui aecte la prcision, voire la pertinence des rponses du systme, lautre inconvnient majeur concerne les complexits particulirement leves des algorithmes de dtection de sous-arbres frquents.

2.3.3

Indexation base sur les arbres et rsums darbres

La manire la plus triviale dindexer structurellement un document XML est de le reprsenter par sa structure arborescente comme sur la FIGURE 2.7. Mais pour des raisons doptimisation certaines approches utilisent des formes gnriques comme variantes 32

2.3. Approches dindexation de linformation structurelle de documents XML de cette reprsentation. Ainsi, cette structure pourrait tre, soit un arbre tiquet correspondant la structure XML originale du document [12, 37, 70, 72, 74, 94], soit un rsum darbre [5,6,27]. Lapproche rsum darbre a lavantage de rduire la complexit algorithmique lors du clustering mais prsente nanmoins (dans certains cas), linconvnient de perturber certaines relations entre lments XML. La FIGURE 2.13 illustre comment dans lapproche [27] un rsum darbre est obtenu par deux transformations conscutives : (i) la premire rduit la profondeur de larbre de sorte que les ls de tout nud ayant la mme tiquette que lun de ses anctres deviennent les descendants directs (ls) de cet anctre ; (ii) la seconde, quant elle, limine les duplications des nuds frres. Larbre obtenu, peut ne pas tre exact mais il est enracin (sa racine est conserve). Tout comme dans [27], un document XML dans [5, 6] est galement reprsent par un rsum darbre tiquet enracin et ordonn, la dirence que celui-ci est obtenu par limination uniquement des duplications des nuds frres et transformation dattributs ventuels en descendants directs (ls) du nud (balise) auquel ces attributs sont rattachs dans le document XML source. La FIGURE 2.14 illustre cette approche de reprsentation et met laccent sur toutes ses caractristiques.

Figure 2.13 Extraction de rsums darbres [27]

Figure 2.14 Approche de reprsentation dun document XML [5, 6] En eet, la transformation de larbre original T1 en le rsum darbre T2 , montre que lattribut t devient eectivement un nud ls du nud a . Quant la duplication des nuds frres b , elle est limine tout en gardant les ls ( c , b et c ), tous rattachs une seule occurrence de b , mais les nuds ( c ) qui taient lorigine cousins sur T1 , sont devenus des frres dont il a fallu aussi liminer la duplication dans T2 . Cependant, 33

Chapitre 2. Indexation de linformation structurelle de documents XML comme prconis, les duplications des nuds imbriqus ( a et b ) sont maintenues.

Ainsi, au lieu dutiliser des arbres XML originaux pour indexer structurellement des documents XML, lapproche prconise dutiliser des rsums darbres, mais sans perte dinformation videmment. En eet, en gardant les attributs en tant que ls du nud correspondant la balise laquelle ils sont rattachs dans le document XML source, tout en liminant seulement les rptitions des nuds frres, nengendre aucune perte dinformation. Ceci permet, entre autres, deectuer un traitement plus rapide et ais de ces arbres. Notons aussi que, la hirarchie de la structure est bien conserve, contrairement [27] o celle-ci pourrait tre compltement modie, comme sur la FIGURE 2.13 o la hauteur de larborescence est passe de 4 3 niveaux, cause particulirement de la transformation (i) qui supprime toute rptition de nud sur tout chemin partant du nud racine aux nuds terminaux (feuilles).

2.3.4

Indexation base sur les vecteurs structurs

Le modle de reprsentation dun document XML par un vecteur structur SVM (Structured Vector Model) a t propos par [114]. Cest un vecteur dont les lments sont des termes (pour le texte), ou un autre vecteur structur (rcursivit) qui rete larborescence de la structure du document. Bien quil soit lorigine conu pour prendre en compte simultanment la structure et le contenu, il peut tre facilement dtourn au prot de la structure toute seule. La FIGURE 2.15 et FIGURE 2.16 illustrent respectivement un modle darbre XML et le vecteur SVM associ. Mais, an dassimiler plus facilement le formalisme du SVM, il convient tout dabord dexpliciter certaines notations avec leurs signications respectives (voir TABLE 2.2). Notation ed (0, 0) ed (i, j ) md (i, j ) md (i) hd td (i, j ) td (i, j ) ed (i, j ) Signication racine du document d j eme nud du niveau i nombre de ls du nud ed (i, j ) nombre de nuds du niveau i de d hauteur de la structure arborescente de d texte enchss dans ed (i, j ) vecteur reprsentant le nud feuille td (i, j ) vecteur reprsentant le nud ed (i, j )

Table 2.2 Notations utilises pour le SVM (arbre et/ou vecteur) Le document est donc schmatiquement reprsent par un vecteur structur dni formellement par ed (0, 0) =< ed (1, 0), ed (1, 1), ..., ed (1, md (i)) >. Les vecteurs sont dnis rcursivement : ed (i, j ) est constitu des sous-vecteurs ls ed (i +1, k ) avec 0 k md (i, j ). Pour comparer structurellement deux documents XML, le modle est exploit en comparant leurs chemins respectifs. Les auteurs [116] ont eectu des expriences sur deux 34

2.3. Approches dindexation de linformation structurelle de documents XML

Figure 2.15 Arbre XML bas sur les notations SVM

Figure 2.16 Modle SVM dun arbre XML corpus XML de petite taille avec des structures trs simples, leur modle ayant des dicults sadapter des structures complexes [30]. Une extension du modle [114] prend en compte les ventuels liens entre les documents dans le SVM. Lextension en question consiste en la reprsentation SLVM (Structured Link Vector Model), o les lments du vecteur sont les termes, la structure et le voisinage des documents. Notons que la prise en compte des liens donne lieu non plus une simple arborescence mais un graphe [115].

2.3.5

Indexation base sur les chemins (paths)

Les documents XML sont souvent reprsents (ou indexs) structurellement par des arbres tiquets dont les tiquettes correspondent aux balises, et ventuellement aux noms des attributs. Un exemple de document XML et de la structure arborescente associe est 35

Chapitre 2. Indexation de linformation structurelle de documents XML illustr par la FIGURE 2.7, plus haut dans la sous-section 2.3.1. Rappelons quun chemin consiste en une suite darcs orients tels que lextrmit terminale de lun soit identique lextrmit initiale du suivant. Intuitivement le chemin est le plus court trajet entre la racine de larbre et un nud considr. Un sous-chemin est un segment du chemin, cest--dire une portion du chemin. Cependant la notion de chemin que nous dnissons ici, couvre la fois celles de chemin et de sous-chemin. Les auteurs [102,103] ont choisi de reprsenter des documents XML par dirents sousensembles de chemins ou de sous-chemins. Cest une reprsentation linaire des arbres XML permettant daplatir leur arborescence tout en conservant leurs structures et donc de rduire les complexits des traitements. Lide de considrer les sous-chemins, et pas seulement les chemins, est que la similarit structurelle entre les documents peut apparatre dirents niveaux. Pour des collections de documents XML trs htrognes, les dirences et ressemblances apparaitront ds les premiers niveaux (proche de la racine). Pour les collections plus homognes, il peut tre intressant de ne conserver que les sous-chemins proches des feuilles, comme contexte au contenu textuel [102, 103]. Les chemins sont individuellement considrs comme des mots. Ce choix pose le problme dune ventuelle dpendance entre eux. Par exemple body.sec.st.it et sec.st.it ne sont videment pas totalement indpendants. Ceci est important lorsquon utilise des algorithmes de classication qui supposent que les mots sont indpendants, mme si cela nest pas compltement vri en pratique. Pour pallier cet inconvnient, ces chemins sont spars selon leur longueur. Dans TABLE 2.3 est prsent un ensemble de chemins avec leurs frquences respectives pour lexemple de FIGURE 2.17 et/ou FIGURE 2.18.

Figure 2.17 Document test.xml [102, 103] 36

2.3. Approches dindexation de linformation structurelle de documents XML

Figure 2.18 Arbre XML (avec contenu) associ au document de la FIGURE 2.17

Mots body.sec.bib body.sec.st body.sec.p body.sec.au body.sec.sno@

Tf 2 2 3 2 3

Table 2.3 Les paths (chemins) de longueur 3 avec leurs frquences respectives

2.3.6

Indexation base sur les niveaux

Lindexation base sur les niveaux est une approche ddie la classication structurelle de documents XML moyennant un parcours des structures arborescentes associes, par niveaux (Breadth First Traversal : Parcours en largeur dabord). Les documents XML sont reprsents structurellement par des arbres tiquets tout comme dans la plupart des approches, mais au lieu de les parcourir en profondeur, les parcours en largeur (ou par niveau) sont utiliss. Ainsi, les sous-ensembles (niveaux) des nuds visits correspondent des segments dindex de linformation structurelle dun document XML. On peut ce titre parler de la possibilit daplatir ces arborescences (tout comme dans lapproche dindexation par les chemins cite prcdemment), et les transformer en plusieurs sousensembles nomms ici niveaux. Lapproche [70] a exploit cette option pour la facilit quelle ore dans le calcul des similarits. En eet, il est plus pratique de calculer ces similarits progressivement par niveau que dopter pour un calcul direct entre deux arbres. La FIGURE 2.19 donne un aperu sur la subdivision en plusieurs niveaux de deux arbres T1 et T2 . Les niveaux peuvent tre exploits individuellement au cours de la comparaison des deux arbres, mais le fait de connaitre aussi leur position relative dans leurs arbres respectifs, permet ainsi de considrer leurs contextes hirarchiques (niveaux anctres et niveaux descendants) an de garantir une certaine abilit dans le calcul des similarits de leurs arborescences respectives. 37

Chapitre 2. Indexation de linformation structurelle de documents XML

Figure 2.19 Exemple dindexation base sur les niveaux des arbres

2.3.7

Indexation base sur les bitmaps

Dans [118], deux versions de reprsentation de documents sont proposes. La premire consiste utiliser une matrice binaire (index bitmap) 2 dimensions : les documents et les chemins des lments terminaux (feuilles) partir de la racine. Pour illustrer, la FIGURE 2.20 prsente un ensemble de simples documents XML, la TABLE 2.4 dcrit un index bitmap associ.

Figure 2.20 Exemple de documents XML Soit lensemble des chemins : p0 = e0 .e1 , p1 = e0 .e2 .e3 , p2 = e0 .e2 .e4 , p3 = e0 .e5 , p4 = e0 .e2 .e4 .e6 , p5 = e0 .e2 .e4 .e7 , p6 = e0 .e8 , p7 = e0 .e9 Le principe de construction de lindex bitmap est tel que si un chemin pi appartient un document dj , le bit de celui-ci est positionn 1, sinon il sera positionn 0. Les chemins et documents prcdents sont reprsents par lindex bitmap de la TABLE 2.4. Un aspect important et caractrisant de cette reprsentation est quelle est obtenue directement partir du document XML source et des dirents chemins considrs, contrairement aux deux approches prcdentes, savoir, lindexation par les chemins , et lindexation par niveaux , o la reprsentation est plutt issue de la structure arbo38

2.3. Approches dindexation de linformation structurelle de documents XML p0 1 1 1 p1 1 1 1 p2 1 1 1 p3 1 0 1 p4 0 1 0 p5 0 1 0 p6 0 1 0 p7 0 0 1

d1 d2 d3

Table 2.4 Un index bitmap des documents XML de la FIGURE 2.20 rescente associe au document XML. Cette reprsentation a t tendue 3 dimensions pour prendre galement en compte les contenus des documents. Ainsi, le BitCube (bitmap 3 dimensions) dun document XML est dni par le quadruplet (d, p, v, b), o d est le document XML, p est un chemin, v un terme (ou un contenu) dun chemin et b un boolen. Celui-ci est positionn vrai si p contient le terme v , f aux sinon. Ce type de reprsentation permet doptimiser les requtes dinterrogation de la collection.

39

Chapitre 3 Classsication
3.1 Inroduction

Apparue vers le dbut des annes 1960 mais qui sest largement dveloppe durant ces 20 dernires annes, la problmatique de classication automatique est considre comme une tche ancienne de la RI [30]. Les mthodes de classication (Taxonomies, Rseaux de Neurones, etc.) taient dj connues avant mme leur mise en forme algorithmique. Les premiers algorithmes de classication automatique prennent forme vers 1955 [88] et ne cessent de samliorer au courant des annes 1960 [100]. Cest cette poque que la statistique textuelle prend ses lettres de noblesse dope par linformatique lui permettant de valider et dappliquer les mthodes [100]. Lobjectif de la classication documentaire est dattribuer un document une ou plusieurs classes parmi un ensemble prdni. Cette problmatique a par ailleurs t rencontre rcemment dans de nouvelles applications dans des domaines tels que le ltrage sur Internet, la veille technologique, etc. Aujourdhui, cette problmatique utilise largement les mthodes et techniques issues de lapprentissage automatique et plusieurs algorithmes dapprentissage supervis lui ont t appliqus comme les k-plus proches voisins, la nave Bayes, les arbres de dcision, les machines vecteurs de support, les rseaux de neurones, etc [30].

3.2

Notion de classe

Traditionnellement la notion de classe dans la classication documentaire a souvent t synonyme de thme, on parle alors de classication thmatique. La tche revient partitionner un ensemble de documents autour de thmatiques que lon dsigne communment par classes. Dans ce cas, il sagit par exemple, de savoir si un document concerne le thme botanique, le thme philosophie ou bien le thme physique. Aujourdhui la tche de classication a volu en mme temps que les besoins. Cette volution a engendr de nouvelles problmatiques pour lesquelles les classes ne correspondent plus ncessairement des thmatiques. A ce titre, la tche de ltrage (text ltering) propose par la campagne TREC (Text Retrieval Conference) permet de bien comprendre la problmatique de clas41

Chapitre 3. Classsication sication [85]. Un systme de ltrage est dni par exemple comme tant un processus qui permet dextraire partir dun ot dinformations (News, emails, actualits journalires), celles qui sont susceptibles dintresser un ou plusieurs utilisateurs ayant des besoins en information stables [93]. TREC-4 propose dvaluer un ensemble de classieurs binaires indiquant si un nouveau document qui se prsente est accept ou pas. On cite ci-aprs quelques exemples concrets de classication binaire [58]. Un logiciel qui dtecte si un message est un Spam ou non. Un systme qui slectionne des informations pertinentes dans des ux de dpches les envoie dirents organismes concerns. Un systme dagent sintresse aux ux de type Newsgroup et avertit un utilisateur ds quune nouvelle peut potentiellement lintresser [85]. Dans de tels systmes une classe pertinente est assimile un besoin en information qui pourrait intresser un utilisateur particulier ou une entreprise. Dautres problmatiques mergentes telles que la rpartition automatique de courriers de clients la personne comptente dans une entreprise ou bien le tri de courriers lectroniques dans direntes botes aux lettres personnelles ne peuvent tre qualies de problmatiques thmatiques. Si lon dsigne chaque classe par une tiquette associe des documents. Le principe du systme de classication est simple. En eet, si lon suppose que lutilisateur connat eectivement la smantique vhicule par une tiquette, ce nest priori pas le cas du systme proprement parler. Par consquent, le systme identie et classe de manire automatique les documents en se basant uniquement sur leurs labels sans toutefois connatre quelle est leur signication. Lutilisateur par contre, lui qui est cens (re)connatre priori la signication des tiquettes, sera en mesure de slectionner directement les documents qui lintressent via ces tiquettes. La FIGURE 3.1 prsente un exemple o lon imagine un systme ctif de classication de courriers lectroniques bas sur la notion de classes tiquetes [30]. Nous remarquons que les labels des classes possdent eectivement des smantiques de direntes natures (messages dun certain type, messages manant dune certaine source, thme, etc.) que lutilisateur peut facilement interprter. Ce systme organise des emails dans des boites aux lettres qui correspondent chacune une classe du problme de classication.

Figure 3.1 Exemple de systme de classication demails [30] 42

3.3. Dnition formelle de la classication

3.3

Dnition formelle de la classication

Soient C = {c1 , c2 , ..., cn } un ensemble de classes et D = {d1 , d2 , ..., dm } un ensemble de documents classer. On dira quun systme de classication attribue automatiquement chaque document un ensemble de classes : 0, 1 ou plusieurs. Lorsquun document di appartient une classe quelconque cj , on dira que le document di est pertinent pour la classe cj . Plusieurs formalisations du problme de classication ont t proposes dans la littrature par dirents auteurs. On cite titre indicatif la formalisation de Sebastiani [86] et reprise par Yang [113] qui semble trs pratique. Pour cette formalisation on dnit deux fonctions [30] : Une fonction de dcision qui consiste attribuer chaque document un ensemble de classes Une fonction cible indiquant la vritable appartenance dun document un ensemble de classes. La fonction de dcision permet destimer la fonction cible. Plus cette estimation est pertinente (correcte), meilleur est le systme de classication. Ces deux fonctions associent chaque couple (di , cj ) D C une valeur boolenne indiquant si le document di ou / cj . La fonction de dcisison : D C est telle que : (di , cj ) = vrai f aux si di est attribu la classe cj sinon

La fonction cible : D C est telle que : (di , cj ) = vrai f aux si di appartient la classe cj sinon

Habituellement avec les systmes de classication bass sur les mthodes dapprentissage, on value la fonction de dcision en utilisant un corpus dentranement. Un corpus dentrainement est une collection dobjets rpartis en classes dont on connait priori les noms (tiquettes) et le nombre. Un modle dapprentissage est caractris par trois phases principales dont : Lapprentissage (phase dinduction) qui consiste en llaboration du modle sur un corpus dapprentissage dont on connat la classication. Cela correspond la fonction cible (training data). Le test et validation du modle sur un nouvel chantillon test dont on connat aussi la classication pour choisir le meilleur modle (test data). lapplication du classieur (phase de dduction) aux documents classer. Application de la fonction de dcision par estimation de la fonction cible (application data). 43

Chapitre 3. Classsication

3.4

Le ranking

Contrairement la classication dnie dans la section prcdente, qui met une dcision dure sur lappartenance ou non dun objet une classe, le ranking (classement) ordonne (ou trie) ces objets par ordre de leur pertinence pour une classe donne [30]. On peut aussi dire que le ranking permet dordonner les classes par ordre de leur pertinence pour un objet donn. En dautres termes, la tche de ranking se base sur le calcul de la valeur dune fonction de score dnie par : Score : O C [0,1] La valeur de Score(o, c) appartenant lintervalle [0,1] reprsente la pertinence de lobjet o pour la classe c. Voici deux exemples typiques dapplication du ranking [30] : Le ltrage de documents en xant un seuil de tolrance par rapport au score de ranking. Le classement (ranking) de pages Web par rapport une thmatique xe par lutilisateur. Ainsi, la fonction Score(o, c) nous informe sur le degr de pertinence de lobjet o pour la classe c. Plus ce degr est proche de 1, trs pertinent est lobjet pour cette classe. Le calcul de la fonction de score permet alors de classer les objets par ordre de pertinence an de savoir si un objet est plus pertinent ou moins pertinent quun autre pour une classe donne. Une bonne partie des systmes probabilistes utilisent des algorithmes de classication automatique base sur le calcul dune fonction de score comme celle quon vient de dnir ci dessus. Par exemple pour chaque document et chaque classe, on calcule la probabilit P (d|c) que le document d soit pertinent pour la classe c. Le principe de ranking (classement) par probabilit [83] snonce ainsi : Eectuer un ranking des documents en fonction de leur probabilit posteriori est optimal dans le sens o les documents sont indpendants les uns des autres [85]. Plusieurs systmes de ranking actuels suivent le principe de lindpendance des documents. Par consquent, pour les modles probabilistes la fonction de score est : Score(d, c) = P (c|d) Les mmes systmes, peuvent cependant tre aussi utiliss dans le cadre dune classication binaire (dure). Il sut cet eet, de transformer la fonction de score en une fonction de dcision comme suit : Si reprsente un seuil (ou degr) de pertinence dun document d vis--vis dune classe donne c, la fonction de dcision recherche (d, c) sexprime comme suit [30] : (d, c) = vrai f aux si score(d, c) > sinon

44

3.5. Le clustering

3.5

Le clustering

Le clustering (ou regroupement) est la tche qui sintresse trouver de manire automatique une organisation cohrente un groupe dobjets. Elle correspond la tche de classication non-supervise [30]. La problmatique du clustering a t largement tudie en apprentissage, en reconnaissance des formes et en analyse de documents. Une autre application importante de la tche de clustering est en rapport avec la tche de RD (Recherche Documentaire). Elle consiste crer priori sur un ensemble de documents un ensemble de clusters. Pour une requte donne, le systme de RD va tout dabord chercher le cluster le plus pertinent pour la requte, puis trier les documents par ordre de pertinence dans ce cluster (ranking) [30]. Cette mthode permet de limiter la complexit de la recherche dans les grandes bases de donnes et de renvoyer un sousensemble de documents tous pertinents pour la requte puisque le choix du cluster est valu partir des caractristiques communes des documents qui le composent. Cest une technique qui permet habituellement daugmenter la prcision dun systme de RD. En eet, dune part, elle rduit, de manire plus que signicative, la complexit temporelle de la recherche sur de grandes bases documentaires, dautre part, les documents retourns par le moteur de recherche, en rponse une requte, sont tous pertinents, car ils prsentent logiquement des caractristique similaires, voire identiques pour cette requte (le cluster a t construit sur la base de caractristiques communes aux documents qui sy trouvent). On rencontre deux grandes familles de mthodes de clustering : Les systmes fonds sur un calcul de similarit qui rassemblent un sous-ensemble de documents similaires dans un mme cluster. Cette similarit peut par exemple ne concerner que la structure du document, tout comme elle peut impliquer un mlange de modles (structure + contenu). Les systmes probabilistes fonds sur un mlange de modles (structure+contenu) [30].

3.6

Contextes de classication

Le problme de la classication en gnral est de construire une procdure permettant dassocier une ou plusieurs classes un objet. Les mthodes de classication peuvent tre tout dabord exclusives, cest--dire quun objet nappartient qu une et une seule classe, ou bien non exclusives. Dans ce dernier cas, un objet peut appartenir plusieurs classes simultanment, ventuellement avec des degrs dappartenance. On parle alors de recouvrement (overlapping clustering method). On distingue ensuite deux types de traitements : lapproche supervise et lapproche non supervise (ou clustering). Dans la premire, on connat les classes possibles, et on dispose dun ensemble dobjets dj classs, servant densemble dapprentissage. Le problme est alors dtre en mesure dassocier tout nouvel objet, sa classe la plus approprie, en se servant des exemples dj tiquets. Dans la seconde, par contre (classication non supervise), les classes possibles ne sont pas connues lavance, et les exemples disponibles sont non tiquets. Le but est donc de regrouper dans un mme cluster (ou groupe), les objets considrs comme similaires, 45

Chapitre 3. Classsication pour constituer les classes. La FIGURE 3.2 prsente les dirents types de mthodes, regroups sous forme dune hirarchie par Jain et Dubes dans [45].

Figure 3.2 Dirents types de mthodes de classication Il existe dirents contextes de classication : Classication bi-classe La classication bi-classe est la problmatique pour laquelle le systme de classication rpond la question Le document est-il pertinent ou non pour une classe donne ? . Par exemple, un message est-il un Spam ou non ? Cette problmatique est le contexte de classication que lon dsigne dordinaire sur lInternet par ltrage [30]. Classication multi-classe disjointe (exclusive) La classication multi-classe disjointe correspond au contexte o nous sommes en prsence de plusieurs classes (>1) et pour lequel un document appartient exactement une seule classe. La classication classes disjointes est la problmatique pour laquelle le systme de classication rpond la question A quelle classe (au singulier) appartient tel document ? [30]. Classication multi-classe (non-exclusive) Cest le cas le plus gnral de la classication. Dans cette problmatique le systme de classication associe zro (0), une (1) ou plusieurs (>1) classes un document. Autrement dit, le systme doit rpondre la question Quelles sont les classes (au pluriel) auxquelles appartient le document ? . On est dans un cas de classication non-exclusive. Ce type de classication correspond par exemple la problmatique de classication du corpus Reuters 2 . Dans ce cas, il nest pas dicile de constater quun problme de n classes se rsout comme n problmes biclasses [30]. Cependant, recemment les auteurs dans [92] ont propos une mthode per2. Le corpus Reuters est un corpus clbre de documents. Il a t conu par lagence de presse Reuters an que des systmes soient dvelopps pour la classication automatique de dpches de presse. Il correspond une problmatique de classication en plusieurs classes (un document appartient une ou plusieurs classes)

46

3.7. Paramtres dvaluation des performances dun systme de classication mettant de rsoudre directement un problme multi-classe sans dcomposition pralable en plusieurs problmes bi-classes.

3.7

Paramtres dvaluation des performances dun systme de classication

On ne mesure pas la performance absolue dun systme, dune technique ou dune approche. La mesure de la performance dun systme apparat comme une notion subjective dpendant de lutilisation nale de ce systme. De mme, lvaluation de la performance dun systme de classication nest pas toujours une tche triviale. Pour valuer par exemple la performance dun clustering, dun ranking ou dune classication, mme si dans le fond on cherche juger le systme sur la base des mmes critres, les procds dirent dun systme lautre. La performance de la classication dpend notamment de lecacit de la description de lobjet classer. De plus, si lon veut obtenir un systme dapprentissage, la procdure de classication doit permettre de classer ecacement tout nouvel objet (pouvoir prdictif). Plusieurs critres pour valuer la performance dun SRI, ont t proposs : Facilit dutilisation Cot daccs /stockage Prsentation des rsultats Capacit dun systme slectionner des documents pertinents. Le dernier critre est vraisemblablement le plus dterminant pour juger de la qualit dun systme de classication. Mais, ceci demande selon les contraintes du problme tudi, une certaine rigueur pour rduire dans la mesure du possible, le taux derreurs de classication, une certaine robustesse saccommoder de linformation superue ou du manque dinformation, la possibilit de manipuler diverses informations. Habituellement on fait intervenir conjointement deux mesures dnomms rappel et prcision pour mesurer les performances des SRI ou des systmes de classication. Informellement le rappel est dni par le nombre de documents pertinents au regard du nombre de documents pertinents retourns par le systme. Cela signie que lorsque lutilisateur interroge la base documentaire il souhaite voir retourns tous les documents susceptibles de rpondre son besoin en information. Si cette adquation entre le questionnement de lutilisateur et le nombre de documents prsents est importante alors le taux de rappel est lev. A linverse, si le systme possde de nombreux documents intressants mais que ceux-ci napparaissent pas, on parle alors de silence. Le rappel soppose au silence. La prcision, quant elle, reprsente le nombre de documents pertinents par rapport au nombre total de documents retourns par le systme. Le principe est que lorsquun utilisateur interroge une base documentaire, il souhaite que les documents retourns en rponse son interrogation correspondent son attente. Tous les documents retourns 47

Chapitre 3. Classsication superus ou non pertinents, constituent du bruit. La prcision soppose ce bruit documentaire. Si elle est leve, cela signie que peu de documents inutiles sont proposs par le systme et que, par consquent, ce dernier peut tre considr comme prcis. En bref, on dnit dans un systme de classication : Le rappel [121], comme tant la proportion de documents pertinents correctement classs. la prcision [121] correspond la capacit dun systme de classication ne pas juger comme pertinent, un document qui ne lest pas. Formellement, si Xd est le nombre de documents bien classs, Nd le nombre de documents appartenant la classe c, et Nc le nombre de documents attribus la classe c, alors les mesures du rappel R et de la prcision P sont exprims respectivement comme suit : R= P = Xd Nd Xd Nc

La prcision mesure indpendamment du rappel et inversement, est peu signicative. Il va donc falloir employer conjointement ces deux mtriques an de pouvoir valuer signicativement la performance dun systme. Il existe en ce sens des mesures alternatives combinant ces deux mtriques. Une mesure qui combine la prcision et le rappel est leur pondration, nomme F-mesure ou F introduite par [101] est donne par la formule suivante : ( 2 + 1)P R F = 2P + R On voit trs bien daprs cette expression quil est possible, grce au paramtre, daccorder un poids plus ou moins lev la prcision du classieur. On xe couramment la valeur de 1, ce qui donne : 2P R F1 = P +R o la prcision et le rappel sont pondrs de manire quitable.

3.8

valuation dun classieur bi-classe

Notre problme consiste valuer un classieur binaire qui nous renseigne si un document d est pertinent ou non pour une classe donne c. Nous nous plaons alors dans le contexte simple de la problmatique de ltrage o c reprsente une classe unique, celle des documents pertinents, et c celle des documents non pertinents [30]. Nous pouvons en fait, appliquer aussi ce principe en ce qui concerne un systme de classication multiclasse ; il sut tout simplement de considrer quun classieur multi-classe correspond un ensemble de classieurs bi-classes, cest--dire quil faut juste combiner les mesures employes avec les dirents classieurs bi-classes.

48

3.8. valuation dun classieur bi-classe Pour tester lecacit du classieur, on se base sur un corpus tiquet de documents, cest--dire que lon connait priori quelle catgorie appartient un document, pertinent ou non pertinent. Pour ce faire, on construit une matrice de contingence comme celle de la TABLE 3.1 o sont rpertories les informations ncessaires au calcul des paramtres dvaluation des performances du classieur. Cette matrice consiste en un tableau dont les cases sont des entiers dnis dans un mme systme de mesure et dunit homogne [30].
hhh hh

Classe trouve hh hhhh hhh Classe relle h h

hhh

Pertinent (d, C ) = vrai VP FP

Non pertinent (d, C ) = f aux FN VN

Pertinent (d, C ) = vrai Non pertinent (d, C ) = f aux

Table 3.1 Matrice de contingence [30] En fait, ces 4 informations sont capitales et sont interprtes comme suit : V P : les vrais documents pertinents, cest--dire ceux qui sont pertinents et considrs par le classieur comme bien classs, on les appelle les vrais positifs . V N : les vrais documents non pertinents, cest--dire ceux qui sont non-pertinents et considrs par le classieur comme bien classs, on les appelle les vrais ngatifs . F P : les faux documents pertinents, cest--dire ceux qui sont non pertinents et mal classs par le classieur, on les nomme les faux positifs ; F N : les faux documents non pertinents, cest--dire ceux qui sont pertinents et mal classs par le classieur, nomms faux ngatifs . Pour le calcul du rappel R et de la prcision P , il sut dinfrer les probabilits p(|) et p(|), dun document d par rapport la classe c. A cet eet, on utilise la fonction cible et la fonction de dcision . Donc, daprs la matrice de contingence et compte tenu de la dnition de la mesure R, on a : R = p(((d, c) = vrai|(d, c)) = vrai) = VP V P + FN

Comme le rappel tant la capacit dun systme slectionner tous les documents pertinents dune collection, alors dans le cas o F N = 0, le rappel est = 1. Cependant, que cette estimation soit proche de 0 ou de 1, le rappel demeure insusant pour valuer lecacit dun systme de classication. Cest pourquoi il va falloir galement calculer la prcision. Alors, compte tenu de la dnition de la mesure de P et des informations recueillies sur la matrice de contingence, on a : P = p(((d, c) = vrai|(d, c)) = vrai) = VP V P + FP

On voit bien que la prcision correspond la proportion de documents rellement pertinents correctement classs.

49

Chapitre 3. Classsication Les points suivants illustrent quatre situations caricaturales de mesures des performances (R, P et F1 ) de classieurs tests sur un corpus de 500 documents [30]. Ce corpus est rparti priori par la fonction cible sur deux classes c (300 documents pertinents) et c (200 documents non pertinents). Si tous les documents sont considrs par le classieur comme tant tous pertinents, cest--dire V P = 300, F P = 200, F N = 0 et V N = 0. Par consquent, R = 100% ; P = 60% et F1 = 75% Si tous les documents sont considrs par le classieur comme tant tous non pertinents, cest--dire V P = 0, F P = 0, F N = 300, V N = 200. Par consquent, R = 0%, P = 0% et F1 = 0%. Si le classieur ne considre pertinents que les documents qui le sont rellement, il sera dsign par classieur parfait , alors V P = 300, F P = 0, F N = 0, V N = 200, et par consquent, R = 100%, P = 100% et F1 = 100%. Si le classieur prend tous les documents qui sont eectivement pertinents pour des non pertinents, et tous les documents non pertinents pour des pertinents, il sera quali de classieur le pire , alors V P = 0, F P = 200, F N = 300, V N = 0, et par consquent, R = 0%, P = 0% et F1 = 0%. Dans la conguration classieur le pire ainsi que celle o tous les documents, quel que soit leur statut, sont non-pertinents pour le classieur, la prcision et le rappel sont nuls (0%). Par consquent, il est inutile dappliquer la formule pour F1 . Mais, on considre que F1 = 0, lorsquon est dans ce cas de gure.

3.9

valuation de classieurs multi-classes

Comme prconis, lvaluation dun classieur multi-classe, revient se placer dans le contexte de plusieurs classieurs bi-classes. La solution consiste donc reconsidrer les mmes mtriques (R, P et F1 ), et les utiliser bon escient, suivant le contexte multiclasse. De nouvelles considrations peuvent alors entrer en jeu. Pour cela, soit C = (c1 , ..., c|C | ), o |C | reprsente le nombre de classes, cest--dire le nombre de classieurs bi-classes. Sachant que tj reprsente le nombre de documents de la classe cj et que, Rj , Pj et F1j sont les mesures de la performance dun classieur j , on peut alors calculer les mesures globales pour le classieur |C | classes connaissant ces mesures. Il sut pour cela de calculer les moyennes de ces mesures. Cependant, en cas dingalit de tailles des classes, ces moyennes risquent dtre incohrentes et ne pas reter la ralit du classieur, notamment en ce qui concerne les classes eectifs levs. Pour contourner cet inconvnient et amliorer les paramtres dvaluation, il convient dintroduire deux nouvelles mesures : la micro_mean et la macro_mean (respectivement la micro-moyenne et la macro-moyenne) [121]. La micro_mean est une moyenne qui prend en compte la taille des classes. La macro_mean est une moyenne qui ignore totalement la taille des classes. Les mesures globales (rappel, prcision et F-mesure) de type micro_mean et macro_mean sont alors explicites comme suit : 50

3.9. valuation de classieurs multi-classes La micro_mean Le rappel (R)

|C |

tj Rj R=
j =1 |C |

tj
j =1

La prcision (P )
|C |

tj Pj P =
j =1 |C |

tj
j =1

La F-mesure (F1 )
|C |

tj F1j F1 =
j =1 |C |

tj
j =1

La macro_mean Le rappel (R)

|C |

Rj R= La prcision (P )
|C | j =1

|C |

Pj P = La F-mesure (F1 )
|C | j =1

|C |

F1j F1 =
j =1

|C |

Tandis que la micro_mean permet destimer la performance du classieur en prsence de classes eectifs levs, la macro_mean elle, par contre, permet destimer cette performance sur des classes eectifs rduits. 51

Chapitre 3. Classsication

3.10

valuation dun systme de clustering

Une bonne mthode de clustering produira des clusters de bonne qualit. Par dnition un cluster est de bonne qualit si : la similarit intra-cluster est trs leve ; la similarit inter-clusters est trs faible. Mesurer la qualit dun systme de clustering nest pas une tche triviale. La manire la plus simple est de faire appel un expert. Cest une mthode excessivement chre qui nest utilise que dans des cas exceptionnels, pour des applications spciques. Dans le cas de la RD, la manire la plus vidente pour valuer la pertinence du clustering, consiste tester la prcision des rponses du systme sans utiliser les clusters puis en utilisant les clusters. Si le systme rpond avec une plus grande prcision avec lutilisation des clusters, le clustering sera jug comme tant de bonne qualit [30]. Au del de la pertinence des rponses retournes, dautres critres comme la vitesse de rponse du systme de RD peuvent tre utiliss. Mais, ce genre de critres est dpendant de la tche xe [30]. En revanche, il existe un autre type dvaluation indpendant de la tche. On peut citer la mesure de similarit intra-cluster. Cest un paramtre qui permet de mesurer lhomognit dun cluster. Plus ce paramtre est lev, meilleure est la qualit du cluster [35]. Pour mesurer la qualit dun clustering indpendamment dune tche spcique, on peut se baser par exemple sur un corpus tiquet de classes. Lvaluation consiste vrier dans quelle mesure le clustering est capable de retrouver des clusters en accord avec les classes du corpus tiquet qui seront considres comme des classes cibles. Trois nouvelles mtriques ont t introduites pour valuer la qualit dun clustering [121] : la puret, lentropie et linformation mutuelle [30]. Soient C = {c1 , ..., cm } un ensemble de classes et L = {l1 , l2 , ..., ln }, un ensemble de clusters. Les classes des documents sont repres grce la fonction cible (d, c). La fonction de dcision (d, c) permet dassigner un document un cluster. On part de lhypothse qu chaque cluster l est associe la classe majoritaire des documents quil contient. On dsigne cette classe par cl . On dnit alors : La puret du cluster l comme tant la proportion de documents du cluster l qui appartiennent la classe majoritaire cl du cluster, et on lexprime par : nombre de documents du cluster issus de la classe cl puret(l) = nombre de documents du cluster l Si tous les documents dun cluster proviennent de la mme classe, la puret du cluster sera gale 1. Il peut aussi arriver, que lon ait (cas extrme) un cluster par document, la puret est de 100% dans ce cas. Cest pour cela que, pour comparer des systmes de clustering, il faut comparer la mesure de puret nombres de clusters gaux. On calculera comme mesures globales, la puret micro-moyenne et la puret macro-moyenne.

52

3.10. valuation dun systme de clustering Lentropie permet dvaluer la repartition des direntes classes de documents dans un cluster. Elle est exprime par lequation : entropie(l) =
m nl nl 1 i i log log (m) i=1 nl nl

o nl est le nombre de documents dans le cluster l, nl i est le nombre de documents de la classe i dans le cluster l et m est le nombre de classes. Pour obtenir une mesure globale de lentropie sur lensemble des clusters, on fait appel aux mesures micro_mean et macro_mean. De mme, pour comparer des systmes de clustering, il faut eectuer la mesure de lentropie nombres gaux de clusters. Si lentropie est trs faible, le clustering est de bonne qualit. Lentropie idale est gale 0. Linformation mutuelle qui mesure lindpendance entre les clusters et les classes, sexprime comme suit : Ind(C, L) =
cC, lL

p(c, l)log

p(c, l) p(c)p(l)

Plus cette indpendance est faible, forte est linformation mutuelle, bon sera le clustering.

53

Chapitre 4 Classication structurelle de documents XML

4.1 Inroduction

Plusieurs mthodes de traitement des donnes structures ont t dveloppes ces dernires annes dans dirents domaines notamment celui de la bioinformatique o le traitement de squences et darbres a pris une place prpondrante et plus particulirement rcemment dans le domaine de la recherche dinformation et en bases de donnes pour traiter des documents structurs. Ces mthodes font appel direntes techniques comme les distances ddition, les mthodes stochastiques, les sous-ensembles frquents, etc. Elles ont principalement t dveloppes pour le calcul de similarits entre arbres et sous-arbres, pour des tches de classication ou de clustering. Des problmatiques plus complexes, comme lintgration de schmas dans les bases de donnes XML, ont rcemment fait leur apparition [28, 30, 96]. Les premiers travaux concernant la classication des donnes structures ont t dvelopps par la communaut des BD, notamment avec les modles relationnels et entits associations [18,39,49,68]. Une taxonomie de ces travaux peut tre trouve dans [82]. Trs peu de travaux font rfrence lutilisation de techniques dapprentissage et les mthodes utilises sont largement heuristiques. Elles apparaissent rapidement comme des mthodes spciques un certain type de donnes structures et elles ne sont que peu extensibles au traitement des donnes arborescentes textuelles du type des documents XML rencontrs en RIS [30]. Dans la suite de ce chapitre nous faisons un rsum de ltat de lart sur les approches de classication de structures arborescente applicables des documents de type XML. Nous dcrivons ensuite de manire plus dtaille quelques unes parmi ces approches en mettant en valeur leurs principales caractristiques. Mais avant cela, il convient dabord de donner une synthse des mthodes spciques appliques aux documents HTML. 55

Chapitre 4. Classication structurelle de documents XML

4.2

Mthodes spciques

Nous rencontrons dans cette catgorie certaines mthodes de classication spciques qui utilisent explicitement la smantique des tags HTML. Ces mthodes ne sont pas applicables la classication dun nouveau corpus de documents XML pour lequel la smantique des tags nest pas connue du systme. Notons toutefois quelles constituent un ensemble de travaux prcurseurs sur la classication de documents semi-structurs. Ces mthodes sont en gnral bases sur des combinaisons de classieurs. Elles utilisent des critres comme les titres de pages et/ou de sections, les hyperliens, les contenus textuels de la page en cours ou des pages pointes par des hyperliens, etc. [19, 21, 33, 81, 113]. Lide sous-jacente est que la spcication des liens du Web peut contenir de nombreuses informations implicites qui peuvent tre exploites pour ordonner ou ltrer des pages Web. En particulier, un lien dune page Pi vers une autre page Pj peut tre considr comme un choix de la page Pj par lauteur de la page Pi . Ainsi, les liens dont le but principal est de permettre une navigation facile au sein dun site, peuvent aussi tre interprts comme des liens de proximit smantique entre pages Web [19]. Lalgorithme rencontr dans [17] est parmi les tout premiers exploiter les topologies des liens pour aider au ranking (classement) de pages Web. Lusage des liens essaie galement de contrer les problmes lis au vocabulary problem [38], cest--dire contribue aider les utilisateurs formuler leur besoin. Dans ce contexte Brin et Page [75] utilisent la notion de propagation populaire pour dier leur algorithme Page Rank utilis dans le clbre moteur de recherche Google. Lide de la propagation populaire que lon nomme aussi macroscopic distilation dans [19] a initialement t exploite pour lanalyse de citations ou de co-citations dans la littrature scientique [108]. En dautres termes, au lieu de modier directement lindex des documents, la mthode consiste mettre en avant les documents qui jouent un rle primordial dans la toile des liens. Lalgorithme HITS (Hyperlinked Induced Topic Search) [53] amliore la propagation populaire en ajoutant la dimension de pertinence des pages. Ainsi, une page rfrence par un grand nombre de pages pertinentes est une bonne page , ou une page qui rfrence un grand nombre de pages pertinentes est une bonne page . Si lalgorithme Page Rank attribue un score global chaque page, lalgorithme HITS lui, par contre, se base sur une technique dordonnancement dpendante de la requte. De plus, au lieu de donner un simple score, lalgorithme en fournit deux, savoir, les scores d autorit et de rayonnement. Les auteurs dans [78] montrent que lutilisation des liens, dans un modle dargumentation probabiliste (Probabilistic Argumentation System), permet damliorer signicativement le ranking des documents. Parmi les mthodes utilises pour la classication de pages HTML, lapproche [81] propose la combinaison de trois classieurs : le premier sintresse au contenu textuel des pages, le second aux titres des pages et des sections, et le troisime aux hyperliens. Les rsultats obtenus montrent une amlioration nette des performances de la classication.

56

4.3. Approches de classication structurelle de documents XML Lapproche propose dans [113] est quasiment similaire : trois classieurs combinent respectivement linformation textuelle, les tags et les mtadonnes. Dans [21], cest un vecteur qui est propos pour encoder les documents HTML o chaque partie du vecteur reprsente linformation textuelle des direntes entits structurelles, savoir, les titres, les liens, le texte, etc. Les auteurs dans [33] exploitent les tags HTML pour slectionner linformation pertinente dans une page HTML. Enn, dans [19], on propose dutiliser linformation contenue dans des pages lies par des hyperliens la page que lon veut classer. Rcemment, des mthodes similaires de combinaisons de classieurs ont t dveloppes pour classer des emails. L aussi, la smantique des direntes parties du courrier lectronique, comme les titres, les destinataires, etc., qui entrent en jeu, est considre comme xe et connue priori. Linconvnient majeur de ces mthodes, est quelles ne peuvent traiter quun type particulier de documents (email ou HTML par exemple), et quelles ne peuvent donc pas tre adaptes dirents corpus. De plus, ces mthodes sont spciques la tche de classication.

4.3

Approches de classication structurelle de documents XML

Les travaux sur la classication de documents XML existants se distinguent par la manire de reprsenter les documents, mais aussi par les mthodes de classication utilises. Nous nous focalisons ici sur les approches qui reprsentent les documents XML par leurs structures seulement. On distingue dans ce contexte deux principales catgories. Dans la premire, on classe directement des documents XML. Dans la seconde, par contre, au lieu de classer directement des documents XML, on classe leurs DTDs. Nous dcrivons succinctement ci-aprs certaines approches et, ce titre, nous nous intressons celles qui reprsentent structurellement les documents (XML ou DTDs) par des arbres tiquets. Dans le cadre de la premire catgorie, savoir, celle qui classe directement les documents XML, la structure qui est utilise pour classer un document est issue du document lui mme. Cette structure est soit un arbre tiquet correspondant la structure XML originale du document [8, 12, 37, 70, 72, 74, 94], soit un rsum darbre [5, 6, 27]. Lapproche rsum darbre a lavantage de rduire la complexit algorithmique lors du clustering, mais prsente nanmoins (dans certains cas), linconvnient de perturber certaines relations entre lments XML. La FIGURE 4.1 illustre comment dans lapproche [27], un rsum darbre est obtenu par deux transformations : (i) la premire rduit la profondeur de larbre de sorte que les ls de tout nud ayant la mme tiquette que lun de ses anctres deviennent des descendants directs (ls) de cet anctre ; (ii) la seconde, quant elle, limine les rptitions des nuds frres. Par contre, dans [5, 6], un rsum darbre est obtenu par limination seulement des duplications des nuds frres, et trans57

Chapitre 4. Classication structurelle de documents XML

Figure 4.1 Extraction de rsums darbres selon [27] formation dattributs ventuels en descendants immdiats (ls) du nud (balise) auquel ces attributs sont rattachs dans le document XML source. Autrement dit, les relations hirarchiques entre les lments XML sont conserves et sans perte dinformation. Les auteurs [24, 28, 54, 95] proposent un autre modle de reprsentation des structures de documents XML, savoir, leurs approches sont plutt fondes sur la dtection de sousarbres qui apparaissent susamment frquemment dans des collections darbres tiquets XML. Plus prcisment, dans [95], les sous-arbres frquents peuvent tre ordonns ou non, exacts, ou bien conserver uniquement la notion danctre commun, alors que dans les deux autres approches [24, 28], ces sous-arbres doivent tre ordonns, ils peuvent aussi tre exacts. Les sous-arbres en dessous de la che sur la FIGURE 4.2 sont tous frquents selon lapproche [95]. Quant aux deux derniers sous-arbres, ils sont exacts, enracins et ordonns, donc frquents selon [24,28]. Un autre type de proposition [36] consiste linariser la structure arborescente de chaque document XML, savoir, la transformer en une squence numrique et ensuite comparer de telles squences travers lanalyse de leurs frquences.

Figure 4.2 Extraction de sous-arbres frquents selon [95] La classication consiste alors comparer chaque structure extraite avec le reprsentant dun cluster. Ce reprsentant, habituellement appel centrode est larbre le plus pertinent reprsenter structurellement tous les documents XML du cluster [5, 6]. Ce centrode peut changer, cest--dire quil peut tre remplac par un autre arbre plus reprsentatif en fonction de nouveaux documents aects au cluster. Dans [95] un cluster 58

4.3. Approches de classication structurelle de documents XML est caractris par le sous-arbre frquent maximal, cest--dire le sous-arbre frquent qui possde le plus grand nombre de nuds parmi tous les sous-arbres du cluster. Notons quavec la technique des sous-arbres frquents, un document XML peut tre rattach plusieurs clusters. Dans [8,27,37,70,72,74], chaque cluster est reprsent par un groupe de documents XML similairement structurs, tandis quavec les approches [5, 6, 95], un cluster peut avoir seulement un seul reprsentant (centrode ou sous-arbre frquent maximal). Concernant le processus de classication en soi, plusieurs approches ont t proposes. Les auteurs dans [72] proposent un clustering incrmental bas sur la similarit des paths (chemins) prenant en compte dirents critres tels que le nombre de nuds communs entre larbre reprsentant un document XML classer et les arbres du cluster considr ; le nombre de nuds communs des chemins, ainsi que lordre des nuds de larbre du document XML classer. Dans [5, 6], les auteurs eectuent aussi un clustering incrmental, mais il est bas sur la similarit structurelle entre le centrode et la structure du document XML classer. Pour dtecter la similarit structurelle entre des documents XML, les auteurs dans [36] exploitent la Transforme de Fourier Discrte pour comparer de manire eective et eciente des documents cods (cest--dire signaux chantillonns) dans le domaine des frquences. Cette approche se dmarque formellement des approches standards qui sont pour la majorit bases sur des algorithmes de matching de graphes (ou darbres) et permet, entre autre, une rduction signicative en termes de temps de calcul. En eet, si N est le nombre maximum de tags dans deux documents XML, la complexit temporelle de leur matching est O(N logN ), alors quelle est de lordre O(N 2 ) avec certaines approches, comme lalgorithme de Chawathe [20]. Dans [8, 24, 27, 37, 74], la similarit entre deux arbres est base sur la distance ddition. La distance ddition mesure le nombre doprations lmentaires 3 ncessaires, pour transformer un arbre en un autre. La plupart des algorithmes de calcul de la distance ddition sappuient sur la technique de la programmation dynamique [20, 22, 87, 91, 105, 120]. Notons quil peut exister plusieurs squences doprations ddition pour transformer un arbre en un autre. Par consquent, le cot des oprations de chaque squence est considr, et celle ayant donn le plus faible cot, dnit alors la distance ddition dans chaque comparaison de deux arbres [74]. La distance ddition permet ainsi deectuer un clustering darbres en utilisant une technique classique de classication hirarchique ascendante 4 [24, 27, 37, 74]. Dans les approches de clustering bases sur les arbres frquents, les auteurs [95] ont dvelopp un algorithme 5 permettant de dcouvrir le sous-arbre frquent maximal dans un cluster, cest--dire celui qui a le plus grand nombre de nuds de tous les sous-arbres du clusters. De mme, les auteurs dans [28] ont galement dvelopp leur algorithme 6 trs proche des algorithmes FREQT et TREEMINER proposs respectivement dans [10] et [119]. Notons quavec ce type dapproche, un arbre XML peut tre partag entre plusieurs clusters, cest--dire quil peut contenir plusieurs sous-arbres frquents apparaissant respectivement dans plusieurs clusters. Nous avons donc faire un clustering multicluster non-exclusif (recouvrement).
3. 4. 5. 6. Les oprations lmentaires sont les insertions, remplacements et suppressions de nuds Appele aussi mthode de classication agglomerative Algorithme TreeFinder RSF : Recherche de sous-structures frquentes

59

Chapitre 4. Classication structurelle de documents XML

Concernant la seconde catgorie, savoir, la classication de documents XML via leurs DTDs, nous relatons brivement ci-aprs quelques unes des approches parmi les plus connues. Rappelons ce titre quune DTD est considre comme une grammaire contexte libre qui engendre un nombre potentiellement inni de documents XML. De ce fait, au lieu de classer directement des documents XML, lapproche prconise dtablir la classication de leurs DTDs quand celles-ci sont connues. Ainsi, chaque cluster rsultant de cette classication devient le reprsentant dun ensemble de documents XML structurellement similaires. Lavantage est quil est possible dintgrer plus rapidement un nombre considrable de documents XML ensemble. Linconvnient, est que les nuds des arbres DTDs dnotent souvent des expressions rgulires dont le traitement nest pas toujours trivial et engendre de surcroit (dans certains cas) une perte dinformation [57]. Dans [57] les auteurs proposent un modle de clustering nomm Xclust o chaque DTD est reprsente par un arbre. La similarit entre deux nuds de deux arbres est calcule en exploitant plusieurs niveaux : la similarit ontologique des nuds en utilisant un dictionnaire, la similarit de leurs ensembles de descendants immdiats, la similarit de leurs anctres et, enn, la similarit des ensembles de feuilles des sous-arbres dont ils sont respectivement les racines. Les auteurs de SPL (Schema Probabilistic Learning) [90] proposent plutt un mcanisme qui identie syntaxiquement la similarit entre DTDs en adoptant une stratgie de classication ascendante. Comparativement XClust, SPL exploite uniquement les contextes des descendants immdiats. Les auteurs de Cupid [62] ont dvelopp un algorithme qui sappuie sur un schma gnrique de matching de DTDs ; le but du matching est de cibler un schma mdian vers lequel doivent converger toutes les DTDs ayant des structures similaires. Tout comme XClust, pour calculer la similarit des arbres DTDs, lapproche Cupid sappuie sur un dictionnaire, mais elle exploite uniquement les contextes feuilles. Enn, LSD (Learning Schema Document) [31], est une approche base sur lapprentissage et linfrence, combins avec une instance de DTD. Cest une classication supervise, cest--dire les classes sont identies lavance. Il existe de nombreuses autres mthodes comme [30, 32, 41, 50, 55, 71, 98, 99, 102, 110], ddies pour classer ou clustriser des documents XML conjointement sur la base de la structure et du contenu. Ces mthodes sont en fait exibles puisquelles peuvent tre aisment adaptes la structure toute seule. A titre dexemple, dans [30,110], les auteurs proposent un modle stochastique bas sur des rseaux Bayesiens [76], dcrivant les dirents types de relations entre lments XML. Il a t prouv exprimentalement que ce modle sadapte eectivement la structure seule et permet, entre autres, dinfrer les dirents types de relations structurelles entre les lments dans un document XML. De mme, lapproche [102] qui est fonde sur la notion de chemins et/ou de sous-chemins, utilisant la structure et le contenu, peut galement fonctionner en mode structure seule. Lapproche 60

4.4. Approche des arbres frquents prconise que les documents XML soient reprsents par un ensemble de leurs chemins et sous-chemins tels que ces derniers soient classes par longueur. Cette reprsentation permet ainsi daplatir ces documents, tout en conservant leurs structures. La motivation de prendre en compte les sous-chemins, et pas seulement les chemins, est que certains documents XML se ressemblent, mais cette ressemblance apparat dirents niveaux. Par exemple, tant donns les chemins p1 = sec.paragraph et p2 = sec.sec.paragraph ; la ressemblance de ces deux chemins apparat partir de dirents niveaux, cest--dire du premier niveau pour p1 (la premire section sec de p1 ), et du second niveau de p2 (la deuxime section sec de p2 ). Les auteurs dans [118] utilisent plutt une approche base sur la notion de bitmap. Une sorte de matrice binaire 2 dimensions nomme index bitmap permettant de reprsenter une collection de documents XML. Chaque document XML est dni par une squence de chemins partant de la racine aux lments terminaux (feuilles). Le principe de lindex bitmap est que si un chemin pi appartient un document dj alors (pi , dj ) = 1, sinon (pi , dj ) = 0. Une fois lindex bitmap construit, un algorithme permettant de calculer la similarit, lui est appliqu pour clustriser les documents XML quil reprsente. A lissue de cet aperu succinct sur les approches concernant la classication structurelle de documents XML, nous allons maintenant dcrire de manire dtaille quelques unes de ces approches. Nous avons choisi particulirement celles qui se distinguent par leur manire de reprsenter les documents ainsi que par les mthodes de classication utilises.

4.4

Approche des arbres frquents

Cette approche a t utilise dans [10, 28, 106, 119] en RI avec XML et mme en Data Mining [2]. A lorigine les motivations pour ces travaux proviennent des bases de donnes pour la fouille de donnes (Data Mining) [2] et du dveloppement de schmas mdiateurs pour linterrogation de donnes XML. Lutilisation darbres frquents a t rcemment propose par certains auteurs [28,95], pour faire du clustering darbres tiquets XML. Le mme principe est appliqu, savoir que, toutes ces mthodes sont bases sur la recherche de sous-schmas frquents. Nous allons nous focaliser sur ce principe commun aux direntes mthodes. Nous nous appuyons sur lapproche [95] pour comprendre le principe des arbres frquents. La mthode des arbres frquents a t propose dans le but de dcouvrir, dans un corpus darbres, un ensemble de sous-arbres frquents qui permettront par la suite de caractriser un document an de lui associer le cluster appropri. La FIGURE 4.3 donne des exemples darbres XML et les sous-arbres frquents extraits par un tel systme [30]. Les sous-arbres frquents peuvent tre des arbres ordonns ou non ; ils peuvent galement tre des arbres exacts ou bien conserver uniquement la notion danctre [30]. En bref, ils peuvent apparaitre dans une fort darbres selon une inclusion faible non exacte et non ordonne. 61

Chapitre 4. Classication structurelle de documents XML

Comme illustr par la FIGURE 4.3, larbre en dessous du trait horizontal est un arbre frquent commun aux deux arbres du haut (au dessus du trait horizontal). Larbre frquent (en dessous de la che) nest pas un sous-arbre exact ni ordonn. Il conserve cependant la notion danctre commun (dans les deux arbres au dessus de la che, voiture doccasion est lanctre des nuds modle , prix et anne ).

Figure 4.3 Approche de dtection de sous-arbres frquents [30] Une fois les arbres frquents calculs, les documents sont regroups dans un mme cluster sils partagent le mme arbre frquent. Notons quun arbre XML peut tre associ plusieurs clusters, cest--dire quun document XML peut partager plusieurs sous-arbres frquents avec dautres documents XML. Ensuite, pour chaque cluster il sagit de calculer larbre maximal commun aux documents du cluster. Cet arbre est alors larbre reprsentatif du cluster. La dcouverte de larbre maximal commun est luvre de lalgorithme TreeFinder [30]. Lalgorithme TreeFinder permet : deectuer un clustering darbres, bas sur la dtection des arbres frquents. de calculer galement un reprsentant pour chaque cluster. Ce reprsentant peut ventuellement servir dinterface avec un utilisateur pour reprsenter le cluster ou bien pour lui permettre dinterroger les documents qui sy trouvent. Lalgorithme comprend deux tapes : La premire consiste regrouper les arbres qui ont en commun un nombre susant de paires lies par la relation anctre. La deuxime construit pour chaque cluster trouv ltape prcdente, larbre maximal commun tous les lments du cluster. 62

4.5. Approche des rsums darbres

En somme, lapproche se distingue par les caractres suivants : Un seul reprsentant pour chaque cluster ; Ce reprsentant est le sous-arbre frquent maximal du cluster, cest--dire celui qui a le plus grand nombre de nuds dans le cluster ; Un cluster contient plusieurs sous-arbres frquents, mais un arbre XML peut tre assign plusieurs clusters, cest--dire quun document XML peut partager plusieurs sous-arbres frquents avec dautres documents XML ; nous avons alors un clustering multi-cluster non-exclusif ; Un sous-arbre frquent peut apparaitre dans une fort darbres selon une inclusion faible non-exacte et non-ordonne. Autrement dit, en permettant une plus grande exibilit dans linclusion, permet de traiter des documents XML htrognes. A contrario, les approches [10,28] sont bases sur linclusion stricte, exacte et ordonne travaillant sous les contraintes de DTDs ou de schmas XML ne sintressent quaux documents XML homognes.

4.5

Approche des rsums darbres

Un rsum darbre est une forme abstraite darbre proche dun sous-arbre apparaissant dans un arbre (selon une inclusion comme celle dnie au chapitre 2 en sous-section 2.1), mais comparativement au sous-arbre, un rsum darbre doit : reprsenter la totalit de larbre ; ne pas comporter de redondance (duplications de nuds) inutile. Les exemples de la FIGURE 4.4 et FIGURE 4.5 sont des rsums darbres. Dans le premier [27], on limine les redondances horizontales (duplications des nuds frres) ainsi que les rptitions verticales (en profondeur) ; ceci perturbe invitablement certaines relations de fratrie. Dans le deuxime [5, 6], en revanche, le rsum darbre est obtenu en liminant uniquement les duplications horizontales et en gardant les ventuels attributs en tant que ls des nuds (balises) auxquels ils sont rattachs dans le document XML source. Pour tayer nos propos, la FIGURE 4.6 montre un sous-arbre apparaissant selon une inclusion stricte ordonne et non-exacte o lon peut voir que les duplications sont maintenues ; T6 est inclus dans T2 selon une inclusion stricte ordonne non exacte.

Figure 4.4 Rsums darbres selon lapproche [27]

63

Chapitre 4. Classication structurelle de documents XML

Figure 4.5 Rsums darbres selon lapproche [5]

Figure 4.6 Inclusion stricte ordonne non exacte

Ainsi, nous allons prsenter lapproche [27] qui reprsente un modle de clustering de documents XML sur la base de leur similarit structurelle. Les structures arborescentes associes aux documents XML sont des rsums darbres comme celui de la FIGURE 4.4 (obtenu selon les transformations (i) et (ii)). Clustriser (regrouper) structurellement des documents XML revient donc nalement clustriser leurs rsums darbres. Lappariement de ces arborescences sappuie sur la distance ddition. Rappelons que la distance ddition reprsente le nombre dinsertions, remplacements et suppressions ncessaires pour transformer un arbre en un autre. Un grand nombre dalgorithmes concernant le calcul de cette distance sappuient sur le principe de la programmation dynamique. Notons aussi quil peut exister plusieurs suites doprations ddition pour transformer un arbre en un autre. De ce fait, le cot des oprations de chaque suite est considr, et celle ayant donn le plus faible cot dnit alors la distance ddition. La distance ddition permet ainsi deectuer un clustering darbres en utilisant une technique de classication hirarchique ascendante. Le calcul de la distance ddition est inspir de lalgorithme Chawathe [20]. Ce dernier est connu pour sa rapidit (complexit de lordre O(M N ), M et N tant les nombres de nuds des arbres apparier), relativement aux autres algorithmes de calcul de la distance ddition existants [22,87,91,105,120]. Nous allons prsenter cet algorithme plus loin dans cette section, mais il va falloir auparavant introduire certaines notions pour comprendre facilement le principe de la mthode. 64

4.5. Approche des rsums darbres

4.5.1

Dnitions prliminaires et notions de base

Dnition 4.1 (Scnario ddition) Un scenario ddition est une suite doprations ddition utilises pour transformer un arbre T1 en un arbre T2 . Les oprations fondamentales quon peut utiliser dans un scnario ddition sont linsertion, la suppression et la mise--jour (ou remplacement). Dnition 4.2 (Insertion) Soit p un nud dans un arbre T , et soient T1 ,..., Tk des sous-arbres de p. Soit n un nud / (nappartenant pas ) T , soit l une tiquette et i [1..k + 1]. Lopration nomme ins(n, i, p, l) insre le nud n comme le ieme ls de p. Dans larbre transform, n est un nud feuille dtiquette l. Dnition 4.3 (Suppression) Soit n un nud feuille dans T . Lopration de suppression del(n) entraine llimination du nud n de larbre T . Autrement dit, si n est le ieme ls de p T dont les ls sont c1 , ..., ck , alors dans larbre transform, p a pour ls c1 , ..., ci1 , ci+1 , ..., ck . Dnition 4.4 (Remplacement) Si n est un nud dans T et v est une tiquette alors lopration de remplacement rep(n, v ) produit un arbre T identique T except que dans T , l(n) = v . La FIGURE 4.7 donne un exemple de deux scnarios ddition pour transformer respectivement T1 en T2 et T2 en T1 . La suite del(8), del(9), rep(7, a), del(7) transforme T1 en T2 ; lautre suite ins(7, 2, 2, c), rep(7, c), ins(9, 1, 7, a), (8, 1, 7, d), quant elle, fait le chemin inverse, cest--dire transforme T2 en T1 . Les graphes ddition ont t utiliss par plusieurs algorithmes [67, 69, 111] ecaces pour comparer des squences (arbres, chaines, etc.). En eet, le problme de chercher le cot minimum dun scnario ddition entre deux squences est rduit au problme de trouver le plus court chemin dun bout lautre du graphe ddition. Dnition 4.5 (Graphe ddition) Le graphe ddition de deux squences A=(A [1],..., A[m]) et B= (B [1],..., B[n]) est la grille (n + 1) (m + 1) o : un point (x, y ) correspond intuitivement (A[x], B[y]) pour x [1,m] et y [1,n]. lorigine (0,0) du graphe est le point le plus haut le plus gauche. les artes sont orientes horizontalement droite, verticalement vers le bas, ou diagonalement droite, selon lopration eectuer : suppression, insertion ou remplacement. ces artes ont des poids correspondant aux cots des oprations quelles reprsentent. Le graphe ddition de la FIGURE 4.8 correspond la comparaison des squences (chaines de caractres) A= ababadab et B=acababc. Traverser : une arte horizontale ((x-1, y), (x, y)) dans le graphe ddition correspond lopration de suppression de A[x]. une arte verticale ((x, y-1), (x, y)) consiste insrer B[y]. une arte diagonale ((x-1, y-1), (x, y)) correspond une opration de remplacement.

65

Chapitre 4. Classication structurelle de documents XML

Figure 4.7 Oprations ddition sur deux arbres T1 et T2

66

4.5. Approche des rsums darbres

Figure 4.8 Graphe ddition pour comparer les squences A et B Le chemin mis en vidence dans la FIGURE 4.8 correspond au scnario ddition suivant : del( A[2]), ins(B[2]), del(A[6]), ins(B[6]), del(A[7]), del(A[8]), ins(B[7]), et il est facile de verier quen appliquant ce scnario sur A, on obtient eectivement B.

Figure 4.9 Graphe ddition pour comparer les arbres A et B Le chemin indiqu en utilisant des lignes en gras dans la FIGURE 4.9 correspond au scnario ddition suivant : rep(2, c), rep(5, b), del(6), del(7), del(8), del(9), del(11), ins(n1 , 1, 10, b), ins(n2 , 3, 1, a), ins(n3 , 1, n2 , b), ins(n4 , 2, n2 , c). Les identiants n1 , n2 , n3 et n4 sont utiliss pour les nuds nouvellement insrs. A lissue de cet aperu succinct sur le principe de la mthode de calcul de la distance ddition, il convient maintenant de prsenter lalgorithme permettant de mettre en uvre 67

Chapitre 4. Classication structurelle de documents XML ce calcul.

4.5.2

Calcul de la distance ddition

Approche de Chawathe [20] Entre : Soient A et B deux matrices reprsentant deux arbres tels que A[i].l et A[i].d dnotent respectivement le niveau et la profondeur du ieme nud (en pr ordre) de A (il en est de mme pour B). Le nombre dlments dans A et B sont M et N respectivement. Sortie : La matrice distance D o D [i, j] est gale la longueur du plus court chemin, de lorigine (0, 0) au point (i, j) dans le graphe ddition de A et B. Mthode : D est initialise lorigine (0, 0), suivie par le calcul des distances le long du bord suprieur gauche de la matrice. Outre les oprations de remplacement, dinsertion et de suppression, les fonctions cu, cd et ci permettent galement de calculer les cots respectivement de chacune de ces oprations. Ainsi, si on suppose que cu, cd et ci sexcutent en temps constants , et respectivement, le temps dexcution de lalgorithme est proportionnel 1 + M + N + ( + + )M N ou O(M N ). Un pseudo-code de lalgorithme est donn dans la FIGURE 4.10.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:

D[0,0] 0 for i 1 to M do D[i, 0] D[i-1, 0] + cd (A[i]) end for for j 1 to N do D[0, j] D[0, j-1]+ ci (B[j]) end for for i 1 to M do for j 1 to N do m1 ; m2 ; m3 if A[i].d = B[j].d then m1 D[i-1, j-1]+ cu(A[i], B[j]) end if if (j=N)or(B[j+1].dA[i].d) then m2 D[i-1, j]+ cd(A[i]) end if if (i=M)or(A[i+1].d B[j].d) then m3 D[i, j-1]+ ci(B[j]) end if end for D[i, j] min(m1 , m2 , m3 ) end for return D[i,j] Figure 4.10 Calcul de la distance ddition (version Chawathe) [20]

68

4.5. Approche des rsums darbres Approche de Dalamagas [27]

Comparativement [20] qui est une approche plus gnrale, lapproche [27] suggre que les oprations dinsertion et de suppression nauront lieu que sur les nuds feuilles ; dailleurs supprimer ou insrer un nud interne et dplacer ses descendants, modie de fait la structure logique du document XML source. Cependant, lopration de remplacement dun nud, quel quil soit, ne pose particulirement aucun problme, et peut tre eectue en cas de ncessit. Sur la FIGURE 4.1 (prsente en dbut de section), llimination de la duplication verticale du nud A peut tre vue un peu comme la suppression dun nud interne. Autrement dit, cela suppose de dplacer galement ses ls vers le haut, en vertu de la transformation verticale, note (i) sur la FIGURE 4.1. On va maintenant dnir une mtrique pour la distance an dvaluer la similarit entre arbres tiquets et ordonns reprsentant structurellement des documents XML. Cette distance peut tre calcule laide dalgorithmes ddition darbres qui dterminent les direntes oprations pour transformer un arbre en un autre (comme celui prsent prcdemment par la FIGURE 4.10).

Dnition 4.6 (Distance structurelle) Soient T1 et T2 reprsentant deux documents XML, D(T1 , T2 ) leur distance ddition, cest--dire le nombre doprations ncessaires pour passer de T1 T2 , et D (T1 , T2 ) reprsente le cot ncessaire pour supprimer tous les nuds de T1 et insrer tous les nuds de T2 . La distance structurelle entre T1 et T2 est dnie par lquation suivante :

S (T1 , T2 ) =

D(T1 , T2 ) D (T1 , T2 )

S (T1 , T2 ) est faible (leve) quand les arbres ont des structures similaires (direntes) et un pourcentage lev (faible) de nuds en commun (0 (1) est la valeur minimale (maximale)). Dans lexemple illustr par la FIGURE 4.11, D (T1 , T2 ) = 12, puisque 5 nuds doivent tre supprims de T1 et 7 nuds doivent tre insrs partir de T2 , 5 donc S (T1 , T2 ) = 12 = 0.4166, puisque la distance des arbres est 5 (nombre doprations ddition), et le total des oprations ddition est gale 12. 69

Chapitre 4. Classication structurelle de documents XML

Figure 4.11 Squence doprations ddition pour transformer T1 en T2 Etant donn deux arbres T1 et T2 de racines s et t respectivement, lalgorithme de la FIGURE 4.12 calcule leur distance ddition selon lapproche [27]. CalcDist(Arbre s, Arbre t) D[0,0] UpdateCost(LabelOf(s), LabelOf(t)) for i 1 to NumOfChildren(s) do D[i, 0] D[i-1, 0]+ NumOfNodes(si ) end for for j 1 to NumOfChildren(t) do D[0, j] D[0, j-1]+ NumOfNodes(tj ) end for for i 1 to NumOfChildren(s) do for j 1 to NumOfChildren(t) do D[i, j] min(D[i-1, j-1]+CalcDist(si ,tj ), D[i, j-1]+NumOfNodes(tj ), D[i-1, j]+NumOfNodes(si )) 12: end for 13: end for 14: return D[NumOfChildren(s), NumOfChildren(t)] Figure 4.12 Calcul de la distance ddition (version Dalamagas) [27] o : si est le ieme ls de s et tj est le j eme ls de t ; NumOfChildren(s) renvoie le nombre de ls de s, (il en est de mme pour t) ; NumOfNodes(s) renvoie le nombre de nuds du sous-arbre de racine s (y compris s lui-mme) ; LabelOf(s) renvoie ltiquette du nud s ; UpdateCost(LabelOf(s), LabelOf(t)) renvoie le cot cr (le cot du remplacement) = 1 si LabelOf(s)= LabelOf(t), 0 dans le cas contraire.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:

70

4.6. Approche des DTDs : cas Xclust Cette approche utilise un algorithme de programmation dynamique quivalent celui de [20] (Chawathe) en termes doprations ddition utilises. Leur dirence rside fondamentalement dans la manire dexcuter ces oprations, cest--dire dans la manire dont le cot (complexit) de ces oprations est calcul. Dans lalgorithme [20], ce cot est de lordre O(M N ) puisquil est calcul tout simplement lintrieur de la boucle imbrique M N , comme on peut le voir dans lalgorithme de la FIGURE 4.10. Dans [27] (Dalamagas), par contre, ce cot est calcul lextrieur de cette boucle, comme on peut le voir galement dans lalgorithme de la FIGURE 4.12. En somme, comme on a pu le constater, les deux algorithmes sappuient sur le principe de la programmation dynamique. Dans un cas comme dans lautre, dans le fond les deux algorithmes se rejoignent (les arbres apparier sont parcourus ou reprsents sous leur forme prxe et on cherche calculer leur distance ddition). Lapproche [20] (Chawathe) reprsente les arbres par des vecteurs, et est assez intressante dans la mesure o elle prsente une complexit algorithmique relativement raisonnable de lordre O(M N ) et quelle prend galement en considration les niveaux des nuds, au cours du matching. On peut voir cette caractristique exprime dans lalgorithme de la FIGURE 4.10. Lapproche [27] doit fournir pratiquement un rsultat proche de celui de [20], savoir, O(M N ), mais videmment, aprs la drcursication de lalgorithme de la FIGURE 4.12.

4.6
4.6.1

Approche des DTDs : cas Xclust

Reprsentation des DTDs

Pour reprsenter une DTD, on utilise habituellement un formalisme issu de la thorie des langages. On utilise en loccurrence un modle de grammaire contexte libre comme celui de la FIGURE 4.13.

Figure 4.13 DTD dcrivant des articles Par analogie un lment < ! ELEMENT A ( )> est transposable sous forme de rgle du type A correspondant au modle de production caractrisant une grammaire contexte libre selon la notation conventionnelle. Daprs la FIGURE 4.13, chaque lment est dcrit par . Chaque lment de , except llment racine (qui napparat pas entre parenthses dans une DTD), peut tre sux par certaines contraintes exprimant des cardinalits ou des options. Par exemple : Author 71

Chapitre 4. Classication structurelle de documents XML

Figure 4.14 Reprsentation en arbre de la DTD de la FIGURE 4.13 + signie que Author apparat une ou plusieurs fois ; Title ? indique que llment Title est optionnel, cest--dire quil napparait quune seule fois ou pas du tout ; un lment suivi de loprateur * peut apparatre une ou plusieurs fois, ou aucune fois. Les lments groups en une squence ordonne doivent tre spars par des virgules , comme par exemple (Title, Author +, Section +), tandis que ceux exprimant un choix doivent tre spars par le symbole | comme dans lexpression (Para | (Title ? , Para+) +) *. Parmi les lments de , il y en a qui sont dsigns par des variables (correspondant au vocabulaire non-terminal selon le formalisme des grammaires conventionnelles), comme les lments Title, Para, Section, etc. qui reprsentent les balises dans un document XML, mais il y a aussi, ceux qui sont des constantes (reprsentant le vocabulaire terminal dune grammaire) correspondant au type des contenus (des lments et des attributs) dans les documents XML dcrits par cette DTD. Notons cependant que XClust [57] ne sintresse qu la composante structurelle des DTDs. Lapproche XClust utilise un arbre pour reprsenter une DTD comme celui de la FIGURE 4.14 On peut y rencontrer trois types de nuds : les nuds simples reprsentant les noms des lments de la DTD les nuds annots reprsentant des noms dlments suivis de cardinalits (+, *, ?). les nuds auxiliaires pour les expressions rgulires. Il existe deux catgories de nuds auxiliaires : les nuds OR pour les squences de choix et les nuds AND pour les squences ordonnes, dnots respectivement par les symboles | (trait de Scheer) et , (virgule). Les arbres DTD dans ce cas ne seront pas faciles manier, car il est dicile de dterminer la similarit de deux lments comportant des nuds composites de type AND-OR. Une solution vidente est dclater les arbres ANDOR en fort darbres AND et de calculer ensuite plus facilement la similarit base sur les nuds AND. Mais cela risque dengendrer une prolifration darbres AND. Une autre option serait de remplacer dans les arbres les nuds OR par des nuds AND. Cette solution provoque de facto une perte dinformation [57], mais, il est possible de minimiser cette perte en appliquant les rgles de transformation par ordre de priorit comme illustr par la TABLE 4.1. Les rgles E1 E5 prservent mieux linformation et on leur attribue la priorit haute. 72

4.6. Approche des DTDs : cas Xclust Rgle E1 E2 E3 E4 E5 Transformation (a|b)* (a*,b*) ((a|b)*)+((a|b)+)*(a*,b*) ((a,b)*)+((a,b)+)*(a,b)* ((a|b)*) ?((a|b) ?)*(a*,b*) ((a,b)*) ?((a,b) ?)*(a,b)* ((a|b)+) ?((a|b) ?)+(a*,b*) ((a,b)+) ?((a,b) ?)+(a,b)* ((E)*)* (E)* ((E) ?) ?(E) ? ((E)+)+(E)+ (a|b)(a,b) (a|b)+(a+,b+) (a|b) ?(a,b) ? (a,b)* (a*,b*) (a,b)+(a+,b+) (a,b) ?(a ?,b ?) Priorit haute haute haute haute haute

L6

faible

L7

faible

Table 4.1 Rgles de transformation dun arbre DTD Par exemple ((a,b)*)+ dans la rgle E2 implique quil y a au moins un (a,b)*, ou un ((a,b)*, (a,b)*,...) qui donne nalement (a,b)*, car ((a,b)*)+ (a,b)*, ou ((a,b)*)* (a,b)*. De mme ((a, b)+)* implique zro (cest--dire : chaine vide), ou plusieurs (a,b)+(a,b)*. Les rgles L6 et L7 provoquent une perte dinformation et on leur attribue la priorit basse (faible). La rgle L7 transforme lexpression rgulire (a, b)+ en (a+,b+) qui cause une perte dinformation. Ceci, parce que (a, b)+ implique que la squence ab (le symbole a suivi du symbole b) doit apparatre une ou plusieurs fois, tandis que dans (a+, b+) cette contrainte nest pas impose. En bref, ces rgles vitent davoir une complexit spatiale exponentielle due au split (clatement) des arbres AND-OR en forts darbres AND. En appliquant les rgles de la TABLE 4.1 sur un arbre DTD, tout nud auxiliaire OR se transforme en plusieurs nuds AND quil faudrait concatner ensuite.

4.6.2

Calcul de la similarit

Pour calculer la similarit entre deux DTDs, il est ncessaire de calculer la similarit entre leurs lments respectifs. La mthode propose pour ce calcul, considre les smantiques, les structures et les informations de contexte de ces lments. Dans XClust [57], la similarit de base correspond la similarit des nuds en tant que termes simples laquelle on ajoute les contraintes de cardinalit. Le premier pas pour dterminer la similarit entre les lments de deux DTDs est de mettre en adquation leurs noms pour rsoudre les abrviations, les homonymes, les synonymes, etc. En gnral, pour un domaine donn on utilise un thesaurus [62]. Cependant, pour traiter des acronymes tels que Emp et Employ, on peut utiliser une table spcique. On peut utiliser le WordNet the73

Chapitre 4. Classication structurelle de documents XML saurus, un dictionnaire sur le Net par exemple pour dterminer si les noms des lments sont synonymes. XClust introduit la TABLE 4.2 pour estimer linuence que peuvent avoir les cardinalits sur les nuds. Ainsi, la similarit de base note BasicSim(e1 , e2 ) de deux nuds (e1 , e2 ) est dnie comme lagrgation (la somme pondre) de la similarit ontologique OntologicSim dduite par exemple dun thesaurus et de la similarit cardinale ConstraintSim. BasicSim(e1 , e2 ) = w1 OntologicSim(e1 , e2 ) + w2 ContraintSim(e1 .card, e2 .card) o w1 et w2 sont des poids tels que w1 + w2 = 1 avec w1 0 et w2 0 * + ? Nant * 1 0.9 0.7 0.7 + 0.9 1 0.7 0.7 ? 0.7 0.7 1 0.8 Nant 0.7 0.7 0.8 1 Table 4.2 Table des similarits cardinales Pour obtenir donc la similarit de base BasicSim(e1 , e2 ), deux algorithmes ont t proposs, dont le premier calcule la similarit ontologique OntologicSim des nuds, tandis que le second exploite la similarit cardinale ContraintSim(e1 .card, e2 .card) de ces nuds et complte le calcul sur la base de la formule prcdente. Mais pour calculer la similarit, proprement dite, de deux nuds, la similarit de base ne sut pas, il faut alors introduire un certain contexte. Pour Xclust, le contexte utilis implique les descendants et les anctres dun nud. On parle alors des similarits, respectivement des chemins anctres (Path Context Coecient ) et des descendants (descendants immdiats et feuilles ). La FIGURE 4.15 met en valeur trois contextes introduits par XClust.

Figure 4.15 Contextes utiliss dans XClust [57] La similarit entre deux arbres T1 et T2 sexprime comme suit :
n m

sim(e1i , e2j ) Similarit(T1 , T2 ) = 74

i=1 j =1

M ax(|T1 |, |T2 |)

4.6. Approche des DTDs : cas Xclust o sim(e1i , e2j ) est la similarit des nuds e1i et e2j qui est gale au moins . Le symbole reprsente la valeur minimale du seuil de similarit. Les nuds appartiennent respectivement aux arbres T1 et T2 . |T1 | et |T2 | tant respectivement les tailles (nombres de nuds) des arbres T1 et T2 . Mais le calcul proprement dit, de la similarit de deux nuds e1i et e2j , tel quil est prconis dans lapproche XClust, ncessite dintroduire de nouvelles considrations qui tiennent compte du contexte hirarchique de chaque nud. En eet, pour calculer la similarit de deux nuds donns e1i et e2j , la formule suivante agrge trois types de similarits : sim(e1i , e2j ) = w1 S1 (e1i , e2j ) + w2 S2 (e1i , e2j ) + w3 S3 (e1i , e2j ) o w1 0, w2 0 et w3 0 sont des poids tels que w1 + w2 + w3 = 1. S1 (e1i , e2j ) reprsente la similarit smantique de e1i et e2j . Cette dernire dpend de la similarit ontologique de e1i et e2j (dduite partir dun dictionnaire), et de la similarit de leurs anctres respectifs. La similarit smantique de e1i et e2j est calcule par : S1 (e1i , e2j ) = S0 (e1i , e2j ) P CC (r1 .e1i , r2 .e2j ) S0 (e1i , e2i ) tant la similarit ontologique (dduite dun dictionnaire), des nuds e1i et e2j . Un simple algorithme permet de calculer cette similarit. Si les nuds sont reprsents par le mme terme, alors leur similarit est videmment gale 1 ; sils sont synonymes, elle est xe par exemple 0.8 ou 0.9, sinon elle est forcment gale 0. Dans la TABLE 4.3 est donn un exemple de similarits ontologiques des nuds de deux arbres. Les lignes sont reprsentes par les nuds du premier arbre, les colonnes par ceux du second. Facture Produit Code Qte Prixunit Num Facture 1 0 0 0 0 0 Article 0 0.9 0 0 0 0 Q Pu 0 0 0 0 0 0 0.9 0 0 0.9 0 0 Design 0 0 0 0 0 0

Table 4.3 Matrice de similarit ontologique P CC (r1 .e1i , r2 .e2j ) (Path Context Coecient) reprsente la similarit des chemins r1 .e1i et r2 .e2j allant respectivement des racines r1 et r2 aux nuds e1i et e2j . En fait, cest la similarit des anctres respectivement des nuds e1i et e2j . Et pour calculer sa valeur, la formule suivante est applique :
p q

S0 (n1k , n2l ) P CC (r1 .e1i , r2 .e2j ) =

k=1 l=1

M ax(|r1 .e1i |, |r2 .e2j |)

Les nuds n1k et n2l appartiennent respectivement aux chemins (paths) r1 .e1i et r2 .e2j . 75

Chapitre 4. Classication structurelle de documents XML S2 (e1i , e2j ) correspond la similarit des descendants immdiats respectivement de e1i et e2j .
r s

S0 (p1k , p2l ) M ax(|desc1 |, |desc1 |) Les nuds p1k et p2l appartiennent aux ensembles (desc1 et desc2 ) de ls de e1i et e2j respectivement. La troisime similarit envisage, savoir S3 (e1i , e2j ) correspond la similarit des contextes feuilles.
t u

S2 (e1i , e2j ) =

k=1 l=1

simleaf (q1k , q2l ) M ax(|leave1 |, |leave2 |) simleaf (q1k , q2l ) reprsente la similarit des nuds feuilles q1k et q2l . Les nuds q1k et q2l appartiennent respectivement aux ensembles (leave1 et leave2 ) de feuilles des sous-arbres de racines e1i et e2j . Mais pour calculer la similairit simleaf (q1k , q2l ) proprement dite, on utilise la formule suivante : simleaf (q1k , q2l ) = P CC (e1i .q1k , e2j .q2l ) S0 (q1k , q2l ) Ce calcul implique la similarit ontologique S0 (q1k , q2l ) (dictionnaire), des nuds feuilles q1k et q2l et la similarit P CC (e1i .q1k , e2j .q2l ) des chemins (similarit des anctres), allant de e1i et e2j respectivement q1k et q2l . Une fois toutes les tapes de calcul matrises, les auteurs XClust proposent un algorithme qui cre une matrice de similarit de ces DTDs. Le principe de lalgorithme est simple : il part dun ensemble de DTDs, par exemple D = {DTD1 , DTD2 ,..., DTDn }, puis compare la DTD1 avec les (n 1) DTDs restantes, ensuite, il passe la comparaison de la DTD2 avec les (n 2) DTDs restantes, et ainsi de suite, jusqu terminer le processus de construction (comparaison de la DTDn1 avec la DTDn ), de la matrice de similarit envisage. Ltape suivante consiste utiliser la matrice de similarit calcule prcedemment en appliquant un algorithme classique de classication ascendante qui renouvelle (diminue), chaque tape dintgration, la valeur du seuil de similarit. Le processus de clustering sarrte quand on a un nombre grable de clusters. Comme on peut sen apercevoir lapproche XClust se prsente comme un processus long, onreux et dicile assimiler la fois. Il possde nanmoins certaines qualits comme celle de pouvoir classer indirectement un nombre potentiellement inni de documents XML. Ses principaux dfauts sont : les nuds des arbres DTDs dnotent des expressions rgulires dont le traitement nest pas toujours trivial ; la perte dinformation, due aux transformations des nuds OR en nuds AND ; la prolifration darbres de type AND due lclatement des nuds OR-AND en nuds AND se traduit par des complexits spatiales excessives ; 76 S3 (e1i , e2j ) =
k=1 l=1

4.7. Approche des bitmaps les complexits algorithmiques restent particulirement leves cause de la prise en compte des contextes hirarchiques ascendants (anctres) et descendants (immdiats et notamment feuilles) dans le calcul des similarits ; une grande dicult grer les nuds rcursifs ; la construction de larbre DTD partir de la DTD reste une tche manuelle.

4.7

Approche des bitmaps

Traditionnellement les index bitmaps sont utiliss soit dans des bases de donnes, soit dans des entrepts de donnes (data warehouse), an doptimiser les requtes dinterrogation ou de fouille de donnes. Ce type dindex a par ailleurs t employ dans le cadre du clustering de documents XML [118]. Nous donnons ci-aprs un aperu sur lapproche [118], mais il convient dintroduire paralllement galement les concepts ncessaires pour comprendre la technique du bitmap dans le cadre XML. Dnition 4.7 (epath) Un epath est une squence de nuds imbriqus dont le plus profond est un simple contenu. En dautres termes, il correspond un chemin dun nud terminal (feuille) partir de la racine. Par exemple dans la FIGURE 4.16 section.section.section.gure est un epath.

Figure 4.16 Exemple de document XML Un document XML est dni comme une squence depaths. Une base de donnes XML contient un ensemble de documents XML. On peut ainsi dnir lindex dune base XML en considrant lensemble des documents quelle contient ainsi que leurs dirents epaths. Dnition 4.8 (Index bitmap) Lindex bitmap dune base de donnes XML est une matrice binaire 2 dimensions dont les colonnes sont reprsentes par les epaths, et les lignes par les documents XML quelle contient.

77

Chapitre 4. Classication structurelle de documents XML La FIGURE 4.17 et TABLE 4.4 prsentent respectivement un ensemble de documents XML ainsi que lindex bitmap associ en considrant les epaths : p0 = e0 .e1 , p1 = e0 .e2 .e3 , p2 = e0 .e2 .e4 , p3 = e0 .e5 , p4 = e0 .e2 .e4 .e6 , p5 = e0 .e2 .e4 .e7 , p6 = e0 .e8 , p7 = e0 .e9 .

Figure 4.17 Exemple de documents XML Le principe de construction de lindex bitmap est tel que si un epath pi appartient un document dj , le bit de celui-ci est positionn 1, sinon il sera positionn 0. Autrement dit, (pi , dj ) = 1 si lepath pi apparait dans le document dj , et (pi , dj ) = 0 dans le cas contraire. Les epaths et documents XML prcdents sont reprsents par lindex bitmap de la TABLE 4.4. d1 d2 d3 p0 1 1 1 p1 1 1 1 p2 1 1 1 p3 1 0 1 p4 0 1 0 p5 0 1 0 p6 0 1 0 p7 0 0 1

Table 4.4 Un index bitmap de la FIGURE 4.17

Dnition 4.9 (Taille du bitmap) |bi | dnote la taille du bitmap bi , qui est le nombre de 1 dans le bitmap bi , et [bi ] dnote la cardinalit du bitmap bi , qui est le nombre de 1 et de 0 dans bi . Dnition 4.10 (Distance) La distance entre deux documents di et dj peut tre dnie par lquation dist(di , dj ) = |xOR(di , dj )| ou xOR reprsente loprateur OU exclusif (bit bit) sur les lignes di et dj . Par exemple, la distance entre d1 et d2 sur la FIGURE 4.17 est |xOR(d1 , d2 )| = 4. Les documents di et dj sont identiques si |xOR(di , dj )| = 0. 78

4.7. Approche des bitmaps Dnition 4.11 (Similarit) La similarit structurelle entre deux documents XML (lignes bitmaps), di et dj est dnie par : sim(di , dj ) = 1 dist(di , dj )| M ax([di], [dj ])

Deux documents di et dj sont -similaires si sim(di , dj ) , o 0 1 et est un seuil donn.

4 =1 , tandis que Par exemple, daprs la FIGURE 4.17, la similarit de d1 et d2 est 1- 8 2 1 7 la similarit de d1 et d3 est 1- 8 = 8 . Le document d1 est plus proche de d3 que de d2 en termes de chemins (ou epaths).

Une colonne (epath) de lindex bitmap peut tre dcrite par sa popularit. Un epath est populaire sil est utilis assez frquemment. Dnition 4.12 (Popularit) La popularit dun epath est dnie par : pop(pi ) = |pi | [ pi ]

Un epath est n-populaire si pop(pi ) n, o 0 n 1 pour un seuil de popularit n donn. Un epath pi est m-impopulaire si pop(pi ) m, o 0 m 1. Par exemple, daprs la FIGURE 4.17 p3 est populaire 67% car pop(p3 ) = 0.67, tandis que p4 est populaire 33%. Il est vident que la popularit dun epath change lorsquun nouveau document est ajout ou supprim. Dnition 4.13 (Types depaths) Il existe 3 catgories distinctes depaths : Si pop(pi ) n alors pi est dit populaire ; Si pop(pi ) 1 n alors pi est dit impopulaire f aible ; Si 1-n<pop(pi ) < n alors pi est dit impopulaire f ort. Nous allons dcrire prsent deux caractristiques de lindex bitmap : le rayon et le centre. Le rayon est une variance, tandis que le centre est une moyenne. Dnition 4.14 (Centre ou centrode) Dans un cluster de documents XML, le centre est un vecteur form de bits 1 correspondant toutes les colonnes (epaths) populaires et impopulaires fortes et de bits 0 correspondant aux colonnes impopulaires faibles. Dnition 4.15 (Rayon) Le rayon du cluster de documents XML est dni comme radius(c) = M ax{dist(dc , dj )}, o dc est le centre de lindex bitmap et dj est le vecteur bitmap du j eme document dans le cluster c.

79

Chapitre 4. Classication structurelle de documents XML Un ensemble de documents XML peut tre clustris (partitionn) en un certain nombre de clusters. Le nombre de partitions dpend des caractristiques des documents. Pour simplier, nous considrons seulement les index bitmaps reprsentant les documents et epaths. Soit alors lexemple de lindex bitmap de la TABLE 4.5.

d1 d2 d3 d4 d5

p0 1 1 1 1 1

p1 1 1 1 1 1

p2 1 1 1 1 1

p3 1 1 1 0 1

p4 0 1 0 0 1

p5 0 1 0 0 1

p6 0 0 0 0 1

p7 0 1 0 0 1

p8 1 1 0 1 0

p9 0 0 1 0 0

p10 0 0 1 1 0

p11 0 0 1 1 0

p12 1 0 0 1 0

p13 1 0 1 1 0

p14 1 0 0 1 0

p15 0 1 1 0 0

p16 0 1 0 0 0

p17 0 0 1 0 0

p18 1 0 1 1 0

Table 4.5 Un index bitmap

Les tapes de partitionnement (ou clustering) sont les suivantes : Rarrangement des colonnes et des lignes de lindex bitmap : Identier les colonnes (epaths) populaires en calculant pop(pi ) ; Dcaler toutes les colonnes populaires gauche. Par exemple si on suppose que le seuil de popularit est 0.6, alors les colonnes p0 p3 , p8 , p13 et p18 sont populaires. Les rsultats aprs le dcalage sont illustrs par la TABLE 4.6 ; Identier les lignes (dj ) similaires en calculant sim(di , dj ) pour les bits des colonnes populaires. Ainsi, dans la TABLE 4.6, il y a deux paires de documents similaires (d1 , d4 ) et (d2 , d5 ) ; Sil y a encore des lignes (dj ) clustriser partir du rsultat prcdent, identier les lignes similaires en calculant sim(di , dj ) pour les colonnes de bits impopulaires. Sur le mme exemple d3 est similaire la partition (d1 , d4 ). Par consquent, les deux nouvelles partitions sont (d1 , d3 , d4 ) et (d2 , d5 ) comme montr par la TABLE 4.7. Eliminer les colonnes pi telles que pop(pi ) = 0. A nouveau sur le mme exemple, on obtient le rsultat de la TABLE 4.8. Jusqu prsent, lopration sim(di , dj ) est base sur le calcul par paire. On peut modier cette opration dans une certaine mesure. Au lieu dutiliser deux bitmaps, on peut utiliser les centres des index bitmaps. En bref, il existe trois approches didentication de la similarit : En calculant sim pour des paires de documents la fois. En calculant sim dun bitmap (dj ) avec le centre (dc ) dun index bitmap cible. En calculant le rayon (rj ) dun bitmap (dj ) partir du centre (dc ) dun index bitmap cible. Tous les bitmaps dans un rayon donn sont dans la mme partition (cluster). 80

4.8. Approche des noyaux darbres (tree kernels) p0 p1 p2 p3 p8 p13 p18 p 4 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 p5 0 0 1 1 0 p6 0 0 0 1 0 p7 0 0 1 1 0 p9 0 0 0 0 1 p10 0 1 0 0 1 p11 0 1 0 0 1 p12 1 1 0 0 0 p14 1 1 0 0 0 p15 0 0 1 0 1 p16 0 0 1 0 0 p17 0 0 0 0 1

d1 d4 d2 d5 d3

Table 4.6 Un index bitmap aprs dcalage des colonnes (epaths) populaires gauche p0 p1 p2 p3 p8 p13 p18 p 4 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 0 p0 p1 p2 p3 p8 p13 p18 p
4

d1 d4 d3

p5 0 0 0

p6 0 0 0

p7 0 0 0

p9 0 0 1

p10 0 1 1

p11 0 1 1

p12 1 1 0

p14 1 1 0

p15 0 0 1

p16 0 0 0

p17 0 0 1

d2 1 d5 1

1 1

1 1

1 1

1 0

0 0

0 0

1 1

p5 p6 p7 p9 p10 p11 p12 p14 p15 p16 p17 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0

Table 4.7 Index bitmap partitionn en deux avant llimination des bits 0 p0 p1 p2 p3 p4 p5 p6 p7 p8 p15 p16 d2 1 1 1 1 1 1 0 1 1 1 1 d5 1 1 1 1 1 1 1 1 0 0 0 p0 p1 p2 p3 p8 p9 p10 p11 p12 p13 p14 p15 p17 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 Table 4.8 Index bitmap de la TABLE 4.6 partitionn

d1 d3 d4

p18 1 1 1

4.8

Approche des noyaux darbres (tree kernels)

Avec le dveloppement des modles base de noyaux, un nouveau champ dinvestigation particulirement fertile sest ouvert sur la cration et ltude de noyaux spciques aux structures. Alors que les mthodes plus anciennes de traitement des structures, eectuent une projection explicite des structures dans un espace vectoriel connu, les fonctions noyaux elles, permettent de calculer par un produit scalaire des similarits entre deux structures sans avoir transformer ces structures en vecteurs. Cest un des avantages importants des noyaux par rapport aux mthodes vectorielles classiques [30]. Nous nous limitons ici dcrire que la fonction noyau darbre. Mais pour expliquer le principe, il convient dabord de sappuyer sur le noyau dune chane de caractres (string kernels ). Les string kernels [60, 104] sont des noyaux qui calculent une similarit (un produit scalaire) entre deux chanes de caractres. Ce sont les premiers noyaux dvelopps 81

Chapitre 4. Classication structurelle de documents XML pour le traitement de donnes structures, ici, des squences discrtes. Soit le vocabulaire discret V = {V1 , ..., V|V | }. Une squence x V , V tant lensemble des squences possibles sur le vocabulaire V , sera compose de lensemble de ses lments : x = (x1 , ..., x|x| ) o |x| est le nombre dlments de x [30]. Le noyau p-spectrum kernel, est associ la fonction p de projection dans un espace de grande dimension dnie comme suit : Soit V p lensemble des squences de V de taille p, et u une sous-squence de taille gale p p p, on a : p (x) = {p u (x), u V } tel que : u (x) = le nombre de fois que u apparat dans x. Si lon considre le vocabulaire V = {a, b, c, r, t}, lespace de projection dnie par un 2-spectrum kernel sur ce vocabulaire, sera lespace de toutes les paires construites sur V 2 = {aa, ab, ac, ar, at, ba, bb, bc, br, bt, ca, cb, cc, cr, ct, ra, rb, rc, rr, rt, ta, tb, tc, tr, tt}. Tout mot construit partir de V peut tre reprsent dans cet espace. Les reprsentations des mots bar, bat, car, cat, dans cet espace, sont donnes dans la TABLE 4.9. 2 bar bat car cat ar 1 0 1 0 at 0 1 0 1 ba 1 1 0 0 ca 0 0 1 1

Table 4.9 Noyeau : reprsentation du 2-spectrum Kernel

spectrum sera alors dni comme le produit scalaire dans Le noyau nal spectrum K2 lespace prcdent : spectrum =< p (x1 ), p (x2 ) >= K2 uV p 1 p 2 p u (x )u (x )

Pour lexemple de la TABLE 4.9, la matrice des noyaux entre les 4 mots est prsente dans la TABLE 4.10.
spectrum K2 bar bat car cat

bar 2 1 1 0

bat 1 2 0 1

car 1 0 2 1

cat 0 1 1 2

Table 4.10 Matrice des noyeaux dans lespace du 2-spectrum kernel Nous constatons nettement lavantage du noyau sur les reprsentations vectorielles. En eet, non seulement le noyau permet de calculer par un produit scalaire des similarits entre deux structures sans avoir transformer ces structures en vecteurs, mais aussi, 82

4.8. Approche des noyaux darbres (tree kernels) reprsenter les mots par projection dans un espace de grande dimension et mme potentiellement inni. Ce qui donne une meilleure reprsentativit des documents contenant ces mots. Dans lespace de projection les mots ne sont plus considrs comme des units atomiques indivisibles, comme cest le cas des reprsentations vectorielles traditionnelles, mais comme des structures composes de sous-mots plus ns. Les noyaux darbres doivent suivre le mme principe, savoir, les arbres ne sont plus considrs comme des units atomiques indivisibles mais comme des structures composes de sous-arbres. On retrouve ici la reprsentation structurelle (indexation) dun document XML par plusieurs sous-arbres, comme dans le cas des des sous-arbres frquents. Plusieurs noyaux darbres existent ; certains font lhypothse que les arbres sont binaires ou non, dautres que les nuds sont tiquets comme cest notamment le cas des documents XML. Nous prsentons ici un exemple simpli de noyau bas sur la prsence de sous-arbres dans une fort darbres XML. Pour ce faire, considrons une fort darbres XML ; les sous-arbres prsents dans cette fort sont numrs de 1 n. Soit hi (T ) la fonction qui renvoie le nombre doccurrences du sous-arbre i dans larbre T . On dnit alors le noyau darbre entre deux arbres XML, T1 et T2 comme le produit scalaire :
n

K (T1 , T2 ) =
i=1

hi (T1 )hi (T2 )

. Un tel noyau considre que deux arbres sont dautant plus similaires quils possdent des sous-arbres communs. Linconvnient est que, tout comme avec les sous-arbres frquents, cette mthode ne prend pas galement en compte la taille des sous-arbres, et lon comptera de la mme manire la prsence simultane dans 2 arbres dune mme feuille ou bien dun grand sous-arbre commun. La FIGURE 4.18 illustre deux ensembles darbres qui ont la mme valeur de similarit alors que dans (a) les deux arbres sont clairement plus similaires que dans (b). En eet, daprs le calcul du noyau, les ensembles (a) et (b) possdent la mme valeur de similarit alors quintuitivement, il est clair que les arbres de lensemble (a) sont nettement plus similaires que ceux de (b) [30].

Figure 4.18 Noyau darbre

83

Chapitre 5 Modle de clustering incrmental bas sur des rsums darbres

5.1 Introduction

En trs peu de temps, XML est devenu un standard incontournable pour la reprsentation et lchange de donnes sur le Web. De plus, non seulement les collections de documents XML sont rutilises, mais le volume de leurs changes saccrot continuellement. Cependant, avec les outils actuellement disponibles, la recherche dinformations dans ce type de documents est une tche non triviale. Les documents XML sont caractriss par un contenu (du texte) et une structure (balises). Ce type de documents ne peut cependant tre exploit ecacement par les mthodes conventionnelles de Recherche dInformation. En eet, ces dernires sont bases sur des modles orients contenu , tandis que le format XML permet dajouter des contraintes structurelles (balises). De mme, les approches traditionnelles de traitement des donnes telles que les bases de donnes relationnelles se sont avres peu appropries. Celles-ci sont principalement ddies la gestion des donnes fortement structures, alors que les documents XML sont considrs comme des donnes semi-structures [36]. En bref, la croissance continue des documents XML sur le Web a soulev un certain nombre de questions, telles que linterrogation, lindexation [23, 42, 47, 59, 65, 73, 80, 85, 107, 115], et/ou la classication [3, 7, 1214, 16, 27, 30, 32, 36, 37, 44, 46, 57, 70, 72, 74, 89, 112, 122], de ces documents. La classication a pour rle de regrouper des documents XML similaires dans des clusters (ou classes), an de rduire le temps de rponse et augmenter la prcision des moteurs de recherche. Cette classication peut tre thmatique ou structurelle. Nous nous intrssons particulirement la classication de documents XML, base sur leur similarit structurelle, cest--dire les arbres ordonns et tiquts dcrivant les relations entre les lments respectifs des documents. Cette similarit structurelle permet de regrouper des documents partageant des structures similaires. Ceci aiderait, dune part, mieux organiser les documents XML et, dautre part, mieux rpondre, en termes decience et decacit, aux requtes contenant des conditions structurelles. Rappelons que dans la recherche dinformation avec XML, les requtes peuvent tre formules en utilisant 85

Chapitre 5. Modle de clustering incrmental bas sur des rsums darbres des mots cls seulement ou des mots cls et des conditions structurelles. La question principale que nous abordons dans cette thse est Comment regrouper structurellement des documents XML quand leur DTD nest pas connue ? Notre proposition dans ce sens est une approche de classication base sur des structures de rsums darbres , de ces documents. Cette approche sappuie sur deux tapes cls. Dans la premier, chaque document XML est reprsent par sa structure de rsum darbre qui est ensuite utilise comme modle de reprsentation pour classer structurellement le document XML correspondant. Dans la seconde, une mesure de similarit structurelle ecace, base sur ces structures de rsums darbres est propose. A ce titre, la question primordiale est Comment mesurer la similarit structurelle de documents XML ? Cette similarit soulve dautres questions lies notamment au degr de similarit des structures, en particulier : A partir de quel seuil de similarit doit-on considrer que deux documents XML peuvent tre structurellement similaires ? Cest ces questions que nous tentons de rpondre dans cette thse.

5.2

Classication base sur la similarit structurelle

Les travaux sur la classication de documents XML existants se distinguent par la manire de reprsenter les documents, mais aussi par les mthodes de classication utilises. Nous nous intressons ici aux approches qui reprsentent les documents XML par leurs structures seulement. On distingue dans ce contexte deux principales catgories. Dans la premire, on classe directement des documents XML. Dans la seconde, par contre, on classe indirectement des documents XML via leurs DTDs.

5.2.1

Prsentation gnrale de lapproche

Notre approche se situe dans la premire catgorie, savoir, parmi les approches qui consistent classer directement des documents XML. Spciquement, pour classer structurellement des documents XML, nous utilisons leurs structures de rsums darbres tiquets. Les tiquettes correspondent aux tags et/ou attributs XML. Une structure de rsum darbre tiquet, comme illustr dans la FIGURE 5.1, est automatiquement extraite par un extracteur (ou parser), directement partir de chaque document XML considr ; elle est ensuite utilise comme modle de reprsentation par un classif ieur pour classer structurellement le document XML correspondant. Nous montrons et expliquons succinctement dans 5.2.2 comment seectue le parsing. Nous dcrivons et expliquons galement dans 5.2.3 notre algorithme de clustering.

Figure 5.1 Approche de classication structurelle 86

5.2. Classication base sur la similarit structurelle

5.2.2

Extraction du rsum darbre structurel

Nous proposons de reprsenter structurellement les documents XML par leurs structures de rsums darbres an de minimiser les traitements tout en vitant notamment la perte dinformation. Lide de base est que les rptitions de tags et/ou la possibilit davoir des tags optionnels (et leurs sous-arbres par voie de consquence), sont parmi les principales raisons qui font que des documents XML peuvent tre structurellement dirents, mme sils partagent la mme DTD. Dans ce contexte, ce nest pas toute linformation structurelle qui est utilise pour representer un document XML. Notre rsum darbre peut alors tre considr comme une structure gnrique dans le sens o lorsque des nuds (tags) frres sont dupliqus, il nest pas ncessaire de repercuter cette duplication dans la structure que nous voudrions extraire. Notons cependant que par souci de non perte dinformation et/ou de non destruction de la hirarchie de la structure XML, les duplications des nuds imbriqus, ne seront pas limines. Au mme titre, supprimer ou ignorer les attributs peut galement entrainer une perte dinformation. Alors, un moyen de les garder, serait de les considrer comme des descendants immdiats des lments auxquels ils sont rattachs dans le document XML source. Lexemple de la FIGURE 5.2 illustre cette approche de reprsentation en mettant laccent sur toutes ses caractristques.

Figure 5.2 Approche de representation dun document XML

En eet, la transformation de larbre original T1 en le rsum darbre T2 , montre que lattribut t devient un nud ls de llment a . Quant la duplication des nuds frres b , elle est limine, tout en gardant les ls ( c , b et c ) rattachs une seule occurrence de b , mais les nuds c qui taient initialement cousins sur T1 , sont devenus des frres dont il a fallu aussi liminer la duplication. Cependant, comme prconis, les duplications des nuds imbriqus ( a et b ) sont maintenues. Notre algorithme dextraction du rsum darbre est schmatiquement illustr par lorganigramme de la FIGURE 5.3. 87

Chapitre 5. Modle de clustering incrmental bas sur des rsums darbres

Figure 5.3 Algorithme dextraction dun rsum darbre XML Comme on peut le voir, notre algorithme stale sur deux phases : La premire (dsigne par Premier Parsing sur la FIGURE 5.3), sappuie sur SAX, qui renvoie tous les tags et attributs rencontrs sur un document XML. Ces derniers sont intercepts, ltrs puis transforms en une forme intermdiaire parenthse comme celle de la FIGURE 5.4. Cette forme intermdiaire est compose seulement de parenthses ouvrantes et fermantes ainsi que de tags et/ou attributs. La profondeur des parenthses dnit les niveaux hirarchiques des lments XML. Le choix de cette forme intermdiaire est motiv par lecacit de ltape suivante de lalgorithme dextraction. En eet, il existe plusieurs algorithmes permettant de construire un arbre partir dune forme parenthse, mais nous en avons choisi un qui sappuie sur la priorit des oprateurs (parenthses ainsi que les tags et attributs), pour sa rapidit. Au cours de la seconde phase (ou Second Parsing sur la FIGURE 5.3), la forme intermdiaire, produite par la premire phase, est transforme par un autre parseur en le rsum darbre correspondant conformment aux prvisions de notre approche, cest--dire en liminant les duplications des nuds frres, et en considrant chaque attribut comme un descendant direct (ls) de llment (tag) auquel il est rattach dans le document XML source. Lessentiel de la tche dextraction est accompli par ce deuxime parseur, car cest lui qui permet de passer de la forme linaire (source) du document sa reprsentation hirarchique (rsum darbre). Une illustration de cette extraction est schmatiquement prsente par la FIGURE 5.4. En somme, trois oprations essentielles sont eectues ce niveau : (i) Passage de la forme linaire du document sa reprsentation hirarchique ; (ii) Suppression des duplications des nuds frres ; (iii) Transformation des attributs eventuels en descendants directs des lments auxquels ils sont rattachs dans le document XML source. 88

5.2. Classication base sur la similarit structurelle

Figure 5.4 Un document XML et son rsum darbre

structurel

Ainsi, au lieu dutiliser des arbres XML originaux pour reprsenter des documents XML, on utilise leurs structures de rsums darbres , mais sans perte dinformation, puisque on limine seulement les rptitions des nuds frres. Ceci permet, dune part, deectuer un matching plus rapide et ais de ces arbres et, dautre part, davoir un clustering de bonne qualit.

5.2.3

Approche de clustering

On dnit formellement un cluster comme un ensemble darbres Ci = {Tik |k = 1..p} tel que p = |Ci | est le nombre darbres dans lensemble Ci . Ti1 est le rsum darbre le plus pertinent reprsenter tous les arbres du cluster Ci ; on le nomme centrode de Ci . Sim est la fonction de similarit, telle que Simk=2..p (Ti1 , Tik ) 1 avec 0 < 1. est le seuil de similarit minimum partir duquel tous les arbres de lensemble Ci , sont considrs comme similaires. Soit lensemble des clusters existants. Notre algorithme de clustering est donn dans la FIGURE 5.5. Pour classer un arbre T (reprsentant un document XML), lalgorithme doit fonctionner comme suit : Sil nexiste aucun cluster dans lensemble , alors {C1 T ; C1 }, cest-dire quil faut tout simplement en crer un, en y mettant le premier arbre T qui se prsente. T est initialement considr comme le centrode de C1 . Sil existe dj au moins un cluster, on parcourt lensemble pour vrier sil ya un cluster Ci qui peut loger larbre T . L aussi, deux cas peuvent tre envisags : Dans le premier, on est suppos avoir trouv le cluster Ci le plus appropri pour larbre T . En loccurrence, Ci est celui dont le centrode donne le meilleur degr de similarit avec larbre T . Ceci est formellement exprim par argmaxi=1..n ( {Sim(Ti1 , T )} 1). Cependant, pour avoir le centrode le plus reprsenatif pour Ci , il est primordial de calculer le poids de chacun de ses arbres. Pour cela, on 89

Chapitre 5. Modle de clustering incrmental bas sur des rsums darbres

1: for any tree T do 2: if = then 3: C1 T 4: C1 5: else 6: if argmaxi=1..n ( {Sim(Ti1 , T )} 1) = then 7: Ci T 8: for k 1 to p do 9: weight(Tik ) Tij Ci Sim(Tik , Tij ) 10: end for 11: Ti1 argmaxk=1..p (weight(Tik )) 12: else 13: CT 14: C 15: end if 16: end if 17: end for

Figure 5.5 Algorithme de clustering utilise la fonction weight(Tik ) qui nous permet didentier quel est larbre le plus important et, ce titre, il sera dsign comme nouveau centrode de Ci . Dans le second, il va falloir tout simplement crer un nouveau cluster et lajouter , comme prconis dans lalgorithme par else{C T ; C }. Notons que notre clustering est incremental et non supervis. De plus, contrairement au clustering classique, o le nombre de documents est xe, dans notre cas, de nouveaux documents peuvent tre ajouts, et leur nombre dans un cluster est une fonction du temps. Ainsi, notre clustering demeure ouvert et peut, donc, traiter de nouveaux documents tout moment. Mais, le nombre de clusters peut lui aussi augmenter en fonction de lhtrognit de la structure des documents. Autrement dit, la complexit algorithmique du clustering, elle aussi, peut augmenter. Pour pallier cet inconvnient, nous proposons une procdure dans 5.2.4 pour rduire signicativement cette complxit. Il existe une varit de mthodes de clustering bases sur la distance ddition pour calculer la similarit entre objets [77]. Notre clustering est plutt bas sur une autre mesure de similarit. Nous expliquons dans 5.2.4 cette mesure de similarit. Par ailleurs, notre clustering est caractris par la mobilt des centrodes. Cette mobilt garantit un clustering de qualit, cest--dire quelle augmente la similarit intra-clusters et diminuerait, par voie de consquence, la similarit inter-clusters. A chaque fois quun nouveau document XML se prsente, son reprsentant est systmatiquement compar dabord tous les centrodes existants de lensemble , ensuite, tous les arbres (sils existent), du cluster auquel il est assign. Notons cet eet que, le reprsentant dun nouveau document pourrait tre act, soit un cluster nouvellement cr, o il jouera initialement le rle de centrode, soit un cluster dj existant, cas o le centrode pourrait ventuellement tre remplac par un autre arbre plus reprsentatif, parmi tous les arbres du cluster. 90

5.2. Classication base sur la similarit structurelle Une autre caractristique intressante de ce clustering est le seuil de similarit que lon pourrait modier en fonction des besoins. On suit en quelque sorte le mme principe que la densit des clusters dcrite dans la mthode DBSCAN (Density-Based Spatial Clustering of Applications with Noise) [35]. En eet, conformment la fonction de similarit dnie ci-dessus, il est possible dattribuer une valeur assez leve au seuil de similarit , si lon veut obtenir des clusters ns et homognes. A linverse, une valeur relativement basse de ce seuil, produirait des clusters moins ns et htrognes. Cest un comportement que lon pourra facilement vrier dans la partie exprimentale (sous-section 6.4 du chapitre 6).

5.2.4

Similarit structurelle

De manire gnrale (sur des documents plats ), pour comparer deux termes, on utilise un dictionnaire. Mais dans un contexte hirarchique (comme XML), il est ncessaire de considrer chaque terme (nud) dans son tendue contextuelle. Lide est que mme si deux nuds sont reprsents par le mme nom, ou des noms synonymes, cela nimplique pas quils demeurent ncessairement identiques ou similaires dans le contexte de leurs anctres respectifs qui peuvent tre compltement dirents. Ainsi, la similarit de deux nuds dpend non seulement de leur similarit ontologique (les termes peuvent tre similaires parce quils sont reprsents par la mme chaine de caractres, ou bien peuvent tre synonymes, daprs le dictionnaire), mais aussi, de leurs anctres respectifs [6]. Nous proposons alors de considrer, pour chaque nud, son contexte anctres. Denition Prliminaire Soit V = [x1 , x2 , ..., xn ] un vecteur Rn ; sa norme (distance Euclidienne) est V = n 2 2 i=1 xi . Lusage de la norme permet dexploiter bon escient la notion de poids. On peut tendre cet usage des entits qui ne sont pas forcment des vecteurs de Rn . En eet, par exemple, si S = (a, b, b, a, b, c, c) est une squence de nuds, alors les poids (frquences) de a, b et c sont respectivement 2, 3 et 2. Par consquent, si ces poids sont stocks dans un vecteur comme N = [2, 3, 2], alors la norme associe S est N = 2 22 + 32 + 22 = 2 17. La norme srvira par la suite, pour la normalisation des valeurs de similarits. Mesure de similarit structurelle Soient T1 et T2 deux arbres reprsentant respectivement deux documents XML. Nous proposons de calculer leur similarit comme suit : Sim(T1 , T2 ) =
n i=1 m j =1

Simnode (e1i , e2j ) M1 M2

(5.1)

o Simnode (ei1 , e2j ) 1 est la similarit des nuds e1i et e2j . Les nuds e1i et e2j appartiennent respectivement T1 et T2 . Les bornes suprieures n = |T1 | et m = |T2 | sont les tailles (nombres de nuds) de T1 et T2 , respectivement. Le produit M1 M2 m permet de normaliser la somme n i=1 j =1 Simnode (e1i , e2j ). M1 et M2 sont deux vecteurs 91

Chapitre 5. Modle de clustering incrmental bas sur des rsums darbres dont les lments sont les poids des nuds appartenant respectivement T1 et T2 . La similarit entre deux nuds e1i et e2j sexprime comme suit : Simnode (e1i , e2j ) = P CC (r1 .e1i , r2 .e2j ) S0 (e1i , e2j ) (5.2)

o S0 (e1i , e2j ) est la similarit ontologique des nuds e1i et e2j . En dautres termes, S0 (e1i , e2j ) = 1 si e1i = e2j , S0 (e1i , e2j ) = 1 si e1i et e2j sont synonymes, sinon S0 (e1i , e2j ) = 0. P CC (r1 .e1i , r2 .e2j ) (Path Context Coecient ), represente la similarit des chemins r1 .e1i et r2 .e2j partant des racines r1 et r2 aux nuds e1i et e2j , respectivement. En fait, le terme P CC (r1 .e1i , r2 .e2j ) est la similarit des anctres respectivement des nuds e1i et e2j . Les nuds anctres jouent un rle prpondrant dans le calcul de la similarit. Ceci est bas sur lide que mme si deux nuds sont ontologiquement identiques ou similaires, ils ne le resteront pas forcment dans le contexte de leurs anctres respectifs qui peuvent tre compltement dirents. P CC (r1 .e1i , r2 .e2j ) est calcul comme suit : S1 (n1k , n2l ) (5.3) P1 P 2 o S1 (n1k , n2l ) est la similarit ontologique des nuds n1k et n2l . Les nuds n1k et n2l appartiennent respectivement aux chemins r1 .e1i et r2 .e2j . Les bornes suprieures p = |r1 .e1i | et q = |r2 .e2j | sont les tailles des chemins r1 .e1i et r2 .e2j , respectivement. P1 et P2 sont deux vecteurs dont les lments sont les poids des nuds appartenant respectivement r1 .e1i et r2 .e2j . P CC (r1 .e1i , r2 .e2j ) = Ce systme de formules est applicable tout type de nud. Cependant, si au moins un des nuds e1i et e2j est une racine, il est vident quil na pas danctres, et par consquent, P CC (r1 .e1i , r2 .e2j ) = 0, alors que e1i et e2j peuvent tre ontologiquement identiques ou synonymes. Pour y remdier, on remplace la similarit Simnode (e1i , e2j ) par la similarit ontologique S0 (e1i , e2j ). Autrement dit, P CC (r1 .e1i , r2 .e2j ) = 1. Sur la base des quations (5.1), (5.2), et (5.3), un pseudocode de lalgorithme de la similarit entre deux arbres T1 et T2 , est prsent dans la FIGURE 5.6. Sim est la similarit entre deux arbres T1 et T2 dsigne par Sim(T1 , T2 ) dans lquation (5.1), tandis que P CC est la similarit des anctres des nuds e1i et e2j , note P CC (r1 .e1i , r2 .e2j ) dans lquation (5.3). S0 [e1i , e2j ] est la similarit ontologique des nuds e1i et e2j comme indiqu dans lquation (5.2) par S0 (e1i , e2j ). Il en est de mme pour S1 [n1k , n2l ] avec les nuds n1k et n2l comme indiqu dans lquation (5.3) par S1 (n1k , n2l ). Ainsi, pour i 1 to n et j 1 to m, S0 [e1i , e2j ] est la matrice de similarit ontologique des arbres T1 et T2 . De mme, pour k 1 to p et l 1 to q , S1 [n1k , n2l ] est la matrice de similarit ontologique des anctres des nuds e1i et e2j . Les termes ||P1 ||, P2 , ||M1 || et ||M2 || sont calculs conformment la dnition de la norme donne ci-dessus dans le paragraphe Denition Prliminaire . Cet algorithme possde dans le pire des cas, une complexit de lordre O(N 2 h2 ). N et h sont respectivement la taille (nombre de nuds) maximum et la hauteur maximum 92
p k=1 q l=1

5.2. Classication base sur la similarit structurelle

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:

Sim 0 for i 1 to n do for j 1 to m do if (e1i est une racine) or (e2j est une racine) then P CC 1 else P CC 0 for k 1 to p do for l 1 to q do P CC P CC + S1 [n1k , n2l ] end for end for P CC P CC P1 P2 end if if S0 [e1i , e2j ] = 0 then Sim Sim + P CC S0 [e1i , e2j ] end if end for end for Sim M1Sim M2 return Sim Figure 5.6 Algorithme de calcul de la similarit

des arbres T1 et T2 . Mais ceci est tout--fait normal puisque les arbres ne sont pas des structures linaires et, par consquent, leur comparaison ncessite de prendre en compte le contexte hirarchique des relations entre les nuds. Cependant, la hauteur est gnralement plus petite que la taille de larbre, execept lorsque larbre est dgnr. Il existe plusieurs algorithmes de comparaison darbres bass sur la distance ddition. Certains dentre eux, tels que [20,27,74,94], ne prennent pas en compte le contexte hirarchique des nuds, et ils ont une complexit algorithmique de lordre de O(N 2 ). Dautres cependant, comme ceux de [52, 91, 120], ont des complexits plus lves comprises entre O(N 3 log n) et O(N 4 h2 ), car ils tiennent compte du contexte hirarchique des nuds. Plusieurs autres solutions ont t dveloppes, et reccemment dans [29], les auteurs ont dcrit un nouvel algorithme qui ncessite dans le pire des cas, une complcxit temporelle de lordre O(N 3 ). Nous conrmerons la tendance de la complexit algorithmique de notre mesure de similarit dans la section exprimentale. Plus prcisment, dans lexprience de timing. Reduction de la complexit algorithmique du clustering Avant de dmarrer lexperimentation, il convient de donner une ide sur la pertinence et la performance de notre approche de clustering. En eet, dj en optant pour des structures de rsums darbres , la place des structures darbres originaux pour reprsenter des documents XML, permet de toute vidence damliorer la complexit temporelle du 93

Chapitre 5. Modle de clustering incrmental bas sur des rsums darbres clustering. Notons aussi que, cette manire de reprsenter les structures des documents XML, vite la perte dinformation et prserve la hirarchie de la structure des documents. Cependant, la complexit algorithmique du clustering, augmente avec le nombre de clusters. En eet, durant le processus de clustering, on eectue plusieurs comparaisons, an de pouvoir localiser le cluster le plus appropri, permettant ainsi, de classer un document. On peut rduire le nombre de comparaisons et amliorer substantiellement la performance du clustering. Pour ce faire, au lieu dappliquer navement les formules proposes dans 5.2.4, on introduit certaines conditions pralables permettant dacclerer le processus de matching. On selectionne cet eet, le cluster qui a le plus de chance de donner une similarit au moins gale au seuil de similarit . Pour cela, on sappuie sur la formule (5.4) pour liminer les clusters inutiles (ceux dont les centrodes donnent une similarit infrieure ), dans le processus de matching, et dtecter par voie de consquence, le cluster appropri. Similarity (T1 , T2 ) =
n i=1 m j =1

M1

S0 (e1i , e2j ) M2

(5.4)

T1 et T2 sont respectivement les rsums darbres de deux documents XML. Rappelons que M1 et M2 sont deux vecteurs dont les lments sont les poids (frquences) des nuds appartenant repectivement T1 et T2 . Lide est que si Similarity (T1 , T2 ) < , il est mathmatiquement imposible en utilisant les prcdentes formules (5.1), (5.2) et (5.3), dobtenir une valeur de similarit qui peut atteindre le seuil . En eet, si lon considre les formules (5.1), (5.2) et (5.4), alors Similarity (T1 , T2 ) Sim(T1 , T2 ), ceci parce que dans (5.2) on a toujours 0 P CC (r1 .e1i , r2 .e2j ) 1. Lavantage dutiliser la condition Similarity (T1 , T2 ) < est double. Dune part, cela permet de dtecter rapidement le cluster appropri. Dautre part, cela garantit que tous les centrodes des clusters limins, ne peuvent donner une similarit Sim(T1 , T2 ) gale . Cependant, le nombre de documents dans un cluster lui aussi peut augmenter et cela va faire croitre inexorablement la complexit algorithmique au cours du changement de centrode. En eet, chaque fois quun nouveau document est ajout dans un cluster contenant dja des documents, la procdure de recherche du meilleur reprsentant (centrode) est engage : Ti1 argmaxk=1..p (weight(Tik )) (voir algorithme de clustering de la FIGURE 5.5). Cest un inconvnient majeur, quil va falloir contourner sans toutefois diminuer sensiblement la abilit du clustering. Mais comme la similarit nest pas transitive, on ne peut trouver de solution gnrale au problme. Cependant, certaines solutions ad hoc sont possibles comme par exemple : Modier lalgorithme de telle sorte quil arrte de chercher remplacer le centrode ds lors quune certaine condition est vrie (cette condition peut tre par exemple un nombre susant de fois quun centrode a t modi). On peut tout aussi laisser lalgorithme tel quel et procder comme suit (solution semi automatique) : 1. Faire tourner lalgorithme jusqu atteindre un certain nombre de documents dans un cluster. Ce nombre sera x en fonction des caractristiques du corpus documentaire utilis (nombre moyen de nuds dans chaque document, profondeurs des arborescences des documents, etc.) ; 94

5.2. Classication base sur la similarit structurelle 2. Rcuprer les documents de tous les clusters respectivement dans des repertoires reservs cet eet ; 3. Vider tous les clusters et ne garder en fait que leurs centrodes respectifs ; 4. Relancer lalgorithme avec ces clusters munis de leurs centrodes respectifs sur les documents non encore traits (rappelons ce titre que notre clustering reste ouvert et peut tre relanc tout moment pour traiter de nouveaux documents) ; 5. Rpeter la procdure partir du point 1, jusqu traiter tous les documents concerns. Cest cette deuxime solution que nous avons adopte dans nos expriementations. Quoique notre clustering soit la base automatique (non supervis), et peut clusteriser un nombre potentiellement inni darbres, mais le fait dintervenir manuellement pour une raison ou pour une autre, donne ce clustering une apparence realtivement semi-supervise.

95

Chapitre 6 Exprimentation
6.1
6.1.1

Implmentation du systme de classication

Parsing

Nous avons dvelopp un premier programme en Java sous lenvironnement JCreator. Le programme dvelopp consiste en deux modules : le premier sappuie sur SAX, pour eectuer un premier parsing comme annonc en section 5.2 (sous-section 5.2.1). Ce module fournit pour chaque document XML trait un chier intermdiaire intercept par un deuxime module pour naliser lextraction du rsum darbre correspondant.

6.1.2

Clustering

Nous avons ensuite crit un deuxime programme en C++ qui utilise les chiers (rsums darbres) gnrs par le premier programme pour les clustriser. Note 1 Les deux programmes (Parsing et Clustering) correspondent respectivement lextracteur (ou parseur) et au classieur, voqus dans la sous-section 5.2.1 travers la FIGURE 5.1.

6.2

Collections XML utilises

Les expriences ont t eectues sur 2 ensembles de donnes, savoir, le corpus XML, ACM SIGMOD Record 7 ainsi quune collection de documents XML synthtique. Le corpus ACM SIGMOD concerne les articles scientiques publis par la confrence ACM SIGMOD. Il est compos de 968 documents XML, correspondant 5 DTDs : HomePage, IndexTermPage, OrdinaryIssuePage, ProceedingsPage et SigmodRecord. Ce corpus est rparti comme dans la TABLE 6.1. Les dtails concernant la collection XML synthtique seront fournis dans la partie rserve cet eet ; plus prcisment, dans lexprience de timing.
7. http ://www.sigmod.org/publications/sigmod-record/xml-edition

97

Chapitre 6. Exprimentation Nom de la DTD IndexTermsPage OrdinaryIssuePage ProceedingsPage SigmodRecord HomePage Nombre de documents XML 920 30 16 1 1

Table 6.1 Repartition du corpus ACM SIGMOD

6.3

Mtriques dvaluation

Lvaluation consiste vrier dans quelle mesure le clustering est suceptible de retrouver des clusters en accord avec les classes du corpus tiquet qui sont considres comme des classes cibles. Pour valider notre approche, nous avons utilis la F-mesure, la puret et lentropie, qui sont des mtriques couramment employes pour mesurer les performances dun clustering.

6.3.1

F-mesure

La F-mesure est une combinaison entre la prcision et le rappel. Elle permet de mesurer lquilibre entre P (la prcision) et R (le rappel) exprims respectivement par les quations (6.1) et (6.2) Xd (6.1) P = Nc R= Xd Nd (6.2)

o Nc est le nombre de documents du cluster C , Nd est le nombre de documents de la classe cible (DTD) et Xd est le nombre de documents de la classe cible aects au cluster C . En fait, chaque DTD est considre comme une classe cible par rapport laquelle on peut valuer notre clustering. Donc on connait priori ces classes, cest--dire quon connait leurs eectifs, ainsi que les noms des documents quelles contiennent. La F-mesure F1 , quant elle, est exprime par lquation (6.3) reprsentant la moyenne harmonique de la prcision et du rappel. 2P R (6.3) F1 = P +R Dans le cas o le cluster est htrogne, cest--dire compos de documents issus de classes direntes, la prcision et le rappel sont respectivement les moyennes des prcisions et rappels du cluster par rapport ces classes.

6.3.2

Puret

La puret dun cluster correspond la proportion de documents du cluster appartenant la classe majoritaire. On part alors de lhypothse qu chaque cluster l est associe la 98

6.3. Mtriques dvaluation classe majoritaire des documents quil contient. On dsigne cette classe par cl et on dnit la puret du cluster l par lequation (6.4). puret(l) = nombre de documents du cluster issus de la classe cl nombre de documents du cluster l (6.4)

Si tous les documents dun cluster proviennent de la mme classe, la puret du cluster sera evidemment gale 1.

6.3.3

Entropie

Lentropie permet dvaluer la rpartition des direntes classes de documents dans un cluster. Si nl reprsente le nombre de documents dans le cluster l, nl i le nombre de documents du cluster l issus de la classe i, et m le nombre de classes, alors lentropie sexprime comme suit par lequation (6.5).
m nl nl 1 i i log entropie(l) = l log (m) i=1 n nl

(6.5)

Si lentropie est trs faible, le clustering est de bonne qualit. Lentropie idale est gale 0. Pour obtenir une mesure globale des metriques prcdentes sur lensemble des clusters, on calcule leurs moyennes. Cependant, en cas dingalit de tailles des clusters, ces moyennes risquent dtre incohrentes et ne pas reter la ralit du classieur, notamment en ce qui concerne les clusters eectifs levs. Pour contourner cet inconvnient et amliorer les paramtres dvaluation, on introduit deux nouvelles mesures, savoir, la micro_mean et la macro_mean (respectivement la micro-moyenne et la macromoyenne). Contrairement la macro_mean qui ignore totalement la taille des clusters, la micro_mean elle, par contre, prend en compte cette taille et permet davoir une ide plus prcise sur la qualit du clustering. Dans ce cas, si Mi correspond lune des mesures prcdentes (F-mesure, puret et entropie), pour un cluster donn i, sa macro_mean et sa micro_mean sont donnes respectivement par les formules (6.6) et (6.7).
R

Mi macro_mean =
i=1

(6.6)

Ni Mi micro_mean =
i=1 R

(6.7) Ni

i=1

o R reprsente le nombre de clusters (i = 1, R), et Ni le nombre de documents de chaque cluster i. 99

Chapitre 6. Exprimentation

6.4

Evaluation

Pour cette exprimentation nous navons pas eu besoin dutiliser un dictionnaire car les vocabulaires des structures sont standards relativement aux corpus utiliss. Nous avons cet eet inhib la procdure de recherche des synonymes dans notre programme de clustering. Dans la phase suivante, nous avons tout dabord extrait des collections de documents XML considres, les rsums darbres correspondants, ensuite nous avons procd respectivement leur clustering. Rappelons que le seuil de similarit suit le mme principe que la densit des clusters de la mthode DBSCAN [35], savoir, si on veut dtecter des clusters trs homognes (les documents XML qui sy trouvent sont structurellement trs similaires), il faut attribuer une valeur lve au seuil de similarit . A linverse, si lon assigne une valeur relativement basse ce seuil, on obtient des clusters htrognes. Nous avons alors x, pour chaque exprimentation ralise, le seuil de similarit des valeurs dans lintervalle [0, 1]. Nous avons pour cela fait tourner le classieur une dizaine de fois respectivement avec un seuil allant de 0.1 1 par pas de 0.1. Pour valider notre approche nous avons eectu plusieurs types de tests. Le premier test eectu consiste calculer les valeurs micro_mean et macro_mean respectivement de la puret, lentropie et la F-mesure. Rappelons que ces mtriques permettent de mesurer les performances dun clustering. Le deuxime test men consiste comparer la mesure de similarit propose la mesure de similarit base sur la distance ddition. Le troisime test consiste vrier la faisabilit et la abilit de notre approche de reprsentation des documents XML. Le quatrime test a pour objectif de comparer nos rsultats ceux de certaines approches. Enn, un test de timing est eectu sur une collection synthtique de documents XML, et a permis de situer notre approche par rapport certains travaux existants.

6.4.1

Mesure des performances du clustering

Comme prconis, nous avons conduit le premier test sur le corpus ACM SIGMOD. La TABLE 6.2 donne pour chaque seuil de similarit le nombre de clusters gnrs, ainsi que le nombre de documents dans chaque cluster. Dans la TABLE 6.3 sont rcapitules les valeurs globales (micro_mean et macro_mean) de la puret, lentropie et la F-mesure. Pour = 1, nous avons obtenu 17 clusters, mais pour des raisons de prsentation nous les avons pas reports dans la TABLE 6.2. Toutes ces valeurs indiquent, conformment nos prvisions, queectivement moins le seuil est lev, moins il ya de clusters. Ce comportement est tout fait prvisible. En eet, pour allant de 0.1 0.5, le nombre de clusters gnrs se situe entre 1 et 4, cest--dire infrieur au nombre de classes cibles (5 DTDs). Autrement dit, des documents XML ne partageant pas la mme DTD, peuvent se regrouper dans 100

6.4. Evaluation Seuil = 0.1 = 0.2 = 0.3 = 0.4 = 0.5 = 0.6 = 0.7 = 0.8 = 0.9 Nbrs de clusters 1 2 2 3 4 5 5 7 9 Eectifs par C2 C3 C4 48 48 31 17 31 16 1 30 16 1 30 16 1 438 18 12 438 18 12 cluster Ci=1,9 C5 C6 C7 C8 1 1 16 1 1 12 2 2 1

C1 968 920 920 920 920 920 920 482 482

C9 1

Table 6.2 Nombres de clusters gnrs avec leurs eectifs pour chaque seuil Seuil = 0.1 = 0.2 = 0.3 = 0.4 = 0.5 = 0.6 = 0.7 = 0.8 = 0.9 Macro_mean Puret Entropie F-mesure 0.9504 0.1479 0.3333 0.8125 0.2550 0.7000 0.8125 0.2550 0.7000 0.9696 0.0753 0.6876 0.9919 0.0218 0.8806 1.0000 0.0000 1.0000 1.0000 0.0000 1.0000 1.0000 0.0000 0.8076 1.0000 0.0000 0.7111 Micro_mean Entropie F-mesure 0.1479 0.3333 0.0250 0.9702 0.0250 0.9702 0.0052 0.9766 0.0028 0.9847 0.0000 1.0000 0.0000 1.0000 0.0000 0.9763 0.0000 0.6590

Puret 0.9504 0.9814 0.9814 0.9979 0.9989 1.0000 1.0000 1.0000 1.0000

Table 6.3 Resultats du test de clustering un mme cluster, ce qui produit des clusters plus ou moins htrognes. Ceci est d vraissemblablement au fait que des documents XML priori htrognes possdent tout de mme un pourcentage de nuds en commun qui leur permet dtre considrs comme tant stucturellement similaires un certain degr et donc de rester regroups dans un mme cluster. Mais ceci est tout fait normal, puisquil ya forcment des nuds en commun entre les documents dune mme collection, mme sils ne drivent pas de la mme DTD. Pour situ entre 0.6 et 0.7, les 5 clusters obtenus correspondent exactement aux 5 classes cibles DTDs stimes (5 DTDs). Ceci est dautant vrai que les macro_mean et micro_mean pour toutes les mtriques utilises sont leurs valeurs idales : 1 pour la puret et la F-mesure, et 0 pour lentropie. Pour un seuil situ entre 0.8 et 0.9, les clusters clatent, mme sils sont priori homognes (leurs documents drivent de la mme DTD). Ce phnomne ressemble quelquepeu une perte dinformation. Cependant, il ny a gure de perte dinformation, si ce nest que le problme est d tout simplement aux DTDs de la collection utilise. Notons quune DTD peut gnralement admettre des lments optionnels (tags et attributs), cest--dire qui peuvent apparaitre dans certains documents XML 101

Chapitre 6. Exprimentation mais pas forcment dans dautres. IndexTermsPage, OrdinaryIssuePage et ProceedingsPage, possdent des lments optionnels tels que < ! ELEMENT S(A)*>, cest-dire que A peut apparaitre une ou plusieurs fois dans certains documents XML et pas du tout dans dautres. Par consquent, certains documents partageant lorigine la mme DTD vont devoir se sparer : une partie dentre eux va migrer vers dautres clusters nouvellement crs. Ceci explique le nombre lv de clusters (7 et 9) par rapport au nombre de classes cibles (5 DTDs) respectivement pour = 0.8 et = 0.9. Conformment aux rsultats obtenus dans ce premier test, un seuil dans lintervalle [0.6, 0.7] semble tre une valeur moyenne satisfaisante pour notre approche avec la collection teste, cest--dire le corpus ACM SIGMOD.

6.4.2

Mesure de similarit propose vs. distance ddition

Dans le deuxime test, nous avons compar la mesure de similarit propose une autre mesure, en loccurrence la distance ddition. Cette dernire a t trs largement utilise dans la majorit des mthodes de clustering. Cette comparaison est motive par le temps de rponse et la pertinence des rsultats de clustering. Nous avons pour cela, dabord remplac dans notre algorithme de clustering, la mesure de similarit propose, par la distance ddition, ensuite nous avons eectu un test avec les mmes valeurs de seuil de similarit que le test prcdent. Par ailleurs, compte tenu des rsultats rcurrents (notamment pour les 920 documents correspondant IndexTermsPage), obtenus dans le test prcdent nous du corpus, savoir, (348=300+30+16+1+1) documents navons alors employ que le 1 3 correspondant respectivement IndexTermsPage, OrdinaryIssuePage, ProceedingsPage, HomePage et SigmodRecord. Les rsultats sont rcapituls dans la TABLE 6.4. La distance ddition applique aux arbres ordonns est une extension de la distance de Levenshtein qui, la base, mesure la similarit entre deux chanes de caractres. Lalgorithme de la FIGURE 6.1 permet de calculer la distance de Levenshtein entre deux chanes de caractres. Cest un algorithme de programmation dynamique utilisant une matrice de dimension (n + 1) (m + 1), n et m sont les longueurs respectivement des deux chanes de caractres. Cet algorithme renvoie un entier positif ou nul. Il renvoie 0 si les chanes c1 et c2 sont gales. Si les chanes c1 et c2 sont trs direntes, la fonction renverra au maximum la plus grande longueur des deux chanes. d[n, m] tant la distance ddition minimale (celle ncessitant un cot minimum en oprations dinsertion, de remplacement et de suppression). La similarit dans ce cas entre deux arbres T1 et T2 de tailles p et q , base de cette distance, est exprime par lequation (6.8) d[p, q ] (6.8) Simdist (T1 , T2 ) = 1 dmax o dmax est obtenu en supprimant tous les nuds de T1 , et les remplacer par ceux de T2 ou inversement. Autrement dit, dmax est la somme des nuds des deux arbres. Labrviation NC dans la TABLE 6.4 reprsente le nombre de clusters ; lunit de temps utilise pour la colonne nomme Temps est la seconde.

102

6.4. Evaluation
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:

for i 0 to n do d[i, 0] i end for for j 0 to m do d[0, j ] j end for for i 1 to n do for j 1 to m do if (c1 [i 1] = c2 [j 1]) then cost 0 else cost 1 end if d[i, j ] M in(d[i 1, j ] + 1, d[i, j 1] + 1, d[i 1, j 1] + cost) end for end for return d[n, m] Figure 6.1 Distance de Levenshtein

Comme on peut le constater, aussi bien pour la mesure de similarit propose que pour la distance ddition, le temps de clustering augmente lorsque le seuil de similarit diminue. Ceci est tout fait normal, puisque lorsque le nombre de clusters est faible, il ya forcment des clusters qui contiennent un grand nombre de documents, ce qui se traduit par un grand nombre de comparaisons au cours du changement de centrode. Quant aux dirences entre les deux mesures, on note un certain dcalage dans les temps de rponse et des dirences sur les valeurs des similarits obtenues. Le facteur temps nest pas trs contraignant et ne doit pas peser beaucoup sur la faisabilit de ce genre dapplication (le clustering nest pas une application interactif o le paramtre temps est toujours prpondrant). La dirence dans les temps de rponse est vidente, tant donnes les dirences entre les deux mesures de similarit compares. Notons cependant que les dirences concernant les valeurs de ces similarits sont cruciales, puisque cest sur la base de la similarit quil sera dcid quun document soit ou non aect un certain cluster. Dailleurs, ces dirences ont un impact direct sur le nombre de clusters obtenus (TABLE 6.4), ou le nombre de documents dans les clusters (TABLE 6.5), comme cest le cas avec les seuils =0.4, 0.8 et 0.9. En eet, avec ces seuils certains documents ne sont pas susamment structurellement similaires (par rapport au centrode) pour pouvoir rester regroups dans un mme cluster. Ceci est d, notre mesure de similarit qui prend en compte le contexte anctres des nuds, si bien quon ne trouve dans un mme cluster que les documents ayant des structures hirarchiquement trs proches. Ainsi, les documents qui ne satisfont pas cette condition, cest--dire qui ne sont pas susamment structurellement similaires migreront vers dautres clusters nouvellement crs (C2 et C4 avec 0.8 ; C2 , C4 , C6 et C7 avec 0.9). En fait, C2 , C4 , C6 et C7 sont considrs comme ne correspondant aucune DTD. Lexemple de la FIGURE 6.2 explique clairement les caractristiques de notre mesure de similarit et montre limportance de la prise en compte 103

Chapitre 6. Exprimentation Seuil = 0.1 = 0.2 = 0.3 = 0.4 = 0.5 = 0.6 = 0.7 = 0.8 = 0.9 Mesure propose NC Temps 1 1.67103 2 1.52103 2 1.52103 3 1.43103 4 1.35103 5 1.28103 5 1.28103 7 1.17103 9 1.10103 Distance ddition NC Temps 1 1.43102 2 1.31102 2 1.31102 2 1.31102 4 1.16102 5 1.02102 5 1.02102 5 1.02102 7 0.85102

Table 6.4 Mesure propose vs. distance ddition (clustering et timing) du contexte des nuds anctres dans le calcul de la similarit.

Figure 6.2 Comparaison de deux arbres XML En eet, le calcul de la similarit entre T1 et T2 montre clairement la dirence entre les deux approches, cest--dire que notre mesure de similarit et la distance ddition. La distance ddition (base sur lalgorithme de la distance de Levenshtein), indique que larbre T1 est identique larbre T2 , alors leur similarit est gale 1. Ceci parce que leur parcours en profondeur en prordre (depth-rst traversal), donne la mme squence de nuds, savoir, a, b, c, dans cet ordre pour les deux arbres, et par consquent, sur la base de lquation (6.8) et lalgorithme qui calcule la distance de Levenshtein de la FIGURE 6.1, le calcul donne une similarit gale 1, alors que les deux arbres sont dirents. Lalgorithme calcule la distance minimum d[3, 3] entre T1 et T2 , d[3, 3] = 0 ; 3 tant la taille (nombre de nuds) de T1 et T2 respectivement. La distance maximum dmax tant gale 6 puisque par dnition dmax est la somme (3+3=6), des nuds des deux arbres. Par consquent, la similarit base sur la distance ddition [3,3] 0 =1- 6 = 1. Cependant, notre mesure de similarit donne est Simdist (T1 , T2 ) = 1 d dmax un rsultat cohrent (retant le contexte hirarachque des nuds), et compltement dirent de celui de lalgorithme de calcul de la distance de Levenshtein. Pour conrmer nos propos, nous calculons la similarit entre T1 et T2 , en appliquant les formules (5.1), (5.2) et (5.3) dnies pour notre mesure de similarit. Pour cela, nous commenons dabord par le calcul de la similarit ontologique, cest--dire S0 (e1 , e2 ), ensuite, nous appliquons graduellement les formules proposes ((5.1), (5.2) et (5.3)), jusquau rsultat nal. La similarit ontologique S0 (e1 , e2 ) = 0, e1 = e2 , mais S0 (a, a) = 1, S0 (b, b) = 1 104

6.4. Evaluation Seuil = 0.1 = 0.2 = 0.3 = 0.4 = 0.5 = 0.6 = 0.7 = 0.8 = 0.9 Seuil = 0.1 = 0.2 = 0.3 = 0.4 = 0.5 = 0.6 = 0.7 = 0.8 = 0.9 C1 348 300 300 300 300 300 300 173 173 Distance ddition C1 C2 C3 C4 C5 C6 C7 348 300 48 300 48 300 48 300 31 16 1 300 30 16 1 1 300 30 16 1 1 300 30 16 1 1 173 127 18 12 16 1 1 Mesure de similarit propose C2 C3 C4 C5 C6 C7 C8 C9 48 48 31 17 31 16 1 30 16 1 1 30 16 1 1 127 18 12 16 1 1 127 18 12 12 2 2 1 1

Table 6.5 Mesure de similarit propose vs. distance ddition (rsultats de clustering)

et S0 (c, c) = 1. Par consquent, Simnode (e1 , e2 ) = 0, e1 = e2 . En dautres termes, nous calculons Simnode (e1 , e2 ) seulement entre les paires de nuds (a, a), (b, b) et (c, c). Les similarits Simnode (a, a) = P CC (a.a, a.a) S0 (a, a), Simnode (b, b) = P CC (a.b, a.b) S0 (b, b) et Simnode (c, c) = P CC (a.c, a.b.c) S0 (c, c) sont calcules conformment lquation (5.2). Mais, puisque le nud a est une racine, alors il na pas danctres et donc P CC (a.a, a.a)=1. P CC (a.b, a.b) et P CC (a.c, a.b.c) sont calculs suivant la formule (5.3). )+S1 (c,c) )+S1 (b,b) 2 = 1+1 = 1 ; P CC (a.c, a.b.c) = S1 (a,a = 1+1 = P CC (a.b, a.b) = S1 (a,a 2 2 2 2 2 2 2 2 2 2 3 6 6 2 = 0.816. Mais comme S0 (a, a) = 1, S0 (b, b) = 1 et S0 (c, c) = 1, alors Simnode (a, a) = 2.45 P CC (a.a, a.a) S0 (a, a) = 1 1 = 1, Simnode (b, b) = P CC (a.b, a.b) S0 (b, b) = 1 1 = 1, et Simnode (c, c) = P CC (a.c, a.b.c) S0 (c, c) = 0.816 1 = 0.816. Cette valeur (0.816), est tout fait conforme, puisque les nuds (c, c) sont sur deux positions relatives distinctes dans les arbres T1 et T2 respectivement, et de surcroit leurs parents sont dirents (a est le pre de c dans T1 et b est le pre de c dans T2 ). Enn, nous obtenons la similarit entre les deux arbres T1 et T2 , cest--dire Sim(T1 , T2 ) =
3 i=1 3 Simnode (e1i ,e2j ) j =1 2 2 n i=1 m j =1

Simnode (e1i ,e2j )

M1 M2

.816 = = 1+1+0 0.94. La valeur (0.94) conrme le rsultat envi3 3 3 sag et dmontre que notre mesure de similarit prend eectivement toujours en compte le contexte hirarchique des nuds contrairement la distance ddition de Levenshtein.

105

Chapitre 6. Exprimentation

6.4.3

Intert de la reprsentation des documents XML par des rsums darbres

Pour conrmer la abilit et la faisabilit de notre approche de rprsentation structurelle des documents XML, nous avons eectu un autre type de test sur un sous-ensemble de documents XML de la collection ACM SIGMOD. Pour cela, nous avons extrait deux chantillons darbres : Le premier tant extrait en utilisant notre parseur (FIGURE 5.3), donc cest un sous-ensemble de rsums darbres. Pour le deuxime, au lieu dextraire des rsums darbres, nous avons modi lgrement notre parseur (Second Parsing sur la FIGURE 5.3), de sorte ne pas liminer les rptitions des nuds frres et dobtenir ainsi des arbres XML originaux. Nous avons pour cela pris un petit sous-ensemble de 100 documents XML reparti comme dans la TABLE 6.6. Nom de la DTD IndexTermsPage OrdinaryIssuePage ProceedingsPage SigmodRecord HomePage Nombre de documents XML 52 30 16 1 1

Table 6.6 Repartition du sous-ensemble du corpus ACM SIGMOD Nous avons ensuite ralis des expriences avec les deux chantillons darbres que nous avons extraits partir du sous-ensemble des 100 documents XML de la TABLE 6.6. Ainsi, comme pour les prcdents tests, nous avons eectu ce test avec un seuil de similarit dans lintervalle [0.1, 0.9]. Dans la TABLE 6.7 sont repertoris les nombres de clusters gnrs ainsi que les nombres de documents quils contiennent respectivement avec les deux types dchantillons darbres XML utiliss pour ce test. La distribution des documents en clusters montre clairement que la reprsentation des documents XML par des rsums darbres est meilleure que leur reprsentation par des arbres XML originaux. En eet, avec les rsums darbres par exemple, pour un seuil de similarit compris entre 0.5 et 0.8, le nombre de clusters gnrs est entre 4 et 6, cest-dire trs proche du nombre de clusters escompt (correspondant aux 5 DTDs cibles). Ces clusters sont homognes, cest--dire quils contiennent des documents partageant les mmes DTDs, particulirement pour un seuil de similarit entre 0.6 et 0.7. En revanche, avec les arbres XML originaux, la distribution des documents est compltement inconhrente et loin du clustering prvu pour toute valeur dans lintervalle [0.1, 0.9]. Par ailleurs, il est vident que la vitesse dexcution du processus de clustering est meilleure avec les rsums darbres quavec les arbres originaux. En eet, les rsums darbres sont meilleurs parce que leurs tailles sont beaucoup plus petites que celles des arbres originaux. En bref, cette exprience a montr que la reprsentation des documents XML par des rsums darbres a deux avantages par rapport aux arbres XML originaux : 106

6.4. Evaluation

Seuil = 0.1 = 0.2 = 0.3 = 0.4 = 0.5 = 0.6 = 0.7 = 0.8 = 0.9

Rsums darbres C1 C2 C3 C4 C5 C6 C7 = 0.1 100 = 0.2 52 48 = 0.3 52 48 = 0.4 52 31 17 = 0.5 52 31 16 1 = 0.6 52 30 16 1 1 = 0.7 52 30 16 1 1 = 0.8 52 18 12 16 1 1 = 0.9 52 18 12 12 2 2 1 Arbres XML originaux 1 2 3 4 5 6 7 8 9 10 11 12 100 - - - - 52 48 - - - - 52 48 - - - - 43 9 17 13 6 5 5 1 1 36 7 9 17 7 6 6 3 2 5 1 1 36 7 9 13 4 7 6 6 3 2 5 1 36 7 9 13 4 7 6 3 2 1 3 2 24 12 7 9 13 4 7 6 3 2 1 3 24 12 7 9 13 4 7 6 2 1 2 1 Seuil

C8 1 13 1 5 2 3 14 1 5 2 15 1 1 5 16 17 1 1 1

Table 6.7 Rsums darbres XML vs. arbres XML originaux

Seuil

0.1

Precision (P ) 0.2 Rappel (R) 1 F-mesure (F1 ) 0.34 Precision (P ) 0.2 Rappel (R) 1 F-mesure (F1 ) 0.34

0.2 0.3 0.4 0.5 0.6 Rsums darbres XML 0.63 0.63 0.67 0.88 1 1 1 1 1 1 0.77 0.77 0.80 0.94 1 Arbres XML originaux 0.63 0.63 1 1 1 1 1 0.75 0.73 0.70 0.77 0.77 0.86 0.84 0.82

0.7 1 1 1

0.8

0.9

1 1 0.92 0.87 0.96 0.93

1 1 1 0.66 0.62 0.60 0.79 0.76 0.75

Table 6.8 Rsums darbres XML vs. arbres XML originaux (P , R et F1 )

107

Chapitre 6. Exprimentation La abilit de la reprsentation des documents XML. La vitesse dexecution du processus de clustering. Cette abilt signie quil ny a ni perte dinformation, ni bruit (information non pertinente). Pour tayer nos propos et conrmer la pertinence de lapproche adopte pour reprsenter structurellement les documents XML, nous utilisons trois mesures communment employes en Recherche dInformation, en loccurence, R (le rappel), P (la prcision) et F1 (la F-mesure). Ainsi, les rsultats de la TABLE 6.7 sont interprts en termes de prcision, rappel et F-mesure, respectivement dans la TABLE 6.8, FIGURE 6.3, FIGURE 6.4 et FIGURE 6.5. La legende RA et AO dans FIGURE 6.3, FIGURE 6.4 et FIGURE 6.5 sont les abrviations de rsums darbres XML et arbres XML originaux , respectivement. Les courbes, particulirement celles du rappel et de la F-mesure, conrment clairement que les rsums darbres XML sont meilleurs que les arbres XML originaux. En eet, la courbe du rappel RA est plus haute que la courbe du rappel AO dans tout lintervalle [0.1, 0.9]. Concernant la prcision, la courbe RA est pratiquement la mme que la courbe AO, except dans le petit intervalle [0.4, 0.5] o elle est plus basse. Il ny a rien de mal ce rsultat puisque, dans lanalyse de ces documents, nous avons constat que certains dentre eux ont plusieurs rptitions de nuds frres. Mais puisque avec les arbres XML originaux ces rptitions ne sont pas limines, alors dans ce cas, mme les documents XML partageant la mme DTD peuvent ne pas rester tous ensemble dans le mme cluster. Ceci est traduit par la courbe du rappel AO partir de = 0.4. Notons que la courbe de la F-mesure RA est plus haute que la courbe de la F-mesure AO. En dautres termes, lapproche de reprsentation des documents XML par des rsums darbres est meilleure que leur reprsentation par leurs arbres originaux.

Figure 6.3 Courbe de la prcision 108

6.4. Evaluation

Figure 6.4 Courbe du rappel

Figure 6.5 Courbe de la F-mesure

6.4.4

Comparaison de nos rsulats avec ceux obtenus avec dautres mthodes

Ce quatrime test consiste comparer certains de nos rsultats dexprimentation avec ceux obtenus dans dautres approches. Nous avons choisi de comparer notre mthode celles dcrites dans [20, 27, 74, 94], pour plusieurs raisons : Tout comme notre approche, ces approches utilisent des structures arborescentes pour reprsenter structurellement des documents XML. De mme, ces approches, tout comme la notre, utilisent les mmes ensembles de donnes dans leurs exprimentations. Leurs mthodes de clustering sont bases sur des mesures de similarit direntes de la notre. Rappelons par ailleurs que les rsultats ne dpendent pas que de la mesure de similarit, mais aussi du modle choisi pour reprsenter les structures des documents XML (arbres originaux ou rsums darbres). 109

Chapitre 6. Exprimentation Etant donn que cest le corpus ACM SIGMOD dont il sagit, nous avons donc rutilis lchantillon du test prcdent, savoir celui de la TABLE 6.6. Dans la TABLE 6.9, on peut voir les rsultats de cette comparaison. Ces valeurs reprsentent les moyennes respectivement des prcisions, rappels et F-mesure dans lintervalle [0, 1].

[20] [27] [74] [94] Notre approche

Prcision (P ) 0.86 0.86 0.81 0.90 0.78

Rappel (R) F-mesure (F1 ) 0.57 0.68 0.57 0.68 0.64 0.72 0.61 0.73 0.97 0.86

Table 6.9 Comparaison de nos rsultats avec ceux de [20, 27, 74, 94]

La TABLE 6.9 montre que notre clustering possde une prcision lgrement infrieure celles des approches [20, 27, 74, 94], mais il a cependant un meilleur rappel et, par consquent, aussi une meilleure F-mesure.

6.4.5

Exprience de timing

Comme prconis, ce test consiste dterminer quel est le temps ncessaire pour calculer la similarit structurelle entre deux documents XML. Rapellons que dans le cas de notre approche, le calcul de cette similarit possde une complexit thorique, dans le pire des cas, de O(N 2 h2 ). N et h reprsentent respectivement la taille maximum et la hauteur maximum des arbres XML T1 et T2 comparer. Pour mener bien ce type dexprimentation, nous avons gnr un ensemble synthtique de 20 documents XML (divis en deux groupes de 10 documents chacun). Le nombre de nuds de chaque groupe de documents varie de 50 500. Le premier groupe est consitu darbres dont les hauteurs sont dans lintervalle [5,10]. Les hauteurs des arbres XML du deuxime groupe, quant elles, sont gales 1, cest--dire que la complexit du calcul de la similarit entre deux arbres T1 et T2 de ce groupe est dans le pire des cas O(N 2 ). Tout comme dans le troisime test, nous avons modi lgrement notre parseur (Second Parsing de la FIGURE 5.3), de sorte ne pas liminer les duplications des nuds frres, et obtenir ainsi des arbres XML originaux (les structures entires des documents XML). Lexprience de timing est eectue sur un PC Lenovo Intel (R) Core (TM) 2 Duo CPU, 2.00 GHz Processor et 2,99 GB de RAM. Les graphes de la FIGURE 6.6 et FIGURE 6.7 expriment les rsultats de lexprience de timing ralise sur les documents du premier et du deuxime groupe respectivement. 110

6.4. Evaluation

Figure 6.6 Rsulats de timing avec les hauteurs h dans lintervalle [5,10] : O(N 2 h2 )

Figure 6.7 Rsulats de timing avec la hauteur h = 1 : O(N 2 ) Dans le premier cas, savoir, avec les arbres de hauteurs comprises dans lintervalle [5,10], comme illustr par la FIGURE 6.6, notre calcul de similarit est trs proche de lalgorithme de Zhang : O(|T1 ||T2 |h1 h2 ) [120] (|T1 | et |T2 | sont respectivement les tailles des arbres T1 et T2 , tandis que h1 et h2 representent leurs hauteurs respectives). En eet, le temps de calcul de la similarit entre deux arbres de tailles |T1 | et |T2 | variables, augmente de faon quasi-quadratique avec la taille des arbres (de chaque arbre). Dans le second cas, cependant, comme illustr par la FIGURE 6.7, avec h = 1, notre algorithme de calcul de la similarit se comporte comme lalgorithme de [20, 27, 74, 94], cest--dire avec une complexit temporelle de O(N 2 ). En eet, le temps de calcul de la similarit entre deux arbres de tailles |T1 | et |T2 | variables, augmente de faon quasi-linaire avec la taille des arbres (de chaque arbre). En vertu de cette exprimentation et conformment aux rsultats obtenus dans tous les tests prcdents, on peut dire que la mesure de similarit propose est able. Tou111

Chapitre 6. Exprimentation tefois, le calcul de la similarit requiert une complexit temporelle leve, quand on a faire des arbres XML de grandes tailles, mais globalement lapproche est pertinente particulirement, puiquelle permet un clustering de qualit.

112

Conclusion gnrale
1 Mthode propose vs. tat de lart

Par rapport certaines mthodes voques dans ltat de lart, notre proposition se dmarque par un certain nombre de points importants. En eet, tout comme dans [27], et contrairement [12, 37, 72, 74], qui reprsentent structurellement des documents XML par leurs arbres XML originaux, dans notre approche un document XML est reprsent par une structure de rsum darbre enracin tiquet et ordonn. Cependant, notre rsum darbre est compltement dirent de celui de [27]. En eet, dans notre cas, un rsum darbre est obtenu par limination uniquement des rptitions des nuds frres, et ajout dattributs ventuels, mais la hirarchie de la structure des documents est bien consrve et sans perte dinformation. En revanche, dans [27], outre llimination des rptitions des nuds frres, il est galement question de celle des nuds imbriqus, tel point que, la hirarchie de la structure peut tre compltement modie. Contrairement certaines mthodes comme [27,37,72,74], o un cluster est reprsent par un groupe de documents XML (structurellement similaires), dans notre cas, un cluster peut avoir seulement un seul reprsentant (centrode), comme dans [95] o un cluster est reprsent par un sous-arbre frquent maximal. Cependant, si dans [95], un document XML peut apparaitre dans plusieurs clusters, dans le cas de notre approche un document nappartient qu un et un seul cluster. Alors que des mthodes comme [24, 27, 37, 74] eectuent un clustering bas sur une technique classique de classication hirarchique ascendante ou descendante, notre mthode tout comme [72], eectue un clustering incremental. Cependant, la dirence entre notre mthode et celles de [72] apparait au niveau des critres employs pour mesurer les similarits. En eet, notre clustering sappuie sur la similarit entre le centrode et la structure de rsum darbre du document XML classer, alors que le clustering de [72] est bas sur la notion de path (chemin) prenant en considration dirents critres comme le nombre de nuds communs entre larbre representant un document XML classer et les arbres du cluster considr, le nombre de nuds communs des chemins, ainsi que lordre des nuds de larbre du document XML classer. Comparativement la distance ddition telle quelle est dnie dans [24, 27, 37, 74], notre mesure de similarit, se distingue par le fait quelle prend en considration la hierarchie de la structure XML. En eet, avec la distance dedition, mis part, lordre qui est respect (les nuds des structures comparer sont visits en prordre), dans la comparaison des structures arborescentes, on ignore compltement la notion de contexte 113

Conclusion gnrale hierarchique des nuds. Notre mesure de similarit est quelque peu inspire de celles de Mong [57] et Madhavan [62], la dirence que dans ces dernres, au lieu de documents XML, on compare plutt leurs DTDs. Dans notre cas, les matching darbres sont relativement allgs du fait que nous manipulons des nuds darbres simples. Contrairement, les nuds dun arbre DTD dnotent souvent des expressions rgulires dont le traitement nest pas toujours trivial. Rappelons que notre clustering est caractris par la mobilit des centrodes du fait que ces derniers peuvent tre variables. En eet, mme si initialement la cration dun cluster, cest le premier arbre qui se prsente qui possde le statut de centrode, il doit tre remplac, si cest ncessaire, par un autre arbre plus reprsentatif parmi les autres arbres du cluster. Notre algorithme de clustering met bien laccent sur ce point travers le calcul de la fonction weight(Tik ) (FIGURE 5.5 Algorithme de clustering), qui mesure le poids de chaque arbre du cluster. Cette mobilit garantit la pertinence du nouveau centrode calcul. Enn, nous rappelons galement que notre clustering est dynamique dans le sens o il peut tout moment, traiter de nouveaux documents XML.

Conclusion et perspectives

Nous avons propos une manire de reprsenter structurellement des documents XML. Nous avons particulirement montr comment extraire la structure de chaque document XML classer. Nous avons galement propos une mesure de similarit ecace, ensuite nous avons dvelopp un algorithme de clustering permettant de regrouper ces structures dans des clusters. Le problme de la classication structurelle de documents XML est quivalent au problme de la classication de structures arborescentes [57, 27]. De ce fait, notre approche ne sapplique pas quaux documents XML, mais tous les documents semi-structurs. Les clusters sont crs au fur et mesure que les documents se prsentent. En dautres termes, notre clusetring est incrmental, cest--dire quil reste ouvert et peut traiter de nouveaux documents. Notre approche touche deux aspects fondamentaux intresants de la Recherche dInformation. En eet, dune part, le clustering permet de rduire le nombre de documents traits et, du coup, augmenter le nombre de documents pertinents qui peuvent tre retourns par un moteur de recherche. Dautre part, les clusters constituent un index permettant aux utilisateurs daccder aux groupes de documents XML quils souhaitent interroger et atteindre les units dinformation qui les intressent. Lexprimentation mene a permis de tester la faisabilit, voire, la abilit de lapproche propose. Pour un passage lchelle, il serait judicieux dtablir des tests sur de plus grandes collections de documents. Nanmoins, notre approche a donn des rsultats concluants comme en tmoignent les nombreux tests raliss sur les collections XML utilises. Nous avons ce titre, eectu plusieurs tests pour valuer la performance de lalgorithme de clustering propos ainsi que la abilit du modle de reprsentation et de la mesure de similarit choisis. Il serait intressant dans une recherche future, damliorer notre mthodologie et de 114

2. Conclusion et perspectives proposer dautres mesures de calcul de la similarit an daccrotre les performances de notre algorithme de clustering.

115

Publications dans le cadre de la thse

Ce travail de thse a donn lieu des publications dans des confrences et revue internationales : Article de revue : [7] Atelhadj, A, Boughanem M, Mezghiche M, Souam F. Using Structural Similarity for Clustering XML Documents. Knowledge and Information Systems, An International Journal, ISSN : 0219-1377 (printed version), ISSN : 0219-3116 (electronic version) by Springer, Vol. 32 Issue 1, pages 109139, DOI 10.1007/s10115-011-04215, 1 July 2012 (Online First May 27, 2011). Articles de confrences : [6] Atelhadj A, Souam F, Mezghiche M. XML Documents Clustering Based on Structural Similarity. In Proceedings of the Internatonal Conference IADIS, WWW/Internet, ISBN : 978-972-8924-93-5, Rome, Italy, 1922 November, pages 559566, (2009) [5] Atelhadj A, Mezghiche M, Souam F. RI structure, RI et XML, RI prcise. Dans, Actes de la 6me Confrence en Recherche dInformation et Applications Coria2009, ISBN : 2-9524747-1-0, Presqule de Giens, France, 57 mai, pages 301317, (2009)

117

Bibliographie
[1] Abiteboul S. Quering semi-structured data. In proceedings of the 6th International Conference on Data Base Theory, IDT97, Delphi, Greece, 810 January, pages 118, (1997) [2] Agrawal R, Srikant R. Fast algorithms for mining association rules in large databases. In Proceedings of the 20th International Conference on Very Large Data Bases, VLDB94, Santiago, Chile, 1215 September, pages 487499, (1994) [3] Atelhadj A, Boughanem M. CSDX : Classication Structurelle de Documents XML. Colloque VSST2006, Veille Scientique, Stratgique et Technologique, Tlcom Lille 1, France, 1617 Janvier, (2006) [4] Atelhadj A. Classication de documents semi-structurs XML selon la thorie des langages. Mmoire de Magister, Universit Mouloud Mammeri de Tizi-Ouzou, (2006) [5] Atelhadj A, Mezghiche M, Souam F. Classication de Structures Arborescentes : Cas de Documents XML. Dans, Actes de la 6eme Confrence en Recherche dInformation et Applications Coria2009, Presqule de Giens, France, 57 Mai, pages 301317, (2009) [6] Atelhadj A, Souam F, Mezghiche M. XML Documents Clustering Based on Structural Similarity. In Proceedings of the Internatonal Conference IADIS WWW/Internet, Rome, Italy, 1922 November, pages 559566, (2009) [7] Atelhadj A, Boughanem M, Mezghiche M, Souam F. Using Structural Similarity for Clustering XML Documents. Knowledge and Information Systems, Online First 27 May, (2011) [8] Alishahi M, Nagibzadeh M, Shakeri Aski B. Tag Name Structure-based Clustering of XML Documents. International Journal of Computer and Electrical Engineering, (Journal of IACSIT : International Association of Computer Science and Information Technology), 2(1) : 119126, (2010) [9] Anderson J, Prez-Carballo J. The nature of indexing : how humans and machines analyze messages and texts for retrieval : part ii : machine indexing, and the allocation of human versus machine eort. Information Processing and Management, 37(2) : 255277, (2001) [10] Asai T, Abe K, Kawasoe S, Arimura H, Sakamoto H, Arikawa S. Ecient substructure discovery from large semi-structured data. In Proceedings of the 2nd SIAM International Conference on Data Mining, Arlington, Virginia, VA, USA, 1113 April, pages 158174, (2002) 119

Bibliographie [11] Balpe J.P, Lelu A, Saleh I. Hypertextes et Hypermdias : Ralisations, outils et mthodes. Paris Hermes, (1995) [12] Bertino E, Guerrini G, Mesiti M. A Matching Algorithm for Measuring the Structural Similarity between an XML Document and a DTD and its Applications. Information Systems 29(1) : 2346, (2004) [13] Bertino E, Guerrini G. Measuring the structural similarity among XML documents and DTDs. Journal of Intelligent Information Systems, 30(1) : 5592, (2008) [14] Bouchachia A, Hassler M. Classication of XML Documents. In Proceedings of the IEEE Symposium on Computational Intelligence and Data Mining, CIDM2007, Honolulu, Hawaii, USA, 15 April, pages 390396, (2007) [15] Boukhors A, Kaszycki A, Laplace J, Munerot S, Poublan L. XML, la synthse. Intgrer XML dans vos architctures. Dunod Paris, (2002) [16] Candillier L, Tellier I, Torre F. Transforming XML trees for Ecient Cassication and Clustering. In Proceedings of the 4th Internatioinal Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2005, Dagstuhl Castle, Germany, 2830 November, pages 469480, (2005) [17] Carriere S, Kazman R. Webquery : Searching and Visualizing the Web through Connectivity. In Proceedings of the 6th International World Wide Conference, Santa Clara, CA, USA, 711 April, pages 701711, (1997) [18] Castano S, De Antonellis V, De Capitani di Vimercati S. Global Viewing of Heterogeneous Data Sources. IEEE Transactions on Knowledge and Data Engineering, IEEE TKDE, 13(2) : 277297, (2001) [19] Chakrabarti S. Integrating the document object model with hyperlinks for enhanced topic distillation and information extraction. In Proceedings of the Tenth International World Wide Web Conference WWW01, Hong-Kong, China, 15 may, pages 211220, (2001) [20] Chawathe, S. Comparing hierarchical data in external memory. In Proceedings of the 25th International Conference on Very Large Data Bases, VLDB 1999, Edinburgh, Scotland, UK, 710 September, pages 90101, (1999) [21] Cline M. Utilizing HTML Structure and Linked pages to improve Learning for text categorization. Undergraduate Honors Thesis, Department of Computer Sciences University of Texas, Austin, Texas, (1999). [22] Cobena G, Abiteboul S, Marian A. Detecting changes in XML documents. In Proceedings of the 18th International Conference on Data Engineering, ICDE 2002, San Jose, California, 26 February 1 March, pages 4152, (2002) [23] Cooper B.F, Sample N, Franklin M.J, Hjaltason G.R, Shadmon M. A Fast Index for Semi-Structured Data. In Proceedings of the 27th International Conference on Very Large Data Bases, VLDB 2001, Roma, Italy, 1114 September, pages 341350, (2001) [24] Costa G, Manco R, Ortale R, Tagarelli A. A Tree-Based Approach to Clustering XML Documents by Structure. In Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD 2004, Pisa, Italy, 2024 September, pages 137148, (2004) 120

[25] Cui J, Liu H, He J, Li P, Du X, Wang P. TagClus : a random walk-based for tag clustering. Knowledge and Information Systems, 27(2) : 193225, (2011) [26] Crouzet T. Je cre mon site Web (du dbutant lexpert). Microsoft press, la maison ddition microsoft, (2001) [27] Dalamagas T, Cheng T, Winkel K-J, Sellis T.K. A methodology for clustering XML documents by structure. Information Systems, 31(3) : 187228, (2006) [28] Del Razo Lopez, F. Recherche de sous-structures arborescentes ordonnes frquentes au sein de bases de donnes semi-structures. Thse de Doctorat, Universit de Montpellier II, (2007) [29] Demaine E.D, Mozes S, Rossman B, Weimann O. An Optimal Decomposition Algorithm for Tree Edit Distance. ACM Transactions on Algorithms, 6(1) : 2 :12 :19, (2009) [30] Denoyer L. Apprentissage et infrence statistique dans les bases de documents structurs : Application aux corpus de documents textuels. Thse de Doctorat, Universit Paris 6, (2004) [31] Doan A, Domingos P, Halevy A. Reconciling Schemas of Disparate Data Sources : a machine-Learning approach. In Proceedings of the 2001 ACM SIGMOD International Conference on Management Data, Santa Barbara, CA, USA, 2124 May, pages 509 520, (2001) [32] Doucet A, Lehtonen, M. Unsupervised classication of text-centric XML document collections. In Proceedings of the 5th Internatioinal Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2006, Dagstuhl Castle, Germany, 1720 December, pages 497509, (2006) [33] Dumais S, Chen H. Hierarchical Classication of Web Content. In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Athens, Greece, 2428 July, pages 256263, (2000) [34] Either K, Housser A. XML Web Tr@ining autoformation en 30 sessions. OEM Edition, (2000) [35] Ester M, Kriegel H-P, Sander J, Xu X. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, KDD 1996, Portland, Oregon, OR, USA, 24 August, pages 226231, (1996) [36] Flesca S, Manco G, Masciari E, Pontieri L, Pugliese A. Fast Detection of XML Structural Similarity. IEEE Transaction, Knowledge and Data Engineering. 17(2) : 160 175, (2005) [37] Francesca, F. D., Gordano, R., Ortale, R., Tagarelli, A. Distance-based Clustering of XML Documents. In Proceedings of the First International Workshop on Mining Graphs, Trees and Sequences, MGTS 2003, Cavtat-Dubrovnik, Croatia, 2226 September, pages 7578, (2003) [38] Furnas G.W, Landauer T.K, Gomez L.M, Dumais S.T. The Vocabulary Problem in Human-System Communication : an analysis and a solution. Communication of the ACM, 30(11) : 964971, (1987) 121

Bibliographie [39] Garcia-Solaco M, Saltor F, Castellanos M. A structure-based schema integration methodology. In Proceedings of the 11th International Conference on Data Engineering, ICDE95, Taipei, Taiwan, 610 March, pages 505512, (1995) [40] Garofalakis M, Gionis A, Rastogi R, Seshadri S, Shim K. XTRACT : A system for extracting document type descriptors from XML documents. In Proceedings of the ACM SIGMOD00 International Conference on Management of Data, Dallas, Texas, USA, 1618 May, pages 165176, (2000) [41] Hagenbuchner, M, Sperduti A, Tsoi A.C, Trentini F, Scarselli F, Gori, M. Clustering XML documents using self-organizing maps for structures. In Proceedings of the 4th Internatioinal Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2005, Dagstuhl Castle, Germany, 2830 November, pages 481496, (2005) [42] Hu G, Hammad R. Querying and Indexing XML Documents. Computational Methods in Science and Enginnering, Publisher IOS Press, 2005, 5(1) : 219233, (2005) [43] Hunter D et al. Initiation XML. Traduction Franaise : Lemainque F., Adam, L., Raspaud C. Wrox Press Edition Eyrolles, (2001) [44] Hwang JH, Ryu KH. A weighted common structure based clustering technique for XML documents. Journal of Systems and Software, JSS, 83(7) : 12671274, (2010) [45] Jain A.K, Dubes R.C. Algorithms for Clustering Data. Prentice-Hall advanced reference series : Computer Science, Prentice-Hall, Inc, Upper Saddle River, NJ, New Jersey, (1988) [46] Jeong B, Lee D, Cho H, Lee J. A novel method for measuring semantic similarity for XML schema matching. Expert Systems with Applications : An International Journal, 34(3) : 1642-1650, (2008) [47] Jiang H, Lu H, Wang W, Ooi B.C. XR-Tree : Indexing XML Data for Ecient Structural Joins. In Proceedings of the 19th International Conference on Data Engineering ICDE 2003, Bangalore, India, March 58, pages 253263, (2003) [48] Joachims T. Text Categorization with Support Vector Machines : Learning with many Relevant Features. In proceedings of the 10th European Conference on Machine Learning ECML-98, Chemnitz, Germany, April 2124, pages 137142, (1998) [49] Kashyap V, Sheth A. Semantic and Schematic Similarities between Database Objects : a Context-Based Approach. VLDB Journal, 5(4) : 276304, (1996) [50] Kc M, Hagenbuchner M, Tsoi A, Scarselli F, Gori M, Sperduti A. XML document mining using contextual self-organizing maps for structures. In Proceedings of the 5th Internatioinal Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2006, Dagstuhl Castle, Germany, 1720 December, pages 510524, (2006) [51] Kilpelinen P. Tree Matching Problem with Applications to Structured Text Databases. Phd Thesis, Department of Computer Science, University of Helsinki, Finland, November 1992. Rapport A-1992-6, (1992) [52] Klein, P.N. Computing the edit-distance between unrooted ordered trees. In Proceedings of the 6th Annual European Symposium on Algorithms ESA98, Venice, Italy, 2426 August, pages 91102, (1998) 122

[53] Kleinberg J.M. Authoritative Sources in a Hyperlinked Environment. Journal of the ACM, 46(5) : 604632, (1999) [54] Kutty S, Tran T, Nayak R, Li Y. Clustering XML Documents Using Frequent Subtrees. In Proceedings of the 7th International Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2008, Dagstuhl Castle, Germany, 1518 December, pages 436445, (2008) [55] Kutty S, Nayak R, Li Y. HCX : an ecient hybrid clustering approach for XML documents. In Proceedings of the 2009 ACM Symposium on Document Engineering, Munich, Germany, 1618 September, pages 9497, (2009) [56] Larsen B, Aone C. Fast and eective text mining using linear-time document clustering. In Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD 1999, San Diego, California, CA, USA 1518 August, pages 1622, (1999) [57] Lee M.L, Yang L.H, Hsu W, Yang X. XClust Clustering XML Schemas for Eective Integration. In Proceedings of the 11th International Conference on Information and Knowledge Management, ACM CIKM 2002, Mclean, Virginia, USA, 49 November, pages 292299, (2002) [58] Lewis D. The TREC-4, Filtering Track. In Proceedings of the 4th Text Retrieval Conference, TREC-4, National Institute of Standards and Technology NIST, Special Publication SP 500-263, Gaithersburg, MD Maryland, USA, 13 November, pages 165180, (1996) [59] Li Q, Moon B. Indexing and Querying XML Data for Regular Path Expressions. In Proceedings of the 27th International Conference on Very Large Data Bases, VLDB 2001, Roma, Italy, 1114 September, pages 361370, (2001) [60] Lodhi H, Saunders C, Shawe-Taylor J, Cristianini N, Watkins C. Text Classication using String Kernels. Machine Learning Research (Journal of), 2 (2002) : 419444, (2002) [61] MacLaughlin B. Java et XML. Edition Oreilly, (2002) [62] Madhavan J, Bernstein A.P, Rahm E. Generic Schema Matching with Cupid. In Proceedings of the 27th International Conference on Very Large Data Bases, VLDB 2001, Roma, Italy, 1114 September, pages 4958, (2001) [63] Maniez J. A decade of research in classication. International Classication Journal, 18(2) : 7377, (1991) [64] Maron M, Kuhns J. On relevance, probabilistic indexing and information retrieval. Journal of the Association of Computing for Machinery JACM, 7 : 216244, (1960) [65] Meier W. An Open Source Native XML Database. In Proceedings of the Web, WebServices, and Database Systems, NODe 2002 Web and Database-Related Workshops, Erfurt, Germany, 710 October, pages 169183, (2002) [66] Michard, A. XML, langages et applications. Edition Eyrolles, (2000) [67] Miller W, Myers E. A le comparison program. Software-Practice and Experience. 15(11) : 10251040, (1985) 123

Bibliographie [68] Milo T, Zohar S. Using Schema Matching to Simplify Heterogeneous Data Translation. In Proceedings of the 24rd International Conference on Very Large Data Bases, VLDB98, New York City, New York, USA, 2427 August, pages 122133, (1998) [69] Myers E. An O(N D) dierence algorithm and its variations. Algorithmica, 1(2) : 251 266, (1986) [70] Nayak R, Xu S. XML documents clustering by structures. In Proceedings of the 4th Internatioinal Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2005, Dagstuhl Castle, Germany, 2830 November, pages 432442, (2005) [71] Nayak R, Tran T. A Progressive Clustering Algorithm to Group the XML Data by Structural and Semantic Similarity. International Journal of Pattern Recognition and Articial Intelligence, IJPRAI, 21(4) : 723743, (2007) [72] Nayak R. Fast and eective clustering of XML data using structural information. Knowledge and Information Systems, 14(2) : 197215, (2008) [73] Ng P.K.L, Ng, V.T.Y. RRSi : indexing XML data for proximity twig queries. Knowledge and Information Systems, 17(2) : 193216, (2008) [74] Nierman A, Jagadish H.V. Evaluating Structural Similarity in XML Documents. In Proceedings of the Fifth International Workshop on the Web and Databases WebDB 2002, Madison, Wisconsin, USA, 67 June, pages 6166, (2002) [75] Page L, Brin S, Motwani R and Wiograd T. The Pagerank Citation Ranking : Bringing Order to the Web. Technical report, Stanford Digital Library Technologies Project, (1998) [76] Patnaik D, Laxman S, Ramakrishnan R. Discovering excitatory relationships using dynamic Bayesian networks. Knowledge Information Systems, Online First, 24 September, (2010) [77] Ptzner D, Leibbrandt R, Powers D. Characterization and evaluation of similarity measures for pairs of clusterings. Knowledge and Information Systems, 19(3) : 361 394, (2009) [78] Picard J, Savoy J. Searching and Classifying the Web using Hyperlinks : A Logical Approach. In Proceedings of the 23rd BCS-IRSG European Colloquium on Information Retrieval Research, ECIR 2001, Darmstadt, Germany, 46 April, pages 110, (2001). [79] Planetoscope-Statistiques. Nombre demails envoys dans le monde. http ://www.planetoscope.com/insolite/1024-Nombre-d-emails-envoyes-dans-lemonde.html, 16 Avril, (2011) [80] Polovici E, Menier G, Marteau P.F. SIRIUS : A lightweight XML indexing and Approximative SeaRch System at INEX 2005. In Proceedings of the 4th Internatioinal Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2005, Dagstuhl Castle, Germany, 2830 November, pages 321335, (2005) [81] Quek C.Y. Classication of WWW Documents. Senior Honors Thesis, School of Computer Science, Carnegie Mellon University CMU, (1997) [82] Rahm E, Bernstein P.A. A Survey of Approaches to Automatic Schema Matching. In VLDB Journal, 10(4) : 334350, (2001) 124

[83] Robertson S. The probability ranking principle in IR. Journal of documentation, 33(4) : 294304, (1997) [84] Roussey C. Une mthode dindexation smantique adapate aux corpus multilingues. Thse de Doctorat, Institut National des Sciences Appliques de Lyon,INSA, (2001) [85] Sauvagnat K. Modle exible pour la Recherche dInformation dans des corpus de documents semi-structurs. Thse de Doctorat, Universit Paul Sabatier de Toulouse, (2005) [86] Sebastiani F. Machine Learning in Automated Text Categorization. ACM Computing Surveys, 34(1) : 147, (2002) [87] Selkow S. The tree-to-tree editing problem. Information Processing Letters, 6(6) : 184 186, (1977) [88] Sokal R.R. Numerical Taxonomy. W.H Freeman and Company editor, 660 Market, San Francisco, California, 94105, (1963), Reprinted by Scientic American, December 1966, 215(6) : 106116,(1966) [89] Song L, Ma J, Lei J, Zhang D, Wang Z. Semantic structural similarity measure for clustering XML documents. In Proceedings of the International Conference on Web Information Systems and Mining WISM09, Shanghai, China, 78 November, Pages 232241, (2009) [90] Su H, Padmanabhan S. Identication of Syntactically Similar DTD Elements in Schema Matching across DTDs. In Proceedings of the 2th International Conference on Web-Age Information Management, WAIM 2001, Xian, China, 911 July, pages 145159, (2001) [91] Tai, K.C. The tree-to-tree correction problem. Journal of the Association of Computing for Machinery JACM, 26 : 422433, (1979) [92] Takahashi K, Takamura H, Okumura M. Direct estimation of class membership probabilities for multiclass classication using multiple scores. Knowledge and Information Systems, 19(2) : 185210, (2009) [93] Tebri, H. Formalisation et spcication dun systme de ltrage incrmental information. Thse de Doctorat, Universit Paul Sabatier, Toulouse, (2004) [94] Tekli J, Chbeir R, Yetongnon K. Ecient XML Structural Similarity Detection using Sub-tree Commonalities. In Proceedings of the 22nd Brazilian Symposium on Databases, SBBD 2007, Joao Pessoa, Paraiba, Brasil, 1519 October, Pages 116130, (2007) [95] Termier A. Extraction darbres frquents dans un corpus htrognes de donnes semistructures : Application la fouille de documents XML. Thse de Doctorat, Universit Paris Sud 11 Orsay, (2004) [96] Thang HQ, Nam VS. XML Schema Automatic Matching Solution. International Journal of Electrical, Computer, and Systems Engineering 4(1) : 6874, (2010) [97] Tran T, Nayak R. Evaluating the Performance of XML Document Clustering by Structure Only. In proceedings of the 5th Internatioinal Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2006, Dagstuhl Castle, Germany, 1720 December, pages 473484, (2006) 125

Bibliographie [98] Tran T, Nayak R, Bruza P. Combining Structure and Content Similarities for XML Document Clustering. In Proceedings of the Seventh Australasian Data Mining Conference, AusDM 2008, Glenelg/Adelaide, SA, Australia, 2728 November, pages 219 226, (2008) [99] Tran T, Kutty S, Nayak R. Utilizing the Structure and Content Information for XML Document Clustering. In Proceedings of the 7th International Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2008, Dagstuhl Castle, Germany, 1518 December, pages 460-468, (2008) [100] Turenne N. Apprentissage statistique pour lextraction de concepts partir de textes. Application au ltrage dinformations textuelles. Thse de Doctorat, Universit Louis-Pasteur Strasbourg, (2000) [101] Van Rijsbergen J.C. Information retrieval. Butterworths, London 2me edition, (1979) [102] Vercoustre A.M, Fegas M, Gul S, Lechevallier Y. A exible structured-based representation for XML document mining. In Proceedings of the 4th Internatioinal Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2005, Dagstuhl Castle, Germany, 2830 November 2005, pages 443457, (2005) [103] Vercoustre A.M, Fegas M, Lechevalier Y, Despeyroux. Classication de documents XML partir dune reprsentation linaire des arbres de ces documents. Dans Actes des siximes journes Extraction et Gestion des Connaissances, EGC2006, Lille 1, France, 1720 Janvier, pages 433444, (2006) [104] Watkins C. Dynamic Alignment Kernels. Advances in Large Margin Classiers, pages 3950, (1999) [105] Wang J, Zhang K, Jeong, K, Shasha D. A system for approximate tree matching. IEEE Transaction and Knowledge and Data Engineering, 6(4) : 559571, (1994) [106] Wang C, Yuan Q, Zhou H, Wang W, Shi B. Chopper : An ecient algorithm for tree mining. Journal of Computer Science and Technology, 19 : 309-319, (2004) [107] Wang H, Wang W, Li J, Lin X, Wong R. Practical Indexing XML Documents for Twig Query. In Proceedings of the 10th Asian Computing Science Conference, ASIAN 2005, Data Management on the Web, Kunming, China, 79 December, pages 208 222, (2005) [108] White H, MCCain K. Bibliometrics. Annual review of information Science and Technology, 24 : 119165, (1989) [109] Williams K , Brundage M , Dengler P , Gabriel J. XML et les bases de donnes. Traduction Franaise : Lemainque, F et al. Edition Eyrolles, (2001) [110] Wisniewsky G, Denoyer L, Gallinari P. Classication automatique de documents structurs : Application au corpus darbres tiquets de type XML. Dans Actes de la 2eme Confrence en Recherche dInformation et Applications, CORIA 2005, Grenoble, France, 911 Mars, pages 167184, (2005) [111] Wu S. An O(NP) sequence comparison algorithm. Information Processing Letters, 35 : 317323, (1990) 126

[112] Xing G, Xia Z, Guo J. Clustering XML Documents Based on Structural Similarity. In Proceedings of the 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, 912 April, pages 905911, (2007) [113] Yang Y, Slattery S, Ghani R. A Study of Approaches to Hypertext Categorization. Journal of Intelligent Information Systems JIIS, 18(2-3) : 219241, (2002) [114] Yang J, Chen X. A Semi-Structured Document Model for Text Mining. Computer Science and Technology (Journal of), 17(5) : 603-610, (2002) [115] Yang J, Cheung W.K, Chen X. Learning element similarity matrix for semistructured document analysis. Knowledge and Information Systems, 19(1) : 5378, (2009) [116] Yi J, Sundaresan N. A Classier for Semi-Structured Documents. In Proceedings of the 6th ACM SIGKDD, International Conference on Knowledge Discovery and Data Mining, Boston, MA, USA. ACM, 2023 August, pages 340344, (2000) [117] Yong S.L, Hagenbuchner M, Tsoi A.C, Scarselli F, Gori M XML document mining using graph neural network. In Proceedings of the 5th Internatioinal Workshop of the INitiative for the Evaluation of XML Retrieval, INEX 2006, Dagstuhl Castle, Germany, 1720 December, pages 458472, (2006) [118] Yoon J.P. et a. BitCube : A Three-Dimensional Bitmap Indexing for XML Documents. Journal of Intelligent Information Systems, JIIS, 17(2-3) 241254, (2001) [119] Zaki M J. Ecient mining frequent trees in a forest. In Proceedings of the 8th ACM SIGKDD, International Conference on Knowledge Discovery and Data Mining, KDD 2002, Edmonton, Alberta, Canada, 2326 July, pages 7180, (2002) [120] Zhang, K., Shasha, D. Simple fast algorithms for the editing distance between trees and related problems. Journal on Computing, Published by the Society for Industrial and Applied Mathematics SIAM 18(6) : 12451262, (1989) [121] Zhao Y, Karypis G. Criterion Functions for Document Clustering : Experiments and Analysis. Technical Report, 0140, Department of Computer Science, University of Minnesota, Minneapolis, MN 55455, (2001) [122] Zhou Y, Cheng H, Xu Yu J. Graph Clustering Based on Structural/Attribute Similarities. In Proceedings of the 35th International Conference on Very Lage Data Bases VLDB Endowment, Lyon, France, 2428 August, 2(1) : pages 718729, (2009)

127