How to reduce execution time for this clustering computation?

Question

Is there any way to reduce total execution time for the function getSilhouetteIndex? P.S. I am using weka SimpleKMeans for getting kmeans and ceval.

private double getSilhouetteIndex(List<ITSPoI> _POIs, SimpleKMeans kmeans, ClusterEvaluation ceval)
{
    double si_index = 0;
    double[] ca = ceval.getClusterAssignments();
    double[] d_arr = new double[ca.length];
    List<Double> si_indexes = new ArrayList<Double>();

    for (int i=0; i<ca.length; i++)
    {
        // STEP 1. Compute the average distance between the i-th PoI and all other points of a given cluster
        double a = averageDist(_POIs,ca,i,1);

        // STEP 2. Compute the average distance between the i-th PoI and all PoIs of other clusters
        for (int j=0; j<ca.length; j++)
        {
            double d = averageDist(_POIs,ca,j,2);
            d_arr[j] = d;
        }

        // STEP 3. Compute the the distance from the i-th PoI to its nearest cluster to which it does not belong
        double b = d_arr[0];
        for (Double _d : d_arr)
        {
            if (_d < b)
                b = _d;
        }

        // STEP 4. Compute the Silhouette index for the i-th PoI
        double si = (b - a)/Math.max(a,b);
        si_indexes.add(si);
    }

    // STEP 5. Compute the average index over all observations
    double sum = 0;
    for(Double _si : si_indexes)
    {
         sum += _si;
    }
    si_index = sum/si_indexes.size();

    return si_index;
}



private double averageDist(List<ITSPoI> _POIs, double[] ca, int id, int calc)
{
    double avgDist = 0;
    List<ITSPoI> clusterPOIs = new ArrayList<ITSPoI>();

    // Distances inside the cluster
    if (calc == 1)
    {
        for (int i = 0; i<ca.length; i++)
        {
            if (ca[i] == ca[id])
                clusterPOIs.add(_POIs.get(i));
        }
    }
    // Distances outside the cluster
    else
    {
        for (int i = 0; i<ca.length; i++)
        {
            if (ca[i] != ca[id])
                clusterPOIs.add(_POIs.get(i));
        }
    }

    double latx, lonx, laty, lony;
    double[] dist = new double[clusterPOIs.size()];
    latx = _POIs.get(id).getLat();
    lonx = _POIs.get(id).getLon();
    for (int i=0; i<clusterPOIs.size(); i++)
    {
        laty = clusterPOIs.get(i).getLat();
        lony = clusterPOIs.get(i).getLon();
        dist[i] = distanceGeo(latx,lonx,laty,lony);
    }

    double sum = 0;
    for(Double d : dist)
    {
         sum += d;
    }
    avgDist = sum/dist.length;

    return avgDist;
}

private double distanceGeo(double lat1, double lon1, double lat2, double lon2)
{
    if (lat1 == lat2 && lon1 == lon2)
    {
        return 0;
    }
    else
    {
        double theta = lon1 - lon2;
        double dist = Math.sin(deg2rad(lat1)) * Math.sin(deg2rad(lat2)) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.cos(deg2rad(theta));
        dist = Math.acos(dist);
        dist = rad2deg(dist);
        dist = dist * 60 * 1.1515;
        dist = dist * 1.609344;
        return dist;
    }
}

Answer 1

There are three methods for computing a great circle distance between two points that are specified by latitude and longitude:

1. You used the spherical law of cosines, which is the most straightforward method based on mathematical principles.
2. The haversine formula yields better accuracy for small distances, though at a greater computational cost.
3. An approximation can be obtained by using the Pythagorean theorem on an equirectangular projection.

For the purposes of clustering, an approximation of the great circle distance might be good enough. I would also declare this function private static final as a very strong hint that it can be inlined — as it should, since it's a pure mathematical function.

private static final double approxDistanceGeo(double lat1, double lon1, double lat2, double lon2)
{
    if (lat1 == lat2 && lon1 == lon2)
    {
        return 0;
    }
    else
    {
        double x = deg2rad(lon1 - lon2) * Math.cos(deg2rad((lat1 + lat2) / 2));
        double y = deg2rad(lat1 - lat2);
        double dist = Math.sqrt(x * x + y * y);
        dist = dist * 60 * 1.1515 * 1.609344;
        return dist;
    }
}

Working directly in radians could save a few deg2rad() conversions.