Moving On: Applications and Beyond
Open in the Padhaiko app8.1 Learning from massive datasets and data streams
Classical data mining algorithms assume the entire dataset fits comfortably in main memory and can be scanned repeatedly. Massive datasets (terabytes to petabytes) and continuous data streams (network packets, clickstreams, IoT telemetry) break both assumptions.
1. Learning from Massive Datasets
When dataset size exceeds RAM or makes algorithms infeasible:
- Subsampling and Partitioning: Train on a representative stratified sample, or split data across distributed shards (e.g., MapReduce / Spark) and aggregate partial counts or models.
- Mini-Batch and Stochastic Gradient Descent (SGD): Update linear models, logistic regression, and neural networks using one instance or small mini-batches ( rows) per step instead of scanning all rows before each weight update.
- Algorithmic Scalability: Prefer linear-time methods (Naive Bayes counts, -means, linear SVM via SGD) over quadratic methods (exact agglomerative clustering, dual kernel SVMs with Gram matrices).
2. Data Stream Mining and Concept Drift
Data Stream Constraints and Concept Drift
- Data Stream Constraints: A continuous, potentially unbounded sequence of arriving instances processed under strict single-pass, bounded-memory, and real-time latency limits—old raw records cannot be revisited once discarded.
- Concept Drift: The phenomenon where the statistical relationship between input features and the target class changes over time (e.g., shifting consumer tastes, evolving spam patterns, seasonal weather). Concept drift may be sudden, gradual, incremental, or recurring.
Key Streaming Algorithms and Drift Adaptation
- Very Fast Decision Trees (VFDT / Hoeffding Trees): Build decision trees incrementally in one pass by storing only sufficient statistics at leaves. Using the Hoeffding bound, after observing examples at a leaf, if the difference between the top two split attributes' Information Gains () exceeds:
(where is the range of Gain for classes and is confidence), the best attribute is guaranteed with probability to be the same choice an infinite batch would make, so the node splits immediately without storing raw rows.
- Adaptation Strategies for Concept Drift:
- Sliding Windows: Retain only the most recent instances (fixed window) or dynamically shrink the window when change is detected (ADWIN — Adaptive Windowing).
- Exponential Forgetting: Multiply older sufficient statistics by a decay factor so recent data carries higher weight.
- Drift Detectors & Model Reset: Monitor online error rate (e.g., DDM — Drift Detection Method); trigger a warning or replace the active model/subtree when error rises significantly above its historical minimum.
8.2 Foundations of Text Mining and Web Mining
Most enterprise and internet information exists not in neat relational tables, but as unstructured text documents and hyperlinked web ecosystems.
1. Text Mining Foundations
To apply standard data mining algorithms to unstructured text, documents must first be converted into numeric feature vectors:
Text Preprocessing Pipeline
- Tokenization & Case Folding: Split text into word tokens (removing punctuation) and convert to lowercase.
- Stopword Removal: Discard high-frequency, low-discrimination function words (
the,is,and,of). - Stemming / Lemmatization: Reduce inflected words to a common root (
mining,mined,minesmine; e.g., Porter stemmer) to merge semantically equivalent tokens. - -Grams (Optional): Include word bigrams (
not good,credit card) alongside single unigrams when word order matters.
Vector Space Model, TF-IDF, and Cosine Similarity
TF-IDF Weighting and Cosine Similarity
In a corpus of documents, represent each document as a sparse vector over the vocabulary using Term Frequency–Inverse Document Frequency (TF-IDF):
where is the frequency of term in document and is the number of documents containing (giving high weight to terms frequent in yet rare across the corpus).
Similarity between two document vectors and is measured by Cosine Similarity (length-normalized dot product):
- Why Cosine Over Euclidean Distance? A -page document and a -page summary on the exact same topic differ widely in raw Euclidean norm, yet point in nearly the same direction ().
- Common Text Mining Tasks: Document classification (spam filtering, news categorization via Multinomial Naive Bayes or Linear SVM), document clustering, sentiment analysis, and topic extraction.
2. Web Mining Foundations
Web mining applies data mining techniques to extract knowledge from web documents, link topology, and user interactions, organized into three core branches:
| Branch | Primary Data Source | Representative Techniques & Applications |
|---|---|---|
| Web Content Mining | Text, HTML DOM, tables, images, and metadata inside web pages | Web crawling, information extraction, page classification, product review mining |
| Web Structure Mining | Directed hyperlink graph between pages | PageRank (global link authority), HITS (Hubs & Authorities), spam-link detection |
| Web Usage Mining | Server access logs, clickstreams, cookies, session histories | Bot filtering, sessionization, frequent path/association discovery, personalized recommendations |
Link Analysis: PageRank and HITS
- PageRank (Random Surfer Model): Models a surfer who follows outgoing links uniformly at random with damping factor (typically ) and teleports to any of the pages with probability :
where is the set of pages linking into and is the total out-degree of page .
- HITS (Hyperlink-Induced Topic Search): Distinguishes Authorities (pages with valuable content pointed to by many good hubs) and Hubs (directory pages pointing to many good authorities), updating both scores iteratively via mutual reinforcement.
Worked Examples
Computing TF-IDF Weights and Cosine Similarity Between Documents
- In a corpus of documents, the term
"mining"appears times in document and occurs in documents overall. Compute using base- logarithm. - Suppose after TF-IDF weighting over a -term vocabulary
("data", "mining"), two documents have vectors and . Compute the Cosine Similarity between and .
Part 1 — Computing :
Part 2 — Computing Cosine Similarity between and :
- Dot product: .
- Vector norms: , .
The two documents share strong thematic alignment ( out of ).
- .
- Cosine Similarity .
Computing PageRank Update and Hoeffding Bound for Streams
- Consider a -page web graph () with damping factor and initial uniform scores for every page. If page receives incoming links from page (which has outgoing links) and page (which has outgoing link), compute the updated .
- In a binary-class data stream (, so Information Gain range ), a Hoeffding Tree sets confidence (). Compute the Hoeffding bound after observing examples at a leaf.
Part 1 — Computing one PageRank iteration for page : Using :
Part 2 — Computing the Hoeffding Bound ():
If the top two candidate attributes differ in Information Gain by more than , the Hoeffding Tree splits immediately without waiting for more stream items.
- .
- Hoeffding bound .
Exercises
Practice Exercises — Massive Datasets, Streams, Text & Web Mining
List three fundamental constraints of data stream mining compared to traditional batch mining, define concept drift, and describe two practical mechanisms to adapt a streaming classifier when drift occurs.
Constraints of Data Stream Mining:
- Single-pass processing: Each item can be inspected once and cannot be stored permanently for multiple epochs.
- Bounded memory: Summary statistics or sketches must fit in fixed RAM regardless of stream length.
- Real-time low latency: Predictions and model updates must finish faster than the stream arrival rate.
Concept Drift and Two Adaptation Mechanisms: Concept drift occurs when the underlying data-generating distribution shifts over time (suddenly, gradually, or cyclically), invalidating old decision boundaries. Two adaptation methods are:
- Adaptive Sliding Windows (e.g., ADWIN): Maintain a recent window of observations and automatically discard older sub-windows whenever statistical tests detect a significant distribution shift.
- Drift Detectors with Model Replacement (e.g., DDM): Track online error rate; when error rises significantly above its running minimum, train a background replacement classifier on recent instances and swap out the stale model.
Data streams impose single-pass, bounded-memory, and real-time latency constraints. Concept drift is the change of underlying target/feature distributions over time, handled via sliding windows (ADWIN), exponential decay, or drift detectors (DDM) that trigger model replacement.
Explain how a Very Fast Decision Tree (VFDT / Hoeffding Tree) decides when to split a node in a single pass. For a binary classification stream () with and examples at a leaf, compute the Hoeffding bound .
VFDT Splitting Criterion: A Hoeffding Tree maintains attribute–class frequency counters at each leaf instead of storing raw instances. Whenever the difference in split heuristic between the best and second-best candidate attributes exceeds the Hoeffding bound , the tree commits to splitting on the top attribute with statistical confidence .
Computing ():
VFDT splits a leaf once using only per-leaf counts. For , , and , .
Describe the standard text preprocessing pipeline (tokenization, stopword removal, stemming). In a corpus of articles, a term appears times in article and appears in articles total: compute its TF-IDF weight. Then compute the Cosine Similarity between two -term vectors and .
Text Preprocessing Pipeline: Tokenization breaks raw text into individual word tokens and normalizes case; stopword removal filters uninformative high-frequency words (the, is, in); stemming reduces morphological variants (computes, computing, computed comput) to reduce vocabulary sparsity.
Computing TF-IDF and Cosine Similarity:
Preprocessing converts raw text via tokenization, stopword removal, and stemming. Here and Cosine Similarity .
Why is Cosine Similarity preferred over Euclidean Distance when comparing TF-IDF document vectors? Explain what happens if a long research article simply repeats every paragraph of a short abstract twice.
Scale Invariance of Cosine Similarity: TF-IDF vector magnitudes grow with document length (higher raw term counts). If document repeats every word of short document twice, : Euclidean distance becomes large, falsely marking them dissimilar!
Angle Between Vectors Remains Zero: Cosine similarity divides by , measuring only the angle between term-distribution directions:
Thus Cosine Similarity recognizes that both documents share the exact same topic distribution regardless of length.
Cosine similarity measures the angle between document vectors rather than vector magnitude, making it invariant to document length—repeating a document twice leaves while Euclidean distance grows large.
Distinguish among Web Content Mining, Web Structure Mining, and Web Usage Mining, and explain the roles of the damping factor in PageRank and Hubs vs. Authorities in HITS.
Three Branches of Web Mining:
- Web Content Mining: Extracts patterns from page text, HTML structure, and multimedia.
- Web Structure Mining: Analyzes the directed hyperlink graph between pages.
- Web Usage Mining: Discovers navigation patterns and user preferences from server logs and clickstreams (after bot filtering and sessionization).
PageRank Damping Factor and HITS Hubs/Authorities:
- In PageRank, the damping factor (typically ) represents the probability that a random surfer keeps clicking outgoing links rather than jumping to a random page with probability , preventing rank sinks (dangling pages) and ensuring a unique stationary distribution.
- In HITS, Authorities are pages holding authoritative content endorsed by many incoming links, while Hubs are index/resource pages linking out to many good authorities; good hubs point to good authorities and good authorities are pointed to by good hubs.
Web Content Mining analyzes page contents, Web Structure Mining analyzes hyperlink topology, and Web Usage Mining analyzes clickstreams/logs. PageRank's damping factor prevents rank sinks via random teleportation, while HITS couples Hub (good out-links) and Authority (good in-links) scores.