We investigate properties that intuitively ought to be satisfied by graph clustering quality functions, that is, functions that assign a score to a clustering of a graph. Graph clustering, also known as network community detection, is often performed by optimizing such a function. Two axioms tailored for graph clusteri…
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 quality”
Cluster analysis is widely used in the areas of machine learning and data mining. Fuzzy clustering is a particular method that considers that a data point can belong to more than one cluster. Fuzzy clustering helps obtain flexible clusters, as needed in such applications as text categorization. The performance of a clu…
Develops a measure for checking cluster quality using multinomial distribution.
problem Determining the true number of clusters in a sample.
method Applying multinomial distribution to distances of data members from their cluster representatives.
result Demonstrates the capability to identify if a sample has inherent clusters.
Many graph clustering quality functions suffer from a resolution limit, the inability to find small clusters in large graphs. So called resolution-limit-free quality functions do not have this limit. This property was previously introduced for hard clustering, that is, graph partitioning. We investigate the resolution-…
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…
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.
Enhances clustering quality evaluation in noisy data.
problem Reliable clustering quality assessment in noisy Gaussian mixtures.
method Feature Importance Rescaling (FIR) method.
result FIR improves correlation between cluster validity indices and ground truth.
New model clusters mixed-type data with missing values, improving air quality analysis.
problem Clustering mixed-type data with missing values and regime persistence.
method Statistical jump model incorporating regime persistence and handling missing data.
result Superior performance in inferring persistent air quality regimes compared to traditional methods.
A unified clustering approach that can estimate number of clusters and produce clustering against this number simultaneously is proposed. Average silhouette width (ASW) is a widely used standard cluster quality index. A distance based objective function that optimizes ASW for clustering is defined. The proposed algorit…
This paper speeds up SVC clustering by compressing data while preserving key properties.
problem Efficiently clustering large-scale real-world data sets.
method Spectrum-preserving data compression for fast support vector clustering.
result Achieved 100X and 115X speedups on real-world data sets while maintaining clustering quality.
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.
Multiple clustering aims at exploring alternative clusterings to organize the data into meaningful groups from different perspectives. Existing multiple clustering algorithms are designed for single-view data. We assume that the individuality and commonality of multi-view data can be leveraged to generate high-quality …
ALPCAHUS clusters data from multiple subspaces with varying noise.
problem Heteroscedastic data with varying noise levels.
method Develops a heteroscedastic PCA method for subspace clustering.
result Improves subspace clustering by accounting for sample-wise noise variances.
A clustering may be considered as fair on pre-specified sensitive attributes if the proportions of sensitive attribute groups in each cluster reflect that in the dataset. In this paper, we consider the task of fair clustering for scenarios involving multiple multi-valued or numeric sensitive attributes. We propose a fa…
Benchmarked over 70 graph clustering algorithms.
problem Lack of comprehensive performance comparison for graph clustering algorithms.
method Evaluated 70+ graph clustering programs for runtime and quality on weighted and unweighted graphs, analyzed ground truth characteristics.
result Supply a start point for engineers and viewpoint for researchers.
A faster Wasserstein k-means algorithm for histogram data reduces computation and maintains clustering quality.
problem Efficiently clustering histogram data with reduced computation time.
method Sparse simplex projection to reduce data samples, centroids, and ground cost matrix, dynamically removing lower-valued samples.
result Significant reduction in computational complexity without compromising clustering quality.
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.
New approach for fair graph clustering using semidefinite relaxation.
problem Ensuring equitable representation in network analysis.
method Semidefinite relaxation approach for NP-hard optimization problem.
result Optimal accuracy-fairness trade-off achieved.
Graph clustering remains challenging for GNNs, but a new method improves performance.
problem Graph clustering is difficult for GNNs, especially in noisy data.
method Developed Deep Modularity Networks (DMoN) inspired by modularity measure.
result DMoN produces high-quality clusters with over 40% improvement over other methods.
Although many convex relaxations of clustering have been proposed in the past decade, current formulations remain restricted to spherical Gaussian or discriminative models and are susceptible to imbalanced clusters. To address these shortcomings, we propose a new class of convex relaxations that can be flexibly applied…
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…
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…
AUC used as a measure of clustering quality in unsupervised learning.
problem Using AUC to evaluate clustering quality in unsupervised learning.
method Developed AUCC as a measure of clustering quality, derived theoretical expected values, and compared with Gamma criterion.
result AUCC has a consistent expected value under random clustering, making it a reliable measure.
We present a structural clustering algorithm for large-scale datasets of small labeled graphs, utilizing a frequent subgraph sampling strategy. A set of representatives provides an intuitive description of each cluster, supports the clustering process, and helps to interpret the clustering results. The projection-based…
This research introduces a new strategy in cluster ensemble selection by using Independency and Diversity metrics. In recent years, Diversity and Quality, which are two metrics in evaluation procedure, have been used for selecting basic clustering results in the cluster ensemble selection. Although quality can improve …
Two algorithms improve K-means clustering speed without sacrificing quality.
problem Improving clustering quality of K-means while speeding up the process.
method Divisive K-means and Parallel Two-Phase K-means.
result Achieved empirically global optimum clustering results with lower complexity.
The paper proposes a new method to evaluate LLM agent responses using ECDF clustering.
problem The standard evaluation of LLM agent responses via majority voting obscures response quality and distribution.
method The paper introduces a novel evaluation framework based on ECDF of cosine similarities and clustering of ECDFs using distances and -medoids algorithm.
result ECDF clustering reveals interpretable group structures in LLM responses, offering insights into agent settings.
We describe a new optimization scheme for finding high-quality correlation clusterings in planar graphs that uses weighted perfect matching as a subroutine. Our method provides lower-bounds on the energy of the optimal correlation clustering that are typically fast to compute and tight in practice. We demonstrate our a…
This paper tackles deep clustering evaluation challenges in high-dimensional data.
problem Evaluation of deep clustering methods is problematic due to the curse of dimensionality and variations in embedding spaces.
method Develops a theoretical framework to highlight the ineffectiveness of internal validation measures and proposes a systematic approach to applying clustering validity indices in deep learning.
result The proposed framework reduces misguidance from improper use of clustering validity indices in deep learning.
New index improves anomaly detection in correlated time series data.
problem Challenges in evaluating cluster quality for anomaly detection.
method Introduced Synchronized Anomaly Agreement Index (SAAI) to assess cluster quality.
result Maximizing SAAI improves anomaly detection accuracy by 0.23 compared to SSC and by 0.32 compared to X-Means.
Experimental evaluation is a major research methodology for investigating clustering algorithms and many other machine learning algorithms. For this purpose, a number of benchmark datasets have been widely used in the literature and their quality plays a key role on the value of the research work. However, in most of t…
Exploration strategy design is one of the challenging problems in reinforcement learning~(RL), especially when the environment contains a large state space or sparse rewards. During exploration, the agent tries to discover novel areas or high reward~(quality) areas. In most existing methods, the novelty and quality in …
Proposes DISCO, the first CVI for density-based clustering with noise.
problem Evaluation of noise assignments in density-based clustering.
method Density-connectivity and Silhouette Coefficient adaptation for noise evaluation.
result DISCO is the first CVI to explicitly assess noise assignments.
Data aggregation improves HAC for resource-constrained systems.
problem Resource constraints in embedded systems limit HAC's applicability.
method Data aggregation with BETULA algorithm reduces memory and runtime requirements.
result HAC can be applied to large datasets on resource-constrained systems.
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.
We present a method for a wine recommendation system that employs multidimensional clustering and unsupervised learning methods. Our algorithm first performs clustering on a large corpus of wine reviews. It then uses the resulting wine clusters as an approximation of the most common flavor palates, recommending a user …
Combining Multiple Clusterings via Crowd Agreement Estimation and Multi-Granularity Link Analysisstat.ML
The clustering ensemble technique aims to combine multiple clusterings into a probably better and more robust clustering and has been receiving an increasing attention in recent years. There are mainly two aspects of limitations in the existing clustering ensemble approaches. Firstly, many approaches lack the ability t…
Topology of Currencies: Persistent Homology for FX Co-movements: A Comparative Clustering Studystat.ML
TDA improves FX clustering quality over traditional methods.
problem Capturing complex currency co-movements in FX markets.
method Topological Data Analysis (TDA) compared to traditional statistical methods on monthly FX returns.
result TDA-based clustering yields more compact and well-separated clusters.
We develop a Vector Quantized Spectral Clustering (VQSC) algorithm that is a combination of Spectral Clustering (SC) and Vector Quantization (VQ) sampling for grouping Soybean genomes. The inspiration here is to use SC for its accuracy and VQ to make the algorithm computationally cheap (the complexity of SC is cubic in…
Cluster-DP improves differential privacy in randomized experiments by clustering data.
problem Reducing variance in causal effect estimation from differentially private data.
method Cluster-DP leverages a given cluster structure to improve the privacy-variance trade-off.
result Selecting higher-quality clusters decreases the variance penalty without compromising privacy guarantees.
New method reduces clustering time and improves accuracy.
problem High time and space complexity in spectral clustering.
method Approximate spectral clustering using GNG network topology.
result Equal or better clustering performance than traditional SC.
New method uses random convex polytopes to measure representation quality.
problem Measuring the quality of deep learning representations.
method Random Polytope Descriptor method based on random convex polytopes.
result Regularization in autoencoders can degrade out-of-distribution detection.
Hierarchical clustering is a widely used approach for clustering datasets at multiple levels of granularity. Despite its popularity, existing algorithms such as hierarchical agglomerative clustering (HAC) are limited to the offline setting, and thus require the entire dataset to be available. This prohibits their use o…
Condorcet's Jury Theorem has been invoked for ensemble classifiers to indicate that the combination of many classifiers can have better predictive performance than a single classifier. Such a theoretical underpinning is unknown for consensus clustering. This article extends Condorcet's Jury Theorem to the mean partitio…
In this article, the logic rule ensembles approach to supervised learning is applied to the unsupervised or semi-supervised clustering. Logic rules which were obtained by combining simple conjunctive rules are used to partition the input space and an ensemble of these rules is used to define a similarity matrix. Simila…
Motivation: With the development of droplet based systems, massive single cell transcriptome data has become available, which enables analysis of cellular and molecular processes at single cell resolution and is instrumental to understanding many biological processes. While state-of-the-art clustering methods have been…
Hierarchical graph clustering is a common technique to reveal the multi-scale structure of complex networks. We propose a novel metric for assessing the quality of a hierarchical clustering. This metric reflects the ability to reconstruct the graph from the dendrogram, which encodes the hierarchy. The optimal represent…
Spectral clustering is a widely studied problem, yet its complexity is prohibitive for dynamic graphs of even modest size. We claim that it is possible to reuse information of past cluster assignments to expedite computation. Our approach builds on a recent idea of sidestepping the main bottleneck of spectral clusterin…