Clustering based on a variable and on a distance matrix

[flucoe]

I have a dataset with locations (coordinates) and a scalar attribute of each location (for example, temperature). I need to cluster the locations based on the scalar attribute, but taking into consideration the distance between locations.

The problem is that, using temperature as an example, it is possible for locations that are far from each other to have the same temperature. If I cluster on temperature, these locations will be in the same cluster when they shouldn't. The opposite is true if two locations that are near each other have different temperatures. In this case, clustering on temperature may result in these observations being in different clusters, while clustering based on a distance matrix would put them in the same one.

So, is there a way in which I could cluster observations giving more importance to one attribute (temperature) and then "refining" based on the distance matrix?

Here is a simple example showing how clustering differs depending on whether an attribute is used as the basis or the distance matrix. My goal is to be able to use both, the attribute and the distance matrix, giving more importance to the attribute.

import numpy as np
import matplotlib.pyplot as plt
import haversine
from scipy.cluster.hierarchy import linkage, fcluster
from scipy.spatial import distance as ssd

# Create location data
x = np.random.rand(100, 1)
y = np.random.rand(100, 1)

t = np.random.randint(0, 20, size=(100,1))

# Compute distance matrix
D = np.zeros((len(x),len(y)))
for k in range(len(x)):
    for j in range(len(y)):
        distance_pair= haversine.distance((x[k], y[k]), (x[j], y[j]))
        D[k,j] = distance_pair

# Compare clustering alternatives
Zt = linkage(t, 'complete')
Zd = linkage(ssd.squareform(D), method="complete")

# Cluster based on t
clt = fcluster(Zt, 5, criterion='distance').reshape(100,1)
plt.figure(figsize=(10, 8))
plt.scatter(x, y, c=clt)  
plt.show()

# Cluster based on distance matrix
cld = fcluster(Zd, 10, criterion='distance').reshape(100,1)
plt.figure(figsize=(10, 8))
plt.scatter(x, y, c=cld)  
plt.show()

haversine.py is available here: https://gist.github.com/rochacbruno/2883505

For full disclosure, I posted this question in stackoverflow a couple of days ago but so far I haven't received any feedback.

Thanks

[scidam]

Hi!

If you want to take into account coordinates along with temperatures, you probably need to use
custom distance, e.g. weighted distance:

import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, fcluster
from scipy.spatial import distance as ssd
from scipy.spatial.distance import pdist, cdist



# copied from haversine.py 
import math
def haversine_distance(origin, destination):
    lat1, lon1 = origin
    lat2, lon2 = destination
    radius = 6371 # km

    dlat = math.radians(lat2-lat1)
    dlon = math.radians(lon2-lon1)
    a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(lat1)) \
        * math.cos(math.radians(lat2)) * math.sin(dlon/2) * math.sin(dlon/2)
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    d = radius * c

    return d 
 
 
 
def compute_distance_matrix(X, temp_weight=None, coord_weight=None):
    D = pdist(X[:, :2], lambda x, y: haversine_distance(x, y))  
    T = pdist(X, lambda x, y: abs(x[-1] - y[-1])) # pairwise differences by temperature
    if temp_weight is None or coord_weight is None: # if at least one of the weights isn't defined, use coordinates only
        return D
    return temp_weight * T + coord_weight * D
       
    
 
np.random.seed(30) 
 
 
# Create location data
x = np.random.rand(100, 1)
y = np.random.rand(100, 1)
 
t = np.random.randint(0, 20, size=(100,1))

 

X = np.hstack([x, y, t])

# Compare clustering alternatives
distance_matrix = compute_distance_matrix(X, temp_weight=100, coord_weight=5)
Zd = linkage(distance_matrix, method="complete")
 
 
# Cluster based on distance matrix
cld = fcluster(Zd, 10, criterion='distance').reshape(100,1)
plt.figure(figsize=(10, 8))
plt.scatter(x, y, c=cld)  
plt.show()

You need to make some experiments with temp_weight and coord_weight values
to get optimal result. The greater the temp_weight value, the bigger impact of temperature on
the cluster structure.

[flucoe]

This is great, thank you!