k-NN과 ANN

추천 시스템, 콘텐츠 기반 정보 검색, 시맨틱 분석 등 다양한 분야에서 '유사성(similarity)'에 기반한 데이터 탐색이 중요해지고 있다. 유사성 기반 탐색의 기본적인 접근 방식으로 k-최근접 이웃(k-Nearest Neighbors, k-NN)과 근사 이웃 탐색(Approximate Nearest Neighbor, ANN)이 있다. 본 글에서는 k-NN의 원리 및 한계를 이해하고, 이의 대안으로 ANN의 개념과 기술적 특징을 설명한다.

1. k-Nearest Neighbor(k-NN)

1-1 k-NN의 정의 및 원리

k-NN은 데이터 포인트 간 거리를 기반으로 동작하는 가장 기본적인 알고리즘 중 하나다. 지도 학습(supervised learning)에서 특정 데이터 포인트와 거리가 가장 가까운 'k'개 이웃 데이터, 즉 최근접 이웃(nearest neighbor)을 식별하고, 이들의 레이블 데이터를 이용하여 해당 포인트의 클래스를 분류하거나 값을 예측한다.

k-NN의 핵심 연산인 가장 가까운 k개 이웃 찾기는 분류나 예측 뿐아니라 그 자체로 유사성 검색 문제에 직접 적용된다. 이것은 전체 데이터셋 내에서 가장 유사한, 즉 가장 거리가 가까운 상위 k개 데이터를 탐색하는 작업을 의미한다. 두 데이터 포인트 간 거리가 가까울수록 높은 유사도를 갖는다고 간주한다.

1-2 유사성 측정: 거리 계산

k-NN은 데이터 포인트 간 거리 또는 유사도를 정량적으로 측정하여 이웃 관계를 정의한다. 데이터 특성에 따라 적합한 측정 지표를 선택할 수 있다. 예를 들어 색상 정보는 RGB(Red, Green, Blue) 값으로 표현 가능하며, 이는 3차원 벡터 $(R, G, B)$로 간주하고 거리를 계산해서 색상의 유사도를 판단할 수 있다.

[예시] 유클리드 거리를 이용한 색상 벡터 거리 계산

• Red: $(255,0,0)$
• Orange: $(255,127,0)$
• Violet: $(128,0,128)$
  유클리드 거리는 $d$차원 공간상 두 점 $q, p$에 대해 다음과 같이 계산한다.

$$
\text{Distance}(p, q) = \sqrt{\sum_{i=1}^{d} (p_i - q_i)^2}
$$
Distance(Red, Orange)

$$
\sqrt{(255-255)^2 + (0-127)^2 + (0-0)^2} = 127
$$
Distance(Red, Violet)
$$
\sqrt{(255-128)^2 + (0-0)^2 + (0-128)^2} \approx 180.3
$$
Red와 Orange간 거리는 127, Red와 Violet간 거리는 약 180.3이다. 거리가 짧을수록 높은 유사도를 의미하므로 이 예시에서는 Orange가 Violet보다 Red에 더 유사한 색이라고 판단한다.

1-3 주요 거리/유사도 계산법

k-NN 탐색 시 데이터 특성에 맞게 다음과 같은 다양한 거리 또는 유사도 계산을 사용할 수 있다.

• Euclidean Distance: $L_2$
• Manhattan Distance: $L_1$
• Cosine Similarity: 벡터의 각도를 이용한 유사도 (크기보다 방향이 중요할 때)
• Hamming Distance
• Jaccard Similarity

1-4 k-NN의 장점

• 원리가 단순하고 직관적이어서 이해 및 구현 용이하다.
• 별도 모델 학습 과정이 필요없는 비모수적(non-parametric) 방법이다. (Lazy Learning)
• 데이터셋의 크기가 작을 경우 효과적으로 작동할 수 있다.
• 다양한 거리/유사도 척도 문제를 특성에 맞게 선택하여 적용할 수 있다.

1-5 k-NN의 한계

단순함에도 불구하고 k-NN의 데이터 규모와 복잡성이 증가함에 따라 다음과 같은 명확한 한계를 갖는다.

