기술 요약: 적응형 평균 이동(Adaptive Mean Shift)을 위한 국소 클러스터 카디널리티 추정

문제 정의

본 논문은 적응형 평균 이동(Adaptive Mean Shift, AMS) 클러스터링의 파라미터 선택 문제를 다룹니다. 전통적인 AMS 알고리즘은 가중 평균을 계산하기 위한 국소 이웃을 정의하기 위해 대역폭(bandwidth) 파라미터에 의존합니다. 기본적인 AMS는 고정된 전역 대역폭을 사용하는 반면, 적응형 변형 모델들은 국소 밀도 추정(예: 커널 밀도 추정 또는 KDE)을 활용하여 이 파라미터를 국소적으로 조정하려고 시도합니다.

저자는 기존 접근 방식에서 두 가지 주요 한계점을 식별했습니다:

1. 규모 의존성(Scale Dependence): 많은 방법론이 데이터셋 전체에 대해 선택된 길이 상수(대역폭)를 필요로 하며, 이는 데이터의 스케일에 민감하게 만듭니다.
2. 국소성 및 노이즈(Locality and Noise): 표준 KDE는 고정된 크기의 이웃 내에서 밀도를 측정합니다. 이 이웃이 너무 크면 먼 클러스터의 점들이 포함되어 국소 추정을 방해하며, 너무 작으면 클러스터 구조를 놓칠 수 있습니다. 또한, 특히 작은 클러스터나 고차원 데이터에서 오버스무딩(oversmoothing)이 발생할 수 있는 KDE는 대역폭 파라미터를 선택하는 것이 까다롭습니다.

본 논문은 점과 그 이웃들 사이의 거리 분포로부터 직접 **카디널리티(cardinality, 점의 개수)**를 추정하는 방법을 제안합니다. 이렇게 추정된 카디널리티는 전역 대역폭이나 고정된 클러스터 개수를 사전에 정의할 필요 없이, 평균 이동 과정의 대역폭과 커널 반경을 도출하는 데 사용됩니다.

방법론

제안된 알고리즘은 클러스터 카디널리티 추정, 적응형 평균 이동, 이상치 분류의 세 가지 주요 단계로 작동합니다.

1. 국소 클러스터 카디널리티 추정

핵-혁신은 모든 다른 점들과의 거리 분포를 사용하여 점 $x_i$의 국소 클러스터 카디널리티($\hat{n}$)를 추정하는 것입니다.

• 거리 분포: 각 점에 대해 다른 모든 점들과의 거리를 정렬합니다. 저자는 다봉형(multimodal) 데이터셋에서 이 분포가 이봉형(bimodal)을 띨 것이라고 가설을 세웁니다. 즉, 첫 번째 모드는 동일한 국소 클러스터 내의 점들 사이의 거리를 나타내고, 두 번째 모드는 다른 클러스터에 있는 점들 사이의 거리를 나타냅니다.
• $\gamma$ 함수: 이 두 모드 사이의 경계(최소 밀도의 "골짜기")를 찾기 위해, 논문은 다음과 같은 함수 $\gamma$를 도입합니다:
  $$\gamma(y^{(k)}) = \frac{s^2}{(\bar{y} - y^{(k)})^2}$$
  여기서 $y^{(k)}$는 $k$번째 정렬된 거리, $\bar{y}$는 처음 $k$개 거리의 평균, $s^2$은 그들의 분산입니다.
• 추정 로직: 알고-리즘은 정의된 탐색 창($minBoundary$에서$maxBoundary$사이) 내에서$\gamma$를 최소화하는 순위$k$를 찾습니다. 이 최솟값은 추정된 클러스터 카디널리티$\hat{n}_i$에 해당합니다.
• 주요 특성:
  • 규모 불변성(Scale Invariance): $\gamma$ 함수는 분산을 거리의 제곱으로 나눈 비율입니다. 데이터를 양의 상수로 곱해도 $\gamma$는 변하지 않으므로, 길이 척도 상수가 필요하지 않습니다.
  • 국소성(Locality): 순위 $k$에서의 $\gamma$ 값은 오직 $k$개의 가장 가까운 거리에만 의존합니다. 더 멀리 떨어진 점들은 국소 클러스터 경계의 추정에 영향을 미치지 않습니다.

2. 적응형 평균 이동

각 점에 대해 $\hat{n}_i$가 추정되면, 이 값들이 평균 이동 과정을 주도합니다:

• 커널 정의: 절단된 가우시안 커널 $K(x; h, \omega)$가 사용됩니다.
  • 대역폭 ($h$): 추정된 카디널리티 $\hat{n}_i$로 제한된 국소 거리 분포의 표준 편차로 계산됩니다.
  • 임계값 ($\omega$): $\hat{n}_i$번째 정렬된 거리로 설정되어, 커널을 추정된 클러스터 반경에서 효과적으로 절단합니다. 이 반경을 벗어나는 점들은 가중치를 0으로 받습니다.
• 고차원 적응: 고차원에서 거리를 상쇄하여 자기 자신과의 거리(0)가 가중치를 지배하거나 수치적 불안정성을 초래하는 것을 방지하기 위해 수정된 커널(식 6)이 제안되었습니다.
• 점진적 영역 증가: 클러스터 경계 근처의 점들에 대한 카디널리티 추정의 양의 편향(positive bias)을 완화하기 위해, 반복적인 평균 이동 단계 동안 고려되는 점의 개수($n_k^*$)를 점진적으로 증가시켜 가중 평균이 실제 모드로 수렴하도록 합니다.

