Evaluation of Cluster Id Assignment Schemes with ABCDE
- URL: http://arxiv.org/abs/2409.18254v1
- Date: Thu, 26 Sep 2024 19:56:56 GMT
- Title: Evaluation of Cluster Id Assignment Schemes with ABCDE
- Authors: Stephan van Staden,
- Abstract summary: A cluster id assignment scheme labels each cluster of a clustering with a distinct id.
Semantic id stability allows the users of a clustering to refer to a concept's cluster with an id that is stable across clusterings/time.
This paper treats the problem of evaluating the relative merits of id assignment schemes.
- Score: 0.0
- License:
- Abstract: A cluster id assignment scheme labels each cluster of a clustering with a distinct id. The goal of id assignment is semantic id stability, which means that, whenever possible, a cluster for the same underlying concept as that of a historical cluster should ideally receive the same id as the historical cluster. Semantic id stability allows the users of a clustering to refer to a concept's cluster with an id that is stable across clusterings/time. This paper treats the problem of evaluating the relative merits of id assignment schemes. In particular, it considers a historical clustering with id assignments, and a new clustering with ids assigned by a baseline and an experiment. It produces metrics that characterize both the magnitude and the quality of the id assignment diffs between the baseline and the experiment. That happens by transforming the problem of cluster id assignment into a problem of cluster membership, and evaluating it with ABCDE. ABCDE is a sophisticated and scalable technique for evaluating differences in cluster membership in real-world applications, where billions of items are grouped into millions of clusters, and some items are more important than others. The paper also describes several generalizations to the basic evaluation setup for id assignment schemes. For example, it is fairly straightforward to evaluate changes that simultaneously mutate cluster memberships and cluster ids. The ideas are generously illustrated with examples.
Related papers
- Dying Clusters Is All You Need -- Deep Clustering With an Unknown Number of Clusters [5.507296054825372]
Finding meaningful groups in high-dimensional data is an important challenge in data mining.
Deep clustering methods have achieved remarkable results in these tasks.
Most of these methods require the user to specify the number of clusters in advance.
This is a major limitation since the number of clusters is typically unknown if labeled data is unavailable.
Most of these approaches estimate the number of clusters separated from the clustering process.
arXiv Detail & Related papers (2024-10-12T11:04:10Z) - ABCDE: Application-Based Cluster Diff Evals [49.1574468325115]
It aims to be practical: it allows items to have associated importance values that are application-specific, it is frugal in its use of human judgements when determining which clustering is better, and it can report metrics for arbitrary slices of items.
The approach to measuring the delta in the clustering quality is novel: instead of trying to construct an expensive ground truth up front and evaluating the each clustering with respect to that, ABCDE samples questions for judgement on the basis of the actual diffs between the clusterings.
arXiv Detail & Related papers (2024-07-31T08:29:35Z) - 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) - Oracle-guided Contrastive Clustering [28.066047266687058]
Oracle-guided Contrastive Clustering(OCC) is proposed to cluster by interactively making pairwise same-cluster" queries to oracles with distinctive demands.
To the best of our knowledge, it is the first deep framework to perform personalized clustering.
arXiv Detail & Related papers (2022-11-01T12:05:12Z) - Implicit Sample Extension for Unsupervised Person Re-Identification [97.46045935897608]
Clustering sometimes mixes different true identities together or splits the same identity into two or more sub clusters.
We propose an Implicit Sample Extension (OurWholeMethod) method to generate what we call support samples around the cluster boundaries.
Experiments demonstrate that the proposed method is effective and achieves state-of-the-art performance for unsupervised person Re-ID.
arXiv Detail & Related papers (2022-04-14T11:41:48Z) - You Never Cluster Alone [150.94921340034688]
We extend the mainstream contrastive learning paradigm to a cluster-level scheme, where all the data subjected to the same cluster contribute to a unified representation.
We define a set of categorical variables as clustering assignment confidence, which links the instance-level learning track with the cluster-level one.
By reparametrizing the assignment variables, TCC is trained end-to-end, requiring no alternating steps.
arXiv Detail & Related papers (2021-06-03T14:59:59Z) - Unsupervised Person Re-identification via Softened Similarity Learning [122.70472387837542]
Person re-identification (re-ID) is an important topic in computer vision.
This paper studies the unsupervised setting of re-ID, which does not require any labeled information.
Experiments on two image-based and video-based datasets demonstrate state-of-the-art performance.
arXiv Detail & Related papers (2020-04-07T17:16:41Z)
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.