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!