Dynamic FP-Growth: Solving Volatility in Social Media Event Detection

TL;DR

Researchers have developed a framework that automatically detects real-world events from the "firehose" of Twitter data using Frequent Pattern Mining (FPM). The breakthrough lies in a dynamic support threshold that adapts to the daily volume of tweets, ensuring the system finds meaningful news even when moving from a quiet day to a viral surge.

Background: The Social Sensor Network

Social networks act as a massive, distributed sensor network. Often, a breaking news story—like the Ferguson shooting or the Greece Crisis—hits Twitter minutes before official news wires. However, mining this data is like drinking from a high-pressure hose: the data is unstructured, fast, and of varying volume.

The Problem: The "Fixed Threshold" Trap

The standard tool for finding trending topics is Frequent Pattern Mining (FPM). In FPM, you need a "support value"—a minimum frequency for a word to be considered important.

• Fixed Support is Brittle: If you set a support of 100, a quiet day might return 0 results, while a busy election day might return 10,000 irrelevant patterns.
• Prior Work: Traditional methods (like Apriori) require scanning the database multiple times, which is impossible in a live stream that never ends and can't be backtracked.

Methodology: High-Adaptability Stream Reasoning

The proposed framework utilizes a three-stage pipeline: Support Definition → FP-Growth Mining → Post-Processing.

1. The Dynamic Support Formula

Instead of guessing a threshold, the authors calculate it on-the-fly for every window (24 hours of data): $S_{pp}=avg(S_T)imesmedian(S_T)$ By multiplying the average frequency by the median, the threshold naturally scales with the density and variety of the conversation.

2. Handling "Small" Windows with Logistic Regression

On days with low engagement, noise often appears "frequent" relatively. To fix this, the authors used a Logistic Regression (LR) model to classify windows. If a window is deemed "small," the support value is doubled to enforce stricter entry requirements for patterns.

Figure 1: The abstract model showing the flow from stream batching to post-processed events.

Experiments: Validating against Global News

The system was tested on the 2015 UK General Election (1 million tweets) and the Greece Crisis (150k tweets).

Key Findings:

• Accuracy: Detected events (e.g., "SNP says Sir John Major's speech very foolish") perfectly matched headlines from The Guardian and BBC on the same day.
• Compression: Post-processing (using Cosine Similarity) successfully merged redundant patterns, reducing the "messy" output of raw mining into clean event strings.
• Robustness: The dynamic threshold successfully scaled from a support of 21 (on quiet days) to 544 (on peak election days).

Figure 2: Sample results showing the high alignment between frequent patterns and real news headlines.

Critical Insight: Why Average was Not Enough

A naive approach might simply use the average frequency as a threshold. However, the authors discovered that words appearing only once account for roughly 1/3 of distinct terms. By incorporating the median and using a branch-size restriction in the FP-tree, they effectively pruned the "long tail" of social media noise that usually clogs event detection systems.

Conclusion & Lessons

This work demonstrates that for event detection to be viable in production, it must be statistically aware of the stream it is processing. The use of a dynamic, median-based support threshold provides a simple yet mathematically sound way to ensure that "frequency" always implies "significance," regardless of how much people are tweeting.

Future Work: The authors plan to implement a ranking mechanism to prioritize events when multiple significant topics emerge simultaneously.