Thèse soutenue en co-tutelle

Titre provenant de l'écran-titre

Partenaire(s) de recherche : Équipe de recherche de Lyon en sciences de l'information et de la communication

Thèse de doctorat Sciences de l'information et de la communication Lyon 2 2010

Thèse de doctorat Sciences de l'information et de la communication ENSSIB 2010

La classification automatique des documents, une approche issue de l’apprentissage artificiel et de la fouille de textes, s’avère être très efficace pour l’organisation des ressources textuelles multilingues. Très peu des travaux se rapportent à la classification automatique de documents écrits en caractères arabes malgré la richesse morphologique de cette langue. Pour cela, nous nous intéressons dans cette thèse à la question de la classification automatique des documents écrits en caractères arabes. Il faut noter que pour surmonter les difficultés liées au traitement automatique de l’arabe, nous nous basons dans cette thèse sur une solution très performante celle basée sur la ressource linguistique informatisée de l’arabe DIINAR.1 et son analyseur morphologique. Le choix de la nature des attributs est un élément très important pour une classification automatique efficace et mérite être fait avec le plus grand soin puisqu’il a un effet directe sur la fidélité des classifieurs. Ainsi, nous avons mené dans cette thèse une étude comparative entre les n-grammes, les racines, les lemmes, et les mots comme nature d’attributs qui nous a permis de conclure une instabilité dans la performance des classifieurs basés sur les corpus construit via les n-grammes vis-à-vis d’une stabilité dans le comportement des classifieurs basés sur les corpus construits à partir des racines.De plus, on constate dans la plupart des travaux menés sur des documents écrits en caractères arabes qu’ils se basent sur des algorithmes d’apprentissage modernes comme, par exemple, les machines à vecteurs supports, les réseaux bayésiens naïfs, et les arbres de décision qui sont connus être parmi les meilleurs performants classifieurs du domaine. Toutefois, on ne trouve, à l’heure actuelle, aucun travail portant sur la classification automatique des documents écrits en caractères arabes qui utilise l’algorithme du dopage (« Boosting »). Pour cela, nous avons mené une étude comparative de la fidélité des arbres de décision (C4.5) dopés, d’une part, et les arbres de décision (C4.5) (sans dopage), les machines à vecteurs supports (SMO), et les réseaux bayésiens naïfs (NBM), d’un autre part, en fonction de la classification automatique des documents écrits en caractères arabes. Nous avons constaté que l’algorithme C4.5 boosté n’a pas pu surpasser la fidélité des algorithmes SVM et NBM. Nous attribuons cette faiblesse, sans reprocher le dopage, au fait que les arbres de décision sont très sensibles au moindre changement de leurs données sous-jacentes qui sont régulièrement pondérées et modifiées lors du dopage.Un document arabe peut être rédigé en une seule ou plusieurs langues i.e. le contenu du document est un mélange de mots écrits en caractères arabes ainsi que d’autres écrits en caractère latins. Tous les travaux portant sur la classification automatique des documents écrits en caractères arabes abordent le sujet d’un point de vue monolingue i.e. en exploitant uniquement le texte écrit en caractères arabes et en éliminant tout autre texte écrit dans d’autres langues. En conséquence, une partie vitale des informations présentes dans les documents est perdue délibérément sachant qu’elle aurait pu contribuer à la subjectivité de la décision prise par le classifieur puisque l’attribution d’un document à une catégorie ou une autre se base, principalement, sur son contenu. En conséquent, l’élimination des mots écrits en caractères latins tronque le texte ce qui met en question le degré de la subjectivité de la décision finale prise par le modèle de prédiction. Pour cela, nous nous sommes intéressés aussi dans cette thèse à la classification automatique des documents arabes ayant un contenu multilingues i.e. écrits en plusieurs langues. Nous avons repensé les pratiques actuelles des chercheurs en essayant de garder autant que possible des attributs écrits en caractères latins fidèles à la classification automatique et d’éliminer uniquement ceux portant peu d’information ou ayant peu de pertinence à leur documents (ex. les mots vides). Cette prise en compte du cas multilingue a entraîné des défis supplémentaires qui rendent quelques aspects de la classification automatique inopérants et nous oblige de leur trouver les solutions convenables. L’aspect le plus affecté par cette extension est celui de la réduction de la taille du vocabulaire par le biais de la sélection d’attributs. Dans ce paradigme, nous avons interrogé six méthodes largement connues et utilisées dans la littérature (le gain d’information, la mesure de χ^2, le rapport de gain, l’information mutuelle, le rapport des chances et la fréquence des documents) et nous avons constaté qu’elles sont incapables de préserver un nombre considérable des mots écrits en caractères latins sauf si le seuil des nombres d’attributs à conserver est assez large. Malheureusement, cette conclusion remet en question l’utilité d’utiliser une méthode de réduction de la taille du vocabulaire. Par conséquent, nous avons proposé quatre solutions capables de conserver un nombre significatif de ces mots tout en assurant une fidélité de classification satisfaisante : Nous avons proposé une nouvelle méthode de sélection qui vise à mesure la fréquence d’un attribut dans l’ensemble des catégories que l’on appelle « 3C » (Coefficient Catégorique Cumulatif). Nous avons proposé ensuite une variante de cette méthode ayant une stratégie de sélection composée que l’on appelle la méthode « 3C-SC». (Pour des détails sur la sélection composée voir le point 4). En plus, nous avons proposé une autre nouvelle méthode de sélection d’attributs que l’on appelle « RFDC » (Rapport de la Fréquence de Documents avec Conformité). Cette méthode se base sur la méthode « 3C » pour calculer les scores des attributs écrits en caractères arabes et utilise une autre nouvelle méthode pour calculer les scores des mots écrits en caractères latins. Cette nouvelle méthode pallie la faible fréquence des termes écrits en caractères latins en introduisant dans son calcul une mesure de « conformité » calculée par la méthode « Fréquence de Conformité Inversée (FCI) ». Pareillement à la méthode « 3C-SC », la méthode « RFDC » adopte une sélection d’attributs composée. Nous avons en plus trouvé qu’en modifiant la stratégie actuelle des méthodes connues pour la sélection des attributs nous avons obtenu une fidélité de classification meilleure que celle obtenue par leur stratégie originale. La stratégie de sélection classique procède séquentiellement dans la sélection des attributs i.e. elle sélection les premiers n attributs. Contrairement à cette stratégie, la nouvelle stratégie applique une sélection composée. Après avoir calculé les scores des attributs et les trier en ordre décroissant de score, cette approche choisie d’abord séquentiellement les premiers n-k mots écrits en caractères arabes et, ensuite, elle revisite cette liste du début pour choisir les premiers k mots écrits en caractères latins.Pour vérifier la validité de nos solutions nous avons mené une large batterie d’expérimentations en utilisant plus que 99 corpus d’apprentissage. Nous avons comparé nos solutions contre les six méthodes indiquées auparavant. Contrairement aux résultats obtenus en se basant sur les méthodes connues, nos solutions étaient capables de garder toujours un nombre de mots écrits en caractères latins significativement large à celui gardé par les méthodes connues. De plus, les algorithmes d’apprentissage basés sur les corpus engendrés par nos solutions ont été toujours plus fidèles à la classification automatique que ceux basés sur les corpus engendrés par les méthodes connues.

