基于互关联后继树的时序模式挖掘

时间序列是现实生活中常见的数据形式之一.在时间序列中发现频繁模式是分析时间序列变化规律的一项重要任务本文提出一种基于互关联后继树模型的时间序列频繁模式发现方法.该方法依据序列重要点进行分段,引人相对斜率值并结合领域知识将序列符号化,在此基础上提出一种互关联后继树的新型挖掘算法,实现了时序频繁模式的发现理论与实验表明,该方法简单、直观、高效,具有实用价值.     

基于互关联后继树的频繁模式挖掘研究

关联规则挖掘是数据挖掘的一个重要的研究内容，而产生频繁模式集是关联规则挖掘的第1步工作。很多传统的频繁模式挖掘算法都需要产生候选模式集，因而效率很低。该文提出了一种不需要产生候选集，而直接构造频繁集的频繁模式挖掘算法——基于互关联后继树的频繁模式挖掘算法。实验证明，该算法具有较好的性能。     

互关联后继树在时间序列特征模式挖掘中的应用

在文献[1]中提出的基于互关联后继树（IRST）的时间序列特征模式挖掘方法的基础上,加入了时间窗口的概念,以弥补IRST这种原本应用于文本检索中的索引模型在时间序列应用中的不足.对IRST以及挖掘算法做出了改进,弥补了其只能挖掘出紧密衔接特征模式的缺陷.实验结果表明,该方法可以挖掘出更多更具应用价值的特征模式.     

基于互关联后继树的概念格构造算法

概念格是知识工程中一个重要的知识表达工具，同时也是形式概念分析的核心．目前已出现了许多有效的概念格构造算法．提出了一个基于互关联后继树的概念格构造算法，以扩展的互关联后继树为数据模型，通过对树的搜索和相关判定定理完成所有形式概念的生成．分析了算法的性能，并做出相关结论．     

基于三元互关联后继树的Web日志挖掘

针对二元的互关联后继树模型进行改进,构造三元互关联后继树,并结合Web日志的特点,构造Web事务集的互关联后继树和增量更新模型,设计基于三元互关联后继树的频繁路径挖掘算法,挖掘Web日志中的频繁路径。通过实验证明了基于三元互关联后继树和改进后的模型的出色插入查询性能。     

基于后继区间的互关联后继树搜索算法

全文检索领域的关键问题是索引模型以及该模型之上的高效搜索算法，基于一种优秀的全文索引模型互关联后继树提出了基于后继区间的搜索算法，大大提升了全文的检索速度，从而更加充分地体现了互关联后继树模型在全文领域的优势。     

后继序列有序的互关联后继树创建和搜索算法

研究针对全文检索领域的索引结构模型,基于二元互关联后继树模型,提出并实现了一个后继序列有序的后继树模型,然后利用此索引模型实现查询操作的优化。     

基于互关联后继树的Web日志挖掘技术

本文将互关联后继树(Inter-Related Suffix Tree，IRST)模型应用于Web日志事务挖掘，构造Web日志事务集的互关联后继树结构，从中挖掘频繁路径。通过实验证明了基于IRST的Web日志挖掘系统有优秀的性能。     

多时间序列跨事务关联分析研究

论文的研究目的是为了对时间序列的发展趋势进行预测。采用的方法是对多时间序列进行跨事务关联规则分析,利用关联规则中前件和后件的时间差进行预测。提出了跨事务关联规则挖掘ITARM,该算法采用了基于压缩FP-树的、分而治之的挖掘方法。算法在产生了频繁1-项集之后,分别利用1-项集中的项作为约束条件,建立压缩FP-树,挖掘跨事务关联规则。文中给出了算法的主要设计思想和算法的伪代码,并对算法的性能进行了测试。测试结果表明,ITARM算法是一个时间和空间性能都较高的跨事务关联规则挖掘算法。     

基于IRST的并行时序模式挖掘算法*

