Python Programming for Biology: Bioinformatics and Beyond

k-nearest neighbours

If you can describe your data as position vectors in a feature space, and have a good way

of  calculating  the  distance  or  similarity  between  points,  then  the  k-nearest  neighbour

method can be used to classify an unknown data vector by comparing it to data vectors for

which there is a known classification. In essence this is like taking a voting poll. For an

unclassified  query  point  you  look  for  a  given  number,

2

 k,  of  nearest  neighbours  in  the

feature space that you have a classification for. You then assume that the classification of

the  query  is  the  same  as  the  majority  of  its  k  neighbours.  Implementing  this  method

successfully  is  dependent  on  having  reasonable  training  data;  you  must  have  sufficient

numbers of well-dispersed vectors of known classification so that any query is not too far

from a known data point, and one class of data should not be significantly more abundant

than  any  other,  otherwise  the  more  populous  classification  will  have  a  positive  bias  for

being a neighbour to the query. It should also be noted that this method can be fairly slow,

given  that  you  have  to  calculate  distances  to  many  classified  points;  however,  if  the

method  works  well  you  can  optimise  later,  for  example,  by  using  constructions  like  k-

dimensional trees

3

to find nearest neighbours without having to check every data point.

---