Text mining

De EduTech Wiki
Aller à la navigation Aller à la recherche

Cet article est une ébauche à compléter. Une ébauche est une entrée ayant un contenu (très) maigre et qui a donc besoin d'un auteur.

Voir aussi:

Introduction

Le text mining est né d'une combinaison du "data mining", de l'analyse quantiative de textes et du traitement automatique du langage.

Les applications principales sont selon Tellier:

  1. La recherche d'information
    • Notamment les moteurs de recherche de type Google
    • Détection de plagiat.
  2. La classification de documents.
    • Tri de email (détection de SPAM)
    • Fouille d'opinions (évaluations positives ou négatives d'un produit, service, etc.)
    • Surveillance et détection de menaces (espionnage, etc.)
  3. L'annotation
    • L'annotation en elle-même sert plus à préparer des analyses. Notamment l'annotation de type "part of speech" qui identifie la nature morpho-syntaxique de chaque élément (token). Exemples:
    • Traduction automatique
    • Identification de zone thématiques (souvent basés sur la phrase comme unité de texte)
  4. Extraction d'Information
    • Définition: Extraire automatiquement de documents textuels des informations factuelles servant à remplir les champs d’un formulaire prédefini
    • Veille d'information basée par exemple sur les ”who did what, where and when, and why”
    • Bibliométrie (réseaux de citations)

Notions de base

Les données textuelles

On peut distinguer 3 grands types de textes:

(1) Tableaux composés de de lignes et colonnes
Il existe plusieurs types formats: texte où les champs (colonnes) sont séparés par un symbole spécifique (TAB, virgule, etc.), formats propriétaires comme Excel, structuration par balises XML, JSON, etc.
(2) Textes libres
Il s'agit d'un text brut sans formattage, souvent obtenu après un filtrage d'un document Web, Word, PDF, etc.
(3) Documents semi-structurés
Il existe tout une variété: pages web structurés (ou éléments de pages web comme tableaux, microformats), formats de syndication comme RSS, formats emails et similaire.

La fouille de texte s'intéresse principalement aux textes libres.

Préparation d'un corpus pour des analyses statistiques

Avant de pouvoir utiliser des méthodes quantitatives de fouille de textes, il faut préparer les documents. En règle générale, on passe à travers les étapes suivantes (pas forcément dans cet ordre précis):

Etapes pour préparer des documents non-structurés

Voici les étapes et filtres les plus importants qu'on utilise pour préparer un ensemble de documents non-structurés. Selon le type d'analyse, on peut ignorer un étape pour des raisons pratiques (pas nécessaire) ou théoriques (on ne veut pas filtrer cette information) et on peut changer l'ordre.

Extraire le corps du document
  • Nécessaire pour des pages web qui contiennent des menus et autres éléments non-reliés au contenu
Traduire en format texte brut (si nécessaire)
  • Il faut enlever des balises (textes HTML, XML, Latex, etc.)
  • Il faut traduire des documents Word, PDF, etc.
Mettre tous les mots en minuscules
Enlever Les ponctuations
Enlever les nombres
Enlever les blancs en trop
Remplacer des caractères
  • Typiquement des "@" ou encore des caractères que votre logiciel d'analyse ne comprend pas (par exemple des apostrophes français ou allemands)
