K-nearest neighbours in C# for large number of dimensions

Question

I'm implementing the K-nearest neighbours classification algorithm in C# for a training and testing set of about 20,000 samples and 25 dimensions.

There are only two classes, represented by '0' and '1' in my implementation. For now, I have the following simple implementation:

// testSamples and trainSamples consists of about 20k vectors each with 25 dimensions
// trainClasses contains 0 or 1 signifying the corresponding class for each sample in trainSamples
static int[] TestKnnCase(IList<double[]> trainSamples, IList<double[]> testSamples, IList<int[]> trainClasses, int K)
{
    Console.WriteLine("Performing KNN with K = "+K);

    var testResults = new int[testSamples.Count()]; 

    var testNumber = testSamples.Count();
    var trainNumber = trainSamples.Count();
    // Declaring these here so that I don't have to 'new' them over and over again in the main loop, 
    // just to save some overhead
    var distances = new double[trainNumber][]; 
    for (var i = 0; i < trainNumber; i++)
    {
       distances[i] = new double[2]; // Will store both distance and index in here
    }

    // Performing KNN ...
    for (var tst = 0; tst < testNumber; tst++)
    {
        // For every test sample, calculate distance from every training sample
        Parallel.For(0, trainNumber, trn =>
        {
            var dist = GetDistance(testSamples[tst], trainSamples[trn]);
            // Storing distance as well as index 
            distances[trn][0] = dist;
            distances[trn][1] = trn;
        });

        // Sort distances and take top K (?What happens in case of multiple points at the same distance?)
        var votingDistances = distances.AsParallel().OrderBy(t => t[0]).Take(K);

        // Do a 'majority vote' to classify test sample
        var yea = 0.0;
        var nay = 0.0;

        foreach (var voter in votingDistances)
        {
            if (trainClasses[(int)voter[1]] == 1)  
               yea++;
            else
               nay++;
        }
        if (yea > nay)
            testResults[tst] = 1;
        else
            testResults[tst] = 0;

    }

    return testResults;
}

// Calculates and returns square of Euclidean distance between two vectors
static double GetDistance(IList<double> sample1, IList<double> sample2)
{
    var distance = 0.0;
    // assume sample1 and sample2 are valid i.e. same length 

    for (var i = 0; i < sample1.Count; i++)
    {   
        var temp = sample1[i] - sample2[i];
        distance += temp * temp;
    }
    return distance;
}

This takes quite a bit of time to execute. On my system it takes about 80 seconds to complete. How can I optimize this, while ensuring that it would also scale to larger number of data samples? As you can see, I've tried using PLINQ and parallel for loops, which did help (without these, it was taking about 120 seconds). What else can I do?

I've read about KD-trees being efficient for KNN in general, but every source I read stated that they're not efficient for higher dimensions.

I also found this Stack Overflow discussion about this, but it seems like this is 3 years old, and I was hoping that someone would know about better solutions to this problem by now.

I've looked at machine learning libraries in C#, but for various reasons I don't want to call R or C code from my C# program, and some other libraries I saw were no more efficient than the code I've written. Now I'm just trying to figure out how I could write the most optimized code for this myself.

I cannot reduce the number of dimensions using PCA or something. For this particular model, 25 dimensions are required.

Also, I did track the execution time using a profiler, and it seems that more than 60% of the runtime is spent in the GetDistance() function, which is why I was wondering whether there exists a different algorithm using a different data structure that does this more optimally.

Answer 1

var distances = new double[trainNumber][]; 
for (var i = 0; i < trainNumber; i++)
{
   distances[i] = new double[2]; // Will store both distance and index in here
}

This is a code smell. You shouldn't use a jagged double array to store an array of distances and indexes. Despite the comment, what you're doing is unclear, and it's very confusing to have a variable named distances that stores both distances and indexes. The only justification for this would be if you actually had hard profiling evidence that it caused a significant speedup.

Make a separate class (or struct, if you're worried about overhead) with members double distance; int index; and then trainInfo (the former distances) should just be a trainNumber-sized array of that type.

Also, since you only need the top K elements, you don't need to sort the whole list (n log n time). You ought to be able to do it with a partial sort (actual code sample) which is almost linear-speed. There are also parallel algorithms for this; you could probably get a speedup using PLINQ with a custom aggregate.

On to the next refactoring.

foreach (var voter in votingDistances)
{
    if (trainClasses[(int)voter[1]] == 1)  
       yea++;
    else
       nay++;
}

This code is also crying out for LINQ. How about

yea = votingDistances.AsParallel().Count(voter=>trainClasses[voter.index] == 1);
nay = votingDistances.Count - yea;

And I'd refactor this:

for (var i = 0; i < sample1.Count; i++)
{   
    var temp = sample1[i] - sample2[i];
    distance += temp * temp;
}

to this:

var differences = sample1.AsParallel().Zip(sample2,(s1,s2)=>s1-s2);
distance = differences.Sum(x=>x*x);

though you could get improved performance from a custom aggregate.

Answer 2

You should definitely avoid computing distance from every training sample. That's the main cause of inefficiency. By using proper data structure, the search for nearest neighbours can be done in \$O(log(n))\$. Your code does that in \$O(n)\$, where \$n\$ is the number of samples. Technical improvements might give you 2-times speed-up, but this will give you ~ 1000-times speed-up or more, depending on the number of samples.

Even if KD-trees were inefficient in higher dimension, they would still be much faster that doing a linear scan over the whole set.

The choice of optimal structure depends on operations you want to support. Do you support adding new elements to the set between queries, or is the set fixed at the beginning and you only query it? In any case, I would recommend some spatial-partitioning data structure.