1. 계산 복잡도 및 검색 속도

• 새로운 쿼리에 대해 최근접 이웃을 찾으려면 저장된 모든 데이터 포인트와 거리를 계산해야 한다.(무차별 대입 방식, brute force search)
• 데이터셋 크기가 $n$이고 차원이 $d$일 때, 단일 쿼리에 대한 검색 시간 복잡도는 $O(nd)$이다.
• $n$ 또는 $d$가 증가함에 따라 검색 시간이 선형적으로 증가하므로 대규모 또는 고차원 데이터셋에서는 검색 효율성이 현저히 저하된다.

  2. 차원의 저주(Curse of Dimensionality)

• 데이터 차원 $d$가 높아지면(고차원 벡터 공간), 데이터 포인트들이 서로 멀리 떨어져 희소하게 분포하는 경향이 나타난다.
• 이로 인해 최근접 이웃과 그렇지 않은 이웃 간 거리 차이가 상대적으로 줄어들어 거리 측정 변별력이 약화되고 성능이 저하될 수 있다.

  3. 데이터 스케일 의존성

• k-NN 거리 계산은 각 피처(차원)가 사용하는 값의 범위에 따라 결과가 달라진다. 값의 범위가 큰 피처는 작은 피처에 비해 수치적인 차이가 더 크게 나타날 수 있다. 예를 들어 유클리드 거리 계산 시 각 피처 값이 차이를 제곱하여 더하는데, 스케일이 큰 피처에서 발생한 값의 차이가 전체 거리 값에 더 지배적인 영향을 미치게 된다. 결과적으로 스케일이 큰 특정 피처의 중요도가 다른 피처들에 비해 과대평가될 수 있다.
• 따라서 k-NN 적용 전 데이터 정규화 또는 표준화와 같은 스케일링 전처리 과정이 요구된다.

  4. 이상치 및 k 값 민감성

• 이웃 후보군에 이상치가 포함되어 있을 경우 결과 정확성에 부정적인 영향을 미칠 수 있다.
• k값의 선택은 이상치 영향과 지역적 패턴 보존 사이의 트레이드오프를 갖는다. k가 크면 이상치에 덜 민감해지지만 지역 구조 정보가 희석될 수 있고, k가 작으면 이상치 및 노이즈에 민감해진다.
• 여기서 지역 패턴이란 전체 데이터 중 가까운 이웃끼리 만들어내는 특성을 말한다.

2. 근사 이웃 탐색(Approximate Nearest Neighbor, ANN)

2-1. ANN의 필요성 및 정의

k-NN의 주된 한계는 대규모, 고차원 데이터에서 $O(nd)$ 검색 시간 복잡도다. 실시간 환경에서는 이런 계산 비용이 실용성(?)을 저해하는 주요 요인이다.
ANN은 k-NN의 확장성 및 속도 문제를 해결하기 위해 제안된 방법을 통칭한다. ANN은 정확성을 일정 수준 허용하는 대신 검색 속도를 향상시키는 것을 목표로 한다. 즉, 100% 정확한 최근접 이웃을 보장하는 대신 실제 최근접 이웃과 매우 유사할 확률이 높은 근사 이웃을 빠른 시간에 찾는 데 집중한다.

2-2. ANN의 의미

ANN은 다음과 같은 이점을 제공한다.

1. 속도 향상: $O(nd)$ 복잡도를 극복하고 다수 ANN 알고리즘은 $O(log n)$ 수준의 준선형 검색 시간을 달성하여 검색 속도를 개선한다.
2. 확장성: 대규모 데이터셋 및 고차원 벡터 환경에서도 효율적인 유사성 검색이 가능하다.
3. 실용성: 대규모 벡터 데이터 기반의 시맨틱 검색, 추천 시스템 등을 현실적으로 구현 가능하게 하는 핵심 기반 기술이다.

2-3. ANN의 작동 원리: 인덱싱

ANN 알고리즘 핵심은 인덱싱 구조를 사전에 구축하여 검색 시 전체 데이터와 비교 연산을 최소화하는 데 있다. 인덱스는 고차원 벡터 공간을 효과적으로 탐색하기 위해 설계된 자료 구조다. 주요 인덱싱 전략은 다음과 같이 분류할 수 있다.

