Quels algorithmes comptent les fréquences des éléments communs dans une collection d'ensembles?

Question

Je voudrais des informations sur les algorithmes qui peuvent aider à identifier la communalité et les différences entre les ensembles de données qui se chevauchent.

En utilisant le système de tag stackoverflow comme exemple:

Disons que cette question a été donnée 5 tags. Disons qu'il y a 1000 autres questions qui ont au moins un de ces tags. Parmi ces 1000 questions, combien de ces questions ont des étiquettes communes que mon article original n'a pas?

Une autre façon plus simple de décrire c'est un système automatique de suggestion de marquage:.

« vous a tagué votre question [5 balises I sélectionnées] des questions autres similiar ont été étiquetés avec [liste des balises qui pourraient être de intérêts]. où la liste [des balises qui pourraient intéresser] sont souvent INTERVENUES balises qui ne sont pas dans ma liste orginal.

exemples de code en C# si possible :)

Answer 1

Je ne connais aucun des algorithmes spécifiques ou des structures de données, mais je pourrais suggérer une façon de base de la manipulation de ce:

Assomption: chaque entrée a cinq balises uniques.

• Collectez toutes les entrées contenant l'une des cinq étiquettes (pas de doublons).
• Pour chaque entrée de la liste, utilisez un tableau associatif (hashtable) pour chaque variable, en incrémentant la valeur.
• Pour chaque entrée de la matrice, ajoutez le nom de la variable dans l'index d'entrée de cette matrice.

En (bâclée) pseudo-code, utilisez deux boucles (si possible):

for each entry 
    if any tag in original_tags 
     tag_list[tag]++ 
end 

for next in tag_list 
    tag_count[tag_list[next]] += next 
end 

Cela devrait produire un tableau creux de noms de balises concaténés (ok, je ne mentionnaient pas un séparateur, mais hé c'est du pseudo code :-). Gardez le nombre le plus élevé, puis itérez en arrière pour les meilleures suggestions.

(Cache pour optimiser, mais attention pour les mises à jour)

Paul.

Answer 2

Regardez dans la distance Wager-Hamming. C'est la distance de Hamming définie sur les chaînes comme le nombre d'opérations d'édition nécessaires pour transformer une chaîne en une chaîne anot sa. Vous pouvez également utiliser l'ordre partiel des classes d'équivalence et définir l'inclusion: lorsque les questions A et B ont le même ensemble d'étiquettes jusqu'au réordonnancement, elles sont égales, définissent l'union, définissent la différence et définissent l'intersection. définir un ordre partiel pour < et> comparaisons.