Return to Snippet

Revision: 22501
at January 13, 2010 13:45 by ahawker

Initial Code
/// <summary>
        /// Given a single tuning data instance and attribute indices, find the
        /// k nearest neighbors based on Euclidean distance.
        /// </summary>
        /// <param name="tune">Single tuning instance</param>
        /// <param name="indices">Indices of features used</param>
        /// <param name="k">Number of neighbors to find</param>
        /// <returns>KVP(double,DataInstance)</returns>
        private List<KeyValuePair<double,DataInstance>> _FindNearestNeighbors(DataInstance tune, List<int> indices, int k){
            var neighbors = new List<KeyValuePair<double,DataInstance>>();
            foreach(DataInstance trainingInstance in _DataSet.DataEntries){
                if(trainingInstance == tune) continue;
                double distance = _ComputeDistance(tune, trainingInstance, indices);
                neighbors.Add(new KeyValuePair<double,DataInstance>(distance, trainingInstance));
            return neighbors.OrderBy(n=>n.Key).Take(k).ToList();

        /// <summary>
        /// Computes the Euclidean distance between the DataInstances tune/train using
        /// the features located at the given indices.
        /// </summary>
        /// <param name="indices">Indices of the features used</param>
        /// <param name="tune">Single tuning instance</param>
        /// <param name="train">Single training instance</param>
        /// <returns>Double</returns>
        private double _ComputeDistance(DataInstance tune, DataInstance train, List<int> indices){
            double d = 0;
            foreach(int i in indices){
                    case Types.continuous:
                        d += _Distance(tune[i], train[i]);
                    case Types.discrete:
                        d += (tune[i] == train[i]) ? 0 : 1;
                    case Types.output:
            return Math.Sqrt(d);

        /// <summary>
        /// Given two values, compute (x - y)^2.
        /// Subroutine for Euclidean Distance computation.
        /// </summary>
        /// <param name="tune">Value from our local tuning set.</param>
        /// <param name="train">Value from our local training set.</param>
        /// <returns>Double</returns>
        private double _Distance(string tune, string train){
            double x = double.Parse(tune);
            double y = double.Parse(train);
            return Math.Pow(x - y, 2);

Initial URL

Initial Description
Snippet out of my C# KNN implementation.

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

Initial Title
KNN - Use Euclidean Distance to find nearest neighbors

Initial Tags
c, Net

Initial Language