Abstract This paper introduces a two-phase framework for clustering massive streams of short, noisy text (like tweets) into distinct real-world events. By combining a fast, single-pass online clustering step with an on-demand offline merging phase, the system efficiently groups related messages even when users describe the exact same event using completely different vocabularies.
Introduction
Social media platforms generate an enormous volume of "microtext"—short, informal, and grammatically varied messages. Identifying real-world events from this firehose is highly valuable for news tracking and emergency response, but it remains a significant challenge.
Traditional document clustering algorithms struggle with microtext for two main reasons: first, they cannot scale to the sheer volume and velocity of streaming social media data; second, the extreme brevity and sparsity of the text mean that standard similarity metrics often fail. Furthermore, people often use completely different words to describe the exact same event depending on their personal style. Existing methods mostly focus on static datasets or rely heavily on surface-level features, leaving a gap for a scalable solution that can continuously cluster dynamic text streams in real-time while still producing coherent, event-level groupings.
Methodology
The authors propose a framework called MSC (Microtext Stream Clustering) that splits the computational workload into two distinct phases:
- Online Discovery Phase: A highly efficient, single-pass algorithm processes incoming tweets. It uses a combined similarity measure that factors in both textual similarity (using Term Frequency) and temporal similarity (using an exponential decay function, as tweets published closer together are more likely related). Instead of storing all historical tweets, the system maintains lightweight "cluster feature vectors" (a textual centroid, a time centroid, and the cluster size). If a new tweet is similar enough to an active cluster, it updates these centroids; if not, it spawns a new base cluster.
- Offline Cluster Merging Phase: Because users use different words for the same event, the online phase might create multiple fragmented "base clusters" for a single event. Upon user request, an offline process merges these base clusters from the bottom up. It uses a custom validation index based on cluster "separation" to automatically determine the optimal number of final clusters, stopping the merge process when cluster distinctness begins to drop.
Experimental Evaluation
The study utilized an annotated corpus of 2,633 tweets collected between July and September 2011. The dataset covers 27 distinct real-world events, ranging from the London riots to the Virginia earthquake and NASA Mars announcements. Tweets were preprocessed to remove URLs, @mentions, and stopwords, and underwent shallow lexical normalization (e.g., reducing the informal "crazyyyyy" to "crazy").
Key Results
The proposed MSC algorithm outperformed standard Incremental Clustering (IC) and time-aware Incremental Clustering (IC-Time) across the board.
As shown in the table above, when retaining the "#" symbol, MSC achieved an F-measure of 0.958 and NMI of 0.955. Stripping the "#" symbol to treat hashtags as normal words further improved performance, with MSC reaching an F-measure of 0.966 and NMI of 0.962. This suggests that treating hashtags as standard vocabulary increases the term frequency of core entities, aiding the vector-space model in finding similarities.
Furthermore, MSC consistently maintained higher clustering accuracy over various time horizons compared to the baselines.
This stability over time proves that the offline merging phase successfully stitches fragmented conversations back together even as the stream progresses.
Discussion and Future Work
A key insight from this work is that time is just as important as text. Incorporating a time-decay similarity measure prevents the algorithm from grouping topically similar but temporally distant tweets into the same event. Additionally, the use of summary statistics allows the algorithm to scale to massive streams without needing to hold raw text in memory.
Limitations: The evaluation was performed on a relatively small, curated dataset. While the algorithm is designed for scale, the paper does not benchmark its computational speed or memory usage on a true, massive-scale live firehose.
Future Work: The authors plan to integrate this clustering algorithm into a larger Emergency Situation Awareness (ESA) system. They also suggest exploring semantic techniques, such as paraphrasing models, to better connect tweets that discuss the same event using entirely different, non-overlapping vocabularies.
Citation: Jie Yin. Proceedings of the Sixth International Joint Conference on Natural Language Processing. 2013.
Summary updated