基于改进TS-DTW距离度量的时间序列聚类

Time Series Clustering Based on Improved TS-DTW Distance Metrics

摘要: 基于不同相似性度量的方法对时间序列进行聚类，比较改进TS-DTW距离与其他距离度量相似性在聚类结果上的效果。结果表明基于改进TS-DTW距离度量的聚类结果比其他方法更有效。利用上海证券交易所50指数成分股进行实证研究，采用改进TS-DTW距离进行聚类，聚类结果表明不同类别的股票后续仍具有一定时效性，基于此构建投资组合，得到的时间序列聚类模型有助于降低投资组合的波动风险。

Abstract: Clustering time series based on different similarity metrics compares the effect of improved TS-DTW distance with other distance metrics of similarity in clustering results. The results show that the clustering results based on the improved TS-DTW distance metric are more effective than other methods. An empirical study is carried out using the constituent stocks of Shanghai Stock Exchange 50 Index, and the clustering results using the improved TS-DTW distance indicate that the follow-up of different categories of stocks is still time-sensitive, based on which the investment portfolios are constructed, and the obtained time-series clustering model helps to reduce the volatility risk of the investment portfolios.

1. 引言

投资组合管理是一个十分复杂的非结构化决策过程，涉及金融预测、投资决策分析、组合优化等一系列过程，受到宏观经济、投资者心理、政府政策等多方面的影响[1] [2]。近年来，随着金融市场的复杂性日益增加，投资者对于寻找有效方法来降低投资组合波动性、控制风险的需求变得尤为迫切。时间序列聚类作为一种重要的数据挖掘方法，在金融领域中扮演着越来越重要的角色。在时间序列聚类的过程中，选择适合的距离度量方法对于获得高质量的聚类结果至关重要。其中，DTW (Dynamic Time Warping，动态时间规整)作为一种时间序列之间距离度量的方法，可以校正序列之间的长度差异、相位错位等问题，被广泛应用于时间序列聚类中。

时间序列是生活中常见的一种数据类型，是按照时间顺序排列的一种数据，广泛存在于金融[3] [4]、社交网络[5] [6]、工业电网[7]、气象[8]等领域。时间序列相似性度量是衡量两条时间序列相似程度的度量方法，是时间序列聚类分析中一个不可缺少的步骤[9]。为提高相似性度量效果，众多研究者进行了相关研究，Berndt等[10]于1994年提出的动态时间规整是时间序列相似性度量中的常用方法。陶洋等[11]在2019年发表了基于DTW距离度量的层次聚类算法，将基于欧氏距离度量相似性改进为基于DTW的距离度量，通过对比不同算法的聚类有效性指标，有效验证了该方法的可行性。与传统相似性度量(如欧氏距离)相比，DTW对时间序列的相位偏移、振幅变化等情况具有更强的鲁棒性[12]。

DTW作为时间序列相似性度量的方法之一，对时间序列数据挖掘起着重要作用[13]。然而，DTW算法亦存在一些缺陷，文章通过对DTW进行改进加上一个约束得到一个改进TS-DTW (时间序列动态时间规整)算法。首先基于不同相似性度量进行层次聚类分析，结果表明基于改进TS-DTW距离度量的聚类结果比其他方法更有效。最后利用上证50指数进行实证研究，采用改进TS-DTW距离进行聚类，聚类结果表明不同类别的股票在后续仍具有一定时效性，构建低波动率的投资组合，以降低投资风险。

2. 算法介绍

2.1. DTW算法

Figure 1. Alignment of Euclidean distances to DTW distances

图1. 欧氏距离与DTW距离的对齐

DTW是一种用于计算两个时间序列相似度的方法。时间序列的相似性度量则是评估两个时间序列相似程度的方法。如图1所示，时间序列上的点不再是一一对应，而是会出现“一对多”、“多对一”对应。

记两个时间序列分为$A=\left\{i_1,i_2,\cdots ,i_n\right\}$ ，$B=\left\{j_1,j_2,\cdots ,j_m\right\}$ 。$A$ 与$B$ 的对应关系可看成图2中蓝色路径$P=\left\{p_1,\cdots ,p_s,\cdots ,p_k\right\}$ ，$P_S=\left(i_s,j_s\right)$ 。

Figure 2. The DTW algorithm solves the path

图2. DTW算法求解路径

$A$ 与$B$ 之间的时间正则化距离，$D_P\left(A,B\right)$ 为：

