R에서 arima() 함수의 계산 복잡도는 얼마입니까?

Question

내 시계열에 n 회원이 있고 ARIMA(1,0,1) 모델에 맞게 싶다면 O 표기법의 복잡성은 어떻게됩니까?

series <- arima.sim(list(order=c(1,0,1), ar=.9, ma=-.5), n=1000) 
result <- arima(series, order=c(1,0,1)) 

감사 : 다음 예에서

나는 코드의 두 번째 줄의 복잡성을 알아야합니다.

Answer 1

복잡도는 O(n)입니다. 이것에 대한 이야기? 아래를 참조하십시오.

의견에서 말했듯이 회귀 모델로 측정 할 수 있습니다. 장난감 데모로서 데이터 수집 및 회귀에 대한 다음 절차를 고려하십시오.

먼저 ARMA(1,1) 모델 (또는 ARIMA(1,0,1))의 모델 피팅 시간을 측정하는 함수를 정의합니다. (내가 여기 기본 system.time()를 사용하고 있습니다. 당신은 패키지 microbenchmark에서 microbenchmark() 사용을 고려할 수 있습니다.하지만 다음에, 나는 시간 측정의 감도를 줄이기 위해 합리적으로 큰 n을 사용합니다.)

t_arma <- function(N) { 
    series <- arima.sim(list(order=c(1,0,1), ar=.9, ma=-.5), n=N) 
    as.numeric((system.time(arima(series, order=c(1,0,1)))))[3] 
    } 

우리는 100 개의 데이터를 수집해야합니다. 우리는 점점 더 큰 n을 시도하고, 모델 피팅 시간을 t으로 측정합니다. 우리는 회귀 모델 a, b을 추정 할 수있다, a * (n^b), 또는 O(n^b) : 우리가 가정하면

k <- 100; t <- numeric(k) 
n <- seq(20000, by = 1000, length = k) ## start from n = 20000 (big enough) 
for (i in 1:k) t[i] <- t_arma(n[i]) 

이제 복잡성은

log(t) ~ log(a) + b * log(n) 

우리는 슬롭 추정에 관심이 있습니다 b .

그래서 우리는 또한 log(n) v.s.의 산포도를 스케치 할 수의이 lm()

fit <- lm(log(t) ~ log(n)) 

#Coefficients: 
#(Intercept)  log(n) 
# -9.2185  0.8646 

를 부르 자 log(t)뿐만 아니라 장착 된 : 일부 특이점이 때문에 경사가 실제보다 낮고, 초기에있다

가

plot(log(n), log(t), main = "scatter plot") 
lines(log(n), fit$fitted, col = 2, lwd = 2) 

. 이제 아웃 라이어를 제거하고 견고성을 위해 모델을 재조정하는 것을 고려합니다.

이상치는 큰 잔류 물을 특징으로합니다. 이제 살펴 보자 :

plot(fit$resi, main = "residuals") 

우리는 표시하고 그 이상 값을 제거 할 수 있습니다. 0.5은 이러한 이상 치를 필터링하는 데 충분한 임계 값입니다.

robust_fit <- lm(log(t) ~ log(n)) 

#Coefficients: 
#(Intercept)  log(n) 
# -11.197  1.039 

plot(log(n), log(t), main = "scatter plot (outliers removed)") 
lines(log(n), robust_fit$fitted, col = 2, lwd = 2) 

와우, 좋은, 우리는 황금과 같습니다

exclude <- fit$resi > 0.5 
n <- n[!exclude] 
t <- t[!exclude] 

이제 우리는 플롯 선형 모델을 다시 장착 및 확인! 기울기 추정값은 1입니다. 따라서 O(n) 복잡도가 정당합니다!