c# - 如何在 C# 中针对大量维度最好地实现 K 最近邻？

Question

我正在用 C# 实现 K 近邻分类算法，用于训练和测试集，每个样本大约有 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 和并行 for 循环，这确实有帮助(没有这些，大约需要 120 秒)。我还能做什么？

我读过关于 KD 树一般对 KNN 有效的信息，但我读到的每一个来源都表明它们对更高维度的效率不高。

我还找到了this stackoverflow discussion关于这个，但这似乎是 3 年前的事了，我希望现在有人知道这个问题的更好解决方案。

我看过 C# 中的机器学习库，但出于各种原因，我不想从我的 C# 程序中调用 R 或 C 代码，而且我看到的其他一些库并不比我的代码更有效书面。现在我只是想弄清楚如何自己编写最优化的代码。

编辑添加 - 我无法使用 PCA 或其他方法减少维数。对于这个特定模型，需要 25 个维度。

Answer 1

每当您尝试提高代码的性能时，第一步就是分析当前性能，以准确了解它把时间花在哪里了。一个好的分析器对此至关重要。在我以前的工作中，我能够使用 dotTrace profiler效果好； Visual Studio 也有一个 built-in profiler .一个好的分析器会逐个方法甚至逐行准确地告诉您代码在哪里花费时间。

话虽这么说，但在阅读您的实现时，我会想到一些事情:

1. 您正在并行处理一些内部循环。你能并行化外循环吗？委托(delegate)调用(请参阅 here 或 here)有一个小但非零的成本，这可能会在“Parallel.For”回调中打击您。

2. 同样，使用数组的 IList 接口(interface)对数组进行索引时，性能也会有所下降。您可能会考虑将数组参数显式声明为“GetDistance()”。

3. 与训练数组的大小相比，K 有多大？您正在对“距离”数组进行完全排序并取前 K，但如果 K 远小于数组大小，则使用 partial sort 可能有意义/selection算法，例如使用 SortedSet并在集合大小超过K时替换最小的元素。