# Cluster based on both positions and similarity scores

I have a dataframe position giving me the x and y positions of 87 points. I also have a 87 x 87 similarity matrix giving me the pairwise similarity scores between those points. My goal is to form groups of points taking into account both the spatial distances and the similarity scores between the points and to find relevant metrics to quantify the quality of the resulting clusters.

I do not have ground truth labels and I do not have prior beliefs on how many clusters I should end up with. After a bit of investigation, I noticed that similarity is usually inversely proportional to distance: close points are more similar than far away points but it happens some times. My similarity scores varies from 0 to 894. it is a very sparse matrix (1035 non zero values), oddly enough it has some zeros on the diagonal, the mean value is 4 and the std is 25. the max value out of the diagonal is 400.

So far I have tried:

• to form clusters taking only the similarity scores into account using AffinyPropagation. This seems to give the most visually pleasant clusters so far but I still need a metric to quantify the quality. This gives me 15 clusters with some overlapping

• to convert my positions into an 87x87 euclidean distances matrix and then this matrix into a spatial affinity matrix, and combine the spatial affinity and the similarity into a single affinity measure by adding them or multiplying them and then applying affinity based clustering algorithms.

• to convert my similarity matrix into a distance matrix by defining d(x1,x2) = min_x3{ 1/sim(x1,x3) + 1/sim(x3, x2)} (I am not sure if the triangle inequality holds but it has been suggested here) and then combine my euclidean distances and these distances into a single distance by adding them or multiplying them and then applying distance based clustering algorithms.

• to use spectral embedding such as laplacian eigenmaps using only the similarity scores to map my points into a 2d or 3d embedding and use clustering algorithms from there. This does not seem to work very well: I end up with 2 clusters and I think the right number should be around 10-15

• I also tried all kind of transformation on the similarity matrix: making it symmetric (it is originally not symmetric), normalizing by dividing by the max value, capping to a percentile and then normalizing, filling the diagonal with ones... it does not seem to make a big difference in the clusters

I am running out of ideas and looking for the general way of dealing with such problems if any exists and for metrics to be able to compare my different approaches.

As I do not know the ground truth labels, according to scikit learn documentation I can only use SilhouetteCoefficient, calinski harabasz index, and davies bouldin index but I am not very familiar with thesee. I also thought of Percentage of Variance Explained as used in the Elbow Method to find the best number of clusters.

Any suggestion would be greatly appreciated!

• Don't you think a theoretical approach is more helpful than trial and error and going by what you consider "visually pleasant"? What is the theory behind what you are doing, and how does it related to the problem you have to solve? You should be asking "what is the right thing to do", not "what can I try and hope it looks nice".... Commented Jul 10, 2019 at 17:11
• Maybe I was not clear but that is exactly what I am asking. "what is the right thing to do?" is very close to "what is the general way to deal with such problems" isn't it? Commented Jul 11, 2019 at 0:54
• There is no "general" way, and you discuss x different attempts but you don't discuss the data not the meaning of it. Commented Jul 11, 2019 at 5:19
• I discussed my different approaches because I did not want answers suggesting to try those approaches and I would also have feedback about these approaches, see if they make sense to other people or not. I think you read my question wrong, I am not going by what I consider visually pleasant, and on the opposite I am looking for a metric. I found one that makes sense to me. I did not discuss the meaning of my data because of I am not allowed to disclose it, and I think it does not really matter because as you said a theoretical approach is more helpful and should apply to all kinds of data. Commented Jul 12, 2019 at 3:34
• No, a theoretical approach would be a specific theory for only this data set. Commented Jul 12, 2019 at 4:50