3

我正在实施一个火焰聚类算法，作为学习更多关于图和图遍历的一种方式，第一步是构建一个 K-最近邻图，我想知道最快的运行方式是什么通过节点列表并连接每个节点只说它是最近的五个邻居。我的想法是，我将从一个节点开始，遍历其他节点的列表，并将最接近的节点保留在一个数组中，确保丢弃前 n 之后的所有内容。现在，我可以通过对列表进行排序并保留前 n 个条目来做到这一点，但我宁愿在内存中保留更少的东西，所以我想知道是否有办法只拥有最终数组并将该数组更新为我遍历，

另外，请注意，这不是Java 中 K-Nearest Neighbor Implementation的副本。KNNG 与 KNN 不同。

4

2 回答 2

1

放置前 n 个节点，按列表排序。然后遍历其余节点，如果它适合当前列表（即是前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);
       }
于 2012-08-06T14:47:28.683 回答
1

我认为最有效的方法是使用绑定优先级队列，例如 https://github.com/tdebatty/java-graphs#bounded-priority-queue

于 2015-04-09T19:43:08.743 回答