Concepts Fondamentaux en Statistique

Data Mining :

Machine Learning : SVM (Séparateurs à Vaste Marge),

Réseaux Bayésiens et K-Plus Proches Voisins



Sommaire :


Présentation du Programme

STATISTICA Machine Learning offre un certain nombre de méthodes statistiques avancées pour traiter des tâches de régression et de classification avec plusieurs variables dépendantes et indépendantes. Parmi ces méthodes, citons la méthode des Séparateurs à Vaste Marge (SVM - Support Vector Machines) pour des problèmes de régression et de classification, la méthode des Réseaux Bayésiens Naïfs pour des problèmes de classification, et la méthodes des K Plus Proches Voisins pour des problèmes de régression et de classification. Vous trouverez une présentation de ces techniques dans l'ouvrage de Hastie, Tibshirani, & Freedman (2001) ; l'ouvrage de Cristianini et Shawe-Taylor (2000) constitue une introduction technique complète des support vector machines.

Séparateurs à Vaste Marge (SVM - Support Vector Machines) (SVM). Cette méthode permet d'effectuer des tâches de régression et de classification en construisant des règles (frontières) de décision non-linéaires. En raison de la nature de l'espace des prédicteurs dans lequel nous trouvons ces frontières de décision, les Support Vector Machines peuvent s'adapter aisément au traitement de problèmes plus ou moins complexes de classification et de régression. STATISTICA SVM intègre quatre types de modèles de Support Vector avec différents noyaux pour l'expansion des fonctions de base, notamment linéaire, polynomial, RBF (fonction à base radiale) et sigmoïde. Ce module permet également de traiter des données déséquilibrées.

Réseaux Bayésiens Naïfs. Il s'agit d'une méthode Bayésienne bien connue, initialement développée pour traiter des tâches de classification. Compte tenu de sa simplicité, c'est-à-dire sous l'hypothèse que les variables indépendantes sont statistiquement indépendantes, les modèles Bayésiens Naïfs constituent des outils efficaces de classification, simples à utiliser et  à interpréter. Les Réseaux Bayésiens Naïfs sont particulièrement efficaces lorsque le nombre de dimensions de l'espace des variables indépendantes (c'est-à-dire le nombre de variables en entrée) est élevé (un problème connu sous le nom du "problème" de dimensionnalité). Pour les raisons évoquées précédemment, les Réseaux Bayésiens Naïfs produisent souvent de meilleurs résultats que d'autres méthodes plus élaborées de classification. STATISTICA Réseaux Bayésiens Naïfs vous permet d'utiliser diverses méthodes pour modéliser les distributions conditionnelles des entrées, notamment la distribution normale, lognormale, gamma et Poisson.

K Plus Proches Voisins. STATISTICA K Plus Proches Voisins est une méthode basée sur la mémoire, qui contrairement à d'autres méthodes statistiques, ne nécessite aucun apprentissage (c'est-à-dire qu'il n'y a aucun modèle à ajuster). Elle appartient à la catégorie des Méthodes Prototypes. Elle fonctionne selon le principe intuitif que les objets les plus proches ont le plus de chances d'appartenir à la même catégorie. Ainsi, avec la méthode des K Plus Proches Voisins, les prévisions reposent sur un ensemble d'exemples prototypes qui servent à prévoir de nouvelles données (c'est-à-dire, inconnues) sur la base du vote majoritaire (pour les tâches de classification) ou sur la base de la moyenne (pour les tâches de régression) des K plus proches prototypes (d'où le nom K Plus Proches Voisins).

Ces programmes ont la faculté de traiter des fichiers de données comportant de très nombreuses observations. En outre, ils peuvent traiter à la fois des variables indépendantes (prédicteurs) continues et catégorielles. Dans certains cas, vous pouvez effectuer un traitement préalable des données en les réduisant afin d'améliorer le pouvoir prédictif du modèle (c'est-à-dire la possibilité de prévoir correctement des données inconnues). Tous les programmes offrent trois méthodes distinctes pour répartir les données en sous-ensemble d'apprentissage et de test. Par ailleurs, vous pouvez, dans certains cas, utiliser la technique de la validation croisée sur les données d'apprentissage afin de sélectionner divers paramètres du modèle parmi un ensemble de valeurs données. Ces options permettent de résoudre le problème du sur-ajustement en limitant la complexité du modèle ou en offrant un contrôle indépendant de la performance du modèle à l'aide de l'ensemble de test.

