CLOHUI : An Efficient Algorithm for Mining Closed High Utility Itemsets from Transaction Databases

摘要

High-utility itemset mining (HUIM) is an important research topic in data mining field and extensivealgorithms have been proposed. However, existing methods for HUIM present too many high-utilityitemsets (HUIs), which reduces not only efficiency but also effectiveness of mining since users have to siftthrough a large number of HUIs to find useful ones. Recently a new representation, closed+ high-utilityitemset (CHUI), has been proposed. With this concept, the number of HUIs is reduced massively. Existingmethods adopt two phases to discover CHUIs from a transaction database. In phase I, an itemset is firstchecked whether it is closed. If the itemset is closed, an overestimation technique is adopted to set an upperbound of the utility of this itemset in the database. The itemsets whose overestimated utilities are no lessthan a given threshold are selected as candidate CHUIs. In phase II, the candidate CHUIs generated fromphase 1 are verified through computing their utilities in the database. However, there are two problems inthese methods. 1) The number of candidate CHUIs is usually very huge and extensive memory is required.2) The method computing closed itemsets is time consuming. Thus in this paper we propose an efficientalgorithm CloHUI for mining CHUIs from a transaction database. CloHUI does not generate anycandidate CHUIs during the mining process, and verifies closed itemsets from a tree structure. We proposea strategy to make the verifying process faster. Extensive experiments have been performed on sparse anddense datasets to compare CloHUI with the state-of-the-art algorithm CHUD, the experiment results showthat for dense datasets our proposed algorithm CloHUI significantly outperforms CHUD: it is more thanan order of magnitude faster, and consumes less memory.