基于Sequitur的时间序列异步周期模式挖掘

现有的时间序列异步周期模式挖掘方法是在获取1-pattern有效段及周期的基础上再以枚举法得到i-patterns,时间复杂度较高。为解决该问题,提出一种改进的异步周期模式挖掘方法。在时间序列符号化后,使用基于Sequitur的候选模式算法获取候选i-patterns及其事件位置序列,通过基于OEOP的i-patterns有效段生成算法得到1-pattern和i-patterns的有效段及周期,从而生成有效子序列。实验结果表明,该方法具有较高的挖掘效率。     

Periodicity detection in time series databases

Periodicity mining is used for predicting trends in time series data. Discovering the rate at which the time series is periodic has always been an obstacle for fully automated periodicity mining. Existing periodicity mining algorithms assume that the periodicity, rate (or simply the period) is user-specified. This assumption is a considerable limitation, especially in time series data where the period is not known a priori. In this paper, we address the problem of detecting the periodicity rate of a time series database. Two types of periodicities are defined, and a scalable, computationally efficient algorithm is proposed for each type. The algorithms perform in O(n log n) time for a time series of length n. Moreover, the proposed algorithms are extended in order to discover the periodic patterns of unknown periods at the same time without affecting the time complexity. Experimental results show that the proposed algorithms are highly accurate with respect to the discovered periodicity rates and periodic patterns. Real-data experiments demonstrate the practicality of the discovered periodic patterns.     

时间序列周期模式挖掘的周期检测方法

周期是时间序列的重要特征之一,用于精确描述时间序列并预测其发展趋势。在现有周期模式挖掘算法中,周期长度由用户事先定义,忽略了噪声的存在。在ERP度量和时间弯曲算法的基础上,提出一种新的周期长度检测方法。该方法可以在时间轴上实现弯曲,包括延伸和平移。它受噪声干扰的影响较小,实验结果表明其性能优于原有周期检测算法。     

Incremental, online, and merge mining of partial periodic patterns in time-series databases

Mining of periodic patterns in time-series databases is an interesting data mining problem. It can be envisioned as a tool for forecasting and prediction of the future behavior of time-series data. Incremental mining refers to the issue of maintaining the discovered patterns over time in the presence of more items being added into the database. Because of the mostly append only nature of updating time-series data, incremental mining would be very effective and efficient. Several algorithms for incremental mining of partial periodic patterns in time-series databases are proposed and are analyzed empirically. The new algorithms allow for online adaptation of the thresholds in order to produce interactive mining of partial periodic patterns. The storage overhead of the incremental online mining algorithms is analyzed. Results show that the storage overhead for storing the intermediate data structures pays off as the incremental online mining of partial periodic patterns proves to be significantly more efficient than the nonincremental nononline versions. Moreover, a new problem, termed merge mining, is introduced as a generalization of incremental mining. Merge mining can be defined as merging the discovered patterns of two or more databases that are mined independently of each other. An algorithm for merge mining of partial periodic patterns in time-series databases is proposed and analyzed.     

Efficient Discovery of Unusual Patterns in Time Series

The problem of finding a specified pattern in a time series database (i.e., query by content) has received much attention and is now a relatively mature field. In contrast, the important problem of enumerating all surprising or interesting patterns has received far less attention. This problem requires a meaningful definition of “surprise”, and an efficient search technique. All previous attempts at finding surprising patterns in time series use a very limited notion of surprise, and/or do not scale to massive datasets. To overcome these limitations we propose a novel technique that defines a pattern surprising if the frequency of its occurrence differs substantially from that expected by chance, given some previously seen data. This notion has the advantage of not requiring the user to explicitly define what is a surprising pattern, which may be hard, or perhaps impossible, to elicit from a domain expert. Instead, the user gives the algorithm a collection of previously observed “normal” data. Our algorithm uses a suffix tree to efficiently encode the frequency of all observed patterns and allows a Markov model to predict the expected frequency of previously unobserved patterns. Once the suffix tree has been constructed, a measure of surprise for all the patterns in a new database can be determined in time and space linear in the size of the database. We demonstrate the utility of our approach with an extensive experimental evaluation.     

