높은 차원 가장 가까운 이웃 검색 및 지역 감도 해싱

Question

여기에 주요 문제가 있습니다. 나는 매우 큰 데이터베이스 (25,000 정도)의 48 차원 벡터를 가지고 있으며, 각각은 0-255 범위의 값으로 채워져있다. 세부 사항은 그리 중요하지 않지만 상황을 설명하는 데 도움이 될 수 있습니다.

나는 가장 가까운 이웃을 필요로하지 않으므로 정확도 내에있는 대략적인 이웃 검색이 허용됩니다. 나는 Locality Sensitivity Hashing와 함께 놀고 있었지만 나는 매우 잃어 버렸다.

"Stable Distribution"의 기사에서 설명한대로 가능한 한 해시 함수를 작성했습니다. 여기에 코드가 있습니다.

def lsh(vector, mean, stdev, r = 1.0, a = None, b = None): 
if not a: 
    a = [normalvariate(mean, stdev) for i in range(48)] 
if not b: 
    b = uniform(0, r) 
hashVal = (sum([a[i]*vectorA[i] for i in range(48)]) + b)/r 
return hashVal 

해싱 기능이 적어도 일부는 작동하고 있습니다. 해시 값으로 점 목록을 정렬하고 목록에서 점과 인접 점 사이의 평균 거리를 계산하면 평균 거리는 무작위로 선택한 두 점에 대해 약 530의 평균 거리와 비교하여 약 400입니다.

내 가장 큰 질문은 이것입니다.

대답 : 내가 이에 대해 더 읽을 수있는 곳에 대한 제안. 내 검색은 많은 결과를 가져 오지 않았습니다. 이 방법은 정수 값 (광산이 아닌)을 출력 할 것을 제안한다. 그리고 나서이 정수 값에 대한 일치 항목을 찾으려고합니다. 일치 항목은 가능성이 가장 가까운 이웃을 나타냅니다. 나는 내 모든 포인트에 대한 해시 값의 테이블을 계산 한 다음 해시 일치에 대해 테이블을 확인해야한다고 생각하지만, 반환하는 값은 충분하지 않아서 결국 끝나지 않을 것입니다. 전혀 일치합니다. 더 많은 테스트가 필요합니다.

C : 다른 해싱 방법을 기반으로 해시 함수를 만드는 방법에 대한 지침?

Answer 1

Maby이 항목은 약간 문제이지만 데이터 집합의 차원을 줄이기 위해 PCA http://en.wikipedia.org/wiki/Principal_component_analysis을 사용해 볼 수 있습니다. numPy 용으로 설계된 PCA 모듈이 많이 있어야합니다 (예 : http://folk.uio.no/henninri/pca_module/). 이 방법은 다소 단순하며 모듈을 사용할 준비가되면 스냅 될 것입니다.

기본적으로 주어진 차원 수 내에서 분산을 최대화하여 치수 수를 줄이는 것입니다 (원하는 수를 지정할 수 있어야합니다).

B : 위키 백과 페이지 math.floor()이 hashVal에 사용하는 것을 나타낸다 : 이것은 당신이 정수를 획득하는 방법이다

Answer 2

여기에 두 가지 답변입니다.

C : 당신이 해밍 방법을 사용하려는 경우, 당신은 아주 간단하게 구현할 수 있습니다 : 각 해밍 해시 함수는 단순히 좌표 (0 ~ 47) 및 비트 수에 의해 정의된다 (0 사이 7) . 나는 내 데이터에 PCA를 수행하기 위해 파이썬의 MTP 툴킷을 사용하여 종료

bool(i & 2**b)