• 공간 분할 기반: 트리를 이용하거나(k-d 트리, Annoy 등) 해싱 기법(Locality-Sensitive Hashing, LSH)을 이용하여 전체 벡터 공간을 여러 하위 영역으로 분할하고, 쿼리와 관련성이 높은 영역 중심으로 탐색한다.
  • 비교적 직관적이며 트리 기반 접근법으로 관리가 쉽지만 고차원에서 성능 저하 가능성이 있다.
• 그래프 기반: 데이터 포인트를 노드(node)로, 인접 이웃 관계를 엣지(edge)로 표현하는 근접성 그래프(proximity graph)를 구축한다(HNSW, NSG 등). 검색은 그래프 탐색(graph traversal)을 통해 효율적으로 수행된다. 최근 우수한 성능으로 널리 활용된다.
  • 높은 정확도와 효율성 제공하지만 인덱스 구축 시간이 비교적 길고 복잡하다.
• 압축/양자화 기반: 벡터 데이터를 저차원 표현으로 압축하거나 이산적인 코드로 변환(Product Quantization, PQ 등)하여 메모리 사용량을 줄이고 거리 계산 속도를 가속화한다. 이 과정에서 일부 정보 손실이 발생할 수 있다.
  • 저장공간 및 계산 속도 면에서 유리하나 정보 손실로 인한 정확도 저하 위험이 있다.

    2-4. ANN의 주요 트레이드오프

ANN 기법을 활용할 때는 다음과 같은 요소들 간의 트레이드 오프를 고려해야 한다.

• 정확도(리콜) vs. 속도: 일반적으로 더 높은 검색 정확도(리콜: 실제 k개의 최근접 이웃 중 찾은 비율)를 요구할수록 검색 속도가 저하되는 경향이 있다.
• 인덱스 구축 시간 vs. 검색 시간: 고성능 검색을 위한 복잡한 인덱스는 구축하는 데 더 많은 시간을 소요할 수 있다. 데이터 갱신 빈도와 검색 속도 요구사항을 고려하여 균형점을 찾아야 한다.
• 메모리 사용량: 인덱스 구조는 원본 데이터 외 추가적인 메모리 공간을 필요로 한다. 인덱스의 종류와 파라미터 설정에 따라 메모리 요구량이 달라진다.

  2-5. ANN 응용

  ANN 기술은 다양한 데이터 집약적 응용 분야에서 활용된다.
• 검색: 시맨틱 검색, 문서 유사도 분석 등.
• 추천 시스템: 사용자 또는 아이템 간 유사성 기반 추천.
• 컴퓨터 비전: 이미지 검색(CBIR), 객체 인식, 특징점 매칭.
• 자연어 처리: 단어/문장 임베딩 유사성 분석, 기계 번역.
• 데이터 마이닝: 중복 데이터 탐지, 이상 탐지, 클러스터링 지원.

3. 결론

k-NN은 유사성 검색의 기본 원리를 제공하는 직관적인 알고리즘이나, 대규모 및 고차원 데이터 환경에서는 $O(nd)$ 시간 복잡도로 인해 실용성에 한계가 있다. ANN은 이러한 한계를 극복하기 위해 정확성을 일부 절충하여 속도와 확장성을 극대화하는 접근법이다. 효율적인 인덱싱 기법을 통해 준선형 검색 시간 복잡도를 달성함으로써, ANN은 현대의 다양한 데이터 중심 응용 시스템에서 필수적인 기술 요소로 자리 잡았다. 따라서 응용 문제의 특성(데이터 규모, 차원, 요구 정확도 및 속도)을 고려하여 k-NN 또는 적합한 ANN 기법을 선택하고 관련 트레이드오프를 최적화하는 것이 중요하다.

참고 자료

• Amazon Web Service Korea Youtbue. "Amazon OpenSearch Service KNN 기능을 사용한 유사 이미지 검색 구현하기"
• Elastic Blog. "Understanding the approximate nearest neighbor (ANN) algorithm"