Vous pouvez produire un grand nombre de graphiques et de feuilles de données pour tester la qualité de l'ajustement et vous aider à interpréter les résultats. Différentes options du générateur de code vous permettent d'enregistrer les modèles estimés (avec tous leurs paramètres) en vue du déploiement, en langage C/C++/C#, Visual Basic ou PMML (voir aussi la rubrique Utiliser du Code C/C++/C# pour le Déploiement). En outre, STATISTICA Machine Learning est totalement automatisé et fait partie intégrante de STATISTICA Data Miner, que vous pouvez utiliser vous construire vos applications sur mesure.

Séparateurs à Vaste Marge (SVM - Support Vector Machines)

La technique des Séparateurs à Vaste Marge (SVM - Support Vector Machines) (également appelées Machines à Vecteur de Support) repose sur le concept de plans de décision définissant des frontières de décision. Un plan de décision est un plan qui permet de séparer un ensemble d'objets appartenant à des classes différentes. L'illustration ci-dessous constitue un exemple représentatif. Dans cet exemple, les objets appartiennent soit à la classe VERTE, soit à la classe ROUGE. La droite de séparation définit une frontière à droite de laquelle tous les objets sont VERTS et à gauche de laquelle tous les objets sont ROUGES. Tout nouvel objet (matérialisé par un cercle blanc) apparaissant à gauche sera affecté à la classe ROUGE (ou au contraire affecté à la classe VERTE s'il se trouve à droite de la ligne de séparation).

L'exemple classique illustré ci-dessus est un modèle de classification linéaire, c'est-à-dire un modèle de classification qui va répartir un ensemble d'objets dans leurs groupes respectifs (VERT et ROUGE dans le cas présent) à l'aide d'une droite. La plupart des tâches de classification n'est malheureusement pas aussi simple, et il faut souvent recourir à des structures plus complexes pour trouver une séparation optimale, c'est-à-dire classer correctement de nouveaux objets (les observations de test) sur la base des exemples disponibles (observations d'apprentissage). C'est le cas dans l'illustration ci-dessous. Par rapport au schéma précédent, il est évident qui nous avons besoin d'une courbe (qui est plus complexe qu'une droite) pour séparer totalement les objets VERTS des objets ROUGES. Les tâches de classification qui utilisent des lignes de séparation pour faire la distinction entre des objets appartenant à des classes distinctes sont connues sous le nom de modèles de classification (ou classifieurs ou encore classificateurs) par hyperplans de séparation. Les Support Vector Machines sont particulièrement bien adaptés pour traiter ce type de tâches.

Le schéma ci-dessous illustre le principe fondamental des Support Vector Machines. Ici, nous pouvons voir que les objets originaux (situés à gauche du schéma) sont transformés, c'est-à-dire réorganisés, à l'aide d'un ensemble de fonctions mathématiques appelées noyaux. Le processus de réorganisation des objets est appelé projection (transformation). Remarque : dans cette nouvelle configuration, nous pouvons séparer les objets projetés (situés à droite du schéma) par une ligne droite, et par conséquent, au lieu de construire une courbe complexe (comme à gauche du schéma), nous pouvons nous contenter de trouver une droite qui va séparer de façon optimale les objets VERTS des objets ROUGES.

Notes et Informations Techniques

STATISTICA Support Vector Machine (SVM) est avant tout une méthode de classification qui permet de réaliser des tâches de classification en construisant des hyperplans dans un espace multidimensionnel, afin de séparer des observations appartenant à des classes différentes. STATISTICA SVM permet également de traiter des tâches de régression et peut utiliser à la fois des variables catégorielles et continues. Pour les variables catégorielles, le programme va créer des variables muettes (dummies) avec les modalités 0 ou 1. Ainsi, une variable dépendante catégorielle à trois modalités, disons (A, B, C), sera représentée par un ensemble de trois variables muettes :

A: {1 0 0}, B: {0 1 0}, C: {0 0 1}

