Algorithme pour les nombres 'k' les plus fréquents

19

Je cherchais l'algorithme le plus efficace (streaming ??) qui me dise les «k» éléments les plus fréquemment rencontrés dans un flux de données à tout moment. Cet article: Les algorithmes de flux de données "Diviser et conquérir" m'ont intéressé.

Par exemple, supposons qu'il y ait des nombres: (4,3,5,1,6,2,4,3,3,8,9,1) et que je recherche les 3 nombres les plus fréquents (disons), alors je devrais prenez (3,4,1) comme réponse.

J'ai essayé de chercher en ligne, mais je n'ai pas trouvé d'endroit qui donne une approche et dit que c'est le meilleur. Une solution triviale serait d'utiliser un tas ou un arbre binaire équilibré, mais je pense qu'il existe une meilleure façon et je voulais savoir si elle est documentée quelque part.

Edit: je recherche un algorithme qui donne toujours la bonne réponse par opposition à un algorithme d'appromixation (dont beaucoup apparaissent dans les résultats de recherche) qui repose sur la distribution des données d'une manière ou d'une autre

dhruvbird
la source
En fait, il existe trois types d'algorithmes: exact, approximatif et "dépendant des données". Vous avez exclu le dernier type, mais les algorithmes approximatifs qui ne dépendent PAS de la distribution des données sont-ils autorisés? comme je l'ai indiqué, sinon, vous avez des problèmes en raison des limites inférieures connues pour ce problème dans un paramètre de flux.
Suresh Venkat,
1
J'étais curieux de savoir si les algorithmes qui utilisent une mémoire limitée (algorithmes de streaming) peuvent réellement faire ce que je voulais et il semble qu'ils ne puissent pas comme vous l'avez souligné. Aussi si un algorithme exact non-streaming est connu qui résout le problème dans le pire des cas garanti O (n), mentionné ici (cité par l'article de Cormode et Hadjileftheriou du lien que vous avez fourni): citeseerx.ist.psu. edu / viewdoc / summary? doi = 10.1.1.106.7889
dhruvbird

Réponses:

20

Il existe une littérature abondante sur ce problème. Premièrement, même pour , le problème est difficile: comme le montrent Alon, Matias et Szegedy , vous ne pouvez pas obtenir une meilleure approximation factorielle constante de la fréquence de l'élément le plus populaire dans l' espace , même si vous sommes prêts à être randomisés.o ( n )k=1o(n)

Cependant, si vous êtes assuré qu'un élément se produit strictement plus de 50% du temps, il existe une astuce simple qui utilise un espace constant et le trouvera (c'est une question de puzzle Google populaire). Plus généralement, vous pouvez trouver des éléments qui se produisent plus de fois en utilisant une généralisation de cette astuce.n/k

Une étude définitive de ce que l'on sait du problème est le document de Cormode et Hadjileftheriou de VLDB 2008 . Il couvre les méthodes ci-dessus et bon nombre des dernières méthodes. l'idée générale est que vous pouvez générer une liste approximative des premiers éléments (où approximative ici signifie que vous pourriez obtenir des éléments dont le nombre est proche du nombre des premiers éléments).kkk

Suresh Venkat
la source
1
+1. Je pense que l'algorithme> 50% du temps est un algorithme bien connu (algorithme d'élément majoritaire) comme vous l'avez mentionné
dhruvbird
2
Merci!! L'article de Cormode et Hadjileftheriou que vous avez mentionné cite cet article: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7889 qui a la même technique que celle à laquelle je pensais. Il maintient 2 listes chaînées; un par fréquence et en son sein une autre liste de tous les éléments ayant la même fréquence.
dhruvbird
pouvez-vous élaborer sur l'algorithme à plus de 50%? et le puzzle google? Je ne peux pas suivre ce raisonnement bâclé, car vous venez de le toucher et vous n'avez pas entièrement dépensé «l'astuce bien connue». Merci.
Ceci est un commentaire (pas assez de réputation) sur le lien userweb.cs.utexas.edu/users/misra/scannedPdf.dir/… de Suresh Venkat : Il semble que l'algorithme présenté nécessite un second passage dans les données, ce qui n'est pas autorisé ici. En fait, je ne vois pas comment un algorithme à un seul passage avec des exigences d'espace O (1) peut exister.
TonyK
2

Je recommande également de lire la section 8.1.3 «Exploration de modèles fréquents dans les flux de données» du livre suivant:

Jiawei Han, Micheline Kamber. Exploration de données --- Concepts et techniques, deuxième édition, Morgan Kaufmann Publishers , 2006.

Il introduit un algorithme, connu sous le nom de Lossy Counting , qui rapproche les éléments fréquents (éléments dont le support est supérieur à un min_support ) avec une précision arbitraire.

Pas exactement ce que vous voulez, mais j'ai pensé que cela pourrait aider.

MS Dousti
la source
vous pouvez peut-être m'aider sur ma question ici
Ben