$D_P\left(A,B\right)=\left[\frac{{\displaystyle {\sum }_{s=1}^k\delta \left(p_s\right)\cdot w_s}}{{\displaystyle {\sum }_{s=1}^k{w}_s}}\right]$

$\delta \left(p_s\right)$ ：$i_s$ 与$j_s$ 间距离，$w_s>0$ ：加权系数。

加权系数需要根据目标，选择不同的形式。

算法的目标是找到最佳的路径$P_0$ ，满足$P_0=\underset{P}{\arg \min }\left(D_P\left(A,B\right)\right)$ 。最佳路径需满足以下三点：

① 单调性：$i_{s-1}\le i_s$ 并且$j_{s-1}\le j_s$ 。

② 连续性：$i_{s-1}-i_s\le 1$ 并且$j_{s-1}-j_s\le 1$ 。

③ 边界条件：$i_1=1$ ，$i_k=n$ 并且$j_1=1$ ，$j_k=m$ 。

其中单调性意味着不能沿着路径往回走，这保证了特征不会在路径中重复。连续性意味着路径不能被跳过，确保没有元素被忽略。边界条件意味着路线从左下角开始，到右上角结束，确保整个序列都被考虑在内。

记$C={\displaystyle {\sum }_{s=1}^k{w}_s}$ ，有：

$D_{P_0}\left(A,B\right)=\frac{1}{C}\cdot \underset{P}{\min }\left[{\displaystyle {\sum }_{s=1}^k\delta \left(p_s\right)\cdot w_s}\right]$

$P_0$ 的求解因此变成了一个动态规划问题。

记这个动态规划问题为$r$ ，则有：

初始条件：$r_{1,1}={\delta }_{1,1}\cdot w_{1,1}$ 。

动态规划等式：$r_{i,j}={\delta }_{i,j}\cdot w_{i,j}+\min \left\{r_{i,j-1},r_{i-1,j},r_{i-1,j-1}\right\}$ 。

由边界条件可知，$r_{n,m}$ 表示着路径$P$ 的终点，因此可以得到：

$D_{P_0}\left(A,B\right)=\frac{1}{C}\cdot r_{n,m}$ (1)

由此DTW算法得到了两个序列的相似度，由(1)式计算。

2.2. DTW-Basic算法

$lcm\left(i,j\right)={\left({{\displaystyle \sum _v\left|x_i^v-y_j^v\right|}}^p\right)}^{1/p}$ (2)

首先，利用DTW算法创建一个局部成本矩阵(LCM或lcm)，它有$n\times m$ 个维度。将X和Y作为输入级数，对于LCM局部成本矩阵的每个元素$\left(i,j\right)$ ，必须计算$x_i$ 和$y_i$ 之间的$l_p$ 范数。公式(2)中$x_i^v$ 表示(可能是多变量)的第v个变量的第i个元素，表示只要多变量序列具有相同数量的变量，就支持它们(注意，对于单变量序列，无论使用的范数如何，LCM都是相同的)，p对应于用于构造LCM的$l_p$ 范数。

$DT{W}_p\left(x,y\right)={\left({\displaystyle \sum \frac{m_{\phi }lcm{\left(k\right)}^p}{M_{\phi }}}\right)}^{1/p},\forall k\in \varphi$ (3)

其次，DTW算法通过迭代地通过LCM，从$lcm\left(1,1\right)$ 开始，到$lcm\left(n,m\right)$ 结束，公式(3)中定义$\varphi =\left\{\left(1,1\right),\cdots ,\left(n,m\right)\right\}$ 为包含最优路径上所有点的集合，$m_{\phi }$ 是每步加权系数，$M_{\phi }$ 是相应的归一化常数。

2.3. 改进DTW算法

若时间序列数据存在部分异常点，如图3中左图中①所示序列X第一个数据异常导致序列Y所有数据点距该点距离最短，从而DTW路径出现“多对一，一对多”的情况，即局部路径坡度太陡或太平缓，如图3中右图中路径①所示，导致序列X，Y之间的DTW与实际相差较大，降低了两者的相关性[14]。

Figure 3. Route description

图3. 路径描述

