Algorithmes pour le Traitement de Données

Introduction Indexation, Représentation Vectorielle L’algorithme des k plus proches voisins (RI et catégorisation) Evaluation Ouvrages de référence

Algorithmes pour le Traitement de Données

Eric Gaussier, Olivier Aycard

Université J. Fourier/Grenoble 1UFR-IM2AG

Informatique, Mathématiques et Mathématiques Appliquées de [email protected], [email protected]

Eric Gaussier, Olivier Aycard Algorithmes pour le Traitement de Données 1


Table des matières

1 Introduction

2 Indexation, Représentation Vectorielle

3 L’algorithme des k plus proches voisins (RI etcatégorisation)

4 Evaluation

5 Ouvrages de référence



Objectifs du cours

L’objectif de cours est d’introduire les principaux modèles etalgorithmes utilisés en Traitement des Données

Nous nous intéresserons en particulier à :

L’indexation et la représentation des documentsLa recherche d’information (RI), y compris la RI sur le WebLa catégorisation et la classification (clustering)La fouille de données



Domaines d’applications (1)

La recherche d’information (RI), y compris la RI sur le Web

Indexation des requêtes et des documents

Appariement entre requêtes et documents (ou entre documents)



Domaines d’applications (2)La catégorisation

Binaire vs multi-classe, mono- vs multi-label

Hiérarchique ou à plat

Formalisation données étiquetées : (x (i), y (i)), 1 ≤ i ≤ n avecx ∈ Rp, y ∈ Y Y = {−1; +1} ; trouver une fonction f , de Rp

dans Y qui à x associe y avec le moins d’erreurs possibles



Domaines d’applications (3)

La classification (clustering)

Partitionnement vs affectation souple

Hiérarchique ou à plat



Table des matières

1 Introduction



4 Evaluation




Etapes de l’indexation textuelle

1 Segmentation

Découper un texte en mots :

l’information donne sens à l’espritl’, information, donne, sens, à, l’, esprit

soit 7 mots mais seulement 6 types ; nécessité d’un dictionnaire(au moins léger) pour certains mots ou expressions

2 Filtrage par un anti-dictionnaire des mots vides3 Normalisation

De la casse, des formes fléchies, des familles lexicalesLemmatisation, racinisation

→ Sac-de-mots : inform, don, sens, esprit



Représentation vectorielle des docs (1)

L’ensemble des types forme le vocabulaire d’une collection. SoitM la taille de ce voc., et soit N le nombre de doc. dans lacollection C. On considére l’espace vectoriel à M dimensions(RM ), dans lequel chaque axe correspond à un type

Chaque document est alors représenté par un vecteur de RM decoordonnées :

Présence/absence ou nbre d’occurrences du type dans le doc. :xi(di) = tfdiNombre d’occurrences normalisé par la long. du doc. :

xi =tfd

i∑Mi=1 tfd

i

Le tf*idf :xi =

tfdi∑M

i=1 tfdi

logNdfi︸︷︷︸

idfi

où dfi représente la fréquence documentaire du mot i :dfi =

∑d∈C 1{i ∈ d}



Représentation vectorielle des docs (2)

La représentation vectorielle adoptée permet d’avoirdirectement accès aux outils mathématiques associés :distances, similarités, réduction de dimensions, ...

Exercices

Chaque document est représenté par un tableau à Mdimensions contenant les poids (coordonnées) des termes(types, mots) ; écrire un algorithme qui calcule le produit scalaireentre 2 documents

Quelle est la complexité d’un algorithme qui calcule le produitscalaire entre un document et tous les autres documents de lacollection ?



Une représentation creuse !

La majorité des termes de la collection n’apparaissent pas dansun document donné ; chaque document a donc la majeurepartie de ses coordonnées nulles ; un gain d’espace peut êtreobtenu en ne représentant pas ces coordonnées nulles

Exemple de représentation creuse :

document d

int l (long. du doc. (types))TabTermes int[l] (indices des termes)TabPoids float[l] (poids des termes)· · ·

Reprendre l’exercice précédent avec cette représentation



Le fichier inverseIl est possible d’accélérer le calcul du produit scalaire, dans lecas de représentations creuses, en utilisant un fichier inverse,c’est-à-dire une structure qui fournit pour chaque termel’ensemble des documents dans lesquels il apparaît :

terme i

int l (nbre de docs assoc.)TabDocs int[l] (indices des docs)· · ·

Reprendre l’exercice précédent avec cette structure

Remarque Avantageux avec toute mesure (distance, similarité)qui ne fait pas intervenir les termes non présents dans undocumentProduit scalaire ?, cosinus ?, distance euclidienne ?



Construction du fichier inverse

Dans le cadre d’une collection statique, 3 étapes principalesrégissent la construction du fichier inverse :

