RU Big Data 2023 (NWI-IBC036) FAQ

Proefstuderen Radboud Proefstuderen Big Data

Welkom bij het proefstuderen college over Big Data.

Introductie

Een (eigenlijk te) eenvoudige poll voor de stemming in het land, kijkt naar de voorkomens van verschillende smileys in Tweets.

Hiervoor gebruik ik programma scraper.py (je kunt het thuis namaken als je de online instructies volgt!).

We laten de scraper een tijdje draaien, en drukken op Ctrl-C om te stoppen:

python scraper.py

Bekijk de verzamelde data door de database te dumpen als CSV, of er enkele SQL queries op uit te voeren:

python queries/usercounts.py
python queries/query.py

Je kunt de database ook dumpen als CSV, een “comma-separated file”, en vervolgens (bijvoorbeeld) als spreadsheet importeren in Google Docs:

python dump.py

Streaming Tweets

Hoe kun je eigenlijk de trending topics bepalen over een groot volume aan Tweets?

De uitdaging is om de tweets niet eerst allemaal op te slaan, maar “on the fly” te analyseren: terwijl ze binnenkomen.

Wie wint in social media?

We passen het programma scraper.py aan om de data niet op te slaan, maar de stemming op Twitter te peilen terwijl de data langskomt - dus zonder die in een database op te slaan!

In informatica-termen is de achterliggende vraag als volgt: How would you find the quantiles of a stream of numbers in O(N) with limited memory?.

Majority

Bekijk de code van functie MJRTY in streamer.py.

Mediaan

Wat als we nu de mediaan van een reeks getallen zouden willen weten?

median_est = 0
for val in stream:
    if val > median_est:
        median_est += 1
    elif val < median_est:
        median_est -= 1

Uitbreiding voor precentielen

Als je het 75% percentiel wilt weten van een reeks getallen, dan is de basis als volgt:

quantile_75 = 0
for val in stream:
    r = random()
    if val > quantile_75 and r > 1 - 0.75:
        quantile_75 += 1
    elif val < quantile_75 and r > 0.75:
        quantile_75 -= 1

De details kun je nalezen in de (Engelstalige en best ingewikkelde) blog post Sketch of the Day: Frugal Streaming. Als je een paar jaar informatica studeert, dan kun je de theorie achter die post tot in detail begrijpen. De truc is dat je door de randomisatie van het algorithme (het gooien van een dobbelsteen) de “mediaan” als het ware verschuift.

Zonder studeren kunnen we nu alvast spelen met de bijbehorende demo:

Probeer maar eens verschillende distributies, en bedenk wat je nu eigenlijk gevisualiseerd ziet worden.,

Van woorden naar getallen

Met woorden is het lastig werken in een computer. Soms vertalen we woorden dan ook naar getallen - vervolgens kunnen we veel sneller met de data omgaan. In technische termen representeren we de woorden als getallen. De keuze van de juiste representatie is misschien wel het belangrijkste onderdeel van informatica.

7 minute video about arrays and hash tables.

Bloom Filters.

Meer weten?

Counting

We kunnen met een Bloom Filter dus snel checken of we een woord eerder hebben gezien - maar dat maakt het woord nog geen geschikt trending topic. Ofwel, we moeten kunnen tellen welke woorden het vaakst voorkomen!

We weten al hoe we het 99.99% percentiel van de aantallen voorkomens met weinig geheugen kunnen bepalen. Kunnen we ook met beperkt geheugen tellen hoe vaak elk woord genoemd wordt? Hiervoor is de count-min sketch ontwikkeld.

In principe weten we nu genoeg om Twitter’s trending topics functionaliteit na te bouwen. Er zitten alleen nog wel wat haken en ogen aan…

  • Wat zijn de termen die we moeten tellen?
  • Hoe bepalen we trending topics per regio?

De eerste vraag is er een in het vakgebied van de “information retrieval” en “natuurlijke taalverwerking”, de laatste een vraag op het gebied van “databases” en “data mining”.

Meer weten?