Data Stream Mining

Every algorithm covered elsewhere in this series implicitly assumes the full dataset is available to look at repeatedly — an association-rule miner can scan the transaction table as many times as it needs, a clustering algorithm can revisit every point. Data stream mining removes that assumption entirely: the data arrives continuously, is effectively unbounded (a stock ticker or a network traffic feed has no defined "last row"), and in most designs can only be looked at once, since storing the entire history defeats the purpose. This single-pass, bounded-memory constraint is the same one covered from a device-level angle in the lesson on ubiquitous data mining (a sensor with limited memory computing a running mean via Welford's algorithm); this lesson covers the techniques that constraint demands at the stream level — sampling, windowing, and detecting when the stream's underlying pattern has changed.

Fixed Windows vs. Sliding Windows

Since a stream can't be stored in full, most stream algorithms operate on a window — a bounded, recent slice of the stream — rather than the whole history. A fixed window processes the stream in non-overlapping chunks: readings 1–100, then 101–200, computing a fresh result for each chunk independently. A sliding window instead maintains a constant-size view that moves forward one item at a time — after processing reading 101, a window of size 100 drops reading 1 and now covers readings 2–101. The practical difference matters: a fixed window can miss a pattern that straddles a chunk boundary (a spike that happens across readings 95–105 gets split and diluted across two separate chunks), while a sliding window catches it because every possible 100-reading span eventually gets evaluated — at the cost of recomputing statistics far more often.

Maintaining a Random Sample: Reservoir Sampling

The vague-sounding "store some data for later" requirement raises a genuinely hard question when the stream's total length is unknown in advance: how do you keep a fair, unbiased random sample of a fixed size k from a stream that might stop after 100 items or after 100 million? Reservoir sampling (Algorithm R) answers this with a surprisingly simple rule: fill a reservoir of size k with the first k items; for every item after that, at position i (counting the very first item as position 0), generate a random integer j between 0 and i inclusive, and if j < k, replace the reservoir slot at index j with the new item — otherwise discard the new item. Tracing this through a 5-item stream (A, B, C, D, E) with a reservoir of size k = 2:

Fill:     reservoir = [A, B]                     (positions 0, 1)
i = 2 (item C): draw j in {0,1,2}. Say j = 1 (< 2) -> replace slot 1
                reservoir = [A, C]
i = 3 (item D): draw j in {0,1,2,3}. Say j = 3 (not < 2) -> discard D
                reservoir = [A, C]
i = 4 (item E): draw j in {0,1,2,3,4}. Say j = 0 (< 2) -> replace slot 0
                reservoir = [E, C]

The algorithm never needed to know the stream would stop at 5 items, and never stored more than k items plus whichever new item just arrived. The guarantee this algorithm provides is precise and checkable: every item that has passed through the stream has exactly a k/n probability of being in the final reservoir, where n is the total stream length. Verifying this for item A in the trace above: A survives only if it is never selected for replacement at steps i = 2, 3, 4. At each step i ≥ k, the probability that a replacement event lands specifically on A's current slot is 1/(i+1), so the probability A survives step i is i/(i+1):

P(A survives) = (2/3) × (3/4) × (4/5)
              = (2×3×4) / (3×4×5)
              = 24 / 60
              = 0.4  =  2/5  =  k/n

The middle terms cancel exactly (a telescoping product), leaving k/n — confirming the algorithm's guarantee holds precisely for this example, not just approximately. This is the actual mechanism behind "keep a representative sample of the data seen so far" for a stream whose length is never known in advance.

Detecting Concept Drift

A model trained once on historical data can quietly become wrong as the stream's underlying pattern shifts over time — a phenomenon called concept drift. A simple, illustrative version of drift detection compares a recent window's statistics against an established baseline: suppose a fraud model's baseline, built from the first 1,000 transactions, shows an average transaction amount of $45. If the most recent window of 100 transactions shows an average of $210 — more than four times the baseline — that shift itself is a signal worth investigating, independent of whether any single transaction was individually flagged as an outlier. Formal algorithms built on this same basic idea, such as DDM (Drift Detection Method), which monitors a classifier's error rate for a statistically significant increase, and ADWIN (Adaptive Windowing), which maintains a variable-size window and shrinks it automatically when it detects the older and newer portions no longer look like they come from the same distribution, are the production-grade versions of this comparison — precise enough to distinguish a genuine shift from ordinary random fluctuation, which a naive fixed threshold like the one above cannot reliably do on its own. Once drift is detected, the usual response is retraining the model on recent data, discarding the assumption that the pattern learned last month still holds today.

Ensemble Methods Applied to Streams

Combining multiple models to improve reliability — covered in full depth in the lesson on bagging and boosting — applies to streams with one added twist: because the stream never stops, an ensemble used for stream mining typically retires and replaces its weakest-performing member model periodically, rather than training a fixed ensemble once and using it forever. This is a direct consequence of concept drift: a model that was one of the strongest members last week can become the weakest once the underlying pattern shifts, so streaming ensembles are evaluated and pruned continuously rather than trained once.

Where This Fits Among the Rest of This Series

The application areas most associated with stream mining — real-time fraud detection, network intrusion detection, IoT sensor monitoring — are covered with their own worked examples in the lesson on data mining applications and the lesson on ubiquitous data mining; what distinguishes this lesson is the specific machinery (bounded windows, reservoir sampling, drift detection) that real-time analysis actually depends on, rather than a second pass through the same application list.