Abstract
Detecting distribution shifts, or concept drift, in high-dimensional transactional data streams is a significant challenge in data mining. Traditional methods often rely on fixed sliding windows or are limited to simple numerical data. We present StreamKrimp, an algorithm that utilizes the Minimum Description Length (MDL) principle to detect changes in discrete data streams. By modeling data through compression using the KRIMP framework, StreamKrimp identifies structural shifts efficiently without the need for exhaustive history storage. Our evaluation across benchmark, synthetic, and real-world datasets demonstrates that StreamKrimp achieves high purity in segment identification and scales effectively to large-scale transactional data.
Introduction
In the era of big data, streams such as financial transactions, sensor logs, and retail market baskets are ubiquitous. These streams are often infinite and dynamic, characterized by "concept drift"—changes in the underlying data-generating process over time. Identifying these shifts is crucial for maintaining the accuracy of predictive models and gaining insights into evolving patterns.
However, transactional data presents unique difficulties: it is high-dimensional, discrete, and lacks the natural ordering found in numerical data. Conventional "sliding window" techniques require pre-defined window sizes, which often lead to a trade-off between sensitivity and latency. StreamKrimp addresses these issues by using a compression-based approach that adapts to the data's inherent structure.
Methods
StreamKrimp is built upon the Minimum Description Length (MDL) principle, which suggests that the best model for a dataset is the one that provides the shortest total description (model length + data length given the model).
1. KRIMP and Code Tables
The core of StreamKrimp is the KRIMP algorithm, which induces "code tables"—dictionaries of frequent itemsets used to compress transactions. The efficiency of this compression depends on the COVER algorithm, which determines how a transaction is represented using the available itemsets in the code table.
The COVER algorithm (Algorithm 1) employs a greedy strategy: for a given transaction $s$, it selects the first itemset $c$ from the code table $CT$ that is a subset of $s$. It then recursively applies this process to the remaining items ($s \setminus T$) until the entire transaction is covered. This greedy approach ensures that the most descriptive (and typically longest) patterns are prioritized for compression.
2. Convergence via Improvement Rate (IR)
Instead of using a fixed window, StreamKrimp monitors the Improvement Rate (IR). It builds a code table on the initial portion (the "head") of the stream, continuously adding data until the compression gain levels off. This stabilization indicates that the model has successfully captured the current distribution's characteristics.
3. Change Detection via Code Table Difference (CTD)
Once a stable model is established, StreamKrimp monitors incoming data blocks. It compares the compression performance of the current code table against a newly induced candidate table. A significant drop in performance, measured as the Code Table Difference (CTD), signals a "split," marking a change in the data distribution.
4. SkipBlocks Optimization
To enhance computational efficiency and save power, the algorithm incorporates SkipBlocks. This optimization uses statistical tests to bypass full model re-induction for data blocks that align well with the current model, only triggering intensive computation when the data appears "suspicious."
Experimental Evaluation
The authors validated StreamKrimp using a diverse set of data:
- UCI Repository Benchmarks: Seven datasets (e.g., Adult, Mushroom) were transformed into streams by concatenating class-labeled segments. StreamKrimp achieved purity scores often exceeding 90%, accurately identifying original class boundaries.
- Synthetic Streams: Controlled tests showed the algorithm is highly sensitive to pattern removal and the splitting or merging of itemsets, detecting 4 out of 6 primary types of distribution changes.
- Accidents Dataset: On a real-world dataset of over 340,000 traffic records from Flanders (1991–2000), StreamKrimp summarized a decade of data into just 14 distinct code tables, highlighting major structural shifts in accident patterns over ten years.
Key Insights
A fundamental insight of StreamKrimp is that compression serves as a robust proxy for similarity. If a model built on Segment A fails to compress Segment B, the two segments are fundamentally different. Furthermore, the algorithm provides "characterization" rather than just detection; the resulting code tables offer a human-interpretable summary of the data's structure at any given time, allowing researchers to inspect what changed, not just when.
Limitations and Future Work
While powerful, StreamKrimp has limitations. It may struggle with very subtle shifts, such as minor frequency changes in existing patterns. Additionally, its sensitivity is tied to the minsup (minimum support) parameter, and inducing new code tables is more computationally expensive than simple statistical counters. Future work may explore the application of these code tables for real-time classification and more sophisticated stream summarization.
Summary updated