摘 要

相似性比对是全面评估两者之间相似性的一种比较。两者越接近，则它们的相似性越大，两者越疏离，则它们的相似性就越小。相似性度量的方法种类繁多，这些方法有各自的适用范围，也有其局限性，一般根据实际问题进行选用。

本文介绍了几种经典的基于距离的相似性度量函数算法，讨论了这些算法的特点，并选择针对夹角余弦相似性度量的不足，提出了改进方案。而且对几个不同的一维信号进行了相似性度量的分析，分别采用了几种不同的算法进行比较，结果显示，改进后的夹角余弦具有更大的优越性，算法的准确度能够满足需求。

关键词：相似性比对；夹角余弦；改进算法

Abstract

The similarity comparison is a comparison that comprehensively assesses the similarity between two things. The closer the two things are, the more similar they are, and the more alienated the two things, the smaller their similarity. The similarity measure has a wide variety of methods. These methods have their own scope of application and their limitations. Generally, they are selected according to actual problems.

This paper introduces several classical distance-based similarity measure function algorithms, discusses the characteristics of these algorithms, and chooses the deficiencies for the angle cosine similarity measure, and proposes an improved scheme. Moreover, several similar one-dimensional signals are analyzed by similarity metrics, and several different algorithms are used for comparison. The results show that the improved angle cosine has greater advantages, and the accuracy of the algorithm can meet the demand.

Key words: Similarity comparison; angle cosine; improved algorithm

目 录

第1章 绪论 1

1.1 研究背景及意义 1

1.1.1研究背景 1

1.1.2相似性度量的研究现状 2

1.2研究内容及目标 4

1.2.1本文主要工作 4

1.2.2论文组织结构 4

第2章 信号相似性比对的关键问题 5

2.1信号的分类与描述方法 5

2.1.1信号的时域和频域描述 6

2.1.2时间序列信号 6

2.2特征的提取与选择 8

2.3信号相似性分析要解决的问题 9

第3章 相似性度量 10

3.1常见的相似性度量 10

3.2基于特征的相似性度量 17

3.3基于模型的相似性度量 17

第4章 基于夹角余弦的加权算法研究 18

4.1相关定义 18

4.1.1时间序列的分段线性表示 18

4.1.2时间序列加权角度表示 19

4.2基于夹角余弦的加权算法研究 20

4.2.1算法描述 20

4.2.2加权夹角余弦相似性度量 20

4.3实验结果与分析 21

4.4本章小结 22

4.4.1加权夹角余弦的优势 22

4.4.2存在的问题 22

第5章 总结 23

参考文献 24

致谢 25

第1章 绪论

1.1 研究背景及意义

1.1.1 研究背景

信号的相似性在海量数据挖掘、信号处理和图像处理等诸多领域有着极为广泛的应用。将一个信号或图像与另一个信号或图像进行比较，也可以计算一个样本与模板的相似程度，随后可以根据结果判断此样本与哪个模板最相似，从而对样本进行分类。除此之外，许多基本的处理操作，例如匹配滤波，互相关和波束形成，可以被解释为基于相似性的度量。这些相关操作通常被看作半自动传感器系统中采用的检测，定位，分类，关联和配准算法的基础^[1]。

相似性度量通常用于比较一些图像、形状、数据集、一维信号以及多维信号等方面相似性的一个函数。在特征匹配、信息检索、图像配准、数据挖掘、卫星遥感、计算机视觉以及天气预报等领域，相似性度量有着基本但却非常重要的作用^[2]。例如，近年来，随着数据不断丰富，各行各业都产生了许多数据，人们对功能强大的分析工具的需求逐步上升，数据挖掘开始得到广泛应用。在数据挖掘中，如果想要对数据进行聚类,邻域搜索这样的算法，必不可少的一步就是进行相似度分析。同样，在模式识别领域中，为了判断待分类样品与哪个模式的模版匹配程度更好，首先应该做的工作就是计算样品与样品之间或者模式类与模式类之间的相似程度；在医学方面，各种生物信号如心电信号、脉搏信号、呼吸信号等生命活动的信号处理上，关键问题也是形容和分析信号之间的相似程度。由此可见相似性的度量问题的比较研究可以为很多实际应用中的相似性度量方法的选择提供重要的依据。

