Weka DBSCAN набор эпсилон на основе географических данных

Question

у меня есть набор географических данных в формате:

46.52100798 6.567126449 gps 
46.52368591 6.59208188 gps 
46.52338534 6.593065244 gps 
46.52303304 6.594046262 gps 

Я хочу сделать DBSCAN кластеризацию и установите параметр эпсилон, который идентичен реальному расстоянию, как 5 метров: В настоящее время код выглядит следующим образом:

public static float distFrom(double lat1, double lng1, double lat2, double lng2) { 
    double earthRadius = 6371000; //meters 
    double dLat = Math.toRadians(lat2-lat1); 
    double dLng = Math.toRadians(lng2-lng1); 
    double a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
      Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * 
        Math.sin(dLng/2) * Math.sin(dLng/2); 
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
    float dist = (float) (earthRadius * c); 
    return dist; 
} 

// метод расчета расстояния с учетом двух пар географических данных.

cl = new DBSCAN(); 
    double [] timeArray = new double[data.numInstances()-1]; 

    for (int i = 1; i<data.numInstances();i++){ 
     timeArray[i-1] =(data.instance(i).value(0)-data.instance(i-1).value(0)); 
    } 
    Arrays.sort(timeArray); 
    int point =(int)(30*60/timeArray[data.numInstances()/2]); 
    System.out.println(point); 
    cl.setMinPoints(point); 
    cl.setEpsilon(0.01); 
    cl.buildClusterer(newData); 

// установить параметры для DBSCAN экземпляра кто знает, как подключить вышеупомянутую часть расстояния вычисления кода в DBSCAN инстанции?

Answer 1

ELKI уже включает эту функцию расстояния LatLngDistanceFunction (будьте уверены, что порядок широты и долготы имеет значение, поэтому мы предоставляем оба варианта в зависимости от вашего порядка столбцов).

-algorithm.distancefunction geo.LatLngDistanceFunction 

Расстояния с помощью этой функции расстояния будет метров. С параметром -geo.model вы также можете переключаться между различными приближениями Земли, такими как простые сферические модели, или сфероидом WGS84. Для DBSCAN это не имеет большого значения, потому что вы захотите использовать небольшой эпсилон (например, 5 метров, который вы предложили) в любом случае.

ELKI также включает в себя индексирование возможности для этой функции расстояния. Когда у вас будут большие наборы данных, ELKI будет намного быстрее (и я приглашаю вас на контрольный номер Weka против ELKI самостоятельно). Подробности о индекса для ускорения гео расстояния можно найти в издании:

Е. Шуберта, А. Zimek, Х.-П. Кригель
Geodetic Distance Queries on R-Trees for Indexing Geographic Data
Трудов 13-го Международного симпозиума по пространственным и временным базам данных (SSTD), Мюнхен, Германия: 146-164, 2013.

Пока вы выбираете эпсилон достаточно малы, и использование реальные данные, R * -tree обычно дает вам ускорение от O (n^2) до ок. O (n log n) - если у вас есть миллионы очков, ускорение часто составляет 100x-1000x.