Posted By

ahawker on 01/13/10


Tagged

c Net knn


Versions (?)

KNN - Use Euclidean Distance to find nearest neighbors


 / Published in: C#
 

Snippet out of my C# KNN implementation.

Uses leave-one-out cross validation tuning with our given K to find our nearest neighbors.

  1. /// <summary>
  2. /// Given a single tuning data instance and attribute indices, find the
  3. /// k nearest neighbors based on Euclidean distance.
  4. /// </summary>
  5. /// <param name="tune">Single tuning instance</param>
  6. /// <param name="indices">Indices of features used</param>
  7. /// <param name="k">Number of neighbors to find</param>
  8. /// <returns>KVP(double,DataInstance)</returns>
  9. private List<KeyValuePair<double,DataInstance>> _FindNearestNeighbors(DataInstance tune, List<int> indices, int k){
  10. var neighbors = new List<KeyValuePair<double,DataInstance>>();
  11. foreach(DataInstance trainingInstance in _DataSet.DataEntries){
  12. if(trainingInstance == tune) continue;
  13. double distance = _ComputeDistance(tune, trainingInstance, indices);
  14. neighbors.Add(new KeyValuePair<double,DataInstance>(distance, trainingInstance));
  15. }
  16. return neighbors.OrderBy(n=>n.Key).Take(k).ToList();
  17. }
  18.  
  19. /// <summary>
  20. /// Computes the Euclidean distance between the DataInstances tune/train using
  21. /// the features located at the given indices.
  22. /// </summary>
  23. /// <param name="indices">Indices of the features used</param>
  24. /// <param name="tune">Single tuning instance</param>
  25. /// <param name="train">Single training instance</param>
  26. /// <returns>Double</returns>
  27. private double _ComputeDistance(DataInstance tune, DataInstance train, List<int> indices){
  28. double d = 0;
  29. foreach(int i in indices){
  30. switch(_DataSet.Features[i].Type){
  31. case Types.continuous:
  32. d += _Distance(tune[i], train[i]);
  33. break;
  34. case Types.discrete:
  35. d += (tune[i] == train[i]) ? 0 : 1;
  36. break;
  37. case Types.output:
  38. default:
  39. break;
  40. }
  41. }
  42. return Math.Sqrt(d);
  43. }
  44.  
  45. /// <summary>
  46. /// Given two values, compute (x - y)^2.
  47. /// Subroutine for Euclidean Distance computation.
  48. /// </summary>
  49. /// <param name="tune">Value from our local tuning set.</param>
  50. /// <param name="train">Value from our local training set.</param>
  51. /// <returns>Double</returns>
  52. private double _Distance(string tune, string train){
  53. double x = double.Parse(tune);
  54. double y = double.Parse(train);
  55. return Math.Pow(x - y, 2);
  56. }

Report this snippet  

You need to login to post a comment.