# How to reduce execution time for this clustering computation?

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

// 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])
}
}
// Distances outside the cluster
else
{
for (int i = 0; i<ca.length; i++)
{
if (ca[i] != ca[id])
}
}

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;
dist = Math.acos(dist);
dist = dist * 60 * 1.1515;
dist = dist * 1.609344;
return dist;
}
}

• 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. – Simon Forsberg Jan 13 '14 at 18:49

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.

• private static double deg2rad(double deg) { return (deg * Math.PI / 180.0); } – Klausos Klausos Jan 13 '14 at 12:59