Novel techniques and an efficient algorithm for closed pattern mining

In this paper we show that frequent closed itemset mining and biclustering, the two most prominent application fields in pattern discovery, can be reduced to the same problem when dealing with binary (0–1) data. FCPMiner, a new powerful pattern mining method, is then introduced to mine such data efficiently. The uniqueness of the proposed method is its extendibility to non-binary data. The mining method is coupled with a novel visualization technique and a pattern aggregation method to detect the most meaningful, non-overlapping patterns. The proposed methods are rigorously tested on both synthetic and real data sets.     

有效的不确定数据概率频繁项集挖掘算法

针对已有概率频繁项集挖掘算法采用模式增长的方式构建树时产生大量树节点,导致内存空间占用较大以及发现概率频繁项集效率低等问题,提出了改进的不确定数据频繁模式增长(PUFP-Growth)算法。该算法通过逐条读取不确定事务数据库中数据,构造类似频繁模式树(FP-Tree)的紧凑树结构,同时更新项头表中保存所有尾节点相同项集的期望值的动态数组。当所有事务数据插入到改进的不确定数据频繁模式树(PUFP-Tree)中以后,通过遍历数组得到所有的概率频繁项集。最后通过实验结果和理论分析表明:PUFP-Growth算法可以有效地发现概率频繁项集;与不确定数据频繁模式增长(UF-Growth)算法和压缩的不确定频繁模式挖掘(CUFP-Mine)算法相比,提出的PUFP-Growth算法能够提高不确定数据概率频繁项集挖掘的效率,并且减少了内存空间的使用。     

基于概率衰减窗口模型的不确定数据流频繁模式挖掘

考虑到不确定数据流的不确定性,设计了一种新的概率频繁模式树PFP-tree和基于该树的概率频繁模式挖掘方法PFP-growth.PFP-growth使用事务性不确定数据流及概率衰减窗口模型,通过计算各概率数据项的期望支持度以发现概率频繁模式,其主要特点有:考虑到窗口内不同时间到达数据项的贡献度不同,采用概率衰减窗口模型计算期望支持度,以提高模式挖掘准确度;设置数据项索引表和事务索引表,以加快频繁模式树检索速度;通过剪枝删除不可能成为频繁模式的结点,以降低模式树的存储及检索开销;对每个结点都设立一个事务概率信息链表,以支持数据项在不同事务中具有不同概率的情形.实验结果表明,PFP-growth在保证挖掘模式准确度的前提下,在处理时间和内存空间等方面都具有较好的性能.     

An incremental mining algorithm for high utility itemsets

Association-rule mining, which is based on frequency values of items, is the most common topic in data mining. In real-world applications, customers may, however, buy many copies of products and each product may have different factors, such as profits and prices. Only mining frequent itemsets in binary databases is thus not suitable for some applications. Utility mining is thus presented to consider additional measures, such as profits or costs according to user preference. In the past, a two-phase mining algorithm was designed for fast discovering high utility itemsets from databases. When data come intermittently, the approach needs to process all the transactions in a batch way. In this paper, an incremental mining algorithm for efficiently mining high utility itemsets is proposed to handle the above situation. It is based on the concept of the fast-update (FUP) approach, which was originally designed for association mining. The proposed approach first partitions itemsets into four parts according to whether they are high transaction-weighted utilization itemsets in the original database and in the newly inserted transactions. Each part is then executed by its own procedure. Experimental results also show that the proposed algorithm executes faster than the two-phase batch mining algorithm in the intermittent data environment     

数据流频繁模式挖掘综述

一些先进应用如欺诈检测和趋势学习等带来了数据流频繁模式挖掘的发展。不同于静态数据,数据流挖掘面临着时空约束和项集组合爆炸等问题。对已有数据流频繁模式挖掘算法进行综述并对经典和最新算法进行分析。按照模式集合的完整程度进行分类,数据流中频繁模式分为全集模式和压缩模式。压缩模式主要包括闭合模式、最大模式、top-k模式以及三者的组合模式。不同之处是闭合模式是无损压缩的,而其他模式是有损压缩的。为了得到有趣的频繁模式,可以挖掘基于用户约束的模式。为了处理数据流中的新近事务,将算法分为基于窗口模型和基于衰减模型的方法。数据流中模式挖掘常见的还包含序列模式和高效用模式,对经典和最新算法进行介绍。最后给出了数据流模式挖掘的下一步工作。     

