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

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

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

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

A survey on algorithms for mining frequent itemsets over data streams

The increasing prominence of data streams arising in a wide range of advanced applications such as fraud detection and trend learning has led to the study of online mining of frequent itemsets (FIs). Unlike mining static databases, mining data streams poses many new challenges. In addition to the one-scan nature, the unbounded memory requirement and the high data arrival rate of data streams, the combinatorial explosion of itemsets exacerbates the mining task. The high complexity of the FI mining problem hinders the application of the stream mining techniques. We recognize that a critical review of existing techniques is needed in order to design and develop efficient mining algorithms and data structures that are able to match the processing rate of the mining with the high arrival rate of data streams. Within a unifying set of notations and terminologies, we describe in this paper the efforts and main techniques for mining data streams and present a comprehensive survey of a number of the state-of-the-art algorithms on mining frequent itemsets over data streams. We classify the stream-mining techniques into two categories based on the window model that they adopt in order to provide insights into how and why the techniques are useful. Then, we further analyze the algorithms according to whether they are exact or approximate and, for approximate approaches, whether they are false-positive or false-negative. We also discuss various interesting issues, including the merits and limitations in existing research and substantive areas for future research.     

对数据流频繁项集挖掘算法WSW-Imp的改进

近年来随着新的应用的出现,比如网络流量分析、在线事物分析和网络欺诈检测等,对数据流的挖掘成了一个越来越重要的课题。对于数据流频繁项集的挖掘,目前绝大部分的研究都集中在传统的窗口模式下进行,即时间衰退窗口模式、界标窗口模式和滑动窗口模式。Pauray S.M.Tsai于2009年提出了一种新的窗口模式：加权滑动窗口模式,并设计了两个基于此窗口模式的数据流频繁项集挖掘算法WSW和WSW-Imp,其中WSW-Imp是对WSW算法的改进。在研究了加权滑动窗口模式以及WSW-Imp算法的基础上,对WSW-Imp算法作了进一步的改进,设计了算法WSW-Imp2,并从理论上证明了WSW-Imp2算法比WSW-Imp算法更高效,实验结果也表明了这一点。     

Interactive mining of top-K frequent closed itemsets from data streams

Mining closed frequent itemsets from data streams is of interest recently. However, it is not easy for users to determine a proper minimum support threshold. Hence, it is more reasonable to ask users to set a bound on the result size. Therefore, an interactive single-pass algorithm, called TKC-DS (top-K frequent closed itemsets of data streams), is proposed for mining top-K closed itemsets from data streams efficiently. A novel data structure, called CIL (closed itemset lattice), is developed for maintaining the essential information of closed itemsets generated so far. Experimental results show that the proposed TKC-DS algorithm is an efficient method for mining top-K frequent itemsets from data streams.     

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

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

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

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

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

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

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

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

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.

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

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

数据流中一种基于滑动窗口的前K个

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

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.

Finding frequent itemsets over online data streams

Conventional data mining methods for finding frequent itemsets require considerable computing time to produce their results from a large data set. Due to this reason, it is almost impossible to apply them to an analysis task in an online data stream where a new transaction is continuously generated at a rapid rate. An algorithm for finding frequent itemsets over an online data stream should support flexible trade-off between processing time and mining accuracy. Furthermore, the most up-to-date resulting set of frequent itemsets should be available quickly at any moment. To satisfy these requirements, this paper proposes a data mining method for finding frequent itemsets over an online data stream. The proposed method examines each transaction one-by-one without any candidate generation process. The count of an itemset that appears in each transaction is monitored by a lexicographic tree resided in main memory. The current set of monitored itemsets in an online data stream is minimized by two major operations: delayed-insertion and pruning. The former is delaying the insertion of a new itemset in recent transactions until the itemset becomes significant enough to be monitored. The latter is pruning a monitored itemset when the itemset turns out to be insignificant. The number of monitored itemsets can be flexibly controlled by the thresholds of these two operations. As the number of monitored itemsets is decreased, frequent itemsets in the online data stream are more rapidly traced while they are less accurate. The performance of the proposed method is analyzed through a series of experiments in order to identify its various characteristics.     

基于向量的数据流滑动窗口中最大频繁项集挖掘*

针对相关算法在挖掘数据流最大频繁项集时所存在的问题,提出了一种基于向量的数据流滑动窗口中最大频繁项集挖掘算法。该算法首先用向量作为概要数据结构,采用定量更新滑动窗口策略解决时间粒度问题;其次通过位运算产生频繁项集,利用矩阵和数组存储辅助信息,深度优先搜索产生最大频繁项集时利用剪枝策略进一步减少挖掘时间;最后用索引链表存储挖掘结果以提高超集检测效率。理论分析和实验结果验证了该算法的有效性。     

数据流上最近频繁项集挖掘算法

数据流频繁项集挖掘是指在数据流中找出出现频数大于给定的最小支持度的项集过程。随着一些新兴应用如传感器网络、网络监控等的出现,数据流中频繁项集挖掘引起了很大的重视。提出了一种新颖的数据流频繁项集挖掘算法RFIF。不同于现有算法,RFIF算法针对现实中的一些实际应用,更多的考虑最近时间发生的事件,但也不完全抛弃历史数据,通过引入GIMT函数,逐渐加大项集支持度的阈值,减少对历史数据中频繁项集的维护。实验验证了算法的有效性。     

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.     

不确定数据流最大频繁项集挖掘算法研究

对于大型数据,频繁项集挖掘显得庞大而冗余,挖掘最大频繁项集可以减少挖出的频繁项集的个数。可是对于不确定性数据流,传统判断项集是否频繁的方法已不能准确表达项集的频繁性,而且目前还没有在不确定数据流上挖掘最大频繁项集的相关研究。因此,针对上述不足,提出了一种基于衰减模型的不确定性数据流最大频繁项集挖掘算法TUFSMax。该算法采用标记树结点的方法,使得算法不需要超集检测就可挖掘出所有的最大频繁项集,节约了超集检测时间。实验证明了提出的算法在时间和空间上具有高效性。     

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.     

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.