Thursday, November 12, 2026

K-Means Clustering for Spatial Analysis: Coordinates, Distances, and Python Code

TL;DR

K-means on raw latitude and longitude can give neat clusters that are simply wrong, because a degree of longitude shrinks as you move away from the equator. This guide shows why, then fixes it two ways: project to meters first, or use DBSCAN with haversine distance. Delivery vans, it turns out, prefer clusters built in meters, not degrees.

The quickest route through it:

Say a delivery company in Oslo wants to split 600 addresses into two routes, one per van. An analyst loads the latitude and longitude columns, runs k-means with two clusters, and gets two neat groups on the map. The problem is that they are the wrong groups: each van ends up crossing between two roads 3 km apart all day, while the obvious split, one road per van, is ignored.

Nothing is wrong with k-means here. The problem is the input. K-means clustering for spatial analysis works well, but only when the distances it sees match real distances on the ground, and raw latitude and longitude do not. One degree of longitude near Oslo is about half as long as one degree of latitude. The fix is to project the coordinates into meters before clustering, or to switch to a method that measures distance on the sphere, such as DBSCAN with the haversine metric. This guide shows both, with runnable scikit-learn code and real output.

Key Takeaways

  • K-means groups points by minimizing squared Euclidean distance to cluster centers. It has no idea that the inputs are angles on a sphere.
  • A degree of latitude is about 111 km everywhere, but a degree of longitude shrinks with the cosine of latitude: about 56 km at 60 degrees north. Raw degrees stretch east to west distances relative to north to south.
  • For city or regional data, project coordinates to a metric system such as UTM with pyproj, then run k-means on meters.
  • For data spread across large areas, or when you want clusters defined by a distance like “within 500 m”, use DBSCAN with metric="haversine" on coordinates in radians.
  • In our test, k-means on raw degrees matched the true groups no better than chance (adjusted Rand index 0.00). On projected coordinates it scored 0.98.

What Is K-Means Clustering?

K-means clustering is an unsupervised algorithm that splits data into k groups so that each point belongs to the group with the nearest center (centroid). It starts with k initial centers, assigns every point to its closest center, moves each center to the mean of its points, and repeats until the assignments stop changing.

Two details matter for spatial data. First, “closest” means straight-line Euclidean distance in whatever units the columns are in. Second, k-means minimizes the sum of squared distances, so a direction that looks longer in the input units has more influence on where the clusters split. scikit-learn’s KMeans only supports Euclidean distance, so getting the units right is your job.

Why Latitude and Longitude Distort Distances

Latitude and longitude are angles, not distances. Lines of latitude are evenly spaced, so one degree north is about 111 km anywhere on Earth. Lines of longitude meet at the poles, so the ground distance of one degree east shrinks with latitude:

Place Latitude 1 degree of longitude
Quito 0 degrees about 111 km
New York about 41 N about 84 km
Oslo about 60 N about 56 km

The values follow from 111 km multiplied by the cosine of the latitude. In Oslo, two points 1 km apart east to west differ by about 0.018 degrees of longitude, while two points 1 km apart north to south differ by only 0.009 degrees of latitude. To k-means, which works on the raw numbers, the east to west gap looks twice as big.

There is a second problem at the 180th meridian. Points at longitude 179.9 and -179.9 are about 22 km apart at the equator, but k-means sees a gap of 359.8 degrees. And a centroid computed as the mean of raw coordinates can land in the wrong place for data that wraps around the globe.

A Runnable Example With Generated Coordinates

The script below generates two groups of delivery addresses near Oslo. Each group runs east to west along a main road (spread of 1.2 km east to west, 0.6 km north to south), and the two roads are 3 km apart. It then clusters the points three ways and compares each result with the true groups using the adjusted Rand index, where 1.0 means a perfect match and 0 means no better than chance.

import numpy as np
from pyproj import Transformer
from sklearn.cluster import DBSCAN, KMeans
from sklearn.metrics import adjusted_rand_score

rng = np.random.default_rng(42)

