How to reduce execution time for this clustering computation?
There are three methods for computing a great circle distance between two points that are specified by latitude and longitude:


You used the spherical law of cosines, which is the most straightforward method based on mathematical principles.
The haversine formula yields better accuracy for small distances, though at a greater computational cost.
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 &amp;&amp; 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.