Afin de construire un hyperplan optimal, SVM va utiliser un algorithme itératif d'apprentissage, qui va permettre de minimiser la fonction d'erreur. Selon la forme de la fonction d'erreur, nous pouvons classer les modèles SVM en quatre groupes distincts :

  • SVM de Type 1 pour la Classification (également appelée Classification C-SVM)

  • SVM de Type 2 pour la Classification (également appelée Classification nu-SVM)

  • SVM de Type 1 pour la Régression (également appelée Régression epsilon-SVM)

  • SVM de Type 2 pour la Régression (également appelée Régression nu-SVM)

Ci-dessous, une brève synthèse de chaque modèle.

SVM pour la Classification

SVM de Type 1 pour la Classification

Pour ce type de SVM, l'apprentissage va chercher à minimiser la fonction d'erreur suivante :

sous les contraintes :

C représente la constante de capacité, w représente le vecteur des coefficients, b représente une constant et représente des paramètres permettant de traiter les données non séparables (entrées). L'indice i varie pour les N observations d'apprentissage. Remarque : représente les libellés de classes et xi représente les variables indépendantes. Le noyau permet de transformer les données de l'espace original (indépendant) dans l'espace caractéristique (feature space). Plus C sera important, plus l'erreur sera pénalisée. Par conséquent, il faut choisir C avec soin afin d'éviter le sur-ajustement.

SVM de Type 2 pour la Classification

Contrairement aux SVM de Type 1 pour la Classification, le modèle SVM de Type 2 pour la Classification va chercher à minimiser la fonction d'erreur suivante :

sous les contraintes :

SVM pour la Régression

Dans un modèle SVM pour la régression, nous devons estimer la dépendance fonctionnelle entre la variable dépendante y et un ensemble de variables indépendantes x. Nous supposons, comme pour d'autres problèmes de régression, que la relation entre les variables indépendantes et la variable dépendante s'exprime comme la somme d'une fonction déterministe f et d'une certaine composante additive de bruit :

y = f(x) + bruit

La tâche consiste alors à trouver la forme fonctionnelle de f qui permet de prévoir correctement de nouvelles observations encore inconnues de SVM. C'est ce que nous obtenons en effectuant l'apprentissage du modèle SVM sur un échantillon, c'est-à-dire l'ensemble d'apprentissage ; ce processus, tout comme pour la classification (voir ci-dessous), consiste à optimiser de façon séquentielle une fonction d'erreur. Selon la forme de cette fonction d'erreur, nous pouvons définir deux types de modèles SVM :

SVM de Type 1 pour la Régression

Pour ce type de SVM, la fonction d'erreur s'exprime comme suit :

que nous minimisons sous les contraintes :

SVM de Type 2 pour la Régression

Pour ce type de SVM, la fonction d'erreur est donnée par la formule :

que nous minimisons sous les contraintes :

Fonctions Noyaux

STATISTICA SVM vous permet d'utiliser un certain nombre de noyaux dans vos modèles de Support Vector Machines. Ces noyaux peuvent être de type linéaire, polynomial, fonction gaussienne radiale (RBF) et sigmoïde :

La fonction gaussienne radiale (RBF) est de loin le type de noyaux le plus fréquent en Séparateurs à Vaste Marge (SVM - Support Vector Machines). Ceci, en raison de ses réponses localisées et finies sur toute l'étendue de l'axe réel x.

Réseaux Bayésiens Naïfs (Classification)

La technique de classification par les Réseaux Bayésiens Naïfs repose sur le théorème appelé théorème Bayésien et donne généralement d'excellents résultats lorsque le nombre de dimensions en entrée est élevé. Malgré leur simplicité, les Réseaux Bayésiens Naïfs donnent souvent de meilleurs résultats que certaines méthodes plus sophistiquées de classification.

Afin d'illustrer le concept de Classifieur Bayésien Naïf, considérons l'exemple reporté ci-dessus. Comme indiqué, nous pouvons classer les objets dans la catégorie VERT ou dans la catégorie ROUGE. Notre problème va consister à classer de nouvelles observations, c'est-à-dire de décider à quelles classes nous devrons les affecter, sur la base des objets actuellement disponibles.

