Tree Index evaluates cluster quality by creating decision trees from data.
problem Evaluating the quality of cluster results from various techniques.
method Tree Index creates a decision tree from clustered data, combining entropy and depth of leaves.
result Tree Index discriminates between sensible and non-sensible clusters on brain dataset.
The paper connects two clustering methods by showing gradient ascent flow can move up the cluster tree.
problem Establishing a strong correspondence between clustering methods.
method Moving up the cluster tree by following the gradient ascent flow.
result Gradient ascent flow can be used to move up the cluster tree.
A cluster tree provides a highly-interpretable summary of a density function by representing the hierarchy of its high-density clusters. It is estimated using the empirical tree, which is the cluster tree constructed from a density estimator. This paper addresses the basic question of quantifying our uncertainty by ass…
Kauri is a novel unsupervised binary tree for clustering that outperforms existing methods.
problem Learning a tree end-to-end for clustering without labels is an open challenge.
method Greedy maximization of the kernel KMeans objective without centroids.
result Kauri often outperforms existing unsupervised clustering methods, especially with non-linear kernels.
Locally adaptive clustering for tree delineation.
problem Tree delineation from distance data.
method Locally adaptive hierarchical cluster termination.
result Multi-scale alternative to conventional termination criteria.
A new k-means algorithm using cover trees accelerates clustering.
problem Efficiently clustering large datasets with k-means.
method Combining cover trees with upper and lower bounds.
result Significantly reduces distance computations and improves clustering performance.
A new hierarchical clustering method selects representative points from sub-minimum-spanning-trees.
problem Selecting representative points for hierarchical clustering to improve robustness and reliability.
method Identify representative points using reciprocal nearest data points in sub-minimum-spanning-trees.
result The proposed algorithm outperforms other methods in accuracy and efficiency.
For a density f on Rd, a {\it high-density cluster} is any connected component of {x:f(x)≥λ}, for some λ>0. The set of all high-density clusters forms a hierarchy called the {\it cluster tree} of f. We present two procedures for estimating the cluster tree given samples from f. The first…
New clustering method recovers hidden tree structure from data.
problem Recovering hidden hierarchical structure in data.
method Maximum average dot product for merging clusters in hierarchical clustering.
result The algorithm produces a tree that accurately represents the underlying generative hierarchical structure.
Improves clustering interpretability with decision trees.
problem Hard-to-explain cluster assignments in clustering algorithms.
method Decision tree-based clustering with k-means and k-medians objectives. result An efficient algorithm producing explainable clusters with provable guarantees.
ExKMC improves explainable k-means clustering by balancing accuracy and simplicity.
problem Limited explainable methods for unsupervised learning.
method Develops ExKMC, a new algorithm that uses a decision tree with k′ leaves to explain k-means clustering, trading explainability for accuracy. result ExKMC produces a low-cost clustering that outperforms existing methods.
Many modern clustering methods scale well to a large number of data items, N, but not to a large number of clusters, K. This paper introduces PERCH, a new non-greedy algorithm for online hierarchical clustering that scales to both massive N and K--a problem setting we term extreme clustering. Our algorithm efficiently …
This paper introduces a new method to cluster qualitative attribute data using tree structures.
problem Clustering qualitative attribute data, especially when values are not in Euclidean space.
method Developed a joint learning mechanism to iteratively learn trees representing qualitative values' order relationships.
result The joint learning mechanism successfully clusters qualitative attribute data, yielding accurate results.
Improved BIRCH clustering method to avoid numeric issues.
problem Numeric instability in BIRCH clustering.
method Introduced a new cluster feature to replace the sum of squares, avoiding catastrophic cancellation.
result The new method is more numerically stable and efficient.
New method embeds phylogenetic trees for clustering, recovering evolutionary relationships.
problem Lack of a meaningful way to embed phylogenetic trees into a vector space.
method Split-weight embedding to fit clustering algorithms to phylogenetic trees.
result Split-weight embedding recovers meaningful evolutionary relationships in simulated and real data.
Proposes a hierarchical clustering method for positive and negative dissimilarities.
problem Clustering dissimilarities, especially positive and negative.
method Hierarchical correlation clustering followed by tree preserving embedding.
result Performance on various datasets.
Interactive steering improves hierarchical clustering for diverse user needs.
problem Existing hierarchical clustering methods fail to meet diverse user needs.
method Knowledge-driven and data-driven constraints, interactive steering through a visual interface.
result Facilitates the building of customized clustering trees efficiently and effectively.
A new classification method based on Minimum Spanning Trees
problem Improving classification in supervised learning
method Proposing a classification algorithm based on Minimum Spanning Trees
result The proposed method is effective and computationally efficient
Tree-SNE combines t-SNE and hierarchical clustering for data visualization.
problem Data visualization and clustering in complex datasets.
method Stacked one-dimensional t-SNE embeddings and alpha-clustering.
result Effective hierarchical clustering and visualization of various datasets.
Nowadays, data are generated massively and rapidly from scientific fields as bioinformatics, neuroscience and astronomy to business and engineering fields. Cluster analysis, as one of the major data analysis tools, is therefore more significant than ever. We propose in this work an effective Semi-supervised Divisive Cl…
Hierarchical structure is ubiquitous in data across many domains. There are many hierarchical clustering methods, frequently used by domain experts, which strive to discover this structure. However, most of these methods limit discoverable hierarchies to those with binary branching structure. This limitation, while com…
A new tree-based model for multivariate responses interprets piecewise linear regimes.
problem Recovering piecewise multivariate linear regimes in complex data.
method Twoblock clustering trees with coskewness-based dimension reduction.
result Recovery of piecewise linear regimes in data.
The level set tree approach of Hartigan (1975) provides a probabilistically based and highly interpretable encoding of the clustering behavior of a dataset. By representing the hierarchy of data modes as a dendrogram of the level sets of a density estimator, this approach offers many advantages for exploratory analysis…
LILI clustering reduces bias in causal inference by grouping similar counterfactual outcomes.
problem Bias in causal inference from causal forest methods.
method LILI clustering algorithm integrates causal trees through leaf similarity.
result LILI clustering reduces bias and improves prediction accuracy for ATE.
We introduce block-tree graphs as a framework for deriving efficient algorithms on graphical models. We define block-tree graphs as a tree-structured graph where each node is a cluster of nodes such that the clusters in the graph are disjoint. This differs from junction-trees, where two clusters connected by an edge al…
Lumbermark clusters data robustly, slicing limbs of mutual reachability trees.
problem Detecting clusters of varying sizes, densities, and shapes in datasets.
method Iteratively chops limbs of a mutual reachability minimum spanning tree.
result Lumbermark produces partitions with user-specified sizes.
TD-GEN generates graphs using tree decomposition, improving efficiency and performance.
problem Efficiently generating graphs with statistical properties.
method Tree decomposition, permutation invariant tree generation, incremental graph generation.
result Improved graph generation efficiency and performance.
We studied the topology of correlation networks among 34 major currencies using the concept of a minimal spanning tree and hierarchical tree for the full years of 2007-2008 when major economic turbulence occurred. We used the USD (US Dollar) and the TL (Turkish Lira) as numeraires in which the USD was the major currenc…
A recently proposed clustering method, called the Nearest Descent (ND), can organize the whole dataset into a sparsely connected graph, called the In-tree. This ND-based Intree structure proves able to reveal the clustering structure underlying the dataset, except one imperfect place, that is, there are some undesired …
A new method for hierarchical clustering using continuous embeddings and optimization.
problem Hierarchical clustering with provable quality guarantees.
method Continuous relaxation of discrete optimization problem using hyperbolic embeddings and decoding.
result Continuous relaxation yields a discrete tree with (1 + epsilon)-factor approximation for optimal tree.
A new clustering algorithm for functional data using binary trees.
problem Clustering multivariate functional data with measurement errors.
method Recursive binary tree splitting for data clustering.
result Good performance in various complex settings, including vehicle trajectories.
We propose a new outline for adaptive dictionary learning methods for sparse encoding based on a hierarchical clustering of the training data. Through recursive application of a clustering method, the data is organized into a binary partition tree representing a multiscale structure. The dictionary atoms are defined ad…
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 terminate in a chain of nested partitions that satisfies a natural homogeneity requirement. Each recursive …
A new method, tree-SNE, solves the scale problem in t-SNE.
problem Clustering and visualizing high-dimensional data, especially MNIST digits.
method Revisits t-SNE idea to create a 2+1 dimensional embedding with a scale parameter.
result The optimal embedding depends continuously on the scale parameter for all initial conditions.
Defines hierarchical clustering axioms for various densities.
problem Defining hierarchical clustering for different types of densities.
method An axiomatic approach to piecewise constant densities, then extending to general densities.
result Our axiomatic definition results in Hartigan's cluster tree under certain conditions.
Nearest neighbor (k-NN) graphs are widely used in machine learning and data mining applications, and our aim is to better understand what they reveal about the cluster structure of the unknown underlying distribution of points. Moreover, is it possible to identify spurious structures that might arise due to sampling va…
nTreeClus clusters categorical sequences using tree-based learners and k-mers.
problem Challenges in clustering categorical and sequential data.
method nTreeClus uses Tree-based Learners, k-mers, and autoregressive models for categorical time series.
result nTreeClus outperformed baseline methods in various validation metrics.
New framework estimates staged tree models using hierarchical clustering on the probability simplex.
problem Estimating staged tree models with context-specific dependencies.
method Hierarchical clustering on the probability simplex, using simplex-based divergences and linkage methods.
result Total Variation divergence with Ward.D2 linkage produces staged trees with better model fit, structure recovery, and computational efficiency.
Proposes oblique predictive clustering trees for faster, more efficient learning.
problem Learning time scales poorly with output space dimensionality and cannot exploit data sparsity.
method Design and implement oblique splits using linear combinations of features.
result Achieves performance on-par with state-of-the-art methods and is orders of magnitude faster.
Hierarchical clustering is a popular method for analyzing data which associates a tree to a dataset. Hartigan consistency has been used extensively as a framework to analyze such clustering algorithms from a statistical point of view. Still, as we show in the paper, a tree which is Hartigan consistent with a given dens…
C-FAR automates clustering assessment for neural tracking.
problem Manual assessment of clusters by humans is slow and impractical for large datasets.
method C-FAR uses automated feedback queries to select optimal clustering from multiple algorithms.
result C-FAR produces near-perfect clustering on simulated neural data.
A new clustering algorithm reduces density peaks clustering's computational complexity.
problem High computational complexity of density peaks clustering.
method Sparse distance matrix, sparse search, K-d tree, second-order difference method.
result Reduced computational complexity from O(n2K) to O(n(n1−1/K+k)). We study in this paper a variant of Wasserstein barycenter problem, which we refer to as tree-Wasserstein barycenter, by leveraging a specific class of ground metrics, namely tree metrics, for Wasserstein distance. Drawing on the tree structure, we propose an efficient algorithmic approach to solve the tree-Wasserstein…
New A* algorithm improves hierarchical clustering quality.
problem Improving hierarchical clustering quality in large search spaces.
method Combining A* search with a trellis data structure.
result Achieves higher quality results than baselines in particle physics and other benchmarks.
Agglomerative hierarchical clustering can be implemented with several strategies that differ in the way elements of a collection are grouped together to build a hierarchy of clusters. Here we introduce versatile linkage, a new infinite system of agglomerative hierarchical clustering strategies based on generalized mean…
Paper addresses limitations of traditional hierarchical clustering methods.
problem Traditional hierarchical clustering methods face limitations in binary trees and ultrametrics.
method Introduces the notion of a valid hierarchy and a two-step algorithm to construct a binary tree and prune it to enforce validity.
result Proposes a method to recover the finest valid hierarchy, which is not constrained to binary structures.
State-of-the-art clustering algorithms use heuristics to partition the feature space and provide little insight into the rationale for cluster membership, limiting their interpretability. In healthcare applications, the latter poses a barrier to the adoption of these methods since medical researchers are required to pr…
MSTs provide a fast and meaningful clustering method in low-dimensional data.
problem Quantifying the effectiveness of MSTs in low-dimensional clustering tasks.
method Identifying upper bounds for MST performance, reviewing and extending existing MST-based partitioning schemes.
result MST methods can be very competitive, often outperforming traditional clustering algorithms.