相似性度量函数的研究可谓已经非常成熟，现有的相似性度量方法就有许多种。由于基于距离的相似度比较简单直观易操作，所以很多研究者在选择度量函数时，会优先考虑基于距离的度量方案，这种基于距离的方案也是使用较多的度量方法。顾名思义，就是通过计算两个样本之间的距离来衡量他们之间的相似程度。通常的结论是，距离越小说明两样品相似性越大,反之则相似性越小。距离度量方法中应用最广的有欧氏距离、马氏距离、闵可夫斯基距离、相关系数、动态时间弯曲距离等。

1.1.2 相似性度量的研究现状

相似性度量一般是用距离度量或角度度量。由于基于距离的相似度比较简单直观易操作，所以很多研究者在选择度量函数时，会优先考虑基于距离的度量方案。选择的基于距离的相似性度量函数一般可分为以下两种情况：其一是选择运用已有的距离函数，如欧氏距离、曼哈顿距离、相关系数、夹角余弦、动态时问弯曲距离等，这些方法的研究已经很深入了，有很多案例可以借鉴，也能够满足一般的简单需求，对一些复杂的数据可能不太使用。这时候就需要自定义一种距离度量公式。前者的理论更加成熟，应用领域较广，简单而且有效；后者是研究者针对某一特殊范畴，针对此领域数据或信息独有的特点，现有的算法不能得到很好的效果，所以只能优化已有的度量方法使结果拥有更高的可信度，再推广到此领域广泛使用通过优化已有的度量方法来提高相似性分析的准确性，具有较强的专业性。除此之外，还有很多因素会对度量结果产生影响。例如时间序列特别容易受到噪声影响而发生波动，由此会造成振幅的平移和伸缩、时间轴的伸缩和弯曲、线性漂移、不连续性等等，会使得原本相似的时间序列呈现出多种变形^[3]。选择相似性度量函数或自定义的度量函数应该尽量使结果具有较强的可靠性，尽量减小序列变形的影响，保证度量结果的准确性。

距离度量函数的显著优点就是计算比较简单，直观上让人比较容易理解,复杂度较低,运行时的周期也比较短，能够很好地应用于相似性查询和聚类等问题中。然而距离函数最大的局限性就是它要求序列等长且时间点逐一对应，对很多噪声特别敏感，并且它也不支持时间序列的变形问题，因而很多学者在钻研后，对这种方法提出了很多改进和完善算法的方案，使准确性大大提高，适用性也更加广泛。以欧氏距离为例，有人提出了标准化的欧氏距离算法，该算法先对序列进行均值标准化，处理数据后再计算其欧氏距离^[4]。改进后的算法可以有效解决序列存在的振幅平移和伸缩问题。除此之外，Keogh等人提出了一种加权欧氏距离,并采集用户反馈过来的信息来进行权值的修正^[5]。Gavrilov等人则从另一个角度来进行考虑，提出先进行时间序列的分段归一化，再使用欧式距离计算其相似度^[6]。经过改进后的算法能够降低因为发生线性漂移给结果带来的不良影响。这些研究在某种程度上减轻了振幅形变和漂移对相似性度量结果带来的不利影响，但在解决时间轴的伸缩与弯曲的问题上，这些研究却毫无进展。

1994年，为了处理好序列的时间轴伸缩和弯曲问题，Bemdt和Clifford首先在时间序列的分类中引入了动态时间弯曲(DTW)的概念^[7]。这项成果对于研究者是一个重大的启发，此后，研究者做了大量的分类研究实验，实验结果表明，DTW在很多数据集上表现出了十分优越的性能。与简单距离算法相比，DTW的显著优点是：不要求序列等长且逐一对应。在处理位于时间轴弯曲部分的序列点时，能先对这部分点进行自我复制，再进行对齐匹配。由此很好地处理了时间轴的伸缩与弯曲序列的相似性度量问题。但DTW距离算法的缺陷也是显而易见的:算法比较复杂，不满足空间距离三角不等式的条件，也很容易受到噪音和孤立点的干扰，这些缺点都限制了动态时间弯曲方法还没有在现实中得到大量广泛的应用。

