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 .