Le problème de classification automatique de données : approches mono et multi-objectif

Abstract

Le clustering est l’une des tâches les plus importantes et les plus étudiées en data mining. Bien que beaucoup d’algorithmes de clustering aient été proposés dans la littérature de recherche, la plupart d'entre eux ne peuvent pas traiter correctement des ensembles de données ayant des clusters de formes arbitraires et de densité variable. De plus, les plus connus des algorithmes dépendent des paramètres utilisateur qui sont difficiles à définir. Dans le cadre de cette thèse, nous considérons le problème de clustering traitant des ensembles de données avec un nombre inconnu de clusters, ayant des formes arbitraires, présentant des variations de densité et contenant des outliers. Notre motivation principale est de proposer de nouvelles approches permettant d’automatiser le processus de clustering en considérant des ensembles de données possédant toutes ces spécifications. Pour répondre à ces exigences, nous avons proposé, tout d’abord, un nouvel indice de validation du clustering basé sur la connectivité et la densité (CDBCVI), qui permet de faire face au cas de clusters de formes arbitraires et de différentes densités. Il facilite ainsi l'évaluation des algorithmes de clustering et la sélection de leurs paramètres appropriés. Ce nouvel indice est basé sur les relations de densité et de connectivité entre les objets de données, extraites sur la base du graphe de proximité de Gabriel. L'incorporation des relations de connectivité et de densité permet d'obtenir de bons résultats de clustering dans le cas de clusters de n'importe quelle forme, taille ou densité. Par la suite, nous avons proposé trois approches de clustering mono- et multi-objectif qui permettent d’automatiser le processus de clustering et d’améliorer la qualité de ses résultats. Ces approches utilisent un schéma de codage de solutions basé sur la densité, inspiré des algorithmes basés sur la densité NBC (Neighborhood-Based Clustering) et DBSCAN (Density Based Spatial Clustering of Applications with Noise) qui sont très efficaces dans le cas de clusters ayant des formes arbitraires et des densités différentes. La première approche consiste à utiliser la métaheuristique de recherche par voisinage variable (Variable Neighborhood Search (VNS)), afin de remédier à la difficulté du choix de la valeur du paramètre unique de l’algorithme NBC et améliorer ses résultats. La deuxième approche consiste à utiliser l’algorithme de colonie d’abeilles artificielles (Artificiel Bee Colonies (ABC)) afin d’automatiser et améliorer la qualité du clustering de l’algorithme NBC. Quant à la troisième approche, elle consiste à utiliser l’algorithme ABC afin d’automatiser et améliorer la qualité du clustering en s’inspirant de la procédure d’expansion de clusters de l’algorithme DBSCAN. Pour améliorer le processus d'évaluation des solutions de clustering au cours des itérations, nous avons défini plusieurs fonctions objectif basées sur des concepts de densité, vu que la prise en compte d'une seule fonction objectif peut ne pas être conforme aux ensembles de données ayant des clusters de formes complexes et des outliers. Nous avons testé la performance des approches proposées par une expérimentation approfondie sur des ensembles de données réels et synthétiques. Les résultats expérimentaux démontrent l’efficacité et la supériorité des approches proposées par rapport à plusieurs d’autres approches de la littérature