多维时序数据中的相似子序列搜索研究

由于动态时间弯曲距离较之欧氏距离有更好鲁棒性,因此被广泛用作时序数据相似子序列搜索研究领域中的相似性度量.在单一维度上的相似子序列搜索可能不能获得足够的匹配结果作为继续深入分析的依据,因此通过引入在多维数据分析中常用的数据立方体模型将相似子序列搜索问题扩展到了多维场景之下,从而在多个维度上得到搜索结果以获取更多有价值的知识.在此基础上利用数据立方体相邻层次单元间的相关性对基本的搜索算法进行了改进,在保证准确性的基础上提高了搜索效率.在真实网络安全数据集上的实验验证了所提方法的有效性.     

QAR数据多维子序列的相似性搜索

QAR数据的高维度以及维度之间不确定的相互关联性,使得原有低维空间上度量时间序列的相似性的方法不再适用,另一方面由于民航行业的特殊性,利用QAR数据进行相似性搜索来确定飞行故障,对相似性的定义也有特殊的要求。通过专家经验结合一种层次分析算法来确定飞行故障所关联的属性维度的重要性,对QAR数据的多维子序列进行符号化表示,并利用k-d树的特殊性质建立索引,使QAR数据多维子序列的快速相似性搜索成为可能,结合形状和距离对相似性进行定义和度量,实验证明查找速度快,准确度较为满意。     

基于WSTB的时间序列相似搜索算法

提出了基于WSTB（Weighted Shape To Bit-vector）的相似搜索方法，该方法在线性分段的基础上建立时问序列曲线箱，而且创立具有相似形状的时序子序列箱后建立相应的索引，对给定序列和相似序列距离的快速计算，并根据查询的时间序列的特征确定相应的权重，不需要逐个检查子序列箱内容就可以进行快速索引。WSTB方法避免了进行逐个距离比较而造成的巨大的计算量，从而明显地提高搜索效率。最后验证了方法的通用性和有效性。     

多元飞行数据的时间序列相似性搜索方法

针对多元时间序列搜索的实际特点，提出WSTB方法，以线性分段建立时间序列曲线箱。创立具有相似形状的时序子序列箱，建立相应的索引，对给定序列和相似序列距离的快速计算，根据查询的时间序列的特征确定相应的权重，不需要逐个检查子序列箱内容就可以进行快速索引。采用实际飞行数据进行适应性验证，验证了该算法的通用性和有效性。     

基于二进制压缩的时间序列相似搜索

该文提出了一种基于二进制压缩(BC)的时间序列相似搜索的方法。该方法是把时间序列分段,提取每段上面的关键点把这些点转换成一个比特流,这些关键点是把每一段分成子段取这些子段的中间点,记录下比特流达到压缩的目的。该文证明了该方法在理论上具备非漏报的性质。然后使用天际线对时间序列进行索引。实验表明,该文提出的基于BC的方法比PAA方法有更小的边界,在相似度搜索的时候基于天际线索引的BC方法比基于R*树的PPA方法更有效率。     

基于形态特征的时间序列相似性搜索算法

时间序列相似性搜索是数据挖掘的一个重要基础性研究内容,它的相似性定义主要是基于欧氏距离,这类算法的缺点:如果时间序列产生偏移,会产生错误的结果.基于形态特征的时间序列相似性快速搜索算法,以界标为分界点,利用界标提取了时间序列的特征,将时序分为若干子序列,并对每个子序列进行线性化,将线性化后的子序列进行预处理;同样将查询序列进行基于界标的分段算法,然后利用一种改进的快速相似性搜索算法,可以快速地搜索到与查询序列相似的序列.?＃ 箅例表明了算法的有效性.     

基于时间序列的感知QoS的云服务组合

研究基于时间序列的感知QoS的云服务组合,将服务的QoS偏好随时间不断变化的过程纳入云服务组合的研究范围,将云服务组合建模成时间序列的相似度对比问题。分别用欧几里得距离和扩展Frobenius范数距离度量二维时间序列的相似度,继而用基于主成分分析的扩展Frobenius范数距离和欧几里得距离、Brute Force等方法度量多维时间序列的相似度,通过实验对比验证扩展Frobenius范数距离度量相似度在时间和准确性上的优越性。关     

基于非相似原理快速查找多个shapelets

