최근접 이웃 분류(K-nearest neighbors classification)
새 점과 가장 가까운 k개의 예를 찾아 다수결로 이름표를 정하는 분류 방법. 예를 모두 기억해 둘 뿐 따로 학습하지 않고, 무엇을 '가깝다'고 할지는 거리 함수(metric)가 정한다.
파랑과 노랑 두 종류의 점 100개가 있습니다. 두 품종의 꽃을 두 가지 치수로 잰 것이라고 생각해도 좋습니다. 이름표가 없는 새 점 Q를 끌어 보세요. Q와 가장 가까운 k =
이것이 k-최근접 이웃 분류의 전부이고, 예로부터 규칙을 찾는 기계 학습(machine learning)의 가장 단순한 방법입니다. 규칙을 따로 배우지 않고 예를 모두 기억해 두었다가, 물어볼 때마다 가까운 예들에게 투표를 시킵니다. 배경의 작은 점들은 평면 전체의 답, 곧 결정 영역입니다. k = 1이면 경계가 들쭉날쭉하고, 반대편 무리 안에 섞인 점 하나하나가 제 둘레에 작은 섬을 만듭니다. 이때 경계는 예들이 만드는 보로노이 다이어그램(Voronoi diagram)의 칸 경계를 이어 붙인 것입니다.
섬이 많다고 좋은 것이 아닙니다. 예로 쓴 점은 자기 자신이 가장 가까운 이웃이므로 k = 1이면 예로 쓴 점을 모두 맞힙니다(훈련 정확도 100%). 그러나 같은 분포에서 새로 뽑은 (그림에는 없는) 시험용 점 600개로 재면 훨씬 못합니다. 예에 섞인 우연까지 외워 버린 것, 곧 과적합(overfitting)입니다. 지금 k에서 훈련 정확도는
무엇을 '가깝다'고 할지가 답을 바꿉니다. 맨해튼 거리(Manhattan distance)로 바꾸면 이웃을 담는 공이 마름모가 되고 경계도 달라집니다(Lp 노름, Lp norm). 두 좌표의 단위가 다르면(키는 cm, 몸무게는 kg) 수가 큰 쪽이 거리를 혼자 정하므로, 보통은 좌표마다 평균(mean)을 빼고 표준편차(standard deviation)로 나누어 눈금을 맞추거나(표준화, standardization) 마할라노비스 거리(Mahalanobis distance)를 씁니다. 문서라면 코사인 유사도(cosine similarity), 철자라면 편집 거리(edit distance), 0과 1의 문자열이라면 해밍 거리(Hamming distance)로 이웃을 찾습니다. 방법은 그대로 두고 거리만 갈아 끼우면 됩니다.
확률(probability)로 보면 k개 이웃 가운데 노랑의 비율은 'Q 근처에서 노랑일 조건부 확률(conditional probability)'의 추정값입니다. 예가 많아질수록 k도 함께 키우되 예의 수에 비해서는 작게 두면, 큰 수의 법칙(law of large numbers)에 따라 이 추정이 참값에 다가갑니다. 그러면 분류 실력이 이론상 가장 좋은 분류기만큼 좋아집니다. 가장 좋은 분류기란 각 점에서 노랑일 참 확률을 안다고 치고 더 확률이 높은 쪽을 고르는 분류기로, 그 확률을 베이즈 정리(Bayes' theorem)로 계산하므로 베이즈 분류기라 부릅니다. 그보다 오류가 적은 분류기는 있을 수 없습니다. k = 1이라도 예가 한없이 많으면 오류율이 베이즈 분류기(Bayes classifier)의 두 배를 넘지 않는다는 것이 1967년 미국의 정보 이론가 토머스 커버와 피터 하트의 결과입니다. 방법 자체는 1951년 미국 공군 항공의학교의 보고서에서 통계학자 에벌린 픽스와 조지프 호지스가 처음 제안한 것으로 꼽힙니다.
이어지는 곳. 차원이 높아지면 거의 모든 점(almost everywhere)이 비슷하게 멀어져 '가장 가까운 이웃'이 뜻을 잃습니다(차원의 저주(curse of dimensionality)). 이름이 비슷한 k-평균 군집(k-means clustering)은 이름표 없이 무리를 찾는 전혀 다른 방법입니다. 지금까지 찾은 가장 가까운 k개를 힙(heap)에 담아 두면, 더 가까운 점이 나올 때마다 그중 가장 먼 것을 빠르게 밀어낼 수 있습니다. 예가 수백만 개면 모든 거리를 재는 대신, 공간을 미리 반씩 거듭 나눠 둔 나무 구조(k-d 트리(k-d tree) 등)에서 먼 칸을 통째로 건너뛰거나, 조금 틀려도 되는 대신 훨씬 빠른 근사 검색으로 이웃을 찾습니다. 언어 모델(language model)에 질문과 가까운 문서를 찾아 넣어 주는 검색 증강 생성(retrieval-augmented generation)은 수백만 개의 문서 벡터(vector)에서 바로 이런 근사 최근접 이웃(approximate nearest neighbor) 검색을 합니다. '이 상품을 산 사람과 비슷한 사람들이 산 것'을 보여 주는 추천도 이웃 찾기입니다.
이 개념이 나오는 긴 글
이 개념 위에 세워진 것
이 개념을 언급하는 페이지
- 조건부 확률
… 이것은 '이 근처라는 조건 아래서는 어느 쪽일 확률이 높은가'를 이웃들의 비율로 어림하는 일입니다(최근접 이웃 분류). x마다 조건부 확률 P(y \mid x) 를 정해 둔 표는 x에서 y로 가는 '확률적 함수'로 볼 수 …
- 마할라노비스 거리
… C로 곧장 가는 거리는 B를 거쳐 가는 거리보다 길 수 없다)까지 지키는 진짜 거리 함수라서,최근접 이웃 분류나 k-평균 군집에서 유클리드 거리 대신 쓸 수 있습니다. 인도의 통계학자 ⟦프라산타 찬드라 …
- k-평균 군집
… 이름은 1967년 미국의 통계학자 제임스 매퀸이 붙였습니다. 이어지는 곳. 이름표를 보고 배우는최근접 이웃 분류와 달리, k-평균은 정답 이름표 없이 데이터만 보고 구조를 찾는 비지도 학습입니다(기계 학습). …
- 차원의 저주
… 가장 먼 쌍의 차이가 겨우 13%쯤입니다. 모두가 모두에게서 비슷하게 멀면, '가장 가까운 이웃'을 찾는최근접 이웃 분류나 가까운 점끼리 묶는 k-평균 군집은 기댈 곳을 잃습니다. 까닭은 큰 수의 법칙입니다. ⟦유클리드 …
- 자카드 지수
… 상자가 겹친 넓이 ÷ 합친 넓이를 IoU라 부르며 같은 값을 씁니다. 비슷한 사용자나 문서를 찾아 추천하는최근접 이웃방법도 흔히 자카드 거리로 이웃을 고릅니다.
- 거리 함수
… 나눈 지도가 보로노이 다이어그램입니다. 새 데이터를 가장 가까운 예와 같은 무리로 분류하는 방법이최근접 이웃 분류입니다. 변수마다 단위와 퍼짐이 다르면 유클리드 거리가 공정하지 않습니다. 퍼짐까지 고려해 거리를 다시 …
- 보로노이 다이어그램
… 참값에 다가가는 리만 합과 같은 생각입니다. 새 점을 분류할 때 가장 가까운 예의 이름표를 붙이는최근접 이웃 분류(k = 1)는 보로노이 영역에 이름표를 붙이는 것과 같습니다. 영역 안의 점은 모두 그 기준점이 가장 …
- 해밍 거리
… 글자를 넣고 빼는 것도 허용하는 편집 거리로 넘어갑니다. 받은 문자열을 가장 가까운 부호어로 읽는 것은최근접 이웃찾기와 같습니다. 부호어를 얼마나 촘촘히 둘 수 있는지, 곧 잡음이 있는 통로로 오류 확률을 원하는 만큼 …
- 편집 거리
… 되기 때문입니다. 맞춤법 검사기는 틀린 단어와 편집 거리가 가장 가까운 사전 단어를 권하는데, 이것은최근접 이웃찾기입니다. 생물학에서는 DNA와 단백질 서열을 맞출 때 같은 표를 씁니다. 다만 비슷한 성질의 …
- 하버사인 공식
… 같은 타원체 공식을 씁니다. 대원 거리는 세 규칙을 지키는 거리 함수이니, 가장 가까운 공항을 찾는최근접 이웃검색이나 구면 위의 보로노이 다이어그램에도 그대로 쓰입니다.
- 단어 임베딩
… 벡터의 내적을 길이로 나눈 것이라, 수십만 낱말 가운데 가까운 이웃을 찾는 일도 결국 큰 행렬 곱셈과최근접 이웃검색입니다. 그림은 23차원을 2차원에 눌러 그린 것이라 그림 속 거리와 실제 코사인 순위가 어긋날 수 …
- 퍼셉트론
… 내놓았는데, 이것은 최소제곱 회귀를 점 하나씩 푸는 셈입니다. 예를 모두 기억해 두는최근접 이웃 분류와 달리, 퍼셉트론은 수 세 개(w₁, w₂, b)만 남기고 예를 버립니다.
- 과적합
… 멈추는 조기 종료, 학습 중 단위를 무작위로 끄는 드롭아웃도 씁니다. 과적합은 여러 모습으로 나타납니다.최근접 이웃 분류에서 k = 1이면 예로 쓴 점은 모두 맞히지만 새 점에서는 못합니다. n-그램 언어 모델에서 n을 …
- 기계 학습
… 붙습니다. '가장 가까운 예 따라 하기'는 새 예에 가장 가까운 학습 예의 이름표를 그대로 답하는 규칙(최근접 이웃 분류)이라, 학습 데이터에서는 언제나 0% 틀립니다(같은 값에 다른 이름표가 붙은 점이 없다면). 그러나 겹친 …
- 편향–분산 분해
… 상태입니다. 실제로는 f를 모르므로 세 조각을 따로 잴 수 없고, 합만 교차 검증으로 어림합니다.최근접 이웃회귀에서 이웃 k개의 y를 평균하면 x 자리가 고정일 때 분산이 정확히 \sigma^2/k 여서, k가 …
- 결정 트리와 랜덤 포레스트
… 고를 수 있고, 여기서는 '좌표 < 문턱' 꼴로 제한되어 있습니다. 좌표 대신 거리로 이웃을 찾는최근접 이웃 분류도 자료에서 바로 경계를 만드는 방법이지만, 경계의 모양은 축에 매이지 않습니다. 입력 공간을 영역으로 …
- 서포트 벡터 머신과 커널
… x - \vec x_i\rVert^2} + b , 곧 서포트 벡터들이 가까울수록 크게 던지는 가중 투표라서최근접 이웃 분류와도 닮았습니다. 무한 차원으로 옮겨도 괜찮은 까닭은 마진에 있습니다. 바프니크의 이론에 따르면 반지름 …
- 인공지능
… 맞는 직선을 찾는 최소제곱 회귀, 예/아니요의 확률을 내는 로지스틱 회귀, 가장 가까운 예를 따르는최근접 이웃 분류, 비슷한 점끼리 묶는 k-평균 군집, 자료가 가장 많이 퍼진 방향을 찾는 주성분 분석, 숨은 값을 …
- 어텐션
… 됩니다(가장 큰 점수가 하나뿐일 때). 열쇠들의 길이가 모두 같다면 이것은 방향이 가장 가까운 열쇠, 곧최근접 이웃찾기입니다. 이 그림처럼 열쇠 길이가 다르면 긴 열쇠가 유리합니다. 반대로 쿼리가 원점에 가까우면 가중치가 …
- 검색 증강 생성
… 프롬프트에 찾은 조각들을 이어 붙일 뿐 확률을 더하지는 않습니다. 수억 개 가운데 가까운 것 찾기. 정확한최근접 이웃찾기는 질문 하나마다 모든 벡터와 내적을 계산해야 합니다. 조각이 1억 개이고 차원이 1,000이면 질문 …