利用用户交互的相似水文过程搜索方法

摘要

本发明公开一种利用用户交互的相似水文过程搜索方法，以带权重的欧式距离作为相似度量，对用户指定的查询序列进行相似搜索，用户对查询结果进行标注，根据用户对查询序列模式的理解，对查询结果设置相似或不相似程度；算法将相似和不相似的序列特征进行合并，并调整权重，产生更加符合用户要求的查询序列，并循环进行查询，直到用户结束查询过程。本发明利用用户交互调整查询序列和权重，提高查询的准确性以及水文序列相似搜索的准确性。

说明书

技术领域

本发明涉及信息处理技术，具体涉及一种利用用户交互的相似水文过程搜索 方法。

背景技术

时间序列相似性查找就是在时间序列数据库中查找和发现与给定模式相似 的时间序列，查找相似子序列的过程在实际问题中经常遇到，例如，在人类的基 因组计划中，从DNA基因序列中查找出与给定的基因片段相似的子片段，根据 遗传的相似性进行研究；根据各种商品的销售记录，找出具有相似的商品销售模 式，根据相似产品的销售模式来制定相似的销售策略等；找出自然灾害发生的相 同前兆，从而对预报自然灾害进行决策研究；在水文领域，找出与当前洪水过程 相似的历史洪水过程，回答防汛指挥中经常会想到的“当前水文过程与历史上哪 一时期的水文过程类似”等问题。

相似性搜索在1993年由R.Agrawal首次提出，他是时间序列预测、分类、 聚类以及序列模式挖掘等等的重要基础。时间序列相似性查找与传统的精确查询 不同，由于时间序列在数值上具有连续性以及有不同的噪声影响，因此，大部分 情况下不需要时间序列很精确匹配。另一方面是时间序列相似性查询不是针对时 间序列中的某个具体的数值，而根据给定的查询序列来找查找是在一段时间内具 有相似形态特征和变化趋势的时间序列。在时间序列相似性搜索中，需解决的问 题包括时间序列特征提取、时间序列索引以及相似度量等。针对相似度量，研究 人员提出了各种度量方法，如欧氏距离及其基于Lp准则的变种、动态时间弯曲 距离(Dynamic Time Warping，DTW)、编辑距离(Edit Distance,ED)、模式 距离(Pattern Distance,PD)以及最长公共子串(Longest Common Subsequence, LCSS)等。

目前时间序列相似性搜索主要关注于找到适合具体数据特征的特征提取方 法，以及相应领域的相似度量方法。然而，由于“相似”是用户对序列的一种语 义认知，而特征以及相似度量都是基于序列底层的数据，这两者之间存在一定的 差异。因此，找到一种不变的特征提取方法和相似度量方法来适应所有用户对某 时间序列的“相似”的认知是困难的。

相关反馈的策略就是让用户参与到相似查询过程中，让用户对每次的查询结 果进行调整和标注，系统通过搜集用户对结果的调整和标注，从而调整特征提取 或者相似度量的方法，以学习用户对序列相似的语义认知，直到用户满意或放弃 查询。相关反馈最早被用在基于内容的图像检索中，将图像看做高维空间的矢量 是从图像中提取的颜色、纹理、形状等底层特征或者它们的组合，Rⁿ通常被称为特征空间。在特征空间上可以定义矢量间的距离函数以衡量图像之间 的差异。由于特定特征空间中的距离并不能反映不同人对不同图像的感受的差 异，采用固定特征提取以及距离函数衡量图像间的相似程度在图像检索中往往不 能得到满意的结果。为改善查询结果，可以通过改变特征空间、改变距离的计算 方法以及相似度的衡量公式等使相似度更接近于人的感受，相关反馈技术便是通 过与用户交互得到以上目标。在时间序列的相似搜索方面，1998年，Eamonn J.Keogh等提出一个基于相关反馈的时间序列探索框架，并能够分类和聚类，时 间序列采用带权重的逐段线性拟合(PLR)方式描述，每段拥有一个描述该段重 要性的权重，在检索过程中通过用户的交互修正权重，但是PLR计算复杂度较 高，同时在计算两个子序列之间距离时，还需要进一步进行分割对齐，同时PLR 描述不能进行有效的索引。2002年，郑斌祥等利用离散傅里叶变换对时间序列 进行降维，并利用R树建立索引进行相似检索，用户对结果序列进行标注，并 给出每个结果序列的重要度，新的查询序列为旧查询序列和所有结果序列以重要 度为系数的线性组合，该方法不能考虑序列不同部分的重要程度，一般一段时间 序列隐含的模式往往由序列的一部分决定，而其他部分对序列的模式的影响相对 较小。

发明内容

发明目的：本发明的目的在于解决现有技术中存在的不足，提供一种提高水 文时间序列相似性分析准确率的利用用户交互的相似水文过程搜索方法，本发明 以带权重的欧式距离作为相似度量，对用户指定的查询序列进行相似搜索，用户 对查询结果进行标注，根据用户对查询序列模式的理解，对查询结果设置相似或 不相似程度；算法将相似和不相似的序列特征进行合并，并调整权重，产生更加 符合用户要求的查询序列，并循环进行查询，直到用户结束查询过程。。

技术方案：本发明的一种利用用户交互的相似水文过程搜索方法，包括以下 步骤：

(1)对水文过程时间序列(如洪水水位过程等)进行小波变换，并进行重 构形成小波水文时间序列，初步过滤掉时间序列中存在的噪声数据；

(2)采用滑动窗口从小波水文序列中提取子序列；

(3)采用分段聚集近似法(Piecewise Aggregate Approximation，即PAA) 对步骤(2)所得子序列进行降维；

(4)采用空间索引方法(如，R*-tree等)对步骤(3)中生成的子序列创 建索引；

(5)对初始查询序列采用步骤(3)中的分段聚集近似法进行降维处理；

(6)进行k-近邻查询，并将查询结果按照与查询序列的相似程度高低排序 展示给用户；

(7)若用户对查询结果满意，则本次查询结果；否则，用户对查询结果进 行标注，识别出相似序列和不相似序列，并设置相似程度的高度，以及不相似程 度的高低；

(8)系统获取用户标注的信息，进行反馈处理，利用用户对结果的重新标 注，计算出新的查询序列，并转至步骤(5)。

进一步的，所述步骤(1)中，水文过程时间序列为以为时间序列，且过滤 时间序列中的噪声数据的具体步骤为：

(11)将水文过程时间序列进行小波分解；

(12)采用高频系数的阈值量化，即确定小波变换的尺度；

(13)重构形成小波水文时间序列。

进一步的，所述步骤(3)中对子序列进行降维处理的具体过程为：

将步骤(2)所得的子序列分成N段，每段的最终取值为该段内包含的数据 项的均值；一个长度为m的子序列，通过分段聚集近似法处理后，被描述成N 维空间中的一个点，对应的向量为的第i个元素为：

${\bar{x}}_i=\frac{N}{m}\underset{j=m/N(i-1)+1}{\overset{(m/N)i}{\Sigma }}{x}_j,1\le i\le N$

上式中，子序列的段数N任意设置，每段包含的点数为

进一步的，所述步骤(2)中，采用长度为w的滑动窗口沿小波水文序列按 照步长为1进行滑动，提取子序列，长度为n的小波水文序列总共提取子序列的 个数为n-w+1。其中，n是序列长度且大于零，w是子窗口长度且小于n。

进一步的，所述步骤(5)中，初始查询序列为任意长度，可以是从水文小 波序列中提取的任意一段，或者用户手绘的序列。

进一步的，所述步骤(7)中，用户对每个结果序列进行标注，给每个序列 设定一个影响值，以反映该结果和用户所期望的序列的相似程度。且用正数影响 值表示某个结果序列s与用户期望的序列是相似的，用负数影响值表示某个结果 序列s与用户期望的序列不相似，同时用户采用影响值的数值大小来描述相似和 不相似程度。

进一步的，所述步骤(7)中，在对结果序列进行相关反馈处理时，基于用 户设定的影响值进行线性组合；并且基于用户标注的多样性来调整权重，即用户 标注出与查询序列相似或不相似的序列

有益效果：与现有技术相比，本发明具有以下优点：

(1)本发明利用PAA对时间序列进行降维，在此基础提出带权重欧式距离 作为相似距离计算方法，利用用户交互调整查询序列和权重，反映序列不同部分 对用户所关心模式的重要程度，提高查询的准确性以及水文序列相似搜索的准确 性；

(2)本发明中，PAA体征提取计算方便，高效，同时能实现带权重的距离 度量；在索引下，本发明还能够实现任意长度的查询序列的kNN查询；对子序列 各部分的权重设置可以体现子序列各部分在模式中的重要性。

附图说明

图1为本发明的流程示意图；

图2为本发明中小波变换效果示意图；

图3为本发明中采用PAA对时间序列描述效果示意图；

图4为实施例中初始查询序列示意图；

图5为实施例中进行第一次查询的3NN序列示意图；

图6为实施例中新的查询序列示意图；

图7为实施例中新的查询序列的3NN示意图。

其中，图2(a)为原始水文时间序列的示意图，图2(b)bior小波4层变换 及重构后的序列示意图，图4(a)为原始水位序列示意图，图4(b)为尺度为3 的小波分解及重构结果示意图，图4(c)为查询序列的PAA描述示意图。

具体实施方式

下面对本发明技术方案进行详细说明，但是本发明的保护范围不局限于所述 实施例。

如图1所示，本发明的一种利用用户交互的相似水文过程搜索方法，包括以 下步骤：首先使用离散小波变换对水文过程时间序列进行转换，然后进行重构， 过滤噪声；然后利用PAA对小波水文序列进行降维，并基于R*_tree建立索引；对 用户选定的查询序列各序列点设置权重，利用PAA提取特征；进行kNN查询，并 将查询结果按照相似程度高低展示给用户；用户根据主观判断对结果序列重新排 序，并设置相似程度和不相似程度；系统根据用户的标注信息，重新计算查询序 列，并调整查询序列各部分的权重，进行下一轮查询。

具体过程如下：

步骤101、水文过程时间序列是原始的描述水文过程的一维时间序列，如洪 水水位过程等。

步骤102、对水文过程进行小波变换，并进行重构，形成小波水文时间序列， 初步过滤掉时间序列中存在的噪声数据。

水文序列过程的大部分时间点往往是不太重要的，少数时间中，监测值的变 化可能非常重要，如，洪水过程时间序列只在暴雨产生汇流形成洪水的一段时间 内能够体现流域的产汇流规律，而在洪水过程时间序列前后的大部分时间中，时 间序列一般是变化不大。同时在监测过程中，由于环境或设备的影响，可能出现 一些随机的噪声，这些会对相似查询产生误差。因此需要先对水文时间序列的噪 声进行过滤。

在本发明中，利用离散小波变换进行水文时间序列相似搜索具有以下优点： (1)局部特征，小波变换有无限基函数，可以捕捉到数据的局部特性；(2)多 分辨率分析，小波变换是分等级的对于不同的应用，可以方便地调整，随着尺度 的增加，形状越来越清晰；(3)效率高，小波变换算法的执行速度非常快，时间 复杂度为O(n)(n为序列长度)。离散小波变换可以进行多分辨率变换，对于不同 的应用，可以方便调整。小波变换将原始信号x变换成小波系数y，y＝[ya,yd]， 其中包括近似(approximation)系数ya与细节(detail)系数yd，一般称ya为低频信 号，是时间序列的趋势成分和周期等确定的部分，而yd为高频信号，表现出细 节的变化，并含有随机成分和噪声。在重构时间将细节系数yd设置为0，则可 以过滤掉噪声。

本发明中，利用一维小波进行时间序列消噪的一般步骤为：(1)进行时间序 列小波分解；(2)高频系数的阀值量化；(3)一维小波的重构。其中，高频系数 的阀值量化，即确定小波变换的尺度，指将部分细节系数设置为0，这样在重构 时，可以去掉细节部分，从而达到过滤噪声的效果。重构后的序列长度与原始时 间序列长度相同。如图2所示，某水位序列经过4层bior小波变换后，序列的 整体特征被很好地保留。

步骤103、对小波水文时间序列利用PAA进行降维，包括两个部分：首先 提取子序列，然后对子序列进行特征提取，实现降维。具体过程如下：

(1)提取子序列。本发明采用滑动窗口提取子序列，假设小波水文序列的 长度为n，选择长度为m的滑动窗口，沿着小波水文序列按照步长1滑动，总共 可以提取出n-m+1个子序列。

(2)PAA降维。PAA降维将子序列分成N段，每段的最终取值为该段内包 含的数据项的均值。一个长度为m的子序列,通过PAA处理后，被描述成N维空 间中的一个点，对应的向量为的第i个元素为${\bar{x}}_i=\frac{N}{m}\underset{j=m/N(i-1)+1}{\overset{(m/N)i}{\Sigma }}{x}_j.$

如图3所示，为采用PAA对时间序列X进行描述后，得到的新序列X’。

采用PAA进行特征提取时，子序列的段数N由用户自己设定，每段包含的 点数为N越小，则每段包含的点数越多，近似程度越高，特征空间维度越 低，则索引效率越高，但是在进行kNN查询时，会产生更多的侯选集，降低后 处理阶段的性能；N越大，则特征序列越接近原始序列，特征空间维度越高，降 低索引的效率。其中，若m不是N的整数倍，则在最后一段中包含剩余的点。

步骤104、利用R*_tree对步骤3创建的特征空间中的点进行索引。

步骤105、初始查询序列为用户指定的一个子序列。可以使用户手工绘制的 一个序列，或者从小波水文序列中截取的一段序列，或者从其他来源获取的子序 列。查询序列的长度可以是任意长度。

步骤106、对初始查询序列进行小波变换和重构，其详细过程与步骤2一致。

步骤107、对初始查询序列进行PAA处理时，每段包含数据点数与步骤2 相同，若查询序列长度不是的整数倍，则最后一段包含的点可能变少

步骤108、k-近邻查询。查询当前查询序列的k近邻，本发明采用带权重的 欧式距离来度量序列之间的相似程度，假设一个查询序列描述为{X＝x₁,...,x_n， W＝w₁,...,w_n}，其中W为X中对应元素的权重，则带权重的欧式距离度量DW 为：

$\mathrm{DW}\left(\right[W,W],Y)=\sqrt{\underset{i=1}{\overset{n}{\Sigma }}{w}_i{(x_i-y_i)}^2}$

假设PAA分段数为N，PAA对序列变换后，每个段的权重为：

${\bar{w}}_i=\min (w_{(n/N)(i-1)+1},...,w_{(n/N)i})$

即每段的权重是其包含的所有数据点的权重最小值。PAA特征提取后的欧 式距离为：

$\mathrm{DRW}\left(\right[\bar{X},\bar{W}],\bar{Y})=\sqrt{\frac{n}{N}}\sqrt{\underset{i=1}{\overset{N}{\Sigma }}{w}_i{(x_i-y_i)}^2}$

DRW和DW满足以下不等式，因此基于PAA进行索引和kNN查询不会漏 掉相似序列。

$\mathrm{DRW}\left(\right[\bar{X},\bar{W}],\bar{Y})\le \mathrm{DW}\left(\right[X,W],Y)$

步骤109、用户标注。用户对查询结果进行调整，将查询返回的kNN分成 相似和不相似序列。针对相似的序列，按照结果序列和用户期望的序列之间的相 似程度，设置一个影响值，数值大小关系他们的相关程度的大小。比如，若要表 示一个序列A比序列B与用户期望的序列相似2倍，则可以给序列A设置1，B 序列设置1/2，或者给A设置2，给B设置1。给不相关的序列，按照其与用户 期望的序列的不相似程度设置负影响值。所有的影响值大小不限，但是相互之间 的大小关系要能够体现相似，不相似程度的大小关系。

步骤110、反馈处理。对用户的标注进行反馈处理，得到新的查询序列，并 调整新序列每个部分的权重。假设查询序列为Q_old,结果序列为S₁,S₂,...,S_i,每个序 列对应的影响值为I_old,I₁,I₂,…,I_i，则新序列为

Q_new＝(Q_old*I_old+S₁*I₁+S₂*I₂+…+S_i*I_i)/(I_old+I₁+I₂+I_i)

在对权重进行调整时，采用两两合并的方式：将两个分别带有影响值I_A和 I_B的序列A和B进行合并，合并产生新序列C的过程merge：

d＝DW(A,B)

if(I_A*I_B<0)then

sign＝-1

else

sign＝1

for i＝1to m

d_i＝DW(A_i,B_i)

C_wi＝wi*(1+sign/(1+d_i/d))

end for

C_wi＝normalize(C_wi)

normalize将C_w各项和规范到1，即：

对查询结果进行合并，实现权重调整时，采用merge(…merge(merge([Q_old,I _Qold],[S₁,I₁]),[S₂,I₂]),…,[S_i,I_i])的调用顺序得到W_Qnew。

步骤111、新的查询序列，即为步骤110产生的[Q_new,W_Qnew]。后继的查询， 需要先转步骤107，对新查询序列进行PAA提取特征，然后,转步骤108进行 kNN查询。

实施例：

本实施例对太湖流域进行日均水位序列相似查询，该水位数据包含1955 年至2005年的日均水位。对所有日均水位数据进行尺度为4的bior小波变换， 然后采用滑动窗口提取宽度为60的子序列，并利用PAA提取特征，每个子序 列的段数设定为10，采用R*_tree建立索引。

选择一段长度为60的水位序列作为查询序列，如图4(a)所示；选取尺度 为4时进行小波分解，然后重构，如图4(b)所示；PAA特征提取后的查询序 列，如图4(c)所示。

第一次查询结果如图5所示。经过用户标注，系统对结果进行合并，得到新 的查询序列，如图6所示。利用新的查询序列得到的3NN，如图7所示。