In location-based resource allocation scenarios, the distances between each
individual and the facility are desired to be approximately equal, thereby
ensuring fairness. Individually fair clustering is often employed to achieve
the principle of treating all points equally, which can be applied in these
scenarios. This paper proposes a novel algorithm, tilted k-means (TKM), aiming
to achieve individual fairness in clustering. We integrate the exponential
tilting into the sum of squared errors (SSE) to formulate a novel objective
function called tilted SSE. We demonstrate that the tilted SSE can generalize
to SSE and employ the coordinate descent and first-order gradient method for
optimization. We propose a novel fairness metric, the variance of the distances
within each cluster, which can alleviate the Matthew Effect typically caused by
existing fairness metrics. Our theoretical analysis demonstrates that the
well-known k-means++ incurs a multiplicative error of O(k log k), and we
establish the convergence of TKM under mild conditions. In terms of fairness,
we prove that the variance generated by TKM decreases with a scaled
hyperparameter. In terms of efficiency, we demonstrate the time complexity is
linear with the dataset size. Our experiments demonstrate that TKM outperforms
state-of-the-art methods in effectiveness, fairness, and efficiency.

这篇论文提出了一种名为倾斜 k-means（TKM）的新算法，以实现聚类的个体公平性。通过将指数倾斜集成到平方误差和（SSE）中，形成了一种新的目标函数 —— 倾斜 SSE。基于协作下降和一阶梯度法进行优化，证明了 TKM 的收敛性。在公平性方面，证明了 TKM 生成的方差随着按比例缩放的超参数减小。在效率方面，证明了算法的时间复杂度与数据集大小呈线性关系。实验证明 TKM 在效果、公平性和效率方面优于现有的方法。