Travaux pratiques - Fouille de données textuelles

Références externes utiles :

Introduction

Dans ce TP nous apprendrons à explorer le contenu d’une base de textes d’assez grande taille, en utilisant l’analyse sémantique latente (LSA - Latent Semantic Analysis). Le but premier est d’explorer les données en déterminant quels sont les « concepts » (ou classes sémantiques) qui expliquent le mieux les données. Nous extrairons aussi les documents représentatifs et ferons des requêtes qui permettent de trouver les documents de la base qui mentionnent certains termes ou qui sont similaires à un document requête.

LSA vise à mieux représenter un corpus de documents en explorant les relations entre les mots dans les documents. Le but est de « distiller » à partir du corpus un ensemble de « concepts » pertinents. Chaque concept saisit une direction de variation dans les données, qui souvent correspond à un sujet abordé dans le corpus. En grandes lignes, chaque concept est décrit par trois caractéristiques : la pertinence du concept pour chaque document du corpus, l’affinité par rapport aux autres termes du corpus et l’utilité du concept dans la description de la variance des données. En sélectionnant seulement les concepts les plus importants, LSA peut décrire les données avec une représentation approximative qui emploie moins de concepts, qui élimine du « bruit » et fusionne des sujets similaires.

LSA découvre cette représentation en utilisant la décomposition en valeurs singulières (Singular Value Decomposition, SVD). SVD factorise la matrice TF-IDF (Term Frequency - Inverse Document Frequency) du corpus en trois matrices : une qui exprime l’importance des concepts par rapport aux autres documents, une qui exprime les concepts par rapport aux termes (mots) importants, et une troisième qui donne l’importance de chaque concept. La structure de ces matrices est telle qu’une approximation de rang plus faible de la matrice d’origine peut être obtenue par élimination des concepts les moins importants.

