Como calcular o estimador de escala Qn de Rousseeuw e Croux '(1993) para amostras grandes?

13

Seja Qn=Cn.{|XEu-Xj|;Eu<j}(k) portanto, para uma amostra muito curta como , pode ser calculada a partir da localização da estática da ésima ordem das diferenças entre pares: 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

AssimQn=Cn.2

Obviamente, para amostras grandes dizendo consistir em 80.000 registros, precisamos de uma memória muito grande.

Existe alguma maneira de calcular Qn no espaço 1D em vez de 2D?

Um link para a resposta ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf, embora eu não possa entendê-lo completamente.

K-1
fonte
1
OK, a resposta para as pessoas que lerão isso mais tarde: se você apenas deseja calcular um estimador de escala robusto para um dado 1 - instale a versão mais recente do R 2 - instale o pacote robustbase 3 pronto para uso! mas se você estiver desenvolvendo um código fora desse ambiente, precisará usar medianas altas ponderadas para minimizar os cálculos necessários para Sn ou Qn.
K-1
1
O link para o artigo não funciona. Uma referência adequada (melhor ainda, com uma citação das informações mais relevantes) nos ajudaria a localizar as informações; como está, é inútil quando o link morre (como costuma acontecer).
Glen_b -Reinstala Monica 16/03
2
não deveria ser k = h escolher 2 = h (h-1) / 2 = 6 ? Porém, não altera o resultado final.
um tigre
por que Qn = Cn * 2, por que 2? como foi calculado?
lidox 15/02

Respostas:

15

Atualização: O ponto crucial do problema é que, para alcançar a complexidade de tempo O(nlog(n)) , é necessário na ordem do armazenamento O(n) .


Não, O(nlog(n)) é o limite teórico mais baixo para a complexidade de tempo de (consulte (1)) selecionar o elemento kth entre todos os n(n1)2 possíveis|xixj|:1i<jn.

Você pode obter espaço O(1) , mas apenas verificando ingenuamente todas as combinações de xixj no tempo O(n2) .

A boa notícia é que você pode usar o estimador τ de escala (consulte (2) e (3) para obter uma versão melhorada e algumas comparações de tempo), implementadas na função scaleTau2()no Rpacote robustbase. O estimador univariado τ é um estimador de escala em duas etapas (ou seja, re-ponderado). Possui 95% de eficiência gaussiana, 50% de ponto de interrupção e complexidade de O(n) tempo e O(1) espaço (além de poder ser facilmente on-line), reduzindo metade dos custos computacionais em uso repetido - embora você terá que cavar no Rcódigo para implementar esta opção, é bastante simples de fazer).

  1. A complexidade da seleção e classificação em X + Y e matrizes com colunas classificadas GN Frederickson e DB Johnson, Journal of Computer and System Sciences Volume 24, Edição 2, abril de 1982, páginas 197-208.
  2. Yohai, V. e Zamar, R. (1988). Estimativas de regressão de altos pontos de ruptura por meio da minimização de uma escala eficiente. Jornal da Associação Estatística Americana 83 406–413.
  3. Maronna, R. e Zamar, R. (2002). Estimativas robustas de localização e dispersão para conjuntos de dados de alta dimensão. Technometrics 44 307-317

Editar Para usar isso

  1. Inicie R(é gratuito e pode ser baixado aqui )
  2. Instale o pacote digitando:
install.packages("robustbase")
  1. Carregue o pacote digitando:
library("robustbase")
  1. Carregue seu arquivo de dados e execute a função:
mydatavector <- read.table("address to my file in text format", header=T)
scaleTau2(mydatavector)
user603
fonte
2
@ user603: o tau ao qual você estava se referindo. Btw, por que não é difundido se ele tem tão boas eficiências estatísticas e computacionais e ponto de ruptura?
Quartzo
2
a) você pode calcular online o louco e a mediana . A partir daí, é trivial calcular o Tau. b) o colapso não é robusto e o Tau tem um viés terrível na presença de discrepantes. Você pode encontrar mais argumento contra ela no ponto 5 do o Qn papel
user603
1
@ user603 você quer dizer este artigo? wis.kuleuven.be/stat/robust/papers/publications-1994/…
German Demidov
1
@ user603 de acordo com o artigo, a curva de polarização nos diz quanto estimador pode mudar devido a uma determinada fração de contaminação. e S n foram influenciados pelos meus exemplos simulados (distribuição normal + 20% de valores extremamente altos / baixos), e o nível de viés foi comparável. Pode ser que eu tenha algo errado, mas ambos SQnSn e Q n parecem sofrer do mesmo problema. SnQn
German Demidov
1
@ user603 desculpe, o efeito não pôde ser visto em amostras de tamanho 100. Vejo claramente o problema usando amostras de tamanhos grandes. Todos eles têm preconceitos terríveis, mas tem o maior. τ
German Demidov
0

(Resposta muito curta) O texto para comentar diz

evite responder perguntas nos comentários.

aqui está: Existe um artigo sobre um algoritmo online que aparentemente funciona muito bem: Aplicando o Estimator OnlineQn .

EDITAR

(pelo usuário user603). O algoritmo vinculado neste artigo é uma versão da janela em movimento do .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
fonte
Embora você não deva responder nos comentários, também não deve postar comentários como respostas, e se a sua resposta for apenas um link, não é uma resposta (mas pode ser um comentário). Se você deseja que seja uma resposta em vez de um comentário, sua resposta deve conter as informações relevantes de alguma maneira, como uma citação de um link devidamente referenciado ou sua própria explicação dos detalhes importantes. Se puder, forneça os detalhes necessários; Como alternativa, posso converter isso em um comentário para você.
Glen_b -Reinstala Monica
@Glen_b: vá em frente e converta. Obrigado pelo esclarecimento.
serv-inc
1
@ user603 O talvez você possa (como nos links do meu comentário) editar as informações essenciais na resposta acima - como está atualmente, não está nas diretrizes das redes SE para obter respostas.
Glen_b -Reinstala Monica 16/03
Não tem problema, eu vou! (mas é muito tarde aqui,)
user603
@ user603 Obrigado; Vou deixá-lo aqui por enquanto, então
Glen_b -Reinstala Monica 17/03
0

este é o meu implemento de Qn ...

Eu estava programando isso em C e o resultado é este:

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;
}
vencedor
fonte
1
Embora a implementação seja frequentemente misturada ao conteúdo substantivo das perguntas, devemos ser um site para fornecer informações sobre estatísticas, aprendizado de máquina etc., não sobre código. Também pode ser bom fornecer código, mas elabore sua resposta substantiva em texto para pessoas que não leem esse idioma o suficiente para reconhecer e extrair a resposta do código.
gung - Restabelece Monica
Este é o ingênuo O (n ** 2) algoritmo ~
user603