Eu tenho (~ um milhão) vetores de recursos. Existem (~ um milhão) recursos binários, mas em cada vetor apenas (~ mil) deles seria , o restante é . Estou procurando os pares de vetores que possuem pelo menos (~ cem) recursos em comum ( em ambos). O número de tais pares é de magnitude semelhante a (~ um milhão).M K 1 0 L 1 N
Eu acho que isso poderia ser abordado como a procura de pares de pontos próximos em um espaço de alta dimensão. A função de distância pode ser tal que se baseia em quantos recursos os dois vetores têm em comum. Mas provavelmente seria útil com uma métrica de distância mais convencional (como euclidiana) também.
Quais algoritmos conhecidos seriam úteis para abordar esse problema? Qualquer coisa quadrática em ou não será prática.
Um exemplo de formulação do problema no mundo real é considerar pessoas que se deslocam entre vários locais. Se duas pessoas estavam no mesmo local ao mesmo tempo, dizemos que elas se conheceram. (O número de combinações de horário e local com pelo menos uma pessoa presente é ) Estamos procurando amigos: pessoas que se encontraram pelo menos vezes.
fonte
Respostas:
Parece que a abordagem que você está procurando é uma combinação de assinaturas minhash e hash sensível à localidade (LSH); o pdf (disponível gratuitamente) dos Mining Massive Datasets descreve essa abordagem (e outras medidas de similaridade) em alguns detalhes no Capítulo 3, mas brevemente:
Uma assinatura minhash é uma representação condensada da sua matriz original que é construída aplicando um número n de funções de hash aos recursos, reduzindo assim o número de recursos por observação. Isso reduz o tamanho dos seus dados, mas você provavelmente notará que isso ainda deixa um problema de .O ( N2)
Para resolver isso, o MMDS recomenda que, se tudo o que você deseja encontrar é pares acima de um certo limite de semelhança (o que parece se aplicar no seu caso), você pode se concentrar apenas nos pares com maior probabilidade de serem semelhantes - essa abordagem é chamado Hashing sensível à localidade e, na seção 3.4, eles mostram um exemplo de como combinar a abordagem de assinatura minhash com o LSH.
Além do texto, também há palestras disponíveis no curso Coursera de mesmo nome.
fonte
Este é apenas um produto interno dos vetores de recursos binários. Quando o produto interno for maior que , o par terá pelo menos L elementos em comum. Esse cálculo deve ser relativamente rápido - pelo menos, mais rápido que a distância euclidiana, o que seria um desperdício e lento para esses dados. Como você estipula que está procurando pares, isso significa inerentemente que você deve fazer ( NL - 1 eu cálculos para comparar todos os vetores.( N2)
Encontrar pontos próximos é realmente um problema de agrupamento. Mas o primeiro passo dos algoritmos de agrupamento com os quais estou familiarizado é calcular distâncias ou semelhanças aos pares. Tenho certeza que alguém desenvolveu alternativas mais eficientes. Um ponto sobre a terminologia: ter pelo menos vizinhos comuns é formulado como uma semelhança , não uma distância! Produtos internos são, nesse caso, semelhanças não-normalizadas de cosseno.eu
Você pode tornar isso mais tratável executando apenas o cálculo interno do produto quando a soma do vetor de recurso (que neste caso é a mesma da norma) para uma observação for maior que , pois é impossível para esse vetor de recurso binário ter um produto interno com outro vector recurso binário que irá satisfazer o meu critério quando esta soma é inferior a L . Obviamente, calcular essas somas é apenas de complexidade O ( N ) , portanto, é uma maneira barata de reduzir a magnitude da etapa interna do produto.L - 1 eu O ( N)
Mas a maneira clássica de reduzir o escopo desse problema é fazer uma pré-filtragem adicional. Você está especialmente interessado em quando um recurso um tanto incomum assume o valor 1? Nesse caso, execute apenas o cálculo para esses vetores de recursos.
Ou talvez você possa se beneficiar com a reestruturação do seu problema. Por exemplo, a amostragem é conhecida por ter boas propriedades; a estatística inferencial desenvolve essa idéia com bastante profundidade. Portanto, talvez seja inviável analisar todo o conjunto de dados, mas é perfeitamente viável examinar uma pequena amostra. Não sei qual pergunta você está tentando responder, mas se você planejar cuidadosamente seu experimento, poderá apenas observar alguns milhares de observações, com mais do que dados suficientes para fins de validação.
Depois de alguma reflexão adicional, eu tenho um forte pressentimento de que os dados que você está trabalhando com algum tipo de gráfico . É muito plausível que G seja composto por vários componentes conectados; nesse caso, você pode decompor G em um conjunto de gráficos, com o feliz efeito colateral de reduzir a dimensionalidade dos dados. Mesmo se o gráfico tiver apenas dois componentes conectados aproximadamente do mesmo tamanho, isso significa que suas comparações O ( N 2 ) em pares têm aproximadamente 1G G G O ( N2) o custo total!1 14
Se o gráfico for simétrico, as seguintes observações podem ser úteis:
Se você tem um gráfico bipartido conectando pessoas a comportamentos, pode pensar nisso como uma rede de afiliação , com pessoas como linhas e comportamentos como colunas. Se você quiser conectar as pessoas através dos comportamentos que eles têm em comum, você pode calcular B B T = A . A i j é o número de comportamentos que as pessoas têm em comum. Obviamente, o conjunto de vértices onde A i j ≥ L responde à sua pergunta.B B BT= A UMAeu j UMAeu j≥ L
fonte
Consulte também: dados
dos vizinhos mais próximos de dados com dimensões muito altas na datacience.stackexchange
pairwise.py :
fonte
Para cada recurso, crie um dicionário contendo os índices que compartilham esse recurso. Felizmente, esse número não será muito grande (se você tiver um recurso que é compartilhado por todos os índices, essa abordagem está arruinada, você pode parar de ler aqui).
Eu apliquei esse método para implementar um KNN em conjunto de texto grande (trem: 2 000 000 linhas, teste 35 000 linhas, número de recursos: 10 000, número médio de recursos por elemento: 20), que foi executado em cerca de uma hora. .
fonte
L. Erotz, M. Steinbach e V. Kumar. "Um novo algoritmo de cluster vizinho mais próximo compartilhado e suas aplicações." Anais do 1º Workshop sobre Cluster de Dados de Alta Dimensão e suas Aplicações, 2002.
fonte
Dado que seu k é 100 e seu n é 1e6, isso deve lhe proporcionar uma velocidade de ~ 1e4x em comparação com a FFT clássica.
Se você precisar de mais 20x de velocidade e correr riscos, em vez de envolver todas as linhas no domínio e procurar o pico, poderá inicializar um subconjunto de linhas.
Você também pode pré-filtrar colunas removendo colunas cujas somas estão abaixo de 50 ou algum outro limite que esteja na ordem da metade do número de linhas que você deseja corresponder. No mínimo, você deve remover colunas de todos os zeros e todos os 1s como não informativos. O mesmo ocorre com as linhas totalmente vazias ou vazias o suficiente, ou com linhas tão cheias que são irrelevantes.
Tarefas: devo colocar um exemplo aqui usando dados sintéticos e comparar alguns dos métodos.
fonte
Acabei de encontrar um artigo que é diretamente relevante.
Na verdade, é implementado em https://github.com/soundcloud/cosine-lsh-join-spark, que é onde eu o encontrei.
É baseado no hash sensível à localidade (já mencionado em outras respostas). Depois de reduzir os vetores de características para um espaço de baixa dimensão, ele usa uma junção rápida da distância de Hamming para encontrar os vizinhos mais próximos.
fonte