Dans le cadre de ce TP nous utiliserons une partie de la base de donnée Wikimedia (https://dumps.wikimedia.org). La base complète est d’env. 57 Go, pour des raisons de ressources disponibles nous travaillerons sur un échantillon de 200 Mo (approximativement 6000 pages).

Une suite utile de ce TP est la classification automatique de tweets avec des représentations Word2Vec, qui ne sera pas abordée dans les séances de travaux pratiques mais que vous pouvez suivre ou dont vous pouvez vous en inspirer pour votre projet.

Création de l’environnement de travail

Exécutez les commandes suivantes pour créer l’environnement nécessaire. D’abord, créez les répertoires de travail dans une fenêtre terminal :

$ cd
$ mkdir -p tptexte/data

Ensuite récuperez les données :

$ cd tptexte/data
$ wget http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/enwiki.xml.bz2
$ bzip2 -d enwiki.xml.bz2
$ cd ..

La dernière commande vous positionne dans le répertoire tptexte, il faudra y rester pour entrer les commandes du bloc suivant.

Il est nécessaire maintenant de construire un .jar qui inclut les librairies externes employées avec toutes leurs dépendences. Cela exige normalement d’installer et lancer l’outil Maven, et peut prendre jusqu’à 30 minutes. Afin de vous faire gagner ce temps, nous avons déjà préparé le .jar qui sera téléchargé. Pour cela, entrez les commandes suivantes dans la fenêtre terminal :

$ wget http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/topDocsForTerms.scala
$ wget http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/deps.zip
$ unzip deps.zip
$ wget http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/lsa.jar

Si le .jar n’avait pas été déjà disponible, il aurait été nécessaire de le créer, en installant d’abord Maven. Les commandes qui auraient été nécessaires sont listées ci-dessous (ne les exécutez pas si vous avez récupéré déjà le .jar).

$ cd deps
$ sudo yum install maven
$ mvn package
$ cd ..

On lance spark-shell dans ~/tptexte, avec un peu plus de mémoire à sa disposition (1 Go) et en ajoutant le fichier .jar avec les bonnes librairies et dépendances dans le chemin d’accès de Spark :

$ spark-shell --driver-memory 1g --jars lsa.jar

Dans spark-shell on commence par importer les paquetages nécessaires. Il est possible de copier et coller dans spark-shell des instructions multi-lignes (comme le dernier import ci-dessous) en entrant d’abord :paste.

scala> import com.cloudera.datascience.lsa._
scala> import com.cloudera.datascience.lsa.ParseWikipedia._
scala> import com.cloudera.datascience.lsa.RunLSA._
scala> import org.apache.spark.mllib.linalg._
scala> import org.apache.spark.mllib.linalg.distributed.RowMatrix
scala> import breeze.linalg.{DenseMatrix => BDenseMatrix,
              DenseVector => BDenseVector, SparseVector => BSparseVector}

Le TP utilise le projet Cloud9 pour lire la base de données Wikimedia en format XML et extraire les parties qui nous intéressent : les titres et les corps de texte. Nous utilisons aussi le projet Stanford Core NLP pour effectuer les traitements linguistiques necessaires (segmentation, étiquetage, lemmatisation).

Par la suite, à chaque fois que vous rencontrez un appel de méthode préfixée par les objets ParseWikipedia et RunLSA vous devez regarder l’implémentation correspondante dans les sources en scala : fichiers ParseWikipedia.scala et RunLSA.scala du répertoire tptexte/deps/lsa/src/main/scala/com/cloudera/datascience/lsa/.

Remarque générale : après avoir entré une commande (dans la fenêtre terminal ou dans spak-shell) regardez attentivement la réponse que vous obtenez. Si cette réponse indique une anomalie (par ex. suite à une faute de frappe), essayez de corriger cette anomalie avant d’aller plus loin. Il est inutile d’entrer les commandes suivantes sans avoir corrigé l’anomalie.

Chargement de la base de données

Nous construisons un RDD à partir des données situées sur le systeme de fichiers local :

scala> val wikixmlfile = "data/enwiki.xml"
scala> val sampleSize = 0.3
scala> val xmlPages = ParseWikipedia.readFile(wikixmlfile, sc).sample(false, sampleSize, 11L)
scala> xmlPages.take(2)
scala> val plainText = xmlPages.filter(_ != null).flatMap(ParseWikipedia.wikiXmlToPlainText)
scala> plainText.take(2)

Si vous voulez obtenir un échantillon différent à chaque fois que vous exécutez les commandes, enlevez le paramètre 11L (seed). Inspectez les types de données des valeurs xmlPages et plainText. Regardez le fichier source enwiki.xml et essayez de comprendre la chaîne de traitement (regardez aussi les sources en scala, comme demandé précédemment).

Lemmatisation

Chaque élément de plainText est une paire de chaînes de caractères (type string) : la première chaîne est le titre d’une page Wikimedia, la seconde chaîne est le contenu textuel de cette page. Pour chaque page il faut découper le texte en mots, mettre les mots dans leur forme canonique (lemmatisation) et ensuite éliminer les stop words. La forme canonique dépend du rôle morphologique et syntaxique du mot. Il faut donc aussi appliquer un étiqueteur grammatical (tagger) sur le texte du contenu. On réalise cette chaîne de traitement en nous servant des outils Java issus du projet Stanford NLP, comme suit (rappelons qu’il est possible de copier et coller dans spark-shell des instructions multi-lignes en entrant d’abord :paste) :

scala> val stopWords = sc.broadcast(ParseWikipedia
                         .loadStopWords("deps/lsa/src/main/resources/stopwords.txt")).value
scala> val lemmatized = plainText.mapPartitions(iter => {
           val pipeline = ParseWikipedia.createNLPPipeline();
           iter.map{ case(title, contents) =>
                         (title, ParseWikipedia.plainTextToLemmas(contents, stopWords, pipeline))};
       }).cache()

scala> lemmatized.take(2)
scala> val filtered = lemmatized.filter(_._2.size > 1)

Question :

Quel est le rôle de la dernière commande ?

Correction :

Dans _._2, le premier _ correspond à l’élément générique de lemmatized et ._2 indique sa deuxième composante, qui est la liste des lemmes extraites du texte de l’article Wikimedia (après suppression des stop words). La première composante (_._1 correspond au titre sde l’article. Cette commnde permet donc d’éliminer de filtered les éventuels éléments de lemmatized pour lesquels la liste de lemmes contient moins de deux lemmes.

Spark propose aussi un tokenizer et un outil de suppression des stop words (ainsi qu’un outil de calcul des représentations TF-IDF). En revanche, Spark ne propose pas la lemmatisation, ni l’étiquetage (tagging) préalable. En conséquence, en appliquant directement les outils proposés par Spark (tokenizer suivi de suppression des stop words), les formes fléchies d’un même lemme sont traitées comme des mots (termes) distincts. Cela est nocif pour les modèles construits sur ces représentations car leur dimension est inutilement élevée (chaque forme fléchie d’un mot est comptée comme mot distinct) et deux formes différentes d’un même mot qui apparaissent dans deux documents ne permettent pas de faire le lien entre ces documents. En revanche, le calcul des pondérations TF-IDF est plus efficace avec l’outil Spark qu’avec celui de ParseWikipedia employé dans la suite.

Calcul de la matrice TF-IDF

Maintenant nous sommes prêts à calculer la matrice TF-IDF de la base de données. Pour chaque document nous obtenons la représentation TF-IDF mais pour alléger les calculs nous gardons seulement un nombre de numTerms termes (mots, ou plutôt lemmes), les plus fréquents dans les documents.

scala> val numTerms = 1000 // nombre de termes à garder (les plus fréquents)
scala> val (termDocMatrix, termIds, docIds, idfs) =
            ParseWikipedia.termDocumentMatrix(filtered, stopWords, numTerms, sc)

Quelle est l’expression exacte de la pondération TF-IDF calculée ? Regardez les sources en scala.

Nous utiliserons beaucoup cette matrice par la suite et demandons donc à Spark de la garder en mémoire :

scala> termDocMatrix.cache()

Calcul de LSA et inspection des résultats

Il est utile de revoir la présentation de LSA dans le cours.

Nous appliquons une decomposition en valeurs singulières (SVD) de la matrice \(\mathbf{M}\) des représentations vectorielles TF-IDF. MLlib contient une implémentation de SVD qui garde les \(k\) plus grandes valeurs singulières et qui produit trois matrices \(\mathbf{U}\), \(\mathbf{S}\) et \(\mathbf{V}\) telles que \(\mathbf{M} \approx \mathbf{U}_k \cdot \mathbf{S}_k \cdot \mathbf{V}_k^T\). Si la matrice \(\mathbf{M}\) est de taille \(m \times n\) (\(m\) documents, \(n\) termes), alors :

  • \(\mathbf{U}_k\) est une matrice \(m \times k\) : ses colonnes forment une base orthonormale dans l’espace de dimension \(m\) ; l’élément \(u_{ij}\) de \(\mathbf{U}_k\) indique « l’importance » du concept \(j\) pour le document \(i\) ;
  • \(\mathbf{S}_k\) est une matrice diagonale \(k \times k\) : les éléments sur la diagonale principale représentent l’importance de chaque concept extrait (son « pouvoir à expliquer les données ») ;
  • \(\mathbf{V}_k\) est une matrice \(n \times k\) : ses colonnes forment une base orthonormale dans l’espace de dimension \(n\) ; l’élément \(v_{ij}\) de \(\mathbf{V}_k\) indique « l’implication » du mot (terme) \(i\) dans le concept \(j\).

La décomposition est paramétrée par \(k\), le nombre de concepts à garder. Si \(k = n\) alors la décomposition est exacte (on retrouve la matrice \(\mathbf{M}\) sans approximations). Normalement \(k \ll n\) et \(\mathbf{U}_k \mathbf{S}_k \mathbf{V}_k^T\) est une approximation de \(\mathbf{M}\) qui est optimale par rapport à la norme L2 (perte quadratique minimale).

scala> val mat = new RowMatrix(termDocMatrix)
scala> val k = 200 // nombre de valeurs singulières à garder
scala> val svd = mat.computeSVD(k, computeU = true)

En utilisant cette décompostion, nous pouvons afficher les concepts importants à travers les termes qui les caractérisent et les documents dans lesquels ils se manifestent le plus :

scala> val topConceptTerms = RunLSA.topTermsInTopConcepts(svd, 10, 10, termIds)
scala> val topConceptDocs = RunLSA.topDocsInTopConcepts(svd, 10, 10, docIds)
scala> for ((terms, docs) <- topConceptTerms.zip(topConceptDocs)) {
          println("Concept terms: " + terms.map(_._1).mkString(", "));
          println("Concept docs: " + docs.map(_._1).mkString(", "));
          println();
       }

Regardez l’implémentation des methodes RunLSA.topTermsInTopConcepts et RunLSA.topDocsInTopConcepts.

Question :

Regroupez dans un programme tptexte.scala toutes les commandes ci-dessus qui suivent la lecture du fichier de données. Chargez ce programme avec la commande :load tptexte.scala et faites varier le paramètre \(k\) : 100, 400. Comparez les concepts trouvés dans ces différents cas.

Correction :

Pour \(k\) = 400 les concepts trouvés semblent plus consistants que pour une plus petite valeur. Cependant, choisir une valeur de \(k\) trop grande n’est pas indiqué car cela revient à rechercher un nombre trop élevé de concepts (topics) dans le corpus, ce qui conduit à la division du corpus en trop de parties de pertinence discutable. La bonne valeur de \(k\) est à obtenir par expérimentation/investigation du corpus.

Question :

Faites varier numTerms : 500, 2000.

Optionnel : faites varier sampleSize : 0.5, 0.6 (attention, les calculs peuvent prendre beaucoup plus de temps).

Que constatez-vous ? Expliquez.

Correction :

Prendre plus de termes permet de mieux représenter les documents, mais à partir d’un certain nombre de termes les « faux mots » (issus par ex. de fautes d’ortographe) et les usages inhabituels introduisent du bruit dans la représentation du contenu. Concernant sampleSize, des résultats obtenus sur un échantillon plus large sont plus pertinents que ceux obtenus sur un échantillon plus faible mais les calculs sont plus coûteux.

Recherches par rapport à un (groupe de) mot(s) ou à un document

Cette section du TP est optionnelle.

La decomposition précedente permet aussi de faire des recherches dans la base de données, en prenant comme requête un mot, un groupe de mots ou un document.

Trouver des termes similaires à un mot/terme

Dans la matrice \(\mathbf{M}\) des représentations vectorielles TF-IDF, un vecteur colonne correspond à un terme (mot), chaque composante de ce vecteur exprimant son poids TF-IDF par rapport au document correspondant. De ce fait, le cosinus entre deux vecteurs colonnes correspond à une similarité entre les deux mots, similarité induite par les fréquences d’apparition des mots et leurs cooccurrences dans les documents. Passer par la SVD à une matrice de rang réduit, comme expliqué plus haut, entraîne une perte d’information mais a aussi des avantages : prise en compte de la synonymie (par « condensation » des termes reliés) et, dans une certaine mesure, de la polysémie (en plaçant moins de poids sur les mots qui ont plusieurs sens), ainsi que l’élimination du « bruit ».

Cependant, il n’est pas nécessaire de calculer complètement la matrice de rang réduit pour évaluer la similarité cosinus entre des termes. En effet, on peut démontrer que la similarité cosinus entre deux colonnes de la matrice de rang réduit \(\mathbf{U}_k \mathbf{S}_k \mathbf{V}_k^T\) est strictement égale à la similarité cosinus entre les colonnes correspondantes de \(\mathbf{S}_k \mathbf{V}_k^T\).

Considérons la tâche de trouver l’ensemble des termes les plus similaires à un terme particulier. Trouver la similarité cosinus entre un terme et tous les autres termes équivaut à normaliser chaque ligne de \(\mathbf{V}_k \mathbf{S}_k\) à norme 1 et ensuite multiplier la ligne correspondant à ce terme par toutes les autres lignes de \(\mathbf{V}_k \mathbf{S}_k\) (les lignes de \(\mathbf{V}_k \mathbf{S}_k\) sont les colonnes de la matrice transposée, \(\mathbf{S}_k \mathbf{V}_k^T\)). Chaque élément du vecteur résultant contiendra la similarité entre le terme requête et le terme correspondant.

scala> val VS = RunLSA.multiplyByDiagonalMatrix(svd.V, svd.s)
scala> val normalizedVS = RunLSA.rowsNormalized(VS)
scala> var idTerms = collection.mutable.Map[String,Int]()
scala> for(pair <- termIds) idTerms(pair._2) = pair._1

scala> RunLSA.printTopTermsForTerm(normalizedVS, "problem", idTerms, termIds)
scala> RunLSA.printTopTermsForTerm(normalizedVS, "mother", idTerms, termIds)
scala> RunLSA.printTopTermsForTerm(normalizedVS, "africa", idTerms, termIds)

Trouver des documents similaires à un mot/terme

Calculer la similarité entre un terme et un document revient à choisir la ligne \(\mathbf{u}\) correspondant au document dans la matrice \(\mathbf{U}_k\), la ligne \(\mathbf{v}\) correspondant au terme dans la matrice \(\mathbf{V}_k\), et ensuite calculer le produit \(\mathbf{u} \mathbf{S}_k \mathbf{v}^T\). Pour déterminer la similarité d’un terme à chacun des documents on calcule donc \(\mathbf{U}_k \mathbf{S}_k \mathbf{v}^T\). Dans l’autre sens, on peut déterminer les similarités entre un document \(\mathbf{u}\) et tous les termes par le produit \(\mathbf{u} \mathbf{S}_k \mathbf{V}_k^T\).

scala> val US = RunLSA.multiplyByDiagonalMatrix(svd.U, svd.s)
scala> RunLSA.printTopDocsForTerm(US, svd.V, "problem", idTerms, docIds)
scala> RunLSA.printTopDocsForTerm(US, svd.V, "mother", idTerms, docIds)
scala> RunLSA.printTopDocsForTerm(US, svd.V, "africa", idTerms, docIds)

Trouver des documents similaires à un autre document

La matrice \(\mathbf{U}_k\) décrit chaque document par les \(k\) concepts trouvés par la SVD. Pour trouver des documents similaires à un autre document, on pondère chaque colonne de la matrice \(\mathbf{U}_k\) par les valeurs singulières correspondantes (trouvées sur la diagonale de la matrice \(\mathbf{S}_k\)) en faisant le produit \(\mathbf{U}_k \mathbf{S}_k\). Ensuite, on normalise chaque ligne du résultat à une norme de 1 et on calcule la similarité entre deux documents comme le cosinus des deux lignes correspondantes de la matrice normalisée.

scala> val normalizedUS = RunLSA.rowsNormalized(US)
scala> var idDocs = collection.mutable.Map[String,Long]()
scala> for(pair <- docIds) idDocs(pair._2) = pair._1
scala> RunLSA.printTopDocsForDoc(normalizedUS, "P versus NP problem", idDocs, docIds)
scala> RunLSA.printTopDocsForDoc(normalizedUS, "Commonwealth", idDocs, docIds)

Trouver des documents similaires à un groupe de plusieurs mots

Nous avons vu plus haut que pour trouver des documents pertinents à un seul terme il faut commencer par choisir la ligne correspondant à ce terme dans la matrice \(\mathbf{V}_k\). Cela revient à multiplier \(\mathbf{V}_k^T\) par un vecteur colonne de dimension \(n\) avec la composante correspondant au terme égale à 1 et les autres composantes nulles. Pour passer à plusieurs termes, on multiplie \(\mathbf{V}_k^T\) par un vecteur colonne de dimension \(n\) avec des composantes non nulles pour tous les termes impliqués dans la requête. Afin de garder le même système de pondération que pour la matrice TF-IDF originale, \(\mathbf{M}\), on considère le poids de chaque terme de la requête égal à son IDF. Ce type de requête équivaut à l’ajout d’un nouveau document au corpus, document qui contient les termes de la requête, et ensuite chercher les documents les plus proches par la méthode présentée plus haut.

scala> :load topDocsForTerms.scala
scala> printTopDocsForTerms(Seq("birth", "control"))
scala> printTopDocsForTerms(Seq("kingdom", "island"))

Regardez l’implementation des methodes utilisées de la classe RunLSA et essayez de suivre leur fonctionnemment à partir des explications précédentes.

Bibliographie

Karau, H., A. Konwinski, P. Wendell et M. Zaharia, Learning Spark, O’Reilly, 2015.

Ryza, S., U. Laserson, S. Owen and J. Wills, Advanced Analytics with Spark, O’Reilly, 2010.