🤖 machine learning

Fast and effective algorithms for fair clustering at scale

본 논문은 대규모 데이터셋에서 기존 방법보다 우수한 성능을 보이며 보호 그룹 간 사용자 정의 공정성 제약 조건을 충족하면서도 클러스터링 비용 최소화와 공정성 보장 간의 균형을 효과적으로 맞추는 공정한 클러스터링을 위한 일반적 프레임워크와 세 가지 확장 가능한 휴리스틱을 제안한다.

원저자: Claudio Mantuano, Manuel Kammermann, Philipp Baumann

게시일 2026-05-14

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Claudio Mantuano, Manuel Kammermann, Philipp Baumann

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

1,000 명의 손님을 10 개의 원탁에 배치해야 하는 파티 플래너가 된 상황을 상상해 보세요. 당신의 목표는 서로 아는 사이이거나 비슷한 취향을 가진 사람들을 함께 앉히는 것입니다 (이를 클러스터링이라고 합니다). 하지만 동시에 엄격한 규칙이 하나 있습니다. 모든 테이블은 나이, 성별, 거주지 등 서로 다른 배경을 가진 손님들이 공평하게 섞여 있어야 합니다 (이를 공정성이라고 합니다).

가장 비슷한 사람들끼리만 무작정 섞어놓고 배분 조합을 고려하지 않으면, 우연히 한 테이블은 특정 집단만으로 가득 차고 다른 테이블은 또 다른 집단만으로 가득 차게 될 수 있습니다. 이렇게 되면 '불공평한' 테이블이 만들어집니다. 문제는 테이블을 완벽하게 섞으려면 종종 손님들을 그들의'가장 친한 친구'로부터 더 멀리 떨어져 앉혀야 하므로, 파티의 효율성이 떨어질 수 있다는 점입니다.

이 논문은 수백만 명의 사람들로 구성된 대규모 데이터셋을 대상으로 하면서도 테이블을 공정하게 유지하고 손님들을 만족시키는 이 대규모 파티의 좌석 배치 문제를 해결하는 세 가지 새로운 초고속 방법을 소개합니다.

핵심 문제: '공정성 대 비용'의 줄다리기

저자들은 두 가지 목표 사이의 지속적인 갈등을 설명합니다.

낮은 비용: 손님들이 편안함을 느끼도록 손님을 테이블의'중심'(테이블의 평균적인 사람) 에 가깝게 배치하는 것.
높은 공정성: 모든 테이블에 서로 다른 그룹의 적절한 비율이 포함되도록 보장하는 것.

보통 테이블을 완벽하게 공정하게 만들려고 하면, 손님들이 그곳에 앉기 위해 이동해야 하는'비용'(거리) 이 증가합니다. 기존 방법들은 서툴게 파티를 준비하는 플래너와 같았습니다. 거대한 파티를 처리하지 못하거나, 플래너에게 테이블의 공정성 정도를 조절할 수 있는 권한을 거의 주지 못했습니다. 그들은 종종 정밀하게 조정하기 어려운'가중치'노브를 사용했습니다.

해결책: 세 가지 도구 키트

저자들은 다양한 파티 규모를 처리할 수 있는 일반적인 프레임워크 (마스터 플랜) 와 세 가지 구체적인 도구 (휴리스틱) 를 제안합니다. 세 가지 도구 모두'분해 방식'을 사용하는데, 이는 두 단계로 이루어진 춤과 같습니다.

배정: 누가 어느 테이블에 앉을지 결정합니다.
업데이트: 그 자리에 앉은 사람들의 평균 위치에 맞춰 테이블의 중심을 이동시킵니다.
좌석 배정이 더 이상 개선되지 않을 때까지 이 춤을 반복합니다.

다음은 세 가지 도구입니다.

1. MPFC:'정밀 건축가'

