Алгоритм KNN с оценкой диапазона почти всегда возвращает более K баллов ⇐ C#

[Anonymous]

Я пишу алгоритм обработки пространственных данных с использованием R-дерева для университетского проекта, где перед нами стоит задача написать алгоритм KNN в виде запроса диапазона с использованием оценки диапазона. Мы не были ограничены одним языком программирования, поэтому я выбрал C#.
Я настроил R-дерево, класс Point и основу алгоритма KNN, но не смог выяснить, как реализовать эффективную функцию оценки диапазона, поэтому я поискал в Интернете существующие реализации. Я наткнулся на статью («Эффективные запросы k ближайших соседей в удаленных пространственных базах данных с использованием оценки диапазона»), в которой предлагалось решение на основе плотности, где диапазон оценивается на основе плотности MBB (минимальной ограничивающей рамки) всего набор данных.

Код: Выделить всё

Density = number of points in MBB / area of MBB

Вот часть моего класса, где я реализовал функции, написанные в статье:

Код: Выделить всё

public class KNNRangeQueryRTreeDensity {

... (constructor and pivate fields omitted)

private double GetDensityOfDatasetByGeometry(Geometry geom)
{
int numOfObjs = geom.NumPoints;
Envelope env = geom.EnvelopeInternal;
double area = (env.MaxX - env.MinX) * (env.MaxY - env.MinY);
return numOfObjs / area;
}

public double EstimateRangeWithDensity(int k, Geometry databaseGeometry)
{
return Math.Sqrt(k / (Math.PI * GetDensityOfDatasetByGeometry(databaseGeometry)));
}

public double ExpandRange(int k, Point queryPoint, Envelope prevEnv, int numOfNNRetrieved)
{
double range, envDensity;

if (numOfNNRetrieved == 0)
{
range = 2 * ((prevEnv.MaxX - prevEnv.MinX) / 2);
}
else
{
envDensity = numOfNNRetrieved / ((prevEnv.MaxX - prevEnv.MinX) * (prevEnv.MaxY - prevEnv.MinY));
range = Math.Sqrt(k / (Math.PI * envDensity));
}

return range;
}

public (List, double) KNNQuery(int k, Point queryPoint)
{
double dist;
double range = EstimateRangeWithDensity(k, _pointsGeometry); //perform range estimation
Envelope window = new Envelope(queryPoint.X - range, queryPoint.X + range, queryPoint.Y - range, queryPoint.Y + range); //create a new window (envelope) using the query point and range

IList
 resultsList = _rTree.Query(window).OrderBy(x => x.DistanceTo(queryPoint)).ToList(); //perform window query
List nnList = new List(k); //create list with a capacity of k
int count = 0; //this keeps track of how many points are actually added to nnList
foreach (Point point in resultsList) //perform initial query based on the range estimation above
{
dist = point.DistanceTo(queryPoint);

if (dist  x.DistanceTo(queryPoint)).ToList(); //perform window query
count = 0;
foreach (Point point in resultsList) //perform initial query based on the range estimation above
{
dist = point.DistanceTo(queryPoint);

if (dist  и точку запроса (0.5, 0.6):
[code]ID        X                 Y

1|1,629170883274251|5,007505367979177
2|0,7293811350732022|6,2009057338353735
3|4,087100198532967|8,718630060888188
4|6,081353833936785|0,508181154964576
... (up to point 1024)

Кажется, все работает нормально, однако вместо 12 точек возвращается 13.
Консоль вывод:

Код: Выделить всё

Enter filename with full path: M:\Visual Studio\DPTProj\rangedataset.txt
How many neighbors do you want to retrieve (k = ?)?
Type here: 12

Building R-tree...
R-tree built successfully.

Estimated range for k = 12: 0,8435869948686181

Points within radius 0,8435869948686181 of (0,5, 0,6):
1: (0,6843068314177482, 0,46912474579602703) | Distance to query point: 0,22604720805664638
2: (0,4947431154990304, 0,2580122092077565) | Distance to query point: 0,34202819165328435
3: (0,09012448605621443, 0,4170682841991392) | Distance to query point: 0,4488451287209534
4: (0,8195993866862726, 0,259394385041387) | Distance to query point: 0,46707167855863035
5: (0,28279345495756414, 0,1435370604244699) | Distance to query point: 0,5055067738568947
6: (0,10963706770429252, 0,2626442072273438) | Distance to query point: 0,5159381259683864
7: (0,12078106408975137, 0,17282920897604392) | Distance to query point: 0,5712108945537835
8: (1,0621745516835592, 0,7497310129691526) | Distance to query point: 0,5817728103008762
9: (0,6616472921621275, 1,2313257349800906) | Distance to query point: 0,6516916684379966
10: (1,1860976280579798, 0,6747156943542489) | Distance to query point: 0,6901538887883075
11: (0,06693545266377528, 0,04315583037359446) | Distance to query point: 0,705422094498358
12: (0,7070193349882119, 1,280761478133854) | Distance to query point: 0,7115428273617488
13: (0,19052830067953483, 1,2878140673450258) | Distance to query point: 0,754228694706058

Returned 13 points - range query executed with one or more errors

(Строка «с одной или несколькими ошибками» выше отображается всякий раз, когда количество возвращаемых точек отличается от k.)
Это также происходит при различных значениях k (например, k = 128), где возвращается 147 точек.
Пока я запускал это через отладчик, кажется, что в цикл foreach внутри цикла while, причем последний выполняется, если первый запрос диапазона возвращает менее k точек. Поэтому по мере расширения диапазона в список результатов добавляется больше точек, что нежелательно:

Код: Выделить всё

while (count < k)
{
range = ExpandRange(k, queryPoint, window, count); //expand range
window = new Envelope(queryPoint.X - range, queryPoint.X + range, queryPoint.Y - range, queryPoint.Y + range);

//repeat above code block
resultsList = _rTree.Query(window).OrderBy(x => x.DistanceTo(queryPoint)).ToList(); //perform window query
count = 0;
foreach (Point point in resultsList) //

Подробнее здесь: [url]https://stackoverflow.com/questions/79351264/knn-algorithm-with-range-estimation-almost-always-returns-more-than-k-points[/url]