shapelets是描述时间序列局部特征的子序列,它能最大程度对不同类别进行区分。从它的发明至今一直吸引着研究者的关注,但是由于过高的时间复杂度阻碍了它被广泛应用。一种快速查找多个shapelets的方法（Non-Similar Discover of Shapelet,NSDS）被提出：基于shapelets非相似的特性,根据子序列间距离分布设置一个距离阈值,以此过滤掉候选集中的相似子序列。再使用类可分离性作为过滤后的候选子序列的评价标准,最终选择出性能最好的多个shapelets。通过在单变量时间序列数据集上的实验表明了该方法可以极大缩短查找shapelets时间,而且能保持较高的分类准确性。将该方法扩展到多变量时间序列,对多个变量采用组合分类器的方法来提高整体分类的准确率。     

一种基于关键点的SAX改进算法

SAX(symbolic aggregate approximation)是一种符号化的时间序列相似性度量方法,该方法在对时间序列划分时,采用了PAA算法的均值划分,但均分点无法有效描述序列的形态变化,导致序列间对应分段均值相似的情况下,SAX无法有效区分序列之间的相似度.在SAX算法的基础上,提出了基于关键点的SAX改进算法(KP_SAX),该算法的相似性度量公式既可描述时间序列自身数值变化的统计规律,又可描述时间序列形态变化.实验结果表明:KP_SAX虽然部分提高了算法的复杂度,但可在SAX算法无法计算序列相似度的情况下,有效计算各序列间的相似度距离,达到了改进的目的.     

MapReduce并行加速数据流多模式相似性搜索

设计时间序列数据在Hadoop分布式文件系统（HDFS）中的有效存储方式,利用分布式缓存工具Distributed Cache将各子序列分发到Hadoop集群的计算节点上,将动态时间弯曲距离矩阵划分成多个子矩阵,采取并行迭代计算每条反对角线上子矩阵的方法,基于MapReduce编程模型,实现高效并行计算时间序列动态弯曲距离,通过改进剪裁冗余计算方法,设计实现一种数据流多模式相似性搜索并行算法。中国雪深长时间序列数据集的实验结果表明,当每条时间序列的长度达到5000以上时,并行计算动态弯曲距离所需时间少于串行计算所需时间,当每条时间序列的长度达到9000以上时,参与计算的集群节点越多,并行计算所需时间越少;当模式长度达到4000、参与计算的集群节点数达5个以上时,从数据流中并行搜索出与模式匹配的相似子序列所需时间约为串行搜索所需时间的20%。     

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

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

HierarchyScan: A Hierarchical Algorithm for Similarity Search in Databases Consisting of Long Sequences

In this paper, a hierarchical algorithm, HierarchyScan, is proposed to efficiently locate one-dimensional subsequences within a collection of sequences with arbitrary length. The proposed algorithm performs correlation between the stored sequences and the template pattern in the transformed domain to identify subsequences in a scale- and phase-independent fashion. This is in contrast to those approaches based on the computation of Euclidean distance in the transformed domain. In the proposed hierarchical algorithm, the transformed domain representation of each original sequence is divided into multiple groups of coefficients. The matching is performed hierarchically from the group with the greatest filtering capability to the group with the lowest filtering capability. Only those subsequences whose maximum correlation value is higher than a predefined threshold will be selected for additional screening. This approach is compared to the sequential scanning and an order-of-magnitude speedup is observed.     

3-D curve matching using splines

A machine vision algorithm to find the longest common subcurve of two 3-D curves is presented. The curves are represented by splines fitted through sequences of sample points extracted from dense range data. The approximated 3-D curves are transformed into 1-D numerical strings of rotation and translation invariant shape signatures, based on a multiresolution representation of the curvature and torsion values of the space curves. The shape signature strings are matched using an efficient hashing technique that finds longest matching substrings. The results of the string matching stage are later verified by a robust, least-squares, 3-D curve matching technique, which also recovers the Euclidean transformation between the curves being matched. This algorithm is of average complexity O(n) where n is the number of the sample points on the two curves. The algorithm has applications in assembly and object recognition tasks. Results of assembly experiments are included.     

电子中介中的多属性匹配研究

研究了电子中介处理个人之间单件物品交易时的多属性匹配问题。建立了多目标匹配模型,推导了用理想点法求解该模型时,求解其一次距离最小等价于求解原各目标相应系数直接相加所得的单目标指派问题。用有指导随机搜索算法求解了距理想点的二次距离最小。仿真实验表明,变量规模小于65时可以求二次距离最小并得到满意解;而大于65时求一次距离最小更为合适。     

