提出个体公平的层次聚类方法，降低局部相似性扭曲。
Individual Fairness in Hierarchical Clustering
- 基于局部k近邻约束，定义个体公平的可行性问题
- 证明存在θ(log n)量级的局部与全局可实现性差距
- 理论与实验结合，适用于对公平性敏感的聚类场景
层次聚类生成的超度量结构施加了强全局几何约束，可能导致局部相似性失真，且对个别数据点的影响不均。本文研究在个体公平性要求下的层次聚类，该要求限制局部k-近邻范围内的相对失真。我们将此要求形式化为支配超度量上的可行性问题，并刻画了可行性所需的最小乘性松弛。我们识别出一个尖锐的局部阈值，证明其在有界扰动下保持稳定，建立了k的单调性，并揭示了局部与全局可实现性之间固有的Θ(log n)分离。在合成与真实数据集上的实验支持了理论结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。