자동 매칭 기능 (2차 매칭 알고리즘 : K-means clustering 도입)

1. 서론 및 매칭 알고리즘 구조

서론

현대의 온라인 플랫폼 및 서비스에서는 사용자의 다양성과 특성을 고려한 정밀한 매칭이 필수적이다. 기존의 매칭 알고리즘은 전체 후보자 집합에서 모든 쌍을 비교하는 방식(브루트포스)을 사용하여 높은 정확도를 보장하지만, 후보자 수가 많아질 경우 연산 비용이 기하급수적으로 증가하는 단점이 있다. 이에 따라, 효율성과 확장성을 동시에 달성할 수 있는 새로운 매칭 알고리즘이 필요하다.

본 알고리즘은 후보자들의 평점, 스터디 분야, 선호 시간대를 8:1:1의 가중치로 반영하여 K-means 클러스터링을 통해 유사한 후보자들을 그룹화한다. 이를 통해 전체 후보자 집합을 소규모 클러스터로 나누어 연산량을 크게 줄인다. 각 클러스터 내에서는 인접한 이웃 후보자들 중 최대 5명을 대상으로 CPD(누적 확률 분포)를 활용한 확률적 랜덤 샘플링을 수행하여, 유사도가 높은 후보자들이 선택될 확률을 극대화하면서도 매번 동일한 결과에 치우치지 않는 다양성을 확보한다.

이와 같이, 본 매칭 알고리즘은 효율적인 데이터 분할과 확률 기반 선택을 결합하여, 기존의 O(n²) 방식보다 낮은 시간 복잡도(O(n log n))로 우수한 매칭 품질을 보장할 수 있다. 이를 통해 대규모 사용자 환경에서도 신속하고 안정적인 매칭이 가능하며, 전체 시스템의 확장성과 유연성을 높일 수 있다.

매칭 알고리즘 구조

1. 데이터 구조
   • 후보자의 정보를 저장하는 Candidate 클래스를 설계
   • Comparable 인터페이스를 구현하여 정렬을 쉽게 처리
2. 클러스터링 방식
   • K-means 클러스터링을 적용하여 후보자들을 유사한 그룹으로 나눔.
   • 클러스터링 기준은 평점(8), 스터디 분야(1), 선호시간대(1)의 가중치를 적용하여 유사도를 측정
3. 랜덤 샘플링
   • 각 후보(클러스터)당 가장 가까운 5명의 이웃을 비교()
   • 그 후, 이웃 후보군 내에서 가장 높은 유사도를 가진 쌍을 확률적으로 선택(CPD)
4. 예시 시나리오
   • 10명의 가상의 후보 데이터를 생성하여 알고리즘을 실행합니다.
   • 실행 결과(매칭된 쌍)를 출력하여 확인할 수 있도록 구성합니다.

2. 클러스터 기반 매칭 : K-means 클러스터링

후보자들을 유사한 특성별로 묶기 위해 K-means 클러스터링을 사용한다. 클러스터링 시 유사도 계산에 가중치를 적용하여, rating에는 8, studyField에는 1, preferredTime에는 1의 가중치를 부여한다. 이러한 가중치는 rating 차이가 다른 속성보다 더욱 크게 작용하도록 함.

후보자 리스트를 K-means로 K개의 클러스터로 나눈다. 유클리디안 거리 계산 시 가중치를 적용하여 거리값을 산출한다. 클러스터링 결과는 List<List<Candidate>>로 반환된다.

3. K-means 클러스터링으로 그룹화했을 때의 장점

• 연산량 감소
  전체 후보자 집합에서 모든 쌍을 비교하는 대신, 후보자들을 유사한 그룹(클러스터)으로 묶어 매칭 비교 범위를 크게 줄인다.
  예를 들어, 30명의 후보 전체를 비교하면 435쌍이 될 수 있으나, 클러스터 내에서만 비교하면 계산량이 크게 줄어든다.
• 유사성 극대화
  K-means 클러스터링은 후보자들의 평점, 스터디 분야, 선호 시간대를 8:1:1의 가중치로 반영해 유사한 후보들을 그룹화한다.
  같은 클러스터에 속한 후보들은 서로 유사할 가능성이 높아 매칭 품질이 향상된다.
• 후처리 및 확장성
  클러스터 단위로 매칭을 처리하면 각 그룹별로 개별 최적화나 후처리(예: 인접 클러스터와의 재매칭)를 쉽게 적용할 수 있다. 후보 수가 많아도 병렬 처리나 분할 처리가 용이하다.

4. CPD(누적 확률 분포)를 사용한 랜덤 샘플링 매칭의 장점

• 확률적 다양성
  단순히 최고 점수를 가진 후보만 매칭하는 대신, 각 후보의 유사도(예: 거리의 역수)를 정규화해 누적 분포를 구성한 후 난수를 통해 랜덤하게 선택한다.
  이 방식은 매번 같은 결과가 아니라 여러 번 실행할 때 다양한 매칭 결과를 얻을 수 있게 하며, 마지막에 처리되는 후보들의 매칭 품질도 보장해 전체 후보에 대한 공정한 매칭 결과를 도출한다.
• 미세 차이 반영
  가중치(거리의 역수)를 누적해 확률 분포를 만들면, 유사도가 미세하게 차이나는 후보들 사이에서도 작은 확률 차이가 반영된다. 보통 가장 유사한 후보가 선택되지만 때로는 차순위 후보도 선택될 여지가 생긴다.
• 단순 구현 및 효율성
  누적 확률 분포(CPD)를 계산한 후 난수 값과 비교해 후보를 선택하는 방식은 구현이 간단하고, 상수 개수(예: 5명의 이웃)만 처리하면 되므로 계산 부담이 매우 적다.

5. 시간복잡도 분석

• 클러스터링 (K-means)
  각 후보에 대해 K(상수)개의 센트로이드와의 거리를 계산하므로 한 iteration에 O(n·K)이다.
  반복 횟수가 상수에 수렴한다고 가정하면 전체 클러스터링은 O(n)이다.
• 클러스터 내부 매칭
  각 클러스터 내 후보자 수를 m이라 하면, 정렬 및 이웃 후보 선택 과정이 O(m log m)이다.
  전체 후보가 n명이고 클러스터 수가 상수 K이면 평균 m ≈ n/K이고, 전체 매칭 과정은 O(K · (n/K · log(n/K))) = O(n log(n/K))이다.
  K가 상수이면 이는 O(n log n)와 유사하다.
• 랜덤 샘플링 및 CPD 계산
  각 후보에 대해 상수(예: 5명) 이웃만 비교하므로 이 과정은 상수 시간 O(1)으로 처리된다.
  전체적으로 O(n) 시간에 처리된다.
• 전체 시간복잡도
  클러스터링과 클러스터 내부 매칭 단계의 계산량을 고려하면 전체 알고리즘은 O(n log n) 시간복잡도를 가진다.

K-means 클러스터링을 통해 후보군을 유사한 그룹으로 나누고,
CPD 기반 랜덤 샘플링을 적용하여 전체 후보에 대한 균등한 매칭 품질을 보장할 수 있을 것임