가장 적합한 경우: 중규모 파티 (최대 10 만 명).
작동 원리: 이 도구는 좌석 배정을 복잡한 수학 퍼즐 (이진 선형 계획법) 로 취급합니다. 공정성 규칙을 충족하면서 거리를 최소화하는 완벽한 배정 방식을 계산합니다.
비유: 모든 가능한 좌석 배정표를 설계도 against 확인한 후 가장 좋은 것을 선택하는 초엄격한 건축가를 상상해 보세요. 이는 놀라울 정도로 정확하고 유연합니다 (이 두 사람은 반드시 함께 앉아야 한다는 규칙 추가 등). 하지만 파티가 너무 커지면 속도가 느려집니다.

2. MS-FlowFC:'교통 관리자'

가장 적합한 경우: 하나의 특정 유형의 다양성 (예: 성별 또는 나이만) 을 가진 대규모 파티.
작동 원리: 거대한 수학 퍼즐 하나를 푸는 대신, 이 도구는 문제를 더 작고 빠른 단계로 나눕니다.'최소 비용 흐름'알고리즘을 사용하는데, 이는 고속도로의 교통을 관리하는 것과 같습니다. 단계별로 그룹을 테이블로 보내 도로가 정체되지 않고 규칙이 준수되도록 합니다.
비유: 교통 경찰이 차들을 지시하는 것을 생각해 보세요. 도시 전체의 교통을 한 번에 계획하는 대신, 차선 하나를 지시한 다음 다음 차선을 지시하여 모든 사람이 충돌 없이 목적지에 빠르게 도착하도록 합니다. 건축가보다 훨씬 빠르지만, 하나의'교통 규칙'(하나의 민감한 특성) 만 있을 때 가장 잘 작동합니다.

3. S-MPFC:'군중 요약자'

가장 적합한 경우: 대규모 파티 (수백만 명의 손님).
작동 원리: 이는 궁극적인 속도 도구입니다. 춤이 시작되기 전에 유사한 손님들을'배치'로 그룹화하고 각 배치에 대한 단일'대표'를 생성합니다. 그런 다음 이 대표들 (파티의 작은 버전) 에 대한 좌석 배치 문제를 해결한 후 결과를 실제 손님들에게 매핑합니다.
비유: 백만 명의 군중이 있다고 상상해 보세요. 모든 사람에게 어디에 앉고 싶은지 묻는 대신, 1 만 명씩을 대표하는 100 명의'대변인'에게 물어봅니다. 100 명의 대변인이 어디에 앉을지 정한 다음, 나머지 사람들은 모두 그들의 대표를 따릅니다. 이를 통해 플래너는 몇 초 만에 문제를 해결할 수 있습니다.

결과: 왜 이것이 중요한가

저자들은 실제 세계 데이터 (신용카드 기록, 인구 조사 데이터, 심지어 사이버 보안 로그 등) 를 사용하여 기존 방법들과 이 도구들을 테스트했습니다.

속도: 새로운 도구들은 훨씬 더 빠릅니다. 약 250 만 명의 데이터셋에서'군중 요약자'(S-MPFC) 는 더 나은 좌석 배정을 찾으면서도 이전 최고 방법보다 99.7% 더 빠릅니다.
품질: 새로운 방법들은 경쟁사보다 더 빠를 뿐만 아니라'비용'이 더 낮은 (손님들이 더 만족하는) 해결책을 찾았습니다.
제어: 저자들은'허용 오차 매개변수'(0 에서 1 까지의 다이얼) 를 도입했습니다.
- 0으로 설정: 완벽한 공정성을 요구합니다 (모든 테이블이 전체 군중의 완벽한 거울이 됩니다).
- 1로 설정: 공정성을 완전히 무시합니다 (일반적인 클러스터링).
- 마법: 이 다이얼은 사용자에게 정밀한 제어를 제공합니다. 기존 방법들은 온/오프 방식의 전등 스위치와 같았지만, 이는 조광기 스위치처럼 필요한 정확한 균형을 찾을 수 있게 해줍니다.

