Une nouvelle mesure de co-similarité : applications aux données textuelles et génomique
Institution:
GrenobleDisciplines:
Directors:
Abstract EN:
Clustering is the unsupervised classification of patterns (observations, data items, or feature vectors) into homogeneous and contrasted groups (clusters As datasets become larger and more varied, adaptations to existing algorithms are required to maintain the quality of cluster. Ln this regard, high¬dimensional data poses sorne problems for traditional clustering algorithms known as the curse of dimensionality. This thesis proposes a co-similarity based algorithm that is based on the concept of higher-order co-occurrences, which are extracted from the given data. Ln the case of text analysis, for example, document similarity is calculated based on word similarity, which in turn is calculated on the basis of document similarity. Using this iterative approach, we can bring similar documents closer together even if they do not share the same words but share similar words. This approach doesn't need externallinguistic resources like a thesaurus Furthermore this approach can also be extended to incorporate prior knowledge from a training dataset for the task of text categorization. Prior categor labels coming from data in the training set can be used to influence similarity measures between worlds to better classify incoming test dataset among the different categories. Thus, the same conceptual approach, that can be expressed in the framework of the graph theory, can be used for both clustering and categorization task depending on the amount of prior information available. Our results show significant increase in the accuracy with respect to the state of the art of both one-way and two-way clustering on the different datasets that were tested.
Abstract FR:
La classification de données (apprentissage non-supervisé) vise à regrouper un ensemble d'observations sous la forme de classes homogènes et contrastées. Lorsque les données sont caractérisées par un grands nombre de propriétés, il devient nécessaire d'adapter les méthodes classique, notamment au niveau des métriques, afin de maintenir des classes pertinentes; ce phénomène est connu sous le nom de "malédiction de la dimension". Dans cette thèse nous proposons une mesure de co-similarité basée sur la notion de co-occurrences d'ordre supérieur, directement extraites à partir des données. Dans le cas de l'analyse de texte, par exemple, les similarités entre documents sont calculées en prenant en compte les similarités entre mots, qui simultanément prennent en compte les similarités entre documents. Par cette approche circulaire, nous mettons en correspondance des documents sans mots communs mais juste des mots similaires. Cette approche s'effectue sans nécessiter de thesaurus externe. En outre, notre méthode peut également être étendu pour tirer partie de connaissances "a priori" pour réaliser des tâches de catégorisation de textes: l'étiquette des documents est utilisée pour influencer les mesures de similarité entre les mots afin de classer de nouvelles données. Ainsi, le même cadn conceptuel, exprimable en terme de la théorie des graphes, peut être utilisé à la fois pour les tâches de classification et de catégorisation en fonction de la quantité d'information initiale. Nos résultats montrent une amélioration significative de la précision, par rapport à l'état de l'art, pour le co-clustering et la catégorisation sur les jeux d données qui ont été testés.