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.     

Efficient updating of discovered high-utility itemsets for transaction deletion in dynamic databases

Most algorithms related to association rule mining are designed to discover frequent itemsets from a binary database. Other factors such as profit, cost, or quantity are not concerned in binary databases. Utility mining was thus proposed to measure the utility values of purchased items for finding high-utility itemsets from a static database. In real-world applications, transactions are changed whether insertion or deletion in a dynamic database. An existing maintenance approach for handling high-utility itemsets in dynamic databases with transaction deletion must rescan the database when necessary. In this paper, an efficient algorithm, called PRE-HUI-DEL, for updating high-utility itemsets based on the pre-large concept for transaction deletion is proposed. The pre-large concept is used to partition transaction-weighted utilization itemsets into three sets with nine cases according to whether they have large (high), pre-large, or small transaction-weighted utilization in the original database and in the deleted transactions. Specific procedures are then applied to each case for maintaining and updating the discovered high-utility itemsets. Experimental results show that the proposed PRE-HUI-DEL algorithm outperforms a batch two-phase algorithm and a FUP2-based algorithm in maintaining high-utility itemsets.     

Updating high-utility pattern trees with transaction modification

Traditional association-rule mining only concerns the occurrence frequencies of the items in a binary database. In real-world applications, customers may buy several copies of the purchased items. Other factors such as profit, quantity, or price should be concerned to measure the utilities of the purchased items. High-utility itemsets mining was thus proposed to consider the factors of quantity and profit. Two-phase model was the most commonly way to keep the transaction-weighted utilization downward closure property, thus reducing the numerous candidates in utility mining. Most methods for finding high-utility itemsets are used to handle a static database. In practical applications, transactions are changed whether insertion, deletion, or modification. Some itemsets may arise as the new high-utility itemsets or become invalid knowledge in the updated database. In this paper, a maintenance Fast Updated High Utility Pattern tree for transaction MODification (FUP-HUP-tree-MOD) algorithm is thus proposed to effective maintain and update the built HUP tree for mining high-utility itemsets in dynamic databases without candidate generation. Experiments are conducted to show better performance of the proposed algorithm compared to the two-phase algorithm and the HUP tree algorithm in batch mode.     

Maintaining discovered frequent itemsets: Cases for changeable database and support

Mining frequent itemsets from large databases has played an essential role in many data mining tasks. It is also important to maintain the discovered frequent itemsets for these data mining tasks when the database is updated. All algorithms proposed so far for the maintenance of discovered frequent itemsets are only performed with a fixed minimum support,which is the same as that used to obtain the discovered frequent itemsets. That is, users cannot change the minimum support even if the new results are unsatisfactory to the users. In this paper two new complementary algorithms, FMP (First Maintaining Process) and RMP (Repeated Maintaining Process), are proposed to maintain discovered frequent itemsets in the case that new transaction data are added to a transaction database. Both algorithms allow users to change the minimum support for the maintenance processes. FMP is used for the first maintaining process, and when the result derived from the FMP is unsatisfactory, RMP will be performed repeatedly until satisfactory results are obtained. The proposed algorithms re-use the previous results to cut down the cost of maintenance. Extensive experiments have been conducted to assess the performance of the algorithms. The experimental results show that the proposed algorithms are very resultful compared with the previous mining and maintenance algorithms for maintenance of discovered frequent itemsets.     

OHUQI: Mining on-shelf high-utility quantitative itemsets

Mobile edge computing has brought fresh opportunities and challenges to data science. Utility-driven mining, a recently emerging branch of utility-based data science, has been widely applied because it considers both the utility factor and the quantity characteristic with ranges of patterns. However, most existing utility-mining algorithms assume that patterns always appear regardless of the period. For instance, some products may sell well at certain times of the year. Considering the rich information in the database, such as quantity and time, we propose an effective and efficient approach, namely OHUQI, for discovering on-shelf high-utility quantitative itemsets. To avoid scanning the database multiple times, we adopt a data structure to maintain some necessary information, and thus OHUQI only accesses the database twice. Several pruning strategies are also designed to prune a large number of unpromising itemsets in advance to shrink the search space. Finally, the subsequent experimental results show that OHUQI performs well on several real-world datasets.

     

A transaction mapping algorithm for frequent itemsets mining