The automatic classification of documents is an approach resulting from the hybridization of machine learning and text mining techniques. It is has proven to be very effective for the automatic organization of text based resources, in particularly, multilingual ones. We find, however, very little literature written on the subject when it comes to Arabic documents despite the fact that this language is morphologically much richer than Latin based ones. It should be noted that, in order to overcome the difficulties related to the automatic processing of Arabic documents, a deep analysis, such as the one performed by the morphological analyzer based on the computerized dictionary for Arabic DIINAR.1, is required.One of the intrinsic elements of any automatic classification system is the choice of the attribute s nature. Great care should be taken while making that choice since it has a great impact on the classifier s accuracy. One of the contributions made by this thesis is the presentation of a comparative study between Support Vector Machines (SMO) and Naïve Bayes Multinomial (NBM) algorithms based on multiple corpuses generated from n-grams, stems, lemmas, and words. We concluded that the performance of the classifiers based on corpuses generated from stems was better than the one based on lemmas and words. In addition, the performance of the classifiers based on stems was more stable than the one based on corpuses generated from n-grams.Another contribution made by this thesis is the use of Boosting as a classifier. None of the literature written on the automatic classification of Arabic documents has ever used it before despite the fact that this algorithm was designed for that purpose. Therefore, we have conducted a comparative study between Decision Trees (C4.5), Boosted Decision Trees (C4.5 and AdaBoost.M1), SMO, and NBM algorithms respectively. Boosting was indeed able to boost the performance of C4.5 but the regular re-weighting made by Boosting to the dataset s instances hampered C4.5 from bypassing the performances of SMO and NBM algorithms. This weakness is due to the very nature of decision trees that renders them very sensitive to any change in their underlying data.We noticed while analyzing our dataset that an Arabic document is either written in one (i.e. Arabic) or multiple languages (i.e. it will contain words written in Arabic mixed with a minority of words written in another language). All of the literature written on the automatic classification of Arabic documents treats both cases equally and eliminates all the foreign terms in case it finds any. This deliberate elimination deprives the learning process from a vital part of the information found in the documents knowing that it could have contributed to the decision taken by the classifier since to assign to a document one category or another relies basically on its content and as such the degree of certainty of the decision made by the classifier is being compromised. Therefore, the main contribution made by this thesis is that it deals with the automatic classification of Arabic documents from a multilingual perspective and tries to preserve as much as possible of the foreign terms while eliminating only the useless ones (e.g. stowords). Dealing with Arabic documents from a multilingual point of view proved to be challenging especially during the feature selection process. We have considered and tested six well known feature selection measures (Information Gain, ^2, Gain Ratio, Mutual Information, Odds Ratio, and Document Frequency) only to find out that they were incapable of preserving enough foreign terms unless the selection s threshold is sufficiently high. Unfortunately, using a high threshold raises doubts about the benefit of using feature selection in the first place. As a result, we proposed a four solutions capable of preserving a significant number of foreign terms and leading to satisfactory classification accuracy and results: We have proposed a new feature selection measure based on the categorical frequency of the attribute. We called it the measure of the 3Cs (Cumulative Categorical Coefficient). We then proposed a variant of the previous method that adopts a composite selection strategy. We called it 3C-SC (more details on the composite selection strategy are presented in 4). Our third proposed solution is called RDFC (the Ratio of the Document Frequency with Conformity). This solution uses the 3C measure to calculate the scores of the Arabic terms and then uses another measure to calculate the scores of foreign terms. The other measure compensates for the weak frequency of foreign terms by introducing during its calculations the notion of conformity that we estimate by using the Inverted Conformity Frequency measure. As it is the case with 3C-SC , this solution adopts a composite selection strategy. The last proposed solution alters the selection strategy of the already known measures. The standard strategy proceeds sequentially in its selection i.e. it chooses the first n-terms. On the other hand, by applying a composite selection, we choose first the first n-k arabic terms and then we revisit the list of scored terms to choose the first k foreign terms. This alteration allowed us to obtain better classification accuracy compared to the one obtained by applying the standard one.In order to test the validity of our solutions, we ran a large series of experiments based on more than 99 datasets. We compared the results obtained by the classifiers based on datasets generated by our solutions against ones generated by the known measures. Our solutions were always able to preserve a higher number of foreign terms during the feature selection process as compared to known measures. Moreover, the classification accuracy of the algorithms based on datasets generated by our solutions was almost always better than the one obtained by algorithms based on datasets generated by the known methods.

Configuration requise : un logiciel capable de lire un fichier au format : text/html