We study constrained clustering, where constraints guide the clustering process. In existing works, two categories of constraints have been widely explored, namely pairwise and cardinality constraints. Pairwise constraints enforce the cluster labels of two instances to be the same (must-link constraints) or different (…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Cluster constraints”
Clustering is inherently ill-posed: there often exist multiple valid clusterings of a single dataset, and without any additional information a clustering system has no way of knowing which clustering it should produce. This motivates the use of constraints in clustering, as they allow users to communicate their interes…
Proposes a constraint for deep clustering to handle both simple and complex topologies.
problem Limited prior knowledge for deep clustering methods to perform well on complex topologies.
method Introduces a constraint using symmetric InfoNCE to enhance deep clustering performance.
result The constraint improves deep clustering methods' performance on both simple and complex topologies.
Semi-supervised clustering methods incorporate a limited amount of supervision into the clustering process. Typically, this supervision is provided by the user in the form of pairwise constraints. Existing methods use such constraints in one of the following ways: they adapt their clustering procedure, their similarity…
New algorithm clusters data and learns kernels without relaxing constraints.
problem Learning kernels or distance metrics from pairwise constraints without losing generalization.
method Joint clustering and kernel learning without relaxing constraints.
result Outperforms existing approaches on diverse datasets.
Algorithm identifies intended fairness constraints from expert demonstrations for fair clustering.
problem Fair clustering challenges due to incomplete fairness constraints.
method Algorithm identifies fairness metric from expert demonstrations and generates clusters.
result Algorithm identifies and generates fair clusters from limited expert demonstrations.
Paper shows affine constraint is unnecessary for high-dimensional data.
problem The necessity of an affine constraint in affine subspace clustering.
method Theoretical and empirical analysis of conditions for correctness of affine subspace clustering methods.
result Affine constraint has negligible effect on clustering performance for high-dimensional data.
Constrained clustering has been well-studied for algorithms such as -means and hierarchical clustering. However, how to satisfy many constraints in these algorithmic settings has been shown to be intractable. One alternative to encode many constraints is to use spectral clustering, which remains a developing area. I…
On consistency of constrained spectral clustering under representation-aware stochastic block modelstat.ML
New method finds balanced clusters in graphs using auxiliary information.
problem Finding balanced clusters in graphs with population-level constraints.
method Proposes individual-level balancing constraint and develops spectral clustering algorithms.
result Establishes first statistical consistency result for constrained spectral clustering.
The paper tackles fair correlation clustering with new algorithms and analysis.
problem Fair variants of correlation clustering under various constraints.
method Introducing a novel combinatorial optimization problem for fairlet decomposition.
result Approximation algorithms for fair correlation clustering under multiple fairness constraints.
An important form of prior information in clustering comes in form of cannot-link and must-link constraints. We present a generalization of the popular spectral clustering technique which integrates such constraints. Motivated by the recently proposed -spectral clustering for the unconstrained problem, our method is…
Algorithm tackles clustered contextual bandits with resource constraints.
problem Maximizing reward while respecting resource limits in unknown cluster contexts.
method Combines econometrics and bandit constraints techniques for sublinear regret.
result Achieves sublinear regret without needing all arm information.
S3C2 uses Siamese networks for semi-supervised clustering with pairwise constraints.
problem Semi-supervised clustering with pairwise constraints.
method S3C2 decomposes SSC into two classification tasks: first, using Siamese networks to label unlabeled pairs; second, using the labeled dataset for clustering.
result S3C2 outperforms existing SSC methods on various datasets.
We examine overlapping clustering schemes with functorial constraints, in the spirit of Carlsson--Memoli. This avoids issues arising from the chaining required by partition-based methods. Our principal result shows that any clustering functor is naturally constrained to refine single-linkage clusters and be refined by …
The paper tackles fair correlation clustering with fairness constraints.
problem Minimizing disagreements while adhering to fairness constraints for clustering.
method Two variants of fairness constraints are considered: equal distribution and relative bounds. Approximation algorithms are developed for these constraints.
result Approximation algorithms for fair correlation clustering with theoretical guarantees and empirical validation.
A novel method relaxes binary constraints to non-negative spheres for multi-matching and clustering.
problem Optimization problems over binary matrices with injectivity constraints.
method Non-negative spherical relaxation followed by conditional power iteration.
result Automatic adjustment of the continuous parameter related to universe size.
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.
FOSC-X: An extended framework for extracting multiple optimal flat clusterings from hierarchical cluster trees
problem Extracting multiple optimal flat clusterings from hierarchical cluster trees
method Dynamic programming with lower and upper feasibility bounds
result Guaranteed optimal rankings of top-M solutions with linear-time complexity
Hierarchical clustering is a popular unsupervised data analysis method. For many real-world applications, we would like to exploit prior information about the data that imposes constraints on the clustering hierarchy, and is not captured by the set of features available to the algorithm. This gives rise to the problem …
Constraint-based clustering algorithms exploit background knowledge to construct clusterings that are aligned with the interests of a particular user. This background knowledge is often obtained by allowing the clustering system to pose pairwise queries to the user: should these two elements be in the same cluster or n…
Extracting significant places or places of interest (POIs) using individuals' spatio-temporal data is of fundamental importance for human mobility analysis. Classical clustering methods have been used in prior work for detecting POIs, but without considering temporal constraints. Usually, the involved parameters for cl…
We consider the problem of metric learning subject to a set of constraints on relative-distance comparisons between the data items. Such constraints are meant to reflect side-information that is not expressed directly in the feature vectors of the data items. The relative-distance constraints used in this work are part…
This paper proposes an active metric learning method for clustering with pairwise constraints.
problem Clustering with pairwise constraints and improving clustering performance.
method Active metric learning method that queries informative instance pairs and updates the learned metric sequentially.
result The proposed method enhances clustering performance and provides a tighter error bound.
Proposes ConiVAT for better cluster assessment and clustering with background knowledge.
problem Challenges in cluster assessment and clustering with noise and bridge points.
method Uses background constraints to improve VAT/iVAT for complex datasets.
result Improves clustering accuracy and resolves issues with noise and bridge points.
A lens cluster minimizes perimeter in the plane with given area constraints.
problem Minimizing perimeter in the plane with given area constraints.
method Analyzing lens clusters consisting of circular arcs with specific geometric properties.
result Lens clusters are local minimizers of the total perimeter functional.
Efficient algorithms find solutions in a rare well-connected cluster at low constraint densities.
problem Finding solutions in the symmetric binary perceptron at low density.
method Formal proof of existence of a subdominant connected cluster and application of an efficient multiscale majority algorithm.
result An efficient algorithm can find solutions in a subdominant connected cluster with high probability.
The area of constrained clustering has been extensively explored by researchers and used by practitioners. Constrained clustering formulations exist for popular algorithms such as k-means, mixture models, and spectral clustering but have several limitations. A fundamental strength of deep learning is its flexibility, a…
Clustering is an effective technique in data mining to group a set of objects in terms of some attributes. Among various clustering approaches, the family of K-Means algorithms gains popularity due to simplicity and efficiency. However, most of existing K-Means based clustering algorithms cannot deal with outliers well…
Consistent spectral clustering with fairness constraints on representation graphs.
problem Finding balanced clusters in similarity graphs with fairness constraints.
method Developed variants of unnormalized and normalized spectral clustering for fair planted partitions.
result Consistency results for constrained spectral clustering under fair planted partitions.
FCA improves fair clustering by optimizing utility and fairness.
problem Balancing fairness and utility in clustering.
method FCA alternates between aligning data and optimizing cluster centers in an aligned space.
result FCA achieves a superior trade-off between fairness and utility.
Cluster-DAGs improve causal discovery with prior knowledge.
problem Finding cause-effect relationships from high-dimensional data.
method Cluster-DAGs as prior knowledge framework, modified constraint-based algorithms Cluster-PC and Cluster-FCI.
result Cluster-PC and Cluster-FCI outperform baselines without prior knowledge.
Proposes ConstraintMatch for semi-supervised clustering with unconstrained data.
problem Leveraging unconstrained data alongside constraints for clustering models.
method Semi-supervised context with pseudo-constraining and pseudo-labeling mechanisms.
result Demonstrates effectiveness of ConstraintMatch over baselines.
Traditional clustering methods often perform clustering with low-level indiscriminative representations and ignore relationships between patterns, resulting in slight achievements in the era of deep learning. To handle this problem, we develop Deep Discriminative Clustering (DDC) that models the clustering task by inve…
Improves clustering fairness by learning fair clusters adaptively.
problem Fairness in deep clustering, especially for protected status variables.
method Formulates group-level fairness as ILP, integrates into discriminative deep clustering, refines learning algorithm.
result Consistently outperforms fair clustering algorithms on real-world datasets.
We suggest using the max-norm as a convex surrogate constraint for clustering. We show how this yields a better exact cluster recovery guarantee than previously suggested nuclear-norm relaxation, and study the effectiveness of our method, and other related convex relaxations, compared to other clustering approaches.
Proposes a method to improve hierarchical clustering using set-level structural priors.
problem Lack of supervision for non-leaf structure in hierarchical clustering.
method Introduces set-level structural priors for semi-supervised hyperbolic hierarchical clustering.
result Improves label consistency and similarity-based tree quality over baselines.
Proposes CRG_IMSC for better clustering of multi-view data.
problem Lack of effective connectivity in clustering results.
method Directly obtains clustering result with nonnegative constraint; constructs connectivity matrix based on spectral clustering result; uses multiplicative update algorithm.
result Improves clustering performance on benchmark datasets.
AutoEmbedder clusters unlabeled data using semi-supervised DNN embedding.
problem Clustering unlabeled data efficiently and effectively.
method Semi-supervised DNN embedding system using Siamese network architecture.
result AutoEmbedder outperforms existing DNN-based semi-supervised methods.
FONT clusters patients across health systems with privacy and efficiency.
problem Challenges in multi-site cluster analysis due to data-sharing restrictions.
method Federated One-shot Ensemble Clustering (FONT) algorithm that requires only a single round of communication and exchanges only fitted model parameters and class labels.
result FONT improves consistency of patient clusters across sites compared to locally fitted clusters.
New algorithm speeds up fair clustering by 12x.
problem Achieving fair clustering in scalable algorithms.
method s-FairSC algorithm incorporating nullspace projection and Hotelling's deflation.
result s-FairSC is 12x faster and maintains fairness.
Proposes a semi-supervised K-Means algorithm for better feature selection.
problem Data clustering with unknown feature quality and limited labelled data.
method Combines unsupervised sparse clustering and semi-supervised learning with labelled data.
result The algorithm identifies informative features and maintains high performance.
We present a global optimization approach for solving the maximum a-posteriori (MAP) clustering problem under the Gaussian mixture model.Our approach can accommodate side constraints and it preserves the combinatorial structure of the MAP clustering problem by formulating it asa mixed-integer nonlinear optimization pro…
New system constructs cell-type taxonomy across multiple samples.
problem Challenges in matching clusters from different datasets.
method Combines Optimal Transport with Relaxed Marginal Constraints (OT-RMC) for simultaneous alignment of clusters across multiple samples.
result Highly accurate annotation of cell types and sample-level feature extraction.
The high dimensionality of hyperspectral images often results in the degradation of clustering performance. Due to the powerful ability of deep feature extraction and non-linear feature representation, the clustering algorithm based on deep learning has become a hot research topic in the field of hyperspectral remote s…
We introduce a tensor-based clustering method to extract sparse, low-dimensional structure from high-dimensional, multi-indexed datasets. This framework is designed to enable detection of clusters of data in the presence of structural requirements which we encode as algebraic constraints in a linear program. Our cluste…
The non-negative matrix factorization (NMF) model with an additional orthogonality constraint on one of the factor matrices, called the orthogonal NMF (ONMF), has been found a promising clustering model and can outperform the classical K-means. However, solving the ONMF model is a challenging optimization problem becau…
Study financial market graphs with Laplacian constraints.
problem Learning undirected graphs in financial markets.
method Proposes algorithms to estimate graphs accounting for financial data properties.
result Guidelines for estimating graphs in financial markets.
Algorithm maximizes user rewards under per-item budget constraints.
problem Maximizing cumulative rewards in collaborative bandits with budget constraints.
method Collaborative algorithm B-LATTICE that clusters users and collaborates across groups.
result Achieves sub-linear regret bounds matching minimax bounds.