Teaching - TAL

Page principale de l'UE


Traitement Automatique de la Langue

TME clustering thématique & sémantique

imports et installation

Nous allons travailler sur des corpus de textes en utilisant différentes librairies (cf liste non exhaustive ci-dessous). La plupart des outils sont installés en salle machine. Pour les installer chez vous ou mettre à jour les versions des salles de TME: lien

import numpy as  np
import codecs
import matplotlib.pyplot as plt
import unicodedata
import re
from collections import Counter,defaultdict
import os
import string
import pdb
import nltk

Récupération & chargement d'un corpus

Dans ce TME, nous allons travailler avec le corpus 20 newsgroups qui regroupe des news de 20 domaines thématiques. Le but étant de mettre en oeuvre des stratégies de clustering, nous allons travailler en aveugle (ie, sans les étiquettes) puis nous évaluerons la qualité des modèles par rapport à la vérité terrain.

Chargement des documents, mode(s) d'emploi: lien

Vous devez obtenir une liste de textes (ou une liste par classe de documents). Afficher quelques éléments de la liste pour vérifier que tout fonctionne correctement

Traitement des données

Exemple de news chargées:

From: mathew <mathew@mantis.co.uk>
Subject: Alt.Atheism FAQ: Atheist Resources
Summary: Books, addresses, music -- anything related to atheism
Keywords: FAQ, atheism, books, music, fiction, addresses, contacts
Expires: Thu, 29 Apr 1993 11:57:19 GMT
Distribution: world
Organization: Mantis Consultants, Cambridge. UK.
Supersedes: <19930301143317@mantis.co.uk>
Lines: 290


                              Atheist Resources

                      Addresses of Atheist Organizations

                                     USA

FREEDOM FROM RELIGION FOUNDATION

Darwin fish bumper stickers and assorted other atheist paraphernalia are
available from the Freedom From Religion Foundation in the US.

Write to:  FFRF, P.O. Box 750, Madison, WI 53701.
Telephone: (608) 256-8900

EVOLUTION DESIGNS

Evolution Designs sell the "Darwin fish".  It's a fish symbol, like the ones
Christians stick on their cars, but with feet and the word "Darwin" written

