The k-Nearest Neighbours algorithm, as described by Mitchell
15
, works by comparing a sample to be classified with known
samples, identifying the k samples that are nearest to the new one, and estimating the cocaine concentration of the new
sample by averaging them. In this work, cosine and Euclidian distance measures were used, and the averages were weighted
by the inverse of distance. In preliminary experiments, various values of k (number of neighbours) were tried, and k=3 was
selected for the main experiments.
These two methods were selected because they contrast strongly with each other: kNN is an instance-based learner, is fast,
is deterministic and is particularly sensitive to irrelevant and correlated attributes. Neural networks are model-based, are
slower, may converge to local maxima, and are less sensitive to irrelevant/correlated attributes although they also benefit
from feature selection. However, neural networks are able to represent complex non-linear relationships in data, giving good
performance on a wide range of prediction tasks.
3.3
Feature Selection Methods
In a ‘typical’ ML application with well-conditioned data, the number of cases is much larger than the number of attributes
per case. In this study, however, there are 36 cases with 510 attributes per case. For many ML techniques, this causes
problems. For example, a neural network with 510 inputs, 10 neurons in a single hidden layer, and 1 output layer would
have over 5000 degrees of freedom, which with just 36 cases will most often result in convergence to a poor local
minimum. Accordingly, feature selection has been used to reduce the number of attributes per case. The following
approaches to feature selection have been assessed:
1
Local Maxima
2
Optimal Search using a Genetic Algorithm
In each case, the impact of the feature selection methods on the performance of the ML algorithms has been assessed, as
discussed in Section 4 below. For purposes of comparison, the ML algorithms have also been applied without any feature
selection.
The Local Maxima approach involved selecting all points that appeared as peaks (defined as having at least two points on
each side with lower values) on the spectrum of the 100% cocaine sample, but excluding minor peaks below the average
value. This resulted in the selection of 17 points.
The Optimal Search approach was more sophisticated. The objective here was to find a set of attributes that was as small as
possible, with as high accuracy as possible measured relative to a learning algorithm. The optimal search was performed
using a Genetic Algorithm (GA), which is a technique based on the paradigm of biological evolution
16
. The essential idea is
that a population of potential solutions to a problem is created, and the fitness of each individual is assessed by calculating
the how appropriate it is for the problem. The fittest individuals are carried forward to the next generation, and the new
generation’s population is augmented by crossover (producing new individuals that combine features of existing
individuals) and mutation (random changes to an individual). The initial population is created at random, and bred for a
large number of generations until it reaches steady state. This is termed a wrapper approach to feature selection, as the GA
is wrapped around the learning algorithm.
In the first set of GA experiments, the learning algorithm chosen as the target for the accuracy measure was k-Nearest
Neighbours (kNN), as it runs fast and is known to be sensitive to cross-correlated attributes. Each individual consisted of a
string of 510 binary digits, representing a configuration with some attributes selected and others not, depending on whether
15
, works by comparing a sample to be classified with known
samples, identifying the k samples that are nearest to the new one, and estimating the cocaine concentration of the new
sample by averaging them. In this work, cosine and Euclidian distance measures were used, and the averages were weighted
by the inverse of distance. In preliminary experiments, various values of k (number of neighbours) were tried, and k=3 was
selected for the main experiments.
These two methods were selected because they contrast strongly with each other: kNN is an instance-based learner, is fast,
is deterministic and is particularly sensitive to irrelevant and correlated attributes. Neural networks are model-based, are
slower, may converge to local maxima, and are less sensitive to irrelevant/correlated attributes although they also benefit
from feature selection. However, neural networks are able to represent complex non-linear relationships in data, giving good
performance on a wide range of prediction tasks.
3.3
Feature Selection Methods
In a ‘typical’ ML application with well-conditioned data, the number of cases is much larger than the number of attributes
per case. In this study, however, there are 36 cases with 510 attributes per case. For many ML techniques, this causes
problems. For example, a neural network with 510 inputs, 10 neurons in a single hidden layer, and 1 output layer would
have over 5000 degrees of freedom, which with just 36 cases will most often result in convergence to a poor local
minimum. Accordingly, feature selection has been used to reduce the number of attributes per case. The following
approaches to feature selection have been assessed:
1
Local Maxima
2
Optimal Search using a Genetic Algorithm
In each case, the impact of the feature selection methods on the performance of the ML algorithms has been assessed, as
discussed in Section 4 below. For purposes of comparison, the ML algorithms have also been applied without any feature
selection.
The Local Maxima approach involved selecting all points that appeared as peaks (defined as having at least two points on
each side with lower values) on the spectrum of the 100% cocaine sample, but excluding minor peaks below the average
value. This resulted in the selection of 17 points.
The Optimal Search approach was more sophisticated. The objective here was to find a set of attributes that was as small as
possible, with as high accuracy as possible measured relative to a learning algorithm. The optimal search was performed
using a Genetic Algorithm (GA), which is a technique based on the paradigm of biological evolution
16
. The essential idea is
that a population of potential solutions to a problem is created, and the fitness of each individual is assessed by calculating
the how appropriate it is for the problem. The fittest individuals are carried forward to the next generation, and the new
generation’s population is augmented by crossover (producing new individuals that combine features of existing
individuals) and mutation (random changes to an individual). The initial population is created at random, and bred for a
large number of generations until it reaches steady state. This is termed a wrapper approach to feature selection, as the GA
is wrapped around the learning algorithm.
In the first set of GA experiments, the learning algorithm chosen as the target for the accuracy measure was k-Nearest
Neighbours (kNN), as it runs fast and is known to be sensitive to cross-correlated attributes. Each individual consisted of a
string of 510 binary digits, representing a configuration with some attributes selected and others not, depending on whether