---
title: "Nearest-Neighbor Clustering with jpclust and sNNclust"
author: "Michael Hahsler"
output:
  rmarkdown::html_vignette:
    toc: true
vignette: >
  %\VignetteIndexEntry{Nearest-Neighbor Clustering with jpclust and sNNclust}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r setup, include=FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  fig.width = 6,
  fig.height = 4
)
library(dbscan)
```

The **dbscan** package implements two clustering algorithms based on shared
nearest neighbors:

* `jpclust()` implements Jarvis--Patrick clustering; and
* `sNNclust()` implements shared nearest neighbor (SNN) clustering with a
  DBSCAN-style density step.

Both algorithms replace the original distances between observations with a
local similarity: two observations are more similar when their lists of
nearest neighbors have a large overlap. This can be useful when Euclidean
distance alone does not describe local cluster structure well, especially in
data with irregular shapes or differing local densities.

## Shared nearest neighbors

For each observation, first find its `k` nearest neighbors. The shared-neighbor
similarity between two observations is the number of neighbors appearing in
both lists. The package treats each observation as part of its own neighborhood
when counting shared neighbors, and the resulting similarity is between `0`
and `k`.

The algorithms use this information differently:

| Function | Link or neighborhood rule | Cluster formation | Noise model |
|:--|:--|:--|:--|
| `jpclust()` | Mutual nearest neighbors sharing at least `kt` neighbors | Connected components | No; isolated observations form small clusters |
| `sNNclust()` | Mutual nearest neighbors sharing at least `eps` neighbors | DBSCAN-style core, border, and density-connected points | Yes; label `0` denotes noise |

The thresholds `kt` and `eps` are counts of shared neighbors. In particular,
`eps` in `sNNclust()` is not a distance radius and has a different meaning
from `eps` in `dbscan()`.

## Example data

We use the `DS3` data supplied with the package. It contains six
irregularly-shaped groups together with noise and a sinusoidal structure that
intersects the groups.

```{r data}
data("DS3")
x <- as.matrix(DS3)

plot(x, pch = 19, cex = 0.25, asp = 1, main = "DS3 data")
```

For numeric matrices and data frames, both functions use Euclidean distance
and fast kd-tree nearest-neighbor search. Variable scales therefore matter.
Standardize variables when their units are not comparable and scaling is
appropriate for the application.

## Jarvis--Patrick clustering

Jarvis--Patrick clustering links two observations when both of the following
conditions hold:

1. Each observation is in the other's `k`-nearest-neighbor list.
2. Their neighborhoods share at least `kt` neighbors.

Connected observations form clusters. Here we use neighborhoods of 20 points
and require 12 shared neighbors.

```{r jp-fit}
jp <- jpclust(x, k = 20, kt = 12)
c(clusters = ncluster(jp), noise = nnoise(jp))
```

Cluster assignments are stored in `jp$cluster` in the same order as the rows
of `x`. The result also records the algorithm name, distance metric, and
parameters.

```{r jp-result}
names(jp)
jp$param
head(jp$cluster)
```

The convenience function `clplot()` marks observations by cluster. It uses
the first two columns when the data have more than two dimensions.

```{r jp-plot}
clplot(x, jp, cex = 0.25, main = "Jarvis-Patrick clustering")
```

Jarvis--Patrick clustering has no explicit concept of noise. Observations not
connected to a larger group become singleton or other small clusters rather
than receiving label `0`. Conversely, a chain of qualifying links can join
larger structures. In this example, the sinusoidal points can connect groups
that otherwise appear separate.

Increasing `kt` makes the link rule stricter. This removes edges from the
shared-neighbor graph and can split clusters or create more small components.
Decreasing `kt` adds edges and can merge clusters through chaining.

```{r jp-sensitivity}
jp_settings <- c(10, 12, 14)
jp_fits <- lapply(
  jp_settings,
  function(threshold) jpclust(x, k = 20, kt = threshold)
)

