Trouvez des paires proches dans un espace de dimension très élevé avec des vecteurs clairsemés

J'ai (~ un million) de vecteurs de caractéristiques. Il y a (~ un million) d'entités binaires, mais dans chaque vecteur, seulement (~ un millier) d'entre elles seraient égales à , les autres étant . Je recherche les paires de vecteurs qui ont au moins (~ cent) traits en commun ( dans les deux). Le nombre de ces paires est d'une ampleur similaire à (~ un million).M K 1 0 L 1 $N$$M$$K$$1$$0$$L$$1$$N$

Je pense que cela pourrait être envisagé comme la recherche de paires de points proches dans un espace de très grande dimension. La fonction de distance pourrait être telle qu'elle est basée sur le nombre de caractéristiques que les deux vecteurs ont en commun. Mais il serait probablement utile avec une métrique de distance plus conventionnelle (comme Euclidienne) également.

Quels algorithmes bien connus seraient utiles pour aborder ce problème? Tout ce qui est quadratique en ou ne sera pas pratique.$N$$M$

Un exemple de formulation du problème dans le monde réel est de considérer personnes se déplaçant entre plusieurs endroits. Si deux personnes se trouvaient au même endroit en même temps, nous disons qu'elles se sont rencontrées. (Le nombre de combinaisons emplacement-temps avec au moins 1 personne présente est ) Nous recherchons des amis: des personnes qui se sont rencontrées au moins fois.M $N$$M$$L$

Il semble que l'approche que vous recherchez est une combinaison de signatures minhash et de hachage sensible à la localité (LSH); le pdf (disponible gratuitement) de Mining Massive Datasets décrit cette approche (et d'autres mesures de similitude) en détail dans le chapitre 3, mais brièvement:

Une signature minhash est une représentation condensée de votre matrice d'origine qui est construite en appliquant un certain nombre n de fonctions de hachage aux entités, réduisant ainsi le nombre d'entités par observation. Cela réduit la taille de vos données, mais vous remarquerez probablement que cela vous laisse toujours avec un problème .$O(N^2)$

Pour résoudre ce problème, MMDS conseille que si tout ce que vous voulez trouver est des paires au-dessus d'un certain seuil de similitude (qui semblerait s'appliquer dans votre cas), alors vous pouvez vous concentrer uniquement sur les paires qui sont les plus susceptibles d'être similaires - cette approche s'appelle Locality Sensitive Hashing , et dans la section 3.4, ils expliquent comment combiner l'approche de signature minhash avec LSH.

En plus du texte, des cours sont également disponibles sur le cours Coursera du même nom.

Je recherche les paires de vecteurs qui ont au moins caractéristiques en commun.$L$

