R/spectralClustering.R

In anocva: A Non-Parametric Statistical Test to Compare Clustering Structures

#' Spectral clustering
#'
#' Unnormalized spectral clustering function. Uses Partitioning Around Medoids clustering instead of K-means.
#
#' @param W NxN similarity matrix
#' @param k Number of clusters
#'
#' @return Cluster labels
#'
#' @references
#' Von Luxburg, U (2007) A tutorial on spectral clustering. Statistics and computing 17:395–416.
#'
#' Ng A, Jordan M, Weiss Y (2002) On spectral clustering: analysis and an algorithm. In: Advances
#' in Neural Information Processing Systems. Dietterich T, Becker S, Ghahramani Z (Eds.),
#' vol. 14. MIT Press, (pp. 849–856).
#'
#' @import cluster
#'
#' @examples
#' # Install igraph if necessary
#' # install.packages('igraph')
#' # install.packages('cluster')
#'
#' library(anocva)
#'
#' set.seed(2000)
#'
#' if (requireNamespace("igraph", quietly = TRUE)) {
#'
#'   # Create a tree graph
#'   treeGraph = igraph::make_tree(80, children = 4, mode = "undirected")
#'
#'   # Visualize the tree graph
#'   plot(treeGraph, vertex.size = 10, vertex.label = NA)
#'
#'   # Get the adjacency matrix of the tree graph
#'   adj = as.matrix(igraph::get.adjacency(treeGraph))
#'
#'   # Cluster the tree graph in to four clusters
#'   cluster = spectralClustering(adj, 4)
#'
#'   # See the result clustering
#'   plot(treeGraph, vertex.size=10, vertex.color = cluster, vertex.label = NA)
#' }
#'
#' @export
#'
spectralClustering = function(W, k){
  n = ncol(W)
  S = rowSums(W)
  D = diag(S)
  L = D - W
  U = (eigen(L)$vectors)[ , ((n-k+1):n)]
  C = pam(x = U, k = k)
  return(C$clustering)
}