기술 요약: 단순 KNN 기반 이상치 탐지가 견고한 클러스터링을 달성함

문제 정의

본 논문은 표준 k-Means 클러스터링 목적 함수의 변형인 견고한 k-Means (Robust k-Means) 문제를 다룹니다. 여기서 알고리즘은 이상치의 존재를 처리해야 합니다. $n$개의 점으로 구성된 데이터셋 $X$, 클러스터 수 $k$, 이상치 예산 $z$가 주어졌을 때, 목표는 크기 $z$인 부분집합 $Z \subseteq X$(이상치) 를 식별하여 나머지 점들 ($X \setminus Z$) 의 k-Means 비용을 최소화하는 것입니다.

표준 k-Means 및 k-Median 목적 함수는 잡음에 매우 민감합니다. 심지어 단일한 먼 점 하나만으로도 해가 크게 왜곡될 수 있습니다. 견고한 k-Means 에 대한 다항 시간 상수 인자 근사 알고리즘이 존재하지만, 많은 알고리즘은 고차 다항 시간 실행 시간을 갖는 복잡한 선형 프로그래밍 완화나 제약 조건을 위반하는 (예: $k$개 이상의 중심 사용 또는 $z$개 이상의 이상치 제거) 이진 기준 근사에 의존합니다. 최근의 효율적인 알고리즘들은 종종 근선형 시간 복잡도를 달성하기 위해 이진 기준 근사를 사용합니다.

방법론

저자들은 놀랍도록 간단한 접근법을 제안합니다: 표준 k-Means 알고리즘을 적용하기 전에 K-최근접 이웃 (KNN) 휴리스틱을 전처리 단계로 사용하여 이상치를 식별하고 제거하는 것입니다.

핵심 알고리즘

본 논문은 점들의 이상치 제거 점수 부여 방식이 서로 다른 두 가지 알고리즘, OKMeans와 OKMeans2를 소개합니다.

1. OKMeans (일반 KNN):

   • 각 점 $x$에 대해 $K = \frac{c+1}{2}z$인 $K$번째 최근접 이웃까지의 거리를 계산합니다.
   • 여기서 $c$는 최적 클러스터가 크다는 가정 (구체적으로 각 최적 클러스터의 크기가 적어도 $cz$임) 과 관련된 상수입니다.
   • 가장 큰 $K$-NN 거리를 가진 $z$개의 점을 제거합니다.
   • 남은 점들에 표준 $\beta$-근사 k-Means 알고리즘을 실행합니다.

2. OKMeans2 (집계된 KNN):

   • 이상치가 함께 군집화될 수 있는 적대적 입력에 대한 견고성을 높이기 위해 일련의 이웃들까지의 거리를 집계하는 변형입니다.
   • 각 점 $x$에 대해 순위 $z+1$부터 $cz$까지의 이웃들까지의 거리 합을 계산합니다.
   • 가장 큰 집계 점수를 가진 $z$개의 점을 제거합니다.
   • 남은 점들에 표준 k-Means 알고리즘을 실행합니다.

이론적 프레임워크

분석은 다음과 같은 실용적인 가정에 의존합니다: 최적 해의 각 클러스터 크기는 어떤 상수 $c > 1$에 대해 적어도 $cz$이다. 이 가정은 정상 데이터가 이상치 수에 비해 상당한 그룹을 형성하는 실제 시나리오를 반영합니다. 이 가정 하에서 저자들은 KNN 기반 제거 단계가 견고한 k-Means 문제를 표준 k-Means 문제로 상수 인자 축소를 제공함을 증명합니다.

구체적으로:

• OKMeans는 $\Phi(c)$-근사 축소를 달성합니다. 이전 연구에서 일반적인 가정인 $c=3$인 특정 경우, 근사 비율은 9입니다.
• OKMeans2는 $\Psi(c)$-근사 축소를 달성합니다. $c=3$인 경우, 비율은 약 5.98로 개선됩니다.

중요하게도, 이러한 방법들은 많은 기존 효율적 알고리즘이 요구하는 이진 기준 완화와 달리 문제의 엄격한 제약을 준수합니다: 정확히 $k$개의 중심을 사용하고 정확히 $z$개의 이상치를 제거합니다.

주요 기여

