Locality Sensitive Hashing 의 실현

세 가지 계산 가장 가 까 운 방법의 비교:

가장 간단 하고 거 친 방식 은 한 점 과 다른 모든 점 의 거 리 를 계산 하여 가장 가 까 운 것

을 취 하 는 것 이다.

kd - trees 는 훈련 데 이 터 를 이 진 트 리 의 데이터 구조 로 저장 하여 검색 시간 을 줄 이 고 고 차원 공간 에서 잘 표현 하지 못 하 며 계 산 량 도 적지 않다 는 단점 이 있다.

LSH, Locality Sensitive Hashing 은 데이터 가 있 는 공간 에 초 평면 을 무 작위 로 배치 하여 전체 데이터 세트 를 hash 하 는데 최종 목적 도 검색 시간 을 줄 이 는 것

이다.
LSH 의 실현:
워싱턴 대학 기계 학습 전문 과정 에 따라 정리 하 다.

# necessary package
import numpy as np
import graphlab  #           ，  sklearn  
from scipy.sparse import csr_matrix
from sklearn.metrics.pairwise import pairwise_distances
import time
from copy import copy
import matplotlib.pyplot as plt

# load dataset
# dataset    ：URL, name, text
wiki = graphlab.SFrame('people_wiki.gl/')
wiki = wiki.add_row_number()

# compute tf-idf
#             document td-idf
wiki['tf_idf'] = graphlab.text_analytics.tf_idf(wiki['text'])

document 에서 추출 한 td - idf 를 계수 행렬 로 변환 합 니 다.

def sframe_to_scipy(column):
    """
     sframe       
    Convert a dict-typed SArray into a SciPy sparse matrix.
    
    Returns
    -------
        mat : a SciPy sparse matrix where mat[i, j] is the value of word j for document i.
        mapping : a dictionary where mapping[j] is the word whose values are in column j.
    """
        # create triples of (row_id, feature_id, count).
    x = graphlab.SFrame({'X1':column})
    
    # add a row number.
    x = x.add_row_number()
    # stack will transform x to have a row for each unique (row, key) pair.
    x = x.stack('X1', ['feature', 'value'])

    # map words into integers using a OneHotEncoder feature transformation.
    f = graphlab.feature_engineering.OneHotEncoder(features=['feature'])

    # We first fit the transformer using the above data.
    f.fit(x)

    # The transform method will add a new column that is the transformed version
    # of the 'word' column.
    x = f.transform(x)

    # Get the feature mapping.
    mapping = f['feature_encoding']

    # Get the actual word id.
    x['feature_id'] = x['encoded_features'].dict_keys().apply(lambda x: x[0])

    # Create numpy arrays that contain the data for the sparse matrix.
    i = np.array(x['id'])  # document id
    j = np.array(x['feature_id'])  # onehot      id
    v = np.array(x['value'])  #    tfidf 
    width = x['id'].max() + 1 
    height = x['feature_id'].max() + 1

    # Create a sparse matrix.
    #       
    mat = csr_matrix((v, (i, j)), shape=(width, height))
    # maping,      mat            
    return mat, mapping

#       
# corpus      ，   documnet ID，        id
# mapping      id           
corpus, mapping = sframe_to_scipy(wiki['tf_idf'])

corpus.shape == (59071, 547979)

훈련 LSH 모형
첫 번 째 단 계 는 무 작위 로 초 평면 을 생 성하 여 고 스 분 포 를 만족 시 키 고 초 평면 적 인 차원 과 희소 행렬 의 열 수량 이 일치 합 니 다. 두 번 째 단 계 는 document 의 벡터 와 이 초 평면 을 점 승 연산 하여 얻 은 1 차원 벡터, 벡터 중 0 이상 의 요 소 를 1 로 하고 0 이하 의 요 소 를 0 으로 하 며 얻 은 이 벡터 는 데 이 터 를 hash 할 수 있 습 니 다.

def generate_random_vectors(num_vector, dim):
    #        dim * num_vector       
    # num_vector:        
    # dim：        
    return np.random.randn(dim, num_vector)  #          
    #    

