Skip to contents

Clustering algorithms: affinity propagation, CLARANS, CURE, DIANA, CHAMELEON

Source: R/ClusterAlgorithms.R
AffinityPropagation.Rd

AffinityPropagation: Frey-Dueck message passing with exemplar refinement as in apcluster. Clarans: randomized medoid search (Philox). CureClustering: hierarchical merging on shrunken representative points. Diana: divisive analysis as cluster::diana, with the divisive coefficient. Chameleon: k-nearest-neighbour graph partitioning (spectral bisection) and merging by relative interconnectivity and closeness. Identical to the Python arm morie.fn.clusteralgo.

Usage

AffinityPropagation(
  X = NULL,
  S = NULL,
  preference = NULL,
  damping = 0.9,
  maxits = 1000L,
  convits = 100L
)

Clarans(X, k, numlocal = 2L, maxneighbor = NULL, seed = 1)

CureClustering(X, k, n_rep = 5L, alpha = 0.3)

Diana(D, k = NULL, is_distance = TRUE)

Chameleon(X, k, n_neighbors = 5L, min_size = 6L, alpha = 2)

Arguments

X

Data matrix (rows are points).

S

Similarity matrix (default negative squared distances).

preference

Diagonal preference (default median similarity).

damping

Damping factor.

maxits, convits

Maximum iterations and stable iterations to stop.

k

Number of clusters (medoids).

numlocal, maxneighbor

CLARANS restarts and neighbour budget.

seed

Philox seed.

n_rep, alpha

CURE representatives and shrink factor; for Chameleon alpha weights relative closeness.

D

Dissimilarity matrix (or data when is_distance = FALSE).

is_distance

Whether D is a dissimilarity matrix.

n_neighbors, min_size

Graph degree and phase-1 part size.

Value

List with 1-based cluster labels (numbered by first appearance).

References

Frey, B. J. and Dueck, D. (2007). Clustering by passing messages between data points. Science 315, 972-976.

Ng, R. T. and Han, J. (2002). CLARANS: a method for clustering objects for spatial data mining. IEEE Transactions on Knowledge and Data Engineering 14, 1003-1016.

Guha, S., Rastogi, R. and Shim, K. (1998). CURE: an efficient clustering algorithm for large databases. Proceedings of ACM SIGMOD, 73-84.

Kaufman, L. and Rousseeuw, P. J. (1990). Finding Groups in Data. Wiley.

Karypis, G., Han, E.-H. and Kumar, V. (1999). CHAMELEON: a hierarchical clustering algorithm using dynamic modeling. IEEE Computer 32, 68-75.

Examples

X <- rbind(c(0, 0), c(0, 1), c(1, 0), c(8, 8), c(8, 9), c(9, 8))
AffinityPropagation(X)$cluster
#> [1] 1 1 1 2 2 2
Clarans(X, 2)$cluster
#> [1] 1 1 1 2 2 2
CureClustering(X, 2)$cluster
#> [1] 1 1 1 2 2 2
Diana(as.matrix(dist(X)), 2)$cluster
#> [1] 1 1 1 2 2 2