Wie berechnet man den Qn-Skalenschätzer von Rousseeuw und Croux (1993) für große Stichproben?

13

Sei so dass für eine sehr kurze Stichprobe wie berechnet werden kann aus dem Auffinden der ten Ordnung statischer paarweiser Differenzen: Qn=Cn.{|XiXj|;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

Also istQn=Cn.2

Offensichtlich benötigen wir für große Samples, die aus 80.000 Datensätzen bestehen, sehr viel Speicher.

Gibt es überhaupt im 1D-Raum anstelle von 2D zu berechnen ?Qn

Ein Link zur Antwort ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf, obwohl ich es nicht vollständig verstehen kann.

K-1
quelle
1
OK, die Antwort für die Leute, die dies später lesen werden: Wenn Sie nur einen robusten Skalenschätzer für ein Datenelement berechnen möchten, installieren Sie die neueste Version von R 2, und installieren Sie das Robustbase-Paket, 3-ready to go! Wenn Sie jedoch einen Code außerhalb dieser Umgebung entwickeln, müssen Sie gewichtete hohe Mediane verwenden, um die erforderlichen Berechnungen für Sn oder Qn zu minimieren.
K-1
1
Der Link zum Artikel funktioniert nicht. Eine richtige Referenz (noch besser, mit einem Zitat der relevantesten Informationen) hätte uns dabei geholfen, die Informationen zu finden. So wie es aussieht, ist es nutzlos, wenn der Link stirbt (wie so oft).
Glen_b
2
sollte es nicht k = h sein, wähle 2 = h (h-1) / 2 = 6 ? Es ändert jedoch nichts am Endergebnis.
ein Tiger
warum ist Qn = Cn * 2, warum 2? Wie wurde es berechnet?
Lidox

Antworten:

15

Update: Der Kern des Problems besteht darin, dass zum Erreichen der Komplexität von in der Reihenfolge von Speicherplatz benötigt wird.O(nlog(n))O(n)


Nein, ist die untere theoretische Schranke für die zeitliche Komplexität von (siehe (1)) der Auswahl des -Elements unter allen möglich .O(nlog(n))kthn(n1)2|xixj|:1i<jn

Sie können -Raum erhalten, aber nur, indem Sie naiv alle Kombinationen von in der Zeit überprüfen .O(1)xixjO(n2)

Die gute Nachricht ist, dass Sie den in der Funktion im Paket implementierten Skalierungsschätzer (siehe (2) und (3) für eine verbesserte Version und einige Zeitvergleiche verwenden können . Der univariate Schätzer ist ein zweistufiger (dh neu gewichteter) Skalenschätzer. Es hat einen Wirkungsgrad nach Gauß von 95 Prozent, einen Durchschlagspunkt von 50 Prozent und eine Komplexität von -Zeit und -Raum (und es kann problemlos online geschaltet werden), wodurch die Hälfte der Berechnungskosten bei wiederholter Verwendung gespart wird - obwohl Sie müssen in den Code eintauchen, um diese Option zu implementieren, es ist ziemlich einfach zu tun).ττ O ( n ) O ( 1 )scaleTau2()RrobustbaseτO(n)O(1)R

  1. Die Komplexität der Auswahl und Rangfolge in X + Y und Matrizen mit sortierten Spalten GN Frederickson und DB Johnson, Journal of Computer and System Sciences, Band 24, Ausgabe 2, April 1982, Seiten 197-208.
  2. Yohai, V. und Zamar, R. (1988). Hohe Ausfallpunktschätzungen der Regression durch Minimierung eines effizienten Maßstabs. Zeitschrift der American Statistical Association 83 406–413.
  3. Maronna, R. und Zamar, R. (2002). Robuste Schätzungen von Standort und Streuung für hochdimensionale Datensätze. Technometrics 44 307–317

Bearbeiten Um dies zu verwenden

  1. Fire up R(kostenlos und kann hier heruntergeladen werden )
  2. Installieren Sie das Paket, indem Sie Folgendes eingeben:
install.packages("robustbase")
  1. Laden Sie das Paket, indem Sie Folgendes eingeben:
library("robustbase")
  1. Laden Sie Ihre Datendatei und führen Sie die Funktion aus:
mydatavector <- read.table("address to my file in text format", header=T)
scaleTau2(mydatavector)
user603
quelle
2
@ user603: das Tau, auf das Sie sich bezogen haben. Übrigens, warum ist es nicht weit verbreitet, wenn es eine so gute statistische und rechnerische Effizienz und einen so guten Durchschlagspunkt aufweist?
Quarz
2
a) Sie können den Mad und Median online berechnen . Von dort aus ist es trivial, das Tau zu berechnen. b) Ein Ausfall ist keine Robustheit, und der Tau ist in Gegenwart von Ausreißern schrecklich verzerrt. Weitere Argumente dafür finden Sie in Abschnitt 5 des Qn-Papiers
user603,
1
@ user603 meinst du dieses Papier? wis.kuleuven.be/stat/robust/papers/publications-1994/…
Deutsch Demidov
1
@ user603 Dem Papier zufolge gibt die Bias-Kurve an, um wie viel sich der Schätzer aufgrund eines bestimmten Anteils an Verunreinigungen ändern kann. und S n waren für meine simulierten Beispiele voreingenommen (Normalverteilung + 20% der extrem hohen / niedrigen Werte), und der Grad der Voreingenommenheit war vergleichbar. Vielleicht habe ich etwas falsch gemacht, aber S n und Q n scheinen unter demselben Problem zu leiden. QnSnSnQn
Deutsch Demidov
1
@ user603 Entschuldigung, der Effekt konnte für Samples der Größe 100 nicht gesehen werden. Ich sehe das Problem bei großen Samples. Alle von ihnen haben schreckliche Vorurteile, aber hat die größte. τ
Deutsch Demidov
0

