Java中的k最近邻图实现

Question

Java中的k最近邻图实现

3

我正在实现一个Flame聚类算法来学习一些关于图和图遍历的知识，其中的第一步是构建一个K近邻图。我想知道连接每个节点到它的最近的五个邻居节点的最快方法是什么。我的想法是从一个节点开始，迭代遍历其他节点的列表，并保留距离最近的节点到一个数组中，确保顶部n个以外的所有节点都被丢弃。现在，我可以通过对列表进行排序并保留前n个条目来完成此操作，但我更愿意在内存中保存更少的东西，因此我想知道是否有一种方法可以只保留最终的数组，并在迭代遍历时更新该数组，或者是否有一种更有效的生成K近邻图的方法。

另外请注意，这不是Java中K最近邻实现的重复。K最近邻图(KNNG)与KNN不同。

- Slater Victoroff

2个回答

1

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

- Thibault Debatty

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Razvan · Accepted Answer

将前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);
       }