Remplacer des mots
  • Il est parfois utile de remplacer des mots (par exemple des noms d'organisations par des acronymes) afin de préserver une identité à un terme composé.
Enlever les "stop words" (mots communs à tous les textes, comme les articles)
Racinisation (Angl.* Stemming)
  • «En linguistique, la racinisation ou désuffixation (anglais * stemming) est un procédé de transformation des flexions en leur radical ou racine (anglais: stem).» (Wikipédia, 20 oct. 2014).
  • Il existe 2 méthodes: Soit on utilise un dictionnaire (énorme) soit un algorithme. Les algorithmes diffèrent entre les langes. "Porter", les plus populaire pour l'Anglais ne marche pas très bien en français, et il tenter de travailler avec "Carry" ou encore un algorithme adaptable comme Paice/Husk.
Lématisation (alternative plus difficile au stemming)
  • «La lemmatisation désigne l'analyse lexicale du contenu d'un texte regroupant les mots d'une même famille. Chacun des mots d'un contenu se trouve ainsi réduit en une entité appelée lemme (forme canonique). La lemmatisation regroupe les différentes formes que peut revêtir un mot, soit * le nom, le pluriel, le verbe à l'infinitif, etc.» (Lemmatisation, 20 oct. 2014).
Enlever d'autres mots
  • Lorsqu'on analyse un domaine précis (par ex. des fiches sur le "jeu"), on peut enlever des termes comme "jeu" qui se retrouvent dans chaque document.

La racinisation et la lemmatisation

Lire

La racinisation (ou stemming) et la lemmatisation consistent à réduire une liste de mots à une liste plus courte qui ne contient qu'une variante du même mot. Le premier algorithme connu et toujours populaire est le Porter Stemming Algorithm (1979). Les librairies de R, utilisent l'implémentation Snowball qui a adapté l'algorithme Porter à d'autres langues, dont le français.

La racine correspond à la partie du mot qui reste, une fois qu'on a tué son préfixe et son suffixe. Contrairement à un lemme, il ne s'agit pas forcément d'un "vrai" mot.

Exemples:

recherche, chercher, cherches, cherchions, cherchait -> cherch

Il existe un indice de compression IC:

IC = (M - R) / M
M = nombre de mots uniques avant racinisation
R = nombre de racines uniques après racinisation

La lemmatisation cherche une forme canonique d'un mot. Le lemme est un mot de base, comme:

  • un verbe à l'infinitif
  • un adjectif, etc. au singulier masculin.

Exemples:

cherches, cherchions -> chercher
ai, as, a, eussions -> avoir
belles, bel, beaux, beau -> beau

Fréquence et poids de termes

La fréquence de termes (term frequency, tf)
la fréquence d'un terme iest basée sur l'importance proportionnelle d'un terme dans un document.
Donc pour un termei dans un documentj: la "term frequency" tfi,j = fonction de (ti, dj)
Plus précisément, on peut calculer tfi,j = frequencei,j / maxe freqj.
Autrement dit frequence de termei = nombre d’occurrences du terme ti dans le documentj / nombre d’occurrences du terme le plus fréquent dans le document dj
La fréquence inverse (Inverse of document frequency, idf)
Mesure la discrimination d'un terme dans le corpus
Un terme qui apparaît souvent dans le corpus est moins important (pour la discrimination) qu'un terme moins fréquent (TP, Approche basée sur tf*idf
idfi = log 10 (N / dfi)
N = nombre de documents dans le corpus
dfi = nombre de documents contnant le terme ti
Le poids d'un terme (termes pondérés)
Le "poids" d'un terme peut être calculé de façon différente.
Une méthode simple est TfIdf' (Salton). Il s'agit de la combinaison de term frequency et inverse of document frequency, autrement dit: la fréquence du terme dans un document pondéré par la fréquence du terme dans le corpus
fi,j = tfi,j X idfj

Les Matrices termes-documents

Les matrices termes-documents et documents termes résument les mots que l'on retrouve dans divers document d'un corpus.

Matrices documents-termes (Angl.
Document Term Matrix, DTM)
Chaque ligne d'une matrice DT représente un document, chaque colonne un terme (mot)
      Alpha Beta Creux
doc1  2     1    ....
doc2  1
doc3  2


Matrice termes-documents (Angl.
Term Document Matrix, TDM)
Chaque ligne d'une matrice TD représente un terme (mot), chaque colonne un document
        doc1 doc2 doc3
Alpha   2    1    2
Beta    1    0    3
Creux   0    1    0

A partir de ce type de matrice on peut effectuer plusieurs analyses.

Le part-of-speech tagging

Selon ([http://fr.wikipedia.org/wiki/%C3%89tiquetage_morpho-syntaxique Wikipédia, oct 20, 2014), nn linguistique, l'étiquetage morpho-syntaxique (aussi appelé étiquetage grammatical, POS tagging (part-of-speech tagging) en anglais) est le processus qui consiste à associer aux mots d'un texte les informations grammaticales correspondantes comme la partie du discours, le genre, le nombre, etc. à l'aide d'un outil informatique.

Certains types d'analyses du text mining utilisent des techniques de la linguistique. Ils utilisent comme input non pas une liste de mots ou de termes, mais un texte annoté. Ces annotations comprennent:

  • Informations "part-of-speech", c'est à dire la position d'un élément dans une phrase selon une convention linguistique.
  • Informations "lemma

Un outil populaire multi-langues et gratuit est le TreeTagger.

Similarité

Approche classique

L'approche classique simple définit deux documents comme similaires si les deux partagent des termes. Dans modèle, inventé par Salton (1971) (selon Clément Grimal et Gilles Bisson):

  • Deux documents sont similaires s'ils contiennent des termes similaires
  • Deux termes sont similaires s'ils apparaissent dans des documents similaires

On utilise le poids des termes organisés dans les matrices documents-termes.

Cette méthode souffre du fait que les gens n'utilisent pas toujours les mêmes mots pour parler de la même chose. Ce problème est accentué lorsqu'on a des petites textes.

Exemple:

  1. Cette application est facile à utiliser.
  2. Ce logiciel est facile à utiliser.

On constate:

  • Une relation de premier ordre entre application, facile et utiliser (ou entre logiciel, facile, utiliser)
  • Une relation de 2ème ordre (détectable facilement par les humains) entre "application" et "logiciel". Détecter ce type de relation est nettement plus difficile et peut se faire avec des algorithmes comme LSA, X-SIM, et CTK.

Survol d'autres approches

Grimal et Bisson distinguent entre 5 mesures de similarité:

  • Le cosinus
  • X-Sim (avec ou sans k et p) [Hussain et al.(2010)]
  • LSA (Latent Semantic Analysis) [Deerwester et al.(1990)]
  • SNOS (Similarity in Non-Orthogonal Space) [Liu et al.(2004)]
  • CTK (Commute Time Kernel) [Yen et al.(2009)

+Classification Ascendante Hiérarchique, avec l'indice de Ward

Le modèle LSI

Voir aussi Latent semantic analysis and indexing

Ce modèle part de l'idée que deux termes différents qui apparaissent dans des documents qui sont similaires (ont beaucoup de termes en commun) sont également similaires. Dans l'exemple ci-dessus, application est similaire à logiciel car les deux ont une co-occurence avec facile et utiliser.

Ce modèle était développé pour des corpus larges (par exemple des engins de recherche).

L'utilisation de LSI comprend plusieurs étapes:

  • On commence par une matrice documents-termes (DTM)
  • ... (à suivre)

Liens

Général

Tutoriels

Liens en Anglais

(à bouger un jour ...)

General

(websites, blogs, etc.)

  • Blog Onyme. Blog d'une société qui vend des solutions. Contient des articles d'intérêt général.

Machine learning

Topic modeling

Summarization of microblogs

Bibliographie

  • Gilles Bisson et Clément Grimal, Apprentissage multi-vue de co-similarités pour la classification, CAp, 2012. Paper, Slides
  • Clément Grimal et Gilles Bisson, Amélioration de la co-similarité pour la classification de documents, CAP 2011, Paper, Slides
  • S. F. Hussain, C. Grimal, and G. Bisson. An improved co-similarity measure for document clustering. In Proceedings of the 9th ICMLA, 2010.
  • S. Deerwester, S. T. Dumais, G. W. Furnas, Thomas, and R. Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41:391-407, 1990.
  • N. Liu, B. Zhang, J. Yan, Q. Yang, S. Yan, Z. Chen, F. Bai, and W. ying Ma. Learning similarity measures in non-orthogonal space. In Proceedings of the 13th ACM CIKM, pages 334-341. ACM Press, 2004.
  • L. Yen, F. Fouss, C. Decaestecker, P. Francq, and M. Saerens. Graph nodes clustering with the sigmoid commute-time kernel: A comparative study. Data Knowl. Eng., 68(3):338-361, 2009