PaperlayerView exact revision on arXiv

Source-linked AI summary

HUOPM: High Utility Occupancy Pattern Mining

Wensheng Gan, Jerry Chun-Wei Lin, Philippe Fournier-Viger, Han-Chieh Chao, Philip S. Yu

arXiv:1812.10926v1cs.DB

TL;DR

The paper addresses the limits of frequency-only and utility-only pattern mining, where patterns may be important yet unrepresentative of their supporting transactions. It proposes HUOPM, which combines frequency with utility occupancy and uses compact structures and pruning strategies to mine high-quality patterns. Experiments report useful patterns and more efficient search than the state-of-the-art algorithm.

  • Problem

    Existing frequency-based methods overlook item utility and may return patterns with low occupancy, while high utility pattern mining does not assess utility occupancy in supporting transactions.

  • Method

    HUOPM mines high utility occupancy patterns using frequency and utility occupancy, supported by UO-lists, an FU-table, an FU-tree, and pruning strategies.

  • Results

    HUOPM discovers useful high utility occupancy patterns and, with its pruning strategies, outperforms the state-of-the-art algorithm in runtime and search space.

  • Takeaways & Limitations

    Utility occupancy provides a pattern measure that accounts for both item utility and the portion of supporting-transaction utility contributed by the pattern.

Abstract

from arXiv · show

Mining useful patterns from varied types of databases is an important research topic, which has many real-life applications. Most studies have considered the frequency as sole interestingness measure for identifying high quality patterns. However, each object is different in nature. The relative importance of objects is not equal, in terms of criteria such as the utility, risk, or interest. Besides, another limitation of frequent patterns is that they generally have a low occupancy, i.e., they often represent small sets of items in transactions containing many items, and thus may not be truly representative of these transactions. To extract high quality patterns in real life applications, this paper extends the occupancy measure to also assess the utility of patterns in transaction databases. We propose an efficient algorithm named High Utility Occupancy Pattern Mining (HUOPM). It considers user preferences in terms of frequency, utility, and occupancy. A novel Frequency-Utility tree (FU-tree) and two compact data structures, called the utility-occupancy list and FU-table, are designed to provide global and partial downward closure properties for pruning the search space. The proposed method can efficiently discover the complete set of high quality patterns without candidate generation. Extensive experiments have been conducted on several datasets to evaluate the effectiveness and efficiency of the proposed algorithm. Results show that the derived patterns are intelligible, reasonable and acceptable, and that HUOPM with its pruning strategies outperforms the state-of-the-art algorithm, in terms of runtime and search space, respectively.

I. INTRODUCTION

Traditional frequent pattern mining emphasizes frequency, but patterns can also differ in utility and representativeness. HUOPM addresses this gap by mining patterns using frequency, utility occupancy, and compact pruning structures.

  • I. INTRODUCTION: Frequency-based mining may miss important patterns because items differ in utility, while frequent patterns may occupy only a small portion of their supporting transactions.Such low-occupancy patterns may be unrepresentative for applications such as recommendation.
  • I. INTRODUCTION: HUOPM mines patterns using users’ interests, frequency, and utility occupancy, allowing items to have distinct utilities.Utility occupancy evaluates a pattern’s utility contribution in its supporting transactions.
  • I. INTRODUCTION: HUOPM uses UO-lists and FU-tables to store database information and avoid repeatedly scanning the database when mining patterns.These structures support direct retrieval of information from prefix patterns when sufficient conditions hold.
  • I. INTRODUCTION: Remaining utility occupancy provides an upper bound for pruning, enabling HUOPM to discover patterns from an FU-tree using only two database scans.The algorithm combines this bound with its compact data structures to reduce search effort.
  • I. INTRODUCTION: Experiments on real-world and synthetic datasets show that HUOPM finds useful patterns with high utility occupancy and predefined frequency while producing a more compact search space.The experiments evaluate both effectiveness and efficiency of the algorithm and its pruning strategies.

B. Utility-based Pattern Mining

Utility-based pattern mining incorporates item quantities and profits, while utility occupancy measures how much of supporting transactions a pattern contributes. HUOPs require both sufficient support and utility occupancy.

  • Utility-based mining considers item quantities and unit profits, revealing patterns that may be more valuable than frequency-based patterns.
  • Utility occupancy complements utility by comparing a pattern’s utility with the total utility of transactions where it appears.
  • Utility occupancy generalizes item-count occupancy by accounting for distinct item utilities across supporting transactions.
  • A HUOP must satisfy minimum support and minimum utility occupancy thresholds simultaneously.
  • The running example derives HUOPs at α=30% and β=0.30, including singletons, pairs, and larger itemsets.

