Impact de la structure de treillis dans le domaine de fouille de données et la représentation des connaissances.

i

Table des matières

1 I 2	Introduction Cadre conceptuel et théorique Généralités sur la théorie des treillis 2.1 Origine de la théorie des treillis 2.2 Treillis ordinale et treillis algébrique 2.2.1 Définitions algébrique et ordinale d'un treillis 2.2.2 Irréductibles et générateurs minimaux d'un treillis 2.3 Treillis de fermés et système de fermeture 2.3.1 Treillis de fermés 2.3.2 Système de fermeture 2.4 Treillis des concepts et treillis de Galois 7		1 5 6 6 7 10 15 16 16 16
		2.4.1 Treillis des concepts	17
		2.4.2 Treillis de Galois	18
3	Aspects algorithmiques des treillis		19
	3.1	Algorithme de construction du graphe de couverture d'un treillis . . .	20
	3.2	Algorithme de construction de treillis de concepts	26
		3.2.1 Définitions	26
		3.2.2 Algorithme Genall	29
		3.2.3 Etude de la compléxité	35
	3.3	Algorithme de génération de treillis quelconques	35
		3.3.1 Algorithme de L.Nourine	36
		3.3.2 Etude de la compléxité	37
II	Application de la méthode		39
4	Fouille de données et navigation dans un treillis		40
	4.1	Bref aperçu sur les fouilles de données	40
		4.1.1 La fouille d'images	41
		4.1.2 La fouille de textes	41
		4.1.3 La fouille du web	42
	4.2	Chaîne d'extraction des connaissances	42
	4.3	L'Analyse Formelle des Concepts	44
		4.3.1 L'extraction de motifs fréquents	44
		4.3.2 Algorithme d'extraction des motifs fréquents	46
		4.3.3 Extraction de règles d'associations	48

ii

5	4.3.4 Règles d'association 4.3.5 Algorithme de génération de règles d'associations valides . . Application des treillis en représentation des connaissances et extraction d'informations			49 50 53
	5.1	Web sémantique et représentation des connaissances		53
		5.1.1	Web sémantique	53
		5.1.2	Représentation des connaissances	54
	5.2	Extraction d'informations		58
		5.2.1	Recherche d'informations	59
		5.2.2	Traitement automatique de la langue	60
	5.3	Application des règles d'associations aux textes		63
		5.3.1	Description du problème	63
		5.3.2	Expérimentations	65
		5.3.3	Extraction de connaissances par règles d'association	69
		5.3.4	Interprétation des résultats	73
6	Conclusion et perspectives			78

iii

Table des figures

2.1	Exemple de treillis	10
2.2	Exemple de treillis distributif et treillis booléen	11
2.3	Autre exemple de treillis	12
2.4	Treillis de la figure 2.3 où sont precisés, pour chaque noeud de x, les
	ensembles Jx et Mx 13
2.5	Treillis des concepts du contexte de la table 2.3	18
3.1	Arbre lexicographique de la famille F	24
3.2	le graphe de couverture G = (F, ?)	26
3.3	Arbre lexicographique associé au dictionnaire	28
3.4	Matrice decrivant la relation R du contexte K = (X, Y, R)	29
3.5	Treillis des concepts formels, extrait du contexte K, décoré par quelques
	générateurs minimaux	34
3.6	Un ordre qui ne représente pas un treillis 37
4.1	Chaîne d'extraction de connaissances	42
4.2	Exemple de treillis des parties ordonnées par inclusion	49
5.1	Exemple d'ontologie dans le domaine zoologique	54
5.2	Représentation graphique d'un ensemble classique et d'un ensemble
	flou	57
5.3	Schéma général de la recherche d'information	59
5.4	Représentation syntaxiques d'une phrase	62
5.5	Exemple d'un document du corpus	65
5.6	Treillis des concepts généré à partir du logiciel Concept Explorer 1.3	76

iv