Algoritmos para calcular a função de distribuição empírica multivariada (ECDF)?

O ECDF unidimensional é bastante fácil de calcular. No entanto, quando se trata de duas dimensões ou mais, os recursos on-line se tornam escassos e difíceis de alcançar. Alguém pode sugerir, definir e / ou apresentar algoritmos eficientes (implementação não pronta) para calcular ECDF multivariado?

Em uma investigação mais aprofundada, o documento a seguir fornece algoritmos eficientes para o problema do kD ECDF:

Bentley, JL (1980). Dividir e conquistar multidimensional. Comunicações da ACM, 23 (4), 214-229.

A principal estrutura de dados introduzida é conhecida como uma árvore de intervalo e é um pouco semelhante a uma árvore de kd , mas usa uma troca de espaço por tempo para obter consultas de intervalo mais rápidas. O autor do artigo acima, Jon Bentley (da Programming Pearls fame), é o inventor de ambas as estruturas de dados.

Ambas são árvores binárias que particionam recursivamente um conjunto de pontos dimensionais dividindo-se ao longo de um eixo de coordenadas na mediana. Em uma árvore kd, as subárvores de um nó são divididas ao longo da ésima dimensão, onde percorre movendo-se para baixo na árvore. Em uma árvore de intervalo, as subárvores são sempre divididas ao longo da primeira dimensão, mas cada nó é aumentado com uma árvore de intervalo dimensional definida sobre as dimensões restantes.$k$$d$$d$$1\ldots k$$k-1$

No momento da redação deste artigo, a página da Wikipedia para "Range Tree", vinculada acima, aponta para uma palestra em CS (Utrecht U.) comparando esses dois tipos de árvores a partir de 2012. Isso sugere que essas estruturas de dados ainda são essencialmente "estado da arte" " Há menção de uma variante "cascata fracionária" aprimorada para árvores de alcance, mas para o problema de ECDF de todos os pontos, isso apenas permite que o desempenho do algoritmo de Bentley seja alcançado por meio de consultas repetidas da árvore de alcance.

Não tenho certeza se existe uma maneira mais eficiente de calcular o ECDF nos pontos de dados , mas a seguinte abordagem de força bruta deve ser eficiente para calcular o ECDF sobre a "grade" de dados . É uma generalização simples da versão 1D.

Assumir que tem um conjunto de dados consistindo de pontos em dimensões, dado no matriz . Por simplicidade, assumirei que consiste inteiramente em números únicos (ou seja, posição geral *). Vou usar Matlab notação na pseudo-código a seguir, uma vez que é como eu pensava do algoritmo, mas posso expandir a este caso haja interesse.$N$$d$$N\times d$$X$$X$

Primeira computação

$[x_{:,k},I_{:,k}]=\text{sort}[X_{:,k}]$ para ,$k=1:d$

onde é a matriz de classificação em coordenadas e é a matriz do eixo da grade de coordenadas (ambos do tamanho ).$I$$x$$N\times d$

Em seguida, rasterize os pontos de dados na grade de dados implícita, computando um histograma (normalizado) como .$P=\text{accumarray}[I,\frac{1}{N},N\times\text{ones[1,d]}]$

Em seguida, integre esse "EPDF" em cada dimensão para fornecer ao ECDF: para .$P=\text{cumsum}[P,k]$$k=1:d$

Agora é o ECDF amostrado em .$P_{i_1,\ldots,i_d}$$x_{i_1,1},\ldots x_{i_d,d}$

Esse algoritmo leva tempo para cada classificação e para cada soma, portanto, o custo total é . Como o próprio ECDF em grade possui elementos , isso deve ser essencialmente ideal.$\text{O}[N\log N]$$\text{O}[N^d]$$\text{O}[d(N^d+N\log N)]$$\text{O}[N^d]$

(* A suposição de pontos distintos pode ser relaxada usando vez de , juntamente com um pouco de contabilidade.)$\text{unique}[]$$\text{sort}[]$