Limits...
An incremental high-utility mining algorithm with transaction insertion.

Lin JC, Gan W, Hong TP, Zhang B - ScientificWorldJournal (2015)

Bottom Line: High-utility mining was designed to solve the limitations of association-rule mining by considering both the quantity and profit measures.Most algorithms of high-utility mining are designed to handle the static database.Fewer researches handle the dynamic high-utility mining with transaction insertion, thus requiring the computations of database rescan and combination explosion of pattern-growth mechanism.

View Article: PubMed Central - PubMed

Affiliation: School of Computer Science and Technology, Harbin Institute of Technology Shenzhen Graduate School, HIT Campus, Shenzhen University Town, Xili, Shenzhen 518055, China.

ABSTRACT
Association-rule mining is commonly used to discover useful and meaningful patterns from a very large database. It only considers the occurrence frequencies of items to reveal the relationships among itemsets. Traditional association-rule mining is, however, not suitable in real-world applications since the purchased items from a customer may have various factors, such as profit or quantity. High-utility mining was designed to solve the limitations of association-rule mining by considering both the quantity and profit measures. Most algorithms of high-utility mining are designed to handle the static database. Fewer researches handle the dynamic high-utility mining with transaction insertion, thus requiring the computations of database rescan and combination explosion of pattern-growth mechanism. In this paper, an efficient incremental algorithm with transaction insertion is designed to reduce computations without candidate generation based on the utility-list structures. The enumeration tree and the relationships between 2-itemsets are also adopted in the proposed algorithm to speed up the computations. Several experiments are conducted to show the performance of the proposed algorithm in terms of runtime, memory consumption, and number of generated patterns.

No MeSH data available.


Pseudocode of merge-list function.
© Copyright Policy - open-access
Related In: Results  -  Collection


getmorefigures.php?uid=PMC4355605&req=5

alg3: Pseudocode of merge-list function.

Mentions: For the designed incremental algorithm with transaction insertion, the original database is firstly scanned to construct the utility-list structures for all 1-itemsets and the EUCS structure for each item (Lines 2–8). Similarly, the inserted transactions are also scanned to construct the utility-list structures for all 1-itemsets. Each related TWU values of items in the built EUCS are also updated by the inserted transactions (Lines 9–15). The designed merge-list algorithm is used to combine the utility-list structures from the original database and inserted transactions into an updated utility-list structures (Line 16). After that, the 1-extensions of an itemset X are recursively processed (Lines 17–28) by using a depth-first procedure. Each itemset X is then determined by the designed condition to check whether it is a HUI (Lines 18–20). If an itemset is not a HUI, its extension is then determined by the designed condition based on two-phase model (Line 21) for depth-first search. Theupdated EUCS structure is also used to prune the unpromising itemset, thus reducing the search space for mining high-utility itemsets (Lines 24–26). The construction of utility-list structure algorithm is then performed to construct the extULs of X. The proposed HUI-list-INS algorithm is then recursively performed to mine HUIs (Lines 21–29). The algorithm is then terminated until no itemsets are generated. The merge-list algorithm to combine original database and the incremental one are described in Algorithm 3.


An incremental high-utility mining algorithm with transaction insertion.

Lin JC, Gan W, Hong TP, Zhang B - ScientificWorldJournal (2015)

Pseudocode of merge-list function.
© Copyright Policy - open-access
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC4355605&req=5

alg3: Pseudocode of merge-list function.
Mentions: For the designed incremental algorithm with transaction insertion, the original database is firstly scanned to construct the utility-list structures for all 1-itemsets and the EUCS structure for each item (Lines 2–8). Similarly, the inserted transactions are also scanned to construct the utility-list structures for all 1-itemsets. Each related TWU values of items in the built EUCS are also updated by the inserted transactions (Lines 9–15). The designed merge-list algorithm is used to combine the utility-list structures from the original database and inserted transactions into an updated utility-list structures (Line 16). After that, the 1-extensions of an itemset X are recursively processed (Lines 17–28) by using a depth-first procedure. Each itemset X is then determined by the designed condition to check whether it is a HUI (Lines 18–20). If an itemset is not a HUI, its extension is then determined by the designed condition based on two-phase model (Line 21) for depth-first search. Theupdated EUCS structure is also used to prune the unpromising itemset, thus reducing the search space for mining high-utility itemsets (Lines 24–26). The construction of utility-list structure algorithm is then performed to construct the extULs of X. The proposed HUI-list-INS algorithm is then recursively performed to mine HUIs (Lines 21–29). The algorithm is then terminated until no itemsets are generated. The merge-list algorithm to combine original database and the incremental one are described in Algorithm 3.

Bottom Line: High-utility mining was designed to solve the limitations of association-rule mining by considering both the quantity and profit measures.Most algorithms of high-utility mining are designed to handle the static database.Fewer researches handle the dynamic high-utility mining with transaction insertion, thus requiring the computations of database rescan and combination explosion of pattern-growth mechanism.

View Article: PubMed Central - PubMed

Affiliation: School of Computer Science and Technology, Harbin Institute of Technology Shenzhen Graduate School, HIT Campus, Shenzhen University Town, Xili, Shenzhen 518055, China.

ABSTRACT
Association-rule mining is commonly used to discover useful and meaningful patterns from a very large database. It only considers the occurrence frequencies of items to reveal the relationships among itemsets. Traditional association-rule mining is, however, not suitable in real-world applications since the purchased items from a customer may have various factors, such as profit or quantity. High-utility mining was designed to solve the limitations of association-rule mining by considering both the quantity and profit measures. Most algorithms of high-utility mining are designed to handle the static database. Fewer researches handle the dynamic high-utility mining with transaction insertion, thus requiring the computations of database rescan and combination explosion of pattern-growth mechanism. In this paper, an efficient incremental algorithm with transaction insertion is designed to reduce computations without candidate generation based on the utility-list structures. The enumeration tree and the relationships between 2-itemsets are also adopted in the proposed algorithm to speed up the computations. Several experiments are conducted to show the performance of the proposed algorithm in terms of runtime, memory consumption, and number of generated patterns.

No MeSH data available.