Le programme présidentiel de Taubira résumé grâce à un sac de mots en fouille de texte L'utilité des techniques de fouille de texte.

Démonstration du calcul d'un indice de similarité basé sur les tags d'articles publiés avec Pelican. Le projet relève de la fouille de texte (extraction de connaissances) ; il utilisera un TF-IDF (Term Frequency-Inverse Document Frequency) pour pondérer les termes et la similarité cosinus pour comparer les articles entre eux.

Le dépôt du plugin finalisé est sur GitHub.

Sommaire

C'est quoi Pelican ?

Pelican est un générateur de sites statiques. Vous écrivez les articles sous forme de texte, enrichi de quelques règles de formatage pour assurer le rendu des images, tableaux, etc. Ce texte est convertit automatiquement en HTML d'après des squelettes de pages appelés templates.

Pelican garantit une indépendance totale du site généré vis à vis de services tiers. En théorie, pas de développement côté utilisateur puisqu'il n'y a qu'à héberger les pages produites sur un serveur web.

En pratique la personnalisation des templates et l'ajout de fonctionnalités au site peut nécessiter des compétences de développement (HTML, JS, CSS, Python, administration système).

De nombreux plugins existent et sont listés sur les dépôts GitHub du projet [1][2].

Similarité entre articles - "État de l'art" des plugins existants

Le plugin Pelican similar-posts permet au mainteneur d'un site de proposer aux lecteurs une liste d'articles similaires à chaque article consulté. Il ne s'agit pas simplement des articles d'une même catégorie, mais bien une liste produite sur la base du calcul d'une similarité mathématique entre les tags des articles du corpus.

Cependant, les dépendances du projet me paraissent bien lourdes pour l'usage démontré et les données traitées (somme toute peu nombreuses : quelques mots par document, et déjà standardisées (j'y reviens plus tard)) :

  • Gensim : Framework d'analyse sémantique pour représenter des documents sous forme de vecteurs sémantiques. Sert à découvrir la structure sémantique de documents en se basant sur l'identification de motifs à partir un corpus d'entraînement ;
  • Numpy : Souvent installée par défaut avec Python, c'est la librairie de calcul scientifique/mathématique par excellence ;
  • Scipy : Plus axée vers le traitement scientifique des données, elle fédère de nombreux domaines de recherche ;
  • smart-open : Librairie utilisée à la place de la fonction open() pour charger de gros volumes de fichiers, notamment depuis des serveurs en ligne (Amazon S3 et compagnie, HTTP, SFTP) ou localement. Le tout avec compression/décompression à la volée.

Je juge cependant les importations de Numpy et Scipy dans un projet assez couteuses ; ces librairies sont imposantes et peuvent ralentir le processus de génération du site (surtout au premier run car il faut les charger en cache).

Je juge que smart-open n'est clairement pas adaptée pour la génération d'un blog de quelques centaines de pages. Qui peut le plus peut le moins ? Oui mais à mon avis, la règle KISS (Keep It Simple and Stupid) devrait toujours primer les autres.

J'estime que l'usage de Gensim ou même le vieux nltk est également surévalué pour le besoin actuel. Gensim se veut performante, mais le projet actuel n'utilisera qu'une infime portion de ses capacités.

Réinvention de la roue numérique

Il n'est jamais bon de réinventer la roue pour réinventer la roue, mais il y a des situations où je considère cela acceptable :

  • dans le cadre d'une réduction des dépendances : surtout si on utilise une petite fonction basique d'un projet beaucoup plus gros dont l'usage apporte des désagréments qu'il s'agit de mettre en balance avec le gain espéré ;
  • si la fonction utilisée est clairement moins performante ;
  • pour savoir comment ça fonctionne, tout simplement ; ne vous fiez pas aux boîtes noires !
  • si on ne peut avoir confiance dans le projet tiers : sécurité, pérennité/maintenance, bonne foi du dev, etc.

À pondérer par le fait qu'un développeur aura trop souvent l'impression de pouvoir faire mieux que l'existant...

Traitement des données en fouille de texte

La procédure classique en fouille de texte et plus généralement en traitement des données consiste à standardiser le support de travail pour produire des résultats les plus fiables possible.

  • Récupération des données
  • Représentation mathématique/standardisation des données
  • Construction d'une structure de données dédiée
  • Algorithme de comparaison et utilisation d'une métrique de similarité

Récupération des données

Les données utilisées sont les tags des articles.

Pelican fonctionne sur un système de plugins qui une fois chargés se déclarent réceptifs à des signaux émis au cours du processus de génération du site.

En souscrivant par exemple au signal article_generator_write_article :

