Estou implementando o algoritmo de classificação K-vizinhos mais próximos em C # para um conjunto de treinamento e teste de cerca de 20.000 amostras cada e 25 dimensões.

Existem apenas duas classes, representadas por '0' e '1' na minha implementação. Por enquanto, tenho a seguinte implementação simples:

// 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;
}

Isso leva bastante tempo para ser executado. No meu sistema, leva cerca de 80 segundos para ser concluído. Como posso otimizar isso, garantindo que ele também seja dimensionado para um número maior de amostras de dados? Como você pode ver, tentei usar o PLINQ e o paralelo para loops, o que ajudou (sem eles, levava cerca de 120 segundos). O que mais eu posso fazer?

Eu li sobre as árvores KD serem eficientes para o KNN em geral, mas todas as fontes que li afirmaram que elas não são eficientes para dimensões mais altas.

Eu também encontreiesta discussão stackoverflow sobre isso, mas parece que isso tem 3 anos e eu esperava que alguém soubesse sobre melhores soluções para esse problema agora.

Examinei as bibliotecas de aprendizado de máquina em C #, mas por várias razões, não quero chamar código R ou C do meu programa em C #, e algumas outras bibliotecas que vi não eram mais eficientes do que o código que escrevi. Agora estou apenas tentando descobrir como eu poderia escrever o código mais otimizado para isso.

Editado para adicionar - não posso reduzir o número de dimensões usando o PCA ou algo assim. Para este modelo específico, são necessárias 25 dimensões.