时间序列中快速模式发现算法的研究

针对长时间序列,该文提出了一种新的能快速发现序列中时序模式的检索方法。首先将时间序列分成若干等长的子序列;接着从每个子序列中提取特征序列,该特征序列能够反映子序列中数据的变化趋势;然后根据每个特征序列将相应的子序列分配到一系列盒子中,使得不同盒子中的子序列因数据变化趋势不同而不相似,而在同一盒子中的序列由于数据变化趋势相同而有可能相似;最后通过计算每个盒子中任意两个子序列间的欧几里德距离来发现所有的模式。有关实验证明该算法是行之有效的。     

一种不确定连续时间序列的Top-K异常检测算法

针对噪声数据对时间序列异常检测准确性的影响问题, 提出了一种不确定连续时间序列Top-K异常检测算法。在典型时间序列异常检测方法的基础上对时间序列的异常值进行区间处理, 构造满足均匀分布的密度函数, 结合不确定Top-K技术, 实现含噪连续时间序列在分布未知情况下的Top-K异常排序。实验部分采用模拟数据和真实数据进行算法测试, 算法较传统方法在异常检测的准确率方面有明显提高, 虽然在计算时间上有所增加, 但提出了相应的优化策略, 使计算时间在k值大于5时有明显改善, 验证了算法的有效性。     

基于短序列分组和拼接策略的子序列快速查询算法

子序列查询技术在金融、商业、医疗等领域均有重要应用,但因DTW（dynamic time warping）等相似性比对算法的时间复杂度较高,子序列长度对检索时间影响很大,限制了数据集上长子序列检索的效率。针对这一问题提出一种子序列快速查询算法。首先对数据集中特定长度下所有子序列进行分组并标记出代表性子序列;然后在查询时将查询序列切分成定长的小段序列,并用DTW算法确定与小段序列相似的代表子序列候选集;最后对候选集进行序列拼接,获取到查询结果序列。实验表明新算法效率较典型算法提高约10倍。     

基于时间序列的模式表示挖掘频繁子模式

论文提出了一种基于时间序列的模式表示挖掘时间序列中频繁子模式的算法(TSFSM)。时间序列的模式表示本身就具有压缩数据、保持时间序列基本形态的功能,并且具有一定的除噪能力。在时间序列的模式表示的基础上挖掘其频繁子模式,可以大大提高挖掘的效率和准确性,达到事半功倍的效果。在该算法中,还使用了一定的剪枝策略,使得算法的时间复杂度进一步降低。并且该算法计算简单,实现方便,可以支持时间序列的动态增长。     

海量数据流上快速Top-K子序列匹配算法研究

数据流技术在金融分析、网络监控等诸多领域得到了广泛应用,而已有的子序列匹配算法主要针对静态序列,难于直接应用到海量、高速和连续的流数据。本文在动态时间规整技术的基础上,提出了一种新颖的TopKSM算法,能渐进、实时地获取Top-K相似子序列。算法完全符合数据流"单遍扫描"的性能要求。大量的实验表明,与现有的SPRING算法相比,该算法具有更高的性能。     

基于符号化表示的时间序列频繁子序列挖掘

提出一种新的基于符号化表示的时间序列频繁子序列的挖掘算法。利用基于PAA的分段线性表示法进行降维,通过在高斯分布下设置断点,实现时间序列符号化表示,利用投影数据库挖掘频繁子序列。该算法简单、新颖,运行快速,简化了子序列支持数的计算。     

基于特征点界标过滤的时间序列模式匹配方法

动态时间弯曲距离能度量不等长的时间序列、且具有较高的匹配精度,因此广泛应用在时间序列模式匹配中。但其计算复杂度较高,制约了在大规模数据集上的应用。为了实现时间序列模式度量结果和计算复杂度的平衡,提出一种基于特征点界标过滤的时间序列模式匹配方法。首先,提出一种特征点界标过滤的特征提取方法,保留时间序列主要特征,压缩时间维度;然后,利用动态时间弯曲距离对特征序列进行相似性度量;最后,在应用数据集上对所提方法进行有效性验证。实验结果表明,所提方法在保证高精度的前提下,能有效降低计算复杂度。     

时间序列相似模式的分层匹配

首先将时间序列经EMD分解成细节部分和趋势部分,对低频趋势部分的序列数据进行线性分段近似表示,完成对序列数据的压缩,并将其变换成一种0-1串的形式,以适应趋势序列的快速匹配;然后通过对趋势序列模式聚类,达到对序列的粗匹配;最后对粗匹配的序列进行距离计算,从而获取细匹配的模式．实验结果表明该算法是有效的．     

