L’algorithme KNN

K plus proches voisins (KNN) 

La méthode des k plus proches voisins (k-nearest neighbor, KNN) est une méthode supervisée. Elle a été utilisée dans l’estimation statistique et la reconnaissance des modèles comme une technique non paramétrique, cela signifie qu’elle ne fait aucune hypothèse sur la distribution des données.

L’algorithme KNN est l’un des plus simples de tous les algorithmes d’apprentissage automatique. Il est un type d’apprentissage basé sur l’apprentissage paresseux (lazy leaming). En d’autres termes, il n’y a pas de phase d’entraînement explicite ou très minime. Cela signifie que la phase d’entraînement est assez rapide.

La méthode KNN suppose que les données se trouvent dans un espace de caractéristiques. Cela signifie que les points de données sont dans un espace métrique. Les données peuvent être des scalaires ou même des vecteurs multidimensionnels.  La méthode des k plus proches voisins est utilisée pour la classification et la régression. Dans les deux cas, l’entrée se compose des k données d’entraînement les plus proches dans l’espace de caractéristiques.

Pour trouver la classe d’un nouveau cas, cet algorithme se base sur le principe suivant: il cherche les k plus proches voisins de ce nouveau cas, ensuite, il choisit parmi les candidats trouvés le résultat le plus proche et le plus fréquent. Pour affecter un nouvel individu à une classe, l’algorithme cherche les k plus proches voisins parmi les individus déjà classés. Ainsi, l’individu est affecté à la classe qui contient le plus d’individus parmi les candidats trouvés. Cette méthode utilise principalement deux paramètres: une fonction de similarité pour comparer les individus dans l’espace de caractéristiques et le nombre k qui décide combien de voisins influencent la classification.

Les machines à support de vecteurs (SVM) 

Introduit par Vapnik en 1990, les machines à vecteurs de support sont des techniques d’apprentissage supervisé destinées à résoudre des problèmes de classification et de régression. Elles reposent sur deux notions principales : la notion de marge maximale et la notion de fonction noyau. Les machines à support de vecteurs peuvent être utilisées pour résoudre divers problèmes en bio-informatique, recherche d’information et vision par ordinateur, etc.

Avantages des SVM: Les SVM représentent plusieurs avantages, notamment ceux-ci: Elles ont une base théorique solide. Les SVM sont efficaces dans les espaces de grande dimension. Différentes fonctions noyau peuvent être spécifiées. Inconvénients des SVM :Malgré leurs performances, les SVM représentent aussi des faiblesses, notamment celles-ci: Elles utilisent des fonctions mathématiques complexes pour la classification.  Les machines à support de vecteurs demandent un temps énorme durant les phases de test.

Les cartes auto organisatrices de Kohonen (SOM) 

Développées par T. Kohonen en 1982, les cartes auto organisatrice (SOM) sont des types de réseaux de neurones. Elles constituent un outil efficace et performant qui permet de classifier des échantillons par rapport à leurs similarités.

Elles fournissent un moyen pour représenter des données multidimensionnelles dans des espaces de dimensions faibles (habituellement une ou deux dimensions). En outre, elles créent un réseau qui stocke l’information. Avantages des cartes auto-organisatrices de Kohonen : Les cartes auto-organisatrices de Kohonen comportent des avantages tels que: L’algorithme présente des opérations simples. L’algorithme s’avère très léger en termes de coût de calculs.  Permet une visualisation graphique des résultats. Inconvénients des cartes auto-organisatrices de Kohonen : Les des cartes auto-organisatrices de Kohonen comportent des inconvénients tels que: Le voisinage dans les cartes auto-organisatrices est fixe.  Une liaison entre neurones ne peut être cassée même pour mieux représenter des données discontinues. Leur temps énorme de convergence.

Le réseau à architecture évolutive ART