Dans la mesure où il existe deux fois plus d'objets VERTS que de ROUGES, il est raisonnable de penser qu'une nouvelle observation (que nous n'avons pas encore observée) a deux fois plus de chances d'appartenir à la catégorie VERT qu'à la catégorie ROUGE. Dans l'analyse Bayésienne, ce phénomène est appelé probabilité a priori. Les probabilités a priori reposent sur notre expérience passée, qui dans le cas présent se résume au pourcentage d'objets VERTS et d'objets ROUGES, et permettent généralement de prévoir des événements avant qu'ils ne se produisent.

Nous pouvons donc écrire :

Dans la mesure où nous avons au total 60 objets, dont 40 sont VERTS et 20 sont ROUGES, nous pouvons écrire les probabilités a priori d'appartenance aux différentes classes comme suit :

Nos probabilités a priori étant formulées, nous pouvons à présent classer un nouvel objet (matérialisé par un cercle BLANC). Puisque la séparation entre les classes d'objets est relativement nette, nous pouvons raisonnablement considérer que plus nous avons d'objets VERTS (ou ROUGES) à proximité de X, plus nous avons de chances pour que la nouvelle observation appartienne à cette couleur particulière. Pour mesurer cette vraisemblance, nous traçons un cercle autour de X de sorte qu'il contienne un certain nombre de points (déterminé a priori) indépendamment de leur classe d'appartenance. Nous comptabilisons ensuite le nombre de points présents dans le cercle qui appartiennent à chacune des classes. Ce calcul nous permet de déterminer la vraisemblance :

D'après l'illustration ci-dessus, il est évident que la Vraisemblance de X sachant VERT est plus faible que la Vraisemblance de X sachant ROUGE, puisque le cercle contient 1 objet VERT et 3 objets ROUGES. Par conséquent :

Alors que les probabilités a priori indiquent que X a plus de chances d'appartenir à la catégorie VERT (puisqu'il existe deux fois plus de VERTS que de ROUGES) la vraisemblance donne le résultat inverse (puisqu'il existe plus d'objets ROUGES à proximité de X qu'il n'en existe de VERTS). Dans l'analyse Bayésienne, la classification finale est obtenue en combinant ces deux sources d'informations, c'est-à-dire les probabilités a priori et la vraisemblance, en une probabilité a posteriori à l'aide de la règle dite de Bayes (du nom du célèbre mathématicien anglais, le Révérend Thomas Bayes 1702-1761).

Nous allons donc en fin de compte classer X comme un ROUGE puisque cette classe obtient la plus forte probabilité a posteriori.

Remarque. Les probabilités ci-dessus ne sont pas normalisées. Toutefois, ceci n'affecte en rien le résultat de la classification puisque leurs constantes de normalisation sont identiques.

Notes et Informations Techniques

Dans la sections précédente, nous avons traité un exemple intuitif pour expliquer le fonctionnement de la classification par les Réseaux Bayésiens Naïfs. Dans cette section, nous allons maintenant nous attacher aux questions techniques sous-jacentes. STATISTICA Réseaux Bayésiens Naïfs peut traiter un nombre arbitraire de variables indépendantes, qu'elles soient de nature catégorielles ou continues. Étant donné un ensemble de variables, X = {x1,x2,x...,xd}, nous souhaitons calculer la probabilité a posteriori de l'événement Cj parmi un ensemble de possibles C = {c1,c2,c...,cd}. Dans une terminologie plus courante, X représente les prédicteurs et C représente l'ensemble des modalités de la variable dépendante. En utilisant la règle de Bayes, nous pouvons écrire :

p(Cj | x1,x2,x...,xd) représente la probabilité a posteriori d'appartenir à la classe, c'est-à-dire la probabilité que X appartienne à Cj. Puisque les Réseaux Bayésiens Naïfs considèrent que les probabilités conditionnelles des variables indépendantes sont statistiquement indépendantes, nous pouvons décomposer la vraisemblance en un produit de termes :

et reformuuler la probabilité a posteriori comme suit :

Grâce à la règle de Bayes ci-dessus, nous allons affecter une nouvelle observation X à la classe Cj qui possède la plus forte probabilité a posteriori.