요약

이 논문은 단순히"우리가 더 빠르게 만들었다"라고 주장하는 것을 넘어, 현재 이용 가능한 어떤 것보다'공정 클러스터링'문제를 더 잘 해결하는 유연하고 정밀하며 확장 가능한 시스템을 구축했다고 주장합니다. 손님이 100 명이든 1,000 만 명이든, 이 키트에는 공정하고 효율적으로 그들을 앉힐 수 있는 도구가 있으며, 플래너에게 공정성 규칙이 얼마나 엄격해야 하는지에 대한 정확한 통제권을 제공합니다.

기술 요약: 대규모 공정한 클러스터링을 위한 빠르고 효과적인 알고리즘

문제 정의

본 논문은 유사한 객체들을 $k$ 개의 클러스터로 분할하는 비지도 기계 학습 작업의 확장인 공정한 클러스터링 문제를 다룹니다. 이 맥락에서 객체들은 보호 그룹을 정의하는 민감한 특성 (예: 인종, 성별) 을 갖습니다. 목표는 클러스터링 비용 (객체와 해당 클러스터 중심점 사이의 유클리드 거리 제곱의 합으로 정의되며, 즉 $k$ -means) 을 최소화하면서 공정성 제약 조건을 만족하는 것입니다.

공정성은 Chierichetti 등 (2017) 이 처음 도입한 균형 (balance) 개념을 사용하여 측정됩니다. 클러스터링 솔루션은 모든 민감한 특성에 대해, 각 클러스터 내의 임의의 두 보호 그룹에서 유래한 객체들의 비율이 최소 임계값을 충족할 때 공정한 것으로 간주됩니다. 저자들은 목표 균형을 제어하기 위한 허용 오차 매개변수 $\lambda \in [0, 1]$ 를 도입했습니다. $\lambda=0$ 은 데이터셋의 전역 균형과 일치하는 최고 수준의 공정성을 요구하는 반면, $\lambda=1$ 은 공정성 요구 사항을 부과하지 않아 문제를 기존 $k$ -means 문제로 축소합니다. 이 문제는 표준 $k$ -means 문제를 일반화한 것으로 NP-난해 (NP-hard) 입니다.

기존 방법들은 세 가지 주요 한계를 겪고 있습니다:

유연성 부족: 많은 방법들은 특정 문제 변형에 국한되어 있으며, 실용적인 제약 조건 (예: 카디널리티 제약, 무조건 연결/연결 불가 제약) 을 쉽게 통합할 수 없습니다.
세밀하지 않은 제어: 비용 - 공정성 트레이드오프를 분석하는 방법들은 종종 목적 함수의 가중치 매개변수에 의존하여, 원하는 공정성 수준에 대한 간접적이고 부정확한 제어만 제공합니다.
확장성 대 품질: 확장 가능한 접근 방식들은 종종 정보 손실과 해의 품질 저하로 이어질 수 있는 근사치 (fairlets 또는 coresets) 에 의존하거나, 수백만 개의 객체로 확장되지 못합니다.

방법론

저자들은 $k$ -means 분해 기법 (객체 할당과 클러스터 중심점 업데이트 간 교차 반복) 을 기반으로 한 일반 프레임워크를 제안하며, 할당 단계의 구현 방식이 서로 다른 세 가지 휴리스틱을 도입합니다:

1. 수학적 프로그래밍 기반 공정한 클러스터링 (MPFC)

