How to cite this WIREs title:
WIREs Comp Stat

Level set tree methods

Advanced Review

Jussi Klemelä

Published Online: May 31 2018

DOI: 10.1002/wics.1436

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Level set trees provide a tool for analyzing multivariate functions. Level set trees are particularly efficient in visualizing and presenting properties related to local maxima and local minima of functions. Level set trees can help statistical inference related to estimating probability density functions and regression functions, and they can be used in cluster analysis and function optimization, among other things. Level set trees open a new way to look at multivariate functions, which makes the detection and analysis of multivariate phenomena feasible, going beyond one‐ and two‐dimensional analysis. This article is categorized under: Statistical and Graphical Methods of Data Analysis > Analysis of High Dimensional Data Statistical and Graphical Methods of Data Analysis > Statistical Graphics and Visualization Statistical and Graphical Methods of Data Analysis > Nonparametric Methods

(a) A perspective plot; (b) a contour plot; (c) a tree plot; (d) a plot of a volume function; (e) a barycenter plot of the first coordinate; (f) a barycenter plot of the second coordinate

[ Normal View | Magnified View ]

(a) A volume function with two levels to determine clusters; (b) a scatter plot with the corresponding three clusters

[ Normal View | Magnified View ]

(a) A volume function with the level to determine clusters; (b) a scatter plot with the corresponding two clusters; (c) a volume function with a higher level to determine clusters; (d) a scatter plot with the corresponding three clusters

[ Normal View | Magnified View ]

(a) A scatter plot of points, whose density is estimated in Figure ; (b) a colored scatter plot which groups those observations together, which are in the same branch of the level set tree

[ Normal View | Magnified View ]

(a) A tree plot; (b) a plot of a volume function; (c) a plot of the upper part of the volume function; (d) a barycenter plot of the first coordinate; (e) a barycenter plot of the second coordinate; (f) a barycenter plot of the third coordinate

[ Normal View | Magnified View ]

Contour plots of (a) projection ; (b) slice (x₁, x₂) ↦ f(x₁, x₂, 0); (c) projection ; (d) slice (x₁, x₃) ↦ f(x₁, 0, x₃); (e) projection ; (f) slice (x₂, x₃) ↦ f(0, x₂, x₃)

[ Normal View | Magnified View ]

References

