PadhaikoAll subjects

Moving On: Applications and Beyond

Data Mining (ENCT 435)

Open in the Padhaiko app

8.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:

2. Data Stream Mining and Concept Drift

Definition

Data Stream Constraints and Concept Drift

Key Streaming Algorithms and Drift Adaptation

  1. 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.

  1. 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

  1. Tokenization & Case Folding: Split text into word tokens (removing punctuation) and convert to lowercase.
  2. Stopword Removal: Discard high-frequency, low-discrimination function words (the, is, and, of).
  3. Stemming / Lemmatization: Reduce inflected words to a common root (mining, mined, mines mine; e.g., Porter stemmer) to merge semantically equivalent tokens.
  4. -Grams (Optional): Include word bigrams (not good, credit card) alongside single unigrams when word order matters.

Vector Space Model, TF-IDF, and Cosine Similarity

Definition

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):

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:

Three Categories of Web Mining
BranchPrimary Data SourceRepresentative Techniques & Applications
Web Content MiningText, HTML DOM, tables, images, and metadata inside web pagesWeb crawling, information extraction, page classification, product review mining
Web Structure MiningDirected hyperlink graph between pagesPageRank (global link authority), HITS (Hubs & Authorities), spam-link detection
Web Usage MiningServer access logs, clickstreams, cookies, session historiesBot filtering, sessionization, frequent path/association discovery, personalized recommendations

Link Analysis: PageRank and HITS

where is the set of pages linking into and is the total out-degree of page .


Worked Examples

Example 1

Computing TF-IDF Weights and Cosine Similarity Between Documents (6 marks)

  1. In a corpus of documents, the term "mining" appears times in document and occurs in documents overall. Compute using base- logarithm.
  2. 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 ).

Answer:
  1. .
  2. Cosine Similarity .
Example 2

Computing PageRank Update and Hoeffding Bound for Streams (6 marks)

  1. 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 .
  2. 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.

Answer:
  1. .
  2. Hoeffding bound .

Exercises

Practice Exercises — Massive Datasets, Streams, Text & Web Mining

Question 1

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:

  1. Single-pass processing: Each item can be inspected once and cannot be stored permanently for multiple epochs.
  2. Bounded memory: Summary statistics or sketches must fit in fixed RAM regardless of stream length.
  3. 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:

  1. 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.
  2. 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.
Answer:

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.

Question 2

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 ():

Answer:

VFDT splits a leaf once using only per-leaf counts. For , , and , .

Question 3

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:

Answer:

Preprocessing converts raw text via tokenization, stopword removal, and stemming. Here and Cosine Similarity .

Question 4

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.

Answer:

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.

Question 5

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.
Answer:

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.

← Data Transformations