Amélioration de l’efficacité de K-NN

Amélioration de l’efficacité de K-NN

Solution proposée et objectifs du projet

Dans la littérature, on trouve plusieurs voies d’amélioration pour pallier aux faiblesses de K-NN en matière d’efficacité et de gestion d’incertitudes.

• La première voie concerne l’amélioration de l’efficacité en réduisant l’ensemble d’apprentissage à un sous-ensemble d’instances, appelées ces prototypes serviront par la suite comme ensemble d’apprentissage dans le classement d’une nouvelle instance. Dans ce contexte, nous proposons d’utiliser l’algorithme de regroupement FCM, Fuzzy C-Means, pour classifier les instances d’apprentissage dans des clusters ; les centres des clusters obtenus serviront après comme prototypes dans le classement d’une nouvelle instance. Le nombre adéquat de prototypes sera choisi à l’aide d’un indice de validité de clusters qui permet d’estimer la qualité des partitions générées.

• La deuxième voie concerne le traitement des incertitudes et des imprécisions à l’aide de la théorie des ensembles flous et la logique floue.

En effet, la logique floue a été utilisée de façon satisfaisante dans divers domaines d’application où le bruit, l’incertitude et l’imprécision sont inévitables. En fait, la logique floue se veut une approche parfaitement adéquate à la modélisation des connaissances, imprécises, qualitative et vagues. Dans notre travail, nous proposons de (1) représenter les attributs de prédiction par des variables linguistiques capables de prendre des valeurs qualitatives telles que petit, moyen, grand, etc. (2) d’utiliser une mesure de similarité floue, basée sur les variables linguistiques, pendant le classement d’une nouvelle instance.

Ainsi, nous pouvons regrouper les objectifs de ce travail en trois • Etudier les méthodes de génération des prototypes, l’algorithme de regroupement FCM et la logique floue • Implémenter, sous forme d’une application ergonomique et conviviale, la méthode de classement basée sur l’algorithme FCM pour la génération des prototypes et la similarité floue pour le classement. • Réaliser une expérimentation à l’aide de l’application développée, sur les bases d’apprentissage les plus connues.

Approche basée sur les instances.

Cette approche semble convenir à la tâche de classement dans des domaines complexes où la qualité non satisfaisante des données d’apprentissage rend difficile l’obtention d’un modèle de classement généralisé acceptable. Par exemple, le diagnostic médical [7], l’estimation de l’effort logiciel [8][9], ou la reconnaissance de formes, où les attributs sont souvent décrits par des valeurs linguistiques telles que faible, moyenne ou élevée et que les ensembles de données sont généralement incomplet et déséquilibré. La principale différence par rapport à l’approche basée sur l’abstraction est le stockage, pendant la phase de classement, d’un ensemble d’instances sélectionnées dans l’ensemble de données d’apprentissage [10]. Le processus de classement dans cette approche repose sur l’hypothèse « les instances similaires possèdent des classes similaire ». Ainsi, les techniques de classement résultantes requièrent les éléments suivants pendant le classement :

• Un ensemble d’instances représentant toutes les données d’apprentissage ou un sous ensemble sélectionné automatiquement par des algorithmes spécifiques ou manuellement par des experts du domaine.

• Une mesure de similarité qui calcule la similarité entre la nouvelle instance à classifier et les instances stockées. Le choix de la mesure de similarité est basé sur la nature et la représentation des attributs (numérique, catégorique, linguistique, etc.) et du domaine d’application. En pratique, les mesures de similarité dérivées de mesures de distance telles que les distances euclidiennes, euclidiennes inversées, pondérées ou le principe local-global [11], [12] sont généralement utilisées.

• Une règle de décision qui définit comment affecter une classe à une nouvelle instance à partir des classes des instances les plus similaires. Le choix instances les plus similaires dépend de l’interprétation de la qualification de « plus similaire » ; par exemple, les k premières instances similaires.

Plusieurs techniques ont été développées selon cette approche, telles que la technique des plus proches voisins [13], le classement basé sur la similarité [14], le raisonnement à base de cas utilisant des représentations symboliques plus complexes pour les instances [15], et la technique des plus proches prototypes [16]. Dans la suite, nous nous intéresserons à cette dernière technique

L’algorithme K-NN

