Incrementally mining high utility patterns based on pre-large concept

In traditional association rule mining, most algorithms are designed to discover frequent itemsets from a binary database. Utility mining was thus proposed to measure the utility values of purchased items for revealing high utility itemsets from a quantitative database. In the past, a two-phase high utility mining algorithm was thus proposed for efficiently discovering high utility itemsets from a quantitative database. In dynamic data mining, transactions may be inserted, deleted, or modified from a database. In this case, a batch mining procedure must rescan the whole updated database to maintain the up-to-date information. Designing an efficient approach for handling dynamic databases is thus a critical research issue in utility mining. In this paper, an incremental mining algorithm is proposed for efficiently maintaining discovered high utility itemsets based on pre-large concepts. Itemsets are first partitioned into three parts according to whether they have large (high), pre-large, or small transaction-weighted utilization in the original database and in inserted transactions. Individual procedures are then executed for each part. Experimental results show that the proposed incremental high utility mining algorithm outperforms existing algorithms.

I :

A set of m items, I={i ₁,i ₂,…,i _j ,…,i _m }, in which each item i _j has its own profit value p _j ;

P :

The profit table, {p ₁,p ₂,…,p _j ,…,p _m }, in which p _j is the profit value of item i _j ;

D :

The original quantitative database, D={T ₁,T ₂,…,T _k ,…,T _n }, in which each transaction contains several items with purchase quantities;

d :

The new transactions, d={t ₁,t ₂,…,t _k ,…,t _n }, in which each transaction contains several items with purchase quantities;

U :

The entire updated database, i.e., D∪d;

TU ^D :

The total utility of the transactions in D;

TU ^d :

The total utility of the transactions in d;

TU ^U :

The total utility of the transactions in U;

q _kj :

The quantity of item i _j in transaction t _k ;

u _kj :

The utility of item i _j in transaction t _k , which is calculated as q _kj ×p _j ;

tu _k :

The transaction utility of currently processed transaction t _k ;

buf :

A buffer used to store the total utility of the last processed transactions for transaction insertion. It is set to 0 after the database is rescanned;

X :

An itemset containing several items i _j ;

S _u :

The upper utility threshold for large (high) transaction-weighted utilization and high utility itemsets. It is the same as the high utility threshold in traditional utility mining;

S _l :

The lower utility threshold for pre-large transaction-weighted utilization and pre-large itemsets, where S _u >S _l ;

f :

The safety transaction utility bound for new transactions;

C _r :

The set of candidate r-itemsets;

Rescan_Items :

The set of the itemsets that must be rescanned in original database;

\(\mathit{HTWU}_{r}^{D}\) :

The set of large (high) transaction-weighted utilization r-itemsets in the original database;

\(\mathit{PTWU}_{r}^{D}\) :

The set of pre-large transaction-weighted utilization r-itemsets in the original database;

HTWU ^D :

The set of large (high) transaction-weighted utilization itemsets in the original database;

PTWU ^D :

The set of pre-large transaction-weighted utilization itemsets in the original database;

\(\mathit{HTWU}_{r}^{U}\) :

The set of large (high) transaction-weighted utilization r-itemsets in the updated database;

\(\mathit{PTWU}_{r}^{U}\) :

The set of pre-large transaction-weighted utilization r-itemsets in the updated database;

HTWU ^U :

The set of large (high) transaction-weighted utilization itemsets in the updated database;

PTWU ^U :

The set of pre-large transaction-weighted utilization itemsets in the updated database;

HU ^U :

The set of high-utility itemsets in the updated database;

twu ^D(X):

The transaction-weighted utilization of itemset X in the original database;

twu ^d(X):

The transaction-weighted utilization of itemset X in the new transactions;

twu ^U(X):

The transaction-weighted utilization of itemset X in the updated database;

au ^D(X):

The actual utility of itemset X in the original database;

au ^d(X):

The actual utility of itemset X in the new transactions;

au ^U(X):

The actual utility of itemset X in the updated database.

Authors and Affiliations

1. Innovative Information Industry Research Center (IIIRC), Harbin Institute of Technology Shenzhen Graduate School, HIT Campus Shenzhen University Town, Xili, Shenzhen, 518055, P.R. China

   Chun-Wei Lin

2. Shenzhen Key Laboratory of Internet Information Collaboration, School of Computer Science and Technology, Harbin Institute of Technology Shenzhen Graduate School, HIT Campus Shenzhen University Town, Xili, Shenzhen, 518055, P.R. China

   Chun-Wei Lin

3. Department of Computer Science and Information Engineering, National University of Kaohsiung, Kaohsiung, 811, Taiwan, R.O.C.

   Tzung-Pei Hong & Wen-Yang Lin

4. Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, 804, Taiwan, R.O.C.

   Tzung-Pei Hong & Jia-Wei Wong

5. Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, 701, Taiwan, R.O.C.

   Guo-Cheng Lan

Corresponding author

Correspondence to Tzung-Pei Hong.

Reprints and permissions