Как лучше всего реализовать 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 размеров.