AGCD：一种基于最大公因子逼近的鲁棒周期分析方法

YU Juan; LU Pei-zhong

doi:10.1631/FITEE.1400345

Your Location：

Home >

Browse articles >

AGCD：一种基于最大公因子逼近的鲁棒周期分析方法

计算机与自动化 | Updated：2022-06-06

- AGCD：一种基于最大公因子逼近的鲁棒周期分析方法
- AGCD: a robust periodicity analysis method based on approximate greatest common divisor
- 信息与电子工程前沿（英文） 2015年16卷第6期页码：466-473
- Affiliations：
  
  School of Computer Science and Technology, Fudan University, Shanghai 200433, China
- Author bio：
  
  Juan YU, E-mail: juanyu10@fudan.edu.cn
  [ "Pei-zhong LU, E-mail:pzlu@fudan.edu.cn" ]
- Funds：
  
  Project supported by the National Natural Science Foundation of China (No. 60673082)
- DOI：10.1631/FITEE.1400345
  中图分类号： TP301.6
- 收稿：2014-10-09，
  
  修回：2015-05-15，
  
  纸质出版：2015-06
- Accepted：
Scan QR Code
AGCD：一种基于最大公因子逼近的鲁棒周期分析方法[J]. 信息与电子工程前沿（英文）, 2015,16(6):466-473.

YU Juan, LU Pei-zhong. AGCD: a robust periodicity analysis method based on approximate greatest common divisor[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(6): 466-473.
AGCD：一种基于最大公因子逼近的鲁棒周期分析方法[J]. 信息与电子工程前沿（英文）, 2015,16(6):466-473. DOI： 10.1631/FITEE.1400345.

YU Juan, LU Pei-zhong. AGCD: a robust periodicity analysis method based on approximate greatest common divisor[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(6): 466-473. DOI： 10.1631/FITEE.1400345.

摘要

目的

设计较现有方法鲁棒性更佳、效率更高的周期分析方法，从稀疏且含有噪声的周期事件观测数据中估算周期。

创新点

本文首次将最大公因子逼近算法应用于周期估算问题。该算法在处理稀疏且含有噪声的数据方面具有效率高、性能稳定、鲁棒性好的特点。

方法

首先，确定观测数据的噪声空间。本文根据观测数据自适应获取噪声上下限。然后，对观测数据进行预处理，消除其中包含的未知相位参数，并对预处理后的数据逐对以噪声穷举方式搜索所有可能的最大公因子，即采用公因子逼近的方法搜索候选周期，同时统计这些候选周期在整个搜索过程中出现的频率。搜索完成后，根据候选周期出现频率估算周期值，即选择出现频率最高的候选周期为估算周期。最后，采用仿真数据验证AGCD方法在处理稀疏且含有噪声的观测数据方面的鲁棒性和高效性。

结论

(1)AGCD算法效率高，因其以穷举搜索噪声空间方式估算周期。而现有方法是以穷举周期的方式估算周期，噪声空间相比周期的取值空间小很多。所以，AGCD方法在效率上有很大提升。(2)AGCD能以更少的观测数据获得与其他方法近似或更高的准确率。(3)AGCD性能(准确性和效率)较其他方法更加稳定且受周期值影响更小。(4)AGCD方法无需利用有关周期取值区间的先验知识，相比于其他方法适用性更强。

Abstract

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.

关键词

Keywords

references

S.D. Casey , B.M. Sadler . Modifications of the Euclidean algorithm for isolating periodicities from a sparse set of noisy measurements . IEEE Trans. Signal Process. , 1996 . 44 ( 9 ): 2260 - 2272 . DOI: 10.1109/78.536682 http://doi.org/10.1109/78.536682 .

I.V.L. Clarkson . Approximate maximum-likelihood period estimation from sparse, noisy timing data . IEEE Trans. Signal Process. , 2008 . 56 ( 5 ): 1779 - 1787 . DOI: 10.1109/TSP.2007.912268 http://doi.org/10.1109/TSP.2007.912268 .

E. Fogel , M. Gavish . Parameter estimation of quasiperiodic sequences . Proc. Int. Conf. on Acoustics, Speech, and Signal Processing , 1988 . p.2348 - 2351 . DOI: 10.1109/ICASSP.1988.197110 http://doi.org/10.1109/ICASSP.1988.197110 .

D.A. Gray , J. Slocumb , S.D. Elton . Parameter estimation for periodic discrete event processes . Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing , 1994 . p.93 - 96 . DOI: 10.1109/ICASSP.1994.389868 http://doi.org/10.1109/ICASSP.1994.389868 .

N. Howgrave-Graham . Approximate integer common divisors . Proc. Int. Conf. on Cryptography and Lattices , 2001 . p.51 - 66 . DOI: 10.1007/3-540-44670-2_6 http://doi.org/10.1007/3-540-44670-2_6 .

P. Huijse , P.A. Estevez , P. Zegers , 等 . Period estimation in astronomical time series using slotted correntropy . IEEE Signal Process. Lett. , 2011 . 18 ( 6 ): 371 - 374 . DOI: 10.1109/LSP.2011.2141987 http://doi.org/10.1109/LSP.2011.2141987 .

P. Huijse , P.A. Estevez , P. Protopapas , 等 . An information theoretic algorithm for finding periodicities in stellar light curves . IEEE Trans. Signal Process. , 2012 . 60 ( 10 ): 5135 - 5145 . DOI: 10.1109/TSP.2012.2204260 http://doi.org/10.1109/TSP.2012.2204260 .

I. Junier , J. Hérisson , F. Képès . Periodic pattern detection in sparse Boolean sequences . Algor. Mol. Biol. , 2010 . 5 31.1 - 31.11 . DOI: 10.1186/1748-7188-5-31 http://doi.org/10.1186/1748-7188-5-31 .

Z. Li , B. Ding , J. Han , 等 . Mining periodic behaviors for moving objects . Proc. 16th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining , 2010 . p.1099 - 1108 . DOI: 10.1145/1835804.1835942 http://doi.org/10.1145/1835804.1835942 .

Z. Li , J. Wang , J. Han . Mining event periodicity from incomplete observations . Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining , 2012 . p.444 - 452 . DOI: 10.1145/2339530.2339604 http://doi.org/10.1145/2339530.2339604 .

R. McKilliam , I.V.L. Clarkson . Maximum-likelihood period estimation from sparse, noisy timing data . Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing , 2008 . p.3697 - 3700 . DOI: 10.1109/ICASSP.2008.4518455 http://doi.org/10.1109/ICASSP.2008.4518455 .

B.M. Sadler , S.D. Casey . On periodic pulse interval analysis with outliers and missing observations . IEEE Trans. Signal Process. , 1998 . 46 ( 11 ): 2990 - 3002 . DOI: 10.1109/78.726812 http://doi.org/10.1109/78.726812 .

N.D. Sidiropoulos , A. Swami , B.M. Sadler . Quasi-ML period estimation from incomplete timing data . IEEE Trans. Signal Process. , 2005 . 53 ( 2 ): 733 - 739 . DOI: 10.1109/TSP.2004.840761 http://doi.org/10.1109/TSP.2004.840761 .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据