find nearest neighbor in recursive dfs fashion
I am trying to find the nearest neighbor in recursive depth-first-fashion. There are many elements involve prior to getting to this point, to keep it simple I have only included the section that I am currently having trouble.
My idea is to find nearest neighbor to a given point based on some threshold distance, I decided to separate the process int to two methods. One to really find if the nearest neighbor exists and other method to just call that function over and over recursively.
I have ArrayList with double values that I treat as points... if return 0.0, means I did't find the nearest neighbor (Wondering if I really use Object, might do it once I cleanup the logic).
/**
* Find the nearest neighbor based on the distance threshold.
* TODO:
* @param currentPoint current point in the memory.
* @param threshold dynamic distance threshold.
* @return return the neighbor.
*/
private double nearestNeighbor(double currentPoint) {
HashMap<Double, Double> unsorted = new HashMap<Double, Double>();
TreeMap<Double, Double> sorted = null;
double foundNeighbor = 0.0;
for (int i = 0; i < bigCluster.length; i++) {
if (bigCluster[i] != 0.0 && bigCluster[i] != currentPoint) {
double shortestDistance = Math.abs(currentPoint - bigCluster[i]);
if (shortestDistance <= this.getDistanceThreshold())
unsorted.put(shortestDistance, bigCluster[i]);
}
}
if (!unsorted.isEmpty()) {
sorted = new TreeMap<Double, Double>(开发者_如何转开发unsorted);
this.setDistanceThreshold(avgDistanceInCluster());
foundNeighbor = sorted.firstEntry().getValue();
return foundNeighbor;
} else {
return 0.0;
}
}
And here is my method, that I planned on calling the above in a recursive dfs fashion.
/**
* Method will check if a point belongs to a cluster based on the dynamic
* threshold.
*/
public void isBelongToCluster(double point) {
for (int i = 0; i < tempList.size(); i++) {
double aPointInCluster = point;
cluster.add(aPointInCluster);
isVisited[i].visited = true;
double newNeighbor = nearestNeighbor(aPointInCluster);
if (newNeighbor != 0.0) {
cluster.add(newNeighbor);
if (i + 1 != tempList.size() && (isVisited[i].visited != true)) {
isBelongToCluster(newNeighbor);
}
}
}
for (int i = 0; i < cluster.size(); i++) {
if (cluster.get(i) != 0.0)
System.out.println("whats in the cluster -> " + cluster.get(i));
}
}
What I am struggling is with the recursive depth first search. In Addition to that my visitor implementation doesn't look right.
This is how I tried to handle the visitor
public class VisitedPoint {
public double point;
public boolean visited;
public VisitedPoint(double pointToCheck) {
point = pointToCheck;
visited = false;
}
}
then I would create a VisitedPoint object, private VisitedPoint[] isVisited;
but when I used it in my isBelongTo() method I get a null pointer exception.
Thanks in advance for any help.
It feels like you are making this more complex that it needs to be.
If I understand things correctly, you have a series of 1 dimensional point data. You are trying to classify these points into groups, where within a group, the distance between any pair of points is less than the 'threshold distance'.
I would start by sorting the 1 dimensional point data. Starting at the first element, I create a cluster object for that element. If the delta between the first element and the second element is smaller than the threshold I add it to the cluster. Now I look at the delta between the second and the third; advancing along the sorted data, and creating a new cluster to classify things into when I find a delta that is larger than the threshold, until I am at the end of the data.
Does that solve the problem or did I miss a key requirement?
Look at Best Performance-Critical Algorithm for Solving Nearest Neighbor. I hope it helps.
精彩评论