1. KNN 에 대한 이론적 보장: 본 논문은 올바르게 매개변수화되었을 때 (즉, $K$를 $z$에 선형적으로 스케일링할 때) 고전적인 KNN 휴리스틱이 견고한 k-Means 에 대해 강력한 근사 보장을 제공함을 보여주는 최초의 엄밀한 이론적 분석을 제공합니다. 이는 이상치 탐지 휴리스틱과 견고한 클러스터링 이론 간의 간극을 메웁니다.
2. 엄격한 제약 조건 준수: $O(k)$개의 중심을 사용하거나 $(1+\epsilon)z$개의 이상치를 제거할 수 있는 이전의 효율적 알고리즘 (예: TIKMeans) 과 달리, 제안된 방법은 상수 인자 근사 보장을 유지하면서 $k$와 $z$ 제약 조건을 엄격히 준수합니다.
3. 개선된 근사 비율: 제안된 OKMeans2 변형은 $c=3$ 가정 하에서 근사 비율을 9 에서 5.98로 개선하여, 제약을 엄격히 준수하는 방법들 중 이전까지 알려진 가장 좋은 축소 결과를 능가합니다.
4. 코어셋을 통한 확장성: 대규모 데이터셋에서 정확한 KNN 거리를 계산하는 $O(dn^2)$의 복잡성을 해결하기 위해 저자들은 방법을 코어셋 (coreset) 구성과 통합합니다. 이를 통해 실행 시간을 근선형 시간인 $O(dkn \log n)$으로 줄여 수백만 개의 점까지 확장 가능한 접근법을 가능하게 합니다.

실험 결과

저자들은 500 만 개까지의 점으로 구성된 네 가지 실제 데이터셋 (SKIN, SUSY, SHUTTLE, KDDFULL) 에서 OKMeans 와 OKMeans2 를 평가했으며, TIKMeans, IKMeans, RobustKMeans++, NKMeans, 표준 KMeans++ 를 포함한 여섯 가지 기준선과 비교했습니다.

• 클러스터링 품질: 제안된 방법은 경쟁력 있는 클러스터링 비용을 달성하여 종종 정교한 기준선과 일치하거나 능가했습니다. 특히 대규모 SUSY-10 데이터셋에서 OKMeans 는 이전 최첨단 방법 (TIKMeans) 을 개선했습니다.
• 실행 시간 효율성: KNN 기반 접근법은 뛰어난 확장성을 보여주었습니다. SUSY-10 과 같은 대규모 데이터셋에서 OKMeans 는 TIKMeans (약 89.2 초) 와 RobustKMeans++ (약 74.1 초) 보다 훨씬 빠르게 (약 12.9 초) 실행되면서도 높은 해의 품질을 유지했습니다.
• 매개변수 민감도: 방법론은 매개변수 $c$의 선택 (적당한 범위 내에서) 에 대해 견고한 것으로 나타났습니다. 그러나 실험은 이상치 탐지의 표준인 $K$에 대한 작고 고정된 상수를 선택하는 것이 견고한 클러스터링 목적에는 비최적일 수 있다는 이론적 통찰을 확인시켰습니다. $K$는 이상치 예산 $z$에 따라 스케일링되어야 합니다.

중요성과 주장

본 논문은 단순한 KNN 기반 휴리스틱이 견고한 클러스터링에 놀라울 정도로 효과적일 수 있다고 주장하며, 확장 가능하고 고품질의 견고한 클러스터링을 위해 복잡한 샘플링 전략이나 이진 기준 근사가 필요하다는 관념에 도전합니다.

저자들은 다음과 같은 점을 강조합니다:

• 이상치 탐지와 견고한 클러스터링 사이에는 이전에는 간과되었던 직접적인 연결이 존재합니다.
• "대형 클러스터" 가정으로 이론적으로 기반을 둔 KNN 휴리스틱은 더 복잡한 알고리즘에 대한 실용적이고 효율적인 대안을 제공합니다.
• 결과는 이상치 탐지 및 클러스터링 기법을 연결하는 새로운 방향을 시사하며, 실제에서 견고한 클러스터링 알고리즘 설계를 단순화할 가능성을 제시합니다.

본 논문은 현재 분석이 엄밀하지는 않지만, 이상치 탐지와 견고한 클러스터링 프레임워크를 통합하는 향후 연구의 기초를 마련했다고 결론지으며 끝납니다.