signals.article_generator_write_article.connect(similar_articles_set_tfidf)

La fonction similar_articles_set_tfidf recevra un objet generator et un objet content (de type Article ou Page) desquels on pourra accéder aux données qui nous intéressent.

def similar_articles_set_tfidf(article_generator, content):
    ...

Représentation mathématique / standardisation des données

Tokenisation, lemmatisation & racinisation

En théorie, les termes d'un document doivent être traités (normalisés) avant toute tentative d'indexation, archivage, et recherche. Trois étapes successives sont censées être réalisées: la tokenisation, la lemmatisation et la racinisation (stemming en anglais).

La première étape, la tokenisation consiste à diviser le texte en phrases, puis les phrases en mots le tout en supprimant toute mise en forme, ponctuation, etc. On retire aussi les mots trop communs (pronoms, articles) à l'aide d'une liste de mots vides (stop-words).

Les deux étapes suivantes s'appliquent sur les jetons/mots générés à l'étape précédente.

Leur but est de regrouper les termes similaires afin de réduire le nombre de jetons sur lesquels un algorithme pourra travailler.

  • La lemmatisation a pour but de regrouper plusieurs formes d'un terme en une forme sans flexions (conjugaison des verbes, accord des adjectifs). Le terme obtenu est une forme canonique, appelée lemme ; les lemmes constituent les enregistrements d'un dictionnaire.

    Ex:

    petite, petits => petit
    jouons, joué, jouera => jouer
    

    La lemmatisation repose sur une base de données servant à la conversion des formes fléchies vers la forme canonique (lexique).

    Cette étape est très dépendante des fautes d'orthographe.

  • La racinisation, consiste à extraire le radical d'un mot (on le débarrasse de ses préfixes et suffixes). Le résultat est un terme tronqué, commun à plusieurs mots et pas nécessairement présent dans le dictionnaire.

    Ex:

    cheval, chevaux => cheva
    

    Le racinisation repose sur une base de données regroupant les règles syntaxiques et grammaticales de la langue étudiée. Il peut aussi se faire sur un lexique dans ce cas, le taux d'erreur de regroupement sera plus faible. On distingue les erreurs de sur-racinisation (des mots regroupés n'ont pas le même sens = Faux positifs), et la sous-racinisation (des mots ne sont pas regroupés à tort = Faux négatifs)

    Cette étape est moins dépendante des fautes d'orthographe que la lemmatisation.

Influence sur le système de recherche

Les regroupements permettent de réduire drastiquement le corpus de jetons étudié. Toutefois, le sens des phrases est perdu, et pire, les regroupements peuvent se faire sur des mots ayant des sens différents ; la racinisation en particulier est un traitement destructif.

L'usage de ces techniques permet aussi d'augmenter le rappel (plus de documents rapatriés) au détriment de la précision (certains documents rapatriés sont non voulus à causes des erreurs de regroupement) du système de recherche d'information (RI).

Voir l'excellente infographie sur Wikipédia :

Précision et rappel, représentation ensembliste pour un corpus de documents Précision et rappel, représentation ensembliste pour un corpus de documents. Wikipédia - Précision et rappel

Implémentation

Dans le cas qui m'intéresse, j'estime que les tags des articles sont déjà des termes standardisés sans variantes et qu'avec un minimum de rigueur (toujours utiliser des tags d'un ensemble défini au préalable), les étapes de lemmatisation et racinisation deviennent facultatives.

La tokenisation est censée être aussi inutile car un tag est une entité indivisible et le plus souvent composée d'un seul mot.

L'usage de Gensim ou nltk devient instantanément conseillé si ces postulats ne sont pas respectés. Les étapes citées précédemment requièrent des sources de données externes et des algorithmes qu'il est inutile de réimplémenter.

Construction d'une structure de données dédiée

Sac de mots

