基于两点的时间序列相似性研究

目前,时间序列相似性判定大多采用欧式距离和动态时间弯曲DTW（DynamicTimeWar．ping）方法,这两种方法均存在一定缺陷。欧式距离要求序列长度一样,垂直移动序列将影响相似性判定和阈值设置的经验性;动态弯曲距离对欧式距离进行了优化,避免了欧式长度的一致性,但其他两个缺点仍然存在且计算复杂度增加。提出了一种新的基于两点时间序列相似性算法,可计算任意两序列的相似度。首先分析了两点组成的序列形态,提出了相似性判定方法TPSS（TwoPointsSegmentationSimilarity）;其次为提高相似性判定的鲁棒性,减少人为阈值设置的影响,对TPSS进行了拓展;最后给出了算法及实验分析。实验结果表明,该算法能很好地判定任意序列的相似性,提高了鲁棒性及减少人为干预,对数据挖掘中的聚类与预测有很好的帮助作用。     

基于小波和动态时间弯曲的时间序列相似匹配

提出了一种基于小波和动态时间弯曲(DTW)距离的时间序列索引和相似匹配方法. 该方法采用小波变换进行数据降维,利用R·-tree建立多维索引结构. 给出了查询序列的DTW距离边界和其在小波空间的查询超矩形的计算方法,从而将原始空间的基于DTW距离的相似匹配转换为小波空间基于欧氏距离的相似匹配. 证明了此匹配方法不会产生漏报,给出了基于DTW距离的范围查询算法和近邻查询算法. 实验结果表明该方法具有较高匹配精度和其较低的计算代价.     

面向动态时间弯曲距离的灰关联聚类方法研究

灰色关联聚类是灰色系统分析的重要研究领域.现有的灰关联聚类方法在处理不同长度序列数据时,通常采用补齐或删除数据方式进行处理,增加了系统的不确定性.在动态时间弯曲距离基础上,提出了一种新的灰关联聚类方法,通过计算序列间距离矩阵的最短路径来度量相似程度,最终完成序列的灰关联聚类.该方法无需对序列数据进行人工干预,具有更强的鲁棒性.实验结果表明,在处理不同长度数据序列时,聚类结果更为准确.     

基于RFID位置语义的室内移动轨迹聚类算法

面向室内空间的移动轨迹聚类有利于发现室内热点和用户移动模式.针对室内环境在定位技术、距离度量等方面的特殊性,充分考虑室内移动轨迹的空间和语义特征,提出一种基于无线射频识别(radio frequency identi-fication,RFID)位置语义的室内移动轨迹聚类方法.该方法对原始轨迹提取特征点,可简化轨迹以降低算法时间复杂度;从空间形状和位置语义2个方面加权计算轨迹相似度,其中,空间相似度通过定义适用于室内三维空间的距离函数来计算,语义相似度计算基于最长公共子序列思想,并引入移动对象在轨迹点的到达时间和停留时间;利用线性表存储轨迹相似度,采用改进的层次聚类方法对移动轨迹进行聚类.实验结果表明,该方法能够有效地进行室内轨迹聚类并具有较高的效率.     

一种飞行数据相似子序列查询方法

飞行数据是一种典型的时间序列数据,其存在随机噪声以及各种复杂变形,导致了相似子序列查询困难。为此,提出一种基于DTW病态匹配的飞行数据相似子序列查询方法。首先,利用已知的查询序列样本集构建上、下边界曲线,同时给出了相应的下界距离,并证明了其正确性。以此建立下界算法,用于筛选相似度高的子序列。其次,利用DTW距离搜索路径病态匹配来对筛选后的子序列无效序列段进行识别并去除,解决了子序列有效匹配长度难以确定的问题。仿真实验结果表明：该方法可以较为精确地查询出相似子序列,其起止时间偏差可以控制在3 s以下,满足飞机飞行动作查询的实际需求。     

水文时间序列的相似性搜索研究

将时间序列相似性搜索的数据挖掘方法应用于水文时间序列数据中,挖掘相似的水文过程.在分析欧氏距离和动态时间扭曲距离两种相似性距离度量方法特点的基础上,采用对时间轴的伸缩和弯曲具有较好适应性的动态时间扭曲距离法对塔里木河流域源流区出山口水文站沙里桂兰克站1961—2000年共220场洪水流量过程进行相似性搜索,基于相似性距离度量矩阵,挖掘出相似的洪水流量过程.结果表明,沙里桂兰克站洪水过程虽形态多样,但也表现出一定的相似性,基于动态时间扭曲法的相似性搜索能有效挖掘出相似的水文过程.     

基于形态拟合的时间序列距离计算

