Lecture 2 Notes — Data Collection & Sampling
Learning outcomes: LO1 (big-data characteristics), LO3 (analytics on structured and semi-structured data)
Companion files: slides L02, notebook Week2_Data_Collection_Sampling.ipynb, dataset student_population.csv
1. Where data comes from
Analytics starts with a decision about how the data is collected, because every later step inherits its flaws.
- Batch collection gathers data in large chunks on a schedule (nightly exports, monthly census files). It is simple and cheap, and results are always a little stale.
- Streaming collection processes each event as it arrives (clicks, sensor readings, card swipes). It gives low latency, but you can never "look at everything" at once, so you need algorithms that work in one pass with bounded memory.
- Typical sources: operational databases, application logs, web APIs and scraping, sensors/IoT, surveys, and third-party datasets.
Rule of thumb: collect with the question in mind. A dataset that was not designed to answer your question will quietly bias the answer.
2. Why sample at all?
Even in "big data", we often cannot or should not process everything: cost, latency, privacy, or because a well-chosen sample answers the question. The sample is only useful if it represents the population.
3. Four classical sampling techniques
| Technique | How it works | Use when | Watch out for |
|---|---|---|---|
| Simple random | Every unit has equal chance | Population is homogeneous and listable | Small groups can be missed by chance |
| Stratified | Split into strata (e.g. faculty), sample inside each | Subgroups matter and differ | Needs reliable stratum labels |
| Systematic | Every k-th unit after a random start | Ordered list, quick to do | Hidden periodicity in the list |
| Cluster | Randomly pick whole clusters, survey all inside | Population is geographically spread | Clusters may be unlike each other, larger error |
In the notebook we simulate 10,000 students across 4 faculties with a known true mean (about 6.39). Because the truth is known, you can see how far each method lands from it and how stratified sampling protects small faculties.
4. Bias and pitfalls
- Selection bias: the way units are chosen favours some of them (e.g. surveying only students in the library).
- Survivorship bias: only the units that "survived" are visible (reviewing only hotels still in business).
- Non-response bias: the people who answer differ from those who do not.
- Undercoverage: part of the population is missing from the sampling frame (no phone number, no email).
A bigger sample does not fix bias. It only gives you a more precise estimate of the wrong number. Famous example: the 2013 Google Flu Trends overestimated flu prevalence because search behaviour changed while the model assumed it had not.
5. How big must the sample be?
For estimating a proportion:
n = Z² · p(1 − p) / e²
- Z is the z-score for the confidence level (1.96 for 95%: the value that leaves 2.5% in each tail of the standard normal curve).
- p is the expected proportion; use 0.5 when unknown because it maximises p(1 − p), giving the safest (largest) n.
- e is the margin of error.
With Z = 1.96, p = 0.5 and e = 0.05: n = 3.8416 × 0.25 / 0.0025 = 384.16, so round up to 385.
Notice what is not in the formula: the population size. For large populations the required sample barely changes, which is why 385 works for a city or a country.
6. Sampling a stream: reservoir sampling
Problem: keep a uniform random sample of k items from a stream of unknown length, using only O(k) memory and one pass.
Algorithm R: 1. Store the first k items. 2. For the i-th item (i > k), draw j uniformly from 1..i. If j ≤ k, replace reservoir[j] with the new item; otherwise discard it.
Why it is uniform: item i enters with probability k/i, and each later item i' kicks it out with probability 1/i'. Multiplying the survival chances, every item ends in the reservoir with probability k/n. The notebook confirms this with a Monte Carlo run (estimates stay within about ±0.004 of the truth).
7. Sketches: approximate answers in tiny memory
When exact counting needs too much memory, trade a small, bounded error for a huge saving.
- Count-Min Sketch estimates how often each item appears using a small 2-D array of counters and several hash functions. It can only over-estimate. Width controls the error: in the notebook width 2,000 over-counted badly, width 20,000 (depth 4) was accurate.
- HyperLogLog estimates the number of distinct items by looking at the longest run of leading zeros in hashed values. Precision p = 12 uses about 4 KB and gave 0.54% error in the notebook (p = 8 gave about 5%).
8. Choosing the right technique (quick guide)
| Situation | Choose |
|---|---|
| Static list, homogeneous | Simple random |
| Important subgroups | Stratified |
| Spread-out population, costly travel | Cluster |
| Endless stream, need a sample | Reservoir |
| Stream, need frequencies | Count-Min Sketch |
| Stream, need distinct count | HyperLogLog |
9. Key takeaways
- The collection method decides what the data can and cannot tell you.
- Sample size fixes precision; only good design fixes bias.
- On streams, you need one-pass, bounded-memory algorithms.
Next: Data quality and pre-processing I.