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.     

数据流频繁模式挖掘综述

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

Towards a variable size sliding window model for frequent itemset mining over data streams

Sliding window is a widely used model for data stream mining due to its emphasis on recent data and its bounded memory requirement. The main idea behind a transactional sliding window is to keep a fixed size window over a data stream. The window size is kept constant by removing old transactions from the window, when new transactions arrive. Older transactions of window are removed irrespective to whether a significant change has occurred or not. Another challenge of sliding window model is determining window size. The classic approach for determining the window size is to obtain it from the user. In order to determine the precise size of the window, the user must have prior knowledge about the time and scale of changes within the data stream. However, due to the unpredictable changing nature of data streams, this prior knowledge cannot be easily determined. Moreover, by using a fixed window size during a data stream mining, the performance of this model is degraded in terms of reflecting recent changes. Based on these observations, this study relaxes the notion of window size and proposes a new algorithm named VSW (Variable Size sliding Window frequent itemset mining) which is suitable for observing recent changes in the set of frequent itemsets over data streams. The window size is determined dynamically based on amounts of concept change that occurs within the arriving data stream. The window expands as the concept becomes stable and shrinks when a concept change occurs. In this study, it is shown that if stale transactions are removed from the window after a concept change, updated frequent itemsets always belong to the most recent concept. Experimental evaluations on both synthetic and real data show that our algorithm effectively detects the concept change, adjust the window size, and adapts itself to the new concepts along the data stream.     

数据流上一种单遍扫描频繁模式树结构

针对频繁模式增长算法无法适应数据流的无限性和流动性的特点,提出一种新颖的FP-tree的变形结构--FPS-tree,只需单遍扫描便能获取当前窗口的全部数据库信息。为了在滑动窗口时有效地删除过期窗格和插入新窗格,提出一个新颖的概念--“尾结点”,FPS-tree中每条路径上的窗格信息只保持在尾结点里。实验结果表明FPS-tree的压缩性能要优于其他单遍扫描的前缀树结构。     

一种基于变尺度滑动窗口的数据流频繁集挖掘算法

基干传统滑动窗口机制的数据流频繁集挖掘算法较多地考虑快速且精确的效果,而较少考虑数据流的时变特性,对传统的滑动窗口机制进行改进.同时考虑数据流的海量特性和时变特性,提出一种基于变尺度滑动窗口机制的数据流频繁集挖掘算法V-Stream.该算法采用事务链表组的概要数据结构.能够根据数据流的数据分布变化自适应调整窗口大小.Eclipse上的仿真实验结果表明,V-Stream相比Manku算法提高了挖掘数据流频繁集的时间与空间效率.     

A false negative approach to mining frequent itemsets from high speed transactional data streams

Mining frequent itemsets from transactional data streams is challenging due to the nature of the exponential explosion of itemsets and the limit memory space required for mining frequent itemsets. Given a domain of I unique items, the possible number of itemsets can be up to 2^I − 1. When the length of data streams approaches to a very large number N, the possibility of an itemset to be frequent becomes larger and difficult to track with limited memory. The existing studies on finding frequent items from high speed data streams are false-positive oriented. That is, they control memory consumption in the counting processes by an error parameter ?, and allow items with support below the specified minimum support s but above s − ? counted as frequent ones. However, such false-positive oriented approaches cannot be effectively applied to frequent itemsets mining for two reasons. First, false-positive items found increase the number of false-positive frequent itemsets exponentially. Second, minimization of the number of false-positive items found, by using a small ?, will make memory consumption large. Therefore, such approaches may make the problem computationally intractable with bounded memory consumption. In this paper, we developed algorithms that can effectively mine frequent item(set)s from high speed transactional data streams with a bound of memory consumption. Our algorithms are based on Chernoff bound in which we use a running error parameter to prune item(set)s and use a reliability parameter to control memory. While our algorithms are false-negative oriented, that is, certain frequent itemsets may not appear in the results, the number of false-negative itemsets can be controlled by a predefined parameter so that desired recall rate of frequent itemsets can be guaranteed. Our extensive experimental studies show that the proposed algorithms have high accuracy, require less memory, and consume less CPU time. They significantly outperform the existing false-positive algorithms.     

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.     

数据流高效用模式挖掘综述

