Niech więc dla bardzo krótkiej próbki, takiej jak , można ją obliczyć od znalezienia statycznego tego rzędu różnicy par: { 1 , 3 , 6 , 2 , 7 , 5 } $Q_n = C_n.\{|X_i-X_j|;i < j\}_{(k)}$$\{1,3,6,2,7,5\}$$k$

    7 6 5 3 2 1
1   6 5 4 2 1
2   5 4 3 1
3   4 3 2
5   2 1
6   1
7

h = [n / 2] + 1 = 4

k = h (h-1) / 2 = 8

Zatem$Q_n=C_n. 2$

Oczywiście w przypadku dużych próbek, które mówią, że zawierają 80 000 rekordów, potrzebujemy bardzo dużej pamięci.

Czy w ogóle można obliczyć w przestrzeni 1D zamiast 2D?$Q_n$

Link do odpowiedzi ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf, chociaż nie rozumiem tego w pełni.

Aktualizacja: sedno problemu polega na tym, że aby osiągnąć złożoność czasową $O(n\log(n))$ , potrzeba kolejności przechowywania $O(n)$ .

Nie, $O(n\log(n))$ jest dolną teoretyczną granicą złożoności czasowej (patrz (1)) wyboru elementu $k^{th}$ spośród wszystkich $\frac{n(n-1)}{2}$ możliwe$|x_i - x_j|: 1 \leq i \lt j \leq n$.

Można dostać $O(1)$ miejsca, ale tylko przez naiwnie sprawdzając wszystkie kombinacje $x_i-x_j$ w czasie $O(n^2)$ .

Dobrą wiadomością jest to, że można użyć estymatora skali $\tau$ (patrz (2) i (3) dla ulepszonej wersji i niektórych porównań czasowych), zaimplementowanego w funkcji scaleTau2()w Rpakiecie robustbase. Jednoznaczny estymator $\tau$ jest dwuetapowym (tj. Ponownie ważonym) estymatorem skali. Ma 95 procent wydajności Gaussa, 50 procent punktu przebicia oraz złożoność czasu $O(n)$ i przestrzeni $O(1)$ (a ponadto można go łatwo ustawić w trybie online, zmniejszając o połowę koszty obliczeniowe przy wielokrotnym użyciu - chociaż ty będzie musiał zagłębić się w Rkod, aby wdrożyć tę opcję, jest to raczej proste do zrobienia).

1. Złożoność wyboru i rankingu w X + Y i macierzach z posortowanymi kolumnami GN Frederickson i DB Johnson, Journal of Computer and System Sciences Tom 24, Issue 2, April 1982, Pages 197-208.
2. Yohai, V. i Zamar, R. (1988). Oszacowania regresji dla wysokiego punktu awarii za pomocą minimalizacji skutecznej skali. Journal of American Statistics Association 83 406–413.
3. Maronna, R. i Zamar, R. (2002). Solidne oszacowania lokalizacji i dyspersji dla zbiorów danych wielowymiarowych. Technometria 44 307–317

Edytuj Aby użyć tego

1. Odpal się R(jest bezpłatny i można go pobrać tutaj )
2. Zainstaluj pakiet, wpisując:

install.packages("robustbase")

3. Załaduj pakiet, wpisując:

library("robustbase")

4. Załaduj plik danych i uruchom funkcję:

mydatavector <- read.table("address to my file in text format", header=T)
scaleTau2(mydatavector)

(Bardzo krótka odpowiedź) Tekst do komentowania mówi

unikaj odpowiadania na pytania w komentarzach.

$Q_n$

EDYTOWAĆ

$Q_n$

$\{x_i\}_{i=1}^N$$n<N$$\{x_i\}_{i=t-n+1}^t$$Q_n$$N-n+1$$Q_n$$\{Q_n^i\}_{i=1}^{N-n+1}$

$Q_n^i|Q_n^{i-1}$ $O(n\log(n))$$Q_n^i$

$Q_n$$\{x_i\}_{i=1}^N$$O(n^2)$

to moja implementacja Qn ...

Programowałem to w C, a wynik jest następujący:

void bubbleSort(double *datos, int N)
{
 for (int j=0; j<N-1 ;j++)     
  for (int i=j+1; i<N; i++)    
   if (datos[i]<datos[j])      
   {
    double tmp=datos[i];
    datos[i]=datos[j];
    datos[j]=tmp;
   }
}

double  fFactorial(long N)    
{
 double factorial=1.0;

 for (long i=1; i<=N; ++i)
  factorial*=(double)i;

 return factorial;  
}

double fQ_n(double *datos, int N)  // Rousseeuw's and Croux (1993) Qn scale estimator
{
 bubbleSort(datos, N);

 int m=(int)((fFactorial((long)N))/(fFactorial(2)*fFactorial((long)N-2)));

 double D[m];
 //double Cn=2.2219;      //not used now :) constant value https://www.itl.nist.gov/div898/software/dataplot/refman2/auxillar/qn_scale.htm

 int k=(int)((fFactorial((long)N/2+1))/(fFactorial(2)*fFactorial((long)N/2+1-2)));

 int y=0;

 for (int i=0; i<N; i++)
  for (int j=N-1; j>=0; j--)
   if (i<j)
   {
    D[y]=abs(datos[i]-datos[j]);
    y++;
   }

 bubbleSort(D, m);

 return D[k-1];
}

int main(int argc, char **argv)    
{
 double datos[6]={1,2,3,5,6,7};
 int N=6;

 // Priting in terminal the final solution
 printf("\n==[Results] ========================================\n\n");

 printf(" Q_n=%0.3f\n",fQ_n(datos,N));

 return 0;
}