AGCD： a robust periodicity analysis method based on approximate greatest common divisor  

作　　者：Juan YU Pei-zhong LU 

机构地区：[1]School of Computer Science and Technology, Fudan UniversiLy, Shanghai 200433, China

出　　处：《Frontiers of Information Technology & Electronic Engineering》2015年第6期466-473,共8页信息与电子工程前沿（英文版）

基　　金：Project supported by the National Natural Science Foundation of China （No. 60673082）

摘　　要：Periodicity is one of the most common phenomena in the physical world. The problem of periodicity analysis （or period detection） is a research topic in several areas, such as signal processing and data mining. However, period detection is a very challenging problem, due to the sparsity and noisiness of observational datasets of periodic events. This paper focuses on the problem of period detection from sparse and noisy observational datasets. To solve the problem, a novel method based on the approximate greatest common divisor （AGCD） is proposed. The proposed method is robust to sparseness and noise, and is efficient. Moreover, unlike most existing methods, it does not need prior knowledge of the rough range of the period. To evaluate the accuracy and efficiency of the proposed method, comprehensive experiments on synthetic data are conducted. Experimental results show that our method can yield highly accurate results with small datasets, is more robust to sparseness and noise, and is less sensitive to the magnitude of period than compared methods.目的:设计较现有方法鲁棒性更佳、效率更高的周期分析方法,从稀疏且含有噪声的周期事件观测数据中估算周期。创新点:本文首次将最大公因子逼近算法应用于周期估算问题。该算法在处理稀疏且含有噪声的数据方面具有效率高、性能稳定、鲁棒性好的特点。方法:首先,确定观测数据的噪声空间。本文根据观测数据自适应获取噪声上下限。然后,对观测数据进行预处理,消除其中包含的未知相位参数,并对预处理后的数据逐对以噪声穷举方式搜索所有可能的最大公因子,即采用公因子逼近的方法搜索候选周期,同时统计这些候选周期在整个搜索过程中出现的频率。搜索完成后,根据候选周期出现频率估算周期值,即选择出现频率最高的候选周期为估算周期。最后,采用仿真数据验证AGCD方法在处理稀疏且含有噪声的观测数据方面的鲁棒性和高效性。结论:(1)AGCD算法效率高,因其以穷举搜索噪声空间方式估算周期。而现有方法是以穷举周期的方式估算周期,噪声空间相比周期的取值空间小很多。所以,AGCD方法在效率上有很大提升。(2)AGCD能以更少的观测数据获得与其他方法近似或更高的准确率。(3)AGCD性能(准确性和效率)较其他方法更加稳定且受周期值影响更小。(4)AGCD方法无需利用有关周期取值区间的先验知识,相比于其他方法适用性更强。

关 键 词：Periodicity analysis Period detection SPARSITY Noise Approximate greatest common divisor （AGCD） 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]