Aaron,, C., & Bodart,, O. (2016). Local convex hull support and boundary estimation. Journal of Multivariate Analysis, 147, 82–101.
Azzallini,, A., & Torelli,, N. (2007). Clustering via nonparametric density estimation. Statistics and Computing, 17, 71–80.
Baillo,, A. (2003). Total error in a plug‐in estimator of level sets. Statistics %26 Probability Letters, 65, 411–417.
Baíllo,, A., Cuesta‐Albertos,, J. A., & Cuevas,, A. (2001). Convergence rates in nonparametric estimation of level sets. Statistics %26 Probability Letters, 53, 27–35.
Baíllo,, A., Cuevas,, A., & Justel,, A. (2000). Set estimation and nonparametric detection. Canadian Journal of Statistics, 28, 765–782.
Biau,, G., Cadre,, B., & Pelletier,, B. (2007). A graph‐based estimator of the number of clusters. ESAIM: Probability and Statistics, 11, 272–280.
Bugni,, F. (2010). Bootstrap inference in partially identified models defined by moment inequalities: Coverage of the identified set. Econometrica, 76, 735–753.
Burman,, P., & Polonik,, W. (2009). Multivariate mode hunting: Data analytic tools with measures of significance. Journal of Multivariate Analysis, 100, 1198–1218.
Cadre,, B. (2006). Kernel estimation of density level sets. Journal of Multivariate Analysis, 97(4), 999–1023.
Carlsson,, G. (2009). Topology and data. Bulletin of the American Mathematical Society, 46(2), 255–308.
Carr,, H., Snoeyink,, J., & Axen,, U. (2003). Computing contour trees in any dimension. Computational Geometry: Theory and Applications, 24(2), 75–94.
Chacón,, J. E. (2015). A population background for nonparametric density‐based clustering. Statistical Science, 30(4), 518–532.
Chaudhuri,, K., & Dasgupta,, S. (2010). Rates of convergence for the cluster tree. In J. D. Lafferty,, C. K. I. Williams,, J. Shawe‐Taylor,, R. S. Zemel,, & A. Culotta, (Eds.), Advances in neural information processing systems 23 (pp. 343–351). Vancouver, BC: Curran Associates.
Chernozhukov,, V., Hong,, H., & Tamer,, E. (2007). Estimation and confidence regions for parameter sets in econometric models. Econometrica, 75, 1243–1284.
Cuevas,, A., Febreiro,, M., & Fraiman,, R. (2000). Estimating the number of clusters. Canadian Journal of Statistics, 28, 367–382.
Cuevas,, A., Febreiro,, M., & Fraiman,, R. (2001). Cluster analysis: A further approach based on density estimation. Computational Statistics and Data Analysis, 36, 441–459.
Cuevas,, A., González‐Manteiga,, W., & Rodriguez‐Casal,, A. (2006). Plug‐in estimation of general level sets. Australian %26 New Zealand Journal of Statistics, 48, 7–19.
Cuevas,, A., & Rodriguez‐Casal,, A. (2004). On boundary estimation. Advances in Applied Probability, 36(2), 340–354.
Desforges,, M. J., Jacob,, P. J., & Cooper,, J. E. (1998). Application of probability density estimation to the detection of abnormal conditions in engineering. Proceedings of the Institute Mechanical Engineers, 212, 687–703.
Devroye,, L., & Wise,, G. L. (1980). Detection of abnormal behavior via nonparametric estimation of the support. SIAM Journal on Applied Mathematics, 38, 480–488.
Duong,, T., Cowling,, A., Koch,, I., & Wand,, M. P. (2008). Feature significance for multivariate kernel density estimation. Computational Statistics and Data Analysis, 52(9), 4225–4242.
Duong,, T., Koch,, I., & Wand,, M. P. (2009). Highest density difference region estimation with application to flow cytometry data. Biometrical Journal, 51, 504–521.
Edelsbrunner,, H., Letscher,, D., & Zomorodian,, A. (2000). Topological persistence and simplification. In Proceedings of 41st annual IEEE symposium on foundations of computer science (pp. 454–463). Washington, DC: IEEE Computer Society.
Fomenko,, A. T., & Kunii,, T. L. (Eds.). (1997). Topological modeling for visualization. Berlin: Springer.
Fraley,, C., & Raftery,, A. E. (2002). Model‐based clustering, discriminant analysis and density estimation. Journal of the American Statistical Association, 97, 611–631.
Gorban,, A. N. (2013). Thermodynamic tree: The space of admissible paths. SIAM Journal on Applied Dynamical Systems, 12(1), 246–278.
Guillemin,, V., & Pollack,, A. (1974). Differential topology. Englewood Cliffs, NJ: Prentice‐Hall.
Hartigan,, J. A. (1975). Clustering algorithms. New York: Wiley.
Hartigan,, J. A. (1987). Estimation of a convex density cluster in two dimensions. Journal of the American Statistical Association, 82, 267–270.
Holmström,, L., Karttunen,, K., & Klemelä,, J. (2017). Estimation of level set trees using adaptive partitions. Computational Statistics, 32, 1139–1163.
Indyk,, P. (2004). Nearest neighbors in high‐dimensional spaces. In J. E. Goodman, & J. O`Rourke, (Eds.), Handbook of discrete and computational geometry (pp. 877–892). Boca Raton, FL: Chapman %26 Hall/CRC.
Jang,, W. (2006). Nonparametric density estimation and clustering in astronomical sky survey. Computational Statistics and Data Analysis, 50, 760–774.
Karttunen,, K., Holmström,, L., & Klemelä,, J. (2014). Level set trees with enhanced marginal density visualization: Application to flow cytometry. Proceedings 5th international conference on information visualization theory and applications. Lisbon, Portugal, 210–217.
Kent,, B. P., Rinaldo,, A., & Timothy,, V. (2013). DeBaCl: A python package for interactive DEnsity‐BAsed CLustering. Technical report. arXiv:1307.8136.
Klemelä,, J. (2004a). Complexity penalized support estimation. Journal of Multivariate Analysis, 88, 274–297.
Klemelä,, J. (2004b). Visualization of multivariate density estimates with level set trees. Journal of Computational and Graphical Statistics, 13(3), 599–620.
Klemelä,, J. (2005). Algorithms for the manipulation of level sets of nonparametric density estimates. Computational Statistics, 20, 349–368.
Klemelä,, J. (2006). Visualization of multivariate density estimates with shape trees. Journal of Computational and Graphical Statistics, 15(2), 372–397.
Klemelä,, J. (2009). Smoothing of multivariate data: Density estimation and visualization. New York: Wiley.
Korostelev,, A. P., & Tsybakov,, A. B. (1993). Minimax theory of image reconstruction. In Lecture notes in statistics (Vol. 82). Berlin: Springer.
Kpotufe,, S., & von Luxburg,, U. (2011). Pruning nearest neighbor cluster trees. In Proceedings of the 28th international conference on machine learning (Vol. 105, pp. 225–232). Madison, WI: International Machine Learning Society.
Kriegel,, H.‐P., Kröger,, P., Sander,, J., & Zimek,, A. (2011). Density‐based clustering. WIREs Data Mining and Knowledge Discovery, 1, 231–240.
Kunii,, T. L., & Shinagawa,, Y. (Eds.). (1992). Modern geometric computing for visualization. Berlin: Springer.
Maier,, M., Hein,, M., & von Luxburg,, U. (2009). Optimal construction of k‐nearest‐neighbor graphs for identifying noisy clusters. Theoretical Computer Science, 410(19), 1749–1764.
Mammen,, E., & Polonik,, W. (2013). Confidence regions for level sets. Journal of Multivariate Analysis, 122, 202–214.
Mammen,, E., & Tsybakov,, A. B. (1995). Asymptotical minimax recovery of sets with smooth boundaries. Annals of Statistics, 23, 502–524.
Mason,, D., & Polonik,, W. (2009). Asymptotic normality of plug‐in level set estimates. Annals of Applied Probability, 19, 1108–1142.
Matsumoto,, Y. (2000). An introduction to Morse theory. In Translations of mathematical monographs (Vol. 208). Providence, RI: AMS Originally published 1997 (in Japanese).
McMullen,, P. (1970). The maximum numbers of faces of a convex polytope. Mathematika, 17, 179–184.
Menardi,, G., & Azzalini,, A. (2014). An advacement in clustering via nonparametric density estimation. Statistics and Computing, 24, 753–767.
Milnor,, J. (1963). Morse theory. Princeton, NJ: Princeton University Press.
Müller,, D. W., & Sawitzki,, G. (1991). Excess mass estimates and tests of multimodality. Journal of the American Statistical Association, 86, 738–746.
Naumann,, U., Luta,, G., & Wand,, M. P. (2010). The curvHDR method for gating flow cytometry samples. BMC Bioinformatics, 11, 44.
Nocedal,, J., & Wright,, S. J. (1999). Numerical optimization. Berlin: Springer.
Nolan,, D. (1991). The excess‐mass ellipsoid. Journal of Multivariate Analysis, 39, 348–371.
Ooi,, H. (2002). Density visualization and mode hunting using trees. Journal of Computational and Graphical Statistics, 11, 328–347.
Osher,, S. J., & Fedkiw,, R. P. (2002). Level set methods and dynamic implicit surfaces. Berlin: Springer.
Polonik,, W. (1995). Measuring mass concentration and estimating density contour clusters—An excess mass approach. Annals of Statistics, 23, 855–881.
Reeb,, G. (1946). Sur les points singuliers d`une forme de pfaff completement integrable ou d`une fonction numerique. Comptes rendus de l`Académie des Sciences, 222, 847–849.
Rigollet,, P., & Vert,, R. (2009). Optimal rates for plug‐in estimators of density level sets. Bernoulli, 15, 1154–1178.
Rinaldo,, A., & Wasserman,, L. (2010). Generalized density clustering. Annals of Statistics, 38, 2678–2722.
Sethian,, J. A. (1996). Level set methods: Evolving interfaces in geometry, fluid mechanics, computer vision, and materials science. Cambridge: Cambridge University Press.
Singh,, G., Memoli,, F., & Carlsson,, G. (2007). Topological methods for the analysis of high dimensional data sets and 3D object recognition. In M. Botsch,, R. Pajarola,, B. Chen,, & M. Zwicker, (Eds.), Symposium on point based graphics (pp. 91–100). Prague: Eurographics Association.
Singh,, A., Scott,, C., & Nowak,, R. (2009). Adaptive Hausdorff estimation of density level sets. Annals of Statistics, 37, 2760–2782.
Steinwart,, I. (2015). Fully adaptive density‐based clustering. Annals of Statistics, 43, 2132–2167.
Stuetzle,, W. (2003). Estimating the cluster tree of a density by analyzing the minimal spanning tree of a sample. Journal of Classification, 20(5), 25–47.
Stuetzle,, W., & Nugent,, R. (2010). A generalized single linkage method for estimating the cluster tree of a density. Journal of Computational and Graphical Statistics, 19, 397–418.
Tarjan,, R. E. (1972). Depth‐first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160.
Tarjan,, R. E. (1976). Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22, 215–225.
Tsybakov,, A. B. (1997). On nonparametric estimation of density level sets. Annals of Statistics, 25, 948–969.
Walther,, G. (1997). Granulometric smoothing. Annals of Statistics, 25, 2273–2299.
Walther,, G., Zimmerman,, N., Moore,, W., Parks,, D., Meehan,, S., Belitskaya,, I., … Herzenberg,, L. (2009). Automatic clustering of flow cytometry data with density‐based merging. Advances in Bioinformatics, 2009, 686–759.
Weber,, G., Bremer,, P.‐T., & Pascucci,, V. (2007). Topological landscapes: A terrain metaphor for scientific data. IEEE Transactions on Visualization Computer Graphics, 13(6), 1416–1423.
Willett,, R. M., & Nowak,, R. D. (2005). Level set estimation in medical imaging. Proceedings of IEEE Statistical Signal Processing, 5, 1089–1092.
Wishart,, D. (1969). Mode analysis: A generalization of nearest neighbor which reduces chaining effects. In A. J. Cole, (Ed.), Numerical taxonomy (pp. 282–311). New York: Academic Press.
Zhou,, Q., & Wong,, W. H. (2008). Bayesian inference of DNA sequence segmentation. Annals of Applied Statistics, 2(4), 1307–1331.
Zomorodian,, A. (2012). Topological data analysis. In A. Zomorodian, (Ed.), Advances in applied and computational topology (Vol. 70, pp. 1–40). Providence: American Mathematical Society.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts