基于动态时间弯曲距离的灰关联度量方法及其应用

张起荣，刘 歆

(1.毕节学院 信息工程学院，贵州 毕节 551700;2.重庆邮电大学 软件学院，重庆 400065)

0 引言

灰关联分析是不确定性知识获取的重要研究方法［1］，能够根据各因素之间发展趋势的相似或相异程度来衡量彼此的接近程度，是灰预测、灰建模、灰控制和灰决策的基础［1-3］，在多指标决策［4-5］、数据关联性度量［4-6］方面起着重要作用。

在灰关联分析研究中，灰关联度量方法是最为关键的研究内容。邓氏灰关联度(Deng-degree of incidence，DDI)［1］根据序列间的相对距离来衡量其关联程度，具有较好的整体性及规范性，但采样数据的质量、数据的极端分布及初始化算子的选择均会严重影响邓氏关联度的计算精度［4］。广义灰关联度(灰绝对关联度、灰相对关联度、灰综合关联度)［2］以曲线间的相交面积大小作为序列相似度的衡量标准，但当曲线上下波动时，会造成关联度结果与定性分析出现较大偏差。此外，广义灰关联度也不满足灰关联公理中的整体性规则［5］。基于相似性和接近性视角的灰色关联分析模型(grey incidence based on visualangle ofsimilarity and nearness，GIVASN)［4］分别从相似性和接近性2个不同视角测度序列之间的相互关系，构造了一类新的灰色关联分析模型，但仅适用于序列的意义、量纲完全相同的情形。基于信息还原算子的多指标区间灰数关联决策模型(grey incidence of information reduction operator，GI-IRO)［5］加入信息还原算子，有效地解决了一般区间灰数加减逆运算中存在的信息失真问题，但对序列存在的不完备问题依然未能解决。基于累积前景理论的多指标灰关联决策方法 (grey incidence of cumulative prospect theory，GI-CPT)［6］等根据累积前景理论和灰色关联分析定义了前景价值函数，以此构建方案综合前景值最大化的优化模型，最终以最优综合前景值对备选方案进行排序。但前景价值构建需要先验经验，分析要求较高［7-8］。

序列数据存在的不确定性是灰关联度量方法面临的最大难题，当序列数据长度不一致时尤为明显。当前的灰关联度量方法处理的序列数据长度必须相等，对于长度不同的序列则采用删除较长序列数据、均值、级比、GM(1，1)模型预测［1］等方法进行补齐，导致不确定性信息的进一步放大，造成不必要的信息损失。

在现有灰关联模型的研究基础上，本文将动态时间弯曲思想［9］引入灰关联度量中，提出了一种新的灰关联度量方法。该方法无需补齐序列数据，利用序列间距离矩阵的最短路径作为相似判定依据。在此基础上，进一步构建了相应的灰关联度量方法，有效解决了序列数据长度不一致问题。为了证明了方法的有效性，本文将其应用于分类算法中，取得了较为优异的仿真测试结果。

1 相关理论基础

1.1 灰关联分析与灰关联度

灰色关联分析是指对一个系统发展变化态势的定量描述和比较的方法［10-12］，通过灰色关联度来比较参考数据列和若干个比较数据列的几何形状相似程度，样本的数量及分布规律对灰色关联分析均无影响。灰关联度越大，则序列间发展方向和速率越接近，关系越紧密。在实际应用中，邓氏灰关联度和广义灰关联度是应用较为广泛的2种灰关联度。

定义1 邓氏灰关联度［1］。设 X0={x0(1)，x0(2)，…，x0(n)}为参考序列，Xi={xi(1)，xi(2)，…，xi(n)}，(1 ＜i≤m，m∈N)为比较序列，序列长度相同。则邓氏灰关联度可表示为

ρ为分辨系数，ρ∈［0，1］。

定义2 广义灰色关联度［2］。设序列Xi与Xj长度相同且皆为1时距序列［10］，XiD={xi(1)d，xi(2)d，…，xi(n)d}为原始序列经过序列算子D变换后生成的像序列，则广义灰色关联度定义为

根据采用数据初始算子的不同，广义灰关联度可分为灰色绝对关联度(始点零化算子)和灰色相对关联度(初值化算子)。

灰色关联度是灰色关联分析的基础，然而仔细分析定义1和定义2，无论是邓氏灰色关联度还是广义灰关联度，均不能处理序列长度不一致问题。当序列Xi与Xj长度不等时，必须进行补齐或者删除较长序列的过剩数据，很大程度上增加了系统的不确定性。

1.2 动态时间弯曲距离

动态时间弯曲(dynamic time warping，DTW)［9］方法由Berndt与Clifford于1994年引入到时序数据研究中，用于语音匹配及视觉模式识别领域。DTW通过弯曲时间轴，获得时间序列之间的最小距离，如图1所示。DTW不仅能够确定时间序列间中点的最佳对应关系，而且很好地解决了欧氏距离中难以处理一系列难题，如时间轴伸缩、弯曲和线性漂移等。目前，DTW已经广泛应用于医疗信号、生物数据分析和模式识别［13-14］等多个领域。

图1 动态时间弯曲路径Fig.1 Path of dynamic time warping

定义3 动态时间弯曲距离(dynamic time warping，DTW)［11］。给定时间序列 X={x1，x2，…，xn}与Y={y1，y2，…，ym}，则序列X与序列Y间的动态时间弯曲距离D(X，Y)=f(n，m)，其中，f(n，m)计算方法为

从本质上来说，DTW距离的实质是在序列间距离矩阵中，寻找一条从a11到anm的最小弯曲路径，如图1所示。

DTW距离反映了序列间的相似程度。DTW距离越小，则序列越相似，反之则越大。DTW方法可以解出任意长度的时间序列间的距离，满足正定性、对称性和三角不等性。

2 基于动态时间弯曲距离的灰关联度量方法

在DTW基础上，可构建基于动态时间弯曲距离的灰关联度量方法。

定义4 动态时间弯曲灰关联度(dynamic time warping degree of grey incidence，DTW Degree)。给定序列 Xi={xi(1)，xi(2)，…，xi(m)}与 Xj={xj(1)，xj(2)，…，xj(n)}，DTW(Xi，Xj)是序列 Xi和Xj间的动态时间弯曲距离，则2序列间的灰关联度定义为

(4)式中:1＜ti≤m，1＜tj≤n;ρ为分辨系数;λ为DTW(Xi，Xj)所对应的路径长度(由于DTW距离存在着弯曲路径长短的问题，故(4)式中对该距离进行了平均处理)。分辨系数ρ控制着系统对两级差的影响，一般来说，通常设置 ρ∈［0，1］，或ρ=0.5 。

从定义4可以看出，动态时间弯曲灰关联度对于序列长度没有强制要求，无论序列长度相等或不等均可以由序列间的距离矩阵计算两者的距离，从而进一步计算出相应的灰关联度，有效避免了人为补齐序列长度带来的未知性与不确定性。

为验证动态时间弯曲灰关联度的正确性，可从是否满足灰关联公理［1］进行证明。

1)规范性。记 Δ(Xi，Xj)=DTW(Xi，Xj)/λ ，因为 Δ(Xi，Xj)≥mmin mnin|xi(ti)－xj(tj)|，故0＜γ(Xi，Xj)≤1 。

2)整体性。由于动态时间弯曲灰关联度仅是序列Xi与Xj之间关联程度的度量，未考虑其他因素，故这里没有整体性的问题(类似于广义灰关联度)。

3)偶对对称性。由DTW距离性质可知DTW(Xi，Xj)=DTW(Xj，Xi)，故 γ(Xi，Xj)= γ(Xj，Xi)。

4)接近性。Δ(Xi，Xj)反映了序列Xi与Xj之间的距离，距离越小，则γ(Xi，Xj)越大，从而序列Xi与Xj越接近。

在动态时间弯曲灰关联度基础上，本文提出了一种自适应序列长度灰关联度量方法。

算法1 基于动态时间弯曲距离的灰关联度量方法(grey incidence measurement algorithm based on DTW，DTW-GIM)。

输入:序列 Xi={xi(1)，xi(2)，…，xi(m)}与Xj={xj(1)，xj(2)，…，xj(n)}。

输出:Xi与Xj间的动态时间弯曲灰关联度。

算法步骤如下。

1)计算序列Xi与Xj初值像。

2)计算动态时间弯曲距离DTW(Xi，Xj)及弯曲路径长度λ。

3)调用(4)式计算 γ(Xi，Xj)。

4)返回 γ(Xi，Xj)。

算法以DTW距离为核心，有效地解决了序列长度不一致、时间轴伸缩弯曲和线性漂移问题。在算法的复杂性上，时间复杂度为O(n×m);在存储空间上，由于仅保持当前及上一次计算结果，故空间复杂度为O(min(n×m))。

3 基于动态时间弯曲的灰关联度量方法的应用

基于动态时间弯曲的灰关联度量方法可以广泛地应用于信息系统中数据的相似性比较、分类聚类等领域，同时，也可以作为灰关联度计算的一种有益补充。本文以数据挖掘领域中最基本的分类问题为例，将动态时间弯曲灰关联度应用于分类算法中。

