Среднее расстояние между точками в кластере - PullRequest
Новая
       19

Среднее расстояние между точками в кластере

1 голос
/ 01 ноября 2009

Звучит так, как будто я понял концепцию, но, похоже, не могу понять правильность реализации. e У меня есть кластер (ArrayList) с несколькими точками, и я хочу рассчитать среднее расстояние. Пример: точки в группе (A, B, C, D, E, F, ..., n), расстояние AB, расстояние AC, расстояние AD, ... расстояние A, N, расстояние (B, C) расстояние ( B, D) ... Расстояние (B, N) ...

Заранее спасибо.

Ответы [ 2 ]

2 голосов
/ 01 ноября 2009

Вы не хотите дважды считать любой сегмент, поэтому ваш алгоритм должен быть двойным для цикла. Внешний цикл переходит от A к M (вам не нужно проверять N, потому что для него ничего не останется подключиться), каждый раз переходя от curPoint к N, вычисляя каждое расстояние. Вы добавляете все расстояния и делите их на количество точек (n-1) ^ 2/2. Должно быть довольно просто.

Не существует каких-либо стандартных алгоритмов для улучшения этого, о которых я знаю, и это не является широко изученной проблемой. Я предполагаю, что вы могли бы получить довольно разумную оценку (если оценка полезна) путем выборки расстояний от каждой точки до нескольких других. Но это предположение.

(После просмотра вашего кода) Вот еще одна попытка: 

public double avgDistanceInCluster() { 
    double totDistance = 0.0; 
    for (int i = 0; i < bigCluster.length - 1; i++) { 
        for (int j = i+1; j < bigCluster.length; j++) { 
            totDistance += distance(bigCluster[i], bigCluster[j]);
        }
    }
    return totDistance / (bigCluster.length * (bigCluster.length - 1)) / 2; 
}

Обратите внимание, что предел для первого цикла отличается. Расстояние между двумя точками, вероятно, sqrt((x1 - x2)^2 + (y1 -y2)^2).

0 голосов
/ 02 ноября 2009

СПАСИБО за всю помощь, Иногда после объяснения вопроса на форуме ответ просто всплывает на ум. Это то, что я в итоге делаю.

У меня есть кластер точек, и мне нужно рассчитать среднее расстояние между точками (парами) в кластере. Итак, это то, что я сделал. Я уверен, что кто-то придет с лучшим ответом, если так, пожалуйста, оставьте записку. Заранее спасибо. 

/**
 * Calculate avg distance between points in cluster
 * @return
 */
public double avgDistanceInCluster() {
    double avgDistance = 0.0;
    Stack<Double> holder = new Stack<Double>();
    for (int i = 0; i < cluster.size(); i++) {
        System.out.println(cluster.get(i));
        for (int j = i+1; j < cluster.size(); j++) {
            avgDistance = (cluster.get(i) + cluster.get(j))/2; 
            holder.push(avgDistance);
        }
    }
    Iterator<Double> iter = holder.iterator();
    double avgClusterDist = 0;
    while (iter.hasNext()) {
        avgClusterDist =+ holder.pop();
        System.out.println(avgClusterDist);
    }
    return avgClusterDist/cluster.size();
}
...