.. _chap-tpFouilleTexte: ################################################# Travaux pratiques - Fouille de données textuelles ################################################# .. only:: html .. container:: notebook .. image:: _static/zeppelin_classic_logo.png :class: svg-inline `Cahier Zeppelin `_ Références externes utiles : * `Documentation Spark `_ * `Documentation API Spark en Scala `_ * `Documentation langage Scala `_ ************* Introduction ************* **L'objectif** de cette séance de TP est d'apprendre à examiner, avec Spark, 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 termes présents dans le 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 inspirer pour votre projet. Création de l'environnement de travail ====================================== Exécutez les commandes suivantes pour créer l’environnement nécessaire (cela récupère une archive de texte de la Wikipedia anglophone). .. admonition:: Note Sous Windows, il faudra créer un répertoire ``tptexte`` avec un sous-répertoire ``data`` dans votre dossier de travail (par exemple, le dossier d'installation de Zeppelin). `Téléchargez `_ puis décompressez l'archive ``enwiki.xml.bz2`` (par exemple, avec 7-zip) dans le sous-répertoire ``data``. .. code-block:: bash %%bash mkdir -p tptexte/data cd tptexte/data wget -nc 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 : .. admonition:: Note Sous Windows, téléchargez les fichiers `lsa.jar `_ et `deps.zip `_ et décompressez ce dernier (dans le répertoire ``tptexte``). .. code-block:: bash %%bash cd tptexte wget -nc http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/lsa.jar wget -nc http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/deps.zip unzip deps.zip .. admonition:: Note Si le ``.jar`` n'avait pas été déjà disponible, il aurait été nécessaire de le créer, en installant d'abord Maven avec ``mvn package`` dans le dossiers ``deps`` (**n'exécutez pas cette commande** si vous avez récupéré déjà le ``.jar``). .. only:: not jupyter 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`` : .. code-block:: bash $ spark-shell --driver-memory 1g --jars lsa.jar .. only:: jupyter .. code-block:: scala %spark.dep z.load("tptexte/lsa.jar") Dans Spark, on commence par importer les paquetages nécessaires. .. admonition:: Note 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`` (Ctrl+D pour quitter). .. code-block:: scala import com.cloudera.datascience.lsa._ import com.cloudera.datascience.lsa.ParseWikipedia._ import com.cloudera.datascience.lsa.RunLSA._ import org.apache.spark.mllib.linalg._ import org.apache.spark.mllib.linalg.distributed.RowMatrix 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/``. Vous les trouverez dans l'archive à cette adresse: `http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/deps.zip `_ (il s'agit de l'archive ``deps.zip`` téléchargée tout à l'heure). .. admonition:: Remarque générale : Après avoir entré une commande (suivant le cas, soit dans la fenêtre terminal, soit dans Zeppelin ou ``spark-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 système de fichiers local. Nous allons charger en mémoire l’extrait de Wikipédia anglais contenu dans le fichier XML ``enwiki.xml`` (téléchargé précédemment). Ce fichier contient une collection d’articles représentés sous une forme structurée en XML. .. code-block:: scala val wikixmlfile = "tptexte/data/enwiki.xml" val sampleSize = 0.3 val xmlPages = ParseWikipedia.readFile(wikixmlfile, sc).sample(false, sampleSize, 11L) xmlPages.take(2) Ceci produit un *RDD* contenant des documents au format XML. Nous allons convertir ces articles au format texte brut en utilisant la fonction ``wikiXmlToPlainText`` du module ``ParseWikipedia`` : .. code-block:: scala val plainText = xmlPages.filter(_ != null).flatMap(ParseWikipedia.wikiXmlToPlainText) 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*. Par exemple, l’adjectif *petit* est la lemmatisation de 4 formes dites fléchies : *petit*, *petite*, *petits* et *petites*. Les mots vides (*stop words*) sont des mots non significants et très communs, généralement des articles et des pronoms (*la*, *le*, *un*, *du*, etc.). 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``) : .. code-block:: scala val stopWords = sc.broadcast(ParseWikipedia .loadStopWords("tptexte/deps/lsa/src/main/resources/stopwords.txt")).value val lemmatized = plainText.mapPartitions(iter => { val pipeline = ParseWikipedia.createNLPPipeline(); iter.map{ case(title, contents) => (title, ParseWikipedia.plainTextToLemmas(contents, stopWords, pipeline))}; }).cache() lemmatized.take(2) val filtered = lemmatized.filter(_._2.size > 1) .. admonition:: Question : Quel est le rôle de la dernière commande ? .. ifconfig:: tpscala in ('public') .. admonition:: 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 de 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. Nous pouvons voir quelques exemples de titres d'articles de notre corpus en créant un *RDD* qui ne contient que la première colonne et en tirer 10 lignes au hasard : .. code-block:: scala val titres = lemmatized.map(_._1) titres.takeSample(false, 10) 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 (cela peut toutefois réduire les capacités discriminantes des représentations ainsi obtenues). .. code-block:: scala val numTerms = 1000 // nombre de termes à garder (les plus fréquents) 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 : .. code-block:: 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 :math:`\mathbf{M}` des représentations vectorielles TF-IDF. MLlib contient une implémentation de SVD qui garde les :math:`k` plus grandes valeurs singulières et qui produit trois matrices :math:`\mathbf{U}`, :math:`\mathbf{S}` et :math:`\mathbf{V}` telles que :math:`\mathbf{M} \approx \mathbf{U}_k \cdot \mathbf{S}_k \cdot \mathbf{V}_k^T`. Si la matrice :math:`\mathbf{M}` est de taille :math:`m \times n` (:math:`m` documents, :math:`n` termes), alors : * :math:`\mathbf{U}_k` est une matrice :math:`m \times k` : ses colonnes forment une base orthonormale dans l'espace de dimension :math:`m` ; l'élément :math:`u_{ij}` de :math:`\mathbf{U}_k` indique « l'importance » du concept :math:`j` pour le document :math:`i` ; * :math:`\mathbf{S}_k` est une matrice diagonale :math:`k \times k` : les éléments sur la diagonale principale représentent l'importance de chaque concept extrait (son « pouvoir à expliquer les données ») ; * :math:`\mathbf{V}_k` est une matrice :math:`n \times k` : ses colonnes forment une base orthonormale dans l'espace de dimension :math:`n` ; l'élément :math:`v_{ij}` de :math:`\mathbf{V}_k` indique « l'implication » du mot (terme) :math:`i` dans le concept :math:`j`. La décomposition est paramétrée par :math:`k`, le nombre de concepts à garder. Si :math:`k = n` alors la décomposition est exacte (on retrouve la matrice :math:`\mathbf{M}` sans approximations). Normalement :math:`k \ll n` et :math:`\mathbf{U}_k \mathbf{S}_k \mathbf{V}_k^T` est une approximation de :math:`\mathbf{M}` qui est optimale par rapport à la norme L2 (perte quadratique minimale). .. code-block:: scala val mat = new RowMatrix(termDocMatrix) val k = 200 // nombre de valeurs singulières à garder val svd = mat.computeSVD(k, computeU = true) En utilisant cette décomposition, nous pouvons afficher les concepts importants à travers les termes qui les caractérisent et les documents dans lesquels ils se manifestent le plus : .. code-block:: scala val topConceptTerms = RunLSA.topTermsInTopConcepts(svd, 10, 10, termIds) val topConceptDocs = RunLSA.topDocsInTopConcepts(svd, 10, 10, docIds) 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``. .. admonition:: Question : Faites varier le paramètre ``k`` : 100, 400. Comparez les concepts trouvés dans ces différents cas. .. ifconfig:: tpscala in ('public') .. admonition:: 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. .. admonition:: 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. .. ifconfig:: tpscala in ('public') .. admonition:: 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 :math:`\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 :math:`\mathbf{U}_k \mathbf{S}_k \mathbf{V}_k^T` est strictement égale à la similarité cosinus entre les colonnes correspondantes de :math:`\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 :math:`\mathbf{V}_k \mathbf{S}_k` à norme 1 et ensuite multiplier la ligne correspondant à ce terme par toutes les autres lignes de :math:`\mathbf{V}_k \mathbf{S}_k` (les lignes de :math:`\mathbf{V}_k \mathbf{S}_k` sont les colonnes de la matrice transposée, :math:`\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. .. code-block:: scala val VS = RunLSA.multiplyByDiagonalMatrix(svd.V, svd.s) val normalizedVS = RunLSA.rowsNormalized(VS) var idTerms = collection.mutable.Map[String,Int]() for(pair <- termIds) idTerms(pair._2) = pair._1 RunLSA.printTopTermsForTerm(normalizedVS, "problem", idTerms, termIds) RunLSA.printTopTermsForTerm(normalizedVS, "mother", idTerms, termIds) 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 :math:`\mathbf{u}` correspondant au document dans la matrice :math:`\mathbf{U}_k`, la ligne :math:`\mathbf{v}` correspondant au terme dans la matrice :math:`\mathbf{V}_k`, et ensuite calculer le produit :math:`\mathbf{u} \mathbf{S}_k \mathbf{v}^T`. Pour déterminer la similarité d'un terme à chacun des documents on calcule donc :math:`\mathbf{U}_k \mathbf{S}_k \mathbf{v}^T`. Dans l'autre sens, on peut déterminer les similarités entre un document :math:`\mathbf{u}` et tous les termes par le produit :math:`\mathbf{u} \mathbf{S}_k \mathbf{V}_k^T`. .. code-block:: scala val US = RunLSA.multiplyByDiagonalMatrix(svd.U, svd.s) RunLSA.printTopDocsForTerm(US, svd.V, "problem", idTerms, docIds) RunLSA.printTopDocsForTerm(US, svd.V, "mother", idTerms, docIds) RunLSA.printTopDocsForTerm(US, svd.V, "africa", idTerms, docIds) Trouver des documents similaires à un autre document ---------------------------------------------------- La matrice :math:`\mathbf{U}_k` décrit chaque document par les :math:`k` concepts trouvés par la SVD. Pour trouver des documents similaires à un autre document, on pondère chaque colonne de la matrice :math:`\mathbf{U}_k` par les valeurs singulières correspondantes (trouvées sur la diagonale de la matrice :math:`\mathbf{S}_k`) en faisant le produit :math:`\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. .. code-block:: scala val normalizedUS = RunLSA.rowsNormalized(US) var idDocs = collection.mutable.Map[String,Long]() for(pair <- docIds) idDocs(pair._2) = pair._1 RunLSA.printTopDocsForDoc(normalizedUS, "P versus NP problem", idDocs, docIds) RunLSA.printTopDocsForDoc(normalizedUS, "Commonwealth", idDocs, docIds) .. admonition:: Note Si vous obtenez une erreur ``java.util.NoSuchElementException: key not found``, c'est que le titre d'article que vous cherchez ne fait pas partie de votre corpus (cela peut arriver si vous avez changé la *seed* plus haut). Dans ce cas, choisissez un autre titre d'article. 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 :math:`\mathbf{V}_k`. Cela revient à multiplier :math:`\mathbf{V}_k^T` par un vecteur colonne de dimension :math:`n` avec la composante correspondant au terme égale à 1 et les autres composantes nulles. Pour passer à plusieurs termes, on multiplie :math:`\mathbf{V}_k^T` par un vecteur colonne de dimension :math:`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, :math:`\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. Nous créeons une fonction ``printTopDocsForTerms`` qui permet d'obtenir les documents qui représentent le mieux une série de mots : .. code-block:: scala def termsToQueryVector( terms: Seq[String], idTerms: Map[String, Int], idfs: Map[String, Double]): BSparseVector[Double] = { val indices = terms.map(idTerms(_)).toArray val values = terms.map(idfs(_)).toArray new BSparseVector[Double](indices, values, idTerms.size) } def topDocsForTermQuery( US: RowMatrix, V: Matrix, query: BSparseVector[Double]): Seq[(Double, Long)] = { val breezeV = new BDenseMatrix[Double](V.numRows, V.numCols, V.toArray) val termRowArr = (breezeV.t * query).toArray val termRowVec = Matrices.dense(termRowArr.length, 1, termRowArr) val docScores = US.multiply(termRowVec) val allDocWeights = docScores.rows.map(_.toArray(0)). zipWithUniqueId allDocWeights.top(10) } def printTopDocsForTerms(terms: Seq[String]) { val queryVec = termsToQueryVector(terms, idTerms.toMap, idfs.toMap) printIdWeights(topDocsForTermQuery(US, svd.V, queryVec), docIds) } .. code-block:: scala printTopDocsForTerms(Seq("birth", "control")) 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.