1 Extraction des paires d’identifiants (terme, doc), passe complétesur la collection

2 Tri des paires suivant les id. de terme, puis les id. de docs

3 Regroupement des paires pour établir, pour chaque terme, laliste des docs

Ces étapes ne posent aucun probléme dans le cas de petitescollections oï tout se fait en mémoire

Quid des grandes collections ?



Cas de mémoire insuffisante

Il faut dans ce cas stocker des informations temporaires surdisqueTrois étapes :

1 Collecte des paires TermId-DocId et écriture dans un fichier

2 Lecture par blocs de ce fichier, inversion de chaque bloc etécriture dans une série de fichier

3 Fusion des différents fichier pour créer le fichier inversé

Algorithme associé : Blocked sort-based indexing (BSBI)



L’algorithme BSBI (1)

1 n← 0

2 while (tous les docs n’ont pas été traités)

3 do

4 n← n + 1

5 block← ParseBlock()

6 BSBI-Invert(block)

7 WriteBlockToDisk(block,fn)

8 MergeBlocks(f1, ..., fn ;fmerged)



L’algorithme BSBI (2)L’inversion, dans BSBI, consiste en un tri sur les identifiants determes (premiére clé) et les identifiants de documents(deuxiéme clé). Le résultat est donc un fichier inverse pour lebloc lu. Complexité en O(T log T ) oï T est le nombre de pairesterme-document (mais étapes de lecture et de fusion peuventêtre plus longues)

Exemple

t1 = "brutus", t2 = "caesar", t3 = "julius", t4 = "kill", t5 = "noble"

t1 : d1 t2 : d4 t2 : d1t3 : d10 t1 : d3 t4 : d8t5 : d5 t2 : d2 t1 : d7



Table des matières

1 Introduction



4 Evaluation




Les k plus proches voisins (kppv) (1)

L’idée sous-jacente est de faire reposer la classification d’unexemple sur la base de la classification des exemples proches,ce qui permet une modélisation fine de la frontière entreclasses (parfois trop fine) - Illustration au tableau.C’est une approche dite memory-based, ou fondée sur lamémoire. On parle aussi de lazy learning, c’est-à-dired’apprentissage paresseux car il n’y a pas d’apprentissageproprement dit : les exemples d’apprentissage sont simplementstockés et réutilisés lors de la classification.




Algorithme standardSoit un objet x à classer.

1 Déterminer Nk (x), l’ensemble des k plus proches voisins de x

2 Choisir la classe de x sur la base d’un vote majoritaire dansNk (x)



IllustrationExempleOn considère le jeu de données suivant :

No exple valeur att. 1 (x1) valeur att. 2 (x2) classe1 3 3 -2 4 3.8 -3 5 3 -4 6 3.5 -5 3 4 +6 4 4.2 +7 4 6 +8 6 5 +

k = 3, xT = (5,3.5)

Quelle est la classe de x ?




AméliorationsLe vote majoritaire est parfois remplacé par un vote majoritairepondéré par la distance (ou similarité) entreexemples/objets/éléments.Il est possible d’apprendre (malgré tout) certains éléments :

Seuil sur chaque classe - on utilise Nck (x), ensemble des voisins

de x dans la classe c et la distance (ou similarité) obtenue surNc

k (x)

Métrique complète (exemple avec la distance de Mahalanobis)




Implantation dans le cas de matrices creusesUtilisation du fichier (ou de la table) inverse




La malédiction des grandes dimensions (Curse ofdimensionality)

On suppose que l’on dispose uniformément des points dans unhypercube de côté 1 d’un espace vectoriel de dimension p defaçon à ce que, pour chaque point, il existe un voisin situé àune distance de 10−1.Combien faut-il de points pour réaliser cela dans un esapcevectoriel de dimension 1, 2, p ?




La malédiction des grandes dimensions (Curse ofdimensionality)

De manière générale, dans un espace vectoriel de grandedimension, la distance entre un point donné x et son point leplus proche dans un ensemble d’apprentissage est comparable(proche) de celle entre x et son point le plus éloigné dansl’ensemble d’apprentissage (malédiction des grandesdimensions).

En pratique, il n’est pas certain que nous soyons frappé parcette malédiction ! Les techniques de réduction de dimension etde sélection d’attributs permettent de s’en affranchir.



Table des matières

1 Introduction



4 Evaluation




Précision, rappel, F-mesure



Ensemble d’apprentissage, de validation etde tests



Validation croisée



Table des matières

1 Introduction



4 Evaluation




Ouvrages de référence

Recherche d’information : Applications, modèles et algorithmes -M.-R. Amini, E. Gaussier - Eyrolles, 2013

Introduction to Information Retrieval - C. Manning, P. Raghavan,H. Schütze - Cambridge Univ. Press, 2008


Documents

Algorithmes pour le Traitement de Données