dbscan: sNN – R documentation

Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!

sNN

Find Shared Nearest Neighbors

Description

Calculates the number of shared nearest neighbors, the shared nearest neighbor similarity and creates a shared nearest neighbors graph.

Usage

sNN(
  x,
  k,
  kt = NULL,
  jp = FALSE,
  sort = TRUE,
  search = "kdtree",
  bucketSize = 10,
  splitRule = "suggest",
  approx = 0
)

Arguments

`x`	a data matrix, a dist object or a kNN object.
`k`	number of neighbors to consider to calculate the shared nearest neighbors.
`kt`	minimum threshold on the number of shared nearest neighbors to build the shared nearest neighbor graph. Edges are only preserved if `kt` or more neighbors are shared.
`jp`	use the definition by Javis and Patrick (1973), where shared neighbors are only counted between points that are in each other's neighborhood, otherwise 0 is returned. If `FALSE`, then the number of shared neighbors is returned, even if the points are not neighbors.
`sort`	sort by the number of shared nearest neighbors? Note that this is expensive and `sort = FALSE` is much faster. sNN objects can be sorted using `sort()`.
`search`	nearest neighbor search strategy (one of `"kdtree"`, `"linear"` or `"dist"`).
`bucketSize`	max size of the kd-tree leafs.
`splitRule`	rule to split the kd-tree. One of `"STD"`, `"MIDPT"`, `"FAIR"`, `"SL_MIDPT"`, `"SL_FAIR"` or `"SUGGEST"` (SL stands for sliding). `"SUGGEST"` uses ANNs best guess.
`approx`	use approximate nearest neighbors. All NN up to a distance of a factor of `(1 + approx) eps` may be used. Some actual NN may be omitted leading to spurious clusters and noise points. However, the algorithm will enjoy a significant speedup.

Details

The number of shared nearest neighbors is the intersection of the kNN neighborhood of two points. Note: that each point is considered to be part of its own kNN neighborhood. The range for the shared nearest neighbors is [0, k].

Javis and Patrick (1973) use the shared nearest neighbor graph for clustering. They only count shared neighbors between points that are in each other's kNN neighborhood.

Value

An object of class sNN (subclass of kNN and NN) containing a list with the following components:

`id`	a matrix with ids.
`dist`	a matrix with the distances.
`shared`	a matrix with the number of shared nearest neighbors.
`k`	number of `k` used.

Author(s)

Michael Hahsler

References

R. A. Jarvis and E. A. Patrick. 1973. Clustering Using a Similarity Measure Based on Shared Near Neighbors. IEEE Trans. Comput. 22, 11 (November 1973), 1025-1034. doi: 10.1109/T-C.1973.223640

Examples

data(iris)
x <- iris[, -5]

# finding kNN and add the number of shared nearest neighbors.
k <- 5
nn <- sNN(x, k = k)
nn

# shared nearest neighbor distribution
table(as.vector(nn$shared))

# explore neighborhood of point 10
i <- 10
nn$shared[i,]

plot(nn, x)

# apply a threshold to create a sNN graph with edges
# if more than 3 neighbors are shared.
nn_3 <- sNN(nn, kt = 3)
plot(nn_3, x)

# get an adjacency list for the shared nearest neighbor graph
adjacencylist(nn_3)

dbscan

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) and Related Algorithms

v1.1-10

GPL (>= 2)

Authors

Michael Hahsler [aut, cre, cph], Matthew Piekenbrock [aut, cph], Sunil Arya [ctb, cph], David Mount [ctb, cph]

Initial release

2022-01-14

sNN