Après visualisation de quelques fichiers, on souhaite faire quelques traitements, par exemple:

  • suppression des entetes (jusqu'au premier double saut de ligne)
  • suppression des caractères spéciaux + ponctuation
  • mise en minuscules...

Attention aux codages des textes: chaque outil attend un format de données spécifiques, il faut faire un certain nombre de conversions !!!

Voici des outils utiles pour effectuer ces opérations :

import string
import unicodedata
import re

def process(txt):
    txt = txt[txt.find("\n\n"):] # elimination de l'entete (on ne conserve que les caractères après la première occurence du motif
    txt = unicodedata.normalize("NFKD",txt).encode("ascii","ignore") # elimination des caractères spéciaux, accents...

    punc = string.punctuation    # recupération de la ponctuation
    punc += u'\n\r\t\\'          # ajouts de caractères à enlever
    table =string.maketrans(punc, ' '*len(punc))  # table de conversion punc -> espace
    txt = string.translate(txt,table).lower() # elimination des accents + minuscules

    return re.sub(" +"," ", txt) # expression régulière pour transformer les espaces multiples en simples espaces

# validation du processus
print docs[0][0]
print process(docs[0][0])

Attention aux boucles for en python qui sont particulièrement inefficaces... On essaie de les imbriquer dans des listes (elles sont alors pré-compilées et beaucoup plus rapides)

# version rapide
corpuspp = [[process(t) for t in topic] for topic in docs]

Note: cette étape est critique, il faut choisir les traitements et les séparateurs.

Exercice

  • conserver les points si on veut séparer selon les phrases,
  • conserver ou pas les majuscules en fonction de la tâche visée,
  • conserver/éliminer les chiffres,
  • les mots outils (stop-words) peuvent être supprimés ici où lors de la constitution du dictionnaire.
  • remplacer les url par le tag url (expression régulière)
  • ne conserver que les noms et les verbes

!!! Prise en main des modèles

Les sacs de mots (à la main)

Avant d'utiliser des traitements & algorithmes sur l'étagère, nous allons coder un k-means afin de valider le fonctionnement de la méthode, de l'intérieur. Première étape, la transformation en sacs de mots.

Sac de mots, étape 1 = constitution du dictionnaire

Méthode de base:

  1. séparer les documents en mots
  2. dans une table de hash, stocker tous les mots uniques (et leur nombre d'apparition, on en aura besoin rapidement)
from collections import Counter

def count_ngrams(s,n=2,dic=None): # directement defini sur les N-grams, marche en particulier pour n=1 (mots uniques)
    if dic is None:
        dic=Counter() # = table de hash + comptage
    for i in range(len(s)):
        for j in range(i+1,min(i+n+1,len(s)+1)):
            dic[u''.join(s[i:j])]+=1
    return dic

# constitution du dictionnaire (étape clé de la représentation en sacs de mots)
dico = None
for topic in corpuspp:    # pour tous les thèmes
    for d in topic:       # pour tous les textes du thème
        dico = count_ngrams(d.split(), n=1, dic=dico) # penser à faire un split sur le texte pour séparer les mots

print len(dico)

Suivant les traitements, la taille varie... Pour des traitements costauds (tout en minuscules + élimination des caractères spéciaux), on obtient plus de 280k mots: c'est déjà très très gros alors que nous n'envisageons pas encore les n-grammes.

Note: pour la sélection des mots fréquents/rares, certaines informations sont disponibles dès cette phase du traitement en faisant:

freq = np.array(dico.values(), dtype=float) # attention au type (si int => impossible de stocker des fréquences)
freq /= len(corpuspp) # normalisation

Ce ne sont pas les fréquences documentaires qui sont extraites... Mais simplement le nombre total d'apparitions du terme normalisé par la taille du corpus.

Si l'on souhaite éliminer les stop-words, une liste est accessible dans nltk:

from nltk.corpus import stopwords
print stopwords.words('french')
print stopwords.words('english')

Exercice:

  • Afficher les mots les plus fréquents et les moins fréquents du corpus
  • Déterminer une limite pour la suppression des mots rares/fréquents
  • Modifier la méthode pour trouver la fréquence documentaire
    • Utiliser set pour éliminer les doublons... Au bon endroit
  • Afficher la distribution des fréquences de termes (loi de Zipf)
    • en déduire la taille des dictionnaires en fonction des sélections effectuées

Mise à plat du corpus et stockage des étiquettes à part

# mise à plat du corpus et récupération des étiquettes de thème à part

x_brut = [] # un document par case
y = [] # une étiquette par case
for i,topic in enumerate(corpuspp):
   x_brut += topic # + : operateur de concatenation de listes
   y += [i for n in range(len(topic))]

# In[21]: len(corpuspp)
# Out[21]: 20
# In[22]: len(x_brut)
# Out[22]: 11314

Projection du corpus sur le dictionnaire pour obtenir des sacs de mots


# tables de conversions : mots => index (et inverse)
mots2index = dict(zip(dico.keys(), range(len(dico))))
index2mots = dict(zip(mots2index.values(), mots2index.keys()))

import scipy.sparse

# représentation en sacs de mots
N = len(x_brut)
D = len(mots2index)

# choix important pour les matrices sparses (lil = plus rapide pour notre tache)
bow=scipy.sparse.lil_matrix((N,D))
cpt=0
def add1(i,j):
    bow[i,j] += 1

[[add1(i,mots2index[m]) for m in s.split() if m in mots2index] for i,s in enumerate(x_brut)]

print "bow computed"

# affichage d'un document vu en sac de mots
print [index2mots[i] for i in bow[0].nonzero()[1]]
 

Les traitements supplémentaires à effectuer

Plusieurs traitements sont importants:

  • la normalisation des lignes de la matrice (pour passer d'un comptage à une représentation fréquentielle)
  • la compréhension du dictionnaire:
    • affichage des fréquences des mots dans le corpus
  • la sélection des éléments importants du dictionnaire (élimination des mots rares, des mots trop fréquents...)

Attention, la normalisation n'est pas complètement triviale dans le cadre sparse: il faut être sûr de ne normaliser que les valeurs non nulles sous peine de revenir à une matrice pleine et de (probablement) dépasser la mémoire disponible dans l'ordinateur:

# normalisation : ATTENTION à conserver une structure sparse
size_doc = bow.sum(1) # somme ligne par ligne (= doc par doc)
for i,j in zip(bow.nonzero()[0],bow.nonzero()[1]) : # pour toutes les valeurs non nulles
    bow[i,j] /= size_doc[i]

Algorithme des k-means

1. Tirer aléatoirement k documents (nos k prototypes initiaux)

import numpy as np
import numpy.random as rand

# tirage de k prototypes
prototypes = bow[rand.permutation(N)[:k]].toarray() # conversion en array (dimension acceptable)

2. Trouver pour chaque document le prototype le plus proche

    sim = bow.dot(prototypes.T) # métrique type cos si les vecteurs sont normalisés
    y= sim.argmax(1) # comprendre les dimensions des matrices pour comprendre ce calcul

3. Calculer les nouveaux prototypes

for i in range(k):
    index = np.where(y==i)[0]
    prototypes[i] = np.sum(bow[index,:],1)
prototypes/=prototypes.sum(1) # normalisation

4. Retour en 2.

Il faut ensuite:

  • trouver un critère d'arrêt
  • inspecter les modèles pour comprendre la signification des prototypes

Analyses quantitative et qualitative

Du point de vue quantitatif, l'analyse d'un clustering n'est pas évidente, du fait de l'absence de vérité terrain (la plupart du temps). Dans le cas de 20newsgroups, les étiquettes existent et il est possible d'analyser les résultats, par exemple en terme de pureté:

  • les identifiants de clusters ne correspondent pas aux classes,
  • mais dans chaque cluster, on peut identifier la classe majoritaire,
  • puis calculer quel pourcentage de documents appartient à cette classe majoritaire: c'est la pureté du cluster.
  • Il est ensuite possible d'étendre la métrique à l'ensemble du corpus en pondérant les puretés des clusters par leur taille (on calcule en réalité une espérance sur la pureté).

Il est aussi possible d'analyser la séparation des données en calculant pour chaque prototype la distance moyenne des documents au barycentre puis la distance entre barycentre.

Du point de la qualitatif, l'idée est de comprendre ce qu'il y a dans les clusters: il faut donc analyser le contenu des protoypes:

  • quels mots sont les plus fréquents dans le cluster,
  • quels mots sont les plus représentatifs (fréquents dans ce cluster mais pas dans les autres)...