多粒度时间下的近似周期挖掘研究

研究时态数据库中多粒度时间下的近似周期的挖掘问题。在多粒度时间、多粒度时间格式的基础上引入多粒度时间间隔的定义以及相关性质,构造多粒度近似周期模型,提出一个基于SOM聚类的多粒度近似周期的挖掘算法。利用高频股票数据580000宝钢JBT1进行实验,证明了该算法的有效性。     

多粒度时间下的近似周期挖掘研究

研究时态数据库中多粒度时间下的近似周期的挖掘问题。在多粒度时间、多粒度时问格式的基础上引入多粒度时间间隔的定义以及相关性质,构造多粒度近似周期模型,提出一个基于SOM聚类的多粒度近似周期的挖掘算法。利用高频股票数据580000宝钢JBT1进行实验,证明了该算法的有效性。     

挖掘多粒度时间下异步周期的模式

把异步周期和多时间粒度下的时态模型结合起来研究,并利用异步周期的特点提出了一种有效的挖掘算法。算法先找到所有的有效时间节，再通过有效时间节求出最长的有效时间段。实验表明所提出的算法是稳定而有效的。     

SMCA: a general model for mining asynchronous periodic patterns in temporal databases

Mining periodic patterns in time series databases is an important data mining problem with many applications. Previous studies have considered synchronous periodic patterns where misaligned occurrences are not allowed. However, asynchronous periodic pattern mining has received less attention and only been discussed for a sequence of symbols where each time point contains one event. In this paper, we propose a more general model of asynchronous periodic patterns from a sequence of symbol sets where a time slot can contain multiple events. Three parameters min/spl I.bar/rep, max/spl I.bar/dis, and global/spl I.bar/rep are employed to specify the minimum number of repetitions required for a valid segment of nondisrupted pattern occurrences, the maximum allowed disturbance between two successive valid segments, and the total repetitions required for a valid sequence. A 4-phase algorithm is devised to discover periodic patterns from a time series database presented in vertical format. The experiments demonstrate good performance and scalability with large frequent patterns.     

Discovering Transitional Patterns and Their Significant Milestones in Transaction Databases

A transaction database usually consists of a set of time-stamped transactions. Mining frequent patterns in transaction databases has been studied extensively in data mining research. However, most of the existing frequent pattern mining algorithms (such as Apriori and FP-growth) do not consider the time stamps associated with the transactions. In this paper, we extend the existing frequent pattern mining framework to take into account the time stamp of each transaction and discover patterns whose frequency dramatically changes over time. We define a new type of patterns, called transitional patterns, to capture the dynamic behavior of frequent patterns in a transaction database. Transitional patterns include both positive and negative transitional patterns. Their frequencies increase/decrease dramatically at some time points of a transaction database. We introduce the concept of significant milestones for a transitional pattern, which are time points at which the frequency of the pattern changes most significantly. Moreover, we develop an algorithm to mine from a transaction database the set of transitional patterns along with their significant milestones. Our experimental studies on real-world databases illustrate that mining positive and negative transitional patterns is highly promising as a practical and useful approach for discovering novel and interesting knowledge from large databases.     

Mining fuzzy periodic association rules

We develop techniques for discovering patterns with periodicity in this work. Patterns with periodicity are those that occur at regular time intervals, and therefore there are two aspects to the problem: finding the pattern, and determining the periodicity. The difficulty of the task lies in the problem of discovering these regular time intervals, i.e., the periodicity. Periodicities in the database are usually not very precise and have disturbances, and might occur at time intervals in multiple time granularities. To overcome these difficulties and to be able to discover the patterns with fuzzy periodicity, we propose the fuzzy periodic calendar which defines fuzzy periodicities. Furthermore, we develop algorithms for mining fuzzy periodicities and the fuzzy periodic association rules within them. Experimental results have shown that our method is effective in discovering fuzzy periodic association rules.     

Mining sequential patterns across multiple sequence databases