高效挖掘无序频繁子树

频繁模式挖掘是数据挖掘领域的中一个重要问题，其研究范围包括事务，序列，树和图．频繁子树挖掘广泛应用于生物信息学，web挖掘，化合物结构分析和挖掘等领域．本文提出用模式增长方法在由无序树构成的森林中挖掘直接频繁子树．算法利用规范化方法将元序树化为为唯一的表示形式，利用最右路径扩展方法构造完整的模式增长空间，然后根据待增长模式的拓扑结构确定其增长点并构造相应投影库，从而将挖掘频繁子树模式问题转化为在各投影库中寻找频繁节点问题．通过与HybridTreeMiner算法的实验比较，表明其具有更高的效率。     

基于多尺度的时序数据部分周期模式增量挖掘

针对动态时序数据部分周期模式挖掘过程存在的计算复杂度过高和扩展性差等问题,提出了一种结合多尺度理论的时间序列部分周期模式挖掘算法（MSI-PPPGrowth）,所提算法充分利用了时序数据客观存在的时间多尺度特性,将多尺度理论引入时序数据的部分周期模式挖掘过程。首先,将尺度划分后的原始数据以及增量时序数据作为更细粒度的基准尺度数据集进行独立挖掘;然后,利用不同尺度数据间的相关性实现尺度转换,以间接获取动态更新后的数据集对应的全局频繁模式,从而避免了原始数据集的重复扫描和树结构的不断调整。其中,基于克里金法并考虑时序周期性设计了一个新的频繁缺失计数估计模型（PJK-EstimateCount）,以有效估计在尺度转换过程中的缺失项支持度计数。实验结果表明,MSI-PPPGrowth具有良好的可扩展性和实时性,尤其是对于稠密数据集,其性能优势更为突出。     

Efficient representative pattern mining based on weight and maximality conditions

As a core area in data mining, frequent pattern (or itemset) mining has been studied for a long time. Weighted frequent pattern mining prunes unimportant patterns and maximal frequent pattern mining discovers compact frequent patterns. These approaches contribute to improving mining performance by reducing the search space. However, we need to consider both the downward closure property and patterns' subset checking process when integrating these different methods in order to prevent unintended pattern losses. Moreover, it is also essential to extract valid patterns with faster runtime and less memory consumption. For this reason, in this paper, we propose more efficient maximal weighted frequent pattern (MWFP) mining approaches based on tree and array structures. We describe how to handle these problems more efficiently, maintaining the correctness of our method. We develop two types of maximal weighted frequent mining algorithms based on weight ascending order and support descending order and compare these two algorithms to conclude which is more suitable for MWFP mining. In addition, comprehensive tests in this paper show that our algorithms are more efficient and scalable than state‐of‐the‐art algorithms, and they also have the correctness of the MWFP mining in terms of their pattern generation results.     

基于FIUT结构增量式频繁项集挖掘

增量式频繁项集挖掘是当前研究的热点,基于FP-Growth的Pre-FUFP算法有效处理了频繁模式的更新,但需递归遍历FP-tree,导致效率较低。提出Pre-FIUT算法,引入频繁超度量树结构,提高了获得频繁项集挖掘效率;基于FIUT的Pre-FIUT可通过查看频繁超度量树叶子结点的支持度确定频繁项集,并与次频繁项集概念相结合进行增量式频繁项集挖掘。实验表明,Pre-FIUT算法能快速扫描和更新数据,合理利用内存,精确获得频繁项集。     

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

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

Sliding window based weighted maximal frequent pattern mining over data streams

