# Criteria evaluation for cluster generation in R

The code below finds the "optimal" number of clusters. In the example below, the result was 2 clusters.

Quickly explaining the code: first, the Ideal Point is calculated, which has the minimum breadth of coverage and the maximum waste production value. Then, the Final Solution is selected as the closest Sk solution to the Ideal Point, and k is selected as the best number of clusters. For my purpose this code works fine. However, I would like to know if there is any approach to evaluating the criteria that help to select the number of clusters for this example? In this case, the criteria are breadth of coverage and waste generation potential. Maybe use some multicriteria method? I'm open to suggestions.

library(rdist)
library(geosphere)
library(dplyr)

df1<-structure(c(3315.15739850453, 2589.99900391847, 8869.03953528711,7708.11156943467,
7708.11156943467, 6015.73943344633, 6577.67722745424,5805.83051830159,
4791.95901175901, 4791.95901175901, 4791.95901175901,
4617.00232604443, 4430.08754078434, 4430.08754078434, 4430.08754078434,
4483.18948278638, 4483.18948278638, 3302.09189638597,
1635156.04305,474707.64025, 170773.40775, 64708.312, 64708.312,
64708.312, 949.72635, 949.72635, 949.72635, 949.72635, 949.72635, 949.72635,
949.72635, 949.72635, 949.72635, 949.72635, 949.72635, 949.72635), .Dim = c(18L, 2L
), .Dimnames = list(NULL, c("Breadth of Coverage", "Waste")))

df2<-structure(c(14833.1911512297, 11518.0337527251, 10088.9627146591,8928.03474880667,
8928.03474880667, 7235.66261281833, 7235.66261281833,6463.81590366569,
5449.94439712311, 5449.94439712311, 5449.94439712311,
5274.98771140853, 5088.07292614843, 5088.07292614843, 5088.07292614843,
5088.07292614843,5088.07292614843,3906.975,3315.15739850453,
2589.99900391847, 8869.03953528711, 7708.11156943467, 7708.11156943467,
6015.73943344633, 6577.67722745424, 5805.83051830159, 4791.95901175901,
4791.95901175901, 4791.95901175901, 4617.00232604443, 4430.08754078434,
4430.08754078434, 4430.08754078434, 4483.18948278638,4483.189,4483.189,
1635156.04305, 474707.64025, 170773.40775,64708.312, 64708.312, 64708.312,
949.72635, 949.72635, 949.72635,949.72635, 949.72635, 949.72635, 949.72635,
949.72635, 949.72635,949.72635,949.7264,949.7264),
.Dim = c(18L, 3L),.Dimnames = list(NULL, c("Coverage","Breadth of Coverage", "Waste")))

#Ideal Point is considered the minimum breadth of coverage and maximum production of Waste
IdealPoint<-as.matrix(t(c(min(df1[,1]),max(df1[,2]))))
distance_df1_Ideal<-as.matrix(dist(rbind(df1,IdealPoint)))

#calculating the distance of the cluster solutions to the ideal point
distance_cluster_ideal<-min(distance_df1_Ideal[as.matrix(dim(df1))[1,1]+1,1:as.matrix(dim(df1))[1,1]])
a<-which(distance_df1_Ideal[dim(df1)[1]+1,]==distance_cluster_ideal)
FinalSolution<-df1[a[1],]

f1 <- function(mat, vec, dim = 1, tol = 1e-7, fun = all)
which(apply(mat, dim, function(x) fun(dist(x - vec) < tol)))

b<-as.matrix(f1(df2[,2:3],FinalSolution,fun=any))# optimal value of number of clusters

k<-b[1]+1 #number of clusters
> k
[1] 2

• A standard way to evaluate such a method would be to generate data in which you know what the true clusters are, and then to see whether the method recovers the true number of clusters better than existing competitors. This crucially depends on what you define a cluster to be, as there are various definitions around, and whatever clustering or number of clusters method will only work well relative to the specific cluster concept in use. You may want to read arxiv.org/abs/1503.02059 particularly Sec. 2 and 5.1., maybe also arxiv.org/abs/1809.10496 Feb 3, 2022 at 22:20
• Here is a pretty comprehensive study comparing some methods that are used for estimating the number of clusters: sciencedirect.com/science/article/abs/pii/S003132031200338X Feb 3, 2022 at 22:30
• Crossposted on OR.SE: Criteria evaluation for cluster generation in R Mar 16, 2022 at 22:42

If I understand correctly, you have a clustering method and you want to have an objective way to decide which clustering or set of clusters is best.

A relatively common way (though not, by any means, the only way) to compute the silhouette coefficient for a particular set of clusters.

The silhouette coefficient (explained in some more detail here and here) is a pretty intuitive way of evaluating clustering quality. It essentially compares how tight your clusters are vs. how far away the clusters are from each other to determine how well the data is clustered overall. This makes sense, since you ideally want extremely tight clusters that are very far away from all other clusters, so your clustering is non-overlapping and has clear boundaries.

Here is the formula, and I will explain below:

a(i) is how dissimilar a point is to the other points within its own cluster. b(i) is how dissimilar a point is to the other points of the nearest neighboring cluster. This "silhouette coefficient" measure can range from -1 to 1, where -1 is very poor clustering and +1 is very good clustering.

So, the calculation essentially works this way:

For every point i in your entire dataset, do the following -

1. Calculate the distance from point i to all other points in i's cluster and take the mean. Call this mean a(i).
2. Calculate the distance from point i to all points in the closest cluster to i's cluster, and take the mean of all those distances. Call this b(i).
3. Compute the formula for s(i) (silhouette coefficient) as shown above, using these values of a(i) and b(i).
4. Repeat above process for all points in your dataset, to obtain an s(i) for each of them. Take the average of all the s(i)'s (silhouette coefficients) to get your overall clustering quality.

Conceptual motivation: I hope you can see, by looking at the formula, that the coefficient goes up when your clustering is tight (because then a(i) is low - distance between points of a single cluster is small, as they are close to each other) and when your inter-cluster distance is large (because b(i) is large - distance from points within a cluster are far away from their closest neighboring cluster, meaning clusters do not overlap a lot).

How to use it

So, you would use this by computing the overall silhouette coefficient for multiple clusterings (clustering by different methods, clustering with one method but you're trying to decide optimal number of clusters etc.) and you would choose the clustering that gives you the highest silhouette coefficient (as this gives best tradeoff between tightness of clusters and distance between clusters).

For example, you have your method of clustering and you want to know what number of clusters is best. You run the clustering method to generate 2, 3, 4, and 5 clusters. After each time you generate the clusters, you calculate the overall silhouette coefficient. Let's say for 2 clusters, you got 0.2, for 3 you got 0.4, for 4 you got 0.5, for 5 you got 0.03 . So, you see that the 4 cluster option gave the best combination of cluster tightness + distance between clusters (since the coefficient was the highest), so you choose 4 clusters as your best way to go.

I hope I understood your question correctly, and I hope you find this helpful!