Encuentra pares cercanos en un espacio dimensional muy alto con vectores dispersos

Tengo $N$ (~ un millón) vectores de características. Hay $M$ (~ un millón) características binarias, pero en cada vector solo $K$ (~ mil) de ellas serían $1$ , el resto son $0$ . Estoy buscando los pares de vectores que tienen al menos $L$ (~ cien) características en común ( $1$ en ambos). El número de tales pares es de una magnitud similar a $N$ (~ un millón).

Creo que esto podría abordarse como la búsqueda de pares de puntos cercanos en un espacio de dimensiones muy altas. La función de distancia podría ser tal que se base en la cantidad de características que los dos vectores tienen en común. Pero probablemente también sería útil con una métrica de distancia más convencional (como Euclidiana).

¿Qué algoritmos conocidos serían útiles para abordar este problema? Cualquier cosa que sea cuadrática en $N$ o $M$ no será práctica.

Un ejemplo de formulación del problema en el mundo real es considerar a $N$ personas moviéndose entre varios lugares. Si dos personas estaban en el mismo lugar al mismo tiempo, decimos que se conocieron. (El número de combinaciones de ubicación y hora con al menos 1 persona presente es $M$ ). Estamos buscando amigos: personas que se hayan reunido al menos $L$ veces.

Parece que el enfoque que está buscando es una combinación de firmas minhash y Locality Sensitive Hashing (LSH); El pdf (disponible gratuitamente) de Mining Massive Datasets describe este enfoque (y otras medidas de similitud) con cierto detalle en el Capítulo 3, pero brevemente:

Una firma minhash es una representación condensada de su matriz original que se construye aplicando un número n de funciones hash a las características, reduciendo así el número de características por observación. Esto reduce el tamaño de sus datos, sin embargo, probablemente notará que esto todavía lo deja con un problema de .$O(N^2)$

Para abordar esto, MMDS aconseja que si todo lo que desea encontrar son pares por encima de un cierto umbral de similitud (que parece aplicarse en su caso), entonces puede concentrarse solo en los pares que tienen más probabilidades de ser similares: este enfoque se llama Hashing sensible a la localidad , y en la sección 3.4 explican un ejemplo de cómo combinar el enfoque de firma minhash con LSH.

Además del texto, también hay conferencias disponibles en el curso Coursera del mismo nombre.

Estoy buscando los pares de vectores que tienen al menos características en común.$L$