# Two groups of delivery addresses near Oslo (about 59.9 N), each stretched
# east to west along a main road, with 3 km between the two roads.
# Offsets are in km: x = east, y = north.
n = 300
south = np.column_stack([rng.normal(0, 1.2, n), rng.normal(0, 0.6, n)])
north = np.column_stack([rng.normal(0, 1.2, n), rng.normal(3, 0.6, n)])
xy_km = np.vstack([south, north])
truth = np.repeat([0, 1], n)

# Convert the km offsets to latitude and longitude.
lat0, lon0 = 59.91, 10.75
km_per_deg_lat = 111.2
km_per_deg_lon = 111.2 * np.cos(np.radians(lat0))
lat = lat0 + xy_km[:, 1] / km_per_deg_lat
lon = lon0 + xy_km[:, 0] / km_per_deg_lon
print(f"1 degree of latitude  = {km_per_deg_lat:.1f} km")
print(f"1 degree of longitude = {km_per_deg_lon:.1f} km at {lat0} N")

# 1. Plain k-means on raw (lat, lon) degrees
raw = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(np.column_stack([lat, lon]))

# 2. k-means on projected coordinates in meters (UTM zone 32N covers Oslo)
to_utm = Transformer.from_crs("EPSG:4326", "EPSG:32632", always_xy=True)
easting, northing = to_utm.transform(lon, lat)
projected = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(
    np.column_stack([easting, northing])
)

print(f"Agreement with the true groups (adjusted Rand index, 1.0 = perfect)")
print(f"  k-means on raw degrees:     {adjusted_rand_score(truth, raw):.2f}")
print(f"  k-means on UTM meters:      {adjusted_rand_score(truth, projected):.2f}")

# 3. DBSCAN with haversine distance: no projection, no k to choose
earth_radius_km = 6371.0
eps_km = 0.5
db = DBSCAN(eps=eps_km / earth_radius_km, min_samples=10, metric="haversine",
            algorithm="ball_tree")
labels = db.fit_predict(np.radians(np.column_stack([lat, lon])))
clustered = labels != -1
print(f"  DBSCAN (haversine, 0.5 km): {adjusted_rand_score(truth[clustered], labels[clustered]):.2f}"
      f" on {clustered.sum()} points, {len(set(labels) - {-1})} clusters, "
      f"{(~clustered).sum()} marked as noise")

Output (scikit-learn 1.9, pyproj 3.8):

1 degree of latitude  = 111.2 km
1 degree of longitude = 55.8 km at 59.91 N
Agreement with the true groups (adjusted Rand index, 1.0 = perfect)
  k-means on raw degrees:     -0.00
  k-means on UTM meters:      0.98
  DBSCAN (haversine, 0.5 km): 0.99 on 561 points, 2 clusters, 39 marked as noise

On raw degrees, k-means scored 0.00 (the minus sign is rounding). It split the points into an east half and a west half, cutting across both roads, because in degrees the east to west spread looks larger than the 3 km gap between the roads. After projecting to UTM meters, the same algorithm with the same settings found the two roads almost perfectly. Nothing changed but the units.

Fix 1: Project Coordinates Before Running K-Means

A map projection converts latitude and longitude into flat x and y coordinates in meters. For data inside one city or region, a Universal Transverse Mercator (UTM) zone is a good default: each zone covers 6 degrees of longitude and keeps distances accurate within the zone. Oslo sits in zone 32N, which is EPSG code 32632. pyproj, the Python interface to the PROJ library, does the conversion:

from pyproj import Transformer

to_utm = Transformer.from_crs("EPSG:4326", "EPSG:32632", always_xy=True)
easting, northing = to_utm.transform(lon, lat)  # always_xy: longitude first

Watch the axis order. With always_xy=True, pyproj takes longitude first and latitude second, the opposite of how most people write coordinates. Swapping them is one of the most common bugs in spatial code.

Projection keeps all of k-means’ strengths: it is fast, it scales to millions of points, and you choose the number of groups, which is what you want when the count is fixed by the problem (two vans, five sales regions, ten warehouses). If your data spans several UTM zones, pick a projection made for the whole region, or use the next fix.

Fix 2: DBSCAN With Haversine Distance