ART ((Adaptive Resonance Theory) est une théorie développée par Grossberg et Carpenter. Il décrit un certain nombre de modèles de réseaux neuronaux qui utilisent des méthodes d’apprentissage supervisées et non supervisées. Il existe plusieurs versions de réseaux (ART1, ART2, ART3). Le réseau ART1 est un réseau à entrées binaires.

Architecture: Le réseau de neurone ART1 a une architecture multi-niveaux : la couche d’entrée (unités d’entrées), la couche cachée (ensemble des unités cachées invisible aux utilisateurs) et la couche de sortie (unités de sortie). Dans ce type de réseau, la couche d’entrée et la couche de sortie se sont superposées l’une sur l’autre pour former une seule couche baptisé entrée-sortie. Les neurones de la couche entrée-sortie sont tous connectés aux neurones de la couche cachée; réciproquement, chaque neurone de la couche cachée à son tour est connecté avec tous les neurones de la couche entrée-sortie. La couche cachée est une couche compétitive dans laquelle tous les neurones sont reliés les uns aux autres.

Avantages des ARTs: Les ARTs représentent plusieurs avantages tels que: Le paramétrage des ARTs est facile où ils ne requièrent qu’un seuil de vigilance. Les ARTs peuvent effectuer un apprentissage en temps réel. Ils peuvent fonctionner dans des environnements dynamiques.

Inconvénients des ARTs: Les ARTs ont aussi des inconvénients tels que: Le temps de réponse élevé grâce à une approche à deux couches.

Le même seuil de vigilance est appliqué à tous les clusters.  Les ARTs conduit souvent à la dégradation. Cette dernière est définie par la capacité d’un ART à fournir une classification utile en présence de défauts.

Les algorithmes génétiques

Les algorithmes génétiques ont été initialement développés par Roland (1975). Les AGs utilisent un vocabulaire similaire à celui de la génétique naturelle. Ainsi, une population est un ensemble d’individu et ceci sera résumé, bien souvent, par un seul chromosome. Les chromosomes sont constitués de gènes qui contiennent les caractères de l’individu. On trouvera aussi les principes de sélection, de croisement, de mutation, etc.

Chaque point dans l’espace d’état se traduit par un chromosome en associant une valeur du critère à optimiser. Ensuite, on applique l’algorithme génétique pour sélectionner les meilleurs individus à partir d’une population d’individus générée aléatoirement, tout en assurant une exploration efficace de l’espace d’état.

Avantages des algorithmes génétiques: Les algorithmes génétiques représentent plusieurs avantages tels que:

Leurs convergences ne dépendent pas de la valeur initiale. Ils permettent de déterminer l’optimum global de la fonction objectif .

Ils représentent des méthodes génériques qui peuvent optimiser une large gamme de problèmes différents . Leur capacité à faire plusieurs calculs en parallèle.

Inconvénients des algorithmes génétiques: Les algorithmes génétiques ont aussi des inconvénients tels que: Le temps de calcul est énorme puisqu’ils manipulent plusieurs solutions en parallèle. La recherche pour la solution optimale se limite généralement autour d’un minimum qui n’est pas forcement l’optimum attendu. On parle dans ce cas de convergence prématurée.

L’efficacité d’un algorithme génétique dépend beaucoup de la méthode de croisement et du type de codage choisis .

Table des matières

Chapitre 1 : Introduction
Chapitre 2 : Les méthodes de classification 
2.1 Introduction
2.2 K-moyen (K-mean) 
2.2.1 L’algorithme de K-moyen
2.2.2 Avantages du K-moyen
2.3 K plus proches voisins (KNN)
2.3.1 L’algorithme des k plus proches voisins
2.3.2 Avantages de la méthode des k plus proches voisins
2.3.3 Inconvénients de la méthode des k plus proches voisins
2.4 Les machines à support de vecteurs (SVM) 
2.4.1 Le principe des SVM
2.4.2 Avantages des SVM
2.4.3 Inconvénients des SVM
2.5 Les réseaux de neurones
2.5.1 Architecture
2.5.2 L’apprentissage
2.5.2.1 L’ apprentissage supervisé
2.5.2.2 L’ apprentissage non supervisé
2.5.3 Fonction d’activation
2.5.4 Topologie des réseaux de neurones
2.5.4.1 Propagation vers l’avant de l’information (Feed-forward)
2.5.4.2 Récurent (Feed-back connections)
2.5.5 Les réseaux de Perceptron
2.5.6 Les réseaux Hopfield
2.5.7 Les réseaux du perceptron multicouche (multilayer perceptron MLP)
2.5.8 Avantages des réseaux de neurones
2.5.9 Inconvénients des réseaux de neurones
2.6 Les cartes auto organisatrices de Kohonen (SOM)
2.6.1 L’architecture des cartes auto organisatrices de Kohonen
2.6.2 L’algorithme des cartes auto-organisatrices de Kohonen
2.6.3 Avantages des cartes auto-organisatrices de Kohonen
2.6.4 Inconvénients des cartes auto-organisatrices de Kohonen
2.7 Le réseau à architecture évolutive ART
2.7.1 Architecture
2.7.2 Apprentissage
2.7.2.1 Algorithme
2.7.3 Avantages des ARTs
2.7.4 Inconvénients des ARTs
2.8 Les algorithmes génétiques 
2.8.1 Terminologie
2.8.2 Principes des algorithmes génétiques
2.8.3 Pseudo code d’un Algorithme génétique
2.8.4 Avantages des algorithmes génétiques
2.8.5 Inconvénients des algorithmes génétiques
2.9 Apprentissage profond (Oeep learning) 
2.9.1 Apprentissage automatique
2.9.3 La catégorisation de l’apprentissage profond
2.9.3.1 Les réseaux profonds pour l’apprentissage non supervisé
2.9.3.2 Les réseaux profonds pour l’apprentissage supervisé
2.9.3.3 Les réseaux profonds hybrides
2.9.4 Avantages des réseaux profonds
2.9.5 Inconvénients des réseaux profonds
2.10 Conclusion 
Chapitre 3 : Modèle vectoriel 
3.1 Introduction 
3.2 Espace de documents
3.3 Coefficient de similarité 
3.4 TF-lOF 
3.4.1 Fréquence du terme
3.4.2 Fréquence inverse de document
3.5 Avantages
3.6 Limitation
3.7 Conclusion 
Chapitre 4 : Les règles d’association 
4.1 Introduction
4.2. Définitions 
4.2.1. Transaction et ensemble d’items
4.2.2. Itemset, Itemset fréquent et support
4.2.3 Règle d’association, support et confiance
4.3. La recherche des règles d’association 
4.4. L’algorithme Apriori 
4.4.1 Le principe de l’algorithme Apriori
4.4.2 L’ algorithme Apriori
4.4.3 Générer les règles d’association à partir d’Itemsets fréquents
4.5 Avantages
4.6 Inconvénients
4.7 Conclusion 
Chapitre 5 : Méthodologie 
5.1 Introduction 
5.2 Architecture de notre système
5.3 La création d’index inversé 
5.3 .1 L’ extraction de texte brut
5.3.2 Segmentation
5.3.3 Extraction du vocabulaire
5.3.4 Nettoyage du vocabulaire
5.3.5 L’index inversé
5.4. Classification
5.4.1 La matrice TF-IDF
5.4.2 Choix du classifieur et le processus de classification
5.4.3. Extraction des règles d’association
5.4.3.1 La fragmentation verticale
5.4.3.2 L’extraction des règles d’ association
5.5. Conclusion 
Chapitre 6 : Expérimentations et résultats
6.1 Architecture du système
6.2 Implémentation
6.2.1 Langages choisis pour l’implémentation
6.2.2 Les interfaces
6.3 Expérimentations: «La civilisation des Arabes» 
6.3.1 Partie 1
6.3.2 Partie 2
6.3.3 Partie 3
6.3.4 Partie 4
Chapitre 7 : Conclusion

Télécharger le rapport complet