Training feedforward neural networks using multi-verse optimizer for binary classification problems

Discovering approximately recurrent motifs (ARMs) in timeseries is an active area of research in data mining. Exact motif discovery is defined as the problem of efficiently finding the most similar pairs of timeseries subsequences and can be used as a basis for discovering ARMs. The most efficient algorithm for solving this problem is the MK algorithm which was designed to find a single pair of timeseries subsequences with maximum similarity at a known length. This paper provides three extensions of the MK algorithm that allow it to find the top K similar subsequences at multiple lengths using both the Euclidean distance metric and scale invariant normalized version of it. The proposed algorithms are then applied to both synthetic data and real-world data with a focus on discovery of ARMs in human motion trajectories.     

近似欧氏距离变换的一种并行算法

提出了一种基于超大规模集成电路(VLSI)硬件结构的新型距离变换并行处理算法。距离变换是一种基于二值图像的全局操作，在骨架抽取、形状匹配、目标重建、机器人避障等图像分析与模式识别算法中有着广泛的应用。欧氏距离是精确的L2范数距离，但是由于欧氏距离的非线性，不利于各种并行算法和加速算法的设计与实现，因此在应用中各种变形的加权距离作为欧氏距离的近似得到了实际推广。本文算法是有别于传统近似欧氏距离的并行计算方法，可应用于传统IC硬件或数字信号处理芯片(DSP)。理论分析和实验结果表明，该方法具有算法简单、快速、误差小等特点，可以更好地近似欧氏距离，并同时得到图像的Voronoi图，是一种实际可行的升级算法。     

基于标准化欧式距离的双向特征匹配算法研究

基于特征的匹配算法是图像配准的重要内容,针对传统SIFT匹配法存在的重复匹配、多对一匹配、正确率不高等问题,本文提出了基于标准化欧式距离的双向特征匹配算法。该算法首先通过SIFT算法对特征点进行提取,然后用标准化欧氏距离对特征描述符进行度量,接着采用双向特征匹配算法对特征点进行匹配,最后以RANSAC算法对匹配对进行提纯。实验结果表明,使用标准化欧氏距离进行双向匹配,具有更高的准确率。     

Distance maps from unthresholded magnitudes

A straightforward algorithm that computes distance maps from unthresholded magnitudes is presented, suitable for still images and video sequences. While results on binary images are similar to classic Euclidean Distance Transforms, the proposed approach does not require a binarization step. Thus, no thresholds are needed and no information is lost in intermediate classification stages. Experiments include the evaluation of spatial and temporal coherence of distance map values, showing better results in both measurements than those obtained with Sobel or Deriche gradients and classic chessboard distance transforms.     

基于围线扫描的快速完全欧氏距离变换算法

欧几里德距离变换（EDT）是为由黑白像素构成的二值图像中所有像素找到距离其最近的黑色像素,并计算它们之间的欧几里德距离,目前广泛地应用于图像分析和计算机视觉等领域.本文采用基于围线扫描的思想,提出了一个在二值图像中进行完全欧氏距离变换的算法.算法首先将二值图像中的像素进行分类,对那些本身既不是特征像素且其4-邻域内也没有特征像素的点作上标记,然后对这些标记的像素自内向外进行围线扫描,搜索与它最近的黑点并计算它们的欧氏距离.算法能够计算精确的欧氏距离.同时对算法的时间复杂度进行了简单的分析,并给出了程序实现中得到的一些实验数据,结果表明该算法运算速度快,时空需求在当前的硬件环境下令人满意,是一种有效的和有着巨大实际应用价值的距离变换算法.     

特殊区域的无线传感网络布点优化算法

通过讨论无线传感网络中节点传感距离与通信距离间的特殊关系,针对封闭、半封闭空间等特殊形状的区域进行布点方案研究,提出一种以尽可能少的节点且满足覆盖性和联通性的优化布点算法.分析、计算节点在不同传感距离与通信范围下,相邻传感器覆盖的最大有效范围,并考虑区域边界和障碍的复杂性,结合EMST算法保证全局通信.基于MATAB的仿真结果表明:该算法能在最少节点要求下保证整个区域的覆盖和网络的通信.