Federated Hierarchical Clustering with Automatic Selection of Optimal Cluster Numbers

이 논문은 클라이언트 데이터의 분포를 기반으로 계층적 클러스터링을 수행하여 최적의 클러스터 수를 자동으로 결정하고, 다양한 크기와 형태의 클러스터를 효과적으로 처리할 수 있는 새로운 연방 클러스터링 프레임워크인 Fed-$k^*$-HC 를 제안합니다.

핵심

🗺️ 이야기: 비밀스러운 마을의 지도 그리기

1. 문제 상황: "우리는 몇 개의 마을이 있을까?"

상상해 보세요. 전 세계에 흩어진 수많은 작은 마을 (사용자 기기) 이 있습니다. 각 마을에는 주민들 (데이터) 이 살고 있는데, 어떤 마을은 인구가 1,000 명이고 어떤 마을은 10 명뿐입니다. 또한, 각 마을의 주민들은 서로 다른 취향 (데이터 분포) 을 가지고 있습니다.

중앙 정부 (서버) 는 이 모든 마을을 하나로 묶어 **'전체 지도'**를 만들고 싶습니다. 하지만 두 가지 큰 문제가 있습니다.

1. 비밀 유지: 각 마을의 주민 명단 (원본 데이터) 은 절대 중앙 정부에 보내면 안 됩니다.
2. 알 수 없는 숫자: "전체적으로 몇 개의 큰 마을 (클러스터) 로 나뉘어 있을까?"를 미리 알 수 없습니다. 보통은 "우리는 5 개 마을로 나눈다"고 정해두는데, 실제로는 3 개일 수도, 10 개일 수도 있습니다.

기존 방법들은 "무조건 5 개로 나누자"고 강요하거나, 인구가 적은 마을은 무시하고 큰 마을만 따라가는 실수를 저지르곤 했습니다.

2. 해결책: Fed-k*-HC (스마트한 지도 제작자)

이 논문이 제안한 Fed-k*-HC는 다음과 같은 두 단계의 창의적인 과정을 통해 이 문제를 해결합니다.

1 단계: 각 마을의 '작은 구역' 나누기 (클라이언트 측)
중앙 정부는 직접 주민 명단을 보지 못합니다. 대신, 각 마을의 지도 제작자 (기기) 는 마을을 아주 작은 **'미세 구역 (Micro-subclusters)'**으로 쪼개 봅니다.

• 비유: 마을을 거대한 공원이라고 생각하세요. 공원 전체를 한 번에 보지 말고, 벤치 하나하나, 나무 한 그루씩을 작은 구역으로 나눈 것입니다.
• 보안: 실제 주민 (원본 데이터) 은 보내지 않습니다. 대신, "이 구역은 평균 키가 170cm 이고, 키의 편차가 5cm 입니다"라는 통계 정보만 보내거나, 그 정보를 바탕으로 **가상의 주민 (Synthetic Data)**을 만들어서 보냅니다. 마치 "실제 주민은 아니지만, 이 마을의 분위기를 완벽하게 흉내 낸 가짜 주민"을 보내는 것과 같습니다.

2 단계: 중앙 정부의 '점진적 통합' (서버 측)
중앙 정부는 각 마을에서 받은 '가상의 주민들'을 모아서 지도를 그립니다.

• 자동으로 숫자 찾기: "우리는 몇 개의 큰 마을로 나눌까?"를 미리 정하지 않습니다. 대신, 서로 가까운 '가짜 주민'들을 하나씩 붙여나가며 (Hierarchical Merging), 자연스럽게 뭉쳐지는 지점을 찾습니다.
• 비유: 마치 물방울들이 서로 합쳐져 큰 물방울이 되는 것처럼, 가까운 것끼리 자연스럽게 뭉치다 보면, "아, 여기가 자연스러운 경계구나!"라고 알아차리게 됩니다. 이때 자연스럽게 **최적의 마을 개수 (k*)**가 결정됩니다.
• 불균형 해결: 인구가 10 명뿐인 작은 마을도, 1,000 명인 큰 마을과 똑같이 중요한 '작은 구역'으로 시작했기 때문에, 큰 마을에 흡수되어 사라지지 않고 독립된 마을로 인정받습니다.

3. 이 기술의 핵심 장점 (왜 특별한가요?)

• 🚫 "균일한 효과" 탈출: 기존 방법들은 큰 마을과 작은 마을을 똑같은 크기로 강제로 나누려다 작은 마을을 망가뜨렸습니다. 하지만 이 방법은 자연스럽게 뭉치는 방식을 쓰기 때문에, 인구가 적은 소수 그룹도 제대로 찾아냅니다.
• 🔢 "숫자 맞추기" 자동화: "몇 개로 나눌까?"라는 질문을 미리 답할 필요가 없습니다. 데이터가 말해주는 대로 자연스럽게 정해집니다.
• 🔒 "한 번에 끝내기" (One-shot): 여러 번 오가는 대화 (통신) 없이, 한 번에 정보를 주고받으면 끝납니다. 이는 통신 비용과 시간을 아껴주며, 정보가 오가는 횟수가 적을수록 해킹 위험도 줄어듭니다.

