Il metodo k-Nearest Neighbors e le sue principali estensioni

Abstract

Questa tesi analizza in modo sistematico l’algoritmo k-Nearest Neighbors (k-NN), uno dei metodi non parametrici più noti nell’ambito della statistica matematica e dell’apprendimento supervisionato, insieme alle sue principali estensioni proposte in letteratura. Dopo averne introdotto il contesto storico e i fondamenti teorici, il lavoro approfondisce il ruolo centrale della metrica di distanza nella definizione della nozione di prossimità, esaminando le distanze della famiglia di Minkowski, la distanza di Mahalanobis e l’importanza delle tecniche di standardizzazione e normalizzazione delle feature. Particolare attenzione è dedicata a metodi adattivi della metrica, come il Discriminant Adaptive Nearest Neighbors (DANN), che modifica localmente la distanza per enfatizzare le direzioni maggiormente discriminanti nello spazio delle variabili. Successivamente, vengono analizzate alcune tra le varianti più rilevanti del k-NN, tra cui il Weighted k-NN, il Fuzzy k-NN e l’Adaptive Nearest Neighbors (AdaNN), mettendone in evidenza motivazioni, formulazioni matematiche, vantaggi e limiti. La parte finale del lavoro è dedicata a un’analisi sperimentale condotta su dataset reali, nella quale i diversi approcci vengono confrontati utilizzando opportune metriche di valutazione. I risultati consentono di evidenziare i compromessi tra accuratezza predittiva, robustezza al rumore e costo computazionale, mostrando come le varianti adattive possano migliorare le prestazioni rispetto al k-NN classico in specifici contesti applicativi. Nel complesso, la tesi fornisce una visione organica e comparativa del metodo k-NN e delle sue estensioni, offrendo indicazioni utili per la scelta del modello più appropriato in funzione delle caratteristiche dei dati.

This thesis provides a systematic analysis of the k-Nearest Neighbors (k-NN) algorithm, one of the most well-known nonparametric methods in mathematical statistics and supervised learning, together with its main extensions proposed in the literature. After introducing its historical background and theoretical foundations, the study focuses on the central role of distance metrics in defining the notion of proximity, examining the Minkowski family of distances, the Mahalanobis distance, and the importance of feature standardization and normalization. Special attention is devoted to adaptive metric methods, such as Discriminant Adaptive Nearest Neighbors (DANN), which locally modify the distance measure in order to emphasize the most discriminative directions in the feature space. Subsequently, several relevant variants of the k-NN algorithm are discussed, including Weighted k-NN, Fuzzy k-NN, and Adaptive Nearest Neighbors (AdaNN), highlighting their motivations, mathematical formulations, strengths, and limitations. The final part of the thesis presents an experimental analysis conducted on real datasets, where the different approaches are compared using appropriate evaluation metrics. The results highlight the trade-offs between predictive accuracy, robustness to noise, and computational cost, showing that adaptive variants can outperform the classical k-NN method in specific application scenarios. Overall, this work offers a comprehensive and comparative overview of the k-NN algorithm and its main extensions, providing useful guidelines for selecting the most suitable approach based on the characteristics of the data.