Le document étudié est dorénavant réduit à une liste de termes. Le comptage des occurrences de ces termes (fréquences d'apparition) forme une entité appelée sac de mots (bag of words en anglais).

On peut considérer ce sac de mots comme un vecteur mathématique où chaque position correspond à un terme et le coefficient à cette position correspond à fréquence du terme.

On créé donc un sac de mots pour chaque article et un dictionnaire pour l'ensemble du corpus.

La taille du vecteur d'un article correspond au nombre de mots dans le dictionnaire global du corpus étudié. Chaque vecteur est globalement très vide car un document cumule rarement tous les mots d'un dictionnaire.

Pour comparer les vecteurs entre eux il faut conserver l'ordre des termes (et donc des coefficients).

TF-IDF

Une méthode naïve serait de comparer les vecteurs des articles entre eux et de ne les considérer comme similaires que ceux qui ont le plus de tags en commun. Cette approche ne tient pas compte des fréquences des tags (rareté) à l'échelle du corpus. Par exemple si de nombreux articles ont un tag en commun, peut être vaudrait-il mieux baisser le poids de celui-ci dans leurs vecteurs. À l'inverse, plus un terme est rare dans le corpus, plus son poids doit être important car le terme est considéré comme plus discriminant.

C'est pourquoi nous n'utiliserons pas directement les fréquences des tags dans les vecteurs, mais une pondération de celles-ci par la méthode du TF-IDF (Term Frequency-Inverse Document Frequency).

On définit pour cette méthode 2 grandeurs :

  • TF: La fréquence d'un terme dans un document (brute ou normalisée) ;
  • IDF: Une mesure de la fréquence d'un terme dans le corpus ;

    Formule idf (Inverse Document Frequency)

    |D| : Nombre de documents dans le corpus.

    |{ dj : ti ∈ dj }| : Nombre de documents où le terme ti apparaît.

Ces 2 grandeurs permettent d'obtenir le TF-IDF (poids final d'un terme) :

tfidfij = tfij . idfi

Implémentation

Dans le cas présent mon tf est normalisé par binarisation : 1 = présence du tag, 0 = absence du tag. Ce choix est justifié car aucun tag n'apparaît plusieurs fois pour un article.

Le vecteur d'un document est le tf, le dictionnaire global est l'idf.

Nous devons donc calculer l'idf global de chaque tag et l'ajouter au contexte commun à tous les articles de Pelican, puis calculer le tf et enfin le tfidf pour chaque tag de chaque article en ajoutant le résultat dans un nouvel attribut dédié.

def similar_articles_set_tfidf(article_generator, content):
    # Add idf to global context
    if "idf" not in article_generator.context:
        # Count occurences of tags in all the articles
        tags = Counter(
            tag._name
            for article in article_generator.articles
            for tag in article.metadata.get("tags", [])  # Some articles may not have any tags
        )
        # Add idf to context
        idf = {
            tag_name: log10(len(article_generator.articles) / freq)
            for tag_name, freq in tags.items()
        }
        # Fix arbitrary order of tags (not needed for python 3.6+=)
        article_generator.context["idf"] = OrderedDict(idf)

    # Add tfidf to every articles
    if "tfidf" not in content.metadata:
        for article in article_generator.articles:
            # Get tag names of the article
            article_tags = frozenset(tag._name for tag in article.metadata.get("tags", tuple()))
            # Compute tfidf vector for the current article
            tfidf = tuple(
                # This is the tf binarization
                idf * 1 if tag_name in article_tags else 0
                for tag_name, idf in content._context["idf"].items()
            )
            # Add tfidf to article
            article.metadata["tfidf"] = tfidf

Exemple de calcul de tfidf pour deux articles A ayant pour tags {"a", "b", "c"}, et B ayant pour tags {"c", "b", "d"} :

# sac de mots global :
tags = {"a": 1, "b": 2, "c": 2, "d": 1}

# idf du corpus
idf = {tag_name: log10(2 / freq) for tag_name, freq in tags.items()}
# {'a': 0.3, 'b': 0.0, 'c': 0.0, 'd': 0.3}

# A: tfidf = tf * idf
tfidfA = [idf * 1 if tag_name in tags_A else 0 tag_name, idf in idf.items()]
# [0.3 * 1, 0 * 1, 0 * 1, 0.3 * 0]
# [0.3, 0, 0, 0.0]

# B:
#[0.3 * 0, 0 * 1, 0 * 1, 0.3 * 1]
#[0.0, 0, 0, 0.3]

On remarque que les termes b et c n'ont aucun intérêt puisque présents dans 100% des articles ; leurs poids est donc toujours 0.

Nos vecteurs sont préparés, il faut maintenant les comparer entre eux.

Algorithme de comparaison et utilisation d'une métrique de similarité

Similarité cosinus

J'utilise la similarité cosinus pour comparer les vecteurs entre eux. C'est une méthode classique utilisée en fouille de texte.

Les documents étant réduits à des vecteurs, calculer l'angle que forment les vecteurs dans l'espace revient à calculer leur similarité.

Deux cas extrêmes sont envisagés :

  • Les vecteurs sont colinéaires (parallèles) ; l'angle qu'ils forment est alors de 0° (pas 180° car les termes sont ordonnés arbitrairement dans chaque vecteur) ; cos(0) = 1 (similarité maximale).

  • Les vecteurs sont orthogonaux (se croisent à 90°) ; ils n'ont aucun point commun ; cos(90) = 0 (similarité minimale).