数据流高效用模式挖掘方法是以二进制的频繁模式挖掘方法为前提,引入项的内部效用和外部效用,在模式挖掘过程中可以考虑项的重要性,从而挖掘更有价值的模式。从关键窗口技术、常用方法、表示形式等角度对数据流高效用模式挖掘方法进行分析并总结其相关算法,从而研究其特点、优势、劣势以及其关键问题所在。具体来说,说明了数据流高效用模式常用的概念;对处理数据流高效用模式的关键窗口技术进行了分析,涉及到滑动、衰减、界标和倾斜窗口模型;研究了一阶段和两阶段的数据流高效用模式挖掘方法;分析了高效用模式的表示形式,即完全高效用模式和压缩高效用模式;介绍了其他的数据流高效用模式,包括序列高效用模式、混合高效用模式以及高平均效用模式等;最后展望了数据流高效用模式挖掘的进一步研究方向。     

A novel hash-based approach for mining frequent itemsets over data streams requiring less memory space

In recent times, data are generated as a form of continuous data streams in many applications. Since handling data streams is necessary and discovering knowledge behind data streams can often yield substantial benefits, mining over data streams has become one of the most important issues. Many approaches for mining frequent itemsets over data streams have been proposed. These approaches often consist of two procedures including continuously maintaining synopses for data streams and finding frequent itemsets from the synopses. However, most of the approaches assume that the synopses of data streams can be saved in memory and ignore the fact that the information of the non-frequent itemsets kept in the synopses may cause memory utilization to be significantly degraded. In this paper, we consider compressing the information of all the itemsets into a structure with a fixed size using a hash-based technique. This hash-based approach skillfully summarizes the information of the whole data stream by using a hash table, provides a novel technique to estimate the support counts of the non-frequent itemsets, and keeps only the frequent itemsets for speeding up the mining process. Therefore, the goal of optimizing memory space utilization can be achieved. The correctness guarantee, error analysis, and parameter setting of this approach are presented and a series of experiments is performed to show the effectiveness and the efficiency of this approach.     

数据流频繁项集的快速挖掘方法

近年来,数据流挖掘一直是国内外研究的热点,频繁项集挖掘又是数据流挖掘中的重要问题。根据数据流无限性和流动性的特点,提出了一种在滑动窗口中挖掘频繁项集的算法FIM-SW,FIM-SW算法主要是采用垂直的数据库表示方法,使用二进制向量表示每个数据项,并利用Apriori性质产生频繁项集。实验结果表明,这种算法显著地提高了挖掘效率。     

Online mining of frequent sets in data streams with error guarantee

For most data stream applications, the volume of data is too huge to be stored in permanent devices or to be thoroughly scanned more than once. It is hence recognized that approximate answers are usually sufficient, where a good approximation obtained in a timely manner is often better than the exact answer that is delayed beyond the window of opportunity. Unfortunately, this is not the case for mining frequent patterns over data streams where algorithms capable of online processing data streams do not conform strictly to a precise error guarantee. Since the quality of approximate answers is as important as their timely delivery, it is necessary to design algorithms to meet both criteria at the same time. In this paper, we propose an algorithm that allows online processing of streaming data and yet guaranteeing the support error of frequent patterns strictly within a user-specified threshold. Our theoretical and experimental studies show that our algorithm is an effective and reliable method for finding frequent sets in data stream environments when both constraints need to be satisfied.     

DSM-FI: an efficient algorithm for mining frequent itemsets in data streams

Online mining of data streams is an important data mining problem with broad applications. However, it is also a difficult problem since the streaming data possess some inherent characteristics. In this paper, we propose a new single-pass algorithm, called DSM-FI (data stream mining for frequent itemsets), for online incremental mining of frequent itemsets over a continuous stream of online transactions. According to the proposed algorithm, each transaction of the stream is projected into a set of sub-transactions, and these sub-transactions are inserted into a new in-memory summary data structure, called SFI-forest (summary frequent itemset forest) for maintaining the set of all frequent itemsets embedded in the transaction data stream generated so far. Finally, the set of all frequent itemsets is determined from the current SFI-forest. Theoretical analysis and experimental studies show that the proposed DSM-FI algorithm uses stable memory, makes only one pass over an online transactional data stream, and outperforms the existing algorithms of one-pass mining of frequent itemsets.

基于triemerging机制数据流滑动窗口模型的频繁模式挖掘

因树型结构的良好表达能力,在互联网中传输的信息流越来越多以树型结构形式存储。但由于流式数据的时效性,隐含在数据流中的知识会随着时间的推移发生改变。针对数据流场景下挖掘最近时间段内的频繁子树模式的问题,提出了一种滑动窗口模型下挖掘频繁子树模式算法——SWMiner算法,用于挖掘数据流下任意时刻窗口下所有的频繁子树模式。SWMiner算法使用基于前缀树的结构来压缩存储生成的树模式,并且使用trie merging机制有效地更新子树模式的支持度。实验结果表明,SWMiner算法在滑动窗口模型中的性能优于目前现有的常用算法,能有效地挖掘最近时间段内的频繁树模式。     

