Individual Preference Stability for Clustering
Individual Preference Stability for Clustering
复制标题
DOI：
10.48550/arxiv.2207.03600
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Saba Ahmadi-;Pranjal Awasthi;S. Khuller;Matthäus Kleindessner;Jamie Morgenstern;Pattara Sukprasert;A. Vakilian
中科院分区：
文献类型：
--
作者：
Saba Ahmadi-;Pranjal Awasthi;S. Khuller;Matthäus Kleindessner;Jamie Morgenstern;Pattara Sukprasert;A. Vakilian
在本文中，我们提出了聚类的个体偏好（IP）稳定性的自然概念，该概念要求每个数据点平均而言更接近其自己聚类中的点，而不是任何其他聚类中的点。我们的概念可以从多个角度出发，包括博弈论和算法公平性。我们研究了与我们提出的概念相关的几个问题。我们首先表明，决定给定数据集是否允许 IP 稳定聚类通常是 NP 困难的。因此，我们探索了有效算法的设计，以在一些受限的度量空间中寻找 IP 稳定的聚类。我们提出了一种多时间算法来寻找在实线上满足精确 IP 稳定性的聚类，以及一种有效的算法来寻找树度量的 IP 稳定 2 聚类。我们还考虑放宽稳定性约束，即与任何其他簇相比，每个数据点不应该距离自己的簇太远。对于这种情况，我们提供具有不同保证的多时间算法。我们在真实数据集上评估了一些算法和几种标准聚类方法。
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.