Mining Maximal High Utility Itemsets on Dynamic Profit Databases

Abstract

To overcome the limitation of high-utility itemset mining, more compact, lossless, and concise representations of high utility itemsets (HUIs) have been proposed in previous works, such as closed HUIs (CHUIs) or maximal HUIs (MHUIs). Focusing into MHUI mining, in this article, we present efficient approaches to directly mine MHUIs from transactional databases without generating any candidates. The proposed algorithms, which all execute in one phase, utilize many efficient data structures and pruning techniques such as EUCP combined with EUCS, CUIP combined with FUCS, and the P-set structure to significantly reduce the search space and remove nonpromising itemsets, thus, increase the performance of the MHUI mining process. Furthermore, while previous works assumed that the unit profit of items is fixed, which is not practical in many real-world applications, our work resolved this issue by applying a new utility calculation into the mining process to reflect the true nature of real-world databases, thus, generating more accurate results.     

Efficient closed high-utility pattern fusion model in large-scale databases

High-Utility Itemset Mining (HUIM) is considered a major issue in recent decades since it reveals profit strategies for use in industry for decision-making. Most existing works have focused on mining high-utility itemsets from databases showing large amount of patterns; however exact decisions are still challenging to make from that large amounts of discovered knowledge. Closed High-utility itemset mining (CHUIM) provides a smart way to present concise high-utility itemsets that can be more effective for making correct decisions. However, none of the existing works have focused on handling large-scale databases to integrate discovered knowledge from several distributed databases. In this paper, we first present a large-scale information fusion architecture to integrate discovered closed high-utility patterns from several distributed databases. The generic composite model is used to cluster transactions regarding their relevant correlation that can ensure correctness and completeness of the fusion model. The well-known MapReduce framework is then deployed in the developed DFM-Miner algorithm to handle big datasets for information fusion and integration. Experiments are then compared to the state-of-the-art CHUI-Miner and CLS-Miner algorithms for mining closed high-utility patterns and the results indicated that the designed model is well designed for handling large-scale databases with less memory usage. Moreover, the designed MapReduce framework can speed up the mining performance of closed high-utility patterns in the developed fusion system.     

Meta itemset: a new concise representation of frequent itemset

The sheer size of all frequent itemsets is one challenging problem in data mining research. Based on both closed itemset and maximal itemset, meta itemset which is a new concise representation of frequent itemset is proposed. It is proved that both closed itemset and maximal itemset are special cases of meta itemset. The set of all closed itemsets and the set of all maximal itemsets form the upper bound and the lower bound of the set of all meta itemsets. Then, property and pruning strategies of meta itemset are discussed. Finally, an efficient algorithm for mining meta itemset is proposed. Experimental results show that the proposed algorithm is effective and efficient.     

A fast updated algorithm to maintain the discovered high-utility itemsets for transaction modification

High-utility itemsets mining (HUIM) is a critical issue which concerns not only the occurrence frequencies of itemsets in association-rule mining (ARM), but also the factors of quantity and profit in real-life applications. Many algorithms have been developed to efficiently mine high-utility itemsets (HUIs) from a static database. Discovered HUIs may become invalid or new HUIs may arise when transactions are inserted, deleted or modified. Existing approaches are required to re-process the updated database and re-mine HUIs each time, as previously discovered HUIs are not maintained. Previously, a pre-large concept was proposed to efficiently maintain and update the discovered information in ARM, which cannot be directly applied into HUIM. In this paper, a maintenance (PRE-HUI-MOD) algorithm with transaction modification based on a new pre-large strategy is presented to efficiently maintain and update the discovered HUIs. When the transactions are consequentially modified from the original database, the discovered information is divided into three parts with nine cases. A specific procedure is then performed to maintain and update the discovered information for each case. Based on the designed PRE-HUI-MOD algorithm, it is unnecessary to rescan original database until the accumulative total utility of the modified transactions achieves the designed safety bound, which can greatly reduce the computations of multiple database scans when compared to the batch-mode approaches.     

基于索引数组和复合频繁模式树的频繁闭项集挖掘算法

频繁闭项集惟一确定频繁项集且规模小得多.CROP是一种基于复合频繁模式树的、频繁闭项集高效挖掘算法,但存在着候选结点过多的问题.这些非闭合结点的生成、检查和剪裁带来了大量不必要的操作.提出了一种改进的频繁闭项集挖掘算法CROP_Index.该算法用＂索引数组＂来组织数据,找到频繁共同出现的项集.基于二进制位图,给出了一个包含索引的计算方法,并利用索引启发信息合并,得到复合型频繁模式树的初始结点;同时给出一些新的性质,使得改进的算法只生成闭合结点,从而节省了大量不必要的操作,缩小了搜索空间.实验结果表明该算法效率较高.     