As data have been accumulated more quickly in recent years, corresponding databases have also become huger, and thus, general frequent pattern mining methods have been faced with limitations that do not appropriately respond to the massive data. To overcome this problem, data mining researchers have studied methods which can conduct more efficient and immediate mining tasks by scanning databases only once. Thereafter, the sliding window model, which can perform mining operations focusing on recently accumulated parts over data streams, was proposed, and a variety of mining approaches related to this have been suggested. However, it is hard to mine all of the frequent patterns in the data stream environment since generated patterns are remarkably increased as data streams are continuously extended. Thus, methods for efficiently compressing generated patterns are needed in order to solve that problem. In addition, since not only support conditions but also weight constraints expressing items’ importance are one of the important factors in the pattern mining, we need to consider them in mining process. Motivated by these issues, we propose a novel algorithm, weighted maximal frequent pattern mining over data streams based on sliding window model (WMFP-SW) to obtain weighted maximal frequent patterns reflecting recent information over data streams. Performance experiments report that MWFP-SW outperforms previous algorithms in terms of runtime, memory usage, and scalability.     

一种直接在Trans-树中挖掘频繁模式的新算法

Frequent pattern mining plays an essential role in many important data mining tasks. FP-growth is a very efficient algorithm for frequent pattern mining. However, it still suffers from creating conditional FP-tree separately and recursively during the mining process. In this paper, we propose a new algorithm, called Least-Item-First Pat-tern Growth (LIFPG), for mining frequent patterns. LIFPG mines frequent patterns directly in Trans-tree withoutusing any additional data structures. The key idea is that least items are always considered first when the current pat-tern growth. By this way, conditional sub-tree can be created directly in Trans-tree by adjusting node-links and re-counting counts of some nodes. Experiments show that, in comparison with FP-Growth, our algorithm is about fourtimes faster and saves half of memory;it also has good time and space scalability with the number of transactions,and has an excellent performance in dense dataset mining as well.     

A new algorithm for fast mining frequent itemsets using N-lists

Mining frequent itemsets has emerged as a fundamental problem in data mining and plays an essential role in many important data mining tasks.In this paper,we propose a novel vertical data representation called N-list,which originates from an FP-tree-like coding prefix tree called PPC-tree that stores crucial information about frequent itemsets.Based on the N-list data structure,we develop an efficient mining algorithm,PrePost,for mining all frequent itemsets.Efficiency of PrePost is achieved by the following three reasons.First,N-list is compact since transactions with common prefixes share the same nodes of the PPC-tree.Second,the counting of itemsets’ supports is transformed into the intersection of N-lists and the complexity of intersecting two N-lists can be reduced to O(m + n) by an efficient strategy,where m and n are the cardinalities of the two N-lists respectively.Third,PrePost can directly find frequent itemsets without generating candidate itemsets in some cases by making use of the single path property of N-list.We have experimentally evaluated PrePost against four state-of-the-art algorithms for mining frequent itemsets on a variety of real and synthetic datasets.The experimental results show that the PrePost algorithm is the fastest in most cases.Even though the algorithm consumes more memory when the datasets are sparse,it is still the fastest one.     

On-shelf utility mining with negative item values

On-shelf utility mining has recently received interest in the data mining field due to its practical considerations. On-shelf utility mining considers not only profits and quantities of items in transactions but also their on-shelf time periods in stores. Profit values of items in traditional on-shelf utility mining are considered as being positive. However, in real-world applications, items may be associated with negative profit values. This paper proposes an efficient three-scan mining approach to efficiently find high on-shelf utility itemsets with negative profit values from temporal databases. In particular, an effective itemset generation method is developed to avoid generating a large number of redundant candidates and to effectively reduce the number of data scans in mining. Experimental results for several synthetic and real datasets show that the proposed approach has good performance in pruning effectiveness and execution efficiency.     

A new mining approach for uncertain databases using CUFP trees

In the past, many algorithms have been proposed to mine frequent itemsets from transactional databases, in which the presence or absence of items in transactions was certainly known. In some applications, items may also be uncertain in transactions with their existential probabilities ranging from 0 to 1 in the uncertain dataset. Apparently, the processing in uncertain datasets is quite different from those in certain datasets. The UF-tree algorithm was proposed to construct the UF-tree structure from an uncertain dataset and mine frequent itemsets from the tree. In the UF-tree construction process, however, only the same items with the same existential probabilities in transactions were merged together in the tree, thus causing many redundant nodes in the tree. In this paper, a new tree structure called the compressed uncertain frequent-pattern tree (CUFP tree) is designed to efficiently keep the related information in the mining process. In the CUFP tree, the same items will be merged in a branch of the tree even when the existential probabilities in transactions are not the same. A mining algorithm called the CUFP-mine algorithm is then proposed based on the tree structure to find uncertain frequent patterns. Experimental results show that the proposed approach has a better performance than UF-tree algorithm both in the execution time and in the number of tree nodes.     

