대규모 환경에서의 공정 클러스터링 (Fair Clustering)을 위한 빠르고 효과적인 알고리즘

클러스터링 (Clustering)은 유사한 객체들의 그룹을 식별하는 비지도 학습 (Unsupervised Machine Learning) 작업입니다. 이는 수많은 응용 분야를 가지고 있으며, 객체가 고객, 직원 또는 학생과 같이 개인을 나타내는 공정성 민감 (Fairness-sensitive) 영역에서 점점 더 많이 사용되고 있습니다. 우리는 객체들이 보호 그룹 (Protected groups)에 속하는 공정 클러스터링 문제를 다룹니다. 이 문제는 각 보호 그룹이 각 클러스터에서 충분히 대표되도록 하는, 사용자가 정의한 목표 수준의 공정성을 달성하면서 객체들을 미리 정의된 수의 클러스터로 분할하는 것으로 구성됩니다. 목적은 객체와 해당 클러스터 중심 사이의 유클리드 거리 (Euclidean distances) 제곱 합으로 정의되는 클러스터링 비용을 최소화하는 것입니다. 클러스터링 비용과 공정성은 일반적으로 상충하기 때문에, 실제 응용 분야에서는 이들 사이의 트레이드오프 (Trade-off)를 관리하는 것이 필수적입니다. 기존 방법들은 이러한 트레이드오프에 대해 제한적인 제어만을 제공하며, 대규모 데이터셋으로 확장하는 데 실패하거나, 확장이 가능하더라도 낮은 품질의 솔루션을 생성합니다. 우리는 비용-공정성 트레이드오프에 대해 정밀한 제어를 제공하는 공정 클러스터링을 위한 일반적인 프레임워크를 제안하고, 이를 기반으로 한 세 가지 휴리스틱 (Heuristics)을 소개합니다. 첫 번째 휴리스틱은 솔루션 품질과 추가적인 제약 조건을 통합할 수 있는 유연성에 초점을 맞추고 있으며, 두 번째는 높은 솔루션 품질을 유지하면서 확장성 (Scalability)을 개선하며, 세 번째는 최대의 확장성을 위해 설계되어 수백만 개의 객체가 있는 인스턴스에 대해 몇 초 만에 솔루션을 생성합니다. 제안된 휴리스틱들은 벤치마크 데이터셋에 대한 종합적인 수치 실험에서 기존 방식들보다 뛰어난 성능을 보였습니다. 우리 휴리스틱의 소스 코드와 실험 재현을 위한 지침은 GitHub에서 공개적으로 사용할 수 있습니다.