🌟 요약: 한 마디로 표현하면?

이 기술은 **"서로 다른 마을의 주민 정보를 건드리지 않으면서, 각 마을을 작은 조각으로 쪼개서 중앙에 보내고, 중앙에서 그 조각들이 자연스럽게 뭉쳐지는 모습을 보며 '우리는 사실 몇 개의 큰 마을로 나뉘어 있었구나!'를 자동으로 찾아내는 똑똑한 지도 제작법"**입니다.

이 방법은 특히 인구가 적은 소수 그룹 (불균형 데이터) 을 놓치지 않고, 미리 정해진 규칙 없이도 데이터의 진짜 모습을 찾아낸다는 점에서 매우 혁신적입니다.

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

연방 학습 (Federated Learning, FL) 환경에서 데이터 프라이버시를 보호하면서 비지도 학습 방식으로 데이터 분포 패턴을 파악하는 **연방 클러스터링 (Federated Clustering, FC)**은 중요한 과제입니다. 그러나 기존 FC 방법론들은 다음과 같은 심각한 한계를 가지고 있습니다.

• 클러스터 수의 사전 가정: 대부분의 기존 방법은 클러스터의 개수 ($k$) 를 사전에 알고 있어야 하며, 모든 클라이언트의 클러스터 크기가 균일하다는 (Uniform size) 비현실적인 가정을 합니다.
• 불균형 데이터 처리 실패: 실제 세계 데이터는 클러스터 간 샘플 수의 불균형 (Imbalanced distribution) 이 심한 경우가 많습니다. 기존 방법들은 이러한 불균형을 무시하고 강제로 균일한 그룹을 할당하거나, '균일 효과 (Uniform effect)'로 인해 소수 클러스터를 제대로 식별하지 못합니다.
• 프라이버시와 정보의 트레이드오프: 원본 데이터를 전송하지 않으면서도 정확한 글로벌 분포를 파악하는 것은 어렵습니다. 암호화 기반 방법은 계산 비용이 높고, 단순한 통계 전송은 정보 손실을 초래할 수 있습니다.
• 자동 클러스터 수 결정 부재: 대부분의 기존 연방 클러스터링 알고리즘은 최적의 클러스터 수 ($k^*$) 를 자동으로 결정하지 못합니다.

2. 제안 방법: Fed-k∗-HC (Methodology)

이 논문은 위 문제들을 해결하기 위해 Fed-k∗-HC라는 새로운 연방 클러스터링 프레임워크를 제안합니다. 이 방법은 **단일 통신 라운드 (One-shot)**로 작동하며, 계층적 클러스터링을 기반으로 최적의 클러스터 수를 자동으로 결정합니다.

핵심 구성 요소

1. 클라이언트 측: 자동 미세 분할 (Client-Side Automated Micro-Partitioning)

   • 미세 서브클러스터 생성: 각 클라이언트는 로컬 데이터를 너무 많은 수의 '미세 서브클러스터 (Micro-subclusters)'로 세분화합니다. 이를 위해 SNP (Selection of Number of Prototypes) 알고리즘을 사용하여 경쟁 학습 방식으로 데이터 포인트를 대표하는 시드 포인트 (Seed points) 를 자동으로 선택하고 업데이트합니다.
   • 프라이버시 보호 데이터 생성: 원본 데이터를 서버에 전송하지 않습니다. 대신, 생성된 각 서브클러스터의 **평균 (Mean) 과 공분산 (Covariance)**을 계산하고, 이를 기반으로 **다변량 정규 분포 (Multivariate Normal Distribution)**를 사용하여 원본 데이터와 통계적 특성을 유사하게 가진 **대체 데이터 (Synthetic Data)**를 생성합니다.
   • 전송: 클라이언트는 원본 데이터 대신 이 대체 데이터와 서브클러스터의 통계 정보 (반지름, 샘플 수 등) 만 서버로 전송합니다.