DiffNodesets: An efficient structure for fast mining frequent itemsets

Mining frequent itemsets is an essential problem in data mining and plays an important role in many data mining applications. In recent years, some itemset representations based on node sets have been proposed, which have shown to be very efficient for mining frequent itemsets. In this paper, we propose DiffNodeset, a novel and more efficient itemset representation, for mining frequent itemsets. Based on the DiffNodeset structure, we present an efficient algorithm, named dFIN, to mining frequent itemsets. To achieve high efficiency, dFIN finds frequent itemsets using a set-enumeration tree with a hybrid search strategy and directly enumerates frequent itemsets without candidate generation under some case. For evaluating the performance of dFIN, we have conduct extensive experiments to compare it against with existing leading algorithms on a variety of real and synthetic datasets. The experimental results show that dFIN is significantly faster than these leading algorithms.     

Maintaining the discovered high-utility itemsets with transaction modification

Most approaches for discovering frequent itemsets derive association rules from a binary database. Profit, cost, and quantity are not considered in traditional association-rule mining. Utility mining was proposed to measure the utilities of purchase products to derive highutility itemsets (HUIs). Many algorithms have been proposed to efficiently find HUIs from a static database. In real-world applications, transactions are inserted, deleted, or modified in dynamic situations. Existing batch approaches have to re-process the updated database since previously discovered HUIs are not maintained. In this paper, a Fast UPdated (FUP) strategy with utility measure and a maintenance algorithm, called FUP-HUI-MOD, are developed to efficiently maintain and update discovered HUIs. When transactions are modified, the proposed algorithm partitions the transactions before and after the modification into two parts, creating four cases. Each case is maintained using a specific procedure to update the discovered HUIs. Based on the designed FUP-HUI-MOD algorithm, the original database is not required to be rescanned each time compared to the state-of-the-art high-utility itemset mining algorithms in batch mode. Experiments are conducted to show that the proposed algorithm outperforms batch algorithms in maintaining HUIs.     

An efficient fast algorithm for discovering closed+ high utility itemsets

In recent years, high utility itemsets (HUIs) mining from the transactional databases becomes one of the most emerging research topic in the field of data mining due to its wide range of applications in online e-commerce data analysis, identifying interesting patterns in biomedical data and for cross marketing solutions in retail business. It aims to discover the itemsets with high utilities efficiently by considering item quantities in a transaction and profit values of each item. However, it produces a tremendous number of HUIs, which imposes further burden in analysis of the extracted patterns and also degrades the performance of mining methods. Mining the set of closed ⁺ high utility itemsets (CHUIs) solves this issue as it is a loss-less and condensed representation of all HUIs. In this paper, we aim to present a new algorithm for finding CHUIs from a transactional database, called the CHUM (Closed ⁺ High Utility itemset Miner), which is scalable and efficient. The proposed mining algorithm adopts a tricky aimed vertical representation of the database in order to speed up the execution time in generating itemset closures and compute their utility information without accessing the database. The proposed method makes use of the item co-occurrences strategy in order to further reduce the number of intersections needed to be performed. Several experiments are conducted on various sparse and dense datasets and the simulation results clearly show the scalability and superior performance of our algorithm as compared to those for the existing state-of-the-art CHUD (Closed ⁺ High Utility itemset Discovery) algorithm.     

MAXFP-M iner: 利用FP- tree 快速挖掘最大频繁项集

为提高频繁项集的挖掘效率，提出了最大频繁项集树的概念和基于FP-tree的最大频繁项集挖掘算法MAXFP-Miner，首先建立了FP-tree，在此基础上建立最大频繁项集树MAXFP-tree，MAXFP-tree中包含了所有最大频繁项集，缩小了搜索空间，提高了算法的效率，算法分析和实验表明，该算法特别适合于挖掘稠密型及具有长频繁项集的数据集。     

不确定数据频繁闭项集挖掘算法

由于不确定数据的向下封闭属性,挖掘全部频繁项集的方法会得到一个指数级的结果。为获得一个较小的合适的结果集,研究了在不确定数据上挖掘频繁闭项集,并提出了一种新的频繁闭项集挖掘算法——NA-PFCIM。该算法将项集挖掘过程看作一个概率分布函数,考虑到基于正态分布模型的方法提取的频繁项集精确度较高,而且支持大型数据库,采用了正态分布模型提取频繁项集。同时,为了减少搜索空间以及避免冗余计算,利用基于深度优先搜索的策略来获得所有的概率频繁闭项集。该算法还设计了两个剪枝策略:超集修剪和子集修剪。最后,在常用的数据集(T10I4D100K、Accidents、Mushroom、Chess)上,将提出的NA-PFCIM算法和基于泊松分布的A-PFCIM算法进行比较。实验结果表明,NA-PFCIM算法能够减少所要扩展的项集,同时减少项集频繁概率的计算,其性能优于对比算法。     