分类是一类重要的数据挖掘问题，是在已分类数据的基础上构造分类模型(分类器)，再将待分类数据通过分类模型映射到给定类别中的过程。分类问题的核心在于分类器的构造与待分类数据间的差异性度量。在灰理论分类研究中，采用何种灰关联度量方法进行数据间的差异性度量是最核心的问题，而无论采用何种灰关联度量模型，均不能处理数据缺失问题(不完备信息系统)。通常在处理此类问题时，一般采用人工补齐或直接删除进行处理，引入了新的不确定性。而基于动态时间弯曲的灰关联度量方法对于数据序列是否长度一致不敏感，能有效降低数据的处理难度，提高数据挖掘性能。

在基于动态时间弯曲距离的自适应序列长度灰关联度量方法基础上，结合不同的分类器，可以构建不同的分类方法。以kNN分类方法为例，可得到改进后的分类方法。

算法2 基于动态时间弯曲灰关联度的kNN分类算法。

输入:训练样本集T，测试样本S，近邻数k。

输出:S所属类别。

算法步骤如下。

1)计算S与T中每个样本间的动态时间弯曲灰关联度;

2)按关联度大小对T中样本进行降序排列;

3)T中前k个样本中，类别数最多的类别即为S所属类别;

4)返回S所属类别。

4 实验及分析

为了考察基于动态时间弯曲的灰关联度量方法的正确性，以分类算法为例，采用UCI数据集［14］对采用不同差异性度量的分类方法进行测试。选取UCI数据库中的4个数据集，采用3交叉法进行测试。各数据集的记录数、条件属性数和决策属性数如表1所示。

表1 选取的UCI数据集Tab.1 Selected data sets from UCI

考虑到当前分类方法主要基于完备系统，故首先对于以上数据集在完备的情况下测试算法分类性能。采用经典分类方法 SVM［15］，kNN［15］，Bayes［15］分别基于 DDI，GDI，GI-VASN，GI-CPT 及 DTW-GIM 5种情况进行分类测试。测试结果如表2所示。

表2 完备情况下的正确识别率(单位:%)Tab.2 Correction rate without data lost(unit:%)

从表2可以看出，基于DTW的灰关联度在完备情况下与DDI与GDI得到的分类结果大致相当，高于GI-CPT与GI-VASN，说明该关联度是一种有效的差异性度量标准。为了测试其在不完备系统中的性能，对以上4个数据集进行了随机遗失处理(由于DDI，GDI，GI-VASN，GI-CPT 不能处理不完备信息，故采用均值方法对缺失数据进行了补齐)，试验结果见表3。

表3 不同遗失率下的正确识别率(单位:%)Tab.3 Correction rate on different random loss rate(unit:%)

表3中，对几种灰关联度量方法在不同遗失率下的分类性能(以kNN，k=10为例)进行了相应计算，取值为平均正确识别率。综合表2、表3，可得到DDI，GDI，GI-VASN，GI-CPT，DTW-GIM 的综合分类性能比较，如图2所示。

图2 分类性能比较Fig.2 Performance of classification

从图2可以看出，当遗失率不超过5%时，分类性能较为接近，DDI与 DTW-GIM最优，GI-CPI较差。随着遗失率的增加，DTW-GIM保存了较为优异的分类性能，其正确识别率超过了DDI与GDI。随着属性值遗失率的增加，识别率呈现出快速下降的趋势，说明当属性值缺失较多时，整个不完备系统的不确定性大大增加。

5 结束语

虽然灰理论正日渐成熟，但实际应用还不够广泛，一个重要原因是灰理论缺乏较为灵活的不确定性知识处理能力。面对序列数据存在的不确定性，尤其当序列数据长度不一致时［16］，人为补齐方法会导致不确定性信息的进一步放大，造成不必要的信息损失。

在现有灰关联模型的研究基础上，本文将动态时间弯曲思想引入灰关联度量中，提出了一种新的灰关联度量方法，有效解决了序列数据长度不一致、时间轴伸缩及弯曲问题。相比传统灰关联度量方法而言，该方法能够自动适应序列长度，避免了干扰信息的加入，具有更强的普适性。

［1］邓聚龙.灰理论基础［M］.武汉:华中科技大学出版社，2002:1-46.DENG Jiulong.The Foundation of Grey System ［M］.Wuhan:Huazhong University of Science and Technology Press，2002:1-46.

