Efficient algorithms for mining high-utility itemsets in uncertain databases

Jerry Chun Wei Lin*, Wensheng Gan, Philippe Fournier-Viger, Tzung Pei Hong, S. Tseng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

59 Scopus citations

Abstract

High-utility itemset mining (HUIM) is a useful set of techniques for discovering patterns in transaction databases, which considers both quantity and profit of items. However, most algorithms for mining high-utility itemsets (HUIs) assume that the information stored in databases is precise, i.e., that there is no uncertainty. But in many real-life applications, an item or itemset is not only present or absent in transactions but is also associated with an existence probability. This is especially the case for data collected experimentally or using noisy sensors. In the past, many algorithms were respectively proposed to effectively mine frequent itemsets in uncertain databases. But mining HUIs in an uncertain database has not yet been proposed, although uncertainty is commonly seen in real-world applications. In this paper, a novel framework, named potential high-utility itemset mining (PHUIM) in uncertain databases, is proposed to efficiently discover not only the itemsets with high utilities but also the itemsets with high existence probabilities in an uncertain database based on the tuple uncertainty model. The PHUI-UP algorithm (potential high-utility itemsets upper-bound-based mining algorithm) is first presented to mine potential high-utility itemsets (PHUIs) using a level-wise search. Since PHUI-UP adopts a generate-and-test approach to mine PHUIs, it suffers from the problem of repeatedly scanning the database. To address this issue, a second algorithm named PHUI-List (potential high-utility itemsets PU-list-based mining algorithm) is also proposed. This latter directly mines PHUIs without generating candidates, thanks to a novel probability-utility-list (PU-list) structure, thus greatly improving the scalability of PHUI mining. Substantial experiments were conducted on both real-life and synthetic datasets to assess the performance of the two designed algorithms in terms of runtime, number of patterns, memory consumption, and scalability.

Original languageEnglish
Pages (from-to)171-187
Number of pages17
JournalKnowledge-Based Systems
Volume96
DOIs
StatePublished - 15 Mar 2016

Keywords

  • High-utility itemset
  • Probabilistic-based
  • PU-list structure
  • Uncertain database
  • Upper-bound

Fingerprint Dive into the research topics of 'Efficient algorithms for mining high-utility itemsets in uncertain databases'. Together they form a unique fingerprint.

Cite this