Как лучше всего реализовать K-ближайших соседей в C # для большого количества измерений?

Я реализую алгоритм классификации K-ближайших соседей в C # для обучающего и тестового набора из примерно 20 000 выборок каждый и 25 измерений.

В моей реализации есть только два класса, представленных как «0» и «1». На данный момент у меня есть следующая простая реализация:

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

Это займет совсем немного времени, чтобы выполнить. В моей системе это занимает около 80 секунд. Как я могу оптимизировать это, гарантируя, что оно также будет масштабироваться до большего количества выборок данных? Как вы можете видеть, я пытался использовать PLINQ и параллель для циклов, что помогло (без них это заняло около 120 секунд). Что еще я могу сделать?

Я читал о том, что KD-деревья эффективны для KNN в целом, но в каждом прочитанном мною источнике указано, что они не эффективны для более высоких измерений.

Я также нашелэто обсуждение потока об этом, но кажется, что этому уже 3 года, и я надеялся, что кто-то уже знает о лучших решениях этой проблемы.

Я смотрел на библиотеки машинного обучения в C #, но по разным причинам я не хочу вызывать код R или C из моей программы на C #, и некоторые другие библиотеки, которые я видел, были не более эффективны, чем код, который я написал. Сейчас я просто пытаюсь понять, как я мог бы написать наиболее оптимизированный код для этого сам.

Отредактировано, чтобы добавить - я не могу уменьшить количество измерений, используя PCA или что-то еще. Для этой конкретной модели требуется 25 размеров.

Ответы на вопрос(1)

Ваш ответ на вопрос