기술 요약: 정답(Ground Truth)을 이용한 클러스터링 평가

문제 정의

클러스터링 알고리즘을 평가하는 것은 분류(Classification)와는 구별되는 근본적인 과제를 안고 있다. 분류에서는 예측된 레이블을 정답 레이블과 직접 비교할 수 있다. 그러나 클러스터링의 경우, 클러스터 인덱스는 고유한 대응 관계가 없는 임의의 숫자이며, 솔루션의 클러스터 개수가 정답의 클러스터 개수와 다를 수 있다. 결과적으로, 표준 분류 정확도 지표를 적용할 수 없다.

내부 검증(합계 제곱 오차와 같은 비용 함수 최적화)과 응용 수준의 성능 측면이 존재하지만, 이들은 종종 명확한 해석력이 부족하거나 알고리즘의 구체적인 클러스터링 동작에 대한 깊은 통찰을 제공하지 못한다. 정답이 존재하는 경우에는 외부 타당성 지표(External validity indexes)가 필요하다. 그러나 기존의 척도들은 편향성, 해석력, 그리고 다양한 클러스터링 시나리오(예: 균형 잡힌 클서터 크기 대 불균형한 클러스터 크기)에 대한 적합성 면에서 크게 차이를 보인다.

방법론

본 논문은 외부 타당성 지표를 두 가지 주요 클래스인 **쌍 기반 측정(Pairwise Measures)**과 **집합 매칭 기반 측정(Set-Matching-based Measures)**으로 분류하고 검토한다.

1. 쌍 기반 측정 (Pairwise Measures)

이 측정 방식은 두 클러스터링 간의 점 쌍(point pairs)의 일관성을 평가한다.

• 랜드 지수 (Rand Index, RI): 일치하는 쌍(두 솔루션 모두에서 같은 클러스터에 속하거나 다른 클러스터에 속하는 경우)의 비율을 계산한다. 이는 서로 다른 클러스터에 속하는 쌍의 일치에 의해 수치가 압도되어, 거의 모든 합리적인 클러스터링에 대해 높은 값을 산출한다는 비판을 받는다.
• 조정 랜드 지수 (Adjusted Rand Index, ARI): 무작위 클러스터링 기대치에 대해 RI를 정규화한다. 더 유용하기는 하지만, 클러스터 크기가 불균형할 때 가장 큰 클러스터에 편향되는 경향이 남아 있다.
• 정규화된 상호 정보량 (Normalized Mutual Information, NMI): 클러스터 쌍 사이의 공유된 정보를 정량화하는 정보 이론적 척도이다. 이는 여러 다른 지표(AVIS, NVIS, AMI)와 동일하며, 클러스터의 개수가 많을 때 편향될 수 있다고 언급된다.

2. 집합 매칭 기반 측정 (Set-Matching-based Measures)

이 측정 방식은 솔루션 내 각 클러스터에 대해 정답 내에서 가장 잘 매칭되는 클러스터를 찾아 유사도를 계산한다. 방법론은 세 가지 설계 구성 요소를 포함한다:

• 매칭 전략 (Matching Strategy):
  • 매핑 (Mapping): 단방향(예: Purity, F-Measure) 또는 양방향(예: NVD, CI).
  • 페어링 (Pairing): 여러 클러스터가 동일한 타겟에 매핑되는 것을 방지한다. 이는 그리디 페어링(Greedy Pairing, 예: CH, CR) 또는 헝가리안 알고리즘을 이용한 최적 페어링(Optimal Pairing, 예: ACC, PSI)을 통해 해결할 수 있다.
• 유사도 메트릭 (Similarity Metric):
  • 원시 교집합 (Raw Intersection): 공유된 점의 개수 $|A \cap G|$를 계산한다 (ACC, NVD, CH). 이는 큰 클러스터에 유리하다.
  • 집합 유사도 (Set Similarity): 클러스터 크기를 정규화하기 위해 Jaccard(CSI), Braun-Banquet(PSI), 또는 Sorensen-Dice(FM)를 사용한다.
  • 중심점 매칭 (Centroid Matching): 중심점을 직접 매칭한다 (CI, CR, GCI).
• 정규화 (Normalization):
  • 대부분은 총 점의 개수($N$)로 정규화하여 모든 점이 동등하게 기여하도록 한다.
  • 일부(CI와 같은 경우)는 클러스터 수준에서 점수를 계산하여(클러스터당 0 또는 1) 정수 기반의 오차 개수를 허용한다.