基于子序列全连接和最大团的时间序列模体发现算法

针对时间序列模体发现算法计算复杂，并且无法发现多实例模体的问题，提出基于子序列全连接和最大团的时间序列模体发现（TSSJMC）算法。首先，使用快速时间序列子序列全连接算法求得所有子序列之间的距离，生成距离矩阵；然后，设置相似性阈值，将距离矩阵转化为邻接矩阵，构造子序列相似图；最后采用最大团搜索算法从相似图中搜索最大团，最大团的顶点对应的时间序列为包含最多实例的模体。在公开的时间序列数据集上进行实验，选用已有的能够发现多实例模体的Brute Force和Random Projection算法作为对比对象，分别从准确性、效率、可扩展性和鲁棒性对TSSJMC算法进行分析并获得了客观的评判结果。实验结果表明，与Random Projection算法相比，TSSJMC算法在效率、可扩展性和鲁棒性法方面均有明显优势；与Brute Force算法相比，TSSJMC算法发现的模体实例数量虽略低，但其效率和可扩展性都优于Brute Force算法。因此，TSSJMC是质量和效率相平衡的算法。     

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

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

基于距离和密度的时间序列异常检测方法研究

在时间序列的GMBR表示的基础上,首次提出将基于距离和基于密度的时间序列检测方法结合,给出了时间序列模式异常的定义,并用“异常特征值”来衡量时间序列模式的异常程度.根据所提出的模式异常的定义,在强力搜索算法的基础之上提出了新的时间序列异常检测算法GMBR-DD (Grid Minimum Bounding Rectangle-Discords Detect),该算法将基于距离和基于密度的异常检测方法结合,能够高效地发现时间序列中的异常模式.通过三组实验数据,对提出的异常时间序列定义和时间序列的异常检测算法进行了验证,实验结果表明所提出的时间序列异常检测算法能够有效地发现时间序列的异常变动,为决策提供了很好的平台和有力的工具.     

A fast algorithm for complex discord searches in time series: HOT SAX Time

Time series analysis is quickly proceeding towards long and complex tasks. In recent years, fast approximate algorithms for discord search have been proposed in order to compensate for the increasing size of the time series. It is more interesting, however, to find quick exact solutions. In this research, we improved HOT SAX (Heuristically Ordered Time series using Symbolic Aggregate ApproXimation) by exploiting two main ideas: the warm-up process, and the similarity between sequences close in time. These improvements can reduce the size of the discord search space by orders of magnitude when compared with HOT SAX. The resulting algorithm, called HOT SAX Time (HST), has been validated with real and synthetic time series, and successfully compared with HOT SAX, RRA (Rare Rule Anomaly), SCAMP (SCAlable Matrix Profile), and DADD (Disk Aware Discord Discovery). The complexity of a discord search has been evaluated with a new indicator, the cost per sequence (cps), which allows one to compare searches on time series of different lengths. Numerical evidence suggests that two conditions are involved in determining the complexity of a discord search in a non-trivial way: the length of the discords, and the noise/signal ratio. This is the first exact discord search algorithm that has been demonstrated being more than 100 times faster than HOT SAX.

     

Improvement of the fast exact pairwise-nearest-neighbor algorithm

Pairwise-nearest-neighbor (PNN) is an effective method of data clustering, which can always generate good clustering results, but with high computational complexity. Fast exact PNN (FPNN) algorithm proposed by Fränti et al. is an effective method to speed up PNN and generates the same clustering results as those generated by PNN. In this paper, we present a novel method to improve the FPNN algorithm. Our algorithm uses the property that the cluster distance increases as the cluster merge process proceeds and adopts a fast search algorithm to reject impossible candidate clusters. Experimental results show that our proposed method can effectively reduce the number of distance calculations and computation time of FPNN algorithm. Compared with FPNN, our proposed approach can reduce the computation time and number of distance calculations by a factor of 24.8 and 146.4, respectively, for the data set from three real images. It is noted that our method generates the same clustering results as those produced by PNN and FPNN.     

基于数据流模型的NetFlow流数据安全检测分析系统

本文设计了一个基于数据流模型的Netflow流数据安全监测分析系统,其应用背景是在骨干网络路由器上的大规模数据流处理。基于对Netflow原始流信息中的源/目的IP地址、源/目的端口、TCP/UDP/ICMP协议等进行SUM、CONUT、Top-K三种聚集计算,对骨干网络中的流数据根据相关需求进行监测骨干网络中的网络安全事件,进一步对未知蠕虫病毒具有检测和预警的功能。SUM、COUNT、Top-K三个底层通用算法基于数据流模型,体现出了它的实时性、持续性及其高性能。     

