A hybrid method of genetic algorithm and hill climbing for selecting instances and features in noisy data to enhance nearest neighbor classifier

The performance of the Nearest Neighbor (NN) classifier varies with the similarity function, noisy data, and irrelevant features. Also, NN utilizes all training instances in the generalization phase, thereby leading to a decrease in execution speed and an increase in storage, especially in the cases of high-dimensional problems. This has encouraged researchers in the field to investigate methods for adapting the similarity metric, removing noisy instances, and irrelevant features to improve the generalization speed and classification rate. In this thesis, a hybrid method is formed by using a genetic algorithm (GA) and an instance weighting algorithm, building upon prior work aimed at enhancing the k-NN algorithm through a mixing-by-weighting approach. The objective is to achieve high classification accuracy and minimize the size of the instance and feature sets. The proposed hybrid method utilizes a genetic algorithm (GA) to select prototypes and relevant features. However, a potential issue with GA is the selection of noisy instances as prototypes. To mitigate this, a hill climbing instance weighting method is employed to reduce the impact of noisy prototypes. In each generation of GA, the hybrid method assigns weights to each prototype selected by GA. The weighting algorithm plays a crucial role in determining the influence of each selected prototype by assigning different weights to them. Assigning a large weight to a discriminant prototype increases its influence in classifying numerous instances while reducing the weight of a noisy prototype diminishes its effect in the classification process. Experimental results demonstrate that the proposed scheme significantly improves classification accuracy while simultaneously removing more than 98% and 88% (the average of 13 UCI datasets) of instances and irrelevant features, respectively.

Le prestazioni del classificatore Nearest Neighbor (NN) variano con la funzione di similarità, i dati rumorosi e le caratteristiche irrilevanti. Inoltre, il NN utilizza tutte le istanze di addestramento nella fase di generalizzazione, portando così a una diminuzione della velocità di esecuzione e a un aumento dello spazio di archiviazione, specialmente nei casi di problemi ad alta dimensionalità. Questo ha incoraggiato i ricercatori nel campo a indagare metodi per adattare la metrica di similarità, rimuovere istanze rumorose e caratteristiche irrilevanti per migliorare la velocità di generalizzazione e il tasso di classificazione. In questa tesi, viene proposto un metodo ibrido mediante l’uso di un algoritmo genetico (GA) e un algoritmo di pesatura delle istanze, basato su lavori precedenti volti a migliorare l’algoritmo k-NN attraverso un approccio di miscelazione mediante pesatura. L’obiettivo è ottenere un’alta precisione di classificazione e minimizzare le dimensioni degli insiemi di istanze e caratteristiche. Il metodo ibrido proposto utilizza un algoritmo genetico (GA) per selezionare prototipi e caratteristiche rilevanti. Tuttavia, un potenziale problema con il GA è la selezione di istanze rumorose come prototipi. Per mitigare questo problema, viene utilizzato un metodo di pesatura delle istanze di tipo hill climbing per ridurre l’impatto dei prototipi rumorosi. In ogni generazione del GA, il metodo ibrido assegna pesi a ciascun prototipo selezionato dal GA. L’algoritmo di pesatura svolge un ruolo cruciale nel determinare l’influenza di ciascun prototipo selezionato assegnando loro pesi differenti. Assegnare un peso elevato a un prototipo discriminante aumenta la sua influenza nella classificazione di numerose istanze, mentre ridurre il peso di un prototipo rumoroso ne diminuisce l’effetto nel processo di classificazione. I risultati sperimentali dimostrano che lo schema proposto migliora significativamente l’accuratezza di classificazione eliminando contemporaneamente più del 98% e dell’88% (media di 13 dataset UCI) delle istanze e delle caratteristiche irrilevanti, rispettivamente.