3. "나쁜" 추정치 처리

카디널리티 추정이 탐색 경계에 도달하는 점들(예: 분포가 모호한 클러스터 사이의 점들)은 "나쁜(bad)" 것으로 분류됩니다. 이 점들은 반복적인 평균 이동에서 제외됩니다. 마지막 단계에서 이들은 해당 클러스터의 대역폭에 의해 가중치가 부여되어 가장 가까운 클러스터 모드에 할당됩니다.

주요 기여

1. 카디널리티 기반 파라미터화: 본 논문은 전역 대역폭 파라미터의 필요성을 제거하고, 추정된 국소 클러스터 카디널리티로부터 직접 대역폭과 커널 반경을 도출하는 방법을 도입했습니다.
2. $\gamma$ 함수: 거리 분포에서 두 모드 사이의 최소 밀도를 감지하기 위한 새롭고 규모 불변적이며 국소적인 함수를 제공하여, KDE의 대역폭 선택 문제를 피했습니다.
3. 규모 및 클러스터 독립성: 알고리즘은 클러스터 개수를 입력값으로 요구하지 않으며, 데이터의 스케일 변화에 불변합니다.
4. 절단된 커널 전략: 커널을 추정된 클러스터 반경에서 절단함으로써, 먼 점들(다른 클러스터의 점들)이 국소 가중 평균을 오염시키지 않도록 보장합니다.

실험 결과

저자는 두 가지 벤치마크 세트에서 알고리즘을 평가했습니다:

1. Ren et al. (2014) WAMS와의 비교:

   • 9개의 데이터셋(Iris, Yeast, Steel, USPS, CTG, Letter, Image, Pen, Wave)에서 테스트되었습니다.
   • 제안된 방법은 9개 데이터셋 중 7개에서 WAMS(Weighted Adaptive Mean Shift) 알고리즘보다 높은 Rand Index를 달성했습니다.
   • 이 7개의 데이터셋에서 모든 발표된 베이스라인(WAMS, k-means, EM, Single-linkage)보다 우수한 성능을 보였습니다.
   • 나머지 두 데이터셋(USPS, Image)에서도 경쟁력 있는 성능을 보였으나, 저자는 차이를 완전히 조사하기 위해 해당 베이스라인들의 구체적인 구현 세부 사항에 접근할 수 없었다고 언급했습니다.

2. Gagolewski (2022) 벤치마크와의 비교:

   • 8개의 UCI 데이터셋(Ecoli, Glass, Ionosphere, Sonar, Statlog, WDBC, Wine, Yeast)에서 테스트되었습니다.
   • 알고리즘은 Rand Index가 방법론 간의 차이를 명확히 보여주는 데이터셋에서 확립된 방법들(GIc, EM, k-means, Spectral, Birch)과 경쟁력 있는 성능을 보였습니다.
   • 한계: 가장 큰 클러스터가 데이터의 50% 이상을 차지할 때 알고리즘이 어려움을 겪습니다(기본 maxBoundary는 $0.5n$). 이러한 경우(예: Ionosphere, Sonar, WDBC), 알고리즘이 다수 클래스를 단일 클러스터로 표현하는 데 실패하여 낮은 Rand index를 기록합니다. 저자는 maxBoundary 파라미터를 조정하면 이러한 특정 데이터셋에서 결과를 개선할 수 있지만, 이는 데이터 분포에 대한 지식을 필요로 한다고 언급했습니다.

의의 및 주장

본 논문은 제안된 알고리즘이 적응형 평균 이동 계열 내에서 경쟁력이 있으며, 클러스터 개수를 입력값으로 요구하지 않는다는 점에서 독특한 장점을 제공한다고 주장합니다.

• 겸손함: 저자는 카디널리티 추정기가 "첫 번째 기능적 프로토타입"이자 "진행 중인 작업"임을 인정합니다. 또한 WAMS 알고리즘과의 비교가 적응형 평균 이동 계열의 단 하나의 멤버만을 다루고 있음을 밝히며, 더 광범위한 비교가 필요하다고 말합니다.
• 규모 불변성: 저자는 추정기의 규모 불변성이 데이터 스케일을 위한 길이 상수를 선택할 필요를 없애준다는 점에서 중요한 이론적 개선임을 강조합니다.
• 국소성: 이 방법은 엄격한 국소성을 특징으로 하여, 국소 클러스터의 추정이 먼 데이터 포인트에 의해 방해받지 않도록 합니다.
• 향후 과제: 논문은 카디널리티 추정 작업 자체가 참신하며 추가 연구의 가치가 있다고 제 제안합니다. 향후 개선 사항으로는 고정된 경계를 알고리즘적 모드 찾기(예: 1D mean shift)로 대체하거나, maxBoundary 파라미터를 완전히 데이터 주도적으로 정교화하는 것이 포함될 수 있습니다.

결론적으로, 본 논문은 거리 분포를 활용하여 국소 클러스터 파라미터를 자동으로 결정하는 새로운 적응형 평균 이동 접근법을 제시하며, 규모 불변성과 국소성이라는 이론적 특성을 유지하면서 표준 벤치마크에서 강력한 경험적 성능을 입증했습니다.