丙烯酰胺水溶液聚合DTWBarycenterAveraging（DBA）——平均序列求法 DBA
混凝土包管该算法是⽤来求序列数据集的⼀致序列（平均序列）。由Franc-ois Petitjean提出的。⽬前，该⽅法求得的平均序列是最准确的。 假设⼀元组为，当中的元素为实数时，很容易求的的平均值：
如果 的元素为序列的时，如如果直接套⽤上⾯公式通常会出现原序列没有的模式：
上图是对前三个序列求平均序列，采⽤传统的⽅法（上⾯的公式(1)）求得的第四个序列出现原序列不存
在的峰点，显然我们希望得到的平均序列是最下⾯的序列。为什么式(1)求得的平均序列会出现不存在的模式？主要是因为(1)是分别对序列对应位置上的点值求平均（点对点匹配），但是，在时间序列相似性度量我们知道点对点匹配求得的相似性容易受到序列的移位、错位等影响。同时我们了解动态时间规划（DTW）的思想很容易处理这种情况。举个例⼦： 上图是欧式距离的思想，点对点匹配。下图是DTW思想，序列的⼀个点对应另⼀个序列的⼀个或多个点。
可以换⼀个⾓度理解DTW算法，就是求序列 和序列之间DTW距离可以理解为求序列 和⼀个新的序列（元素也可以为⼦序列）之间的欧式距离，在举个例⼦，上图DTW的例⼦可以变为：
序列 可以包含⼦序列，序列 和序列内的元素是对应匹配的，序列 可以看成是序列 的扩展（具体求法可以参考DTW算法是如何寻弯曲路径的）。
好了，接下来开始谈谈DBA的思想，DBA是通过求下式来获得平均序列:
不幸的是，式(2)不能通过传统求极值的⽅法求解。并且该优化问题被认为式⼀个NP-Hard问题，可以采⽤启发式迭代算法逼近真实值。DBA就是求解式(2)的⼀种⽅法，是⼀种迭代算法。同样⽤⼀个例⼦来阐述DBA的求解步骤（展⽰⼀次迭代步骤），假设求序列 、序列 和序列 的平均序列 ：
松梢斑螟第⼀次迭代（假设序列B为初始平均序列）：
将DTW算法转化维欧式距离⽅法，求得新的序列 。喷粉流水线
求得新的序列 。
求得新的序列 。
令 ，表⽰新序列集。接下来可以求得的新时间序列求平均：
求得 ，第⼆次迭代令 为平均序列重复上⾯的步骤，指导满⾜条件。
这⾥可能有⼈会问，这样求得的平均序列能不能保证式(2)是收敛的？可以根据定义证明：令 是⼀个序列集， 是第 次迭代的平均序列。有：浮游生物计数框
因为 。所以可以保证算法的收敛性。接下来的问题是如何求得 ？⾸先先将DTW转化成欧式表达式：
其中， 是新序列集合 的第个点、 是序列的长度。对上式求偏导就可以得到：
所以， 。
总结：求平均序列对于⼀些算法是⾮常重要的，如K-mean算法在每次迭代时都需要求某⼀序列集的平均讯列，采⽤DBA算法可以获得更为准确的平均序列，提⾼K-mean性能。更深⼊了解关DBA算法还是需要阅读期刊⽂献，下⾯这⼏篇⽂献可能有所帮助。真篇博⽂是我⾃⼰对DBA算法的理解，希望能提供⼀点帮助。
[1]: Petitjean F, Forestier G, Webb G I, et al. Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification[C]// IEEE International Conference on Data Mining. IEEE, 2015:470-479.
[2]: Petitjean, Fran, ois, et al. A global averaging method for dynamic time warping, with applications to clustering[J]. Pattern Recognition, 2011, 44(3):678-693.
[3]: Petitjean F, Gançarski P. Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment[J]. Theoretical Computer Science, 2012, 414(1):76-91.
代码下载（matlab和java）： [4]: >顶空瓶
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议