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.     

数据流中结构二叉树挖掘算法研究

针对传统数据流挖掘算法不能挖掘出频繁项之间的关系而且挖掘时间和空间复杂度高、准确度不高的问题,本文提出了一种数据流中结构二叉树挖掘算法（AMST）。该算法利用了二叉树结构的优势,将所处理事务数据库中的数据流转化成结构化二叉树,然后利用数据流矩阵对结构二叉树进行挖掘。整个过程只对事务数据库进行了一次扫描,大大提高了挖掘的效率。此外,算法还找出了具有层次关系的频繁子树。实验结果表明,AMST算法性能稳定,在时间复杂度和空间复杂度方面有很大的优越性,能够快速准确地对数据流进行挖掘。     

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.

一种直接在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.     

基于密度的混合属性数据流聚类算法

数据流聚类分析是当前数据挖掘研究的热点问题,为了克服数据流聚类框架CluStream算法不能处理混合属性数据流的缺陷,提出了基于密度的混合属性数据流聚类算法MCStream.在微聚类中使用面向维度的距离来度量对象之间的相似度,在宏聚类中使用改进的密度聚类算法M-DBSCAN对微簇进行聚类.实验结果表明,MCStream算法能快速有效地处理混合属性数据流聚类问题.     

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.     

传感器网络分布式数据流的频繁项集挖掘算法

研究无线传感器网络中数据流频繁项集挖掘问题。针对集中式的静态数据流频繁项集挖掘方法不能在传感器网络中直接使用这一特点,提出基于传感器网络的分布式数据流的频繁项集挖掘算法FIMVS。该算法基于FPtree快速挖掘出传感器节点上单一数据流的局部频繁项集,然后通过路由将其在无线传感器网络里逐层上传合并,在Sink节点上汇聚后,采用自顶向下的高效剪枝策略挖掘出全局频繁项集。实验结果表明,该算法能有效地大幅度减少候选项集,降低无线传感器网络中的通信量,并有较高的时间和空间效率。     

Efficient single-pass frequent pattern mining using a prefix-tree

The FP-growth algorithm using the FP-tree has been widely studied for frequent pattern mining because it can dramatically improve performance compared to the candidate generation-and-test paradigm of Apriori. However, it still requires two database scans, which are not consistent with efficient data stream processing. In this paper, we present a novel tree structure, called CP-tree (compact pattern tree), that captures database information with one scan (insertion phase) and provides the same mining performance as the FP-growth method (restructuring phase). The CP-tree introduces the concept of dynamic tree restructuring to produce a highly compact frequency-descending tree structure at runtime. An efficient tree restructuring method, called the branch sorting method, that restructures a prefix-tree branch-by-branch, is also proposed in this paper. Moreover, the CP-tree provides full functionality for interactive and incremental mining. Extensive experimental results show that the CP-tree is efficient for frequent pattern mining, interactive, and incremental mining with a single database scan.     

Approximate mining of maximal frequent itemsets in data streams with different window models

A data stream is a massive, open-ended sequence of data elements continuously generated at a rapid rate. Mining data streams is more difficult than mining static databases because the huge, high-speed and continuous characteristics of streaming data. In this paper, we propose a new one-pass algorithm called DSM-MFI (stands for Data Stream Mining for Maximal Frequent Itemsets), which mines the set of all maximal frequent itemsets in landmark windows over data streams. A new summary data structure called summary frequent itemset forest (abbreviated as SFI-forest) is developed for incremental maintaining the essential information about maximal frequent itemsets embedded in the stream so far. Theoretical analysis and experimental studies show that the proposed algorithm is efficient and scalable for mining the set of all maximal frequent itemsets over the entire history of the data streams.     

流数据挖掘综述

作为一种新的数据形态,流数据对数据挖掘提出了诸多挑战。学者们已提出大量处理流数据的挖掘算法。本文对这些算法进行了综述。首先介绍了多个不同的数据流模型,这些模型对算法设计有着不同的要求。然后,总结了流数据挖掘算法的特点,并给出了算法中常用的技术。最后,分析了各个流数据挖掘任务中的代表性算法。     

Mining sequential patterns from data streams: a centroid approach

In recent years, emerging applications introduced new constraints for data mining methods. These constraints are typical of a new kind of data: the data streams. In data stream processing, memory usage is restricted, new elements are generated continuously and have to be considered in a linear time, no blocking operator can be performed and the data can be examined only once. At this time, only a few methods has been proposed for mining sequential patterns in data streams. We argue that the main reason is the combinatory phenomenon related to sequential pattern mining. In this paper, we propose an algorithm based on sequences alignment for mining approximate sequential patterns in Web usage data streams. To meet the constraint of one scan, a greedy clustering algorithm associated to an alignment method is proposed. We will show that our proposal is able to extract relevant sequences with very low thresholds.     

Frequency-based load shedding over a data stream of tuples

Usually the data generation rate of a data stream is unpredictable, and some data elements of the data stream cannot be processed in real time if the generation rate exceeds the capacity of a data stream processing algorithm. In order to overcome this situation gracefully, a load shedding technique is recommended. This paper proposes a frequency-based load shedding technique over a data stream of tuples. In many data stream processing applications, such as mining frequent patterns, data elements having high frequency can be considered more significant than others having low frequency. Based on this observation, in the proposed technique, only frequent elements of a data stream are processed in real time while the others are trimmed. The decision to shed a load from the data stream or not is controlled automatically by the data generation rate of a data stream. Consequently, an unnecessary load shedding operation is not allowed in the proposed technique.     