一种改进的增量挖掘算法

Pre-FUFP算法基于次频繁项的概念有效处理了频繁模式树的更新,但当有次频繁项变成频繁项时,需要判定原数据库中哪些事务包含该数据项。为此,通过引入次频繁项对应原事务标识符的索引确定需要处理原数据库的事务,减少这一过程所消耗的时间,并用基于压缩FP-tree和矩阵技术代替原始FP-growth挖掘出频繁模式。实验证明该算法在时间效率上较Pre-FUFP有大幅度提高。     

基于多尺度空间划分与路网建模的城市移动轨迹模式挖掘

针对城市移动轨迹模式挖掘问题展开研究, 提出移动全局模式与移动过程模式相结合的挖掘方法, 即通过移动轨迹的起始位置点--终点位置点 (Origin-destination, OD点) 与移动过程序列分别进行移动全局模式与过程模式的发现. 在移动全局模式发现中, 提出了弹性多尺度空间划分方法, 避免了硬性等尺度网格划分对密集区域边缘的破坏, 同时增强了密集区域与稀疏区域的区分能力.在移动过程模式发现中, 提出了基于移动轨迹的路网拓扑关系模型构建方法, 通过路网关键位置点的探测抽取拓扑关系模型.最后基于空间划分集合与路网拓扑模型对原始 移动轨迹数据进行序列数据转换与频繁模式挖掘. 通过深圳市出租车历史 GPS 轨迹数据的实验结果表明, 该方法与现有方法相比在区域划分、数据转换等方面具有更好的性能, 同时挖掘结果语义更为丰富, 可解释性更强.     

动态数据库中增量Top-k高效用模式挖掘算法

高效用模式的挖掘需要设定一个合适的阈值,而阈值设定对用户来说并非易事,阈值过小导致产生大量低效用模式,阈值过大可能导致无高效用模式生成。因而Top-k高效用模式挖掘方法被提出,k指效用值前k大的模式。并且大量的高效用挖掘研究仅针对静态数据库,但在实际应用中常常会遇到新事务的加入的情况。针对以上问题,提出了增量的Top-k高效用挖掘算法TOPK-HUP-INS。算法通过四个有效的策略,在增量数据的情况下,有效地挖掘用户所需数量的高效用模式。通过在不同数据集上的对比实验表明TOPK-HUP-INS算法在时空性能上表现优异。     

基于FP-Tree的最大频繁项目集挖掘及更新算法

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,之前的很多研究都是采用Apriori类的候选项目集生成-检验方法.然而,候选项目集产生的代价是很高的,尤其是在存在大量强模式和/或长模式的时候.提出了一种快速的基于频繁模式树(FP-tree)的最大频繁项目集挖掘DMFIA(discover maximum frequent itemsets algorithm)及其更新算法UMFIA(update maximum frequent itemsets algorithm).算法UMFIA将充分利用以前的挖掘结果来减少在更新的数据库中发现新的最大频繁项目集的费用.     

改进的多数据流协同频繁项集挖掘算法

针对已有的多数据流协同频繁项集挖掘算法存在内存占用率高以及发现频繁项集效率低的问题,提出了改进的多数据流协同频繁项集挖掘（MCMD-Stream）算法。首先,该算法利用单遍扫描数据库的字节序列滑动窗口挖掘算法发现数据流中的潜在频繁项集和频繁项集;其次,构建类似频繁模式树（FP-Tree）的压缩频繁模式树（CP-Tree）存储已发现的潜在频繁项集和频繁项集,同时更新CP-Tree树中每个节点生成的对数倾斜时间表中的频繁项计数;最后,通过汇总分析得出在多条数据流中多次出现的且有价值的频繁项集,即协同频繁项集。相比A-Stream和H-Stream算法,MCMD-Stream算法不仅能够提高多数据流中协同频繁项集挖掘的效率,并且还降低了内存空间的使用率。实验结果表明MCMD-Stream算法能够有效地应用于多数据流的协同频繁项集挖掘。