另一个常被应用于图像配准方面的是Hausdorff距离，Hausdorff距离与欧氏距离相比的优势是，在计算时间序列之间的相似度时，并不严格要求序列点之间是逐一对应的，它的局限性在于个别点的干扰会造成结果的波动比较大^[8]。时间序列有的时候会不连续，表现为在个别点有比较大的不同，但是其余的部分还是比较相似。例如序列X和序列Y非常的相似，但只要在序列X中存在某一点和Y的距离比较大，那么计算两者之间的Hausdorff距离时，就会发现结果非常大，与实际情况X和Y很相似并不符合，这对于相似性度量结果的准确性会造成一定的影响。

自定义的相似度计算方法通常是针对某一特定范围数据如医学中心的电信号，或者为解决特定实际问题而提出的，比如序列变形方面的问题。自定义距离度量方法时，通常同时也会定义特征提取的方法。如基于序列的趋势表示，董晓莉提出了形态距离，王达提出了趋势距离和模式距离^[9]；基于分段斜率表示，张建等人提出了斜率距离和动态模式匹配距离等等^[10]。

近年来，生物信息学和计算机理论研究的飞快进展，研究人员试图生物信息学和计算机理论中的压缩理论应用到时间序列相似性的研究中，提出了一个新的相似性度量方法，即关于压缩理论的相似性度量^[11]。基本思想是，如果想要对数据进行连接和压缩，那么在较相似的数据集上进行应该相对来说比较容易，在相差较大的数据集上进行应该容易的多就会困难很多，而且前者可以获得比后者更大的压缩比。在这个过程中，将压缩所得数据的程序的最短长度定义为Kolmogorov复杂度^[12]，研究者对其进行了比较深刻的研讨，在此基础上，Keogh等人定义了Compression-Based Dissimilarity Measure（CMD），并证明了CMD在聚类分析、异常检测等应用上的可行性与优越性^[13]。

1.2研究内容及目标

1.2.1本文主要工作

相似性度量方法的分析是对信号进行聚类等算法的基本步骤。本文旨在探究不同的相似性度量方法在两个信号的相似性研究上的优缺点。本文的基本内容是介绍几种基本的度量方法，陈述其原理记算法，并重点选择两种基于距离的相似性度量算法，欧氏距离，夹角余弦进行进一步的实验，将实验结果进行对比。在此基础上，提出一种基于夹角余弦的加权相似性度量算法，证明能够得到更精确的相似性度量的结果。

本文所做的主要工作如下：

1) 查找一些相似性度量方面的中英文文献，进行相关知识的学习，明确此次设计的目标及意义；

2) 对信号表示、相似性度量方法、各种算法优劣性进行综述，简要介绍当前国内外的研究背景，发现一些待完善的问题，在此基础上对相似性度量算法的未来研究趋势进行展望；

3) 针对夹角余弦的不足之处，提出一种基于夹角余弦的加权相似性度量算法，并证明其性能优于简单的夹角余弦；

4) 在信号相似性分析上应用度量算法，并分析结果。

1.2.2 论文组织结构

本论文分为五个部分，简述如下：

第1章：阐述课题的研究背景，介绍国内外的研究现状、当前研究的热点问题和一些未解决的问题，并对课题的研究内容和预期目标等进行综合性的阐述，并简要的说明论文的组织结构。

第2章：对信号的不同表示方式进行介绍，阐述信号相似性度量研究的关键问题。

第3章：对几种常用的算法及其特点进行介绍，并进行优劣性比较。

第4章：重点介绍夹角余弦方法在相似性度量上存在的缺陷，并提出改进措施，改进后的算法性能被证明优于夹角余弦。

第5章：对本文得到的结论进行说明，对全文主要工作进行总结，并探讨将来的学习方向。

第2章 信号相似性比对的关键问题

2.1信号的分类与描述方法

蕴含着信息，且能传递信息的物理量称之为信号，所以信息传递的载体就是信号。可根据不同的角度对信号进行分类。

确定性信号与非确定性信号。我们知道，某些信号可以被写作函数形式，例如表现为一个以时间为自变量的确定的函数，那么任意选取其中某一时刻，便能够得到此时刻的函数值，这种信号就是确定性信号。但是，由于采样和运输过程中可能被某些因素影响，实际理论研究中的信号往往带有随机性，不能用函数的形式表示出来，也就不能获取任意时刻的信号幅值，例如噪声信号，这种信号被称为非确定性信号。

