7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ Thanks @Snowbody! These are helpful suggestions. I am a beginner to C#, but I was under the impression that using a jagged array there instead of a class would reduce overhead, am I wrong? Also, would LINQ optimize the code, or is it a matter of good programming practice? \$\endgroup\$ – ubuntunoob Jul 7 '14 at 18:28
  • \$\begingroup\$ LINQ is not really about increasing the speed; it's about beign able to develop more quickly and with less errors, and also produce code that is easier to understand and thus more maintainable. In some instances, you can get a speedup, for instance, parallelizing the difference one I mentioned (I didn't go far enough, you should be using a custom aggregate a la msdn.microsoft.com/en-us/library/dd460697(v=vs.110).aspx ) \$\endgroup\$ – Snowbody Jul 7 '14 at 21:35
  • \$\begingroup\$ An array of arrays is probably less overhead than an array of classes; an array of structs is probably the same. You really need to test it to be sure. Don't prematurely optimize. \$\endgroup\$ – Snowbody Jul 7 '14 at 21:36
  • \$\begingroup\$ Please, please look at the MSDN link I posted -- it shows how to use .AsParallel().Aggregate() to get a big speedup. It calculates standard deviation which is almost the same as distance squared. \$\endgroup\$ – Snowbody Jul 7 '14 at 21:45
  • \$\begingroup\$ Accepting this one as the answer since I haven't found any other solutions that are more efficient. Thanks @Snowbody! Stating for the record - I tried a KD-tree implementation with no significant speedup (presumably due to the large no. of dimensions), and although I came across a bunch of other data structures that may perform high-dimensional KNN efficiently, this actually seems to be an open research problem as of now, so I will leave it at this. \$\endgroup\$ – ubuntunoob Jul 17 '14 at 19:24
6
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.