1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Please mention the langauge of your choice in the future so it'll be easier for people to provide help. $\endgroup$ – Aymuos Nov 13 '20 at 5:56
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Trying to work out if there's a difference between this and the solution I found (below). I didn't try to find the minimum number of colors. One thing I wonder about your solution is how to decide whether two clusters are connected? I used knn based on the cluster centroids for this, and just chose k large enough that it looks good given the number of colors in my pallet. $\endgroup$ – groceryheist Nov 13 '20 at 19:46
  • $\begingroup$ What if your clusters are not uniform and a centroid (and its cluster) which seems to be adjacent to a another cluster is actually separated with another cluster? I believe the above approach works for any clustering method (once you have objects cluster labels) For storing the neighborhood of two clusters, one thing might be finding points on clusters edge like storing edges in a dictionary. Then, finding neighboring points of different clusters. So, if cluster1: {A, B, C} and cluster2:{D,E, F} and distance(A,D} is small, they are neighbors. This seems to be brute-force but is generalizable $\endgroup$ – Fatemeh Asgarinejad Nov 15 '20 at 20:26
  • $\begingroup$ But, I haven't seen your approach yet. $\endgroup$ – Fatemeh Asgarinejad Nov 15 '20 at 20:27
  • $\begingroup$ Here's a visualization: teblunthuis.cc/outgoing/subreddit_terms_tsne_3000.html Data are subreddits with an affinity matrix based on tf-idf cosine similarity. The XY plot is based on t-sne. The clusters are based on One complexity is that the XY plot is based on tsne and the clusters are based on clustering in the affinity matrix not the XY plot so sometimes the clusters don't map well onto the coordinates. The coloring is based on coordinates in the XY space. $\endgroup$ – groceryheist Nov 15 '20 at 20:32
  • $\begingroup$ But I see your suggestion is to use the distance from a centroid of cluster A to the nearest point in cluster B as their distance instead of the distance between centroids. Yeah that seems like an improvement. $\endgroup$ – groceryheist Nov 15 '20 at 21:10
1
$\begingroup$

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)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.