1

再帰的な深さ優先の方法で最近傍を見つけようとしています。この点に到達する前に多くの要素が関係していますが、簡単にするために、現在問題が発生しているセクションのみを含めました。

私の考えは、あるしきい値距離に基づいて特定のポイントに最も近いものを見つけることです。プロセスを 2 つの方法に分けることにしました。最近隣が存在するかどうかを実際に確認する方法と、その関数を再帰的に何度も呼び出す方法です。

ポイントとして扱う double 値を持つ ArrayList があります... 0.0 を返す場合は、最も近い隣人を見つけられなかったことを意味します (実際にオブジェクトを使用しているかどうか疑問に思っている場合は、ロジックをクリーンアップすると実行される可能性があります)。

/**
 * 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;
    }
}

そして、これが私の方法で、上記を再帰的な dfs の方法で呼び出すことを計画していました。

/**
 * 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));
    }
}

私が苦労しているのは、再帰的な深さ優先検索です。それに加えて、ビジターの実装が正しくないようです。

これが私が訪問者を処理しようとした方法です

public class VisitedPoint {

    public double point;
    public boolean visited;

    public VisitedPoint(double pointToCheck) {
        point = pointToCheck;
        visited = false;
    }
}

次に VisitedPoint オブジェクトを作成しますprivate VisitedPoint[] isVisited;が、それを isBelongTo() メソッドで使用すると、null ポインター例外が発生します。

助けてくれてありがとう。

4

2 に答える 2

1

これを必要以上に複雑にしているように感じます。

私が物事を正しく理解していれば、あなたは一連の1次元の点データを持っています。これらのポイントをグループに分類しようとしています。グループ内では、ポイントの任意のペア間の距離が「しきい値距離」よりも小さくなっています。

まず、1次元のポイントデータを並べ替えます。最初の要素から始めて、その要素のクラスターオブジェクトを作成します。最初の要素と2番目の要素の間のデルタがしきい値よりも小さい場合は、それをクラスターに追加します。次に、2番目と3番目の間のデルタを調べます。並べ替えられたデータに沿って進み、データの最後に到達するまで、しきい値よりも大きいデルタを見つけたときに分類するための新しいクラスターを作成します。

それで問題は解決しましたか、それとも重要な要件を見逃しましたか？

于 2009-11-04T18:27:46.233 に答える
1

Nearest Neighbor を解くための Best Performance-Critical Algorithm を見てください。お役に立てば幸いです。

于 2009-11-04T23:00:42.260 に答える