Wie hoch ist die Rechenkomplexität der arima() - Funktion in R?

Question

Wenn meine Zeitreihe n Mitglieder hat und ich möchte passen ARIMA(1,0,1) Modell, was wird die Komplexität in großen O Notation sein?

Im folgenden Beispiel muss ich die Komplexität der zweiten Zeile des Codes wissen:

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

Dank.

Answer 1

Es ist O(n) Komplexität. Eine Geschichte dafür? Siehe unten.

Wie ich im Kommentar gesagt habe, können wir es durch ein Regressionsmodell messen. Betrachten Sie als eine Spielzeugdemonstration das folgende Verfahren für die Datensammlung und -regression.

Zuerst definieren wir eine Funktion zur Messung der Modellanpassungszeit eines Modells ARMA(1,1) (oder ARIMA(1,0,1)). (mit microbenchmark() von Paket microbenchmark. Aber in den folgende Beachten Sie, dass ich die grundlegenden system.time() hier verwenden. Sie sollten versuchen, werde ich ziemlich große n verwenden, um die Empfindlichkeit in Zeitmessung zu reduzieren.)

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] 
    } 

Wir müssen Daten sammeln, sagen wir 100. Wir versuchen 100 zunehmend groß n, und messen Sie die Modellanpassungszeit t.

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]) 

Nun, wenn wir die Komplexität nehmen ist: a * (n^b) oder O(n^b), wir a, b durch ein Regressionsmodell abschätzen kann:

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

und wir sind besonders interessiert an der Slop Schätzung: b .

So ist lm()

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

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

nennen lassen wir auch die Streudiagramm von log(n) v.s. skizzieren kann log(t) sowie die angepasste Linie:

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

einige Ausreißer am Anfang gibt es daher die Neigung geringer ist als es sein sollte. Wir überlegen nun, Ausreißer zu entfernen und das Modell für Robustheit umzurüsten.

Ausreißer sind mit großen Residuen gekennzeichnet. Lassen Sie uns einen Blick:

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

Wir markieren und diese Ausreißer entfernen können. Sieht aus wie 0.5 ist ein gut genug Schwellenwert, um diese Ausreißer zu filtern.

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

nun wieder montieren wir das lineare Modell und machen Grundstück:

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) 

Wow, super, wir sind golden! Der Neigungsschätzwert ist 1. Somit ist die O(n) Komplexität gerechtfertigt!