Bien que l'hypothèse selon laquelle les variables prédictives (indépendantes) sont indépendantes entre elles ne soit pas toujours vérifiée, elle simplifie grandement le problème de classification, puisqu'elle permet aux densités conditionnelles de classes p(xk | Cj) d'être calculées séparément pour chaque variable, c'est-à-dire que nous allons ainsi passer d'un problème multidimensionnel à un certain nombre de problèmes à une seule dimension. En pratique, les Réseaux Bayésiens Naïfs vont réduire un problème d'estimation de densité à multiples dimensions à une estimation de la densité de noyaux à une dimension. Empiriquement, cette hypothèse semble affecter assez peu les probabilités a posteriori, notamment dans les régions proches des frontières de décision, et par conséquent le problème de classification lui-même s'en trouve peu affecté.

STATISTICA Réseaux Bayésiens Naïfs vous propose différents choix de modélisations en fonction de vos besoins analytiques. Vous pourrez notamment utiliser des fonctions de densité normale, lognormale, gamma et de Poisson :

Remarque : les indices k et j s'interprètent comme suit : prenons par exemple µkj pour la distribution normale. Pour k=1 et j=2, µ12 représente simplement la moyenne de la distribution normale de la 1ère variable indépendante pour la 2ème modalité C1 de la variable dépendante. Ainsi, µ12 représente la moyenne de la 1ère variable indépendante pour laquelle les entrées de la variable dépendante appartiennent au 2ème niveau catégoriel C1. De la même manière, σ12 représente l'écart-type de la distribution normale de la 1ère variable indépendante pour la 2ème modalité C2 de la variable dépendante. Par conséquent p(xk | Cj) représente la distribution de la 1ère variable indépendante pour la 2ème modalité C1 de la variable dépendante.

Remarque. Les variables de Poisson sont considérées comme des variables continues puisqu'elles sont davantage ordinales que véritablement catégorielles. Pour les variables catégorielles, nous utilisons une probabilité discrète dont les valeurs des niveaux catégoriels sont proportionnels à leurs effectifs conditionnels dans les données d'apprentissage.

K-Plus Proches Voisins

Afin d'illustrer l'analyse des K Plus Proches Voisins, considérons la problématique de la classification d'un nouvel objet (point de requête) parmi un ensemble d'exemples connus. C'est le schéma reporté ci-dessous, qui matérialise les exemples connus (instances) par des signes plus et moins et le point de requête par un cercle rouge. Notre problème consiste à déterminer le résultat (affecter à une classe) du point de requête en fonction d'un certain nombre de voisins les plus proches. En d'autres termes, nous voulons savoir si nous devons classer le point de requête comme un signe plus ou comme un signe moins.

Considérons le résultat de la procédure des Plus Proches Voisins sur la base du (premier) plus proche voisin. Il est évident dans ce cas que la procédure des Plus Proches Voisins va affecter un signe plus au point de requête (puisque le point le plus proche est matérialisé par un signe plus). Passons à présent le nombre des plus proches voisins à 2, c'est-à-dire les 2 plus proches voisins. Cette fois, la procédure des Plus Proches Voisins ne va pas être en mesure de classer le résultat du point de requête puisque le second point le plus proche est un moins, et que les deux signes plus et moins obtiennent le même score (c'est-à-dire obtiennent le même nombre de votes). Augmentons encore le nombre des plus proches voisins et passons cette fois à 5 (5 plus proches voisins). Nous allons ainsi définir la zone des plus proches voisins, que nous avons matérialisée par un cercle sur la figure précédente. Dans la mesure où nous avons 2 signes plus et 3 signes moins dans ce cercle, la procédure des Plus Proches Voisins va affecter un signe moins au résultat du point de requête.

Régression

Dans cette section, nous allons généraliser le concept des K Plus Proches Voisins aux problèmes de régression. Les problèmes de régression s'attachent à prévoir le résultat d'une variable dépendante à partir d'un ensemble de variables indépendantes. Examinons tout d'abord le schéma ci-dessus où un ensemble de points (matérialisés par des carrés verts) sont issus de la relation entre une variable indépendante x et une variable dépendante y (la courbe rouge). Pour un ensemble donné d'objets verts (connus et appelés exemples) nous utilisons la méthode des K Plus Proches Voisins pour prévoir le résultat de X (appelé point de requête) à partir de l'ensemble d'exemple (les carrés verts).