提出一种建立在集群式高性能计算机上基于互关联后继树的并行时序模式挖掘算法,将数据线段化、树的建立及模式发现在多处理机上进行并行处理,有效地改进了算法的执行效率。实验结果表明,此算法较之串行算法有较高的效率。     

非同步多时间序列中频繁模式的发现算法

从多个时间序列中发现频繁模式在实际应用中具有非常重要的价值.已知文献所提供的方法均假设多时间序列是同步的,但是,在现实世界中,这一条件并不总能满足,许多情况下它们是非同步的.提出了一个从非同步多时间序列中发现频繁模式的算法.该算法首先利用线性化分段表示法和矢量形态聚类实现时间序列的特征分割与符号化转换,然后通过将Agrawal关联模式发现算法的核心思想与时间序列最短实现表示方法相结合,实现了非同步多时间序列中多种结构频繁模式的发掘.与已有算法相比,该算法更简单、更灵活,并且不要求序列严格同步.实验结果证明了该算法的有效性.     

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.     

结合用户兴趣的微博信息传播模式挖掘*

由于信息传播模型是社区挖掘、社区影响力研究的基础,文中提出结合用户兴趣的信息传播模型,设计基于频繁子树的信息传播微观模式挖掘方法.首先,基于微博社交网络图表示及用户多标签建模,将微观信息传播模式转换为频繁子树挖掘问题.然后,针对微博社交网络图单节点多标签特性,设计多标签节点树的频繁子树挖掘算法(MLTreeMiner).最后,结合主题提取方法,使用MLTreeMiner挖掘信息传播模式.在人工数据集上的实验表明,MLtreeMiner能高效地对多标签节点树进行频繁子树挖掘.针对新浪微博真实数据的实验也验证方法的有效性.     

时间序列可变尺度的时频特征求解及其分类

对于许多实际应用来说,获取多个不同窗口尺度上的模式,有助于发现时间序列的不同规律性特征.同时,通过对时间序列时域和频域两方面的分析,有助于挖掘更多的知识.提出了一种新的基于可变尺度的时域频域辨别性特征挖掘方法以及应用于分类的算法.主要采用了不同尺度窗口、符号聚合近似技术以及符号傅里叶近似技术等,以有效地发掘时间序列不同尺度时域频域模式;与此同时,使用统计学方法挖掘部分最具辨别性的特征用于时间序列分类,有效地降低了算法时间复杂度.在多个数据集上的对比实验结果,说明了该算法具有较高的准确率;在真实数据集上的解析,表明了该算法具有更强的可解释性.同时,该算法可扩展应用到多维时间序列分类问题中.     

多时间尺度时间序列趋势预测

针对股票、基金等大量时间序列数据的趋势预测问题，提出一种基于新颖特征模型的多时间尺度时间序列趋势预测算法。首先，在原始时间序列中提取带有多时间尺度特征的特征树，其刻画了时间序列，不仅带有序列在各个层次的特征，同时表示了层次之间的关系。然后，利用聚类挖掘特征序列中的隐含状态。最后，应用隐马尔可夫模型（HMM）设计一个多时间尺度趋势预测算法（MTSTPA），同时对不同尺度下的趋势以及趋势的长度作出预测。在真实股票数据集上的实验中，在各个尺度上的预测准确率均在60%以上，与未使用特征树对比，使用特征树的模型预测效率更高，在某一尺度上准确率高出10个百分点以上。同时，与经典自回归滑动平均模型（ARMA）模型和PHMM（Pattern-based HMM）对比，MTSTPA表现更优，验证了其有效性。     

Frequent Pattern Mining on Message Passing Multiprocessor Systems