Efficient incremental mining of contrast patterns in changing data

A contrast pattern is a set of items (itemset) whose frequency differs significantly between two classes of data. Such patterns describe distinguishing characteristics between datasets, are meaningful to human experts, have strong discriminating ability and can be used for powerful classifiers. Incrementally mining such patterns is very important for evolving datasets, where transactions can be either inserted or deleted and mining needs to be repeated after changes occur. When the change is small, it is undesirable to carry out mining from scratch. Rather, the set of previously mined contrast patterns should be reused where possible to compute the new patterns. A primary example of evolving data is a data stream, where the data is a sequence of continuously arriving transactions (or itemsets). In this paper, we propose an efficient technique for incrementally mining contrast patterns. Our algorithm particularly aims to avoid redundant computation which might occur due to simultaneous transaction insertion and deletion, as is the case for data streams. In an experimental study using real and synthetic data streams, we show our algorithm can be substantially faster than the previous approach.     

浅论数据流挖掘

本文主要讨论了数据流挖掘的现状及发展,简要地介绍了数据流挖掘的概念,详细地介绍了数据流挖掘的特点及其数据模型的特点,介绍了几种常用数据流挖掘流挖掘方法。     

Interactive mining of high utility patterns over data streams

High utility pattern (HUP) mining over data streams has become a challenging research issue in data mining. When a data stream flows through, the old information may not be interesting in the current time period. Therefore, incremental HUP mining is necessary over data streams. Even though some methods have been proposed to discover recent HUPs by using a sliding window, they suffer from the level-wise candidate generation-and-test problem. Hence, they need a large amount of execution time and memory. Moreover, their data structures are not suitable for interactive mining. To solve these problems of the existing algorithms, in this paper, we propose a novel tree structure, called HUS-tree (high utility stream tree) and a new algorithm, called HUPMS (high utility pattern mining over stream data) for incremental and interactive HUP mining over data streams with a sliding window. By capturing the important information of stream data into an HUS-tree, our HUPMS algorithm can mine all the HUPs in the current window with a pattern growth approach. Furthermore, HUS-tree is very efficient for interactive mining. Extensive performance analyses show that our algorithm is very efficient for incremental and interactive HUP mining over data streams and significantly outperforms the existing sliding window-based HUP mining algorithms.     

均衡时空挖掘数据流中频繁项集

数据流具有流动性、连续性以及项分布不均衡性等特点,挖掘数据流中频繁项集是一项意义重大且具有挑战性的工作。提出一种均衡时空挖掘数据流中频繁项集算法—Bala_ Tree, Bala_ Tree实现一遍扫描数据流、快速簇更新、周期树结构重构以及基于经典算法挖掘频繁项集。实验表明,此算法能快速扫描和更新数据,合理利用内存以及精确获得频繁项集,Ba1a_Tree算法优于其他同类算法。     

一种基于Chernoff Bound的数据流上近似频繁项集的挖掘方法

数据流高速、无限和动态的特点决定了必须在有限的内存中以尽快的计算速度完成流数据上的频繁项集挖掘。将数据流中的数据按照段进行划分,采用二元组列表的数据结构进行保存,提出了一种基于滑动窗口的近似频繁项集挖掘方法AFIoDS,以实时获取频繁项集集合的真子集,并引入了概率参数,利用Chernoff Bound来动态改变支持度的近似值,保证真子集中的频繁项集被限制在一定的误差范围之内。此外,为了进一步节省内存,AFIoDS采用闭合项集的形式压缩每个段中获取的频繁项集。通过在3种真实数据集上的实验表明,AFIoDS算法与现有算法相比,在精度没有下降的情况下,具有更快的处理速度,同时其存储开销大大降低。     

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.     

基于时间衰减模型的数据流频繁模式挖掘

频繁模式挖掘是数据流挖掘中的重要研究课题. 针对数据流的时效性和流中心的偏移性特点, 提出了界标窗口模型与时间衰减模型相结合的数据流频繁模式挖掘算法. 该算法通过动态构建全局模式树, 利用时间指数衰减函数对模式树中各模式的支持数进行统计, 以此刻画界标窗口内模式的频繁程度; 进而, 为有效降低空间开销, 设计了剪枝阈值函数, 用于对预期难以成长为频繁的模式及时从全局树中剪除. 本文对出现在算法中的重要参数和阈值进行了深入分析. 一系列实验表明, 与现有同类算法MSW相比, 该算法挖掘精度高(平均超过90%), 内存开销小, 速度上可以满足高速数据流的处理要求, 且可以适应不同事务数量、不同事务平均长度和不同最大潜在频繁模式平均长度的数据流频繁模式挖掘.     

面向数据流的频繁项集挖掘研究

针对数据流的特点,对数据流中频繁模式挖掘问题进行了研究,提出了数据流频繁项集挖掘算法FP-SegCount。该算法将数据流分段并利用改进的FP-growth算法挖掘分段中的频繁项集。然后,利用Count Min Sketch进行项集计数。算法解决了压缩统计和计算快速高效的问题。通过和FP-DS算法的实验对比,FP-SegCount算法具有较好的时间效率。