L’algorithme des K plus proche voisin (K-NN) (figure 3) a été proposé par [13]. C’est un algorithme d’apprentissage, basé sur les instances, où l’affectation d’une classe à un nouvel exemple est effectuée en fonction de sa proximité, en termes de distance, aux instances déjà classées. En pratique, l’utilisation de K-NN nécessite le choix de deux paramètres. Le premier c’est la mesure de distance ; le choix dépend de la structure de l’espace des attributs caractérisant les données d’apprentissage. Le deuxième c’est le nombre K de voisins à prendre en compte dans le classement ; le nouvel exemple est affecté à l’étiquette de classe la plus courante parmi celles des K plus proches voisins obtenu par un vote majoritaire. Malgré les avantages présentés ci-dessus, l’algorithme K-NN peut générer des résultats biaisés lors du choix d’une valeur inappropriée de K. Il existe une multitude de façons différentes de choisir la valeur k ; la plus douce et efficace consiste à appliquer plusieurs fois l’algorithme et à modifier la valeur de k dans chaque essai afin d’atteindre la plus grande précision.

Les améliorations de K-NN

K-NN a fait ses preuves et a donné de bons résultats au cours des dernières décennies. Sa puissance provient de sa capacité à traiter des problèmes de classement complexes caractérisés par des étiquettes de classe multiples, des données déséquilibrées ou bruitées [19]. Cela est dû au fait que les informations de classement sont contenues dans les voisins les plus proches et ne nécessite pas la connaissance préalable de la structure des données et de leur distribution. Malgré le succès réalisé, KNN souffre toujours de plusieurs faiblesses liées ; à la précision de classement ; à l’inefficacité qui est dû au fait que la taille du problème croît en fonction du nombre d’instances et du nombre d’attributs considérés ; et à la faible tolérance des imprécisions et des incertitudes qui apparaissent en raison des limites brutales entre les classes, du bruit induit par le choix inapproprié du paramètre K et de la technique de vote

Table des matières

Dédicaces
Remerciements
Résumé
Abstract
Liste des figures
Liste des tableaux
Liste des acronymes
Introduction générale
Chapitre1 : Cadre général du projet
Introduction
1.Présentation du lieu de stage
2.Problématique
3.Solution proposée et objectifs du projet
Conclusion
Chapitre 2 :Etat de l’art
Introduction
1.Apprentissage supervisé
1.1. Formulation d’un problème de classement
1.2. Processus de classement
1.3. Techniques de classement
1.3.1. Approche basée sur l’abstraction
1.3.2. Approche basée sur les instances.
2.Approche des K plus proches voisins
2.1. L’algorithme K-NN
2.2. Les améliorations de K-NN
3.Amélioration de l’efficacité de K-NN
3.1. Apprentissage de prototypes
3.2. Approches pour l’apprentissage des prototypes
Conclusion
Chapitre 3 : Solution proposée
Introduction
1.Préliminaires
1.1. Logique floue
1.1.1. Ensembles flous
1.1.2. Fonctions d’appartenances usuelles
1.1.3. Propriétés des ensembles flous
1.1.4. Opérations sur les ensembles flous
1.2. Variables linguistiques
1.3. Regroupement flou
1.3.1. Fuzzy C-means
1.3.2. Indices de validités
1.3.3. Indices de validité dans un environnement flou
1.4. Mesure de similarité floue
2.Description de la solution
2.1. Formulation du problème
2.2. Processus de classement
2.3. Extraction des prototypes
2.4. Extraction des ensembles flous
2.5. Calcul des similarités individuelles
2.6. Génération de la matrice de similarité globale :
2.7. Classement
Conclusion
Chapitre 4 : Application et expérimentations
Introduction
1.Outils de développement
1.1. Environnement de développement Pycharm
1.2. Anaconda
1.3. Flask
2.Interfaces Graphiques
2.1. Interface « Classement des bases de données prédéfinis »
2.2. Interface « Nouvelle base de données »
2.3. Interface « CVI »
2.4. Interface « Ensembles flous »
3.Expérimentation
3.1. Données utilisées
3.2. Mesures utilisées
3.2.1. Taux de classement TCl
3.2.2. Taux de Réduction TRé
3.2.3. Rapport de classement et réduction
Conclusion
Conclusion générale

Télécharger le rapport complet