In this paper, given a set of sequence databases across multiple domains, we aim at mining multi-domain sequential patterns, where a multi-domain sequential pattern is a sequence of events whose occurrence time is within a pre-defined time window. We first propose algorithm Naive in which multiple sequence databases are joined as one sequence database for utilizing traditional sequential pattern mining algorithms (e.g., PrefixSpan). Due to the nature of join operations, algorithm Naive is costly and is developed for comparison purposes. Thus, we propose two algorithms without any join operations for mining multi-domain sequential patterns. Explicitly, algorithm IndividualMine derives sequential patterns in each domain and then iteratively combines sequential patterns among sequence databases of multiple domains to derive candidate multi-domain sequential patterns. However, not all sequential patterns mined in the sequence database of each domain are able to form multi-domain sequential patterns. To avoid the mining cost incurred in algorithm IndividualMine, algorithm PropagatedMine is developed. Algorithm PropagatedMine first performs one sequential pattern mining from one sequence database. In light of sequential patterns mined, algorithm PropagatedMine propagates sequential patterns mined to other sequence databases. Furthermore, sequential patterns mined are represented as a lattice structure for further reducing the number of sequential patterns to be propagated. In addition, we develop some mechanisms to allow some empty sets in multi-domain sequential patterns. Performance of the proposed algorithms is comparatively analyzed and sensitivity analysis is conducted. Experimental results show that by exploring propagation and lattice structures, algorithm PropagatedMine outperforms algorithm IndividualMine in terms of efficiency (i.e., the execution time).     

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

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

STNR: A suffix tree based noise resilient algorithm for periodicity detection in time series databases

Periodicity detection has been used extensively in predicting the behavior and trends of time series databases. In this paper, we present a noise resilient algorithm for periodicity detection using suffix trees as an underlying data structure. The algorithm not only calculates symbol and segment periodicity, but also detects the partial (or sequence) periodicity in time series. Most of the existing algorithms fail to perform efficiently in presence of noise; although noise is an inevitable constituent of real world data. The conducted experiments demonstrate that our algorithm performs more efficiently compared to other algorithms in presence of replacement, insertion, deletion or a mixture of any of these types of noise.     

New and efficient knowledge discovery of partial periodic patterns with multiple minimum supports

The problem of mining partial periodic patterns is an important issue with many applications. Previous studies to find these patterns encounter efficiency and effectiveness problem. The efficiency problem is that most previous methods were proposed to find frequent partial periodic patterns by extending the well-known Apriori-like algorithm. However, these methods generate many candidate partial periodic patterns to calculate the patterns’ supports, spending much time for discovering patterns. The effective problem is that only one minimum support threshold is set to find frequent partial periodic patterns but the results is not practical for real-world. In real-life circumstances, some rare or specific events may occur with lower frequencies but their occurrences may offer some vital information to be referred in decision making. If the minimum support is set too high, the associations between events along with higher and lower frequencies cannot be evaluated so that significant knowledge will be ignored. In this study, an algorithm to overcome these two problems has been proposed to generating redundant candidate patterns and setting only one minimum support threshold. The algorithm greatly improves the efficiency and effectiveness. First, it eliminates the need to generate numerous candidate partial periodic patterns thus reducing database scanning. Second, the minimum support threshold of each event can be specified based in its real-life occurring frequency.     

An efficient algorithm for mining top-<Emphasis Type="Italic">k</Emphasis> on-shelf high utility itemsets

High on-shelf utility itemset (HOU) mining is an emerging data mining task which consists of discovering sets of items generating a high profit in transaction databases. The task of HOU mining is more difficult than traditional high utility itemset (HUI) mining, because it also considers the shelf time of items, and items having negative unit profits. HOU mining can be used to discover more useful and interesting patterns in real-life applications than traditional HUI mining. Several algorithms have been proposed for this task. However, a major drawback of these algorithms is that it is difficult for users to find a suitable value for the minimum utility threshold parameter. If the threshold is set too high, not enough patterns are found. And if the threshold is set too low, too many patterns will be found and the algorithm may use an excessive amount of time and memory. To address this issue, we propose to address the problem of top-k on-shelf high utility itemset mining, where the user directly specifies k, the desired number of patterns to be output instead of specifying a minimum utility threshold value. An efficient algorithm named KOSHU (fast top-K on-shelf high utility itemset miner) is proposed to mine the top-k HOUs efficiently, while considering on-shelf time periods of items, and items having positive and/or negative unit profits. KOSHU introduces three novel strategies, named efficient estimated co-occurrence maximum period rate pruning, period utility pruning and concurrence existing of a pair 2-itemset pruning to reduce the search space. KOSHU also incorporates several novel optimizations and a faster method for constructing utility-lists. An extensive performance study on real-life and synthetic datasets shows that the proposed algorithm is efficient both in terms of runtime and memory consumption and has excellent scalability.     

