Brevet FR3007164A1 — publié le 20141219

PROCEDE DE CLASSIFICATION THEMATIQUE AUTOMATIQUE D'UN FICHIER DE TEXTE NUMERIQUE [1] DOMAINE TECHNIQUE DE L'INVENTION [2] L'invention porte sur un procédé de classification thématique automatique d'un fichier de texte numérique. L'invention concerne ainsi le domaine de l'informatique appliquée au langage. [3] ARRIERE PLAN TECHNOLOGIQUE [4] La catégorisation est le processus qui consiste à associer à un document donné une ou plusieurs catégories (ou étiquettes) prédéfinies. L'objectif d'une catégorisation automatique de textes est d'inférer automatiquement une classification en analysant son contenu. La nature même des catégories prédéfinies varie en fonction des objectifs ; il peut s'agir d'identifier la langue du texte, les thématiques abordées, mais aussi par exemple la priorisation souhaitée pour le traitement du document, ou encore les sentiments exprimés. La difficulté de la tâche varie selon le type et la longueur du document: un tweet, un email, un article de presse, un document scientifique ou un avis de consommateur ne s'analysent généralement pas de la même façon. [5] En outre, la catégorisation d'un fichier de texte numérique nécessite généralement un investissement important en amont avec une adaptation qui dépend du domaine d'application. En effet, les étapes opérationnelle préalables à l'apprentissage d'une classification sont le plus souvent : i) la constitution du plan de classement, ii) l'annotation manuelle du corpus d'apprentissage, iii) la définition de caractéristiques linguistiques utilisées par l'algorithme d'apprentissage. Ces opérations peuvent être consommatrices en temps et leur résultat n'est généralement applicable qu'au domaine particulier concerné par les catégories prédéfinies, et aux types de documents représentatifs du corpus d'apprentissage. [6] Des procédés d'apprentissage automatique à la catégorisation sont connus. Ainsi, le document Sebastiani, 2002, "Machine learning in automated Text Categorizatio, in ACM, Computing Surveys, Vol. 34, N°1, pages 1-47, fournit un tableau comparatif des méthodes et applications possibles. Le document Dasari, 2012, "Text Categorization and Machine Learning Methods: Current State of the Art", GJCST, Vol. 12, N°11, complète cet état de l'art avec des approches plus récentes et mesure les progrès accomplis en 10 ans. [07] Une question se pose à propos des plans de classement, généralement définis pour un domaine particulier. En effet, il faut pouvoir savoir quel jeu de catégories prédéfini serait suffisamment couvrant pour catégoriser d'une façon raisonnablement générique un texte tout venant. [08] Les catégories de la base de données en ligne "Wikipédia" sont récemment apparues comme une possibilité de tel plan de classement universel. Le document Schônhofer, P, 2009, "Identifying document topics using the Wikipedia category network", Web Intelligence and Agent Systems, Vol. 7, N°2, pages 195-207, propose ainsi de les L'User pour effectuer une catégorisation thématique avec un algorithme simple qui se contente d'exploiter les titres et les catégories des articles. Une idée proche est présentée dans le document Yun et al., 2011, "Topic Extraction Based on Wikipedia Category", Actes de Computational Sciences and Optimization (CSO). Les catégories Wikipédia servent aussi de référence dans l'ontologie YAGO divulguée par le document SUCHANEK F.,et al., "YAGO: a core of semantic knowledge", WWW 2007, pp. 697-706. [9] Toutefois, les méthodes connues proposent un classement thématique sujet aux erreurs de catégorisation du fait du traitement brut des données de catégories de la base de données Wikipédia. Il existe donc le besoin d'une méthode plus robuste et précise que les méthodes existantes. [10] OBJET DE L'INVENTION [11] L'invention vise à répondre à ce besoin en proposant un procédé de classification thématique d'un fichier de texte numérique à partir d'une base de données encyclopédique comportant un graphe de catégories défini par un ensemble de noeuds de catégories à chacun desquels est rattaché au moins un article, un noeud dit de catégorie générique étant relié à zéro, un, ou à plusieurs noeuds de catégorie plus spécifique, caractérisé en ce que ledit procédé comporte, au cours d'une phase d'apprentissage permettant d'élaborer un modèle de classification thématique, l'étape de regrouper, pour chaque noeud de catégorie, tous les articles rattachés directement audit noeud de catégorie de manière à obtenir pour chaque noeud de catégorie un ensemble de mots dit "sac de mots", déterminer un vecteur dit vecteur termes-fréquences caractéristique du noeud de catégorie correspondant au nombre d'occurrences de chaque mot dans le sac de mots, combiner sur chaque noeud de catégorie le vecteur termes-fréquences qui lui est directement relié avec des vecteurs termes-fréquences de noeuds plus spécifiques, et en ce qu'il comporte, lors d'une phase de production, l'étape de calculer le vecteur termes-fréquences dudit fichier de texte numérique et de retenir dans ledit modèle de classification thématique N noeuds de catégorie ayant les vecteurs termes-fréquences les plus proches du vecteur termes-fréquences du fichier de texte numérique. [012] L'invention permet ainsi de traiter un fichier de texte numérique tout-venant d'une façon générique et automatique, c'est-à-dire sans imposer préalablement une phase d'apprentissage spécifique au domaine ou à la langue du document. L'invention permet d'associer finement à un texte tout-venant écrit dans une langue donnée des catégories dans cette langue de préférence représentées sous forme d'un graphe. [13] L'utilisation d'un index inter-langues de la base de données pourra permettre dans certaines mises en oeuvre d'obtenir un sous-ensemble de ces catégories dans d'autres langues que celle du texte d'origine. Il sera ainsi possible d'autoriser alors une recherche cross-langue des documents associés à une thématique donnée. [14] Selon une mise en oeuvre, le procédé comporte en outre l'étape de reconstituer une représentation informatique sous forme de graphe des noeuds de catégorie retenus. [15] Selon une mise en oeuvre, le procédé comporte l'étape de supprimer des éventuels cycles du graphe de catégories pour obtenir un graphe orienté acyclique. [16] Selon une mise en oeuvre, lors de la phase d'apprentissage, un noeud de catégorie auquel est associé un nombre d'articles inférieur à un seuil est fusionné avec un noeud de catégorie plus générique et les articles qui lui étaient directement reliés sont rattachés audit noeud de catégorie plus générique. [17] Selon une mise en oeuvre, la combinaison consiste à sommer le vecteur termes-fréquences de chaque noeud de catégorie, dit noeud cible, avec des vecteurs termes-fréquences de noeuds de catégorie plus spécifiques directement reliés audit noeud cible, dits noeuds de sous- catégories, lesdits noeuds de sous-catégories étant pondérés. [18] Selon une mise en oeuvre, pour un noeud cible ayant M noeuds de sous-catégories, chaque vecteur termes-fréquences d'un noeud de sous-catégorie est pondéré avec un facteur 1/(M+1). [19] Selon une mise en oeuvre, le ou les vecteurs termes-fréquences 15 des N noeuds de catégorie les plus proches du vecteur termes-fréquences du fichier de texte numérique sont ceux maximisant le produit scalaire avec le vecteur termes-fréquences du fichier de texte numérique. [20] Selon une mise en oeuvre, ledit produit scalaire est pondéré avec des techniques de type TF.IDF et/ou Okapi BM25. 20 [021] Selon une mise en oeuvre, le procédé comporte l'étape d'établir une classification du fichier de texte numérique en catégories dans une langue autre que celle du fichier de texte numérique au moyen d'un index inter-langues associant à un noeud de catégorie ses traductions en d'autres langues. 25 [022] Selon une mise en oeuvre, le procédé comporte l'étape de supprimer les noeuds de catégorie de faible pertinence ayant un degré inférieur ou égal à un seuil. [023] Selon une mise en oeuvre, la base de données encyclopédique est la base de données "Wikipedia" (marque déposée). [24] Selon une mise en oeuvre, la base de données encyclopédique consiste en des avis de consommateurs regroupés par catégories. [25] BREVE DESCRIPTION DES FIGURES [26] L'invention sera mieux comprise à la lecture de la description qui suit et à l'examen des figures qui l'accompagnent. Ces figures ne sont données qu'à titre illustratif mais nullement limitatif de l'invention. [27] La figure 1 est une représentation schématique des différents éléments intervenant dans la mise en oeuvre du procédé de classification automatique selon l'invention; [028] La figure 2 montre un diagramme des différentes étapes du procédé de classification automatique selon l'invention; [029] Les figures 3a à 3f représentent les différentes opérations de traitement réalisées sur un graphe de catégories lors d'une phase d'apprentissage du procédé de classification automatique selon l'invention; [030] Les figures 4a à 4d représentent les différentes opérations réalisées sur un graphe de catégories lors d'une phase de production du procédé de classification automatique selon l'invention. [031] Les éléments identiques, similaires ou analogues conservent la même référence d'une figure à l'autre. [032] DESCRIPTION D'EXEMPLES DE REALISATION DE L'INVENTION [033] Comme cela est montré sur la figure 1, le procédé de classification thématique selon l'invention permet de fournir de manière automatique une liste de catégories pertinentes correspondant à un fichier de texte numérique 1. La liste de catégories pertinentes est affichée de préférence sous forme d'une représentation informatique d'un graphe G1 dans la langue L1 correspondant à la langue du fichier de texte numérique 1. Ce graphe G1 pourra, le cas échéant, être transposé dans plusieurs langues L2, L3, etc.. pour obtenir les représentations correspondantes G2, G3,.... [34] A cet effet, un classifieur 2 prenant de préférence la forme d'un moteur de recherche utilise un modèle de classification thématique 3 fournissant la liste de catégories pertinentes eu égard au fichier 1 analysé. [35] Plus précisément, le modèle de classification thématique 3 est 5 élaboré par apprentissage sur une base de données encyclopédique 5 organisée en catégories auxquelles sont rattachées des articles. Cette base de données est en l'occurrence la base de données "Wikipédia" (marque déposée) traitée sous forme de fichier "dump.xml" par le module 8, mais pourrait en variante être toute autre base de données équivalente. 10 Alternativement, la base de données encyclopédique consiste en des avis de consommateurs regroupés par catégories. [36] Comme montré sur la figure 3a, la base de données encyclopédique 5 comporte un graphe G de catégories représenté de manière simplifiée défini par un ensemble de noeuds de catégories Ci à 15 chacun desquels est rattaché au moins un article Ai.j, un noeud dit de catégorie générique étant relié par un arc à zéro, un, ou à plusieurs noeuds de catégorie plus spécifique que la catégorie générique. Dans un exemple, la catégorie "chaussures" est plus générique que la catégorie "bottes" ou "chaussures de sport" qui en sont des catégories spécifiques. 20 [037] En l'occurrence, le noeud de catégorie générique Cl est relié aux noeuds de catégorie spécifiques C2, C3 et C4, lesquels constituent des noeuds de catégorie générique par rapport aux noeuds de catégorie spécifiques C5, C6, C7 et C8. Pour un noeud de catégorie Ci donné, un arc dit "entrant" provient d'un noeud de catégorie plus générique, tandis qu'un arc 25 dit "sortant" est relié à un noeud de catégorie plus spécifique. Dans l'exemple représenté, on aura donc compris que l'on va du noeud de catégorie le plus générique au noeud de catégorie le plus spécifique lorsqu'on se déplace du haut vers le bas. Toutefois, cette représentation est purement arbitraire et aurait pu être inversée. 30 [038] Au cours d'une phase d'apprentissage PA permettant d'élaborer le modèle de classification thématique 3, les cycles du graphe de catégories sont supprimés dans une étape 101 pour obtenir un graphe G orienté acyclique (DAG-Directed Acyclic Graph) et éviter ainsi les boucles infinies. [39] A cette fin, on met de préférence en oeuvre l'algorithme décrit dans le document Tarjan (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing, Vol. 1, N°2, p. 146-160 qui détecte les zones fortement connexes d'un graphe orienté avec une exploration en profondeur à partir des racines c'est-à-dire des noeuds de catégorie Ci dépourvus d'arc entrant. On supprime ensuite localement un arc jusqu'à supprimer tous les cycles. Le choix de l'arc à supprimer est arbitraire et consiste en l'occurrence à sélectionner ceux qui relient les noeuds de catégorie Ci les plus bas dans la hiérarchie. Ainsi, dans l'exemple représenté, on supprime le cycle entre les noeuds de catégorie C7 et Cl pour obtenir le graphe G de la figure 3b. [40] Par ailleurs, au cours d'une étape 102, un noeud de catégorie Ci auquel est associé un nombre d'articles inférieur à un seuil est fusionné avec le noeud de catégorie Ci plus générique et les articles Ai.j qui lui étaient directement reliés sont rattachés audit noeud de catégorie Ci plus générique. Dans l'exemple représenté aux figures 3c et 3d, le seuil d'articles Ai.j rattaché à un noeud de catégorie Ci valant trois, le noeud de catégorie C8 qui contient trop peu d'articles A8.1, A8.2, A8.3 est fusionné avec son noeud catégorie plus générique C4 et les articles A8.1-A8.3 qui lui étaient directement reliés remontent audit noeud de catégorie plus générique C4. [041] Pour chaque noeud de catégorie, tous les textes des articles rattachés directement au noeud de catégorie sont regroupés dans une étape 103 de manière à obtenir pour chaque catégorie un ensemble de mots dit "sac de mots" ("bag of words" en anglais). [42] Un vecteur Vi dit vecteur termes-fréquences caractéristique du noeud de catégorie Ci correspondant au nombre d'occurrences de chaque mot dans le "sac de mots" est déterminé dans une étape 104. Ainsi, comme cela est représenté sur la figure 3e par exemple, le vecteur V4 associé au noeud de catégorie C4 est défini par un terme tl ayant une occurrence f4.1, le terme t2 ayant une occurrence f4;2, le terme t3 ayant une occurrence f4.3, etc... le terme tk ayant une occurrence f4.k. [43] Au préalable, les textes des articles auront pu être traités par exemple via le moteur de recherche appelé "Lucene" selon une séquence d'opérations classiques en recherche d'informations, telles que la segmentation du texte en mots, la normalisation de leur casse, la suppression des diacritiques, la suppression des mots grammaticaux ("stop words" comme les articles notamment), la racinisation (stemming) et le comptage des termes. L'un des intérêts du moteur "Lucene" est de proposer en standard ces opérations pour une trentaine de langues. [44] On effectue ensuite l'exploration du graphe G des racines les plus génériques vers les feuilles les plus spécifiques dépourvues d'arc sortant, et lors de la remontée récursive, on combine dans une étape 105 sur chaque noeud de catégorie Ci le vecteur termes-fréquences Vi qui lui est directement relié avec des vecteurs termes-fréquences de noeuds de catégorie Ci plus spécifiques. L'objectif est d'associer à chaque noeud de catégorie Ci un vecteur termes-fréquences représentatif. La combinaison est effectuée en sorte que les textes qui sont directement rattachés au noeud de la catégorie constituent une contribution majoritaire, tandis que les textes rattachés aux catégories plus spécifiques constituent une contribution minoritaire. En l'occurrence, le vecteur termes-fréquences Vi de chaque noeud de catégorie, dit noeud cible, est sommé avec des vecteurs termes-fréquences Vi de noeuds de catégorie Ci plus spécifiques directement reliés audit noeud cible, dits noeuds de sous-catégories Ci, lesdits noeuds de sous-catégories Ci étant pondérés. On obtient alors des vecteurs termes-fréquences dits vecteurs optimisés Vi'. [45] De préférence, pour un noeud cible ayant M noeuds de sous-catégorie, chaque vecteur termes-fréquences d'un noeud de sous-catégorie est pondéré avec un facteur d'amortissement (par exemple 1/(M+1)). Ainsi, comme cela est illustré sur la figure 3f, au cours d'une première étape de la remontée récursive le vecteur termes-fréquences V4 est remplacé par le vecteur termes-fréquences V4' = V4 + 0.5*V7. On précise que le vecteur V7 est pondéré par 0.5 car on a M=1 noeuds de sous-catégories en dessous de C4; en sorte que le facteur de combinaison linéaire vaut 1/((M=1)+1)= 0.5. On répète ainsi les opérations jusqu'à la remontée complète du graphe. [46] Les catégories Ci et leur vecteur termes-fréquences Vi' optimisé sont indexés dans un index de recherche 10 stocké dans le modèle de classification 3. [047] Lors d'une phase de production PP, on calcule au cours d'une étape 201 le vecteur termes-fréquences V du fichier de texte numérique 1 à catégoriser de la même façon que l'on avait calculé le vecteur termes-fréquences Vi des articles Ai.j directement rattachés à une catégorie Ci. [048] La classification effective est effectuée en réalisant dans une étape 202 une recherche dans l'index de recherche 10 précédemment constitué au moyen du moteur de recherche 2 qui renvoie alors la liste "à plat" des N catégories les plus pertinentes, c'est-à-dire celles qui ont un vecteur termes-fréquences optimisé Vi' le plus proche du vecteur termes-fréquences V du texte. N qui pourra être fixé par l'utilisateur est compris typiquement entre 5 et 30. Par liste "à plat" de catégorie, on entend les catégories qui ne sont pas hiérarchisées sous forme de graphe dans la mesure où les catégories ne sont pas hiérarchisées en graphe dans l'index de recherche 10. [049] De préférence, on considère que les vecteurs termes-fréquences optimisés Vi' des catégories les plus proches du vecteur termes-fréquences V du fichier de texte numérique 1 sont ceux qui maximisent le produit scalaire entre le vecteur termes-fréquences V et le vecteur termes-fréquences optimisé Vi' d'une catégorie Ci. De préférence, le produit scalaire est pondéré avec des techniques de type TF.IDF et/ou Okapi BM25. [050] Ainsi, comme cela est représenté sur la figure 4a, le fichier de texte numérique 1 sera associé aux noeuds de catégorie C3, C4, C7, C1, C2, le paramètre "p" correspondant au niveau de pertinence de chaque noeud de catégorie. [051] Dans une étape 203, le graphe local montré sur la figure 4b est reconstitué à partir des catégories retenues par le moteur de recherche 2 en utilisant la forme du graphe des catégories. Cette forme du graphe des catégories correspond à l'information 11 des arcs reliant les noeuds de catégorie stockée préalablement dans le modèle de classification au moment de la création de l'index de recherche 10. [052] Dans le graphe Gl, il sera possible d'adapter la couleur d'affichage des noeuds de catégorie Ci à leur pertinence "p", les noeuds de catégorie les plus pertinents présentant un affichage foncé tandis que les moins pertinents présentent un affichage plus clair. [53] Dans une étape 204, on utilise la topologie du graphe pour supprimer les noeuds de catégorie Ci de faible pertinence peu reliés aux autres, comme par exemple les noeuds de degré 1, c'est-à-dire ceux qui comporte un seul ou aucun arc. Dans l'exemple de la figure 4c, on a supprimé ainsi le noeud de catégorie C3. [54] Si la base de données encyclopédique 5 contient un index inter-langue 12 qui associe à un noeud de catégorie Ci ses traductions Ci', Ci", etc... en d'autres langues, l'exploitation de cet index 12 par le modèle de classification 3 permet directement d'établir dans une étape une classification du fichier de texte 1 en catégories d'une autre langue L2-L3. [55] Ainsi, comme montré sur la figure 4d, les noeuds-catégories C1' C2' C4' du graphe G2 correspondent à la traduction dans une autre langue L2 des noeuds de catégorie initiaux C1, C2, C4 dans la langue Ll tandis qu'il n'existe pas de correspondance pour le noeud de catégorie C7 dans l'autre langue L2. En effet, il est à noter que la complétude de l'index inter-langues 12 est aléatoire et varie en fonction des noeuds de catégorie Ci. Pour celles jugées importantes par les utilisateurs, des liens sont fournis vers un grand nombre de langues; en revanche, aucun lien n'existera parfois pour une catégorie trop fine ou d'intérêt secondaire. [56] L'homme du métier pourra bien entendu apporter des modifications au procédé ci-dessus. Ainsi, en variante, le classifieur pourra être basé sur l'utilisation de techniques notamment de type HMM (Hiden Markov Model) ou SVM (Support Vector Machine) ou maximum d'entropie ou réseau de neurones. REVENDICATIONS1. Procédé de classification thématique automatique d'un fichier de texte numérique (1) à partir d'une base de données encyclopédique (5) comportant un graphe de catégories (G) défini par un ensemble de noeuds de catégories (Ci) à chacun desquels est rattaché au moins un article (Ai.j), un noeud dit de catégorie générique étant relié à zéro, un, ou à plusieurs noeuds de catégorie plus spécifique, caractérisé en ce que ledit procédé comporte, au cours d'une phase d'apprentissage (PA) permettant d'élaborer un modèle de classification thématique (3), l'étape de regrouper, pour chaque noeud de catégorie (Ci), tous les articles (Ai.j) rattachés directement audit noeud de catégorie (Ci) de manière à obtenir pour chaque noeud de catégorie (Ci) un ensemble de mots dit "sac de mots", déterminer un vecteur (Vi) dit vecteur termes-fréquences caractéristique du noeud de catégorie (Ci) correspondant au nombre d'occurrences de chaque mot dans le sac de mots, combiner sur chaque noeud de catégorie le vecteur (Vi) termes- fréquences qui lui est directement relié avec des vecteurs termes-fréquences de noeuds plus spécifiques, et en ce qu'il comporte, lors d'une phase de production, l'étape de calculer le vecteur (V) termes-fréquences dudit fichier de texte numérique (1) et de retenir dans ledit modèle de classification thématique (3) N noeuds de catégorie ayant les vecteurs (Vi') termes- fréquences les plus proches du vecteur (V) termes-fréquences du fichier de texte numérique (1). 2. Procédé selon la revendication 1, caractérisé en ce qu'il comporte en outre l'étape de reconstituer une représentation informatique sous forme de graphe (G1) des noeuds de catégorie retenus. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'il comporte l'étape de supprimer des éventuels cycles du graphe de catégories (G) pour obtenir un graphe orienté acyclique. 4. Procédé selon l'une des revendications 1 à 3, caractérisé en ce que lors de la phase d'apprentissage, un noeud de catégorie (Ci) auquel est associé un nombre d'articles inférieur à un seuil est fusionné avec un noeud de catégorie plus générique et les articles (Ai.j) qui lui étaient directement reliés sont rattachés audit noeud de catégorie plus générique. 5. Procédé selon l'une des revendications 1 à 4, caractérisé en ce que la combinaison consiste à sommer le vecteur (Vi) termes-fréquences de chaque noeud de catégorie (Ci), dit noeud cible, avec des vecteurs termes-fréquences de noeuds de catégorie (Ci) plus spécifiques directement reliés audit noeud cible, dits noeuds de sous-catégories, lesdits noeuds de sous- catégories étant pondérés. 6. Procédé selon la revendication 5, caractérisé en ce que pour un noeud cible ayant M noeuds de sous-catégories, chaque vecteur (Vi) termes- fréquences d'un noeud de sous-catégorie est pondéré avec un facteur 1/(M+1). 7. Procédé selon l'une des revendications 1 à 6, caractérisé en ce que le ou les vecteurs (Vi') termes-fréquences des N noeuds de catégorie les plus proches du vecteur termes-fréquences du fichier de texte numérique (1) sont ceux maximisant le produit scalaire avec le vecteur termes-fréquences (V) du fichier de texte numérique (1). 8. Procédé selon la revendication 7, caractérisé en ce que ledit produit scalaire est pondéré avec des techniques de type TF.IDF et/ou Okapi BM25. 9. Procédé selon l'une des revendications 1 à 8, caractérisé en ce qu'il comporte l'étape d'établir une classification du fichier de texte numérique (1) en catégories dans une langue autre que celle du fichier de texte numérique (1) au moyen d'un index inter-langues (12) associant à un noeud de catégorie (Ci) ses traductions en d'autres langues. 10. Procédé selon la revendication 2, caractérisé en ce qu'il comporte l'étape de supprimer les noeuds de catégorie (Ci) de faible pertinence ayant un degré inférieur ou égal à un seuil. 11. Procédé selon l'une des revendications précédentes, caractérisé en ce que la base de données encyclopédique (5) est la base de données "Wikipedia" (marque déposée). 12. Procédé selon l'une des revendications 1 à 10, caractérisé en ce 30 que la base de données encyclopédique (5) consiste en des avis de consommateurs regroupés par catégories.