Mining frequent itemsets in data streams using the weighted sliding window model

In recent years, data stream mining has become an important research topic. With the emergence of new applications, the data we process are not again static, but the continuous dynamic data stream. Examples include network traffic analysis, Web click stream mining, network intrusion detection, and on-line transaction analysis. In this paper, we propose a new framework for data stream mining, called the weighted sliding window model. The proposed model allows the user to specify the number of windows for mining, the size of a window, and the weight for each window. Thus users can specify a higher weight to a more significant data section, which will make the mining result closer to user’s requirements. Based on the weighted sliding window model, we propose a single pass algorithm, called WSW, to efficiently discover all the frequent itemsets from data streams. By analyzing data characteristics, an improved algorithm, called WSW-Imp, is developed to further reduce the time of deciding whether a candidate itemset is frequent or not. Empirical results show that WSW-Imp outperforms WSW under the weighted sliding window model.     

Discovering frequent itemsets over transactional data streams through an efficient and stable approximate approach

A data stream is a massive and unbounded sequence of data elements that are continuously generated at a fast speed. Compared with traditional approaches, data mining in data streams is more challenging since several extra requirements need to be satisfied. In this paper, we propose a mining algorithm for finding frequent itemsets over the transactional data stream. Unlike most of existing algorithms, our method works based on the theory of Approximate Inclusion–Exclusion. Without incrementally maintaining the overall synopsis of the stream, we can approximate the itemsets’ counts according to certain kept information and the counts bounding technique. Some additional techniques are designed and integrated into the algorithm for performance improvement. Besides, the performance of the proposed algorithm is tested and analyzed through a series of experiments.     

TWCT-Stream:数据流上的频繁模式挖掘算法

提出一种结合倾斜时间窗的TWCT树结构,可以保存不同时间粒度下频繁模式的完全集,并设计了其顺序更新和删除算法,使其能够存储在外存,从而有效地降低算法的内存空间需求。结合TWCT树结构特点,提出了数据流上的频繁模式挖掘算法TWCT-Stream,其模式生长的TWCT-Growth算法按字典顺序生成频繁模式,以配合TWCT结构的顺序更新。实验证实算法的内存需求低于FP-Stream等同类算法。     

滑动窗口中数据流频繁项集挖掘方法

根据数据流的流动性与连续性,提出了一种滑动窗口中频繁项集挖掘算法NSW,满足了人们快速获取最近到达数据中频繁项集的需求。该算法采用二进制矩阵表示滑动窗口中的事务列表,通过直接删除最老事务、不产生候选项集等方法控制时间和空间的开销。实验表明,该算法具有较好的时间和空间效率。     

一种改进的数据流最大频繁项集挖掘算法

提出了一种基于DSM MFI算法的改进算法DSMMFI DS算法,它首先将事务数据按一定的全序关系存入DSFI list列表中;然后按排序后的顺序存储到类似概要数据结构的树中;接着删除树中和DSFI list列表中的非频繁项,同时删除窗口衰退支持数大的事务项;最后采用自顶向下和自底向上的双向搜索策略来挖掘数据流的最大频繁项集。通过用例分析和实验表明,该算法比DSM MFI算法具有更好的执行效率。     

Mining top-K frequent itemsets from data streams

Frequent pattern mining on data streams is of interest recently. However, it is not easy for users to determine a proper frequency threshold. It is more reasonable to ask users to set a bound on the result size. We study the problem of mining top K frequent itemsets in data streams. We introduce a method based on the Chernoff bound with a guarantee of the output quality and also a bound on the memory usage. We also propose an algorithm based on the Lossy Counting Algorithm. In most of the experiments of the two proposed algorithms, we obtain perfect solutions and the memory space occupied by our algorithms is very small. Besides, we also propose the adapted approach of these two algorithms in order to handle the case when we are interested in mining the data in a sliding window. The experiments show that the results are accurate.

数据流中一种基于滑动窗口的前K个频繁项集挖掘算法

数据流频繁项集挖掘是当今数据挖掘和知识学习领域重要的研究课题之一。数据流高速性、连续性、无界性、实时性对挖掘算法在时间和空间方面提出了更高的要求。传统的数据挖掘算法由于其存储结构需要频繁地维护,其挖掘方式的精度和速度较低,空间、时间效率不高。在基于粒计算和ECLAT算法的基础上提出一种挖掘数据流滑动窗口中top-K频繁项集算法,采用二进制方式存储项,利用位移运算实现增量更新,实施与运算计算项集支持度,同时利用二分查找法插入到项目序表中,输出前K个频繁项。实验结果表明,该算法在K取值不太高时具有较好的时空高效性。