Pour commencer, considérons l'exemple de la méthode du plus proche voisin (un seul point). Dans ce cas, nous allons rechercher dans l'ensemble des exemples (les carrés verts) celui qui est le plus proche du point de requête X. Dans notre cas particulier, il s'agit de x4. Nous utilisons alors le résultat de x4 (c'est-à-dire y4) comme réponse au résultat de X (c'est-à-dire Y). Ainsi, pour la solution à 1 plus proche voisin, nous pouvons écrire :

Y = y4

Considérons à présent la méthode des 2 plus proches voisins. Dans ce cas, nous allons identifier les deux points les plus proches de X, c'est-à-dire dans notre exemple, y3 et y4. Nous calculons la moyenne de leurs résultats, pour obtenir la solution de Y qui s'exprime comme suit :

La logique ci-dessus peut être étendue à un nombre arbitraire K de plus proches voisins. Pour résumer, avec la méthode des K plus proches voisins, le résultat Y du point de requête X se calcule comme la moyenne des résultats de ses K plus proches voisins.

Détails Techniques

STATISTICA K Plus Proches Voisins est un modèle fondé sur la mémoire ; il est défini par un ensemble d'objets appelés exemples (ou encore, instances) pour lesquels les résultats sont connus (c'est-à-dire que ces exemples possèdent des libellés). Chaque exemple est représenté par une observation constituée d'un ensemble de valeurs indépendantes auxquelles correspondent un ensemble de résultats dépendants (libellés). Les variables dépendantes et indépendantes peuvent être continues ou catégorielles. Dans le cas de variables dépendantes continues, nous avons affaire à un problème de régression ; dans l'autre cas, il s'agit d'un problème de classification. Par conséquent, STATISTICA K Plus Proches Voisins peut traiter à la fois des problèmes de régression et de classification.

Étant donnée une nouvelle observation avec des valeurs indépendantes connues (le point de requête), nous souhaitons estimer le résultat de cette nouvelle observation à partir d'exemples connus constitués par les K plus proches voisins. STATISTICA K Plus Proches Voisins va alors identifier les K exemples les plus proches du point de requête (dont la distance avec le point de requête est la plus faible), d'où le nom K Plus Proches Voisins. Dans les problèmes de régression, les prévisions par les K Plus Proches Voisins sont calculées en prenant la moyenne des résultats des K plus proches voisins ; pour les problèmes de classification, c'est le vote majoritaire qui est utilisé.

Le choix de K est essentiel dans la construction du modèle des K Plus Proches Voisins. En fait, K constitue l'un des paramètres les plus importants du modèle, et peut influencer fortement la qualité des prévisions. Vous pouvez considérer que d'une certaine manière, le nombre K de plus proches voisins est un paramètre de lissage. Pour un problème donné, une valeur faible de K va conduire à une variance importante dans les prévisions. Au contraire, si vous affectez une valeur importante à K, vous allez introduire un biais important dans votre modèle. Par conséquent, la valeur de K doit être suffisamment importante pour minimiser la probabilité d'erreur de classement mais aussi, raisonnablement faible (par rapport au nombre d'observations dans l'échantillon des exemples) pour que les K points les plus proches soient suffisamment proches du point de requête. Ainsi, comme pour tout paramètre de lissage, il existe une valeur optimale de K qui permet d'obtenir un bon compromis entre le biais et la variance du modèle. STATISTICA K Plus Proches Voisins peut fournir une estimation de K en utilisant un algorithme connu sous le nom de validation croisée (Bishop, 1995).

Validation Croisée

La validation croisée est une technique bien établie permettant d'estimer les paramètres inconnus du modèle. Penchons-nous sur la mise en oeuvre de cette technique pour estimer K.

