Single-pass incremental and interactive mining for weighted frequent patterns

摘要

Weighted frequent pattern (WFP) mining is more practical than frequent pattern mining because it can consider different semantic significance (weight) of the items. For this reason, WFP mining becomes an important research issue in data mining and knowledge discovery. However, existing algorithms cannot be applied for incremental and interactive WFP mining and also for stream data mining because they are based on a static database and require multiple database scans. In this paper, we present two novel tree structures IWFPT_(WA) (Incremental WFP tree based on weight ascending order) and IWFPT_(fd) (Incremental WFP tree based on frequency descending order), and two new algorithms IWFP_(WA) and IWFP_(Fd) for incre mental and interactive WFP mining using a single database scan. They are effective for incremental and interactive mining to utilize the current tree structure and to use the previous mining results when a database is updated or a minimum support threshold is changed. IWFP_(WA) gets advantage in candidate pattern generation by obtaining the highest weighted item in the bottom of IWFPT_(Wa)- IWFP_(fd) ensures that any non-candidate item cannot appear before candidate items in any branch of IWFPT_(fd) and thus speeds up the prefix tree and conditional tree creation time during mining operation. IWFPT_(FD) also achieves the highly compact incremental tree to save memory space. To our knowledge, this is the first research work to perform single-pass incremental and interactive mining for weighted frequent patterns. Extensive performance analyses show that our tree structures and algorithms are very efficient and scal able for single-pass incremental and interactive WFP mining.