--- title: "Seriation Methods implemented in the R package seriation" output: rmarkdown::html_vignette: toc: true vignette: > %\VignetteIndexEntry{Seriation Methods implemented in the R package seriation} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- This document contains the seriation methods currently implemented in the R package `seriation`. The methods are organized by methods for distance matrices and data matrices. This list was created for the following version of seriation: ```{r} library("seriation") packageVersion('seriation') ``` Some additional methods need to be registered. ```{r, results="hide", warning=FALSE, message=FALSE} register_DendSer() register_optics() register_smacof() register_GA() register_tsne() register_umap() register_vegan() ``` ```{r, echo = FALSE} print_seriation_method_md <- function(x, add_link = TRUE, heading = 4L, ...) { cat("\n\n", paste0(strrep("#", heading), collapse = ""), " ", x$name, "\n", sep = "") cat(x$description, "\n\n") # cat("* kind:", x$kind, "\n") optimizes <- x$optimizes .make_anchor <- function(x) { # remove leading numbers x <- gsub("^\\d+", "", x) # lower case tolower(x) } opt_info <- attr(optimizes, "description") if(is.na(optimizes)) { optimizes <- "N/A" } else { if (add_link) { optimizes <- paste0("[", optimizes, "]", "(seriation_criteria.html#", .make_anchor(optimizes) ,")") } } if(!is.null(opt_info)) { optimizes <- paste0(optimizes, " (", opt_info, ")") } cat("* optimizes:", optimizes, "\n") cat("* randomized:", x$randomized, "\n") if (!is.na(x$registered_by)) { cat("* registered by: ", x$registered_by, "\n") } cat("* control parameters: ") .print_control(x$control, trim_values = 100) cat("\n---\n\n") invisible(x) } print_method_group <- function(title, desc, methods, l) { cat("\n\n###", title, "\n") cat(desc, "\n\n") available <- vapply(l, function(x) x$name, character(1)) methods <- intersect(methods, available) for (name in methods) print_seriation_method_md(l[[which(available == name)[1L]]]) } .print_control <- function(control, help = TRUE, trim_values = 30L) { if (length(control) < 1L) { writeLines("no parameters") } else{ contr <- lapply( control, FUN = function(x) strtrim(paste(deparse(x), collapse = ""), trim_values) ) contr <- as.data.frame(t(as.data.frame(contr))) colnames(contr) <- c("default") contr <- cbind(contr, help = "N/A") if (!is.null(attr(control, "help"))) for (i in seq(nrow(contr))) { hlp <- attr(control, "help")[[rownames(contr)[i]]] if (!is.null(hlp)) contr[["help"]][i] <- hlp } print(knitr::kable(contr)) } } ``` Seriation methods on the data `x` can be used in ```{r, eval=FALSE} seriate(x, method = "Spectral", control = NULL, rep = 1L) ``` The list below shows what seriation criterion (if any) is optimized by the method. If the method uses randomization (see randomized below), then `rep` can be used to run the algorithms several times and return the best permutation. Available control parameters can be passed on as a list using the `control` argument. ## Methods for dissimilarity data (dist) Seriation methods for dissimilarity data reorder the set of objects in the data. The methods fall into several groups based on the criteria they try to optimize, constraints (like dendrograms), and the algorithmic approach. ```{r, results='asis', echo = FALSE} l <- list_seriation_methods(kind = "dist", names_only = FALSE) available <- vapply(l, function(x) x$name, character(1)) print_method_group("Dendrogram leaf order", "These methods create a dendrogram using hierarchical clustering and then derive the seriation order from the leaf order in the dendrogram. Leaf reordering may be applied.", c("DendSer", grep("^DendSer_", available, value = TRUE), "GW", grep("^GW_", available, value = TRUE), "HC", grep("^HC_", available, value = TRUE), "OLO", grep("^OLO_", available, value = TRUE)), l) print_method_group("Dimensionality reduction", "Find a seriation order by reducing the dimensionality to 1 dimension. This is typically done by minimizing a stress measure or the reconstruction error.", c("MDS", "MDS_angle", "isoMDS", "isomap", "monoMDS", "metaMDS", "Sammon_mapping", "MDS_smacof", "tsne", "umap"), l) print_method_group("Optimization", "These methods try to optimize a seriation criterion directly, typically using a heuristic approach.", c("ARSA", "Enumerate", "BBURCG", "BBWRCG", "GA", "GSA", "SGLS", "QAP_LS", "QAP_2SUM", "QAP_BAR", "QAP_Inertia", "Spectral", "Spectral_norm", "TSP"), l) print_method_group("Other methods", "", c("Identity", "optics", "R2E", "Random", "Reverse", "SPIN_NH", "SPIN_STS", "VAT"), l) ``` ## Methods for data matrices, tables and data.frames ```{r, results='asis', echo = FALSE} l <- list_seriation_methods(kind = "matrix", names_only = FALSE) print_method_group("Seriating rows and columns simultaneously", "Row and column order influence each other.", c("BEA", "BEA_TSP", "BK_unconstrained", "CA"), l) print_method_group("Seriating rows and columns separately using dissimilarities", "", "Heatmap", l) print_method_group("Seriate rows using the data matrix", "These methods need access to the data matrix instead of dissimilarities to reorder objects (rows). The same approach can be applied to columns.", c("LLE", "PCA", "PCA_angle", "AOE", "Mean", "Identity", "Reverse", "Random"), l) ``` # References Arabie, P. and L.J. Hubert (1990): The bond energy algorithm revisited, *IEEE Transactions on Systems, Man, and Cybernetics,* **20**(1), 268--274. Bar-Joseph, Z., E. D. Demaine, D. K. Gifford, and T. Jaakkola. (2001): Fast Optimal Leaf Ordering for Hierarchical Clustering. *Bioinformatics,* **17**(1), 22--29. Barnard, S. T., A. Pothen, and H. D. Simon (1993): A Spectral Algorithm for Envelope Reduction of Sparse Matrices. *In Proceedings of the 1993 ACM/IEEE Conference on Supercomputing,* 493--502. Supercomputing '93. New York, NY, USA: ACM. Bezdek, J.C. and Hathaway, R.J. (2002): VAT: a tool for visual assessment of (cluster) tendency. *Proceedings of the 2002 International Joint Conference on Neural Networks (IJCNN '02),* Volume: 3, 2225--2230. Brower, J.C. and Kile, K.M. (1988): Sedation of an original data matrix as applied to paleoecology. *Lethaia,* **21**, 79--93. Brusco, M., Koehn, H.F., and Stahl, S. (2008): Heuristic Implementation of Dynamic Programming for Matrix Permutation Problems in Combinatorial Data Analysis. *Psychometrika,* **73**(3), 503--522. Brusco, M., and Stahl, S. (2005): *Branch-and-Bound Applications in Combinatorial Data Analysis.* New York: Springer. Chen, C. H. (2002): Generalized Association Plots: Information Visualization via Iteratively Generated Correlation Matrices. *Statistica Sinica,* **12**(1), 7--29. Ding, C. and Xiaofeng He (2004): Linearized cluster assignment via spectral ordering. *Proceedings of the Twenty-first International Conference on Machine learning (ICML '04)*. Climer, S. and Xiongnu Zhang (2006): Rearrangement Clustering: Pitfalls, Remedies, and Applications, *Journal of Machine Learning Research,* **7**(Jun), 919--943. D. Earle, C. B. Hurley (2015): Advances in dendrogram seriation for application to visualization. *Journal of Computational and Graphical Statistics,* **24**(1), 1--25. Friendly, M. (2002): Corrgrams: Exploratory Displays for Correlation Matrices. *The American Statistician,* **56**(4), 316--324. Friendly, M. (2023). *vcdExtra: 'vcd' Extensions and Additions*. R package version 0.8-5, . Gruvaeus, G. and Wainer, H. (1972): Two Additions to Hierarchical Cluster Analysis, *British Journal of Mathematical and Statistical Psychology,* **25**, 200--206. Hahsler, M. (2017): An experimental comparison of seriation methods for one-mode two-way data. *European Journal of Operational Research,* **257**, 133--143. Hahsler M, Buchta C, Hornik K (2023): *seriation: Infrastructure for Ordering Objects Using Seriation*. R package version 1.5.0. Hahsler, M., Hornik, K., and Buchta, C. (2008): Getting things in order: An introduction to ithe R package seriation. *Journal of Statistical Software,* **25**(3), 1--34. Hubert, Lawrence, and James Schultz (1976): Quadratic Assignment as a General Data Analysis Strategy. *British Journal of Mathematical and Statistical Psychology,* **29**(2). Blackwell Publishing Ltd. 190--241. Hurley, Catherine B. (2004): Clustering Visualizations of Multidimensional Data. *Journal of Computational and Graphical Statistics,* **13**(4), 788--806. Kruskal, J.B. (1964). Nonmetric multidimensional scaling: a numerical method. *Psychometrika,* **29**, 115--129. Lenstra, J.K (1974): Clustering a Data Array and the Traveling-Salesman Problem, *Operations Research,* **22**(2) 413--414. Mair P., De Leeuw J. (2015). Unidimensional scaling. In *Wiley StatsRef: Statistics Reference Online,* Wiley, New York. McCormick, W.T., P.J. Schweitzer and T.W. White (1972): Problem decomposition and data reorganization by a clustering technique, *Operations Research,* **20**(5), 993--1009. McInnes, L and Healy, J, UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction, ArXiv e-prints 1802.03426, 2018. Sammon, J. W. (1969) A non-linear mapping for data structure analysis. *IEEE Trans. Comput.*, **C-18** 401--409. Tenenbaum, J.B., de Silva, V. & Langford, J.C. (2000) A global network framework for nonlinear dimensionality reduction. *Science* **290**, 2319-2323. Tsafrir, D., Tsafrir, I., Ein-Dor, L., Zuk, O., Notterman, D.A. and Domany, E. (2005): Sorting points into neighborhoods (SPIN): data analysis and visualization by ordering distance matrices, *Bioinformatics,* **21**(10) 2301--8. van der Maaten, L.J.P.; Hinton, G.E. (Nov 2008). Visualizing Data Using t-SNE. *Journal of Machine Learning Research*. **9**: 2579--2605.