Le principe fondamental de cette méthode consiste à répartir l'échantillon de données en un certain nombre v d'ensembles (des segments ou sous-échantillons disjoints, tirés au hasard). Pour une valeur déterminée de K, nous appliquons le modèle des K Plus Proches Voisins pour calculer les prévisions sur le v-ième segment (c'est-à-dire que nous utilisons les v-1 segments comme des exemples) puis nous estimons l'erreur. Le choix de l'erreur est généralement la somme des carrés pour les problèmes de régression, et la précision (calculée comme le pourcentage d'observations correctement classées) dans les problèmes de classification. Ce processus est alors appliqué successivement à tous les choix possibles de v. À l'issue des v ensembles (cycles), nous prenons la moyenne de ces erreurs ainsi calculées pour définir une mesure de la stabilité du modèle (c'est-à-dire dans quelle mesure le modèle peut prévoir les points de requête). Les étapes précédentes sont ensuite répétées pour différentes valeurs de K et la valeur qui permet d'obtenir l'erreur la plus faible (ou la meilleure précision de classification) est alors choisie comme valeur optimale de K (optimale au sens de la validation croisée). Remarque : le processus de validation croisée nécessite de très nombreux calculs et vous devez prévoir un certain temps pour l'exécution de cet algorithme, en particulier lorsque la taille de l'échantillon d'exemple est important. Vous pouvez également spécifier manuellement la valeur de K. Cette démarche reste acceptable si vous avez déjà une idée de la valeur de K à appliquer (c'est-à-dire, à partir d'analyses antérieures des K Plus Proches Voisins que vous avez déjà réalisées sur des données similaires).

Métrique des Distances

Comme indiqué précédemment, pour un point de requête déterminé, la méthode des K Plus Proches Voisins va réaliser ses prévisions à partir du résultat des K voisins les plus proches de ce point. Par conséquent, pour effectuer des prévisions par les K Plus Proches Voisins, nous devons préalablement définir une certaine métrique pour mesurer les distances entre le point de requête est les observations issues de l'échantillon des exemples. La mesure la plus courante est de loin la distance euclidienne. Mais vous pouvez également utiliser d'autres mesures comme la distance euclidienne au carré, le City-block ou la distance de Chebychev :

x et p représentent respectivement le point de requête et une observation issue de l'échantillon des exemples.

Prévisions des K Plus Proches Voisins

Après avoir sélectionné la valeur de K, vous pouvez effectuer vos prévisions sur la base des exemples des K Plus Proches Voisins. Pour les problèmes de régression, les prévisions des K Plus Proches Voisins se calculent comme la moyenne des résultats des K plus proches voisins.

yi représente la i-ième observation de l'échantillon des exemples et y représente la prévision (résultat) du point de requête. Contrairement à la régression, les prévisions des K Plus Proches Voisins dans les problèmes de classification reposent sur un schéma de vote où le vainqueur détermine le libellé qui est affecté au point de requête.

Remarque. Pour les problèmes de classification binaires, le programme utilise des valeurs impaires de y = 1,3,5 pour éviter les ex-aequos, c'est-à-dire deux classes obtenant le même score.

Husqu'à présent, nous avons parlé de l'analyse des K Plus Proches Voisins sans nous attacher aux distances relatives entre les K exemples les plus proches et le point de requête. En d'autres termes, nous avons considéré que les K voisins avaient la même influence sur les prévisions, quelle que soit leur distance relative au point de requête. Une autre approche (défendue par Shepard, 1968) consiste à utiliser des valeurs relativement grandes de K (voire l'ensemble de l'échantillon des prototypes) avec une importance d'autant plus élevée que les observations sont proches du point de requête. C'est ce que permet la technique dite des distances pondérées.

Pondération des Distances

Dans la mesure où les prévisions des K Plus Proches Voisins se fondent sur l'hypothèse intuitive que les objets les plus proches sont potentiellement similaires, il est assez logique de discriminer les K voisins les plus proches dans le calcul des prévisions, c'est-à-dire d'affecter un rôle plus important aux points les plus proches du point de requête parmi l'ensemble des K plus proches voisins pour déterminer le résultat de ce point de requête. L'introduction d'un ensemble de W pondérations, une pour chacun des voisins les plus proches, permet de définir la proximité relative de chaque voisin par rapport au point de requête. Ainsi, nous pouvons écrire :

D(x, pi ) représente la distance entre le point de requête x et la i-ième observation pi de l'échantillon des exemples. Les pondérations ainsi définies satisfont l'expression :

Par conséquent, pour les problèmes de régression, nous avons :

Pour les problèmes de classification, nous prenons le maximum de l'équation précédente pour chacune des variables de classement.

Ainsi, lorsque K>1, nous pouvons naturellement définir l'écart-type des prévisions dans les problèmes de régression en utilisant la formule :