In this paper, we present a novel algorithm for mining complete frequent itemsets. This algorithm is referred to as the TM (transaction mapping) algorithm from hereon. In this algorithm, transaction ids of each itemset are mapped and compressed to continuous transaction intervals in a different space and the counting of itemsets is performed by intersecting these interval lists in a depth-first order along the lexicographic tree. When the compression coefficient becomes smaller than the average number of comparisons for intervals intersection at a certain level, the algorithm switches to transaction id intersection. We have evaluated the algorithm against two popular frequent itemset mining algorithms, FP-growth and dEclat, using a variety of data sets with short and long frequent patterns. Experimental data show that the TM algorithm outperforms these two algorithms.     

Fast and memory efficient mining of high-utility itemsets from data streams: with and without negative item profits

Mining utility itemsets from data steams is one of the most interesting research issues in data mining and knowledge discovery. In this paper, two efficient sliding window-based algorithms, MHUI-BIT (Mining High-Utility Itemsets based on BITvector) and MHUI-TID (Mining High-Utility Itemsets based on TIDlist), are proposed for mining high-utility itemsets from data streams. Based on the sliding window-based framework of the proposed approaches, two effective representations of item information, Bitvector and TIDlist, and a lexicographical tree-based summary data structure, LexTree-2HTU, are developed to improve the efficiency of discovering high-utility itemsets with positive profits from data streams. Experimental results show that the proposed algorithms outperform than the existing approaches for discovering high-utility itemsets from data streams over sliding windows. Beside, we also propose the adapted approaches of algorithms MHUI-BIT and MHUI-TID in order to handle the case when we are interested in mining utility itemsets with negative item profits. Experiments show that the variants of algorithms MHUI-BIT and MHUI-TID are efficient approaches for mining high-utility itemsets with negative item profits over stream transaction-sensitive sliding windows.     

Maintaining frequent closed itemsets over a sliding window

In this paper, we study the incremental update of Frequent Closed Itemsets (FCIs) over a sliding window in a high-speed data stream. We propose the notion of semi-FCIs, which is to progressively increase the minimum support threshold for an itemset as it is retained longer in the window, thereby drastically reducing the number of itemsets that need to be maintained and processed. We explore the properties of semi-FCIs and observe that a majority of the subsets of a semi-FCI are not semi-FCIs and need not be updated. This finding allows us to devise an efficient algorithm, IncMine, that incrementally updates the set of semi-FCIs over a sliding window. We also develop an inverted index to facilitate the update process. Our empirical results show that IncMine achieves significantly higher throughput and consumes less memory than the state-of-the-art streaming algorithms for mining FCIs and FIs. IncMine also attains high accuracy of 100% precision and over 93% recall.     

数据流中基于事务链表组的频繁闭项集挖掘

挖掘频繁项集是挖掘数据流的基本任务.许多近似算法能够对数据流进行频繁项集的挖掘,但不能有效控制内存资源消耗和挖掘运行时间.为了提高数据流挖掘的效率,通过挖掘数据流中的频繁闭项集来减少挖掘结果项集的数量,并借鉴Relim算法和Manku算法,引入事务链表组作为概要数据结构,提出了一种新的数据流频繁闭项集的挖掘算法.最后通过实验,证明了该算法的有效性.     

减少候选项集的数据流高效用项集挖掘算法

大数据环境下高效用项集挖掘算法中过多的候选项集极大地降低了算法的时空效率,提出了一种减少候选项集的数据流高效用项集挖掘算法。首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入口与节点的冗余效用值;然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;最终,从候选模式中选出高效用模式。基于真实数据流的实验结果表明,本算法的时空效率与内存占用比均优于其他数据流的高效用模式挖掘算法。     

隐私保护的跨多表频繁项集挖掘

给出将跨两表频繁项集挖掘方法扩展到跨三表频繁项集挖掘方法的技术,以三表频繁项集的公共属性记数集作为三方安全协议的参数,设计一个跨三表频繁项集挖掘的隐私保护算法,以便在挖掘求出跨三表频繁项集的同时保护三表中的隐私信息。理论分析和实验结果表明,算法安全、高效,具有可扩展性。     

挖掘滑动时间衰减窗口中网络流频繁项集*

网络流数据频繁项集挖掘是网络流量分析的重要基础。提出一种新颖的基于字典顺序前缀树LOP-Tree的频繁项集挖掘算法STFWFI,该算法采用更符合网络流特点的滑动时间衰减窗口模型,有效降低挖掘频繁项集的时间和空间复杂度;在该树结构上提出一种新的基于统计分布的节点权值计算方法SDNW代替传统的统计计算方法,提高了网络流节点估值的精确度。实验结果表明该算法在网络流频繁项集挖掘过程中获得了良好的效果。     