为改进DTW算法，期望改进后的算法序列X和序列Y数据点对应关系如图3左图中②所示，给DTW算法加设约束窗口，如图3右图中的两条黑线所示，即$\left|i-j\right|\le r$ ，约束路径必须在2条黑线之间，命名为改进TS-DTW算法。如果约束窗口设置得太窄，即r太小，得到的约束路径将与图3右图中用蓝色圆形标记的路径非常相似，这代表传统的欧氏距离，改进后的DTW不希望失去相对于传统欧氏距离的优势。如果r过大，约束窗口就形同虚设，不能改善DTW的缺陷[14]。所以r的取值需要结合实例进行分析后给出。

改进TS-DTW算法过程如表1所示，首先计算每个$lcm\left[i,j\right]$ 的值，并给出约束r，若$\left|i-j\right|\le r$ ，则按照原本的DTW算法的路径进行计算，若$\left|i-j\right|>r$ ，则将其约束到$\left|i-j\right|\le r$ 内，最后得出改进TS-DTW距离d。

Table 1. Improved TS-DTW algorithm

表1. 改进TS-DTW算法

改进TS-DTW算法

输入 时间序列X、Y，约束大小r 输出 添加约束之后的时间序列之间X、Y的距离值 (1) function$\left(X,Y\right)$ (2) for i = 1:n (3) for j = 1:m (4) 计算$lcm\left[i,j\right]$ (5) 给出r (6) if $\left|i-j\right|\le r$ (7) $lcm\left[i,j\right]=\min \{\begin{array}{c}lcm\left[\left(i-1\right),\left(j-1\right)\right]+2\ast lcm\left[i,j\right]\\ lcm\left[\left(i-1\right),j\right]+lcm\left[i,j\right]\\ lcm\left[i,\left(j-1\right)\right]+lcm\left[i,j\right]\end{array}$ (8) else (9) $lcm\left[i,j\right]=lcm\left[\left(i-1\right),\left(j-1\right)\right]+2\ast lcm\left[i,j\right]$ (10) return $d=lcm\left[i,j\right]/\left(n+m-2\right)$

3. 算法对比

DTW-basic算法相较于原有的DTW算法引入了局部成本矩阵概念，对于局部成本矩阵的每个元素$\left(i,j\right)$ ，必须计算$x_i$ 和$y_j$ 之间的$l_p$ 范数。在计算时还加入了相应的归一化常数$M_{\phi }$ 、范数$p$ 。实现一些内存优化更快，特别是当计算DTW几对时间序列之间的距离。

改进TS-DTW算法相较于原有的DTW算法添加了一个约束窗口，即$\left|i-j\right|\le r$ ，将约束外的路径约束到约束窗口内。例如，设两个序列X，Y，$X=\left\{4,10,11,11,10\right\}$ ，$Y=\left\{4,4,5,5,4,4,5\right\}$ ，其中序列X第一个数据异常导致序列Y所有数据点距该点距离最短，表2中红色字体表示改进TS-DTW算法所得路径，其中$r=4$ ，$\left|i-j\right|\le 4$ ，即当$\left|i-j\right|>4$ 时必须按照斜方向走，将其约束到$\left|i-j\right|\le 4$ 内。

Table 2. Improve the TS-DTW algorithm path

表2. 改进TS-DTW算法路径

	[,1]	[,2]	[,3]	[,4]	[,5]	[,6]	[,7]
[1,]	0	0	1	2	2	0	1
[2,]	36	36	26	17	38	74	26
[3,]	85	85	62	63	87	123	146
[4,]	134	134	98	99	136	172	182
[5,]	170	170	123	124	160	196	207

4. 基于不同距离度量进行层次聚类

选取600组数据进行聚类，每组含有60个数据，600组数据分为6类，其中1~100组数据波动为随机波动，101~200组数据波动具有周期性，201~300组数据波动具有上升趋势，301~400组数据波动具有下降趋势，401~500组数据波动具有向上偏移趋势，501~600组数据波动具有向下偏移趋势。如图4所示，其分别为50、150、250、350、450、550组数据图示。

数据链接：http://kdd.ics.uci.edu/databases/synthetic-control/

Figure 4. 50, 150, 250, 350, 450, 550 sets of data in Fig

图4. 50、150、250、350、450、550组数据图示

4.1. 基于欧式距离、DTW距离、改进TS-DTW距离度量的层次聚类比较

首先不考虑第5类和第6类，只对前4类进行分析。因为根据图像可知，前4类的图像趋势易分辨，其分别为1~100组数据波动为随机波动，101~200组数据波动具有周期性，201~300组数据波动具有上升趋势，301~400组数据波动具有下降趋势。为节省计算时间，从每一个类里选取10组数据进行聚类。

第一，利用欧式距离度量，用组间平均链锁距离作为聚类方法进行层次聚类时，将数据波动具有周期性的6组数据分为数据波动为随机波动的类里。

第二，利用DTW距离进行相似性度量，用组间平均链锁距离作为聚类方法进行层次聚类时，可以清晰的将40组数据正确的分类到对应的类里，可见利用DTW距离度量的聚类效果要比用欧式距离的好。

第三，利用改进TS-DTW距离度量，取r = 10，因为经多次试验，取r = 10时，聚类效果最佳。经实验当每组数据个数小于等于一百时r取10左右，当数据个数越来越多时r将失去敏感度，通常取为一个区间，即r的具体取值不在过多的影响实验结果。用组间平均链锁离作为聚类方法进行层次聚类时，其结果和用DTW计算时相同，可见利用改进TS-DTW距离度量其聚类效果也比用欧式距离的好。

由表3可知，用组间平均链锁距离作为聚类方法，用欧式距离度量相似性时有6组数据分类错误，而当使用DTW距离、改进TS-DTW距离度量时，分类正确，聚类效果好。

Table 3. Cluster results based on Euclidean distance, DTW distance, improved TS-DTW distance measure

表3. 基于欧式距离、DTW距离、改进TS-DTW距离度量聚类结果

距离	欧氏距离	DTW	改进TS-DTW
分类错误总数	6	0	0

4.2. 基于不同DTW距离度量的层次聚类比较

基于前600组数据进行聚类，为节省计算时间，从每一个类里选取10组数据进行聚类。

分别利用DTW距离度量、DTW-basic距离度量、改进TS-DTW距离度量，用组间平均链锁距离作为聚类方法进行层次聚类，其结果由表4可知，在用组间平均链锁距离作为聚类方法，用改进TS-DTW距离度量时，其分类错误的总数比用DTW距离、DTW-basic距离时少，且分辨易混淆的类的效果也比用DTW距离、DTW-basic距离时效果好。

Table 4. Based on the clustering results of different DTW distance measures, clustering method: average chain distance between groups

表4. 基于不同DTW距离度量聚类结果，聚类方法：组间平均链锁距离

距离	DTW	DTW-basic	改进TS-DTW
分类错误总数	26	22	17
第三类、第五类分类错误个数	10	10	10
第四类、第六类分类错误个数	10	10	5

当利用不同的聚类方法进行层次聚类时，用改进TS-DTW距离度量得出的聚类结果相较于DTW距离、DTW-basic距离，也会更好。例如当选组内平均链锁距离作为聚类方法进行层次聚类，由表5可以得出，取r = 10时，利用改进TS-DTW距离进行度量，用组内平均链锁距离作为聚类方法进行层次聚类，具有一定分辨第三类和第五类，第四类和第六类的效果，且比用DTW距离分辨第三类和第五类，第四类和第六类的效果好。

Table 5. Based on the clustering results of different DTW distance measures, clustering method: average chain distance within the group

表5. 基于不同DTW距离度量聚类结果，聚类方法：组内平均链锁距离

距离	DTW	DTW-basic	改进TS-DTW
分类错误总数	14	23	13
第三类、第五类分类错误个数	6	10	4
第四类、第六类分类错误个数	8	10	7

5. 实证研究

5.1. 实验数据

研究对象为上证50指数的2023年6月1日至2023年10月31日的收盘价时间序列。上证50指数是以科学、客观的方法从上海证券市场中选取最具代表性的50只股票组成的样本股。因此，选取这份数据是合理的。

在进行股票的聚类分析时，由于不同股票价格之间的差异较大，股票的相似性更多是关注股价变化趋势的相似性，而不是股价本身的数值。因此，使用Z-score标准化对数据进行预处理是必要的。

5.2. 确定聚类数目

采用改进TS-DTW距离进行聚类，并绘制碎石图，由图5可知将50支股票数据聚成4类是比较恰当的。

Figure 5. Grstone plot of hierarchical clustering

图5. 分层聚类的碎石图

5.3 聚类的实际效果

以改进TS-DTW作为距离度量，k = 4进行聚类分析。抽取股票数目较多的一簇(记簇 A)来说明同一簇中的序列相似性，簇A包含12只股票，分别属于以下10个行业：非银金融(中信证券、中信建投、中国平安)，机械设备(三一重工)，银行(招商银行)，房地产(保利发展)，通信(中国联通)，化工(万华化学)，食品饮料(贵州茅台)，家用电器(海尔智家)，采掘(中国石油)，有色金属(紫金矿业)。12只股票所属行业不完全相同，但价格走势相似性很高，具有相似的涨跌趋势，如图6所示。

Figure 6. Share price sequence of Cluster A

图6. 簇A的股价序列

这是因为行业分类并不意味着收益分类。但要寻找行业分类外的外部分类标签并非易事。这表明时间序列聚类模型具备信息挖掘能力。然而，这些相似性是否包含相关信息，则需要更多的信息来加以证实。

Figure 7. Price movements in different categories

图7. 不同类别的中心点股价走势

考虑到样本数量，若要对所有聚类进行考察，很难将所有聚类的关系可视化为图像清晰展现，所以为每一个类别计算一个中心点，代表其所属类别的股价走势。观察图7可以发现，在样本期内不同簇的股价走势具有明显的差异，可以认为聚类效果良好。

5.4. 聚类实证结果的应用

5.4.1. 聚类结果的后续时效性验证

投资组合风险只有在关联性较弱的资产之间进行时，才能有效降低风险[15]。为了降低投资组合的整体风险，投资者通常会选择跨行业配置股票，以实现投资某些相关性低的股票的目标。聚类结果可以帮助找到股价走势相似的股票，获取不同的收益模式。但是其聚类结果的收益相似性在样本期外是否能够延续还需进一步验证。因此，根据时间序列聚类的结果，将构成上证50指数的50只成分股分为4组，然后分析这50只股票在样本期外一个月即2023年11月1日至2023年11月30日的收益率。每组股票被赋予相同权重，计算各聚类簇后续一个月的平均收益率，结果如表6所示。

Table 6. Average yield of different clusters

表6. 不同聚类簇的平均收益率

簇编号	簇内序列数	簇内平均收益率
1	29	−4.8%
2	12	−3.88%
3	4	−5.1%
4	5	3.71%

结果表明，聚类簇在样本期外收益率仍具有较大差异，其中第一簇和第三簇由图7观察其股价走势可得其收益率可能相近。说明聚类结果具有一定的后续时效性。这意味着我们可以利用时间序列聚类模型来构建投资组合，避免投资组合中的资产集中在同一簇，从而降低相关性带来的风险。

5.4.2. 基于聚类结果的投资组合构建

根据聚类结果具有一定的后续时效性，利用这一特性来构建投资组合，避免集中投资于收益相似的投资项目的风险。为了验证这一想法，设置3个对照组，每一组选择4只股票，组成权重相等的投资组合：

类间组合：在4个类别中，每个类别各随机选择1只股票。

随机组合：在50只股票中随机选择4只股票。

类内组合：随机选择一组至少包含4只股票的类别，再从这组股票中随机选择4只股票。

对每个组合模拟50次，计算2023年11月1日至2023年11月30日的日波动率，并取50次模拟结果的平均值。

Table 7. Average daily volatility of the different combinations

表7. 不同组合的平均日波动率

组合方式	平均日波动率
类间	0.0348
随机	0.0396
类内	0.0448

由表7可以看出类间组合的日波动率明显低于随机组合和类内组合的波动率，表明基于时间聚类模型的投资组合能有效降低投资组合的整体波动。

6. 结语

文章在现有DTW距离及DTW-basic距离方法下，增加了改进TS-DTW距离，并利用DTW距离、DTW-basic距离度量相似性及改进TS-DTW距离度量相似性，在用组内平均链锁距离、组间平均链锁距离作为聚类方法进行层次聚类，得出改进TS-DTW距离相较于DTW距离及DTW-basic距离在分辨易混的类时聚类效果更好。在实证研究部分，采用改进TS-DTW作为距离度量进行聚类，聚类结果表明不同类别的股票在后续仍具有一定时效性，构建低波动率的投资组合，以降低投资风险。

在之后的研究学习中，会对DTW的改进及投资组合构建和风险控制有更深的思考，不断改进和完善。关于聚类分析进行更深入的学习，针对聚类过程中相似性度量和聚类算法两方面尝试从不同角度出发，构造不同的聚类模型从而不断提高聚类精度。关于投资组合构建和风险控制进行模型优化，探索更有效的方法以提高投资组合构建的准确性和稳定性，并采取更多数据进行更准确的分析。