Order preserving hierarchical agglomerative clustering
- URL: http://arxiv.org/abs/2004.12488v3
- Date: Thu, 9 Sep 2021 13:39:02 GMT
- Title: Order preserving hierarchical agglomerative clustering
- Authors: Daniel Bakkelund
- Abstract summary: We study the problem of order preserving hierarchical clustering of this kind of ordered data.
The clustering is similarity based and uses standard linkage functions, such as single- and complete linkage.
An optimal hierarchical clustering is defined as the partial dendrogram corresponding to the ultrametric closest to the original dissimilarity measure.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Partial orders and directed acyclic graphs are commonly recurring data
structures that arise naturally in numerous domains and applications and are
used to represent ordered relations between entities in the domains. Examples
are task dependencies in a project plan, transaction order in distributed
ledgers and execution sequences of tasks in computer programs, just to mention
a few. We study the problem of order preserving hierarchical clustering of this
kind of ordered data. That is, if we have $a < b$ in the original data and
denote their respective clusters by $[a]$ and $[b]$, then we shall have $[a] <
[b]$ in the produced clustering. The clustering is similarity based and uses
standard linkage functions, such as single- and complete linkage, and is an
extension of classical hierarchical clustering.
To achieve this, we define the output from running classical hierarchical
clustering on strictly ordered data to be partial dendrograms; sub-trees of
classical dendrograms with several connected components. We then construct an
embedding of partial dendrograms over a set into the family of ultrametrics
over the same set. An optimal hierarchical clustering is defined as the partial
dendrogram corresponding to the ultrametric closest to the original
dissimilarity measure, measured in the p-norm. Thus, the method is a
combination of classical hierarchical clustering and ultrametric fitting.
A reference implementation is employed for experiments on both synthetic
random data and real world data from a database of machine parts. When compared
to existing methods, the experiments show that our method excels both in
cluster quality and order preservation.
Related papers
- Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
We propose a new deep graph clustering method termed Reinforcement Graph Clustering.
In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework.
In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
arXiv Detail & Related papers (2023-08-13T18:12:28Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
We devise an efficient algorithm that recovers clusters using the observed labels.
We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
arXiv Detail & Related papers (2023-06-18T08:46:06Z) - Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure.
We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance.
We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
arXiv Detail & Related papers (2023-05-24T11:05:12Z) - Contrastive Hierarchical Clustering [8.068701201341065]
CoHiClust is a Contrastive Hierarchical Clustering model based on deep neural networks.
By employing a self-supervised learning approach, CoHiClust distills the base network into a binary tree without access to any labeled data.
arXiv Detail & Related papers (2023-03-03T07:54:19Z) - Consistency between ordering and clustering methods for graphs [0.8594140167290096]
We investigate methodological relationships between several clustering and ordering methods.
We propose a measure called the label continuity error, which generically quantifies the degree of consistency between a sequence and partition.
Based on synthetic and real-world datasets, we evaluate the extents to which an ordering method identifies a module structure.
arXiv Detail & Related papers (2022-08-27T05:55:26Z) - Tangles and Hierarchical Clustering [0.0]
We show that the central duality theorem connecting tangles with hierarchical decompositions holds if submodularity is replaced by a different property that we call maximum-submodular.
We show that the data structure that represents hierarchical clustering results, called dendograms, are equivalent to maximum-submodular connectivity functions and their tangles.
arXiv Detail & Related papers (2022-03-16T16:23:48Z) - An objective function for order preserving hierarchical clustering [0.0]
The model is an extension of the Dasgupta cost function for divisive hierarchical clustering.
Finding an optimal solution is NP-hard, so we provide a time approximation, with a relative performance guarantee of $O(log3/2n)$.
arXiv Detail & Related papers (2021-09-09T13:35:01Z) - An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
A cost function for hierarchical clustering was introduced by Dasgupta citedasgupta2016cost.
In this paper, we investigate hierarchical clustering from the emphinformation-theoretic perspective and formulate a new objective function.
arXiv Detail & Related papers (2021-08-13T03:03:56Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
Existing scalable hierarchical clustering methods sacrifice quality for speed.
We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
arXiv Detail & Related papers (2020-10-22T15:58:35Z) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
We propose a graph learning framework to preserve both the local and global structure of data.
Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure.
Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
arXiv Detail & Related papers (2020-08-31T08:41:20Z) - Clustering Binary Data by Application of Combinatorial Optimization
Heuristics [52.77024349608834]
We study clustering methods for binary data, first defining aggregation criteria that measure the compactness of clusters.
Five new and original methods are introduced, using neighborhoods and population behavior optimization metaheuristics.
From a set of 16 data tables generated by a quasi-Monte Carlo experiment, a comparison is performed for one of the aggregations using L1 dissimilarity, with hierarchical clustering, and a version of k-means: partitioning around medoids or PAM.
arXiv Detail & Related papers (2020-01-06T23:33:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.