Individual Fairness in Hierarchical Clustering
Hierarchical clustering produces ultrametric representations that impose strong global geometric constraints and may distort local similarities in ways that disproportionately affect individual data points. We study hierarchical clustering under an individual fairness requirement that bounds relative distortion within local $k$-nearest neighborhoods. We formulate this requirement as a feasibility problem over dominated ultrametrics and characterize the minimal multiplicative slack required for feasibility. We identify a sharp local threshold, prove stability under bounded perturbations, establish monotonicity in $k$, and show an intrinsic $Θ(\log n)$ separation between local and global realizability. Experiments on synthetic and real world datasets support our theoretical results.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Notion of Individual Fairness for Clustering
A common distinction in fair machine learning, in particular in fair classification, is between group fairness and individual fairness. In the context of clustering, group fairness has been studied extensively in recent …
ClusteringFairnessGeneralized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost
Clustering is a fundamental building block of modern statistical analysis pipelines. Fair clustering has seen much attention from the machine learning community in recent years. We are some of the first to study fairness…
ClusteringFairnessFeature-based Individual Fairness in k-Clustering
Ensuring fairness in machine learning algorithms is a challenging and essential task. We consider the problem of clustering a set of points while satisfying fairness constraints. While there have been several attempts to…
ClusteringFairnessDistributional Individual Fairness in Clustering
In this paper, we initiate the study of fair clustering that ensures distributional similarity among similar individuals. In response to improving fairness in machine learning, recent papers have investigated fairness in…
ClusteringFairness(Individual) Fairness for k-Clustering
We give a local search based algorithm for $k$-median ($k$-means) clustering from the perspective of individual fairness. More precisely, for a point $x$ in a point set $P$ of size $n$, let $r(x)$ be the minimum radius …
ClusteringFairness