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

• Simon Forsberg: I might be stupid but what does this method? What is a ITSPoI, what is SimpleKMeans and what is ClusterEvaluation. To me, you haven't provided much context on this question.

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.

• Klausos Klausos: private static double deg2rad(double deg) { return (deg * Math.PI / 180.0); }