Comment calculer l'estimateur à l'échelle Qn de Rousseeuw et Croux (1993) pour les grands échantillons?

13

Soit Qn=Cn.{|XiXj|;i<j}(k) donc pour un échantillon très court comme {1,3,6,2,7,5} il peut être calculé en trouvant la statique du k ème des différences par paires:

    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

Ainsi Qn=Cn.2

De toute évidence, pour les échantillons de grande taille, soit 80 000 enregistrements, nous avons besoin d'une très grande mémoire.

Est-il possible de calculer dans l'espace 1D au lieu de 2D?Qn

Un lien vers la réponse ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf bien que je ne puisse pas le comprendre complètement.

K-1
la source
1
OK, la réponse pour les gars qui liront ceci plus tard: si vous voulez juste calculer un estimateur d'échelle robuste pour un morceau de données 1-installez la dernière version de R 2-installez le paquet robustbase 3 prêt à l'emploi! mais si vous développez un code en dehors de cet environnement, vous devez utiliser des médianes élevées pondérées pour minimiser les calculs requis pour Sn ou Qn.
K-1
1
Le lien vers le document ne fonctionne pas. Une référence appropriée (encore mieux, avec une citation des informations les plus pertinentes) nous aurait aidé à localiser les informations; en l'état, il est inutile lorsque le lien meurt (comme cela arrive souvent).
Glen_b -Reinstate Monica
2
ne devrait-il pas être k = h choisir 2 = h (h-1) / 2 = 6 ? Cela ne change cependant pas le résultat final.
un tigre du
pourquoi Qn = Cn * 2, pourquoi 2? comment a-t-il été calculé?
lidox

Réponses:

15

Mise à jour: Le nœud du problème est que pour atteindre la complexité temporelle O(nlog(n)) , il faut dans l'ordre de stockage O(n) .


Non, O(nlog(n)) est la limite théorique inférieure de la complexité temporelle de (voir (1)) la sélection de l' élément kth parmi tous les n(n1)2 possible|xixj|:1i<jn.

Vous pouvez obtenir de l' espace O(1) , mais uniquement en vérifiant naïvement toutes les combinaisons de xixj dans le temps O(n2) .

La bonne nouvelle est que vous pouvez utiliser l' estimateur d'échelle τ (voir (2) et (3) pour une version améliorée et quelques comparaisons temporelles), implémenté dans la fonction scaleTau2()du Rpackage robustbase. L' estimateur univarié τ est un estimateur d'échelle en deux étapes (c'est-à-dire repondéré). Il a une efficacité gaussienne de 95%, un point de rupture de 50% et la complexité du temps O(n) et de l' espace O(1) (en plus, il peut facilement être mis en ligne, ce qui réduit de moitié les coûts de calcul lors d'une utilisation répétée - bien que vous devra fouiller dans le Rcode pour implémenter cette option, c'est assez simple à faire).

  1. La complexité de la sélection et du classement dans X + Y et les matrices à colonnes triées GN Frederickson et DB Johnson, Journal of Computer and System Sciences Volume 24, Numéro 2, avril 1982, Pages 197-208.
  2. Yohai, V. et Zamar, R. (1988). Estimations de points de rupture élevées de la régression au moyen de la minimisation d'une échelle efficace. Journal de l'American Statistical Association 83 406–413.
  3. Maronna, R. et Zamar, R. (2002). Estimations robustes de l'emplacement et de la dispersion pour les ensembles de données de grande dimension. Technométrie 44 307–317

Modifier Pour utiliser ceci

  1. Allumez R(c'est gratuit et peut être téléchargé à partir d' ici )
  2. Installez le package en tapant:
install.packages("robustbase")
  1. Chargez le package en tapant:
library("robustbase")
  1. Chargez votre fichier de données et exécutez la fonction:
mydatavector <- read.table("address to my file in text format", header=T)
scaleTau2(mydatavector)
user603
la source
2
@ user603: le tau dont vous parliez. Mais pourquoi n'est-il pas répandu s'il a de si bonnes efficacités statistiques et informatiques et un point de panne?
Quartz
2
a) you can compute the mad and median online. From there it's trivial to compute the Tau. b) breakdown ain't robustness and the Tau has terrible bias in the presence of outliers. You can find more argument against it in section 5 of the Qn paper
user603
1
@user603 you mean this paper? wis.kuleuven.be/stat/robust/papers/publications-1994/…
German Demidov
1
@user603 according to the paper, the bias curve tells us how much estimator can change due to a given fraction of contamination. Qn and Sn were biased for my simulated examples (normal distribution + 20% of extremely high/low values), and the level of bias was comparable. May be I got something wrong, but both Sn and Qn seem suffering from the same problem.
German Demidov
1
@ user603 désolé, l'effet ne pouvait pas être vu pour des échantillons de taille 100. Je vois clairement le problème en utilisant de grands échantillons. Tous ont de terribles préjugés, maisτ has the largest one.
German Demidov
0

(Very short answer) The text for commenting says

avoid answering questions in comments.

so here it goes: There is a paper about an online algorithm which seemingly runs quite well: Applying the Qn Estimator Online.

EDIT

(by user user603). The algorithm linked to in this article is a moving window version version of the Qn.

Given a large sample {xi}i=1N divided into time windows of width n<N, {xi}i=tn+1t we can apply the Qn to each time window yielding Nn+1 values of the Qn. Denote these values {Qni}i=1Nn+1

The algorithm cited here allows to obtain Qni|Qni1 at an average cost less than the worst case O(nlog(n)) needed to compute Qni from scratch.

This algorithm can however not be used to compute the Qn of the full original sample {xi}i=1N. It also needs to maintain an buffer whose size can be as large as O(n2) (though it is often much smaller).

serv-inc
la source
While you should not answer in comments, you should also not post comments as answers, and if your answer is only a link, it's not an answer (but might be a comment). If you want it to be an answer rather than a comment, your answer should contain the relevant information in some manner, such as a quote from a properly referenced link, or your own explanation of the important details. If you can, please provide the necessary details; alternatively I can convert this to a comment for you.
Glen_b -Reinstate Monica
@Glen_b: go ahead and convert. Thank you for the clarification.
serv-inc
1
@user603 The perhaps you could (as in the links in my comment) edit the essential information into the above answer -- as it stands at present it's not within the SE networks guidelines for answers.
Glen_b -Reinstate Monica
No problem, I will! (but it is really late here,)
user603
@user603 Thanks; I'll leave it here for now then
Glen_b -Reinstate Monica
0

this is my implement of Qn...

I was programming this in C and the result is this:

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;
}
victor
la source
1
Although implementation is often mixed with substantive content in questions, we are supposed to be a site for providing information about statistics, machine learning, etc., not code. It can be good to provide code as well, but please elaborate your substantive answer in text for people who don't read this language well enough to recognize & extract the answer from the code.
gung - Reinstate Monica
This is the naive O(n**2) algorithm~
user603