가까운 이웃의 메트릭 유효성

Question

kNN 알고리즘은 거리 공리를 따라야합니까? 실패한 메트릭을 적용하면 어떻게됩니까?

d(a,c) < d(a,b) + d(b,c) 

KMeans 클러스터링에 대해 같은 질문이 있습니까?

Answer 1

kNN은 작은 값이 더 가까운 것을 의미하는 근접 조치 만 필요합니다. 이는 kNN이 새로운 관측치를 트레이닝 예제와 비교하여 가장 가까운 k 개의 k (가장 근접한 값을 갖는 첫 번째 k)를 찾는 것이기 때문입니다. kMeans의 경우 use search.

EDIT :가 KNN 그다지 삼각형 방정식이 필요하더라도, 그것은 N은 트레이닝 세트의 크기이며, m은 평가 세트의 크기가 O (N 개 *의 m) 시간에서 실행 . 최적화는 대개 삼각형 방정식을 유지해야하는데, 그 중 일부는 제약 조건이 더 많습니다 (예 : k-d 나무는 유클리드 공간에서만 작동합니다). 자세한 내용은 this question을 참조하십시오.