Quadratic programming with transaction costs

We consider the problem of maximizing the mean-variance utility function of n$n$ assets. Associated with a change in an asset's holdings from its current or target value is a transaction cost. These must be accounted for in practical problems. A straightforward way of doing so results in a 3n$3n$-dimensional optimization problem with 3n$3n$ additional constraints. This higher dimensional problem is computationally expensive to solve. We present an algorithm for solving the 3n$3n$-dimensional problem by modifying an active set quadratic programming (QP) algorithm to solve the 3n$3n$-dimensional problem as an n$n$-dimensional problem accounting for the transaction costs implicitly rather than explicitly. The method is based on deriving the optimality conditions for the higher dimensional problem solely in terms of lower dimensional quantities and requires substantially less computational effort than any active set QP algorithm applied directly on a 3n$3n$-dimensional problem.     

Tough型约束下的频繁闭项集挖掘

回顾了常见的关联规则算法,关注频繁闭项集这一非常有发展前途的方法.在综合Tough型约束与频繁闭项集的基础上,提出了关联规则的一种新算法--基于Tough型约束的频繁闭项集挖掘算法（TC-based FCIM Algorithm）,分析了算法中选择过程和过滤过程这两个重要过程的先后顺序.     

Top-k high average-utility itemsets mining with effective pruning strategies

High average-utility itemset (HAUI) mining has recently received interest in the data mining field due to its balanced utility measurement, which considers not only profits and quantities of items but also the lengths of itemsets. Although several algorithms have been designed for the task of HAUI mining in recent years, it is hard for users to determine an appropriate minimum average-utility threshold for the algorithms to work efficiently and control the mining result precisely. In this paper, we address this issue by introducing a framework of top-k HAUI mining, where \(k\) is the desired number of high average-utility itemsets to be mined instead of setting a minimum average-utility threshold. An efficient list based algorithm named TKAU is proposed to mine the top-k high average-utility itemsets in a single phase. TKAU introduces two novel strategies, named EMUP and EA to avoid performing costly join operations for calculating the utilities of itemsets. Moreover, three strategies named RIU, CAD, and EPBF are also incorporated to raise its internal minimal average-utility threshold effectively, and thus reduce the search space. Extensive experiments on both real and synthetic datasets show that the proposed algorithm has excellent performance and scalability.     

项约束频繁项集挖掘的新方法

项约束频繁项集挖掘是项约束关联规则挖掘的关键步骤。对项约束频繁项集挖掘的内涵进行讨论,认为一个项集X本身满足项约束条件B是不够的,数据库中支持X的全部事务均满足B才能称“项集X满足条件B”。据此,将Direct算法改进为Direct*,在Direct*中负项被作为一个独立的项来看待。项约束是简洁性约束,但目前已有的算法没有充分利用其简洁性,提出利用项约束简洁性的MSEB算法。实验表明：对稠密数据库,MSEB的效率较高,并且Direct*和MSEB两个算法均是正确的。     

Mining erasable itemsets with subset and superset itemset constraints

Erasable itemset (EI) mining, a branch of pattern mining, helps managers to establish new plans for the development of new products. Although the problem of mining EIs was first proposed in 2009, many efficient algorithms for mining these have since been developed. However, these algorithms usually require a lot of time and memory usage. In reality, users only need a small number of EIs which satisfy a particular condition. Having this observation in mind, in this study we develop an efficient algorithm for mining EIs with subset and superset itemset constraints (C₀ ⊆ X ⊆ C₁). Firstly, based on the MEI (Mining Erasable Itemsets) algorithm, we present the MEIC (Mining Erasable Itemsets with subset and superset itemset Constraints) algorithm in which each EI is checked with regard to the constraints before being added to the results. Next, two propositions supporting quick pruning of nodes that do not satisfy the constraints are established. Based on these, we propose an efficient algorithm for mining EIs with subset and superset itemset constraints (called pMEIC – p: pruning). The experimental results show that pMEIC outperforms MEIC in terms of mining time and memory usage.     

用有序FP-tree挖掘最大频繁项集

提出了完全前缀路径和有序FP-tree的概念,给出根据数据项所在的层建立有序FP-tree的方法,利用有序FP-tree表示数据.提出用有序FP-tree中的完全前缀路径进行最大频繁项集挖掘的算法——MFIM算法,该算法利用有序FP-tree中的完全前缀路径对挖掘算法进行优化.实验结果表明,该算法对于浓密数据集中挖掘长模式具有较好的性能.