Estrutura do banco de dados para detecção de similaridade

5

O problema que quero resolver é o seguinte:

Dado um conjunto de usuários, cada um com um conjunto de interesses que eles próprios podem especificar, encontre todos os pares de usuários que compartilham os mesmos interesses com um limiar de semelhança (por exemplo, 50% de interesses semelhantes). Além disso, algumas categorias de interesse devem ter um peso maior do que outras (isto é, mais importante em direção ao limite).

Atualmente, só consigo pensar em modelos relacionais para resolver isso, mas parece errado e algo que levará muito tempo para ser computado quando houver apenas 100 usuários. Com meu conhecimento atual de bancos de dados baseados em documentos (por exemplo, Mongo), acredito que eles não sejam uma opção, já que precisaríamos fazer referência cruzada de documentos o tempo todo (?). Devo fazer mais leituras em bancos de dados baseados em gráficos? Quaisquer ponteiros são bem-vindos.

Estou procurando uma solução equilibrada em termos de complexidade versus desempenho. Não estou procurando por algo que funcione com milhões de usuários, se isso significar que eu tenho que ler toneladas de trabalhos de pesquisa, mas uma abordagem que suporte alguns milhares de usuários será suficiente.

    
por latusaki 28.02.2017 / 10:19
fonte

3 respostas

2

Seu problema é de busca multidimensional, então você precisa de um sistema que seja capaz disso.

Você pode converter seus interesses em uma sequência de recursos e usar o Hashing sensível à localidade para reduzir o conjunto de dados no qual realizar uma pesquisa mais exata.

Outra alternativa seria usar R-Trees .

    
por 28.02.2017 / 16:12
fonte
2

Eu achei Introdução à Recuperação de Informações para ser muito legível e informativo. Há detalhes técnicos e longas listas de "leitura adicional", mas o texto em si não é atolado em detalhes.

O Capítulo 14 sobre Classificação de espaço vetorial se aplicaria a essa situação. Trate cada interesse como uma dimensão em um espaço multidimensional. Normalize os valores (no sentido matemático, não o DB) e pondere adequadamente. Em seguida, calcule uma distância N-dimensional entre os usuários neste espaço. Aqueles com uma distância menor são mais parecidos.

Como isso é essencialmente um monte de cálculos, qualquer SGBD deve ser capaz de executá-lo. Pode ser mais econômico transferir os dados para um servidor de aplicativos e usar seus ciclos de CPU, no entanto.

O número de cálculos aumenta como o quadrado da base de usuários, no entanto. Você pode não conseguir escalá-lo como quiser.

O livro também abrange vários algoritmos de agrupamento de vizinhos mais próximos. Existem heurísticas para reduzir o número total de comparações ao custo de alguma precisão. Esta pode ser uma compensação aceitável neste cenário.

    
por 15.03.2017 / 23:15
fonte
1

Basicamente você tem um gráfico bipartido que consiste em pessoas e interesses (correspondendo a hubs e spokes).

O algoritmo SALSA fornece a lista das melhores pessoas correspondentes (classificadas) para uma pessoa (na consulta tempo).

    
por 15.03.2017 / 23:37
fonte