基于DiffNodeset结构的最大频繁项集挖掘算法

在数据挖掘中,通过挖掘最大频繁项集来代替挖掘频繁项集可以大大地提升系统的运行效率。针对现有的最大频繁项集挖掘算法的运行时间消耗仍然很大的问题,提出了一种基于DiffNodeset结构的最大频繁项集挖掘（DNMFIM）算法。首先,采用了一种新的数据结构DiffNodeset来实现求交集以及支持度的快速计算;其次,引入一种新的线性复杂度的连接方法来降低两个DiffNodeset在连接过程中的复杂度,避免了多次的无效计算;然后,将集合枚举树作为搜索空间,同时采用多种优化剪枝策略来缩小搜索空间;最后,再结合最大频繁项集挖掘算法（MAFIA）中所使用的超集检测技术来有效地提高算法的准确性。实验结果表明,DNMFIM算法在时间效率方面性能优于MAFIA与基于N-list的MAFIA（NB-MAFIA）,该算法在不同类型数据集中进行最大频繁项集挖掘时均有良好的效果。     

基于二进制的频繁项集挖掘新算法

频繁项集挖掘是数据挖掘中的一个经典的问题。然而,大部分算法需要扫描数据库多次,算法效率比较低。该文提出了一个效率比较好的挖掘频繁项集的新算法,在这个算法中,所有的事务都是以二进制的形式表示,所以挖掘极大频繁项集的任务就变成了从二进制集中发现频繁模式。而且,这种算法只需要扫描原始数据库一次。最后,利用试验来证明这种算法的效率和优势。     

一种改进的频繁闭项集挖掘算法

频繁闭项集惟一确定频繁项集且规模小得多,但挖掘频繁闭项集仍是很费时的.为提高挖掘效率,提出了一种改进的频繁闭项集挖掘算法DCI-Closed-Index.该算法用"索引数组"来组织数据,通过为每个项目增加包含索引,找到频繁共同出现的项集.利用二进制位图技术,给出了一个求包含索引的快速算法.然后根据项目在包含索引中出现的频率由高到低进行排序,并利用包含索引作为启发信息,合并同时出现且支持度相等的频繁项,得到初始生成子,从而大大缩小了搜索空间.同时利用索引数组对每一个生成子的前序集和后序集进行约简,得到新的、较小的约简前序集和约简后序集.并证明了约简前序集和后序集与原来的前序集和后序集的功能是一样的.从而减少了候选生成子的集合包含判断的操作.实验结果表明,该算法的性能优于其他主流算法.     

基于B-list的最大频繁项集挖掘算法

针对现有的最大频繁项集挖掘算法挖掘时间过长、内存消耗较大的问题,提出了一种基于构造链表B-list的最大频繁项集挖掘算法BMFI,该算法利用B-list数据结构来挖掘频繁项集并采用全序搜索树作为搜索空间,然后采用父等价剪枝技术来缩小搜索空间,最后再结合基于MFI-tree的投影策略实现超集检测来提高算法的效率。实验结果表明,BMFI算法在时间效率与空间效率方面均优于FPMAX算法与MFIN算法。该算法在稠密数据集与稀疏数据集中进行最大频繁项集挖掘时均有良好的效果。     

A fast high average-utility itemset mining with efficient tighter upper bounds and novel list structure

High-utility itemset mining is a prominent data-mining technique where the profit or weight of itemsets plays a crucial role in defining meaningful patterns. High average-utility itemset (HAUI) mining is an advancement over high-utility itemset mining, which introduces an unbiased measure called average utility to associate the utility of itemsets with their length. Several existing HAUI mining algorithms use various upper bounds such as average-utility upper bound, revised tighter upper bound, and looser upper bound to preserve pruning methods. However, these upper bounds overestimate the average-utility of itemsets and slow down the mining process. This paper presents a fast high average-utility itemset miner (FHAIM) algorithm, which uses two improved upper bounds and several efficient pruning strategies to avoid the processing of unpromising candidate itemsets. Moreover, a novel list structure named recommended average-utility list (RAUL) is presented to store the average-utility and the required information for pruning. The RAUL for an itemset can be constructed by joining the RAULs of its subsets to avoid excessive database scans. We have performed substantial experiments on various benchmark datasets to evaluate the performance of the FHAIM in comparison with two existing HAUI mining algorithms. Experimental results show that FHAIM outperforms the existing HAUI mining algorithms in terms of runtime, memory usage, join counts, and scalability.

     

