реализация графа k ближайших соседей в Java

Я реализую алгоритм кластеризации Flame как способ узнать немного больше о графах и обходе графов, и одним из первых шагов является построение графа K-ближайших соседей, и мне интересно, какой самый быстрый способ будет запускать через список узлов и соединяя каждый из них только для того, чтобы сказать, что это ближайшие пять соседей. Моя мысль заключалась в том, что я начну с узла, пройдусь по списку других узлов и оставлю самые близкие в массиве, следя за тем, чтобы все, что находится за верхним n, было отброшено. Теперь я мог бы сделать это, просто отсортировав список и сохранив первые n записей, но я бы предпочел хранить меньше вещей в памяти, и поэтому мне было интересно, есть ли способ просто получить окончательный массив и обновить этот массив как Я перебираю, или если есть более эффективный способ создания графика k ближайших соседей.

Также обратите внимание, что это НЕ дубликат реализации K-ближайшего соседа в Java. KNNG отличается от KNN.


java graph nearest-neighbor
person Slater Victoroff    schedule 06.08.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Поместите первые n узлов, отсортированных в список. Затем выполните итерацию по остальным узлам и, если он подходит к текущему списку (т.е. является верхним n узлом), поместите его в соответствующую позицию в списке и отбросьте последний верхний n узел. Если он не подходит к первому списку, выбросьте его.

for each neighborNode
 for(int i = 0; i < topNList.size(); i++){
       if((dist = distanceMetric(neighborNode,currentNode)) > topNList.get(i).distance){
             topNList.remove(topNList.size()-1)
             neighborNode.setDistance(dist);
             topNList.add(i, neighborNode);
       }
person Razvan    schedule 06.08.2012
comment
Мне нравится этот ответ, но мне интересно, насколько плоха стоимость повторения соседей на каждой итерации. Если нет ничего другого, я соглашусь с этим, но я считаю, что это снизит эффективность в n раз (количество соседей), что сделает его более похожим на O (nm ^ 2), что не идеально. Я бы предпочел что-то ниже O(m^2), но опять же, я не могу сказать, что это не решает проблему. - person Slater Victoroff; 06.08.2012
comment
Теперь я понял. Вы хотите вычислить knn для каждого узла в графе. - person Razvan; 06.08.2012

arrow_upward
1
arrow_downward

Я думаю, что наиболее эффективным способом было бы использование очереди с привязанным приоритетом, например https://github.com/tdebatty/java-graphs#bounded-priority-queue

person Thibault Debatty    schedule 09.04.2015