테스트 효과:

# Generate 3 random vectors of dimension 5, arranged into a single 5 x 3 matrix.
np.random.seed(0) # set seed=0 for consistent results
generate_random_vectors(num_vector=3, dim=5)
#   3    5    
>>> array([[ 1.76405235,  0.40015721,  0.97873798],
           [ 2.2408932 ,  1.86755799, -0.97727788],
           [ 0.95008842, -0.15135721, -0.10321885],
           [ 0.4105985 ,  0.14404357,  1.45427351],
           [ 0.76103773,  0.12167502,  0.44386323]])

hash 벡터 효과 테스트:

corpus[0:2].dot(random_vectors) >= 0 # compute bit indices of first two documents
>>> array([[ True,  True, False, False, False,  True,  True, False,  True,
         True,  True, False, False,  True, False,  True],
           [True, False, False, False,  True,  True, False,  True,  True,
           False,  True, False,  True, False, False,  True]], dtype=bool)

더 나 아가 이런 벡터 는 정수 로 유일 하 게 대체 할 수 있다.

Bin index                      integer
[0,0,0,0,0,0,0,0,0,0,0,0]   => 0
[0,0,0,0,0,0,0,0,0,0,0,1]   => 1
[0,0,0,0,0,0,0,0,0,0,1,0]   => 2
[0,0,0,0,0,0,0,0,0,0,1,1]   => 3
...
[1,1,1,1,1,1,1,1,1,1,0,0]   => 65532
[1,1,1,1,1,1,1,1,1,1,0,1]   => 65533
[1,1,1,1,1,1,1,1,1,1,1,0]   => 65534
[1,1,1,1,1,1,1,1,1,1,1,1]   => 65535 (= 2^16-1)

이렇게 되면 하나의 숫자 로 이 document 벡터 를 표시 할 수 있 습 니 다.

doc = corpus[0, :]  # first document
index_bits = (doc.dot(random_vectors) >= 0)
powers_of_two = (1 << np.arange(15, -1, -1))
print index_bits
print powers_of_two
print index_bits.dot(powers_of_two)

>>>[[ True  True False False False  True  True False  True  True  True False
  False  True False  True]]
[32768 16384  8192  4096  2048  1024   512   256   128    64    32    16
     8     4     2     1]
[50917]

#   document
index_bits = corpus.dot(random_vectors) >= 0
index_bits.dot(powers_of_two)

>>> array([50917, 36265, 19365, ..., 52983, 27589, 41449])

초 평면 으로 절 단 된 공간 을 통 으로 볼 수 있 고 데이터 세트 는 이 통 에 흩 어 져 있 으 며 위의 배열 은 바로 모든 통 의 ID 이다. 그러면 우리 가 데이터 점 의 가장 가 까 운 점 을 찾 아야 할 때 우 리 는 이 점 이 있 는 통 에서 찾 으 면 계산 대 가 를 줄 일 수 있다.
주의해 야 할 점 은 ID 가 서로 인접 하고 대표 적 인 통 은 공간 적 으로 서로 인접 하지 않 는 다 는 것 이다.(id 와 2 차이 가 나 는 n 제곱 의 다른 id, 그들 이 야 말로 인접 한 것 입 니 다)
모형 훈련

def train_lsh(data, num_vector=16, seed=None):
    
    dim = data.shape[1]
    if seed is not None:
        np.random.seed(seed)
    random_vectors = generate_random_vectors(num_vector, dim)
  
    powers_of_two = 1 << np.arange(num_vector-1, -1, -1)
    #       ，  2 n  
  
    table = {}
    
    # Partition data points into bins
    bin_index_bits = (data.dot(random_vectors) >= 0)
  
    # Encode bin index bits into integers
    bin_indices = bin_index_bits.dot(powers_of_two)
    
    # Update `table` so that `table[i]` is the list of document ids with bin index equal to i.
    for data_index, bin_index in enumerate(bin_indices):
        if bin_index not in table:
            # If no list yet exists for this bin, assign the bin an empty list.
            table[bin_index] = [] 
        # Fetch the list of document ids associated with the bin and add the document id to the end.
        table[bin_index].append(data_index)
        

    model = {'data': data,
             'bin_index_bits': bin_index_bits,
             'bin_indices': bin_indices,
             'table': table,
             'random_vectors': random_vectors,
             'num_vector': num_vector}
    
    return model

