Amplificando um hash sensível à localidade

10

Estou tentando criar um hash sensível à localidade do cosseno, para poder encontrar pares de itens similares candidatos sem precisar comparar todos os pares possíveis. Eu tenho basicamente trabalhando, mas a maioria dos pares nos meus dados parece ter semelhança de cosseno no intervalo de -0.2 a +0.2, então estou tentando cortá-la com bastante precisão e escolher coisas com a similaridade de cosseno 0.1 e acima.

Estive lendo o capítulo 3. Mineração de conjuntos de dados maciços. Isso fala sobre como aumentar a precisão da seleção de pares de candidatos ampliando uma família sensível à localidade. Acho que entendo a explicação matemática, mas estou lutando para ver como implemento isso na prática.

O que tenho até agora é o seguinte

Eu digo 1000 filmes, cada um com classificações de uma seleção de 1 milhão de usuários. Cada filme é representado por um vetor esparso de pontuações de usuários (número da linha = ID do usuário, valor = pontuação do usuário)
Eu construo N vetores aleatórios. O comprimento do vetor corresponde ao comprimento dos vetores do filme (ou seja, o número de usuários). Os valores do vetor são +1 ou -1. Na verdade, eu codifico esses vetores como binários para economizar espaço, com +1 mapeado para 1 e -1 mapeado para 0
Eu construo vetores de esboço para cada filme, pegando o produto escalar do filme e cada um dos N vetores aleatórios (ou melhor, se eu criar uma matriz R colocando os N vetores aleatórios horizontalmente e colocando-os em cima um do outro, em seguida, o esboço para o filme m é R * m), pegando o sinal de cada elemento no vetor resultante, então termino com um vetor de esboço para cada filme de + 1s e -1s, que novamente codifico como binário. Cada vetor tem comprimento N bits.
Em seguida, procuro esboços semelhantes, fazendo o seguinte
1. Dividi o vetor de esboço em b bandas de bits r
2. Cada banda de r bits é um número. Combino esse número com o número da banda e adiciono o filme a um hash bucket abaixo desse número. Cada filme pode ser adicionado a mais de um balde.
3. Então eu olho em cada balde. Todos os filmes que estão no mesmo bloco são pares de candidatos.

Comparando isso com 3.6.3 de mmds, minha etapa AND é quando olho para bandas de bits r - um par de filmes passa a etapa AND se os bits r tiverem o mesmo valor. Minha etapa OR ocorre nos intervalos: os filmes são pares de candidatos se ambos estiverem em um dos intervalos.

O livro sugere que eu posso "amplificar" meus resultados adicionando mais etapas AND e OR, mas não sei como fazer isso praticamente, pois a explicação do processo de construção para outras camadas é em termos de verificar a igualdade aos pares em vez de chegando com números de balde.

Alguém pode me ajudar a entender como fazer isso?

machine-learning Philip Pearl
fonte

4

Eu acho que resolvi algo. Basicamente, estou procurando uma abordagem que funcione em um ambiente de tipo mapa / redução e acho que essa abordagem faz isso.

Assim,

suponha que eu tenha b faixas de r linhas e queira adicionar outro estágio AND, digamos outro c ANDs.
então, em vez de bits b * r, preciso de hashes de bits b * r * c
e eu executo meu procedimento anterior c vezes, sempre em bits b * r
Se x e y forem considerados um par candidato por qualquer um desses procedimentos, ele emitirá um par de valores-chave ((x, y), 1), com a tupla de IDs (x, y) como chave e o valor 1
No final dos procedimentos c, agrupo esses pares por chave e soma
Qualquer par (x, y) com uma soma igual a c era um par candidato em cada uma das rodadas c, e também é um par candidato de todo o procedimento.

Portanto, agora tenho uma solução viável e tudo o que preciso fazer é descobrir se o uso de três etapas como essa me ajudará a obter um resultado melhor com menos bits de hash gerais ou melhor desempenho geral ...

Philip Pearl
fonte

0

h (x, v) = {\begin{cases} 0 0 & E se sgn (x \cdot v) < 0 0 \\ 1 1 & outro \end{cases}

$h(x,v)=\left\{ \begin{array}{ll}0 & \mbox{if }\textrm{sgn}(x\cdot v) < 0\\ 1 & \mbox{else}\end{array} \right.$

v

$v$

h^{'} (x, i) = (h (x, v_{i + 1}), . . ., h (x, v_{i + r}))

$h'(x,i) = (h(x,v_{i+1}),...,h(x,v_{i+r}))$

h^{″} (x, j) = f (h^{'} (x, r j), j)

$h''(x,j) =f(h'(x,rj),j)$

h^{″} (x, y) = {\begin{cases} 1 1 & E se h^{″} (x, j) = h^{″} (y, j) para qualquer j \in [0 0, b) \\ 0 0 & outro \end{cases}

$h''(x,y) =\left\{ \begin{array}{ll}1 & \mbox{if }h''(x,j) = h''(y,j) \mbox{ for any }j \in [0,b)\\ 0 & \mbox{else}\end{array} \right.$

h^{″} (x, y)

$h''(x,y)$

\hat{h} : S \to S^{'}

$\hat{h}:S\to S'$

S^{'}

$S'$

h^{″} (x, j)

$h''(x,j)$

j

$j$

j

$j$

y

$y$

v

$v$

deasmhumnha
fonte

Amplificando um hash sensível à localidade

Respostas: