迈向公平的聚类决策边界：将不同的影响标准整合到最大边际聚类中

《ACM Transactions on Knowledge Discovery from Data》：Towards Fair Decision Boundaries in Clustering: Integrating Disparate Impact Criteria into Maximum Margin Clustering

公平最大间隔聚类算法（FMMC）通过整合离散影响准则和决策边界公平性度量，在保持聚类性能的同时确保公平性。实验表明，FMMC有效降低了决策边界的协方差，提高了平衡性指标，并在真实数据集上验证了其公平性和聚类效果的综合优化。

　　机器学习在影响人类生活的各个领域得到了广泛的应用，这促使了对开发可证明公平的算法的兴趣显著增加。近年来，研究者们在聚类算法中引入了公平性约束，以应对公平性问题。本文提出了一种新的算法，称为公平最大边际聚类（Fair Maximum Margin Clustering, FMMC），该算法将监督学习中的差异影响标准引入到聚类过程中，特别关注决策边界公平性。传统聚类算法如k-means主要依据数据点之间的相似性进行分组，而FMMC通过最大化不同聚类之间的分离度，类似于监督学习中支持向量机（Support Vector Machine, SVM）的工作原理。在监督学习中，差异影响（Disparate Impact）是一种广泛研究的公平性定义，它基于对不同群体的选中率进行衡量，并在反歧视法律中有法律依据。然而，在聚类场景中，由于缺乏真实标签，无法直接应用差异影响的定义。因此，本文选择将差异影响的定义引入到聚类算法中，以解决这一问题。

在本文的研究中，我们通过引入差异影响标准，设计了一种新的公平性约束，以确保每个数据点到决策边界的距离与其敏感属性值之间没有相关性。这一约束旨在防止任何敏感群体受到决策边界的影响。我们展示了FMMC算法在传统公平性度量如Balance方面的表现优于MMC算法。此外，我们还证明了FMMC算法在保持原始MMC算法聚类性能的同时，能够实现公平的聚类。为了验证所提出方法的有效性，我们在合成数据集和真实世界数据集上进行了实验。

在研究的初步阶段，我们介绍了用于本文的符号和术语，并回顾了聚类场景中的公平性定义。Balance标准确保每个聚类中的数据点在各个敏感群体中的分布比例与整个数据集中这些群体的比例相一致，这是聚类场景中常用的公平性标准。然而，这一标准在MMC等聚类算法中难以直接应用，因为MMC通过找到一个超平面来分隔数据点。因此，我们选择使用差异影响标准，这是监督学习场景中一种有法律依据且广泛应用的公平性定义。在本文中，我们首次将差异影响标准引入到MMC算法中。

在本文中，我们介绍了差异影响标准在监督学习中的应用，并讨论了其在聚类场景中的适用性。差异影响标准起源于反歧视法律，特别是在美国，差异影响指的是即使没有有害意图，对受保护群体的不公平影响。在监督学习中，差异影响可能出现在模型预测结果对某些群体产生系统性优势或劣势的情况。例如，在招聘算法中，模型可能会无意中对某一性别群体产生不利影响。为了减少差异影响，研究者们提出了多种公平性度量，如统计对等（Statistical Parity）或民主对等（Demographic Parity），这些度量旨在确保模型在不同群体上的错误率平衡。此外，还有如等效机会（Equalized Odds）和预测对等（Predictive Parity）等标准，它们旨在确保模型在不同群体上的预测结果一致。

为了定义差异影响，我们使用了80%规则。根据这一规则，如果受保护群体的选中率低于不受保护群体的80%，则认为存在差异影响。这一定义在招聘场景中被广泛使用，并被应用于监督学习算法以确保对受保护属性的公平预测。

MMC算法在聚类场景中扩展了监督学习中SVM的思路，旨在找到一个超平面，将数据点分成两个聚类，并确保这两个聚类之间的距离最大。MMC算法通过求解一个优化问题来实现这一目标，其中引入了一个参数来平衡各个聚类中的数据点数量。这一参数使得MMC算法能够避免简单的解，例如将所有数据点归为同一聚类。

在本文中，我们引入了差异影响标准，并将其作为约束条件整合到MMC算法中，从而开发了FMMC算法。FMMC算法通过迭代的投影机制，确保数据点到决策边界的距离与其敏感属性值之间没有相关性。这一方法通过将公平性约束整合到MMC算法中，使得算法能够在保持聚类性能的同时，实现公平性。此外，我们还验证了FMMC算法在合成数据集和真实世界数据集上的有效性。

在本文的研究中，我们通过实验展示了FMMC算法在减少差异影响和提高Balance方面的效果。实验结果显示，FMMC算法在保持较高的聚类性能的同时，能够有效减少差异影响。此外，FMMC算法在合成数据集和真实世界数据集上均表现出良好的Balance。我们还讨论了FMMC算法与其他公平聚类算法（如Fair Spectral Clustering和Scalable Fair Clustering）的比较，结果显示FMMC算法在大多数数据集上均优于这些方法。

在实验部分，我们使用了合成数据集和真实世界数据集进行测试。合成数据集包括Blobs和Two-Moons，它们分别由四个不同的群体和两个月牙形群体组成。真实世界数据集包括Adult、Bank、Credit、Compas、Catalonia、Student和Law数据集，其中每个数据集都有不同的敏感属性，如性别和种族。我们使用了多种公平性度量，包括决策边界协方差、Balance和轮廓系数（Silhouette Score）来评估算法的性能。

在实验中，我们发现FMMC算法在减少差异影响和提高Balance方面表现出色。此外，FMMC算法在合成数据集和真实世界数据集上的轮廓系数变化较小，表明其聚类性能未受到显著影响。实验结果还显示，FMMC算法在处理多值敏感属性时表现良好，尽管其尚未被优化以处理多值敏感属性。

本文的研究为聚类算法的公平性提供了一种新的方法，即通过引入差异影响标准，确保数据点到决策边界的距离与其敏感属性值之间没有相关性。这一方法不仅提高了聚类的公平性，还保持了较高的聚类性能。未来的研究可以进一步探索如何将其他公平性定义，如个体公平性，引入到聚类算法中，以实现更全面的公平性保障。