data.frame(
  kt = jp_settings,
  clusters = vapply(jp_fits, ncluster, integer(1)),
  singleton_clusters = vapply(
    jp_fits,
    function(fit) sum(table(fit$cluster) == 1L),
    integer(1)
  )
)
```

The required range is `1 <= kt <= k`. A useful setting should preserve stable,
meaningful components without fragmenting the data into many tiny clusters.

## Shared nearest neighbor clustering

`sNNclust()` adds a density model to the shared-neighbor graph:

1. Build `k`-nearest-neighbor lists and their shared-neighbor similarities.
2. Retain mutual-neighbor relationships with similarity at least `eps`.
3. Treat an observation as a core point if its SNN neighborhood contains at
   least `minPts` points.
4. Join density-connected core points and optionally assign border points.

For the example, two neighbors must share at least 7 of their 20 neighbors,
and an observation needs a sufficiently dense SNN neighborhood of at least 16
points to become a core point.

```{r snn-fit}
snn <- sNNclust(x, k = 20, eps = 7, minPts = 16)
snn
```

As with DBSCAN, positive integers are arbitrary cluster identifiers and `0`
denotes noise.

```{r snn-plot}
clplot(x, snn, cex = 0.25, main = "Shared nearest neighbor clustering")
```

The parameters control different parts of the algorithm:

* `k` determines the scale at which local neighborhoods are compared. Small
  values emphasize very local structure; large values smooth the similarities
  over a wider neighborhood.
* `eps` is the minimum number of shared neighbors needed for an SNN
  relationship. Increasing it makes similarity more selective.
* `minPts` is the density requirement in the thresholded SNN graph. Increasing
  it makes core-point status more difficult to attain and generally produces
  more noise.
* `borderPoints = TRUE`, the default, assigns non-core observations adjacent
  to a core cluster. Set it to `FALSE` for a core-points-only result analogous
  to DBSCAN*.

Parameter effects interact, so inspect several nearby settings rather than
selecting each value independently.

```{r snn-sensitivity}
snn_settings <- data.frame(
  eps = c(5, 7, 9),
  minPts = c(16, 16, 16)
)

snn_fits <- lapply(
  seq_len(nrow(snn_settings)),
  function(i) sNNclust(
    x,
    k = 20,
    eps = snn_settings$eps[i],
    minPts = snn_settings$minPts[i]
  )
)

transform(
  snn_settings,
  clusters = vapply(snn_fits, ncluster, integer(1)),
  noise = vapply(snn_fits, nnoise, integer(1))
)
```

Cluster counts alone do not identify the best solution. Examine whether the
important groups persist, whether points labeled as noise are plausible, and
whether conclusions are stable under small parameter changes.

## Reuse a nearest-neighbor search

Nearest-neighbor search can be computed once and reused. This is especially
helpful when comparing algorithms or parameter settings on a large data set.
Compute at least the largest `k` that any later fit will need.

```{r reuse-knn}
nn <- kNN(x, k = 30)

jp_from_nn <- jpclust(nn, k = 20, kt = 12)
snn_from_nn <- sNNclust(nn, k = 20, eps = 7, minPts = 16)

c(
  jp_same = identical(jp$cluster, jp_from_nn$cluster),
  snn_same = identical(snn$cluster, snn_from_nn$cluster)
)
```

When the full stored neighborhood should be used, `k` may be omitted from
`jpclust()` because it can be recovered from the `kNN` object. Keep `k`
explicit when using only the first part of a larger precomputed neighborhood.

## Inspect the shared-neighbor graph

The lower-level `sNN()` function exposes the shared-neighbor calculation. Its
`shared` matrix gives the similarity between each observation and each of its
`k` nearest neighbors.

```{r inspect-snn}
shared_nn <- sNN(nn, k = 20, jp = TRUE, sort = FALSE)
shared_nn
table(shared_nn$shared)
```

Using `jp = TRUE` reproduces the mutual-neighbor similarity used internally by
`sNNclust()`. Use this distribution as a diagnostic when selecting a
shared-neighbor threshold. `sNN()` can also apply a threshold directly and its
graph can be inspected with `adjacencylist()` or plotted for small data sets;
see `?sNN`.

## Use a precomputed distance matrix

Both clustering functions also accept a `dist` object. This permits other
distance measures, at the cost of storing all pairwise distances and giving
up the fast kd-tree search.

```{r other-distance, eval=FALSE}
d <- dist(my_data, method = "manhattan")

jp_manhattan <- jpclust(d, k = 20, kt = 12)
snn_manhattan <- sNNclust(d, k = 20, eps = 7, minPts = 16)
```

The distance matrix must be finite. Choose a distance measure, transformations,
and scaling based on the meaning of the variables rather than solely on the
resulting number of clusters.

## Which method should you use?

Use `jpclust()` when a simple connected-components interpretation of mutual
shared-neighbor links is appropriate and small components are meaningful.
Use `sNNclust()` when the analysis needs an explicit density requirement,
noise labels, or control over core and border points. For either method, `k`
sets the neighborhood scale and should reflect the smallest local structure
that needs to be retained.

## References

Jarvis, R. A. and Patrick, E. A. (1973). Clustering Using a Similarity Measure
Based on Shared Near Neighbors. *IEEE Transactions on Computers*, 22(11),
1025--1034. [doi:10.1109/T-C.1973.223640](https://doi.org/10.1109/T-C.1973.223640).

Ertoz, L., Steinbach, M., and Kumar, V. (2003). Finding Clusters of Different
Sizes, Shapes, and Densities in Noisy, High Dimensional Data. *Proceedings of
the 2003 SIAM International Conference on Data Mining*, 47--58.
[doi:10.1137/1.9781611972733.5](https://doi.org/10.1137/1.9781611972733.5).