메커니즘: 할당 단계에서 객체들은 **이진 선형 계획법 (BLP)**을 풀어서 고정된 클러스터 중심점에 할당됩니다.
제약 조건: BLP 는 모든 민감한 특성과 클러스터에 대해 목표 균형이 충족되도록 보장하는 제약 조건을 포함합니다. 제약 조건들은 허용 오차 매개변수 $\lambda$ 를 사용하여 선형화됩니다.
범위: 약 100,000 개까지의 객체로 구성된 인스턴스에 적합합니다. 추가 제약 조건 (예: 카디널리티, 연결 조건) 을 BLP 에 직접 통합할 수 있는 높은 유연성을 제공합니다.
한계: 매우 큰 $n$ 과 $k$ 의 경우 전체 BLP 를 푸는 것은 계산적으로 비용이 많이 듭니다.

2. 다단계 최소 비용 흐름 기반 공정한 클러스터링 (MS-FlowFC)

메커니즘: 단일 민감한 특성을 가진 인스턴스를 위해 설계되었습니다. 할당 단계는 각 보호 그룹 (크기 순으로 정렬됨) 에 대해 하나씩인 여러 단계로 분해됩니다.
알고리즘: 단일 BLP 대신 할당은 최소 비용 흐름 문제의 시퀀스로 풀립니다.
- 1 단계: 가장 큰 보호 그룹이 가장 가까운 중심점에 할당됩니다.
- 후속 단계: 나머지 그룹들은 이전 단계에서 유도된 공정성 경계를 존중하도록 노드 수요와 아크 용량이 동적으로 조정되는 흐름 네트워크를 풀어 할당됩니다.
장점: 최소 비용 흐름 문제는 다항 시간 내에 해결 가능하므로, 높은 해의 품질을 유지하면서 MPFC 대비 상당한 속도 향상을 제공합니다.
한계: 단일 민감한 특성으로 제한됩니다.

3. 확장 가능한 수학적 프로그래밍 기반 공정한 클러스터링 (S-MPFC)

메커니즘: 대규모 데이터셋 (수백만 개의 객체) 을 위해 설계되었습니다. 수정된 MPFC 와 전처리 기술을 결합합니다.
전처리: 데이터셋은 먼저 기존 $k$ -means 를 사용하여 "배치" (유사한 객체의 부분집합) 를 형성하도록 클러스터링됩니다. 각 배치는 각 보호 그룹에서 유래한 객체 수를 나타내는 관련 가중치를 가진 단일 대표자 (배치 중심점) 로 표현됩니다.
클러스터링: BLP 는 개별 객체가 아닌 축소된 대표자 집합에 대해 풀립니다. 결과 할당은 원래 객체들로 매핑됩니다.
혁신: fairlets 또는 coresets 와 달리, 이러한 배치는 내부적으로 공정성 제약 조건을 충족할 필요가 없습니다. 공정성은 대표자의 할당 수준에서 강제됩니다.
장점: 수백만 개의 객체를 초 단위로 처리할 수 있습니다.

주요 기여

정밀한 제어: 프레임워크는 가중치 기반 트레이드오프 방법의 세밀하지 않은 제어를 극복하고 목표 균형을 직접 제어하는 단일 허용 오차 매개변수 $\lambda$ 를 도입합니다.
유연성: BLP 기반 접근 방식 (MPFC 및 S-MPFC) 은 $k$ -median, $k$ -medoids 와 같은 대안 목적 함수에 쉽게 적응할 수 있으며, 카디널리티 또는 연결 조건과 같은 응용 프로그램별 제약 조건을 통합할 수 있습니다.
확장성 기술:
- 정수 계획법 솔버를 피하는 최소 비용 흐름을 사용한 할당 단계에 대한 분해 전략 (MS-FlowFC).
- 부분집합에 내부 공정성 제약을 부과하지 않고 데이터를 집계하여 전통적인 fairlet 분해보다 더 많은 정보를 보존하는 전처리 기술 (S-MPFC).
정확한 벤치마크: 저자들은 이 특정 공정한 $k$ -means 문제에 대한 최초의 정확한 방법으로 주장되는 Mixed-Integer Quadratically Constrained Programming (MIQCP) 모델과 Set-Variable 기반 (SetVars) 형식을 벤치마크를 위한 두 가지 정확한 방법을 제공합니다.

