2007 年 12月 第 21卷 第 6 期
装 甲 兵 工 程 学 院 学 报
Journal of A cademy of A r m ored Force E ngineering
D ec. 2007 V o. l 21 N o . 6
文章编号 : 1672 1497( 2007) 06 0058 04
时间间隔 , k 是整数。
第 6期
张小明等 : 时间序列关联维数快速算法及实现
59
N m = N - (m - 1) , 从这 N m 个点中任意选定 1 个参考点 X i , 计算其余 N m - 1 个点到 X i 的距离 dij = d (X i - X j ) = #X i - X j #, 联积分函数
Nm - 1 Nm
∃ ∃ H ( ri= 1 j = i+ 1
dij ),
则对应式 ( 5)、 ( 6), 有 2 Cm ( r) = ∗ N m (N m - 1 )
N -1 N
m
2 关联和的快速计算
从 G P算法可以看出 , 关联维数需要计算的点 对距离的数量较大, 并且随着数据量的增加, 计算耗 时呈指数级增加 , 在实际计算中 , 当时间序列长度为 20 480 点时, G P算法计算关联维数耗时达 32 m in,
i= 1 j = i+ 1
60
装甲兵工程学院学报
第 21 卷
这样, 采用式 ( 7) 、 ( 8)进行关联和 Cm ( r) 的计算 , 在 计算机编程中就较易实现 , 其程序的处理速度也比 采用式 ( 4)算法快数倍。 2 . 2 点对的最近邻搜索 方法一 : 计算相空间中所有点对的距离, 其时间 2 [ 4] 复杂度为 O (N ) , 可以看出该方法非常耗时, 尤 其是对于大数据量。 方法二 : 只计算小于阈值 r 的距离 , 如图 1( a) , 随着 r 的减小 , 所计算的数据量将大幅减少。但其 计算效率仍不足以满足在线评价的需要。
∃ ∃H
i= 1 j = i+ 1
m
m- 1
r-
∃
| x i+ l | - x j+ l | ,
( 7)
i= 0
Cm ( r ) =
N m - 1 Nm
2 ∗ N m (N m - 1 ) r - 0% m ax { | x i+ l | - x j+ l | } . l% m - 1 ( 8)
∃ ∃H
D 2 (m , r2 )
, j= 1 i
∃H r-
Nm
m- 1
∃
(x i+ l - x j+ l
, r> 0 . ( 4)
[ 3]
i= 0
式 ( 4) 是求关联维数时常用到的递推公式 , 但这样计算, 在时间序列长度较大时, 运算量会非常 大, 并且在计算机编程运算中 , 由于过多的中间重复 运算和计算的舍入误差 , 会出现意想不到的问题。 式 ( 4) 中的空间点间距计算是建立在欧氏空间 R 的球形领域 , 若采用 R 空间中与球形领域中距 离拓扑等价的菱形领域中的距离公式 , 或者采用方 形领域中的距离公式, 则 m 维相空间中的点 X i、 Xj
时间序列关联维数快速算法及实现
张小明
1
刘建敏
1
乔新勇
1
许世永
2
( 1. 装甲兵工程团公司 第 70研究所 , 大同 037036 )
摘
要 : 针对关联维数计 算耗时量大的问题 , 通过改进 点对距离的度量方 法 , 以及采 用 K NN 技术 进行点对的搜索
2 1 /2
当 N ∋ ( 时, C m ( r ) ) 1 。可以看出: 关联积分 Cm ( r )反映了吸引子中点间距离的分布概率, 因此有 D (m, r ) r 2 Cm ( r) = , r % dm ax, dm ax 式中 D 2 (m, r) 是与 m 及 r 有关的常数。对小距离 r1 和 r2, 有 C m ( r2 ) /Cm ( r1 ) = r2 dm ax
N
无法满足在线评估的要求。 在关联维数的计算和相空间 重构参数的选择 中, 计算量最大的部分就是关联和的计算, 关联和表 示了点的空间相关性 , 其本质就是 2 个任意点的距 离小于 r 的概率 , 这是关联维数计算的最主要部分, 也是最耗时的部分 , 主要包含距离计算和点对搜索。 因此 , 笔者从这 2方面入手, 对 G P 算法进行改进, 提高其计算效率。 2 . 1 点对距离的度量 由式 ( 1)得点 X i、 X j 之间的距离为 d ij = d 2 (X i - X j ) = # X i - X j # =
Abstract : Ai m ing at the m atter o f ti m e consu m ing in ca lculating the correlation d i m ensio n , by i m prov ing the m ethod o fm easuring the point po in t d istance , and by using the K N earest N eighbor Search techno logy to ca lculate the correlat ion sum, w e increase the ca lculat ing speed g reat ly. The actua l computation in dicates th at when th e ti m e ser ie s le ngth is 20 480 , the ti m e consu m pt ion of ca lculating th e correlation di m ensio n using the i m proved a lg orithm is 1 /60 o f that of usin g the G P algor ith m. K ey w ord s : ti m e series; correlat io n di m ensio n ; G P a lg orithm; K Nearest N eighbor Search 分形维数是定量刻画混沌吸引子 奇 异 程度 的一个重要参数 , 在众多的分形维数中, 关联维数对 吸引子的不均匀性反应敏感 , 更能反映吸引子的动 [ 1] 态结构 。系统的不确定性成分越多, 关联维数越 大 ; 系统的确定性成分越多 , 关联维数越小。因此 , 关联维数可用于定量 描述非线性系统 的运动。但 是 , 由 于 常 用 的 G P 算 法 ( G rassberger P rocacc ia algorithm ) 计算关联维数耗时 , 而且人为影响因素较 多 , 使得关联维数在实际中得不到广泛应用。 在关联维数的计算过程中, 关联和的计算所占 比重最大, 直接影响着关联维数的计算速度。笔者 通过改进点对距离的度量方法, 以及采用 K NN 技
d ij = d 1 (X i - X j ) = d ij = d( (X i - X j ) =
∃
| x i+ l - x j+ l |,
( 5)
l= 0
0% l% m- 1
m ax { | x i+ l - x j+ l | }.
( 6) 另外 , 由于 # X i - X j # = # X j - X i # , 且考虑 到当 i = j 时, # X i - X j # = 0 , 故关联积分的表达式为 C m ( r) = 2 N m (N m - 1)
[ 2- 3]
。设 { x k !k = 1 , 2 , ∀, N }
是观测某一系统得到的时间序列 , 对该时间序列进 m 行相空间重构 , 将其嵌入 m 维欧氏空间 R 中 , 得到 一个点 (或向量 )集 J (m ), 其元素记作 X n (m, ) = ( x n, xn+ , ∀, x n+ (m - 1) ), 式中 n= 1 , 2 , ∀, Nm , = k t 称作时间延迟, t是 2 次相邻采样的
m m
/
r1 d m ax
D 2 ( m, r1 )
,
对上式两边同时取对数, 得 lnCm ( r 2 ) - lnCm ( r1 ) = ln r2 dm ax
D (m, r )
2 2
- ln r 1 dm ax
D ( m, r )
2 1
,
之间的距离可分别表示为
m- 1
当 | r1 - r2 |很 小时 , D 2 (m, r2 ) ) D 2 (m, r1 )。因此 , 由 上式可得 d lnCm ( r) D 2 (m, r) = , d lnr 即 D 2 (m, r ) 是 lnCm ( r ) lnr 曲 线的斜 率。当 r ∋ 0 时 , 可得到 D 2 (m ) = rli mD (m, r ), ∋0 D 2 (m )不随相空间维数 m 的升高而改变时的值 D 2 = m li m D 2 (m ) ∋( 就是该时间序列的关联维数。 ( 3)
Fast A lgorithm for Calculating the Correlation D i m ension of T i m e Series
ZHANG X ia o m ing
1
L IU Jian m in
1
QI AO X in yong
1
XU Sh i yong
2
(1 . D epartm ent ofM echan ical Eng ineering, A cadem y of A r m ored Force Eng ineering, Bei jing 100072 , Ch in a ; 2 . N o. 7 R esearch Inst itu te, Ch ina N orth I ndu stries G roup C orporat ion, D atong 037036, C h ina)