Nested partitions from hierarchical clustering statistical validation
We develop a greedy algorithm that is fast and scalable in the detection of a nested partition extracted from a dendrogram obtained from hierarchical clustering of a multivariate series. Our algorithm provides a $p$-value for each clade observed in the hierarchical tree. The $p$-value is obtained by computing a number of bootstrap replicas of the dissimilarity matrix and by performing a statistical test on each difference between the dissimilarity associated with a given clade and the dissimilarity of the clade of its parent node. We prove the efficacy of our algorithm with a set of benchmarks generated by using a hierarchical factor model. We compare the results obtained by our algorithm with those of Pvclust. Pvclust is a widely used algorithm developed with a global approach originally motivated by phylogenetic studies. In our numerical experiments we focus on the role of multiple hypothesis test correction and on the robustness of the algorithms to inaccuracy and errors of datasets. We also apply our algorithm to a reference empirical dataset. We verify that our algorithm is much faster than Pvclust algorithm and has a better scalability both in the number of elements and in the number of records of the investigated multivariate set. Our algorithm provides a hierarchically nested partition in much shorter time than currently widely used algorithms allowing to perform a statistically validated cluster analysis detection in very large systems.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering
Community detection is a critical challenge in analysing real graphs, including social, transportation, citation, cybersecurity, and many other networks. This article proposes three new, general, hierarchical frameworks …
Community DetectionGraph Representation LearningRepresentation LearningStochastic Block ModelAnytime Hierarchical Clustering
We propose a new anytime hierarchical clustering method that iteratively transforms an arbitrary initial hierarchy on the configuration of measurements along a sequence of trees we prove for a fixed data set must termina…
Anomaly DetectionClusteringHierarchical Clustering of Asymmetric Networks
This paper considers networks where relationships between nodes are represented by directed dissimilarities. The goal is to study methods that, based on the dissimilarity structure, output hierarchical clusters, i.e., a …
ClusteringPredictive Performance Test based on the Exhaustive Nested Cross-Validation for High-dimensional data
It is crucial to assess the predictive performance of a model in order to establish its practicality and relevance in real-world scenarios, particularly for high-dimensional data analysis. Among data splitting or resampl…
Axiomatic Construction of Hierarchical Clustering in Asymmetric Networks
This paper considers networks where relationships between nodes are represented by directed dissimilarities. The goal is to study methods for the determination of hierarchical clusters, i.e., a family of nested partition…
Clustering