정의 거리:

def norm(x):
    sum_sq = x.dot(x.T)
    norm = np.sqrt(sum_sq)
    return norm

def consine_distance(x, y):
    xy = x.dot(y.T)
    dist = xy / (norm(x) * norm(y))
    return 1 - dist
    

LSH model 을 이용 하여 가장 가 까 운 곳 을 찾 습 니 다.
방향 찾기:

벡터 L 을 초 공간 을 대표 하 는 빈

으로 한다.

우선 이 빈 의 모든 벡터 를 찾 아 라

이 빈 과 1 bit 차이 가 나 는 벡터 찾기

이 빈 과 2 bit 차이 가 나 는 벡터 찾기

후보 빈

반경 r 찾기 확정

검색 반경 에 따라 빈 어 레이 를 반전 시 키 는 bit

def search_nearby_bins(query_bin_bits, table, search_radius=2, initial_candidates=set()):
    """
    For a given query vector and trained LSH model, return all candidate neighbors for
    the query among all bins within the given search radius.
    
    Example usage
    -------------
    >>> model = train_lsh(corpus, num_vector=16, seed=143)
    >>> q = model['bin_index_bits'][0]  # vector for the first document
  
    >>> candidates = search_nearby_bins(q, model['table'])
    """
    num_vector = len(query_bin_bits)
    powers_of_two = 1 << np.arange(num_vector-1, -1, -1)
    
    # Allow the user to provide an initial set of candidates.
    candidate_set = copy(initial_candidates)
    
    for different_bits in combinations(range(num_vector), search_radius):       
        # Flip the bits (n_1,n_2,...,n_r) of the query bin to produce a new bit vector.
        ## Hint: you can iterate over a tuple like a list
        alternate_bits = copy(query_bin_bits)  #           ，      bit   
        for i in different_bits:
            #  i   ，       
            alternate_bits[i] = 1 - alternate_bits[i] # YOUR CODE HERE 
        
        # Convert the new bit vector to an integer index
        nearby_bin = alternate_bits.dot(powers_of_two)
        
        # Fetch the list of documents belonging to the bin indexed by the new bit vector.
        # Then add those documents to candidate_set
        # Make sure that the bin exists in the table!
        # Hint: update() method for sets lets you add an entire list to the set
        if nearby_bin in table:
            #         
            candidate_set.update(table[nearby_bin])
             # YOUR CODE HERE: Update candidate_set with the documents in this bin.
    return candidate_set

def query(vec, model, k, max_search_radius):
    # vec: tfidf  
    # model:      
    # k:      k 
    # max_search_radius:       
  
    data = model['data']
    table = model['table']
    random_vectors = model['random_vectors']
    num_vector = random_vectors.shape[1]
    
    
    # Compute bin index for the query vector, in bit representation.
    bin_index_bits = (vec.dot(random_vectors) >= 0).flatten()
    
    # Search nearby bins and collect candidates
    candidate_set = set()
    for search_radius in xrange(max_search_radius+1):
        candidate_set = search_nearby_bins(bin_index_bits, table, search_radius, initial_candidates=candidate_set)
    
    # Sort candidates by their true distances from the query
    nearest_neighbors = graphlab.SFrame({'id':candidate_set})
    candidates = data[np.array(list(candidate_set)),:]
    nearest_neighbors['distance'] = pairwise_distances(candidates, vec, metric='cosine').flatten()
    
    return nearest_neighbors.topk('distance', k, reverse=True), len(candidate_set)

이상 은 LSH 의 모든 주 함수 입 니 다. 자세 한 내용 은 개인의 git 를 참조 하 십시오.