J'ai un groupe de n ensembles pour lesquels je dois calculer une sorte de valeur "d'unicité" ou de "similitude". J'ai choisi l'indice Jaccard comme une mesure appropriée. Malheureusement, l'indice Jaccard ne fonctionne que sur deux ensembles à la fois. Afin de calculer la similitude entre tous les ensembles, il faudra dans l'ordre des n 2 calculs Jaccard.
(Si cela aide, est généralement compris entre 10 et 10000, et chaque ensemble contient en moyenne 500 éléments. De plus, au final, je me fiche de la similitude de deux ensembles spécifiques - je me soucie seulement de la similitude interne (c'est-à-dire la moyenne (ou au moins une approximation suffisamment précise de la moyenne) de tous les indices Jaccard du groupe))
Deux questions:
- Existe-t-il un moyen d'utiliser toujours l'index Jaccard sans la complexité ?
- Existe-t-il une meilleure façon de calculer la similitude / l'unicité des ensembles à travers un groupe d'ensembles que la manière que j'ai suggérée ci-dessus?
algorithms
time-complexity
rinogo
la source
la source
Réponses:
Une option serait d'utiliser le schéma de signature de [1], le filtrage basé sur la taille : un schéma qui utilise les informations de taille pour réduire le nombre de paires d'ensemble qui doivent être prises en compte.
Ils expérimentent également une forme pondérée; où les poids sont basés sur IDF.
[1] Arasu, Arvind, Venkatesh Ganti et Raghav Kaushik. «Efficient Exact Set-similarity Joins». Dans les actes de la 32e Conférence internationale sur les très grandes bases de données, 918–929. VLDB '06. Dotation VLDB, 2006
la source
Une autre option serait d'utiliser un lien wiki de hachage de sensibilité local . Je l'ai vu utilisé dans la détection de similitudes communautaires par Wu et Zou ( une méthode de détection communautaire incrémentielle pour les systèmes de marquage social utilisant un hachage sensible à la localité , Neural Networks 58: 14-28; ACM DL ) qui détecte essentiellement la similitude entre des nombres entiers ou jeux de chaînes.
la source