IV. PROPOSED ALGORITHM FOR MINING HUOPS

HUOPM uses compact utility-occupancy structures to retain database information and prune the search space using support and utility occupancy.

  • UO-lists and FU-tables maintain utility occupancy information for mining high utility occupancy patterns.
  • HUOPM combines support and utility occupancy measures to prune the search space.

A. Search Space for Mining HUOPs

HUOPs do not obey Apriori’s downward closure, so HUOPM represents the complete search space with an ordered FU-tree. The tree supports systematic traversal by extending prefix nodes.

  • A. Search Space for Mining HUOPs: HUOP mining cannot rely on Apriori downward closure because non-HUOP singletons may have HUOP supersets.
  • A. Search Space for Mining HUOPs: HUOPM orders items by support ascending order, while alternative total orders preserve completeness and correctness but may change efficiency.
  • A. Search Space for Mining HUOPs: The FU-tree is a frequency-utility variant of a sorted set-enumeration tree containing frequency and utility information.
  • A. Search Space for Mining HUOPs: The complete FU-tree search space can be traversed by depth-first or breadth-first search, with child nodes generated by extending parent prefixes.

B. UO-List and FU-Table

HUOPM uses UO-lists and FU-tables to retain transaction-level and aggregate utility-occupancy information, enabling exact pattern evaluation and database-scan-free construction of larger itemsets.

  • UO-list: Remaining utility occupancy sums the utility contributions of items appearing after an itemset under the total item order.For T5, ruo(a,T5) is approximately 0.6735, while ruo(ad,T5) is approximately 0.4490.
  • UO-list: UO-lists store transaction identifiers, utility occupancy, and remaining utility occupancy for every transaction containing an itemset.These structures support direct calculation of support, utility occupancy, and remaining utility occupancy.
  • Construction: The UO-list and FU-table of each frequent 1-itemset are initially constructed in one database scan.
  • FU-table: FU-tables summarize an itemset by its name, support, summed utility occupancy, and summed remaining utility occupancy.
  • Construction: For larger itemsets, HUOPM constructs UO-lists by joining subset lists and subtracting common utility occupancy to avoid double counting.For example, the utility occupancy of a three-itemset combines two extension values and subtracts their shared component.

C. Upper Bound on Utility Occupancy

Because utility occupancy lacks downward closure and descendant support is unknown, HUOPM derives an upper bound from UO-list information to prune unpromising subtrees.

  • Motivation: The search space contains 2^m possible itemsets, making pruning essential because utility occupancy does not satisfy downward closure.
  • Challenge: Unknown descendant support prevents direct upper-bound calculation, although every descendant’s supporting transactions are contained in its parent’s.
  • Upper-bound construction: HUOPM computes an upper bound by sorting uo(X,Tq) + ruo(X,Tq) over the parent’s supporting transactions and averaging the top α × |D| values.The bound can safely discard a subtree when it is below the minimum utility-occupancy threshold.

D. Proposed Pruning Strategies

HUOPM combines global support closure with conditional utility-occupancy closure and four pruning strategies to remove unsupported or low-potential subtrees.

  • Closure properties: The FU-tree has global downward closure for support: a node’s support cannot exceed its parent’s support.
  • Closure properties: Utility-occupancy upper bounds satisfy partial downward closure only within a subtree, not across arbitrary supersets.
  • Pruning strategies: HUOPM prunes a node’s supersets when its support is below α × |D| or its utility-occupancy upper bound is below β.
  • Example: With α = 30% and β = 0.3, itemset (ea) has support 2 instead of the required 3, so all its extension nodes are pruned.
  • Pruning strategies: The remaining-support and empty-or-low-support checks stop UO-list construction or extension storage when descendants cannot meet minimum support.

E. Proposed HUOPM Algorithm

HUOPM scans the database to initialize frequent-item structures, then recursively explores the FU-tree using support tests, utility-occupancy bounds, and UO-list joins.

  • Algorithm: HUOPM takes a database, profit table, minimum support α, and minimum utility-occupancy β as inputs.
  • Initialization: Initialization scans the database to compute item supports and transaction utility, orders frequent items, and builds their UO-lists and FU-tables.
  • Pruning effect: Partial anti-monotonicity prunes low-support or low-utility-occupancy patterns before UO-list construction, reducing joins and the effective FU-tree search space.
  • Recursive search: The recursive search reports an itemset when support reaches α × |D| and utility occupancy reaches β, then explores extensions only when their upper bound reaches β.
  • Upper-bound computation: The upper-bound procedure sorts transaction values and averages the selected top values, with complexity reported as O(n × log(n) × V↓occu[k]).