3. 중심점 지수 (Centroid Index, CI)

본 논문은 **중심점 지수 (CI)**를 특별히 강조한다. 점 수준의 측정 방식과 달리, CI는 클러스터 수준의 측정 방식이다. 이는 클러스터링 결과에 대응하는 중심점이 없는 정답 중심점(고아 중심점, orphan centroids)의 개수를 결정한다.

• 메커니즘: 가장 가까운 중심점(또는 일반화된 버전에서의 최대 중첩)을 기준으로 클러스터를 매칭하고 불일치를 계산한다.
• 출력값: 클러스터의 개수인 $k$ 범위 내의 정수 $[0, k]$를 반환한다. 0은 모든 클러스터가 올바르게 위치했음을 의미한다.

주요 기여 및 결과

본 논문은 외부 지표에 대한 포괄적인 검토를 제공하며, 특정 강점과 약점을 강조한다:

• 해석력: 저자들은 NMI와 ARI 같은 표준 지표들이 [0, 1] 사이의 값을 생성하지만, 직관적으로 해석하기 어렵다고 주장한다(예: 0.90이 "좋은" 클러스터링을 의미하는가?). 반면, CI는 설명 가능한 결과를 제공한다: 잘못 위치한 클러스터의 정확한 개수.
• 편향 분석:
  • NMI는 Birch2 데이터셋에서 보여지듯, 클러스터의 개수가 많을 때(예: $k=100$) 잘못된 클러스터링에 대해서도 기만적으로 높은 점수를 산출하는 것으로 나타났다(잘못된 결과가 NMI 0.96을 기록함).
  • ARI는 불균형한 시나리오에서 가장 큰 클러스터들의 일치에 편향된다.
  • 랜드 지수는 클러스터 크기나 개수에 관계없이 본질적인 편향을 가지고 있어 부적절한 것으로 간주된다.
• 점 수준 vs. 클러스터 수준: 논문은 점 수준의 편차를 포착하는 척도(ACC, PSI)와 클러스터 수준의 구조적 오류를 포착하는 척도(CI)를 구분한다. CI는 미세한 점 수준의 편차(예: 약간의 중심점 이동)는 놓칠 수 있지만, 거시적인 구조적 실패(예: 누락되거나 병합된 클러스터)를 식별하는 데 탁월하다.
• 구현: 논문은 C 언어용 CBEVI 및 ACC(페어링 및 매칭 변형 모두 지원)를 위한 파이썬 라이브러리를 포함한 가용한 소프트웨어 구현을 참조한다.

의의 및 권장 사항

본 논문은 정답을 이용해 클러스터링을 평가하는 실무자들을 위해 다음과 같은 구체적인 권장 사항을 제시하며 결론을 맺는다:

1. 주요 권장 사항 (클러스터 수준): **중심점 지수 (CI)**를 사용하라. 직관적인 성격과 설명 가능한 출력값(오류 개수) 때문에 권장된다. 이는 올바른 클러스터링 구조를 찾았는지 확인하는 데 특히 효과적이다.
2. 보조 권장 사항 (점 수준): 미세하게 조정된 점 수준의 차이가 필요한 경우, **클러스터링 정확도 (ACC)**를 권장한다. 이는 잘 문서화되어 있고, 행동 분석이 완료되었으며, 접근 가능한 소프트웨어가 지원된다.
3. 정규화를 위한 대안: 큰 클러스터를 선호하지 않는 정규화된 점수가 필요한 경우, **페어-셋 지수 (PSI)**를 제안한다.
4. 주의 사항:
   • NMI와 ARI를 사용할 수는 있으나, 그들의 특정 편향(NMI는 많은 클러스터 수, ARI는 불균형한 크기)을 인지해야 한다.
   • 랜드 지수는 명시적으로 권장되지 않는다.

이 연구의 의의는 추상적이고 해석하기 어려운 점수에서 벗어나, 클러스터링 성능에 대해 명확하고 실행 가능한 통찰력을 제공하는 지표로 초점을 전환했다는 데 있으며, 특히 클러스터 수준 평가를 위한 견고하고 설명 가능한 표준으로서 중심점 지수를 옹호한다.