Coloring clusters so that nearby clusters have different colors

Question

I have clustered a large number of points (~3000) into (~400) clusters. I want to plot the data and visualize the clusters. I want to make sure that nearby clusters have different colors. Can anyone recommend an approach to coloring the clusters?

This is a conceptual question, but I'm most interested in solutions in python or R.

Answer 1

matplotlib already takes care of coloring adjancent clusters with different colors. But, I believe it uses a unique color for each cluster. If that's the case, 400 colors would be too much.

There might be better ways, but worst case, try this:

We want to color with minimum number of colors. Hence, the problem turns to a graph coloring problem in which, we don't want two connected adjacent nodes have the same color. Finding the minimum number of colors is an np-hard problem but we can use approximate algorithms.

One way could be defining your cluster centroids as graph nodes and storing their connections and then using a graph coloring algorithm.

Step 1: Store your clusters as an adjacency matrix and convert this matrix to a graph wherein each centroid is the representative of a cluster and the adjacency matrix contains the connectivity(neighborhood) between each centroid and the others. Explanation Code

Step 2: use a coloring algorithm to color the nodes of the graph.

This post contains a coloring algorithm that gets the graph and returns the coloring for that.

Step 3: having the color of each centroid, you can color the whole clusters with minimum number of colors.

Answer 2

I found that taking the centroids of each cluster, running k-nearest-neighbors, and then applying https://en.wikipedia.org/wiki/Greedy_coloring works well. Just keep increasing K until the clusters stand out.

Edit: following @Fatemeh Asgarinejad's suggestion, use the minimum distance from a cluster centroid to a member of the other clusters as the distance in computing KNN Now. This is slower but seems to give a more robust coloring when clusters overlap or have irregular shapes.

My python code:

# data is a pandas data frame of data points with cluster labels

from sklearn.neighbors import NearestNeighbors

def assign_cluster_colors(data, clusters, n_colors=10, n_neighbors = 8):
    
    
    centroids = data.groupby('cluster').agg({'x':np.mean,'y':np.mean})

    color_ids = np.arange(n_colors)

    distances = np.empty(shape=(centroids.shape[0],centroids.shape[0]))

    groups = tsne_data.groupby('cluster')
    for centroid in centroids.itertuples():
        c_dists = groups.apply(lambda r: min(np.sqrt(np.square(centroid.x - r.x) + np.square(centroid.y-r.y))))
        distances[:,centroid.Index] = c_dists

    nbrs = NearestNeighbors(n_neighbors=n_neighbors,metric='precomputed').fit(distances) 
    distances, indices = nbrs.kneighbors()

    color_assignments = np.repeat(-1,len(centroids))

    for i in range(len(centroids)):
        knn = indices[i]
        knn_colors = color_assignments[knn]
        available_colors = color_ids[list(set(color_ids) - set(knn_colors))]

        if(len(available_colors) > 0):
            color_assignments[i] = available_colors[0]
        else:
            raise Exception("Can't color this many neighbors with this many colors")


    centroids = centroids.reset_index()
    colors = centroids.loc[:,['cluster']]
    colors['color'] = color_assignments

    data = data.merge(colors,on='cluster')
    return(data)