2. 서버 측: 계층적 병합 및 자동 $k^*$ 결정 (Server-Side Hierarchical Merging & Automatic $k^*$)

   • SNC (Selection of Number of Clusters) 알고리즘: 서버는 모든 클라이언트로부터 받은 서브클러스터들을 기반으로 글로벌 클러스터 수 $k^*$를 자동으로 결정합니다.
     • Loose Natural Neighbors (LNN) 와 Strict Natural Neighbors (SNN): 기존 자연 이웃 (Natural Neighbor) 알고리즘의 한계를 보완하기 위해, 밀도가 낮은 클러스터의 오류 연결을 방지하기 위해 'Strict Natural Neighbors' 개념을 도입했습니다. 이는 두 점이 서로의 $m$번째 이웃일 때만 연결하는 엄격한 조건을 적용합니다.
     • 최적 $b$ 및 $k^*$ 결정: 거리 분포를 분석하여 최적의 이웃 수 ($b$) 를 찾고, 연결된 구성 요소 (Connected Components) 의 개수를 통해 최종 클러스터 수 $k^*$를 자동으로 추정합니다.
   • 계층적 병합 (Hierarchical Merging): 결정된 $k^*$에 도달할 때까지, 클라이언트 간 서브클러스터를 유사도 (거리, 중첩도, 표준편차 유사도) 를 기반으로 하향식 (Bottom-up) 으로 병합합니다. 이 과정은 작은 클러스터가 무시되거나过早하게 병합되는 것을 방지하여 불균형 데이터를 효과적으로 처리합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 연방 클러스터링 패러다임: 불균형 데이터를 가진 연방 클러스터링 문제를 해결하고, 클러스터 수를 사전에 알지 못해도 되는 새로운 패러다임을 제시했습니다.
2. 미세 분할 및 계층적 병합 메커니즘: 클라이언트 데이터를 미세 서브클러스터로 분할하고, 서버에서 이를 계층적으로 병합함으로써 '균일 효과'를 완화하고 불균형 데이터의 클러스터링 성능을 극대화했습니다.
3. 연방 학습 환경下的 자동 $k^*$ 결정: 기존 방법들과 달리, 데이터 분포를 탐색하여 최적의 클러스터 수 ($k^*$) 를 자동으로 결정하는 알고리즘 (SNC) 을 제안하여 사용자의 사전 지식을 불필요하게 했습니다.
4. 단일 통신 라운드 (One-shot) 효율성: 원본 데이터 전송 없이 통계 기반의 대체 데이터만 한 번 전송하여 프라이버시를 보호하면서도 효율적인 글로벌 모델 구축을 가능하게 했습니다.

4. 실험 결과 (Results)

다양한 합성 데이터 (Synthetic) 와 실제 데이터 (UCI Repository: Pageblock, Yeast, Abalone 등) 를 사용하여 5 가지 기존 방법 (KFed, MUFC, F3KM, Orchestra 등) 과 비교 평가했습니다.

• 성능 우위: 제안된 Fed-k∗-HC 는 F-measure, Accuracy, NMI, ARI 등 대부분의 평가 지표에서 기존 SOTA 방법들보다 우수한 성능을 보였습니다. 특히 **불균형 데이터 (Imbalanced data)**와 Non-IID 환경에서 그 성능 차이가 두드러졌습니다.
• 불균형 데이터 처리: 기존 방법들이 소수 클러스터를 놓치거나 균일한 그룹으로 잘못 분류하는 반면, Fed-k∗-HC 는 밀도가 낮은 소수 클러스터도 정확하게 식별했습니다.
• 자동 $k^*$ 정확도: 대부분의 데이터셋에서 실제 클러스터 수 ($K$) 와 일치하는 $k^*$를 자동으로 추정하는 데 성공했습니다. (Breast 데이터셋과 같이 경계가 모호한 경우 일부 오차가 있었으나, 전체적으로 높은 정확도를 보임).
• 효율성: 단일 통신 라운드로 동작하여 통신 오버헤드가 적으며, 데이터 크기와 클라이언트 수에 대해 선형적으로 확장 가능한 (Scalable) 성능을 입증했습니다.

5. 의의 및 한계 (Significance & Limitations)

• 의의: 이 연구는 연방 학습 환경에서 알려지지 않은 클러스터 수와 심각한 데이터 불균형이라는 두 가지 현실적인 난제를 동시에 해결한 최초의 체계적인 접근 중 하나입니다. 특히 '균일 효과'를 극복하고 프라이버시를 유지하면서 정확한 클러스터링을 수행할 수 있는 방법을 제시함으로써, 의료 진단, 사기 탐지 등 실제 복잡한 분산 데이터 환경에서의 적용 가능성을 크게 높였습니다.
• 한계 및 향후 과제:
  • 서버 측의 계산 비용이 클라이언트 수나 데이터 규모가 매우 커질 경우 증가할 수 있습니다.
  • 극도로 불균형한 분포 (마이크로 서브클러스터보다 더 작은 클러스터) 에서는 탐지 한계가 있을 수 있습니다.
  • 현재는 기본적인 프라이버시 보호 (대체 데이터 생성) 에 의존하고 있으며, 동형 암호화나 차분 프라이버시 (Differential Privacy) 와 같은 고급 기법과의 통합이 향후 과제로 남아있습니다.

결론적으로, Fed-k∗-HC 는 연방 클러스터링 분야에서 불균형 데이터 처리와 자동 클러스터 수 결정이라는 핵심 과제를 해결하여, 실제 응용 분야에 더 가까운 강력한 솔루션을 제공합니다.