k最近鄰居關係圖在Java中的實現

我正在實現一個火焰聚類算法作爲一種學習圖形和圖遍歷的方式，並且其中一個步驟是構造一個K-最近鄰居圖，他想知道最快的方式是通過一系列節點並連接每一個節點來說，它最接近五個鄰居。我的想法是，我會從一個節點開始，遍歷其他節點的列表，並保留數組中最接近的節點，確保放棄排在前n的所有東西。現在，我可以通過對列表進行排序並保留前n個條目來做到這一點，但是我更願意在內存中保留更少的東西，所以我想知道是否有辦法讓最終數組和更新數組爲我迭代，或者如果有更有效的方法來生成k最近鄰圖。k最近鄰居關係圖在Java中的實現

此外，請注意，這不是K-Nearest Neighbour Implementation in Java的重複。 KNNG與KNN不同。

來源

2012-08-06 Slater Victoroff

放置前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-06 14:47:28 Razvan

我喜歡這個答案，但我不知道在每次迭代通過鄰居迭代的成本是多麼糟糕。如果沒有別的東西我會接受，但我相信這會使效率降低n倍（鄰居數量），使其更像O（nm^2），這是不理想的。我更喜歡O（m^2）以下的東西，但是我不能說這不能解決問題。 – 2012-08-06 15:00:31

現在我明白了。你想計算圖中每個節點的knn。 – Razvan 2012-08-06 15:44:33

我認爲最有效的方法是使用綁定的優先級隊列，像 https://github.com/tdebatty/java-graphs#bounded-priority-queue

來源

2015-04-09 19:43:08

k最近鄰居關係圖在Java中的實現

回答

相關問題