(Sehr kurze Antwort) Der Text zum Kommentieren sagt

Vermeiden Sie es, Fragen in Kommentaren zu beantworten.

Also los geht's: Es gibt eine Abhandlung über einen Online-Algorithmus, der anscheinend recht gut funktioniertQn : Anwendung des Q n Estimator Online .

BEARBEITEN

(vom Benutzer user603). Der in diesem Artikel verknüpfte Algorithmus ist eine Moving-Window- Version des .Qn

{xi}i=1Nn<N{xi}i=tn+1tQnNn+1Qn{Qni}i=1Nn+1

Qni|Qni1 O(nlog(n))Qni

Qn{xi}i=1NO(n2)

serv-inc
quelle
Während Sie in Kommentaren nicht antworten sollten, sollten Sie auch keine Kommentare als Antworten posten. Wenn Ihre Antwort nur ein Link ist, ist es keine Antwort (aber möglicherweise ein Kommentar). Wenn Sie möchten, dass es sich um eine Antwort und nicht um einen Kommentar handelt, sollte Ihre Antwort auf irgendeine Weise die relevanten Informationen enthalten, z. B. ein Zitat aus einem richtig referenzierten Link oder Ihre eigene Erläuterung der wichtigen Details. Wenn Sie können, geben Sie bitte die erforderlichen Details an. alternativ kann ich das in einen kommentar für dich umwandeln.
Glen_b
@ Glen_b: Mach weiter und konvertiere. Danke für die Abklärung.
Serv-Inc
1
@ user603 Vielleicht könntest du (wie in den Links in meinem Kommentar) die wesentlichen Informationen in der obigen Antwort bearbeiten - da es derzeit nicht in den SE-Netzwerkrichtlinien für Antworten steht.
Glen_b -Reinstate Monica
Kein Problem, werde ich! (aber es ist wirklich spät hier,)
User603
@ user603 Danke; Dann
lasse
0

Das ist mein Werkzeug von Qn ...

Ich habe dies in C programmiert und das Ergebnis ist folgendes:

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;
}
Sieger
quelle
1
Obwohl die Implementierung bei Fragen häufig mit inhaltlichen Inhalten vermischt wird, soll es sich bei uns um eine Website handeln, die Informationen zu Statistiken, maschinellem Lernen usw. und nicht um Code enthält. Es kann auch gut sein, Code bereitzustellen, aber bitte erarbeiten Sie Ihre inhaltliche Antwort in Textform für Personen, die diese Sprache nicht gut genug lesen, um die Antwort aus dem Code zu erkennen und zu extrahieren.
gung - Wiedereinsetzung von Monica
Dies ist der naive O (n ** 2) -Algorithmus ~
user603