3NAR (n nearest neighbor avrage rapid)

par Ludovic CASTIGLIA

Résumé du projet

Le but de ce projet est de produire un code python qui implémente l'algorithme KNN naïf et 3nar (une version optimisée de l'algorithme KNN naïf). Comparer les performances de ces deux algorithmes. Puis utiliser l'algorithme 3nar dans des cas réel d'utilisation comme par exemple du traitement d'image (réduction de bruit). Pour trouver les valeurs RGB d'un nouveau pixel, nous calculons la moyenne ou la médiane des valeurs R G et B des n pixels voisins. Utilisant donc l'algorithme KNN non plus pour de la classification, mais pour de la régression. Ainsi, chaque point dans ce cas est défini par deux dimensions de coordonné et possède une valeur à trois dimensions.

Principe de l'algorithme 3nar

Le but de cet algorithme repose sur le fait de ne pas avoir à calculer la distance entre tous les points de l'espace et le point que l'on cherche pour trouver les n plus proches voisins. En effet, calculer la distance avec tous les autres points est un processus coûteux et ce plus le nombre de points augmente dans notre espace. Ainsi pour 3nar, nous allons diviser l'espace en région. Lorsque nous voudrons trouver les voisins d'un point, nous trouvons dans quel espace il est situé (calculé en fonction de ses coordonnées), puis nous calculons la distance avec tous les points de cette région, nous sélectionnons ensuite tous les points qui sont à une distance inférieure à la distance entre le point et la bordure de cet espace. Puis s'il n'y a pas assez de points sélectionnés, on trouve les espaces voisins à notre espace et on recommence à sélectionner les points, mais dans notre nouvel espace. On répète ces opérations jusqu'à trouver les n plus proches voisins de notre point dans l'espace. Nous pouvons également enregistrer le résultat de certaines opérations récurrentes comme trouver les coordonnées des espaces autour d'un espace en mémoire. Cela nous permet d'éviter de les calculer plusieurs fois et ainsi nous fait gagner en complexité. Remplaçant ainsi une opération qui peut être en O(n²) ou pire en O(1) car nous n'avons à calculer qu'une seule fois ce résultat dans toutes l'exécution de notre programme.

Calendrier du projet

Dans un premier temps, je vais me concentrer sur la réalisation des deux algorithmes naïf et 3nar. J'estime que j'aurais fini cette tâche autour du 29/01/2025. Puis une fois que j'aurais réalisé ces algorithmes, je vais développer les exemples d'utilisations. En fonction de la complexité des exemples, cela peut prendre plus ou moins de temps, mais je devrais être capable de finir avant le 31/01/2025 au soir. Enfin, durant le week-end du 01|02 février, je vais réaliser le rapport final. Avant de soumettre mon code et mon rapport le 02/02/2025 au soir.

Code fournit:

La première réalisation va être le code en lui-même de KNN naïf et de 3nar.

Deuxièmement, une démo de l'algorithme dans le cas d'une relation linéaire (le prix des habitations de Californie en fonction du nombre de m²).

Troisièmement, une démo de l'algorithme dans le cas d'une relation non-linéaire fictive (les données vont être inventées à partir d'une relation polynomiale aléatoire.)

Enfin, si j'ai le temps, j'aimerais également réaliser une démo de l'algorithme dans le cas de la réduction de bruit d'une image (bruit qui serait ajouté artificiellement avant le traitement).

Données utilisées:

Le prix des maisons en fonction du nombre de m²: https://www.kaggle.com/datasets/yasserh/housing-prices-dataset/data

L'image utilisée pour le traitement: https://www.auvergnevolcansancy.com/app/uploads/2022/08/puy-de-dome-et-de-come-p.soisson-683x1024.jpg