--- title: "Silhouettes for soft and model-based clustering" output: rmarkdown::html_vignette: toc: true vignette: > %\VignetteIndexEntry{Silhouettes for soft and model-based clustering} %\VignetteEncoding{UTF-8} %\VignetteEngine{knitr::rmarkdown} bibliography: references.bib --- ```{r setup, include = FALSE} pkgs <- c("proxy", "ppclust", "mclust") ok <- all(vapply(pkgs, requireNamespace, logical(1), quietly = TRUE)) knitr::opts_chunk$set( collapse = TRUE, comment = "#>", eval = ok, fig.width = 6.5, fig.height = 3.6, dpi = 96, out.width = "100%" ) ``` ```{r not-available, echo = FALSE, results = "asis", eval = !ok} cat("This vignette needs the suggested packages", paste0("'", pkgs, "'", collapse = ", "), "to run its code. Install them to see the output.") ``` Soft clustering methods, such as fuzzy c-means, probabilistic distance clustering and finite mixture models, give each observation a membership probability for every cluster. This vignette shows how **Silhouette** turns those probabilities into silhouette widths, how the different widths relate to one another, and which comparisons they support. ```{r library} library(Silhouette) suppressPackageStartupMessages(library(mclust)) # Mclust() needs mclust attached X <- as.matrix(iris[, 1:4]) set.seed(1) fm <- ppclust::fcm(X, centers = 3, nstart = 5) # fuzzy c-means gm <- Mclust(X, G = 3, verbose = FALSE) # Gaussian mixture ``` # Widths from membership probabilities Write $\gamma_{ik}$ for the membership of observation $i$ in cluster $k$, with $\sum_k \gamma_{ik} = 1$. `softSilhouette()` treats the memberships, or a transformation of them, as a proximity matrix and applies the medoid or PAC width to it [@bhatkapu2024density]. The table gives the names used in that paper: | Name | Call | Proximity | Type | |:---|:---|:---|:---| | PACS | `softSilhouette(z)` | posterior $\gamma_{ik}$ | similarity, PAC width | | PPS | `softSilhouette(z, method = "medoid")` | posterior $\gamma_{ik}$ | similarity, medoid width | | NLPPS | `softSilhouette(z, prob_type = "nlpp", method = "medoid")` | $-\log \gamma_{ik}$ | dissimilarity | | PDS | `softSilhouette(z, prob_type = "pd", method = "medoid")` | density $f_k(x_i)$, computed as $\gamma_{ik} / \hat\pi_k$ | similarity | | CeS | `cerSilhouette(z)` | largest membership $\max_k \gamma_{ik}$ | certainty | | DBS | `dbSilhouette(z)` | $\log(\gamma_{ic_i} / \gamma_{i\nu_i})$, scaled by its sample maximum [@menardi2011density] | log ratio | PACS, PPS and NLPPS take the posterior probabilities as a similarity (or, on the log scale, a dissimilarity) and assign each observation to its largest membership. The PDS takes the component densities as the similarity: for a mixture, $\gamma_{ik} = \pi_k f_k(x_i) / f(x_i)$, so $\gamma_{ik} / \hat\pi_k = f_k(x_i) / f(x_i)$ with $\hat\pi_k = n^{-1} \sum_i \gamma_{ik}$, and the PDS can be computed from the memberships of any soft clustering algorithm. It assigns each observation to its largest density, so it lies between 0 and 1. The certainty silhouette lies between $1/K$ and 1. The DBS of @menardi2011density lies between 0 and 1, and the most confidently assigned observation in the sample always has width 1; Menardi summarizes it by the median, which is the default of `dbSilhouette()`. ```{r widths} avg <- function(s) summary(s, print.summary = FALSE)$avg.width c(PACS = avg(softSilhouette(gm$z)), PPS = avg(softSilhouette(gm$z, method = "medoid")), NLPPS = avg(softSilhouette(gm$z, prob_type = "nlpp", method = "medoid")), PDS = avg(softSilhouette(gm$z, prob_type = "pd", method = "medoid")), CeS = avg(cerSilhouette(gm$z)), DBS = avg(dbSilhouette(gm$z))) ``` These are different indices on different scales. Compare each one across fits, never one index with another. Because they depend only on the memberships, they describe the clustering as the fitted model sees it; the distance-based widths of `Silhouette()` describe it in the data space. # Fuzzy c-means: soft and distance-based widths coincide For fuzzy c-means with fuzzifier $m$ and squared Euclidean distances $d_{ik}$ to the prototypes, the memberships are $u_{ik} = t_{ik}^{-1} / \sum_j t_{ij}^{-1}$ with $t_{ik} = d_{ik}^{1/(m-1)}$ [@bezdek1981]. The ratio of two memberships is therefore the inverse ratio of the corresponding $t_{ik}$: $$ \frac{u_{i\nu_i}}{u_{ic_i}} = \frac{t_{ic_i}}{t_{i\nu_i}}, \qquad\text{so}\qquad 1 - \frac{u_{i\nu_i}}{u_{ic_i}} = \frac{t_{i\nu_i} - t_{ic_i}}{t_{i\nu_i}}. $$ The left-hand side is the `"pp"` medoid width and the right-hand side is the distance-based medoid width on the matrix $T = [t_{ik}]$. The same argument holds for the PAC width. With the default $m = 2$, $T$ is exactly the matrix `d` that `ppclust::fcm()` returns: ```{r identity} all.equal(softSilhouette(fm$u, method = "medoid")$sil_width, Silhouette(fm$d)$sil_width) ``` For fuzzy c-means, then, the membership-based and distance-based widths are the same evidence, and the rows of `calSilhouette()` that look independent are not. With $m = 3$, $T$ holds Euclidean distances, and the `"pp"` widths reproduce the simplified silhouette of @vanderlaan2003pam. # Averaging and the exponent `a` Every width function offers three averages. `average = "crisp"` is the plain mean and `average = "median"` the median. `average = "fuzzy"` is the weighted mean of @campello2006fuzzy, with weights $w_i = (\gamma_{i(1)} - \gamma_{i(2)})^a$, where $\gamma_{i(1)}$ and $\gamma_{i(2)}$ are the two largest memberships of observation $i$. Observations whose two largest memberships are close count for less. The exponent `a` controls how strongly: ```{r exponent} sapply(c(a0 = 0, a0.5 = 0.5, a1 = 1, a2 = 2, a4 = 4), function(a) avg(softSilhouette(fm$u, average = "fuzzy", a = a))) ``` With `a = 0` every weight is 1 and the fuzzy average equals the crisp one. Larger exponents shift weight toward decisively assigned observations and raise the average, so fuzzy averages are comparable only at the same `a`. # Comparing soft clustering algorithms To compare algorithms fitted to the same data with the same number of clusters, compute each width for every fit. Pass the memberships to `Silhouette()` as `prob_matrix` (or the labels as `cluster`) so that each observation keeps the cluster the algorithm assigned. ```{r compare} P_fcm <- sqrt(fm$d) # Euclidean distances P_gmm <- as.matrix(proxy::dist(X, t(gm$parameters$mean))) # to the component means data.frame( algorithm = c("fuzzy c-means", "Gaussian mixture"), distance_medoid = c(avg(Silhouette(P_fcm, prob_matrix = fm$u)), avg(Silhouette(P_gmm, prob_matrix = gm$z))), membership_pp = c(avg(softSilhouette(fm$u)), avg(softSilhouette(gm$z))), ARI_species = c(adjustedRandIndex(max.col(fm$u), iris$Species), adjustedRandIndex(max.col(gm$z), iris$Species))) ``` The two families disagree. Distances to cluster means reward the spherical, equal-spread clusters that fuzzy c-means looks for, so the distance-based width prefers fuzzy c-means. Posterior probabilities reward decisive assignments, which the mixture makes, so the membership-based width prefers the mixture. Here the mixture also agrees better with the species (the adjusted Rand index is shown only as a check, since labels are rarely available). Neither family is a substitute for deciding what kind of cluster the analysis is after. # Choosing the number of clusters For a distance-based width, the number of clusters is usually read where the average is largest. The widths computed from memberships behave differently: their average over $k$ typically starts near 1 and falls, and @bhatkapu2024density read the number of clusters from the *reverse elbow drop*, the value of $k$ after which the average drops sharply. Below, that reading is made automatic as the $k$ just before the largest one-step drop; the DBS is read from its local maxima, following @menardi2011density. Consider four well-separated groups of different spread, clustered by a Gaussian mixture and by fuzzy c-means: ```{r choose-k, fig.alt = "Line chart of average width against the number of clusters from 2 to 8 for four simulated groups: the k-means medoid width and the PACS and certainty widths from Gaussian mixtures and from fuzzy c-means."} set.seed(42) mu <- rbind(c(0, 0), c(6, 0), c(0, 6), c(6, 6)) sds <- c(0.8, 1.2, 1, 1.5) id <- rep(1:4, c(120, 80, 100, 60)) Y <- mu[id, ] + matrix(rnorm(2 * length(id)), ncol = 2) * sds[id] res <- t(sapply(2:8, function(k) { g <- Mclust(Y, G = k, modelNames = "VVV", verbose = FALSE) set.seed(k) km <- kmeans(Y, k, nstart = 20) fc <- ppclust::fcm(Y, centers = k) c(k = k, medoid_kmeans = avg(Silhouette(proxy::dist(Y, km$centers))), PACS_mixture = avg(softSilhouette(g$z)), CeS_mixture = avg(cerSilhouette(g$z)), PACS_fcm = avg(softSilhouette(fc$u)), CeS_fcm = avg(cerSilhouette(fc$u)), bic = g$bic) })) round(res, 3) cols <- c("#2a78d6", "#eb6834", "#eda100", "#1baf7a", "#8a6fd1") matplot(res[, "k"], res[, 2:6], type = "b", pch = c(19, 17, 2, 15, 0), lty = 1, col = cols, xlab = "Number of clusters", ylab = "Average width") legend("bottomleft", colnames(res)[2:6], pch = c(19, 17, 2, 15, 0), col = cols, bty = "n", cex = 0.8) ``` ```{r choose-k-values, include = FALSE} elbow <- function(v) res[which.max(-diff(v)), "k"] best <- c(medoid = res[which.max(res[, "medoid_kmeans"]), "k"], bic = res[which.max(res[, "bic"]), "k"], apply(res[, c("PACS_mixture", "CeS_mixture", "PACS_fcm", "CeS_fcm")], 2, elbow)) ``` The distance-based width is largest at $K = `r best["medoid"]`$ and BIC selects $K = `r best["bic"]`$. Read by the reverse elbow drop, the PACS and certainty averages point to $K = `r best["PACS_mixture"]`$ and `r best["CeS_mixture"]` for the mixture and to `r best["PACS_fcm"]` and `r best["CeS_fcm"]` for fuzzy c-means. Their maximum, by contrast, is not a useful guide, since the averages start near 1. The number of clusters suggested by these widths depends on the algorithm that produced the memberships, on the width and on the averaging, so report all three, and the reading used, with the result. # Pitfalls **Which partition is scored.** Every width function scores one partition: the labels in `cluster` if given, otherwise the largest membership in `prob_matrix`, otherwise the closest cluster in the proximity matrix (the PDS, below, is the exception). `calSilhouette()` uses the same labels in every row except the PDS rows. For a mixture, the most probable component and the nearest mean can differ; those observations are closer to another cluster's mean than to their own and receive negative distance-based widths: ```{r relabel} c(nearest_mean_differs = sum(max.col(gm$z) != max.col(-P_gmm)), negative_widths = sum(Silhouette(P_gmm, prob_matrix = gm$z)$sil_width < 0)) ``` Without `prob_matrix` or `cluster`, `Silhouette()` would instead assign every observation to its nearest mean, scoring a different partition from the one the mixture produced. **The PDS assigns by density.** The PDS places each observation in the cluster with the largest density $f_k(x_i)$, which ignores the mixing proportions, whereas the other widths use the largest membership. When the cluster weights differ, the two can disagree, and the PDS then scores a slightly different partition. To score the mixture's own partition with the PDS, pass it as `cluster`; observations that then receive negative widths are those for which the neighboring component has the higher density: ```{r pd} set.seed(4) z <- c(rnorm(270, 0), rnorm(30, 2.5)) g2 <- Mclust(z, G = 2, modelNames = "E", verbose = FALSE) pds <- softSilhouette(g2$z, prob_type = "pd", method = "medoid") pds_map <- softSilhouette(g2$z, prob_type = "pd", method = "medoid", cluster = max.col(g2$z)) c(density_label_differs = sum(pds$cluster != max.col(g2$z)), negative_default = sum(pds$sil_width < 0), negative_with_map_labels = sum(pds_map$sil_width < 0)) ``` **Zero probabilities and the density-based width.** Mixture posteriors often underflow to exactly zero for well-separated data. A zero neighboring probability makes the log ratio infinite; `dbSilhouette()` then gives that observation width 1, scales the other widths by the largest finite log ratio, and warns: ```{r db-zero} data(thyroid, package = "mclust") gt <- Mclust(scale(thyroid[, -1]), G = 3, verbose = FALSE) db <- dbSilhouette(gt$z, average = "crisp") avg(db) ``` The finite log ratios can still be very large (a posterior of $10^{-300}$ gives a log ratio near 690), and the largest one sets the scale, so the average stays small. The individual widths still rank observations by how decisively they are assigned; the average should not be compared with that of a fit without such extreme probabilities. # Session information ```{r session, eval = TRUE} sessionInfo() ``` # References