针对现有的距离度量方法度量准确度低且计算效率低的问题,提出了基于形态拟合的距离度量算法.该算法使用滑动聚集平均近似方法对序列进行分段降维处理,计算降维后的分段序列的动态弯曲路径,并计算处于动态弯曲路径上的分段序列之间的欧式距离,以所有分段序列的欧式距离的累积值作为最终的距离计算结果.实验表明基于形态拟合的距离度量算法具有度量准确度高且计算效率高的优点.     

基于OLAM的时态序列相似搜索研究

时间序列相似搜索是时间序列数据挖掘的一个重要功能,它所面临的最大问题是搜索空间过大、计算过于复杂。本文提出了基于OLAM体系架构的一种时间序列相似模式分层匹配方法。该方法首先利用对时间序列广义移动均值的聚类进行相似搜索的粗匹配,接着通过构造时间序列趋势的相似度,利用此用户对相似度的要求可以进行第二次筛选;最后通过对剩余的时间序列的距离计算,就可以获得最终相似的时间序列。实验分析表明该方法具有良好的性能和OLAM特征。     

Minwise Hash动态双重阈值过滤器

结合二项分布和小概率原理进行理论推导,提出了Minwise Hash的动态双重阈值过滤器,将比对过程划分为多个比对点,并设置各比对点的动态阈值,过滤相似度低于下界阈值TL(k)的文档,输出相似度高于上界阈值TU(k)的文档.该提前过滤的方法减少了后续的比对次数,降低了工作量,并设计了多组实验,结果显示过滤器在选取了适当的参数时,计算时间仅为原Minwise Hash的31%或原b位Minwise Hash的36%,较大地提升了原算法的时间效率.动态双重阈值过滤器不仅能应用于Minwise Hash,也能用于它的变种算法(如b位Minwise Hash),乃至所有符合二项分布的估计子.     

基于动态时间弯曲距离的城市干道交通流量信息分析方法

为研究城市干道间断流交通运行特征,采用动态时间弯曲距离作为相似性度量指标对城市干道交通流量信息进行分析。建立由数据预处理、动态时间弯曲距离计算、路径信息提取三步骤构成的干道流量信息相似性度量方法,应用实地观察数据,计算干道内不同检测点交通流量信息的相似性度量值,识别信息一致性良好的关键路径;比较同一路径内不同检测点交通流量信息的相似程度,检验信息的传递特征。该方法能自动区分城市干道系统内的关键路径与非关键路径,并反映交通流量信息传递过程中的衰减特征,用以确定干道信号协调控制的对象与范围。     

基于自动编码器的句子语义特征提取及相似度计算

句子特征提取与相似度计算是自然语言处理中的重要问题.目前汉语句子相似度计算方法不能全面考虑句子语义,因而导致相似度计算结果不够准确.提出了基于深层稀疏自动编码器的句子语义特征提取及相似度计算算法.首先将句子表示为高维、稀疏向量,进一步利用深度无监督学习句子非线性特征,即将高维、稀疏向量变换到低维、本质特征空间,此过程是一种更为纯粹的端到端的学习,避免了建立停用词表、分词等工作,最终得到可直接用于句子相似度计算的低维特征表示.实验结果表明,提取到的句子特征应用于句子相似度计算,与基于关系向量模型的句子相似度计算方法相比,提高了相似度计算准确率,计算的时间复杂度仅为O(n).     

周期为2~n的二元序列谱免疫度的算法

通过对周期序列谱免疫度的研究,提出了序列的0限制k错线性复杂度的概念。以Mark Stamp所提出的计算周期为2n的二元序列k错线性复杂度的算法为基础,设计了求周期为2n的二元序列0限制k错线性复杂度的算法1,并利用算法1提出了确定该二元序列谱免疫度的快速算法,该算法具有较高的计算效率,时间复杂度为O(n)。     

基于噪声特征的高精度脉冲相位估计方法

建立了脉冲相位估计模型,提出了加权非线性最小二乘方法,利用脉冲轮廓噪声的统计特征构造了最优加权矩阵,分析了提出方法的理论精度和计算复杂度,并与克拉美-罗下界进行比较.数值仿真和实验表明:提出的方法具有最小方差的渐近无偏估计,当观测时间较长时,该方法的性能优于非线性最小二乘方法,接近最大似然方法,但计算复杂度要明显低于最大似然方法.对于Crab脉冲星,当观测时间为80s时,该方法的距离估计误差比非线性最小二乘法小400m.     

布尔逻辑DNA序列比对系统的软件平台设计

