k-d 트리는 kNN 검색에 효율적입니다. k 가장 가까운 이웃 검색

Question

k- 트리에서 10 차원 데이터를 검색하려면 k 개의 가장 가까운 이웃 검색을 수행해야합니다.

그러나 문제는

는 KD 나무에 대해이 정상입니까 내 알고리즘은 K> 1만큼 2000X와 같은 느린 K = 1 매우 빠르지 만 있음 (K = 2,5,10,20,100)이다, 또는 나는 무엇인가 worng하고있다?

Answer 1

글쎄, 주로 특정 구현 및 데이터 세트에 따라 다릅니다.

균형이 잘 맞지 않는 나무는 필요한 것보다 더 많은 데이터를 검색해야한다는 것을 의미합니다. 나무가 잘 지어 졌는지 확인하십시오.

또한 k 이웃을 찾는 방법에 따라 달라질 수 있습니다. 알고리즘이 가장 가까운 이웃에 대한 트리를 검색하여 저장 한 다음 가장 가까운 두 번째를 검색하고 저장하는 경우 매우 효율적으로 검색을 수행하지 않습니다. 대신 가장 가까운 이웃들과 범프 포인트의 실행 목록을 목록에서 찾아 트리를 가로 지르는 더 가까운 것들을 찾으십시오. 이렇게하면 k 시간 대신에 한 번 검색하면됩니다.

어느 쪽이든, 코스를 진행하는 것처럼 보입니다. 교수님, TA 또는 급우와 이야기하여 결과가 일반적인 지 확인하십시오. 는 ACM 18 (9), 9 월 통신 :

Answer 2

나는이 질문에 대한 답이 알고 있지만, KNN에 대한 자세한 사항을 위해 K-D 나무와 검색 (514 1975) 벤틀리를 참조하십시오.