［2］刘思峰，党耀国，方志耕，等.灰色系统理论及其应用［M］.5版.北京:科学出版社，2010:55-102.LIU Sifeng，DANG Yaoguo，FANG Zhigeng，et al.Grey System Theory and Its Applications［M］.5th ed.Beijing:Science Press，2010:55-102.

［3］刘思峰，胡明礼，杨英杰.灰色系统模型研究进展［J］.南京航空航天大学学报:英文版，2012，29(2):103-111.LIU Sifeng，HU Mingli，YANG Yingjie.Progress of Grey System Models［J］.Transactions of Nanjing University of Aeronautics and Astronautics:English Edition，2012，29(2):103-111.

［4］刘思峰，谢乃明，FORREST J.基于相似性和接近性视角的新型灰色关联分析模型［J］.系统工程理论与实践，2010，30(5):881-887.LIU Sifeng，XIE Naiming，FORREST J.On new models of grey incidence analysis based on visual angle of similarity and nearness［J］.Systems Engineering-Theory ＆ Practice，2010，30(5):881-887.

［5］杨保华，方志耕，周伟，等.基于信息还原算子的多指标区间灰数关联决策模型［J］.控制与决策，2012，27(2):182-186.YANG Baohua，FANG Zhigeng，ZHOU Wei，et al.Incidence decision model of multi-attribute interval grey number based on information reduction operator［J］.Control and Decision，2012，27(2):182-186.

［6］王正新，党耀国，裴玲玲，等.基于累积前景理论的多指标灰关联决策方法［J］.控制与决策，2010，25(2):232-236.WANG Zhengxin，DANG Y G，PEI L L，et al.Mult-index grey relational decision-making based on cumulative prospect theory［J］.Control and Decision，2010，25(2):232-236.

［7］TIAN Min，LIU Sifeng，BU Zhikun.Review of the algorithm models of degrees of grey incidence［C］//IEEE.Proc of IEEE International Conference on Fuzzy Systems.Piscataway，N J:IEEE Press，2008:2162-2168.

［8］BERNDT Donald J，CLIFFORD James.Using Dynamic Time Warping to Find Patterns in Time Series［C］//In proceedings of the KDD Workshop.Seattle，WA:［s.n.］，1994:359-370.

［9］李鹏，刘思峰.基于灰色关联分析和 DS证据理论的区间直觉模糊决策方法［J］.自动化学报，2011，37(8):993-998.LI Peng，LIU Sifeng.Interval-valued Intuitionistic Fuzzy Numbers Decision-making Method Based on Grey Incidence Analysis and D-S Theory of Evidence［J］.Acta Automatica Sinica，2011，37(8):993-998.

［10］李鹏，刘思峰，方志耕.基于灰色关联分析和 MYCIN不确定因子的区间直觉模糊决策方法［J］.控制与决策，2012，27(7):1009-1014.LI Peng，LIU Sifeng，FANG Zhigeng.Interval-valued intuitionistic fuzzy numbers decision-making method based on grey incidence analysis and MYCIN certainty factor［J］.Control and Decision，2012，27(7):1009-1014.

［11］王翯华，朱建军，方志耕.基于灰色关联度的多阶段语言评价信息集结方法［J］.控制与决策，2013，28(1):109-114.WANG Hehua，ZHU Jianjun，FANG Zhigeng.Aggregation of multi-stage linguistic evaluation information based on grey incidence degree［J］.Control and Decision，2013，28(1):109-114.

［12］程文聪，邹鹏，贾焰.多维时序数据中的相似子序列搜索研究［J］.计算机研究与发展，2010，47(3):416-425.CHENG Wencong，ZOU Peng，JIA Yan.Similar Sub-Sequences Search over Multi-Dimensional Time Series Data［J］.Journal of Computer Research and Development，2010，47(3):416-425.

［13］SAKURAI Y，FALOUTSOS C，YAMAMURO M.Stream monitoring under the time warping distance［C］//IEEE.IEEE Data Engineering.Piscataway，N J:IEEE Press，2007:1046-1055.

［14］BACHE K，LICHMAN M.UCI Machine Learning Repository［EB/OL］.(2013-11-21)［2014-02-10］.http://archive.ics.uci.edu/ml.

［15］苏金树，张博锋，徐昕.基于机器学习的文本分类技术研究进展［J］.软件学报，2006，17(9):1848-1859.SU Jinshu，ZHANG Bofeng，XU Xin.Advances in Machine Learning Based Text Categorization［J］，Journal of Software，17(9):1848-1859.

［16］LUO Shengmei，WANG Zhikun，WANG Zhiping.Big-Data Analytics:Challenges，Key Technologies and Prospects［J］.ZTE COMMUNICATIONS，2013，11(2):11-17.