改进曼-惠特尼统计量的变点检测

广东工业大学自动化学院 黄观纳 徐维超 王彦光

关于时间序列数据的变点研究在诸多领域拥有广泛的应用。对于给定的时间序列数据，本文采用滑动窗口思想计算型的曼-惠特尼统计量序列，根据加权移动平均思想加入权重参数，得到改进的曼-惠特尼统计量序列，并根据改进型曼-惠特尼统计量序列的极值分布指定判定变点的策略。实验表明：参数对于检测变点的性能具有双向性，虽然提高检测准确率，但需要提高平均检测误差作为代价。

近年来，时间序列数据的研究是一个广泛研究的课题，在工业生产，医学，气象，图像，金融等领域起着很重要的作用。时间序列数据是一组随着时间变化的序列数据，研究时间序列数据的性质是否发生变化隶属于变点检测问题，在工业故障检测，医学中的心电图和脑电图，气候方面的突发事件分析，人工智能领域的图像的边缘检测和分割技术以及语音辨析技术都能看到两种课题的结合。根据时间序列数据变化性质不同，变点检测模型可以分为均值突变模型和方差突变模型等；根据时间序列数据长度的有限性，变点检测模型可以分为离线变点检测模型和在线变点检测模型。

变点检测早期应用于统计控制过程（SPC），基于统计控制过程中的控制图算法，许多经典的变点检测算法如Shewhart控制图，CUSUM控制图，EWMA控制图相继被提出并广泛应用于变点检测领域。而早期的变点检测算法主要基于参数方法，在某些领域存在着局限性。当系统采集的数据难以知道服从什么分布时，不局限于系统采集的数据的性质和参数的非参数方法更加适用，如Pettitt(1979)提出的一种曼-惠特尼统计量的非参数变点检测方法，D.M.Hawkins(2003)提出的一种基于T假设检验的非参数变点检测模型以及ROSS提出的基于Cramer-von-Mises统计量与Kolmogormov-Smirnov统计量的非参数变点检测模型等。本文的变点检测模型基于曼-惠特尼统计量性质并改进，对时间序列数据进行离线变点检测并分析影响性能的因素。

1 相关理论

1.1 变点检测模型

变点检测可以描述为：变点检测的过程是检测时间序列数据的性质是否发生变化及何时发生变化的过程。给定一个由独立同分布的随机变量组成的时间序列，其中服从累积概率密度函数为均值，为方差，变点检测数学模型如下：

定义τ为变点的位置，而Δ指的是这里要研究的均值突变的幅度。上述模型是变点离线模型，而当n趋向无穷大时，S转变为时间序列数据流，模型则可以推广为在线变点模型。

1.2 曼-惠特尼统计量

曼惠特尼统计量广泛应用于突变点检测研究，它的定义如下：给定两个由独立同分布的随机变量组成的序列，，分别服从累计概率密度函数，因此曼惠特尼统计量可以定义为如下：

其中当x>0时，函数I(x)取1，否则函数I(x)取0。在零假设下，当时，，假设m和n都趋近于无穷大时，标准化后的曼惠特尼统计量近似服从标准正态分布。

2 利用改进型的曼惠特尼统计量进行变点检测

结合上面的变点检测数学模型和曼-惠特尼统计量的性质，我们采用一种类似滑动窗口的方案取获取待检测的时间序列的曼-惠特尼统计量序列。假设，对应的曼惠特尼统计量Tm就可以得到，然后X,Y向右移动一个单位，就如滑动窗口一样，以此类推我们可以得到曼惠特尼统计量序列。

当时间序列数据S出现变点τ时，窗口X,Y移动到出现变点区域时，曼惠特尼统计量序列T就会增大（向上突变），直到窗口X,Y完全处于不同的两个分布，之后曼惠特尼统计量序列T就会下降，知道窗口X,Y完全离开变点区域。因此我们可以定义检测的变点位置是曼惠特尼统计量序列T达到最大值的位置，即：

因此我们可以利用滑动窗口的方法去获取某个时间序列数据的曼-惠特尼统计量序列，并判断曼惠特尼统计量序列最大值的位置是出现突变点的位置。但是，这种情况只是适合出现了突变点的情况，而我们还需要判断给定的时间序列是否发生了突变，这就需要设定判断突变点的阈值。参考（Hawkins D M,Qiu P,Kang C W.The Changepoint Model for Statistical Process Control），当max(T)>thre，我们可以判定该时间序列发生了突变，这里的阈值thre我们可以根据零假设时（时间序列数据未发生突变时）的曼-惠特尼统计量极值分布来决定。令Tmax= max(T)，在给定虚警率α（在零假设情况下，突变点检测模型允许犯错的概率），可得：Pr(Tmax>thre)=α，就可以从这里得出判断突变点的阈值thre。

根据加权移动平均思想，我们在上述的曼-惠特尼统计量序列T中加入一个权重参数，改进的曼-惠特尼统计量如下：

而随着权重参数λ的加入，eTmax的分布与之前的的曼-惠特尼统计量Tmax有所不同，利用极值分布取获取判定变点的阈值时需要令Pr(eTmax>thre)=α。

3 实验

3.1 变点检测的性能指标

为了不失一般性，我们需要根据蒙特卡罗模拟实验方法，设计一套检验变点检测模型的性能指标和实验方案。对于变点检测性能指标的定义，选取检验准确率和平均误差作为文中实验的变点检测模型的性能指标，它们的具体定义如下：

检验准确率（acc）：

平均误差（err）：

3.2 参数λ的影响

根据文献（Wang Y,Huang G,Yang J,et al.Change Point Detection with Mean Shift Based on AUC from Symmetric Sliding Windows）中的证明，当两个窗口长度一致时，曼-惠特尼统计量的方差最小。令m=n=L，随着窗口长度的增大，检验准确率随着增大，平均误差逐渐减小，但到达一定长度后，两个指标趋向稳定。因此，取窗口长度L=50，实验次数Ntrial=10000，模拟时间序列为高斯分布随机序列，λ=0,0.8,0.9，均值突变幅度，Δ=[0,0.25,0.50,...,2.00]，对应每个λ分别算出在不断增加的Δ下的检验准确率与平均误差序列，实验结果如图1所示。

4 结果分析

从图中显示，随着均值突变幅度增大，检测准确率逐渐增大；因为这里采取的实验模拟信号服从标准高斯分布，所以就如图显示一样，当均值突变幅度为1时，检测准确率可以接近于1。相比于其他的λ=0值，当λ=0.8,0.9时，检测准确率在均值突变幅度小于1的范围内表现优于未加入参数λ。同时，检测误差也随着均值突变幅度的增大而下降，随着λ的增大，检测平均误差的衰减速度减缓，其中λ=0.9时衰减速度减缓的效果很明显。加入参数λ可以带来在突变幅度较小时的检测准确率的提高，到也会带来一些误差上的增加。

图1 均值突变幅度

5 讨论

本文融合指数加权移动平均思想在原先的曼-惠特尼统计量序列加入一个参数λ，并且通过实验验证窗口长度和λ参数对于变点检测性能的影响。实验表明：λ参数在相对比较低的均值突变时可以提升变点检测的准确率，而需要牺牲掉检测平均误差，因此如何选择λ参数需要我们在变点检测的检测准确率和检测平均误差中折衷考虑。本文的实验仅限至于高斯随机分布组成的时间序列数据，其他分布的时间序列数据以及实际数据后续进行深入的探讨。