Ich implementiere den Klassifizierungsalgorithmus für K-nächste Nachbarn in C # für einen Trainings- und Testsatz von jeweils etwa 20.000 Stichproben und 25 Dimensionen.

In meiner Implementierung gibt es nur zwei Klassen, die durch '0' und '1' dargestellt werden. Im Moment habe ich die folgende einfache Implementierung:

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

Die Ausführung nimmt einige Zeit in Anspruch. Auf meinem System dauert es ungefähr 80 Sekunden, um fertig zu sein. Wie kann ich dies optimieren und gleichzeitig sicherstellen, dass es auch auf eine größere Anzahl von Datenproben skaliert wird? Wie Sie sehen, habe ich versucht, PLINQ und parallel for-Schleifen zu verwenden, was geholfen hat (ohne diese hat es ungefähr 120 Sekunden gedauert). Was kann ich sonst noch tun?

Ich habe gelesen, dass KD-Bäume für KNN im Allgemeinen effizient sind, aber jede Quelle, die ich las, gab an, dass sie für höhere Dimensionen nicht effizient sind.

Habe ich auch gefundendiese Stapelüberlauf Diskussion Aber es sieht so aus, als wäre es drei Jahre alt und ich hatte gehofft, dass jemand inzwischen bessere Lösungen für dieses Problem finden würde.

Ich habe mir Bibliotheken für maschinelles Lernen in C # angesehen, möchte aber aus verschiedenen Gründen keinen R- oder C-Code aus meinem C # -Programm aufrufen, und einige andere Bibliotheken waren nicht effizienter als der von mir geschriebene Code. Jetzt versuche ich nur herauszufinden, wie ich den für diesen Zweck am besten optimierten Code selbst schreiben kann.

Zum Hinzufügen bearbeitet - Ich kann die Anzahl der Dimensionen nicht mit PCA oder Ähnlichem reduzieren. Für dieses spezielle Modell sind 25 Abmessungen erforderlich.