Ce n'est qu'un produit intérieur de vecteurs de caractéristiques binaires. Lorsque le produit intérieur est supérieur à , la paire aura au moins éléments en commun. Cela devrait être un calcul relativement rapide - au moins, plus rapide que la distance euclidienne, ce qui serait inutile et lent pour ces données. Parce que vous stipulez que vous recherchez des paires, cela signifie par nature que vous devez effectuer des calculs pour comparer chaque vecteur.L ($L-1$$L$$\binom{N}{2}$

Trouver des points proches les uns des autres est en effet un problème de regroupement. Mais la première étape des algorithmes de clustering que je connais est le calcul des distances par paires ou des similitudes. Je suis sûr que quelqu'un a développé des alternatives plus efficaces. Un point sur la terminologie: avoir au moins voisins communs est formulé comme une similitude , pas une distance! Les produits internes sont, dans ce cas, des similitudes de cosinus non normalisés.$L$

Vous pouvez rendre cela plus maniable en effectuant le calcul du produit interne uniquement lorsque la somme du vecteur de caractéristique (qui est dans ce cas la même que la norme) pour une observation est supérieure à , car il est impossible pour ce vecteur de caractéristique binaire d'avoir un produit intérieur avec un autre vecteur caractéristique binaire qui satisfera mon critère lorsque cette somme est inférieure à . De toute évidence, le calcul de ces sommes n'est qu'une complexité , c'est donc un moyen bon marché de réduire l'ampleur de l'étape de produit interne.L O ( N $L-1$$L$$O(N)$

Mais la manière classique de réduire l'étendue de ce problème consiste à effectuer un préfiltrage supplémentaire. Êtes-vous particulièrement intéressé par le fait qu'une fonctionnalité quelque peu inhabituelle prenne la valeur 1? Si tel est le cas, effectuez uniquement le calcul pour ces vecteurs de caractéristiques.

Ou peut-être pourriez-vous bénéficier d'un recadrage de votre problème. Par exemple, l'échantillonnage est connu pour avoir de belles propriétés; des statistiques inférentielles développent cette idée assez en profondeur. Il est donc peut-être impossible d'analyser l'ensemble des données, mais il est parfaitement possible d'examiner un petit échantillon. Je ne sais pas à quelle question vous essayez de répondre, mais si vous concevez soigneusement votre expérience, vous pouvez vous en tirer avec seulement quelques milliers d'observations, avec plus que suffisamment de données restantes à des fins de validation.

Après une réflexion supplémentaire, j'ai une intuition forte que les données que vous travaillez avec une sorte de graphique . Il est très plausible que soit composé de plusieurs composants connectés, auquel cas vous pouvez décomposer en un ensemble de graphiques, avec l'effet secondaire heureux de réduire la dimensionnalité des données. Même si le graphique n'est que deux composants connectés de la même taille, cela signifie que vos comparaisons par paires ont à peu près le coût total!G G O ( N 2 ) $G$$G$$G$$O(N^2)$$\frac{1}{4}$

Si le graphique est symétrique, les observations suivantes peuvent être utiles:

1. Définissez le laplacien de votre graphique comme , où est une matrice diagonale de degré (la somme de chaque vecteur de caractéristique) et est la matrice d'adjacence (l'empilement de vecteurs de caractéristique dans une matrice).D $P=D-A$$D$$A$
2. Le nombre de fois de apparaît comme étant une valeur propre de est le nombre de composantes connexes de . Décomposer le graphique en ses composants connectés et travailler uniquement avec ces composants aura pour effet secondaire de réduire la dimension de vos données; le calcul de votre quantité d'intérêt sera plus facile. Mais le calcul de la composition par eigend sera coûteux pour un million de sommets ...P $0$$P$$G$
3. (Après une permutation complète) est une matrice diagonale par blocs des laplaciens des composantes connexes de .$P$$G$
4. $P$ est semi-défini positif. Ceci est presque certainement utile d'une manière ou d'une autre.
5. La connectivité algébrique de est la valeur de la deuxième plus petite valeur propre de . Cela vous indique à quel point est bien connecté . Cela répondra peut-être à certaines des questions qui vous intéressent: les vecteurs qui ont des caractéristiques en commun. La théorie des graphes spectraux développe cette idée plus en détail.P $G$$P$$G$

"Est-ce un problème SNA?" Je ne suis pas sûr. Dans une application, les fonctionnalités décrivent le comportement et nous cherchons à connecter des personnes ayant des comportements similaires. Est-ce que cela en fait un problème SNA?

Si vous avez un graphique bipartite reliant les personnes aux comportements, vous pouvez le considérer comme un réseau d'affiliation , avec des personnes comme des lignes et des comportements comme des colonnes. Si vous voulez connecter les gens à des gens via les comportements qu'ils ont en commun, vous pouvez calculer . est le nombre de comportements que les gens ont en commun. Évidemment, l'ensemble des sommets où répond à votre question.$B$$BB^T=A$$A_{ij}$$A_{ij}\ge L$

À la recherche de personnes se réunissant en blocs spatio-temporels:
espace en blocs (blocs de ville, km2, ) et le temps en blocs . Il y a de fortes chances que si les gens se rencontrent, ils se rencontreront dans le même bloc. Exécutez donc NN dans chaque bloc. Les temps d'exécution et les taux d'erreur dépendront bien sûr de la taille et de la forme des blocs (également de ce que vous pouvez paralléliser / MapReduce), mais vous avez des paramètres avec lesquels jouer - ingénierie, pas ouvert .$Nspace$$Ntime$
$O( N^2 )$

Voir aussi:
voisins les plus proches recherche de données de très haute dimension sur datascience.stackexchange

pairwise.py :

utilise la bibliothèque Python Gensim et le tas de la bibliothèque standard pour effectuer des comparaisons par paires massivement rapides et évolutives entre un nombre généralement important de documents utilisant TF-IDF et la distance cosinusoïdale.

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

Pour chaque fonctionnalité, créez un dictionnaire contenant les index partageant cette fonctionnalité. Espérons que ce nombre ne sera pas trop grand (si vous avez une fonctionnalité partagée par tous les index, cette approche est ruinée, vous pouvez arrêter de lire ici).

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

J'ai appliqué cette méthode pour implémenter un KNN sur un grand ensemble de texte (train: 2 000 000 lignes, tester 35 000 lignes, nombre d'entités: 10 000, nombre moyen d'entités par élément: 20), qui a fonctionné en une heure environ. .

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

L. Erotz, M. Steinbach et V. Kumar. "Un nouvel algorithme de clustering de voisins les plus proches et ses applications." Actes du 1er atelier sur le regroupement des données de haute dimension et leurs applications, 2002.

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

Étant donné que votre k est 100 et votre n est 1e6, cela devrait vous donner une vitesse de ~ 1e4x par rapport à la FFT classique.

Si vous avez besoin de 20 fois plus de vitesse et que vous êtes un preneur de risques, au lieu de convoluer toutes les lignes contre le domaine et de rechercher le pic, vous pouvez démarrer un sous-ensemble de lignes.

Vous pouvez également préfiltrer les colonnes en supprimant les colonnes dont les sommes sont inférieures à 50, ou tout autre seuil qui est de l'ordre de la moitié du nombre de lignes que vous cherchez à faire correspondre. Au minimum, vous devez supprimer les colonnes de tous les zéros et de tous les 1 comme non informatifs. Idem avec des lignes entièrement vides ou suffisamment vides, ou des lignes si pleines qu'elles ne sont pas pertinentes.

À faire: je devrais mettre un exemple ici en utilisant des données synthétiques et comparer certaines des méthodes.

Je viens de tomber sur un document qui est directement pertinent.

Algorithmes randomisés et PNL: utilisation de la fonction de hachage sensible à la localité pour le regroupement de noms à grande vitesse (Ravichandran et al, 2005)

Il est en fait implémenté dans https://github.com/soundcloud/cosine-lsh-join-spark où je l'ai trouvé.

Il est basé sur un hachage sensible à la localité (déjà mentionné dans d'autres réponses). Après avoir réduit les vecteurs de caractéristiques à un espace de faible dimension, il utilise une jointure de distance de Hamming rapide pour trouver les voisins les plus proches.