Individual Preference Stability for Clustering

• URL: http://arxiv.org/abs/2207.03600v1
• Date: Thu, 7 Jul 2022 22:01:01 GMT
• Title: Individual Preference Stability for Clustering
• Authors: Saba Ahmadi, Pranjal Awasthi, Samir Khuller, Matth\"aus Kleindessner, Jamie Morgenstern, Pattara Sukprasert, Ali Vakilian
• Abstract summary: We propose a natural notion of individual preference (IP) stability for clustering. Our notion asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster.
• Score: 24.301650646957246
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a natural notion of individual preference (IP) stability for clustering, which asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster. Our notion can be motivated from several perspectives, including game theory and algorithmic fairness. We study several questions related to our proposed notion. We first show that deciding whether a given data set allows for an IP-stable clustering in general is NP-hard. As a result, we explore the design of efficient algorithms for finding IP-stable clusterings in some restricted metric spaces. We present a polytime algorithm to find a clustering satisfying exact IP-stability on the real line, and an efficient algorithm to find an IP-stable 2-clustering for a tree metric. We also consider relaxing the stability constraint, i.e., every data point should not be too far from its own cluster compared to any other cluster. For this case, we provide polytime algorithms with different guarantees. We evaluate some of our algorithms and several standard clustering approaches on real data sets.

Related papers

• Gödel Number based Clustering Algorithm with Decimal First Degree Cellular Automata [0.0]
  In this paper, a decimal first degree cellular automata (FDCA) based clustering algorithm is proposed. Data objects are encoded into decimal strings using G"odel number based encoding. In comparison with the existing state-of-the-art clustering algorithms, our proposed algorithm gives better performance.
  arXiv  Detail & Related papers  (2024-05-08T08:30:34Z)
• Scalable Algorithms for Individual Preference Stable Clustering [8.01184332330228]
  In this paper, we study the natural local search algorithm for IP stable clustering. Our analysis confirms a $O(log n)$-IP stability guarantee for this algorithm, where $n$ denotes the number of points in the input.
  arXiv  Detail & Related papers  (2024-03-15T14:58:27Z)
• Constant Approximation for Individual Preference Stable Clustering [26.716316367717585]
  Individual preference (IP) stability is a natural clustering objective inspired by stability and fairness constraints. It was unknown if an $o(n)$-IP stable clustering always emphexists, as the prior state of the art only guaranteed an $O(n)$-IP stable clustering. We show that an $O(1)$-IP stable clustering always exists for general metrics, and we give an efficient algorithm which outputs such a clustering.
  arXiv  Detail & Related papers  (2023-09-28T20:42:46Z)
• Privacy-preserving Continual Federated Clustering via Adaptive Resonance Theory [11.190614418770558]
  In the clustering domain, various algorithms with a federated learning framework (i.e., federated clustering) have been actively studied. This paper proposes a privacy-preserving continual federated clustering algorithm. Experimental results with synthetic and real-world datasets show that the proposed algorithm has superior clustering performance.
  arXiv  Detail & Related papers  (2023-09-07T05:45:47Z)
• 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)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. We provide implementable differentially private clustering algorithms that provide utility when the data is "easy" We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results.
  arXiv  Detail & Related papers  (2021-12-29T08:13:56Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  We introduce a new approach based on A* search for clustering. We overcome the prohibitively large search space by combining A* with a novel emphtrellis data structure. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks.
  arXiv  Detail & Related papers  (2021-04-14T18:15:27Z)
• Determinantal consensus clustering [77.34726150561087]
  We propose the use of determinantal point processes or DPP for the random restart of clustering algorithms. DPPs favor diversity of the center points within subsets. We show through simulations that, contrary to DPP, this technique fails both to ensure diversity, and to obtain a good coverage of all data facets.
  arXiv  Detail & Related papers  (2021-02-07T23:48:24Z)
• Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
  We propose a novel clustering algorithm, which con-siders the smoothness of data for the first time. Our key idea is to cluster tiny clusters, whose centers constitute smooth graphs. Although in this paper, we singly focus on multi-scale situations, the idea of data smoothness can certainly be extended to any clustering algorithms.
  arXiv  Detail & Related papers  (2020-09-10T05:21:20Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)

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.