开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