Extraction of frequent patterns in transaction-oriented database is crucial to several data mining tasks such as association rule generation, time series analysis, classification, etc. Most of these mining tasks require multiple passes over the database and if the database size is large, which is usually the case, scalable high performance solutions involving multiple processors are required. This paper presents an efficient scalable parallel algorithm for mining frequent patterns on parallel shared nothing platforms. The proposed algorithm is based on one of the best known sequential techniques referred to as Frequent Pattern (FP) Growth algorithm. Unlike most of the earlier parallel approaches based on different variants of the Apriori Algorithm, the algorithm presented in this paper does not explicitly result in having entire counting data structure duplicated on each processor. Furthermore, the proposed algorithm introduces minimum communication (and hence synchronization) overheads by efficiently partitioning the list of frequent elements list over processors. The experimental results show scalable performance over different machine and problem sizes. The comparison of implementation results with existing parallel approaches show significant gains in the speedup. On an 8-processor machine, we report an average speedup of 6 for different problem sizes.     

带有间隔约束的多序列模式挖掘

研究这样一个问题：给定多序列、支持度阈值和间隔约束,从多序列中挖掘所有出现次数不小于支持度阈值的频繁序列模式,这里要求模式中任意两个相邻元素在序列中的出现都要满足用户自定义的间隔约束,并且模式在序列中的出现要满足one-off条件。在解决该问题上,已有算法M-OneOffMine在计算模式的支持度时,只考虑模式的每个字符在序列中的首次出现,导致计算的模式支持度远小于其真实支持度,以致许多频繁的模式没有被挖掘出来。为此,设计了一个有效的带有间隔约束的多序列模式挖掘算法--MMSP算法：首先,通过采用二维表保存模式的候选位置;然后,根据候选位置采用最左最优的思想选择匹配位置。通过生物DNA序列进行实验,多序列中元素序列数目不变而序列长度变化时,MMSP挖掘出的频繁模式总数是同类算法M-OneOffMine的3.23倍;在元素序列个数变化时,MMSP挖掘出的频繁模式个数平均是M-OneOffMine的4.11倍;这两种情况下MMSP都有更好的时间性能。在模式长度变化时,MMSP挖掘出的频繁模式个数分别平均是M-OneOffMine的2.21倍和MPP的5.24倍。同时还验证了M-OneOffMine挖掘到的模式是MMSP挖掘到的频繁的子集。实验结果表明,MMSP算法不仅可以挖掘到更多的频繁模式,而且时间花费更少,更适合于实际的应用。     

基于同步频繁树的时间序列关联规则分析

针对经典算法Apriori和频繁模式增长算法 (frequent pattern growth, FP-growth)不能直接对时间序列数据进行关联规则挖掘的问题，提出一种同步频繁树算法（synchronize frequent tree, SFT）。利用时间序列的时间属性具有一维性的特点，定义趋势项-位置表示法表示时间序列数据，将首条时间序列构建成一棵基础树，通过计算树叶子节点与列表项的信息交集，可判断其是否与该树枝中的所有节点构成频繁K项集。在SFT算法中，用趋势项-位置表示的数据内存占用情况要优于原始数据，并且在挖掘过程中不会产生候选频繁项集，使得算法在整个挖掘过程中表现出较好的时间性能。基于商品数据和股票数据的数值实验表明，SFT算法所得结果不仅与其他5种对比算法的结果一致，在各量级的数据和不同的支持度计数中，其时间复杂度都要优于对比算法。     

移动对象无冗余周期模式发现算法

技术的发展进步和需求的多样性,产生了大量的数据,数据背后隐含模式的发现对问题的深入研究起到关键性的作用.为了挖掘移动对象的周期运动模式,提出了一种无冗余周期模式(Non-redundant period patterns,NRPP)发现算法.为解决噪声因素的影响,在现有方法基础上,引入相似性因子,删减冗余周期模式,使挖掘出的模式精简、准确.算法为不同模式设置不同阈值,不但解决了稀有项问题和组合爆炸问题,而且也使得挖掘效率更高效.采用公开移动对象数据实验,结果表明算法能高效挖掘出移动对象的周期模式.     

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

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