The haversine formula gives the great-circle distance between two points on a sphere, the shortest path along the surface. scikit-learn’s DBSCAN accepts metric="haversine", which works on raw coordinates and needs no projection. Three rules apply:

  1. Use radians, latitude first. Pass np.radians(np.column_stack([lat, lon])).
  2. Express eps in radians too. Divide the distance you want by the Earth’s radius: 0.5 km / 6,371 km.
  3. Use the ball tree. algorithm="ball_tree" supports haversine and keeps neighbor searches fast.

DBSCAN is a density-based method: a point belongs to a cluster if enough other points are within eps of it, and points that fit nowhere are labeled -1 as noise. In the example it found both roads (adjusted Rand index 0.99 on the clustered points) and flagged 39 scattered addresses as noise. You do not choose the number of clusters. You choose what “close” means in meters, which is often the more natural question for spatial data: “group stops within 500 m of each other”.

The trade-off is that DBSCAN does not give you a fixed number of groups, and it struggles when clusters have very different densities, such as a dense city center next to sparse suburbs. Haversine also treats the Earth as a perfect sphere. The scikit-learn documentation puts the resulting error at under 1% on average, which is fine for clustering.

Which Approach Should You Use?

Situation Approach
Data in one city or region, fixed number of groups Project to UTM (or a local projection), then k-means
Groups defined by a distance, unknown count, noise expected DBSCAN with haversine on radians
Data spread across a continent or the globe, fixed number of groups Convert to 3D unit-sphere coordinates (x, y, z), run k-means, then map centers back
Features mix coordinates with other columns (income, store size) Project coordinates, then scale all features so no column dominates

The 3D option deserves a note. Converting each point to (cos(lat)cos(lon), cos(lat)sin(lon), sin(lat)) puts it on a unit sphere, where straight-line distance grows with great-circle distance and the 180th meridian problem disappears. The centroids will sit slightly inside the sphere, so normalize them to unit length before converting back to latitude and longitude.

If you combine coordinates with other features, scaling becomes important, since k-means weighs every column by its numeric range. Our guide to standardization vs min-max scaling covers the options. It also pays to check coordinate columns before clustering (latitude between -90 and 90, no swapped columns, no 0,0 placeholders), which a schema check with Pandera data validation can catch automatically.

Back to the Two Vans

The analyst from the opening does not need a new algorithm. Projecting the addresses to UTM zone 32N takes three lines, and the same k-means call then gives one road per van. If the company later wants groups like “stops within 500 m of each other” instead of a fixed number of routes, DBSCAN with haversine distance answers that question on the raw coordinates. Either way, the clustering finally measures the distances the vans actually drive.

Frequently Asked Questions

Can I Use K-Means on Latitude and Longitude Directly?

Only as a rough approximation for data near the equator in a tight area. Elsewhere, longitude degrees are shorter than latitude degrees, so k-means overweights east to west differences, and the 180th meridian breaks distances completely. Projecting first costs almost nothing.

Why Doesn’t scikit-learn KMeans Support Haversine Distance?

K-means updates each center by taking the mean of its points, and that mean minimizes squared Euclidean distance specifically. With another distance the mean is no longer the right center, so the algorithm loses its guarantees. Methods such as DBSCAN, which only compare distances between points, can use haversine directly.

How Do I Choose Eps for DBSCAN on Geographic Data?

Start from the business meaning: the largest gap between two points you would still call part of the same group, such as 500 m for a delivery cluster. Convert it to radians by dividing by 6,371 km. Then adjust min_samples until isolated points are labeled noise and real clusters stay intact.

How Many Clusters Should K-Means Use for Spatial Data?

Often the problem decides it: the number of vans, depots or sales reps. When it does not, compare the silhouette score or the within-cluster sum of squares across several values of k, and check the results on a map, since a split that scores well can still make no sense on the ground.

Disclaimer: The content on this website reflects the views of contributing authors and not necessarily those of Generative AI Lab. This site may contain sponsored content, affiliate links, and material created with generative AI. Thank you for your support.

Generative AI Lab mascot
Generative AI Lab Editorial Team
Articles researched, written and edited by the Generative AI Lab team. About Generative AI Lab

Must read

- Advertisement -spot_img

More articles

- Advertisement -spot_img

Latest articles