Exact and heuristic approaches for mining top-k high-utility itemsets in uncertain databases with mixed utilities

Extracting meaningful patterns from complex, real-world environments, such as noisy IoT sensor networks or e-commerce systems with promotional discounts, requires handling data uncertainty and mixed profit structures. Top-k high-utility itemset mining identifies the k most profitable patterns in transactional data without requiring a user-defined minimum utility threshold. Existing algorithms are designed only for deterministic databases with positive item profits and do not address uncertain data containing both positive and negative utilities. To bridge this critical gap, this paper formulates this problem and introduces two complementary algorithmic approaches. The first approach, PTK-HUIM, is an exact prefix-growth framework based on the Utility-Probability-Utility List (UPU-List) and a two-level pruning mechanism using Positive Transaction-Weighted Utility (PTWU) and Positive Upper Bound (PUB). PTK-HUIM supports three search strategies: depth-first search, breadth-first search, and best-first search. All three strategies are proven to produce the same correct results. The second approach, UTKU-PSO, is the first heuristic algorithm developed for this problem. It extends Particle Swarm Optimization by incorporating probability-aware fitness estimation, PTWU-based bit clearing, and a shifted roulette-wheel selection mechanism to effectively handle negative expected utilities. A counterexample establishes that the classical transaction-weighted utility bound remains unsafe in this combined setting even after probability weighting, so PTWU and PUB are required for correctness rather than merely for efficiency. Since no natively uncertain benchmark with mixed utilities is publicly available, the evaluation augments six real-world benchmark datasets with synthetic existential probabilities, and every reported result is therefore conditional on that assumed model; robustness is assessed under three further probability models, one of which violates the independence assumption and shifts the identity of up to 61% of the top-k set. Experiments show that no single search strategy dominates: pairwise differences are not statistically significant across the suite, because frontier-ordered strategies visit up to 5.9 times fewer nodes but pay up to 17.9 times more per node, and which term prevails depends on transaction length and k. On large, sparse datasets the runtime of UTKU-PSO grows only mildly with k, making it up to 5.6 times faster than the exact family. Its set accuracy, however, degrades substantially at very large k: at k = 20,000 on the sparsest benchmark roughly half of the returned set falls outside the exact top-k, although 83% of the total expected utility is still recovered. Instrumentation traces this to the search space widening faster than the fixed budget can cover it, and a diagnostic requiring no ground truth tracks true accuracy at Spearman rho = 0.998. The proposed framework provides a practical solution with explicitly characterised trade-offs between accuracy and efficiency for utility-driven data analytics in uncertain environments.