基于模式增长方式的高效用模式挖掘算法

高效用模式挖掘是数据挖掘领域的一个重要研究内容; 由于其计算过程包含对模式的内、外效用值的处理, 计算复杂度较大, 因此挖掘算法的主要研究热点问题就是提高算法的时间效率.针对此问题, 本文给出一个基于模式增长方式的高效用模式挖掘算法HUPM-FP, 该算法可以从全局树上挖掘高效用模式, 避免产生候选项集.实验中, 采用6个典型数据集进行实验, 并和目前效率较好的算法FHM (Faster high-utility itemset mining)做了对比, 实验结果表明本文给出的算法时空效率都有较大的提高, 特别是时间效率提高较大, 可以达到1个数量级以上.     

最大频繁项目集的快速更新

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题．为克服基于Apriori的最大频繁项目集挖掘算法存在的不足,DMFIA采用FP-tree存储结构及自顶向下的搜索策略,有效地提高了最大频繁项目集的挖掘效率．但对于频繁项目多而最大频繁项目集维数相对较小的情况,DMFIA要经过多层搜索且在每一层产生大量的候选项目集,因而影响算法的执行效率．为此,该文提出了DMFIA的改进算法IDMFIA(the Improved algorithm of DMFIA)．IDMFIA采用自顶向下和自底向上双向搜索策略,可尽早修剪掉较短最大频繁项目集的超集和较长最大频繁项目集的子集．另外,该文还提出最大频繁项目集更新算法FUMFIA(Fast Updating Maximum Frequent Itemsets Algorithm),该算法充分利用已建立的FP-tree和已挖掘的最大频繁项目集,可对已挖掘的最大频繁项目集进行高效维护．实验结果表明,IDMFIA和FUMFIA可有效提高最大频繁项目集的挖掘和更新效率．     

CFP-tree: A compact disk-based structure for storing and querying frequent itemsets

Frequent itemset mining is an important problem in the data mining area with a wide range of applications. Many decision support systems need to support online interactive frequent itemset mining, which is a challenging task because frequent itemset mining is a computation intensive repetitive process. One solution is to precompute frequent itemsets. In this paper, we propose a compact disk-based data structure—CFP-tree to store precomputed frequent itemsets on a disk to support online mining requests. The CFP-tree structure effectively utilizes the redundancy in frequent itemsets to save space. The compressing ratio of a CFP-tree can be as high as several thousands or even higher. Efficient algorithms for retrieving frequent itemsets from a CFP-tree, as well as efficient algorithms to construct and maintain a CFP-tree, are developed. Our performance study demonstrates that with a CFP-tree, frequent itemset mining requests can be responded to promptly.     

基于二进制的频繁项集挖掘新算法

频繁项集挖掘是数据挖掘中的一个经典的问题。然而,大部分算法需要扫描数据库多次,算法效率比较低。该文提出了一个效率比较好的挖掘频繁项集的新算法,在这个算法中,所有的事务都是以二进制的形式表示,所以挖掘极大频繁项集的任务就变成了从二进制集中发现频繁模式。而且,这种算法只需要扫描原始数据库一次。最后,利用试验来证明这种算法的效率和优势。     

EFIM: a fast and memory efficient algorithm for high-utility itemset mining

In recent years, high-utility itemset mining has emerged as an important data mining task. However, it remains computationally expensive both in terms of runtime and memory consumption. It is thus an important challenge to design more efficient algorithms for this task. In this paper, we address this issue by proposing a novel algorithm named EFIM (EFficient high-utility Itemset Mining), which introduces several new ideas to more efficiently discover high-utility itemsets. EFIM relies on two new upper bounds named revised sub-tree utility and local utility to more effectively prune the search space. It also introduces a novel array-based utility counting technique named Fast Utility Counting to calculate these upper bounds in linear time and space. Moreover, to reduce the cost of database scans, EFIM proposes efficient database projection and transaction merging techniques named High-utility Database Projection and High-utility Transaction Merging (HTM), also performed in linear time. An extensive experimental study on various datasets shows that EFIM is in general two to three orders of magnitude faster than the state-of-art algorithms \(\hbox {d}^2\)HUP, HUI-Miner, HUP-Miner, FHM and UP-Growth+ on dense datasets and performs quite well on sparse datasets. Moreover, a key advantage of EFIM is its low memory consumption.