Encontre pares próximos em um espaço dimensional muito alto com vetores esparsos

9

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 NNMK10L1N

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 N ou M não será prática.


Um exemplo de formulação do problema no mundo real é considerar N 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 é M ) Estamos procurando amigos: pessoas que se encontraram pelo menos L vezes.

Daniel Darabos
fonte
11
Se o vetor 1, recurso 1 for , e o vetor 2, recurso 1 também for 0 , eles têm esse recurso "em comum"? 00
gung - Restabelece Monica
@ user777, presumo que não . Nesse caso, sua resposta é perfeita, mas seria bom que isso fosse explicitamente declarado pelo OP.
gung - Restabelece Monica
@ Gung, você assume certo. Eu editei a pergunta para esclarecer. Obrigado!
Daniel Darabos
11
Sobre quantos pares de vetores têm> 100 características em comum - amostra aleatória + força bruta? Os tamanhos 1M x 1M são um problema real ou são feitos? Veja também a abordagem na pesquisa de cadeia de bits mais próxima do vizinho no stackoverflow.
Denis
11
Uma sugestão possivelmente louca: visualize seus vetores de recursos de 1 Mbit de comprimento como imagens de 1000 x 1000 pixels e procure métodos de agrupamento de imagens, por exemplo, stackoverflow.com/search?q=[image"+clustering . Afaik, você precisa encontrar bons recursos (não pixels únicos) para que isso funcione, mas eu não sou especialista.
Denis

Respostas:

6

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.

Tchotchke
fonte
7

Estou procurando os pares de vetores que têm pelo menos recursos de em comum.L

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 ( NL1L 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.L

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.L1LO(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 1GGGO(N2) o custo total!14

Se o gráfico for simétrico, as seguintes observações podem ser úteis:

  1. Defina o Laplaciano do seu gráfico como , onde D é uma matriz diagonal de grau (a soma de cada vetor de característica) e A é a matriz de adjacência (o empilhamento de vetores de característica em uma matriz).P=DADA
  2. Os tempos Número aparece como um valor próprio de P é o número de componentes ligados de L . A decomposição do gráfico em seus componentes conectados e o trabalho exclusivo com esses componentes terão o efeito colateral de reduzir a dimensão dos seus dados; calcular sua quantidade de interesse será mais fácil. Mas calcular a composição do eigend será caro para um milhão de vértices ...0PG
  3. (Depois de uma permutação cheio) é uma matriz diagonal de bloco dos Laplacians dos componentes conexos de L .PG
  4. é semidefinido positivo. Isso é quase certamente útil de alguma forma.P
  5. A conectividade algébrica de é o valor do segundo menor valor próprio de P . Isso mostra como o G está bem conectado . Talvez isso responda a algumas das perguntas nas quais você está interessado: os vetores que possuem características em comum. A teoria dos grafos espectrais desenvolve essa idéia com mais detalhes.GPG

"Isso é um problema do SNA?" Não tenho certeza. Em um aplicativo, os recursos descrevem o comportamento e procuramos conectar pessoas com comportamentos semelhantes. Isso faz disso um problema de SNA?

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 jL responde à sua pergunta.BBBT=AAijAijL

Sycorax diz restabelecer Monica
fonte
Obrigado pela excelente resposta! São muitas coisas que terei que investigar mais. Não estou convencido de que as comparações entre pares sejam inevitáveis. Não é um problema de agrupamento em que estou procurando grupos de tamanho> 1? Eu esperava que alguma abordagem de particionamento espacial pudesse reduzir bastante o número de comparações pareadas.
Daniel Darabos
Desculpe, eu não sei muito sobre ciência de dados. Mas não é um problema de agrupamento quando procuramos agrupar pontos próximos uns dos outros? Eu tenho uma distância máxima (L) e quero encontrar grupos (pares) de pontos que se encontram a essa distância um do outro. Isso está ampliando demais a definição de clustering?
Daniel Darabos
11
Na verdade, pode ser formulado como um problema gráfico. Nesse caso, temos um gráfico bipartido de N pontos e características M e queremos encontrar pares de pontos que tenham pelo menos L vizinhos comuns. Estou analisando especificamente o fraseado baseado em vetor de recursos agora, esperando que exista um método de agrupamento que possa ser útil para mim. O K-SVD foi sugerido para um problema semelhante em stats.stackexchange.com/questions/93366/… , então estou lendo isso no momento. Obrigado!
Daniel Darabos
"Isso é um problema do SNA?" Não tenho certeza. Em um aplicativo, os recursos descrevem o comportamento e procuramos conectar pessoas com comportamentos semelhantes. Isso faz disso um problema de SNA? Obrigado por me apresentar a terminologia, é muito útil para orientar minha pesquisa.
Daniel Darabos
Eu revi minha resposta. Seu objetivo final é apenas enumerar as pessoas com muitos comportamentos em comum, ou é outra coisa?
Sycorax diz Reinstate Monica
2


NspaceNtime
O(N2)

Consulte também: dados
dos vizinhos mais próximos de dados com dimensões muito altas na datacience.stackexchange

pairwise.py :

usa a biblioteca Python Gensim e o heapq da biblioteca padrão para fazer comparações massivamente rápidas e escalonáveis ​​em pares entre um número arbitrariamente grande de documentos usando TF-IDF e distância de cosseno.

denis
fonte
1

xfeumat1 1:vumaeuvocêe1 1,feumat101:vumaeuvocêe101KKK

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).

feumat1 1:{1 1,101,202},feumat2:{7,202},feumat3:{202}...feumatM:{3,45,6}feumat3O(NK)

xxxPO(N2)

xyd(x,y)<x,y>xyO(K)

O(NPK)O(MN2)

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. .

RUser4512
fonte
Eu não entendo completamente essa abordagem - isso não é porque eu não acredito em você, é inteiramente devido à minha falta de familiaridade com estratégias diferentes para representar dados. Talvez você possa elaborar mais sobre o que abordará nos dois primeiros parágrafos?
Sycorax diz Restabelecer Monica
O(N2)
1

kO(euNregistro(N))

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.

Sycorax diz restabelecer Monica
fonte
Obrigado, é uma leitura interessante. Como você conseguiu o tempo O (LN log (N))? Parece ótimo. Mas a descrição do algoritmo começa com "Construa a matriz de similaridade" e essa seria uma matriz NxN, pelo que entendi.
Daniel Darabos
@DanielDarabos A complexidade é descrita no livro Practical Graph Mining with R.
Sycorax diz Reinstate Monica
1

O(kregistron)k<<n

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.

EngrStudent
fonte
0

Acabei de encontrar um artigo que é diretamente relevante.

Algoritmos randomizados e PNL: usando a função hash sensível à localidade para agrupamento de nomes de alta velocidade (Ravichandran et al, 2005)

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.

Daniel Darabos
fonte