Apprentissage sur des données académiques en vue de faciliter l'orientation et l'aide à la décision

2.3.3.1 Principe du K-PPV

Son principe est le suivant : Une donnée de classe inconnue est comparée à toutes les données stockées. On choisit pour la nouvelle donnée. la classe majoritaire parmi ses K plus proches voisins (Elle peut donc être lourde pour des grandes bases de données) au sens d'une distance choisie. Les k-PPV nécessitent seulement :

· Un entier k

· Une base d'apprentissage L = {(yi, xi), i = 1, ..., nL}

oùyi E {1, ..., c} dénote la classe de l'individu i et le vecteur xi = (xi1, ..., xip) représente les variables prédicatrices de l'individu i.

· Une métrique pour la proximité

· Une métrique pour la proximité(une distance)

on peut choisir la distance euclidienne d_e. Soient deux données représentées par

2.3. LES ALGORITHMES DE MACHINE LEARNING CHAPITRE 2. REVUE DE LA LITTÉRATURE

deux vecteurs x et y , la distance entre ces deux données est donnée par :

de(x,y) =

v u u Xn ti=1

(xi - yi)^2(2.1)

Mémoire de Master II en Informatique 26 c~NJAMEN M. ZELKIF 2020-2021

Ainsi, pour une nouvelle observation (y, x) le plus proche voisin (y1-x1) dans l'échantillon d'apprentissage est déterminépar :

d(x, x1) = mini(d(x, xi))

Et y = y1, la classe du plus proche voisin, est sélectionnée pour la prédiction de y.

2.3.3.2 Avantages de la méthode des K-PPV

La méthode des k plus proches voisins représente des avantages tels que:

1. L'algorithme K-NN est robuste envers des données bruitées. Selon SOLLAH [20]

2. La méthode des k plus proches voisins est efficace si les données sont larges et incomplètes. Selon Wikipédia [21]

3. Cette méthode est l'une des plus simples de tous les algorithmes d'apprentissage automatique. Selon 123dok [22]

2.3.3.3 Inconvénients de la méthode des K-PPV

La méthode des k plus proches voisins comporte des inconvénients tels que :

1. Le besoin de déterminer la valeur du nombre des plus proches voisins (le paramètre k). Dans 123dok [22]

2. Le temps de prédiction est très long puisqu'on doit calculer la distance de tous les exemples. Selon Wikipédia [21]

3. Selon Marwa [23] Cette méthode est gourmande en espace mémoire car elle utilise une grande capacitéde stockage pour le traitement des corpus.

2.3.4 Les Arbres de décision

2.3.4.1 Généralités sur les arbres de décision

L'apprentissage par arbre de décision est une méthode classique en apprentissage automatique. Son but est de créer un modèle qui prédit la valeur d'une variable-cible depuis

2.3. LES ALGORITHMES DE MACHINE LEARNING CHAPITRE 2. REVUE DE LA LITTÉRATURE

Mémoire de Master II en Informatique 27 c~NJAMEN M. ZELKIF 2020-2021

la valeur de plusieurs variables d'entrée.

Une des variables d'entrée est sélectionnée à chaque noeud intérieur (ou interne, noeud qui n'est pas terminal) de l'arbre selon une méthode qui dépend de l'algorithme. Chaque arête vers un noeud-fils correspond à un ensemble de valeurs d'une variable d'entrée, de manière que l'ensemble des arêtes vers les noeuds-fils couvrent toutes les valeurs possibles de la variable d'entrée.

Chaque feuille (ou noeud terminal de l'arbre) représente soit une valeur de la variable-cible, soit une distribution de probabilitédes diverses valeurs possibles de la variable-cible. La combinaison des valeurs des variables d'entrée est représentée par le chemin de la racine jusqu'àla feuille.

L'arbre est en général construit en séparant l'ensemble des données en sous-ensembles en fonction de la valeur d'une caractéristique d'entrée. Ce processus est répétésur chaque sous-ensemble obtenu de manière récursive, il s'agit donc d'un partitionnement récursif.

La récursion est achevée à un noeud soit lorsque tous les sous-ensembles ont la même valeur de la caractéristique-cible, ou lorsque la séparation n'améliore plus la prédiction. Ce processus est appeléinduction descendante d'arbres de décision (top-down induction of decision trees ou TDIDT), c'est un algorithme glouton puisqu'on recherche à chaque n ?ud de l'arbre le partage optimal, dans le but d'obtenir le meilleur partage possible sur l'ensemble de l'arbre de décision. C'est la stratégie la plus commune pour apprendre les arbres de décision depuis les données.

En fouille de données, les arbres de décision peuvent aider à la description, la catégorisation ou la généralisation d'un jeu de données fixé.

L'ensemble d'apprentissage est généralement fourni sous la forme d'enregistrements du type:

(x,Y ) = (x1,x2,x3,...,xk,Y )

La variable Y désigne la variable-cible que l'on cherche à prédire, classer ou généraliser. Le vecteur X est constituédes variables d'entrée x1, x2, x3 etc. qui sont utilisées dans ce but.

Selon Wikipédia [24], Un arbre de décision est une structure graphique sous forme d'un arbre (feuilles et branches) qui illustre un ensemble de choix pour aider à la prise de décision et classer un vecteur d'entrée X.

Cet algorithme est très utilisédans les fouilles de données et la sécurité.

2.3. LES ALGORITHMES DE MACHINE LEARNING CHAPITRE 2. REVUE DE LA LITTÉRATURE

Mémoire de Master II en Informatique 28 c~NJAMEN M. ZELKIF 2020-2021

2.3. LES ALGORITHMES DE MACHINE LEARNING CHAPITRE 2. REVUE DE LA LITTÉRATURE

Mémoire de Master II en Informatique 29 c~NJAMEN M. ZELKIF 2020-2021

Chaque noeud de l'arborescence contient une comparaison de fonction simple par rapport à un champ (exemple : x = female?).

Le résultat de chaque comparaison est vrai ou faux, ce qui détermine si nous devons continuer vers la feuille gauche ou vers la droite du noeud. Une feuille correspond à la décision.

Chaque instance est décrite par un vecteur d'attributs/valeurs En entrée : un ensemble d'instances et leur classe (correctement associées par un »expert»)

Les arbres de décision sont également connus sous le nom d'arbres de classification et de régression (CART).

D'après Alain [14] Les arbres de décision sont des classifieurs pour des instances représentées dans un formalisme attribut/valeur.

· Les noeuds de l'arbre testent les attributs

· Il y a une branche pour chaque valeur de l'attribut testé
· Les feuilles spécifient les catégories (deux ou plus)

Figure 2.4 - Classification avec un Arbre de Décision sur le jeu de donnée Maladies.
Tiréde Alain [14]

Le choix des attributs est très important car :

· Si un attribut crucial n'est pas représentéon ne pourra pas trouver d'arbre de décision qui apprenne les exemples correctement.

· Si deux instances ont la même représentation mais appartiennent à deux classes différentes, le langage des instances (les attributs) est dit inadéquat.

Figure 2.5 - Classification avec un Arbre de Décision sur le jeu de donnée Jouer
Tennis. Tiréde Alain [14]