基于差异性采样的流数据聚类算法

针对传统聚类算法对流数据进行聚类时面临时间复杂度高,存储空间需求大以及准确度较低的问题,提出一种基于差异性采样的流数据聚类算法。首先利用差异性采样法对流数据进行采样并用样本点构造核矩阵,然后利用核模糊C均值聚类算法对核矩阵中的点进行聚类得到一个带有标记的样本核矩阵,最后利用带有标记的样本核矩阵对流数据中的点进行划分。同时利用衰退聚类机制,实时更新样本核矩阵。实验结果表明,相比于传统聚类算法,该算法实现了更低的时间复杂度,同时实时聚类,得到较为理想的聚类结果。     

ESPSA: A prediction-based algorithm for streaming time series segmentation

Streaming time series segmentation is one of the major problems in streaming time series mining, which can create the high-level representation of streaming time series, and thus can provide important supports for many time series mining tasks, such as indexing, clustering, classification, and discord discovery. However, the data elements in streaming time series, which usually arrive online, are fast-changing and unbounded in size, consequently, leading to a higher requirement for the computing efficiency of time series segmentation. Thus, it is a challenging task how to segment streaming time series accurately under the constraint of computing efficiency. In this paper, we propose exponential smoothing prediction-based segmentation algorithm (ESPSA). The proposed algorithm is developed based on a sliding window model, and uses the typical exponential smoothing method to calculate the smoothing value of arrived data element of streaming time series as the prediction value of the future data. Besides, to determine whether a data element is a segmenting key point, we study the statistical characteristics of the prediction error and then deduce the relationship between the prediction error and the compression rate. The extensive experiments on both synthetic and real datasets demonstrate that the proposed algorithm can segment streaming time series effectively and efficiently. More importantly, compared with candidate algorithms, the proposed algorithm can reduce the computing time by orders of magnitude.     

一种基于动态修正值的分布数据流Top-K查询处理算法

对分布式数据流进行查询,得到数值最大的K个对象(Top-K观测查询),最直接的解决方法是由中心结点处理分布式数据流,但这种方法导致中心结点和网络负载较大.提出一种基于动态修正值的查询算法,通过对观测数据进行计算得到修正值,并利用该修正值对不同结点处的对象数据进行操作,从而无需将结点数据流全部发送到中心结点就能完成Top-K观测查询.因而可以减少对网络带宽的要求和降低中心结点的负载,同时还能保持查询结果的完全准确.     

Dm-KDE: dynamical kernel density estimation by sequences of KDE estimators with fixed number of components over data streams

In many data stream mining applications, traditional density estimation methods such as kernel density estimation, reduced set density estimation can not be applied to the density estimation of data streams because of their high computational burden, processing time and intensive memory allocation requirement. In order to reduce the time and space complexity, a novel density estimation method Dm-KDE over data streams based on the proposed algorithm m-KDE which can be used to design a KDE estimator with the fixed number of kernel components for a dataset is proposed. In this method, Dm-KDE sequence entries are created by algorithm m-KDE instead of all kernels obtained from other density estimation methods. In order to further reduce the storage space, Dm-KDE sequence entries can be merged by calculating their KL divergences. Finally, the probability density functions over arbitrary time or entire time can be estimated through the obtained estimation model. In contrast to the state-of-the-art algorithm SOMKE, the distinctive advantage of the proposed algorithm Dm-KDE exists in that it can achieve the same accuracy with much less fixed number of kernel components such that it is suitable for the scenarios where higher on-line computation about the kernel density estimation over data streams is required.We compare Dm-KDE with SOMKE and M-kernel in terms of density estimation accuracy and running time for various stationary datasets. We also apply Dm-KDE to evolving data streams. Experimental results illustrate the effectiveness of the proposed method.     

改进DTW下界函数的距离度量方法研究

动态时间弯曲算法（DTW）是一种常见的时间序列相似性度量方法,对数据挖掘任务起着至关重要的作用。针对现有DTW算法的时间复杂度高、度量精确度一般的特征,提出一种DTW下界函数的提前终止算法（LB_ESDTW）。引入提前终止思想,提高算法的执行效率;再在提前终止算法思想的基础上,与DTW下界函数相结合,提出一种基于提前终止DTW的下界函数算法（LB_ESDTW）。该算法在保证高效的运行时间效率的同时,也使得算法的度量准确率得到了提升。实验结果表明,LB_ESDTW在绝大部分时间序列数据集中,都表现出良好的适应性,针对不同类别的时间序列,都能有良好的度量性能。