Esto es solo un producto interno de vectores de características binarias. Cuando el producto interno es mayor que , el par tendrá al menos L elementos en común. Esto debería ser un cálculo relativamente rápido, al menos, más rápido que la distancia euclidiana, lo que sería un desperdicio y lento para estos datos. Debido a que se estipula que estás buscando parejas, esto será inherentemente significa que tenga que hacer ($L-1$$L$ cálculos para comparar cada vector.$\binom{N}{2}$

Encontrar puntos que estén juntos es un problema de agrupamiento. Pero el primer paso de los algoritmos de agrupación con los que estoy familiarizado es calcular distancias o similitudes por pares. Estoy seguro de que alguien ha desarrollado alternativas más eficientes. Un punto sobre la terminología: ¡tener al menos vecinos comunes se expresa como una similitud , no como una distancia! Los productos internos son, en este caso, similitudes de coseno no normalizadas.$L$

Puede hacer que esto sea más manejable solo realizando el cálculo interno del producto cuando la suma del vector de características (que en este caso es la misma que la norma) para una observación es mayor que , ya que es imposible para ese vector de características binarias tener un producto interior con otro vector de características binario que satisfaga a mi criterio, cuando esta suma es menor que L . Obviamente, calcular estas sumas es solo una complejidad O ( N ) , por lo que es una forma económica de reducir la magnitud del paso interno del producto.$L-1$$L$$O(N)$

Pero la forma clásica de reducir el alcance de este problema es hacer un prefiltrado adicional. ¿Está especialmente interesado cuando una característica poco común toma el valor 1? Si es así, solo realice el cálculo para esos vectores de características.

O tal vez podría beneficiarse reformulando su problema. Por ejemplo, se sabe que el muestreo tiene buenas propiedades; Las estadísticas inferenciales se desarrollan sobre esta idea con bastante profundidad. Entonces, quizás no sea factible analizar todo el conjunto de datos, pero es perfectamente factible examinar una pequeña muestra. No sé qué pregunta está tratando de responder, pero si diseña cuidadosamente su experimento, puede salirse con la suya solo mirando unos pocos miles de observaciones, con datos más que suficientes para fines de validación.

Después de algún pensamiento adicional, tengo una fuerte sospecha de que los datos que va a trabajar tiene algún tipo de gráfico . Es muy plausible que G esté compuesto por varios componentes conectados, en cuyo caso puede descomponer G en un conjunto de gráficos, con el feliz efecto secundario de reducir la dimensionalidad de los datos. Incluso si el gráfico es solo dos componentes conectados de aproximadamente el mismo tamaño, eso significa que sus comparaciones por pares de O ( N 2 ) tienen aproximadamente $G$$G$$G$$O(N^2)$ el costo total!$\frac{1}{4}$

Si el gráfico es simétrico, las siguientes observaciones pueden ser útiles:

1. Defina el Laplaciano de su gráfico como , donde D es una matriz diagonal de grados (la suma de cada vector de características) y A es la matriz de adyacencia (el apilamiento de vectores de características en una matriz).$P=D-A$$D$$A$
2. El número de veces aparece como un valor propio de P es el número de componentes conectados de G . Descomponer el gráfico en sus componentes conectados y trabajar únicamente con esos componentes tendrá el efecto secundario de reducir la dimensión de sus datos; calcular su cantidad de interés será más fácil. Pero calcular la descomposición propia será costoso para un millón de vértices ...$0$$P$$G$
3. (Después de una permutación completa) es una matriz diagonal por bloques de los Laplacianos de los componentes conectados de G .$P$$G$
4. es positivo semidefinido. Esto es casi ciertamente útil de alguna manera.$P$
5. La conectividad algebraica de es el valor de la segunda más pequeño valor propio de P . Esto te dice qué tan bien conectado está G. Tal vez eso responda algunas de las preguntas que le interesan sobre los vectores que tienen características en común. La teoría de grafos espectrales desarrolla esta idea con más detalle.$G$$P$$G$

"¿Es este un problema de SNA?" No estoy seguro. En una aplicación, las características describen el comportamiento y buscamos conectar a personas con comportamientos similares. ¿Eso hace que esto sea un problema de SNA?

Si tiene un gráfico bipartito que conecta a las personas con comportamientos, puede pensar en esto como una red de afiliación , con personas como filas y comportamientos como columnas. Si desea conectar a la gente a la gente a través de los comportamientos que tienen en común, se puede calcular B B T = A . A i j es la cantidad de comportamientos que las personas tienen en común. Obviamente, el conjunto de vértices donde A i j ≥ L responde a su pregunta.$B$$BB^T=A$$A_{ij}$$A_{ij}\ge L$

$Nspace$$Ntime$
$O( N^2 )$

Consulte también: datos
de búsqueda de vecinos muy cercanos en datascience.stackexchange

pairwise.py :

utiliza la biblioteca Python Gensim y el heapq de la biblioteca estándar para hacer comparaciones por parejas masivamente rápidas y escalables entre una gran cantidad de documentos aribtrarily con TF-IDF y la distancia cosenoidal.

$x$$feat_1:value_1, feat_{101}:value_{101}$$K$$K$$K$

Para cada característica, cree un diccionario que contenga los índices que comparten esta característica. Con suerte, este número no será demasiado grande (si tiene una función compartida por todos los índices, este enfoque está arruinado, puede dejar de leer aquí).

$feat_1 : \{1,101,202\}, feat_2 : \{7,202\},feat_3 : \{202\}...feat_M:\{3,45,6\}$$feat_3$$O(NK)$

$x$$x$$x$$P$$O(N^2)$

$x$$y$$d(x,y)$$<x,y>$$x$$y$$O(K)$

$O(NPK)$$O(MN^2)$

Apliqué este método para implementar un KNN sobre un conjunto de texto grande (tren: 2 000 000 líneas, prueba 35 000 líneas, número de características: 10 000, número promedio de características por elemento: 20), que se ejecutó en aproximadamente una hora. .

$k$$O(LN\log(N))$

L. Erotz, M. Steinbach y V. Kumar. "Un nuevo algoritmo compartido de agrupación de vecinos más cercanos y sus aplicaciones". Actas del 1er Taller sobre agrupamiento de datos de alta dimensión y sus aplicaciones, 2002.

$O(k \cdot \log{n} )$$k << n$

Dado que su k es 100 y su n es 1e6, esto debería darle ~ 1e4x de velocidad en comparación con el clásico FFT.

Si necesita otros 20x de velocidad y es un tomador de riesgos, entonces, en lugar de convolucionar todas las filas contra el dominio y buscar el pico, podría arrancar un subconjunto de filas.

También puede prefiltrar columnas eliminando columnas cuyas sumas estén por debajo de 50, o algún otro umbral que esté en el orden de la mitad del número de filas que desea igualar. Como mínimo, debe eliminar las columnas de todos los ceros y todos los 1 como no informativos. Lo mismo con las filas que están completamente vacías o lo suficientemente vacías, o las filas que están tan llenas que son irrelevantes.

Tarea: debería poner un ejemplo aquí usando datos sintéticos y comparar algunos de los métodos.

Acabo de encontrar un artículo que es directamente relevante.

Algoritmos aleatorios y PNL: uso de la función hash sensible a la localidad para la agrupación de sustantivos de alta velocidad (Ravichandran et al, 2005)

En realidad, está implementado en https://github.com/soundcloud/cosine-lsh-join-spark, que es donde lo encontré.

Se basa en el hashing sensible a la localidad (ya mencionado en otras respuestas). Después de haber reducido los vectores de características a un espacio de baja dimensión, utiliza una unión rápida de distancia de Hamming para encontrar los vecinos más cercanos.