KD- 나무와 누락 값 (벡터 비교)

Question

나는 벡터를 저장하고 사용자가 사용자의 쿼리 벡터에 가장 유사한 n 개의 벡터를 찾을 수있는 시스템을 가지고 있습니다. 즉, 사용자가 벡터를 제출하면 (이 벡터를 쿼리 벡터라고 부름) 시스템이 "여기에 n 개의 가장 유사한 벡터가 있습니다."라고 말합니다. 나는 KD-Tree를 사용하여 유사한 벡터를 생성하고 모든 것이 잘 작동하지만 더 많이하고 싶다. 사용자가 완전한 벡터 (값이없는 벡터)를 제출하지 않아도 n 개의 가장 유사한 벡터의 목록을 제시하고자합니다. 즉, 사용자가 3 차원 벡터를 제출하면 여전히 저장 한 n 개의 가장 가까운 벡터 (저장된 벡터는 11 차원 임)를 찾고자합니다.

나는 분명 솔루션의 몇 가지있다,하지만 난 둘 중 하나는 아주 좋은 것 잘 모르겠어요 :

1. 각 사용자가 검색됩니다 차원의 가장 인기있는 하위 집합을 사용하여 구축 된 여러 KD-나무 만들기 . 즉, 사용자가 차원, x, y, z 차원의 쿼리 벡터를 제출하면 x, y, z 차원의 벡터 만 포함 된 이미 작성된 KD 트리에 해당 쿼리를 일치시킵니다.

2. 사용자가 누락 값이있는 쿼리 벡터를 제출하고 쿼리 벡터를 점 제품과 같은 것을 사용하여 하나씩 (DB의 테이블에 저장된) 벡터와 비교할 때 KD- 트리를 무시합니다.

이것은 일반적인 문제 일 수 있습니다. 도와 주셔서 감사합니다.

Answer 1

다음과 같은 결과를 얻었습니다. 사용자가 쿼리 벡터에 차원이없는 경우 값을 지정하지 않으면 API에서 내 일치 범위를 조정하여 어떤 값과도 일치하도록했습니다. .

Answer 2

두 번째 옵션은 원하는 것을위한 합리적인 솔루션처럼 보입니다.

값이있는 경우 가장 중요한 (또는 평균 또는 예상되는 값) 값으로 누락 치수를 채울 수도 있습니다.

Answer 3

첫 번째 해결책은 검색어에 대해 가장 빠를 수 있습니다 (나무 건축물은 마음에 들지 않는 방향의 스플릿을 고려하지 않으므로). 그러나 많은 메모리를 사용하게됩니다. 그리고 나무를 반복해서 재건해야한다면 느려질 수 있습니다.

두 번째 옵션은 몇 가지 점이 없으면 매우 느립니다. 그렇다면 아마도 kd 트리가 필요 없을 것입니다.

가장 좋은 해결책은 작업중인 코드를 손에 넣는 것입니다. 아마도 가장 가까운 이웃 검색은 나무 잎의 점과 쿼리 벡터 사이의 거리를 계산합니다. 당신은 포인트와 쿼리 벡터가 다른 크기 인 경우를 처리하기 위해 이것을 수정할 수 있어야합니다. 예 : 트리의 점이 3D로 주어졌지만 쿼리 벡터의 길이가 2 인 경우 점 (p0, p1, p2)과 쿼리 벡터 (x0, x1) 간의 "거리"는

sqrt((p0-x0)^2 + (p1-x1)^2) 

내가 링크 된 자바 코드를 파고 들지는 않았지만, 도움이 필요할 경우 변경 사항이 필요한 위치를 정확하게 찾을 수 있습니다.

크리스

PS - 제곱 거리가 일반적으로 해당하기 때문에 당신이 위의 방정식에서 SQRT를 필요로하지 않을 수 있습니다.

EDIT 죄송 합니다만, 소스 코드에서 그렇게 분명한 사실을 몰랐습니다.이웃 함수의 버전을 사용해야합니다 :

nearest(double [] key, int n, Checker<T> checker) 

그리고 자신의 Checker 클래스를 구현하십시오. Euclidean 버전을 보려면 EuclideanDistance.java를 참조하십시오. 또한 다른 크기의 키를 처리 할 수 ​​있다는 것을 알고 있기 때문에 쿼리 코드가 throw하는 KeySizeException을 주석으로 처리해야 할 수도 있습니다.

Answer 4

원본 벡터가 제공하지 않는 차원의 분할 인 경우 두 가지 분기를 취하여 기존 KD 트리를 사용해 볼 수 있습니다. 이것은 무차별 검색보다 시간이 적게 걸리고 차원 하위 ​​집합에 대한 특수 트리를 유지하는 것보다 덜 어려울 수 있습니다.

당신은 N-closest 알고리즘을 적용 할 필요가 있습니다. (더 이상의 정보가 없으면 ...), 거리에 대해서는 소스에서 제공 한 요소의 제곱의 합계를 사용합니다 벡터.