실험 결과

저자들은 Backurs 등 (2019) 의 확장 가능한 공정한 클러스터링 (SFC) 알고리즘과 Li 등 (2024) 의 order-and-cut (O&C) 알고리즘을 포함한 벤치마크에 대해 21 개에서 약 250 만 개까지의 객체로 구성된 합성 및 실제 세계 데이터셋에서 방법들을 평가했습니다.

해의 품질:
- 작은 인스턴스에서 MPFC 와 MS-FlowFC 는 일관되게 최적 또는 준최적 해를 찾았으며, 종종 합리적인 시간 제한 내에서 정확한 솔버보다 우수한 성능을 보였습니다.
- 중간 규모 데이터셋 (예: BANK-40K, ADULT) 에서 MPFC 와 MS-FlowFC 는 클러스터 수와 공정성 수준에 따라 약 1% 에서 40% 이상까지 개선된 SFC 보다 낮은 클러스터링 비용을 일관되게 달성했습니다.
- 대규모 데이터셋 (CENSUS1990, 약 250 만 개 객체) 에서 S-MPFC 는 SFC 보다 고품질 해를 생성했습니다.
확장성 및 실행 시간:
- S-MPFC는 250 만 개 객체를 가진 인스턴스를 초 단위로 해결하여 탁월한 확장성을 입증했습니다. 가장 큰 데이터셋에서 SFC 대비 실행 시간을 99.70% 단축하면서 해의 품질을 향상시켰습니다.
- MS-FlowFC는 확장 불가능한 방법 중 가장 빠르며, 중간 규모 데이터셋에서 평균 실행 시간이 SFC 보다 95.47% 낮았습니다.
- 제안된 방법들은 SFC 에 비해 무작위 시드 간 해의 품질 변동성이 더 낮았습니다.
비용 - 공정성 트레이드오프:
- 제안된 휴리스틱들은 $\lambda$ 를 통해 트레이드오프에 대한 정밀한 제어를 입증했습니다.
- O&C 와 비교하여 MPFC 와 MS-FlowFC 는 평균 24.33% 감소한 클러스터링 비용으로 동일하거나 더 높은 공정성 수준을 달성했습니다.
- 제안된 방법들의 경우 높은 공정성을 달성하기 위해 필요한 비용 증가는 O&C 에서 관찰된 급격한 비용 증가에 비해 미미했습니다.

중요성 및 주장

본 논문은 제안된 휴리스틱들이 해의 품질, 확장성, 그리고 유연성 사이의 균형을 맞추는 일반 프레임워크를 제공함으로써 공정한 클러스터링 문헌의 중요한 격차를 해소한다고 주장합니다.

실용적 적용성: 이 방법들은 데이터셋이 크고 공정성 요구 사항이 엄격한 실제 세계 배포를 위해 설계되었습니다. 수백만 개의 객체를 초 단위로 처리할 수 있는 능력은 시간 민감형 응용 프로그램에 적합하게 만듭니다.
우월한 트레이드오프 관리: 저자들은 기존 최첨단 방법들에 비해 비용 - 공정성 트레이드오프에 대한 우월한 제어를 제공한다고 주장하며, 실무자들이 과도한 클러스터링 비용을 치르지 않고도 특정 공정성 목표를 달성할 수 있게 한다고 합니다.
견고성: 결과는 제안된 방법들이 다양한 데이터셋 크기, 클러스터 수, 그리고 공정성 수준에서 견고하며 효율성과 효과성 모두에서 선도적인 벤치마크를 일관되게 능가함을 나타냅니다.

저자들은 향후 작업이 추가 제약 조건과 대안 초기화 전략을 탐구할 수 있지만, 현재 휴리스틱은 대규모 실용적 응용을 위한 공정한 클러스터링을 실현 가능하게 만드는 중요한 진전이라고 결론지었습니다.