V. EXPERIMENTS

The experiments evaluate HUOPM against closely related OCEAN methods on real-world and synthetic datasets, focusing on pattern discovery, runtime, search-tree exploration, and item ordering.

  • The study evaluates high utility occupancy pattern mining on both real-world and synthetic datasets.The addressed task is discovering patterns using frequency and utility occupancy.
  • OCEAN is the state-of-the-art comparison algorithm, while HUOPM generates the proposed complete pattern set.
  • HUOPM experiments compare derived patterns, execution time, visited search-tree nodes, and item-processing order against OCEAN.The evaluation uses HUOPs* from OCEAN and HUOPs from HUOPM.

A. Experimental Setup and Datasets

The experiments run Java implementations on six real-world and synthetic datasets with varied sizes, densities, and transaction lengths, using randomly generated item quantities and unit profits for utility-based mining.

  • Six datasets—four real-world and two synthetic—cover sparse and dense databases with varied transaction counts, item counts, and average lengths.The datasets are BMSPOS2, retail, chess, mushroom, T10I4D100K, and T40I10D100K.
  • The experiments use Java on a 3.2 GHz Intel Core i5-3460 PC with 4 GB memory and 32-bit Windows 7.
  • The datasets include retail as sparse, while chess and mushroom are dense, providing contrasting transaction structures for evaluation.
  • T40I10D100K contains 100,000 transactions, 942 distinct items, and average transaction length 39.6; item quantities and unit profits are randomly generated.

B. Pattern Analysis

Pattern analysis shows that HUOPM discovers more high utility occupancy patterns than OCEAN, including patterns OCEAN misses, while pattern counts vary with α, β, and support thresholds.

  • In the running example, HUOPM’s top-10 results include three HUOPs absent from OCEAN, and their minimum utility occupancy is 0.6554 versus 0.5604 for OCEAN-derived patterns.
  • Across varied α and β settings, HUOPs* is always smaller than HUOPs, indicating that OCEAN misses patterns found by HUOPM.The number of produced patterns decreases as minimum support increases, and fewer patterns are obtained at higher β.
  • Tables IV and V report derived-pattern counts while varying α under fixed β and β under fixed α, respectively.
  • HUOPM discovers numerous high utility occupancy patterns that OCEAN misses, addressing OCEAN’s incomplete pattern coverage.The paper concludes that HUOPM can discover the complete HUOP set more effectively than OCEAN.

C. Efficiency Analysis

Efficiency analysis finds HUOPM faster than OCEAN across the tested settings, with all four pruning strategies producing the fastest variant and reducing runtime or search effort.

  • HUOPMP 1234, which uses all pruning strategies, is fastest on every dataset in all tested cases, while OCEAN is usually slowest.
  • Strategy 3 reduces the search space by pruning subtrees, while Strategy 4 significantly reduces execution time in several tested settings.
  • Strategy 2 trades efficiency against effectiveness because calculating utility-occupancy upper bounds adds time but can prune unpromising itemsets.
  • Two-way ANOVA finds a significant runtime difference between HUOPM and OCEAN in most cases under varied α with fixed β.Reported examples include P = 0.019, P < 0.001, and one nonsignificant case with P = 0.116.

D. Effect of Pruning Strategies

HUOPM’s pruning strategies reduce both the FU-tree search space and runtime as frequency and utility-occupancy thresholds increase. Support-ascending item processing provides the best runtime and memory performance among the evaluated orders.

  • D. Effect of Pruning Strategies: HUOPM prunes more nodes and runs faster as α or β increases, producing a smaller search space.The number of visited nodes reflects, to some extent, the execution time required for processing the FU-tree.
  • D. Effect of Pruning Strategies: HUOPMP1234 consistently achieves the lowest runtime among the four algorithm versions, although Strategy 4 does not reduce visited nodes beyond Strategy 3.N3 and N4 remain identical as α and β increase, while the full strategy combination still reduces runtime.
  • D. Effect of Pruning Strategies: The upper-bound strategy makes the search space more compact by pruning unpromising patterns on both sparse and dense datasets.This follows from comparing N2 and N3, with and without the upper bound.
  • E. Processing Order of Items: HUOPMtwuas performs similarly to HUOPMsupas but requires more memory on the reported datasets.The comparison is shown for the accidents and retail datasets.
  • E. Processing Order of Items: Support-ascending item processing delivers the best execution-time and memory performance among the five evaluated orders.The adopted order also reduces the number of UO-lists and join operations performed during mining.
Loading 1812.10926v1…