---
title: "Interpreting silhouette widths"
output:
  rmarkdown::html_vignette:
    toc: true
vignette: >
  %\VignetteIndexEntry{Interpreting silhouette widths}
  %\VignetteEncoding{UTF-8}
  %\VignetteEngine{knitr::rmarkdown}
bibliography: references.bib
---

```{r setup, include = FALSE}
pkgs <- c("proxy", "cluster", "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.")
```

Silhouette widths look alike but mean different things depending on how they
were computed. This vignette explains how the widths in **Silhouette** relate to
the classical silhouette, what ranges they take, and which comparisons between
them are valid.

```{r library}
library(Silhouette)
X <- as.matrix(iris[, 1:4])
set.seed(1)
km <- kmeans(X, centers = 3, nstart = 20)
P <- as.matrix(proxy::dist(X, km$centers))   # distances to the 3 centers
```

# Classical and simplified widths

The classical width of @rousseeuw1987silhouettes compares the *average*
dissimilarity of observation $i$ to the other members of its cluster, $a_i$,
with the smallest average dissimilarity to the members of another cluster,
$b_i$:
$$
s_i = \frac{b_i - a_i}{\max(a_i, b_i)}.
$$
It needs all $n(n-1)/2$ pairwise dissimilarities. The simplified silhouette of
@vanderlaan2003pam replaces the two averages by the dissimilarities between
$x_i$ and a representative of each cluster, such as its centroid or medoid, so
it needs only an $n \times K$ matrix. That is what `Silhouette()` computes.

The two are related but not equal:

```{r classical}
s_simple <- Silhouette(P)$sil_width
s_classic <- cluster::silhouette(km$cluster, dist(X))[, "sil_width"]
c(correlation = cor(s_simple, s_classic),
  mean_simplified = mean(s_simple),
  mean_simplified_pac = mean(Silhouette(P, method = "pac")$sil_width),
  mean_classical = mean(s_classic))
```

The simplified widths rank observations much as the classical ones do, but the
simplified average (medoid normalization) is higher, because the distance to a
centroid is smaller than the average distance to all members of a cluster. The
PAC average is usually closer to the classical level. Thresholds published for
the classical average, such as "above 0.5 is reasonable structure", therefore do
not transfer to the simplified average. If you need a fast approximation of the
classical width itself for a crisp partition, `approxSilhouette()` in the
Bioconductor package **bluster** [@bluster] is designed for that; the strengths
of **Silhouette** are soft and model-based clusterings, arbitrary cluster-level
proximities, and multi-way partitions.

# Three properties of the simplified widths

Write $a_i$ and $b_i$ for the proximities to the assigned and neighboring
clusters, and $r_i = a_i / b_i$ for dissimilarities.

**1. With labels from the same matrix, the widths are not negative.** Without
`cluster` or `prob_matrix`, `Silhouette()` assigns each observation to its
nearest cluster, so $a_i \le b_i$ and the medoid width $1 - r_i$ lies in
$[0, 1]$. Unlike the classical silhouette, where a negative width flags an
observation that is closer on average to another cluster, poorly placed
observations show up here as widths near zero. Negative widths appear only when
the partition comes from elsewhere (next section).

```{r nonnegative}
min(s_simple)
```

**2. PAC is a monotone shrinkage of the medoid width.** The PAC width is
$(1 - r_i)/(1 + r_i) = s_i / (2 - s_i)$, and $s_i / (2 - |s_i|)$ in general. It
orders observations exactly as the medoid width does and is never larger in
absolute value (a medoid width of 0.5 becomes 1/3), so the choice between them
changes the level of the average, not which observations look poorly clustered.

**3. Squared distances inflate the widths.** Replacing every distance by its
square replaces $r_i$ by $r_i^2$, and the width by $1 - r_i^2 = s_i(2 - s_i)$.
Some functions, such as `ppclust::fcm()`, return squared distances, so check the
scale of the matrix you pass.

```{r squared}
all.equal(Silhouette(P^2)$sil_width, s_simple * (2 - s_simple))
```

# Where the cluster labels come from

A silhouette scores a partition, so it matters which partition is scored. Every
width function takes its labels, in order of precedence, from

1. the `cluster` argument, when supplied;
2. the largest membership in `prob_matrix`, when supplied;
3. the closest cluster in the proximity matrix.