针对目前基于动态规划的DNA序列全局比对算法时间复杂度较高,设计了一个DNA序列全局比对系统。该系统用FPGA进行序列的比对,并配备一个软件平台存储数据、发送命令以及发送和接收数据。测试数据表明,该系统的DNA序列比对时间在序列相似度较低情况下,为Needleman的42%;在序列相似度较高的情况下,为Needleman的6%。     

一种新的语义相似度计算方法

在信息检索领域,基于不精确的语义信息进行查询,需要用户多次进行筛选,降低了查询效率,因此,语义相似度计算的精确性至关重要.目前,人们主要利用概念词的距离、内容、属性等信息进行语义相似度计算,其中综合距离,信息内容和概念词属性等因素的混合式语义相似度计算方法是比较热门的方法,但该方法进行语义相似度计算时,权值的确定是根据专家的经验,人为的进行确定,具有一定的主观性,影响了语义相似度计算的准确性和客观性.因此,本文提出了一种新的混合式语义相似度计算方法,采用模糊优化的思想确定混合式语义相似度计算方法中的权值,避免了主观性,使语义相似度的计算更准确,查询结果更符合人们的需求.     

本体中概念间语义相似度和相关度混合计算方法

语义相似度计算广泛应用于自然语言处理中,但现有语义相似度计算方法没有充分挖掘本体结构中概念间的关系.笔者针对当前概念相似度计算的片面性和不完善性等不足,提出一种计算概念间语义相似度和相关度的混合方法.从有向边包含的特征属性对语义距离进行扩展,结合概念深度,将语义距离转换成语义相似度,通过引入概念间相关度计算,使最终概念语义相似度计算更加精确.并将该方法与人的主观判断结果进行比较,验证了该方法的可行性和有效性.     

弹性动作关联序列的模式检索

视频检索要求在数据库中能够找到与待检索视频序列相关的序列,该相关序列也可以是数据库中某个序列的部分序列,为此提出了一个动态编程方法.该方法综合了计算信息领域的编辑距离算法和信号处理领域的动态时间规整(DTW)算法,并克服了它们都不能直接用于动作检索的局限性,由于可以通过调节参数使所提方法转换为上述2种方法,所以可把它们看作是所提方法的特例.通过在不同数据库上的实验,以及和编辑距离算法和动态时间规整算法的比较,发现在相同的误检率条件下,所提算法的检测率要好于其他2种算法.     

一种增量式文本软聚类算法

针对传统文本聚类算法时间复杂度较高，而与距离无关的算法又不适用于动态、变化的文本集等问题，提出了一种基于语义序列的增量式文本软聚类算法．该算法考虑了长文本的多主题特性，并利用语义序列相似关系计算相似语义序列集合的覆盖度，同时将每次选择的具有最小熵重叠值的候选类作为一个结果聚类，这样在整个聚类的过程中大大减小了文本向量空间的维数，缩短了计算时间．由于所提算法的语义序列只与文本自身相关，所以它适用于增量式聚类．实验结果表明，算法的聚类精度高于同条件下的其他聚类算法，尤其适合于长文本集的软聚类．     

基于词法、句法和语义的句子相似度计算方法

为了解决现有句子相似度算法未考虑句子语义信息的问题,提出了一种基于词法、句法和语义的句子相似度计算方法.将句子相似度分为词法层、句法层、语义层3个层次.在词法层,通过构建句子的词汇相似度矩阵和数字序列相似度矩阵来计算词法相似度;在句法层,使用概念词汇转化成的RDF三元组相似度来计算句法相似度;在语义层,基于本体树状结构中最短路径表示的语义距离来计算语义相似度.然后,提出句子语义相似度计算模型,采集图书领域句子对作为测试集,构建图书领域本体作为知识源.实验结果表明,所提方法具有更高的准确率和召回率,其F-度量值达0.649 9,与余弦相似度算法、基于编辑距离的算法和基于TF-IDF的算法相比分别提高约12%、17%和16%.     

冒泡排序算法及其改进算法的实验分析

排序是计算机科学的基本问题之一.通过描述传统的、带标记的、双向的和交替排序四种冒泡排序算法,总结出它们的时间复杂度为O(n2)和空间复杂度为O(1).通过编程验证了四种排序算法在不同随机度情况下的性能,指出它们的适用原则:当随机度比较小时,应选取非传统冒泡排序算法;当随机度比较大时,则应选取传统冒泡排序算法.实验表明,四种算法的时间消耗与输入序列的规模近似地呈指数曲线关系,传统冒泡排序算法的时间消耗与输入序列随机度近似地呈水平直线关系,而其它三种算法的时间消耗与输入序列随机度呈40?左右的斜线关系.