用户访问兴趣路径挖掘方法

针对当前挖掘用户访问模式算法仅将频繁访问路径作为用户浏览兴趣路径的问题,依据使用Web日志挖掘用户兴趣页面时,通过引入页面信息量参数,综合考虑页面访问次数、浏览时间和页面信息量大小来定义用户兴趣度,提出了基于兴趣度的用户访问模式挖掘算法。实验证明该算法是有效的,在用户浏览兴趣度量方面比当前的频繁访问路径挖掘算法更准确。     

基于多维时态关联规则的演化模糊推理预测算法

挖掘时态关联规则的目的是为了发现带有时态信息的项集之间有趣的关系.由于数据库经常动态更新,时态关联规则的挖掘也应该适应数据库的更新.然而,现有的大多数算法不仅需要重新挖掘更新的数据库,浪费了大量的时间和效率,而且不能利用已存在的规则定量地预测某些项的变化趋势.本文提出了一个基于多维时态关联规则的演化模糊推理预测建模算法（Evolving fuzzy inference model based on multidimensional temporal association rules,EFI-MTAR）,主要优势是构建了一种基于多维时态关联规则的模糊推理建模算法（Fuzzy inference modeling algorithm based on multidimensional temporal association rules,FI-MTAR）,实现了对时间序列的定量预测.此外,为了降低规则更新的代价和加快规则预测的速度,提出了概念漂移检测策略来处理时间序列数据以适应数据库的动态更新.实验结果表明了本文提出算法的有效性和准确性.     

Spatiotemporal feature mining algorithm based on multiple minimum supports of pattern growth in Internet of Things

The temporal and spatial characteristics of users are involved in most Internet of Things (IoT) applications. The spatial and temporal movement patterns of users are the most direct manifestation of the temporal and spatial characteristics. The user’s interests, activities, experience and other characteristics are reflected by mobile mode. In view of the low clustering efficiency of moving objects in convergent pattern mining in the IoT, a spatiotemporal feature mining algorithm based on multiple minimum supports of pattern growth is proposed. Based on the temporal characteristics of user trajectories, frequent and asynchronous periodic spatiotemporal movement patterns are mined. Firstly, the location sequence is modeled, and the time information is added to the model. Then, a mining algorithm of asynchronous periodic sequential pattern is adopted. The algorithm is based on multiple minimum supports of pattern growth. According to multiple minimum supports, the sequential pattern of asynchronous period is mined deeply and recursively. Finally, the proposed method is validated and evaluated by Gowalla dataset, in which the user characteristics are truly reflected. It is shown by the experimental results that the average pointwise mutual information (PWI) of the proposed algorithm reaches 0.93. And the algorithm is proved to be effective and accurate.

     

基于B-list的快速频繁模式挖掘算法

针对现有的频繁模式挖掘算法存在建树复杂、挖掘效率低等问题,提出一种基于构造链表（B-list）的频繁模式挖掘（BLFPM）算法。BLFPM使用一种新的数据结构B-list表示频繁项集,通过连接两个k-1-频繁项集的B-list可以快速得到k-项集的支持度,避免了多次扫描数据库;针对连接两个B-list时间复杂度高的问题,给出了一种线性时间复杂度的连接方法,提高了BLFPM的时间效率;同时,BLFPM采用集合枚举树代表搜索空间,并使用子集非频繁剪枝策略,减小了频繁模式挖掘的搜索空间,提高了算法的执行速度。实验结果表明,与NSFI算法和prepost算法相比,BLFPM的时间效率提高约12%到29%,空间效率提高约10%到24%,对稀疏数据库或稠密数据库进行频繁模式挖掘均可以得到良好的效果。