One of the longstanding problems in spectral graph clustering (SGC) is the so-called model order selection problem: automated selection of the correct number of clusters. This is equivalent to the problem of finding the number of connected components or communities in an undirected graph. In this paper, we propose AMOS…
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,657 papers · 148 categories
Trend · papers per month
48 results for “clustering problem”
New SMC algorithm reduces memory usage for online clustering.
problem Uncertainty in online clustering with complex distributions.
method Decomposes clustering into independent subproblems using SMC.
result Accurately and efficiently solves clustering problems.
Cluster-wise linear regression (CLR), a clustering problem intertwined with regression, is to find clusters of entities such that the overall sum of squared errors from regressions performed over these clusters is minimized, where each cluster may have different variances. We generalize the CLR problem by allowing each…
Clustering ensemble, or consensus clustering, has emerged as a powerful tool for improving both the robustness and the stability of results from individual clustering methods. Weighted clustering ensemble arises naturally from clustering ensemble. One of the arguments for weighted clustering ensemble is that elements (…
Clustering is the problem of separating a set of objects into groups (called clusters) so that objects within the same cluster are more similar to each other than to those in different clusters. Spectral clustering is a now well-known method for clustering which utilizes the spectrum of the data similarity matrix to pe…
Convex clustering solves a stable optimization problem for clustering.
problem Clustering with stable and scalable solutions.
method Solving a convex optimization problem with a single tuning parameter.
result The optimization problem has a unique global minimizer stable to inputs.
CCMM efficiently solves large-scale convex clustering problems.
problem Scalability and hierarchical structure in convex clustering.
method Majorization-minimization algorithm with cluster fusions and efficient updating.
result CCMM achieves efficient solutions for large datasets.
Subspace clustering is the problem of clustering data points into a union of low-dimensional linear/affine subspaces. It is the mathematical abstraction of many important problems in computer vision, image processing and machine learning. A line of recent work (4, 19, 24, 20) provided strong theoretical guarantee for s…
In this paper we study the problem of correlation clustering under fairness constraints. In the classic correlation clustering problem, we are given a complete graph where each edge is labeled positive or negative. The goal is to obtain a clustering of the vertices that minimizes disagreements -- the number of negative…
Exact cluster recovery with same-cluster queries for arbitrary ellipsoidal clusters.
problem Recovering clusters from same-cluster queries in arbitrary ellipsoidal clusters.
method Relaxing spherical -means assumption to arbitrary ellipsoidal clusters, designing an algorithm with logarithmic query complexity.
result Exact recovery of clusters using queries and time.
The problem of dimension reduction is of increasing importance in modern data analysis. In this paper, we consider modeling the collection of points in a high dimensional space as a union of low dimensional subspaces. In particular we propose a highly scalable sampling based algorithm that clusters the entire data via …
Probabilistic fair clustering tackles uncertain group membership.
problem Fair clustering with imperfect group membership.
method Probabilistic algorithms for metric graphs and metric membership.
result Approximation ratio guarantees for fair clustering.
Co-Clustering, the problem of simultaneously identifying clusters across multiple aspects of a data set, is a natural generalization of clustering to higher-order structured data. Recent convex formulations of bi-clustering and tensor co-clustering, which shrink estimated centroids together using a convex fusion penalt…
We study the question of fair clustering under the {\em disparate impact} doctrine, where each protected class must have approximately equal representation in every cluster. We formulate the fair clustering problem under both the -center and the -median objectives, and show that even with two protected classes th…
Transform learning improves K-means clustering for document analysis.
problem Improving K-means clustering for document analysis.
method Embedding K-means clustering loss into transform learning framework and solving jointly using ADMM.
result Improves over state-of-the-art in document clustering.
Clustering explores meaningful patterns in the non-labeled data sets. Cluster Ensemble Selection (CES) is a new approach, which can combine individual clustering results for increasing the performance of the final results. Although CES can achieve better final results in comparison with individual clustering algorithms…
Mode clustering is a nonparametric method for clustering that defines clusters using the basins of attraction of a density estimator's modes. We provide several enhancements to mode clustering: (i) a soft variant of cluster assignment, (ii) a measure of connectivity between clusters, (iii) a technique for choosing the …
MultiDendrograms is a Java-written application that computes agglomerative hierarchical clusterings of data. Starting from a distances (or weights) matrix, MultiDendrograms is able to calculate its dendrograms using the most common agglomerative hierarchical clustering methods. The application implements a variable-gro…
SimpleMKKM improves multi-kernel clustering efficiency.
problem Efficient multi-kernel clustering.
method Re-formulated minimization-maximization problem into a smooth minimization, solved with gradient descent.
result Outperforms state-of-the-art multi-kernel clustering alternatives.
Method uses NMF for clustering with partial distance measurements.
problem Proximity clustering with partial distance measurements.
method Nyström approximation with Nonnegative Matrix Factorization.
result Find nearly optimal clustering quality on synthetic and real-world data.
Data stream clustering tackles real-time data processing challenges.
problem Real-time processing of data streams with less prior information.
method Review of data stream clustering algorithms and their characteristics.
result Comparison and analysis of data stream clustering algorithms.
As the size of datasets become massive, many commonly-used clustering algorithms (for example, -means or hierarchical agglomerative clustering (HAC) require prohibitive computational cost and memory. In this paper, we propose a solution to these clustering problems by extending threshold clustering (TC) to probl…
Bagging and boosting are proved to be the best methods of building multiple classifiers in classification combination problems. In the area of "flat clustering" problems, it is also recognized that multi-clustering methods based on boosting provide clusterings of an improved quality. In this paper, we introduce a novel…
Paper proposes a new co-clustering method for overlapping clusters and outliers.
problem Real-world datasets often contain overlaps and outliers in co-clusters.
method Formulated Non-Exhaustive, Overlapping Co-Clustering problem and developed NEO-CC algorithm.
result NEO-CC algorithm effectively captures underlying co-clustering structure of real-world data.
We consider two closely related problems: planted clustering and submatrix localization. The planted clustering problem assumes that a random graph is generated based on some underlying clusters of the nodes; the task is to recover these clusters given the graph. The submatrix localization problem concerns locating hid…
Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimizationmath.OC
Plain vanilla K-means clustering has proven to be successful in practice, yet it suffers from outlier sensitivity and may produce highly unbalanced clusters. To mitigate both shortcomings, we formulate a joint outlier detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outl…
Scaling clustering algorithms to massive data sets is a challenging task. Recently, several successful approaches based on data summarization methods, such as coresets and sketches, were proposed. While these techniques provide provably good and small summaries, they are inherently problem dependent - the practitioner …
It has always been a great challenge for clustering algorithms to automatically determine the cluster numbers according to the distribution of datasets. Several approaches have been proposed to address this issue, including the recent promising work which incorporate Bayesian Nonparametrics into the -means clusterin…
Cross-manifold clustering is a hard topic and many traditional clustering methods fail because of the cross-manifold structures. In this paper, we propose a Multiple Flat Projections Clustering (MFPC) to deal with cross-manifold clustering problems. In our MFPC, the given samples are projected into multiple subspaces t…
The problem of finding groups in data (cluster analysis) has been extensively studied by researchers from the fields of Statistics and Computer Science, among others. However, despite its popularity it is widely recognized that the investigation of some theoretical aspects of clustering has been relatively sparse. One …
Paper provides a performance guarantee for spectral clustering.
problem Finding the global solution to the minimum ratio cut problem.
method Two-step spectral clustering method with a rounding step, analyzed using two-to-infinity norm perturbation bounds.
result Spectral clustering is guaranteed to output the global solution under certain conditions.
The problem of Hybrid Linear Modeling (HLM) is to model and segment data using a mixture of affine subspaces. Different strategies have been proposed to solve this problem, however, rigorous analysis justifying their performance is missing. This paper suggests the Theoretical Spectral Curvature Clustering (TSCC) algori…
Quality assessments of models in unsupervised learning and clustering verification in particular have been a long-standing problem in the machine learning research. The lack of robust and universally applicable cluster validity scores often makes the algorithm selection and hyperparameter evaluation a tough guess. In t…
Graph clustering improved using Boltzmann machine heuristics.
problem Graph clustering to form densely connected clusters.
method Two mathematical programming formulations, two variations of Boltzmann machine heuristic.
result Boltzmann machine provides superior solutions and faster computation times.
In this paper, we propose a general model for plane-based clustering. The general model contains many existing plane-based clustering methods, e.g., k-plane clustering (kPC), proximal plane clustering (PPC), twin support vector clustering (TWSVC) and its extensions. Under this general model, one may obtain an appropria…
Solves clustering contradictions by high-dimensional embedding with wide gaps.
problem Kleinberg's clustering axioms are contradictory.
method Embedding in high-dimensional space with wide gaps between clusters.
result Handles clustering contradictions by design.
We focus on solving the clustered lasso problem, which is a least squares problem with the -type penalties imposed on both the coefficients and their pairwise differences to learn the group structure of the regression parameters. Here we first reformulate the clustered lasso regularizer as a weighted ordered-la…
Selective inference controls Type I error in k-means clustering tests.
problem Inflated Type I error in classical hypothesis tests for k-means clusters.
method Selective inference approach to control Type I error.
result Proposes a computable finite-sample p-value for selective inference.
Cluster jackknife improves inference for staggered DID methods.
problem Over-rejection of CSDID in small clusters or treated clusters.
method Cluster jackknife for CSDID inference.
result Cluster jackknife greatly improves inference for CSDID.
In this paper, a similarity-driven cluster merging method is proposed for unsuper-vised fuzzy clustering. The cluster merging method is used to resolve the problem of cluster validation. Starting with an overspecified number of clusters in the data, pairs of similar clusters are merged based on the proposed similarity-…
Paper proposes a new method to improve clustering ensemble performance.
problem Improving clustering ensemble performance by refining co-association matrix.
method Low-rank tensor approximation to derive coherent-link matrix and refine co-association matrix.
result The proposed method achieves breakthrough in clustering performance compared to state-of-the-art methods.
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 computational lower bounds for clustering and related problems.
problem Statistical-computational gaps in high-dimensional clustering problems.
method Investigation of low-degree polynomials in latent space models to derive lower bounds.
result New and sharper computational lower bounds for clustering, sparse clustering, and biclustering.
We describe a probabilistic (generative) view of affinity matrices along with inference algorithms for a subclass of problems associated with data clustering. This probabilistic view is helpful in understanding different models and algorithms that are based on affinity functions OF the data. IN particular, we show how(…
Proposes a new method for clustering tasks in multi-task learning.
problem Improving performance of multiple related prediction tasks.
method Semisoft task clustering approach with a three-step algorithm.
result Validation of the proposed approach on synthetic and real-world datasets.
-means clustering is a fundamental problem in unsupervised learning. The problem concerns finding a partition of the data points into clusters such that the within-cluster variation is minimized. Despite its importance and wide applicability, a theoretical understanding of the -means problem has not been comp…
Unsupervised learning is widely recognized as one of the most important challenges facing machine learning nowa- days. However, in spite of hundreds of papers on the topic being published every year, current theoretical understanding and practical implementations of such tasks, in particular of clustering, is very rudi…
Determining the quality of the results obtained by clustering techniques is a key issue in unsupervised machine learning. Many authors have discussed the desirable features of good clustering algorithms. However, Jon Kleinberg established an impossibility theorem for clustering. As a consequence, a wealth of studies ha…