For k-means at convergence, the nearest center is the assigned cluster, but for
other methods it need not be. Without `cluster`, scoring an average-linkage
partition against its own centroids would silently reassign some observations
to their nearest centroid; with `cluster`, the partition is kept and those
observations receive negative widths:

```{r relabel}
hc <- cutree(hclust(dist(X), method = "average"), k = 3)
centers <- apply(X, 2, function(v) tapply(v, hc, mean))
P_hc <- proxy::dist(X, centers)
c(reassigned_without_cluster = sum(Silhouette(P_hc)$cluster != hc),
  negative_with_cluster = sum(Silhouette(P_hc, cluster = hc)$sil_width < 0))
```

If a membership matrix is supplied as `prob_matrix`, the labels come from the
memberships. An observation whose most probable cluster is not its nearest
center then gets a negative width, which is informative: it marks disagreement
between the fitted model and the geometry. For a Gaussian mixture:

```{r negative}
suppressPackageStartupMessages(library(mclust))
gm <- Mclust(X, G = 3, verbose = FALSE)
P_gmm <- as.matrix(proxy::dist(X, t(gm$parameters$mean)))
sum(Silhouette(P_gmm, prob_matrix = gm$z)$sil_width < 0)
```

# Ranges of the widths

| Width | Function and argument | Range |
|:---|:---|:---|
| medoid | `Silhouette(method = "medoid")` | $[0, 1]$ with labels from the same matrix |
| PAC | `Silhouette(method = "pac")` | $[0, 1]$ with labels from the same matrix |
| PACS, PPS (posterior probabilities) | `softSilhouette(prob_type = "pp")` | $[0, 1]$ |
| NLPPS (negative log posteriors) | `softSilhouette(prob_type = "nlpp")` | $[0, 1]$ |
| PDS (probability densities) | `softSilhouette(prob_type = "pd")` | $[0, 1]$ |
| CeS (certainty) | `cerSilhouette()` | $[1/K, 1]$ |
| DBS (density-based) | `dbSilhouette()` | $[0, 1]$, and the maximum in each sample is always 1 |

The ranges assume the default labels. With labels supplied through `cluster`
(or, for `Silhouette()`, through `prob_matrix`), every width except the
certainty width can be negative and ranges over $[-1, 1]$; the certainty width
ranges over $[0, 1]$.

Exactly tied proximities or memberships are resolved in favor of the column
that comes first. With ties, the labels (though not the widths, which are then
0) depend on the order of the columns; supply `cluster` to control them.

# Which comparisons are valid

- **The same width across partitions of the same data.** Average widths of one
  kind (same function, method, transformation and averaging) can be compared
  across algorithms or numbers of clusters, keeping in mind that each width
  favors a particular kind of cluster.
- **Not one width against another.** The rows of `calSilhouette()` are on
  different scales. Choosing "the best method" by the largest value compares
  scales, not clusterings. Nor are the rows independent evidence: each PAC row
  is a monotone transformation of the matching medoid row, the PPS, PACS and
  DBS rank observations identically, the PDS equals the PPS when the clusters
  have equal weights, and for fuzzy c-means the PPS and distance-based widths
  coincide (see `?calSilhouette`).
- **Not simplified against classical.** See the first section.
- **Fuzzy averages only at the same `a`.** The weights
  $(\gamma_{i(1)} - \gamma_{i(2)})^a$, built from the two largest memberships,
  change with `a`, and so does the average.
- **Certainty and density-based widths with care.** The certainty width cannot
  fall below $1/K$, so its level falls as $K$ grows. The density-based width is
  scaled by the most confident observation in the sample, so its average
  depends on that one observation.
- **Choosing $K$ needs a stated reading.** For the distance-based widths, the
  number of clusters is usually read where the average is largest. For the
  widths computed from memberships (PACS, PPS, NLPPS, CeS, PDS), whose average
  typically starts near 1 and falls, @bhatkapu2024density read it from the
  reverse elbow drop, and the DBS is read from its local maxima
  [@menardi2011density]. The result depends on the algorithm, the width and the averaging; see
  `vignette("soft-clustering", package = "Silhouette")`.

# Session information

```{r session, eval = TRUE}
sessionInfo()
```

# References
