Weighted FP-Tree Mining Algorithms for Conversion Time Data Flow

Xiaojun Chen, Jia Ke, Qianqian Zhang, Xinping Song, Xiao‐Ming JiangInternational Journal of Database Theory and Application 2016 · DOI

TL;DR

This paper introduces a novel "time gap degree" concept to enhance association rule mining in dynamic time-series data streams. By incorporating these time-based weights into an FP-Tree algorithm (FPSPAN-Growth), the authors achieve improved recall and precision in discovering relationships, outperforming traditional FP-Growth and Apriori methods.

What Problem Does This Paper Address?

Data streams are characterized by their dynamic, ever-changing nature and temporal correlations. Traditional association rule mining algorithms, which often treat data as static transactions, struggle to accurately capture the relationships within these time-varying data streams. This is because they fail to account for the varying time intervals between data points, leading to inaccurate or incomplete insights. The challenge lies in developing mining techniques that can effectively leverage the temporal aspect of data streams to uncover meaningful patterns.

Methods

The core contribution of this paper is the introduction of the "time gap degree" concept. This metric quantifies the temporal characteristics of transactions within a data stream. The authors then propose a modified FP-Tree mining algorithm, termed FPSPAN-Growth, which integrates these time gap degrees as weights.

Here's a breakdown of the approach:

  • Time Gap Degree: This new concept is used to represent the time intervals between successive data points or events within a transaction. It's essentially a weighted measure of temporal proximity.
  • Weighted FP-Tree (FPSPAN-Tree): The standard FP-Tree structure is adapted to incorporate these time gap degrees as node weights. This allows the tree to dynamically represent the temporal significance of items.
  • FPSPAN-Growth Algorithm: This algorithm builds upon the FP-Growth framework but modifies the support counting mechanism to consider the time gap weights. Instead of just counting item occurrences, it calculates a weighted support, making it more sensitive to temporal patterns. The algorithm recursively constructs conditional FP-Trees, but now with weighted nodes, to efficiently mine frequent item sets.

Datasets

The paper uses a dataset described as "actual datasets (international classification of diseases 10 from Hospital Information System)" for simulation experiments. No new benchmark datasets are introduced.

Key Insights and Ideas

  • Temporal Dynamics Matter: The paper strongly emphasizes that simply treating time-series data as static transactions misses crucial information. The temporal relationships, captured by the "time gap degree," are vital for accurate pattern discovery.
  • Weighting for Accuracy: Introducing weights based on time gap degrees significantly improves the accuracy of association rule mining. This is because it allows the algorithm to prioritize relationships that are temporally more relevant or significant.
  • FPSPAN-Tree vs. FP-Tree: The visual comparison in Figure 1 highlights how the FPSPAN-Tree structure, with its weighted nodes, can lead to different ordering and relationships of item sets compared to a standard FP-Tree. This difference is attributed to the time gap weights influencing the mining process.
  • Improved Recall and Precision: The experimental results demonstrate that the FPSPAN-Growth algorithm achieves higher recall (completeness of discovered rules) and precision (accuracy of discovered rules) compared to traditional FP-Growth and Apriori.

Key Results

  • Improved Performance Metrics: The FPSPAN-Growth algorithm consistently outperformed FP-Growth and Apriori in terms of Recall and Precision. For instance, at a minsup of 40%, FPSPAN-Growth showed the highest Recall, and significantly higher Precision than FP-Growth.
  • Comparable Computational Time: While FPSPAN-Growth incurs a slight overhead due to the calculation of cumulative time gap weights, its overall execution time is comparable to FP-Growth and significantly faster than Apriori-based multidimensional association rule mining algorithms. The paper notes that the executive time of FPSPAN-Growth is "a little lager than that of FP-Growth" but still efficient.
  • Reduced Rule Generation (with higher accuracy): Figure 4 shows that FPSPAN-Tree generates fewer association rules than FP-Tree. This is attributed to the algorithm's ability to filter out more non-frequent items due to the timing parameters, leading to a more accurate set of rules.

Limitations and Future Work

  • Slightly Higher Execution Time: The authors acknowledge that FPSPAN-Growth is slightly slower than FP-Growth due to the additional computation involved in calculating cumulative time gap weights.
  • Future Work: The paper doesn't explicitly detail future work directions, but the success in incorporating temporal dynamics suggests potential for applying this weighted approach to other time-series data mining tasks or exploring more sophisticated weighting schemes. The authors also mention that the algorithm is designed for "conversion time data flow," implying potential for further exploration in specific application domains.

Summary updated

Abstract

The data distribution in the data streams usually changes dynamically with time. Traditional mining algorithms based on transaction are difficult to establish the correlation between time characteristics and relationship features, thus making the results inaccurate. By analyzing the problems in the processing of time data stream, we put forward the concept of time gap degrees and design a mining algorithms based on weighted FP-Tree. We introduce the concept of FP-Tree node weights to transform the time data dynamically and excavate the data stream association rules. The experiments performed on the actual data set show that the algorithm can improve the recall and precision while consumes comparable computational time.
BibTeX
@article{chen2016weighted,
  author = {Xiaojun Chen and Jia Ke and Qianqian Zhang and Xinping Song and Xiao‐Ming Jiang},
  title = {{Weighted FP-Tree Mining Algorithms for Conversion Time Data Flow}},
  journal = {International Journal of Database Theory and Application},
  year = {2016},
  doi = {10.14257/ijdta.2016.9.1.15},
}
Figure