Soit deux vecteurs A et B, le cosinus de leur angle θ s'obtient en prenant leur produit scalaire divisé par le produit de leurs normes :

Formule similarité cosinus entre vecteurs A et B

Plusieurs normes de vecteurs existent, nous utiliserons la norme euclidienne.

Exemple pour un repère orthonormé (2 dimensions) :

||A|| = √(x2 + y2)

Implémentation

Le produit scalaire de 2 vecteurs consiste à multiplier leurs coefficients, puis à additionner les résultats.

def dot_product(v1, v2):
    return sum(map(op.mul, v1, v2))

Le calcul de la norme d'un vecteur revient à calculer la racine carrée du produit scalaire de ce vecteur par lui-même.

Par conséquent la distance cosinus se calcule comme suit :

# Compute similarity vs all other articles
# Get the tfidf of the current article
tfidf_current = content.metadata["tfidf"]
norm_current = dot_product(tfidf_current, tfidf_current)
# Iterate on all the articles of the corpus
articles = dict()
for article in article_generator.articles:
    if article == content:
        continue
    tfidf_adverse = article.metadata["tfidf"]
    prod = dot_product(tfidf_current, tfidf_adverse)
    norm_adverse = dot_product(tfidf_adverse, tfidf_adverse)

    if min(norm_current, norm_adverse) == 0:
        cosine = 0
    else:
        cosine = prod / ((norm_current * norm_adverse)**0.5)
    articles[article] = cosine

Il s'agit ensuite de récupérer les n articles ayant les valeurs les plus importantes.

# Get the 2 most similar articles
most_similar = tuple(article for article, score in Counter(articles).most_common(2) if score > 0)
if most_similar:
    # Add these articles to similar_articles attribute of the current article
    content.similar_articles = most_similar

À propos de performance

Quelques tests de performance sur les implémentations de la similarité cosinus avec Numpy et Scipy :

import random
u = [random.random() for i in range(100)]
v = [random.random() for i in range(100)]

import numpy
u_np = numpy.array(u)
v_np = numpy.array(v)

# Bare Python
def dot_product(v1, v2):
    return sum(map(op.mul, v1, v2))

def vector_cos_py(v1, v2):
    prod = dot_product(v1, v2)
    len1 = dot_product(v1, v1)
    len2 = dot_product(v2, v2)
    return prod / (len1 * len2)**0.5

# Scipy
from scipy.spatial.distance import cosine as _vector_cos2
def vector_cos_scipy(u, v):
    return 1.0 - _vector_cos2(u, v)

# Numpy
from numpy import dot
from numpy.linalg import norm

def vector_cos_np(u, v):
    return dot(u, v)/(norm(u)*norm(v))

# timeit vector_cos_py(u, v)
# timeit vector_cos_py(u_np, v_np)
# timeit vector_cos_scipy(u, v)
# timeit vector_cos_scipy(u_np, v_np)
# timeit vector_cos_np(u, v)
# timeit vector_cos_np(u_np, v_np)
méthodedurée
numpy + numpy arrays19µs
pur python20µs
numpy46µs
scipy + numpy arrays58µs
scipy74µs
pur python + numpy arrays117µs


Il se trouve que l'implémentation montrée en pur Python est plus rapide que celle de Scikit-learn (17.4 fois plus lente), celle de Scipy (3.7 fois plus lente)[3] et celle de numpy (2.3 fois plus lente).

Note : Les librairies basées sur numpy sont défavorisées lorsqu'elles reçoivent des listes Python car leur transtypage en numpy.arrays est coûteux.


En pratique dans le plugin une optimisation est faite, pour quasiment réduire de moitié les calculs réalisés. En effet, la technique exposée ci-dessus calcule une similarité pour chaque article vs tous les autres (produit cartésien).

Par exemple pour 4 articles A, B, C, D, les tests suivants sont faits:

AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD

Or A.C = C.A car le calcul du produit scalaire est commutatif.

Le traitement requis relève en fait de la combinaison :

itertools.combinations('ABCD', 2)
# AB AC AD BC BD CD

Conclusion

L'implémentation manuelle est tout à fait possible et présente les avantages suivants :

  • Pas de dépendances ;
  • Implémentation courte ~60 lignes avec commentaires ;
  • La méthode est efficace ;
  • Permet d'apprendre des notions.

L'implémentation du plugin similar-posts est très similaire (voir le code sur GiHub) sauf que le calcul de similarité est encapsulé dans Gensim.

Sources