离散信号与连续信号。按照时间函数中时间取值的不间断特性，信号又被分为连续信号与离散信号。如果在观测的时间区间内，除了一些有限个数的不连续点外，任意取一个时间点，都有一个确定的函数值与之相对应，那么这个信号即可划分为连续信号。与连续信号对应的是离散信号，离散信号通常为一系列离散的点。离散信号是离散的，只在一些离散时刻有函数值在，其他时刻值上并没有定义，例如采样信号。

周期信号与非周期信号。若某信号是确定性信号并且满足以下公式的信号则被称为周期信号

f(t) = f(t nT) n = 0 , ±1 , ±2......(任意整数) （2.1）

该关系式中的最小的T值，被称为信号的最小周期。可以看出来，周期信号在时间上都是无穷无尽的，并且具有周而复始的特征。只需获得某一个信号在随意一个周期内的变更过程，便可确定这个信号在任意时刻的状态。而非周期信号不满足式（2.1），不具有周期重复性，因此研究非周期信号的特性就比周期信号的研究复杂一些。

一维信号与多维信号。从表达式上来说，信号的函数变量的表达能够只有一个，也能够有许多个，根据变量个数是一个还是多个将信号分为一维信号和多维信号。一维信号的典型例子就是语音信号，声音可以表示为声压以频率为变量的函数。一张黑白图像中的每一个点拥有不同的光强度，其中每个点都是二维坐标系中两个变量的函数，就是二维信号。实际上，还可以呈现更多维数变量的信号，例如电磁波在三维空间的传播，同时考虑时间变量而构成四维信号。

除上述划分方式外，还可将信号分为时域信号和频域信号，有限信号与无限信号等。

2.1.1信号的时域和频域描述

信号有三种基本的表达方式，函数表达式、波形图、以及频谱表示。在这三种表达方法中，能够较直观表达出信号状态的是函数表达式。其中最基本的是以时间为自变量的函数表达式，它体现的是信号的幅值随着时间变动的过程。

频谱是将时域表达的信号变换到频域中，可以将复杂的时间过程分解成若干谐波分量的形式。可以采用傅里叶分析的方法来衔接时域和频域。傅里叶分析是先把时域信号x(t)经过傅里叶变换后变为频域信号X(f)，然后在频域中研究此信号。其中X(f)叫做信号的频谱，表示的是在不同频率分量处信号成分的大小。频域分析时，作为独立变量来参与分析的是信号的角频率或频率，分析信号的相位和幅值随频率变化的特点。在频域中能够观察到信号的组成成分。对信号进行分析时，频域分析的显著优势是，能够提供的信息相比于时域信号波形包含的信息更丰富直观。

时域分析与频域分析可以分别从两个不一样的领域对信号进行分析和处理。时域分析的目的是观察时间与动态信号的关系，频域分析的任务则是观察频率与信号的关系。信号在时域中的表现比较直观容易理解，频域分析则更加深刻，比较适合做深入的研究。目前，信号的分析重心在渐渐从时域向频域在转移。但是它们之间仍具有彼此相互联系和不可分割的特点。

对于同一信号来说不管用哪种方法来描述，其信息量都是一样的。

2.1.2时间序列信号

现有的相似性度量算法的研究很多都是基于时间序列，当今时间序列的研究比较热门。并且对时间序列进行相似性的分析，对数据发掘中的聚类分析也比较大的益处。时间序列与其他信号的不同表现为：时间序列中的数据是依照时间先后排列的，同时其也包含着时间信息和数据信息。相邻时间对应的数据一般具有连贯性，时间序列一般也是有规律可循的，掌握时间序列的规律可以对以后的数据进行预测。

将某种现象某一个统计指标下观测的数据，按照其发生的时间先后顺序排列成一个有序的数列，这个数列就被称作时间序列^[14]。这类数据反映了这个事物或者现象等，当时间变化时，它们的状态或程度的改变过程。从工程技术到经济学，再从地理学到天文学，在各个领域中产生的数据都会以时间序列的形式存储。例如，股票市场的每日波动，某火车站每日的客流量序列，某销售公司的销售量的月度序列，某化学反应过程按小时观测的产量序列等。

一个时间序列通常被记为:

x={(x₀ , t₀) , (x₁ , t₁) , ... , (x_n , t_n) }

其中x_n是要记录的量的观测值， t_n 则是按时间顺序严格增加的，并且时间序列的采样间隔一般都是相同的，因此可以简记为x={x₀ , x₁ , ... , x_n }。