Classification non hiérarchique ou de partitionnement

La classification automatique est un ensemble de méthodes conçu pour analyser des jeux de données que ce soit dans le cadre scientifique ou d’analyses stratégiques de la recherche. Ces méthodes s’appuient sur la combinaison de techniques dédiée à la classification supervisée ou non- supervisée. On peut définir une méthode comme étant une marche rationnelle qUI permet d’atteindre la connaissance d’ un but. Vu l’intérêt de la classification, nombreux sont les chercheurs qui ont consacré énormément d’efforts et de savoir-faire pour mettre à  jour différentes méthodes et les rendre disponibles aux utilisateurs. On peut distinguer plusieurs méthodes de classification à savoir:
•Les méthodes hiérarchiques (ascendantes ou descendantes).
•Les méthodes de partitionnement (K-means, K- médoïdes … ).
•Les méthodes neuronales (PMC, SOM, MULTISOM … ).

C’est en optimisant un critère visant à regrouper les individus dans des classes les plus homogènes possibles, et, entre elles les plus distinctes possibles, que résulte une classification non-supervisée. En outre, la classification permet de mettre en évidence ces regroupements sans connaissance sur les données traitées.

La classification non-supervisée est un ensemble de méthodes ayant pour objectif la recherche d’une typologie ou segmentation existante, c’est-à-dire une partition ou répartition des individus en classes homogènes ou catégories. Dans ce mémoire, nous faisons appel à la classification non-supervisée sur des données textuelles afin de pouvoir regrouper des objets ayant des similitudes en des groupes homogènes. À cet effet, on a eu recours aux méthodes de partitionnement (Kmédoïdes) et aux méthodes hiérarchiques ascendantes (agglomératives) ou descendantes (divisives), tout en utilisant un environnement de développement gratuit RStudio (Présentation du RStudio, 2019).

Classification non hiérarchique ou de partitionnement 

Les méthodes de classification non hiérarchique cherchent à construire directement des partitions avec un nombre de classes fixe a priori. On s’intéresse plus particulièrement à la méthode des K-means et celle des K-médoïdes.

Méthode des K-means 

K-means est une méthode qui a été développée par MacQueen en 1967 (MacQueen, 1967 ). Elle vise à partitionner un ensemble de données en K classes homogènes, K est le nombre de classes voulue ou fixé a priori.

Algorithme basique des K-means 

Dans sa version de base, l’algorithme des K-means s’énonce comme suit:
Entrée: K le nombre de classes voulues ou fixé a priori
Début:
o Choisir aléatoirement les centres de classes
o Répéter
• Affecter chaque objet à la classe dont le centre est le plus proche
• Recalculer le centre de chaque classe

o Jusqu’à (convergence)
Sortie: Une artition des individus en K classes

Étant donné qu’elle est itérative, cette méthode converge vers une solution quel que soit son point de départ. Cependant, la partition finale obtenue dépend de la partition initiale.

Méthode des K-médoïdes

K-médoïdes ou le partitionnement autour des médoïdes est un algorithme de classification non hiérarchique qui est légèrement modifié par rapport à l’algorithme des K-means. En fait, c’est une variante des K-means. Il s’avère que le calcul des Kmédoïdes est plus robuste au bruit que le calcul de K-means. (Jin et Han., 2011). Le médoïde est l’élément le plus central de la classe, c’est à dire celui pour lequel la somme des distances aux autres éléments de la classe est la plus faible. Nous obtenons ainsi l’algorithme des K-médoïdes, dans lequel le seul changement par rapport au K-means est le remplacement des centres de gravité par des médoïdes.

Algorithme des K-médoïdes : 

Dans sa version de base, l’algorithme des K-médoïdes s’énonce comme suit:
• Entrée: K le nombre de classes voulues ou K est fixé a priori.
• Début :
o Choisir au hasard les médoïdes de classes
o Répéter
• Affecter chaque objet à la classe dont le médoïde est le plus proche
• Recalculer les médoïdes de chaque classe à partir des objets regroupés
o Jusqu’à (convergence)
Sortie: Une partition des objets en K classes .

Table des matières

CHAPITRE 1 INTRODUCTION
CHAPITRE 2 RÈGLES D’ASSOCIATION
2.1. Introduction
2.2. Notions et Définitions
2.2. 1. Transaction et Items
2.2.2. Itemset
2.2.3. Support
2.3. Règle d’association Standard
2.3. 1. Propriétés et opérations des règles d’association classiques
2.4. Processus d’extraction des règles d’association
2.4.1. L’algorithme Apriori
2.4.2. Avantages et limites des règles d’association
2.5. Les règles d’association maximales
2.5.1. Taxonomie et catégorie
2.5.2. M-support d’itemset
2.5.3. M-Support d’ une règle d’association X max Y
2.5.4. M-Confiance d’ une règle d’association maximale
2.5.5. Avantages et inconvénients :
2.6. Les règles d’association séquentielles
2.6. 1. Notions et définitions :
2.6.2. Extraction des motifs séquentiels :
2.6.3. Propriétés des séquences fréquentes
2.7. Conclusion
CHAPITRE 3 CLASSIFICATION
3.1 . Introduction
3.2. Représentation vectorielle
3.3. Mesures de similarité et de dissimilarité
3.3.1. Mesure de similarité
3.3.2. Mesures de dissimilarité et de distance
3.4. Classification hiérarchique
3.4.1. Choix d’un indice d’agrégation de classes
3.4.2. Algorithme de Classification Ascendante Hiérarchique
3.4.3. Arbre de classification
3.5. Classification non hiérarchique ou de partitionnement
3.5.1. Méthode des K-means
3.5.2. Méthode des K-médoïdes
3.6. Choix du nombre de classes
3.6.l.Choix d’un grand nombre de classes
3.6.2.Choix du petit nombre de K classes
3.6.3.Choix optimal du nombre de classes
CHAPITRE 4
MÉTHODOLOGIE
4.1. Introduction
4.2. Présentation du schéma
4.2.1 . Gestion du document
4.2.2. Segmentation
4.2.3. Préparation du texte
4.2.4. Nettoyage du texte
4.2.5. Extraction du vocabulaire
4.2.6. Les règles d’association
4.2.7. Classification
4.3. Exempl e à deux thématiques différentes
4.3.1 . Segmentation
4.3.2. Préparation du texte
4.3.3. Nettoyage du texte
4.3.4. Lemmatisation
4.3.5. Extraction du vocabulaire
4.3.6. Application des règles d’association
4.3.7. Classification
4.4. Conclusion
CHAPITRE 5 EXPERIMENTATIONS ET DISCUSSIONS
5.1. Introduction
5.2. Première expérimentation
5.2.1. Itemsets fréquents comme descripteur du texte
5.2.2. Mots comme descripteurs
5.3. Deuxième expérimentation
CHAPITRE 6 CONCLUSION

Cours gratuitTélécharger le document complet

 

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *