Dans cet article nous présentons un automate cellulaire (Class_AC) pour résoudre un problème de text mining en l'occurrence la classification non supervisée (Clustering). Avant de procéder à l'expérimentation par l'automate cellulaire, nous avons vectorisés nos données en procédant à l'indexation des documents textuels provenant de la base de donnée REUTERS 21578 par l'approche Wordnet. L'automate que nous proposons dans cet article est une grille de cellules de structure plane avec un voisinage découlant de cette structure (planaire). Trois fonctions de transitions ont servi à faire varier l'automate ayant quatre états pour chaque cellule. Les résultats obtenus montrent que la machine virtuelle à calcul parallèle (Class_AC) regroupe efficacement des documents similaires à un seuil prés.
Le biomimétisme dans un sens littéraire est l'imitation de la vie. La biologie a toujours été une source d'inspiration pour les chercheurs dans différents domaines. Ces derniers ont trouvé un modèle presque idéal dans l'observation des phénomènes naturels et leur adaptation en vue de résoudre des problèmes. Parmi ces modèles on trouve les algorithmes génétiques, les colonies de fourmis, les essaims particulaires, nuages des insectes volants [Mon 2003] et bien entendu les automates cellulaires qui sont l'objet de notre étude. Les premières approches citées sont des méthodes reconnues et largement étudiées par contre les automates cellulaires sont des méthodes très peu utilisées et notamment dans le domaine de la classification non supervisée et ça a été notre motivation quant à l'utilisation de cette méthode dans ce domaine. Cette méthode est connue de la communauté scientifique comme étant un outil d'implémentation de machine et autre (Un Automate Cellulaire (AC) est avant tout une machine formelle) par contre dans cet article la méthode des automates cellulaires est utilisée comme étant une méthode biomimétique. Depuis les années 50, le biomimétisme n'a cessé de progresser de façon constante et est un des principaux enjeux de la recherche actuelle.
Le biomimétisme est une pratique scientifique consistant à imiter, ou à s'inspirer de systèmes naturels, ou vivants. Parmi les exemples de ce domaine, on retrouve entre autres : formes de poissons pour l'aérodynamisme de voitures, ou autres véhicules, ou encore l'algorithme de colonies de fourmis pour la recherche du plus court chemin dans un graphe... Le Text mining, est l'ensemble des techniques et des méthodes destinées au traitement automatique des données textuelles en langage naturel, est une analyse multidimensionnelle des données textuelles qui vise à analyser et découvrir des connaissances et des relations à partir des documents disponibles. Dans le text mining les similarités sont utilisées pour produire des représentations synthétiques de vaste collection de documents. Le text mining comprend une succession d'étapes permettant de passer des documents au texte, du texte au nombre, du nombre à l'analyse, de l'analyse à la prise de décision. Nous commençons par un état de l'art, les techniques d'indexations des documents utilisées, une description générale de l'automate cellulaire pour le clustering, des résultats et nous donnerons une conclusion et les perspectives.
Pour mettre en oeuvre des méthodes de classification il faut faire un choix d'un mode de représentation des documents [Seb 2002], car il n'existe actuellement aucune méthode d'apprentissage capable de représenter directement des données non structurées (textes). Ensuite, il est nécessaire de choisir une mesure de similarité et enfin, de choisir un algorithme de classification non supervisée.
a. Représentation des documents textuels Un document (texte) di est représenté par un vecteur numérique de la façon suivante : di = (V 1i , V 2i , ..., V | T | i ) Où T est l'ensemble des termes (ou descripteurs) qui apparaissent au moins une fois dans le corpus. (|T| est la taille du vocabulaire), et V ki représente le poids (ou la fréquence). La représentation la plus simple des documents textuels est appelé «représentation sac de mots » [Aas 1999], elle consiste à transformer des textes en vecteurs où chaque élément représente un mot. Cette représentation de textes exclut toute forme d'analyse grammaticales et de toute notion de distance entre les mots. Une autre représentation, appelée "sac de phrases", assure une sélection de phrases (séquences de mots dans les textes, et non pas le lexème "phrases"), en favorisant ceux qui sont susceptibles de porter une signification. Logiquement, une telle représentation doit fournir de meilleurs résultats que ceux obtenus par la représentation "sac de mots". Une autre méthode pour la représentation des textes est celle basée sur les techniques de lemmatisation et consiste à chercher la racine lexicale d'un terme [Sah 1999], par exemple, la forme de l'infinitif singulier pour les verbes et les noms. Une autre méthode de représentation, qui a plusieurs avantages (principalement, cette méthode traite les documents textuels indépendamment de la langue utilisée), est basée sur les "n-grammes" (un "n-gramme" est une séquence de n caractères consécutifs).
Il existe différentes méthodes pour calculer le poids V ki sachant que, pour chaque terme, il est possible de calculer non seulement sa fréquence dans le corpus, mais aussi le nombre de documents contenant ce terme. Ce sont là des articles les plus en vus pour l'inspiration de notre travail et surtout celui de la classification de données par automate cellulaire car d'autres travaux non cités dans cet article on fait objet de recherches bibliographiques mais cités en références.
Nous avons utilisés dans notre expérimentation le corpus REUTERS 21578 qui représente une base de données de dépêches d'information en langue anglaise. Ainsi pour faire du clustering des documents textuels on doit faire un certain traitement pour vectoriser (numériser) nos textes (sans perdre la sémantique) et appliquer ensuite notre automate cellulaire. La première étape de l'indexation est le prétraitement qui consiste à éliminer tout symbole qui ne correspond pas à une lettre de l'alphabet (points, virgules, traits d'union, chiffres etc.). Cette opération est motivée par le fait que ces caractères ne sont pas liés au contenu des documents et ne change rien au sens s'ils sont omis et par conséquent ils peuvent être négligés. La deuxième étape est appelée stopping qui correspond à la suppression de tous les mots qui sont trop fréquents (ils n'aident donc pas à distinguer entre les documents) ou jouent un rôle purement fonctionnel dans la construction des phrases (articles, prépositions, etc.). Le résultat du stopping est que le nombre de mots dans la collection, ce qu'on appelle la masse des mots, est réduit en moyenne de 50%. Les mots à éliminer, connus comme stopwords, sont récoltés dans la stoplist qui contient en général entre 300 et 400 éléments puis vient l'étape du stemming qui consiste à remplacer chaque mot du document par sa racine comme par exemple : national, nationalité et nationalisation sont remplacés par leur racine « national » et les verbes conjugués par leur infinitifs. Le stemming n'a pas d'impact sur la masse des mots, mais réduit de 30% en moyenne la taille du document. Nous avons utilisés l'algorithme de PORTER pour remédier à cette étape. Ensuite nous avons la lemmatisation en utilisant l'approche Wordnet qui représente une base de donnée lexicale, un dictionnaire informatisé développée par des linguistes. Les mots dans WORDNET sont représentés par leur forme canonique ou encore appelé lemme. Cette étape est utilisée pour préparer la suivante qui est l'étape cruciale de l'indexation à savoir la vectorisation (numérisation). La lemmatisation consiste à remplacer chaque mot du document par son synset (synonyme dans la base lexicale). Nous avons utilisés WORDNET comme base de donnée lexicale (car REUTERS 21578 est un corpus de dépêches en anglais). La vectorisation est réalisé par la méthode TF-IDF (Term Frequency / Inverse Document Frequency) qui est dérivé d'un algorithme de recherche d'information. L'idée de base est de représenter les documents par des vecteurs et de mesurer la proximité entre documents par l'angle entre les vecteurs, cet angle étant donc supposé représenter une distance sémantique. Le principe est de coder chaque élément du sac de mot par un scalaire (nombre) appelé tfidf pour donner un aspect mathématique aux documents textes. où :
• tf(i,j) est le term Frequency : fréquence du terme ti dans le document dj • idf(i) est l'inverse document frequency : le logarithme du rapport entre le nombre N de documents dans le corpus et le nombre N i de documents qui contiennent le terme ti . Un document d i du corpus après vectorisation est : d i = (x 1 ,x 2 ,…….,x m ) où m est le nombre de mot du i éme sac de mot et x j est son tf-idf Ce schéma d'indexation donne plus de poids aux termes qui apparaissent avec une haute fréquence dans peu de documents. L'idée sous-jacente est que de tels mots aident à discriminer entre textes ayant différent sujet. Le tf-idf a deux limites fondamentales : La première est que les documents plus longs ont typiquement des poids plut forts parce qu'ils contiennent plus de mots, donc « les term frequencies » tendent à être plus élevées. La deuxième est que la dépendance de la « term ( , ) .
( ) ( , ). lo g
-Indexer les documents du corpus à classifier.
-Vectoriser chaque document texte du corpus par la méthode TF-IDF.
-Calculer la matrice de similarité à partir des vecteurs trouvés : sim(i,j)=D(d i ,d j ).
-Initialiser toutes les cellules de l'automate à l'état « Morte » (état=0).
-Répéter (à chaque instant t)
-Pour chaque cellule de l'automate faire Si cellule est morte Alors Si une cellule est isolée alors inchangé (Reste isolée) A chaque itération de l'algorithme, les cellules vont changés leurs état selon les de transition définies par l'automate cellulaire qui vont tendre à regrouper des états similaires pour les cellules actives (contenant l'index des documents).La classification est recouvrante (Les données peuvent apparaître plusieurs fois dans la grille).
Après expérimentation de l'algorithme Class_AC, sur des documents issus du corpus Reuters 21578, nous avons obtenu les résultats suivants en nombre de classes et pureté des clusters. En ce qui concerne la pureté d'un cluster nous avons utilisés un seuil de similarité qui représente la distance entre deux documents. Si cette distance est inférieure ou égale au seuil alors les documents sont similaires. Pour la distance cosinus ce seuil est comparé à la valeur |1 -cos(V i ,V j )|. Puisqu'on a utilisé un seuil donc on n'aura pas besoin de calculer l'entropie qui mesure la pureté du cluster trouvé ni de la F-mesure pour évaluer les taux d'erreurs en classification. nous ont aidés à numériser nos documents et ainsi pouvoir utiliser notre automate cellulaire sur des vecteurs numériques. Donc les passages des documents au texte, du texte au nombre, du nombre à l'analyse par les automates cellulaires et de l'analyse à la prise de décision sur la classification ainsi trouvée ont fait l'objet de cette étude dans cet article. Cet algorithme sera, dans le futur proche, comparé à un algorithme utilisant l'apprentissage par les cartes auto organisatrice de KOHONEN. L'algorithme peut contribuer ainsi à la problématique de la fouille de donnée textuelle et de la classification non supervisée.
Dans cet article, nous avons proposé un algorithme qui résout un problème de data mining en l'occurrence le text mining par une méthode biomimétique (Automates cellulaires). Cet algorithme sera dans le futur expérimenté pour d'autres types de données tels que les images et les données multimédias en général pour résoudre une autre problématique de fouille de données.