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

9

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?

Alexander F.
fonte
Essa pode ser uma questão de ciência da computação, mas acho que este é o melhor lugar para encontrar uma resposta, deixe-me saber se devo procurar em outro lugar. Obrigado.
Alexander F.
Existe realmente alguma diferença fundamental? Computar um ECDF univariado é equivalente a classificar os dados. Computar um ECDF multivariado é equivalente a classificar os dados lexicograficamente.
whuber
11
@ Whuber, não exatamente, tanto quanto eu sei. Para cada ponto de dados X(i), precisamos contar o número de pontos contidos no hipercubo definido por ele (de -infaté e incluindo X(i)em todas as dimensões). A classificação lexicográfica (dicionário?) Não funcionará necessariamente aqui, pois os pontos de dados devem ser comparados em todas as dimensões separadamente. Por exemplo: (2,3,4)será lexicograficamente maior em comparação com (1,2,15), mas o hipercubo definido por (2,3,4)não conterá (1,2,15)desde então 15>4.
Alexander F.
É verdade que a correspondência não é tão direta. Mas alguém poderia explorar essa classificação, ou algo parecido, para construir um ponto quadtree (ou octree etc ) com esforço . Você pode querer investigar a geometria computacional e a literatura de indexação espacial para obter detalhes. O(nlog(n))
whuber

Respostas:

7

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.kdd1kk1

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.

GeoMatt22
fonte
Obrigado pelo artigo interessante! Eu acho que é disso que eu preciso: árvores kd. Seria ótimo ver métodos alternativos. A menos que este seja o estado da arte.
Alexander F.
@AlexanderF. Atualizei minha resposta para melhor descrever o algoritmo (incluindo uma referência mais "oficial"). Parece que a abordagem ainda está próxima do estado da arte. Para desenvolvimentos recentes, a frase-chave parece ser "consultas de intervalo ortogonal" se você quiser investigar mais.
GeoMatt22
3

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.NdN×dXX

Primeira computação

[x:,k,Eu:,k]=ordenar[X:,k] para ,k=1 1:d

onde é a matriz de classificação em coordenadas e é a matriz do eixo da grade de coordenadas (ambos do tamanho ).EuxN×d

Em seguida, rasterize os pontos de dados na grade de dados implícita, computando um histograma (normalizado) como .P=accumarray[Eu,1 1N,N×uns [1, d]]

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

Agora é o ECDF amostrado em .PEu1 1,,EudxEu1 1,1 1,xEud,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.O[NregistroN]O[Nd]O[d(Nd+NregistroN)]O[Nd]

(* A suposição de pontos distintos pode ser relaxada usando vez de , juntamente com um pouco de contabilidade.)único[]ordenar[]

GeoMatt22
fonte
11
Você pode estar interessado em aprender sobre quadríceps e suas generalizações de dimensões mais altas, que fornecem maneiras eficientes de pesquisar pontos nos espaços euclidianos. Eles usam assintoticamente recursos , o que é muito melhor que para . O(Nregistro(N))O(Nd)d>1 1
whuber
11
@ whuber Eu tenho uma idéia disso, (por exemplo, árvores kd ). Não tenho certeza se existe uma única "melhor resposta" aqui? Normalmente, para um problema como esse, você também especificará quais operações sua estrutura de dados ECDF abstrata deve suportar (por exemplo, consultas de pontos, integrais de subespaço, atualização com novos pontos etc.). Isso ajudará a determinar qual implementação é mais adequada.
GeoMatt22
11
Eu acredito que deve ficar claro quais operações precisam ser suportadas para um ECDF. O mínimo é avaliá-lo em qualquer ponto do espaço. É verdade que, se alguém quiser construir um ECDF dinamicamente, abordagens alternativas podem ser superiores, mas essas questões parecem estar além do escopo da presente pergunta.
whuber
@ GeoMatt22, isso realmente parece um método para calcular histograma e pode ser bom nos casos em que a aproximação é "boa o suficiente". No entanto, por que usar um método que é O(N^d)quando a força bruta se aproxima O(d*N^2). Por exemplo, por enquanto não tenho um conjunto de dados muito grande, então uso o seguinte liner Matlab para calcular o ECDF tridimensional com O(d*N)complexidade de armazenamento ( C(i)é a frequência do ponto de dados Y(i,:)): arrayfun(@(i) sum(C(all(bsxfun(@le,Y, Y(i,:)), 2))), (1:size(Y,1)).');
Alexander F.
11
(+1) Não por fornecer um algoritmo eficiente, mas por explicar claramente um ineficiente que me ajudou a entender o problema.
Scortchi - Restabelece Monica