Filtrando um conjunto de dados para obter uma distribuição mais uniforme para o treinamento em redes neurais

Estou pensando em usar redes neurais artificiais (RNA) para prever as taxas de reação no meu fluido, em vez de resolver o sistema completo de ODEs rígidas. Algumas pessoas do meu laboratório já fizeram algum trabalho para não começar do zero, mas estou tendo problemas com meus aplicativos. Acho que um deles diz respeito à qualidade do meu conjunto de dados para treinamento. Geralmente, extraímos dados de treinamento de simulações de CFD que são 1D / 2D / 3D. Não importa o que aconteça, acabamos com uma matriz multidimensional de dados para alimentar a rede neural. Para ter uma idéia do tamanho do problema, estou estudando o treinamento de 8 redes com 10 entradas e uma saída para cada uma. Sinto que um conjunto de treinamento de cerca de 100.000 pontos seria razoável, mas o problema é que esses 100.000 pontos precisam cobrir uma região específica do meu espaço multidimensional.

• Para cada instantâneo, apenas uma pequena parte dos pontos fica na região em que preciso de uma amostragem alta para garantir que meu treinamento seja preciso
• Ao compilar os instantâneos, acabo com muitos pontos quase duplicados que (acredito) têm um efeito negativo no meu treinamento da ANN: a) influenciando o treinamento colocando mais peso nessas regiões; b) adicionando pontos desnecessários.

Então, eu tentei filtrar os pontos que gravei antes de incluí-los no meu conjunto de treinamento. A meu ver, isso envolve verificar se um novo ponto está dentro de um determinado raio n-dimensional de cada ponto do meu conjunto de dados. Essa abordagem de força bruta, com exceção de alguns truques, como n ^ 2, funciona mais ou menos para extrair 10.000 pontos de 100.000 (leva 30 minutos, digamos), mas se decompõe à medida que eu aumento os tamanhos e números dos instantâneos ... Claramente , deve haver uma maneira mais inteligente de fazer isso, mas não sei em que direção começar a procurar. Tentei pela primeira vez com python e poderia mudar para o FORTRAN para acelerar as coisas, mas acho que devo procurar uma estratégia melhor primeiro. Minha única esperança é algum tipo de árvore kd? Tenho pouca ou nenhuma experiência com eles e o problema que vejo é que minha árvore crescerá à medida que construo meu conjunto de dados e isso só pode aumentar a complexidade. Uma biblioteca em árvore python kd se adequa à minha necessidade? Devo mudar para FORTRAN, considerando o tamanho do meu problema? Qualquer conselho é apreciado, obrigado!

Nas simulações de dinâmica molecular, temos o mesmo problema: dado um raio de corte , encontre todas as partículas no máximo uma da outra. A abordagem mais simples é dividir o espaço em células com comprimento de borda de pelo menos e comparar cada partícula em cada célula com todas as partículas nas 26 células vizinhas (em três dimensões, para dimensões , isso é ). Por construção, partículas em outras células estarão mais distantes que .r c O ( n ) r c d 3 d - 1 r $r_c$$r_c$$\mathcal O(n)$$r_c$$d$$3^d-1$$r_c$

No seu caso em que você está testando apenas uma posição para um conjunto fixo de pontos, divida o espaço em células de comprimento da aresta , classifique os pontos nas células (isso pode ser feito em ), e, em seguida, para cada ponto de teste, encontre a célula na qual esse ponto se encontra (pode ser feito em ) e verifique a distância entre os pontos nessa célula e as células circundantes (pode ser feito em , que depende da densidade do ponto e , mas não do número total de pontos).O ( n ) O ( 1 ) O ( 1 ) r $\ge r_c$$\mathcal O(n)$$\mathcal O(1)$$\mathcal O(1)$$r_c$

Todo o procedimento é descrito aqui . Se você quiser obter mais detalhes, tente pesquisar no Google por "lista vinculada a células" ou "lista de células".

A árvore do kd também é uma boa abordagem, mas pode ser mais difícil de implementar por conta própria (parece haver uma implementação em Python aqui , mas não permite adicionar pontos). No entanto, não se preocupe com a complexidade da árvore, pois, para uma distribuição de pontos mais ou menos uniforme, a profundidade da pesquisa se comportará como para pontos. Ou seja, dobrar a quantidade de pontos fará com que o esforço de pesquisa cresça por um fator constante. Você também precisa construir a árvore uma vez e pode atualizá-la rapidamente ao adicionar novos pontos.$\mathcal O(\log_2 n)$$n$

O problema que você declarou é um problema clássico em Geometria computacional: consultas de intervalo. Isso é:

Entrada: um subconjunto S do espaço euclidiano n-dimensional e um conjunto de pontos nesse espaço P.
Saída: o subconjunto de P que cruza S.

$O(n^{1-1/d}+r)$$O(n)$$O(n^{1-\frac{1}{d}}+r)$$O(n)$

O algoritmo envolve uma estratégia de dividir e conquistar (recursão) e uma estrutura de dados especial (kd-tree). Aqui está um esboço do algoritmo:

Begin MainProgram

    results = a new SET   (a kd-tree)
    search(space,root,results)
    return results
endMainProgram

Subroutine search(space,node,results)
    if (space contains node.region) then
        add node.point to the results
        for each descendant of node
            add d.point to results
        return
    if (space contains node.point) then 
        add node.point to results
    if (space extends below node.coordinate) then
        search(space,node.below,results)
    if (space extends above node.coordinate) then
        search(space,node.above,results)
endsubroutine

-source: Algoritmos em poucas palavras, página 298

A chave para o caso retangular é que podemos definir facilmente a estrutura de dados para incluir um subconjunto inteiro de uma só vez ... daí a árvore KD. A árvore KD simplesmente divide seu espaço n-dimensional cortando-o sucessivamente por hiperplanos, da mesma forma que um espaço 3D pode ser dividido por planos.

Para o seu problema específico que envolve consultas de alcance na direção radial (não caixas retangulares), você pode encontrar uma divisão recursiva de espaço semelhante baseada na esfera n ... Há uma estrutura de dados semelhante chamada de árvore vp, projetada para implementação de particionamento de espaço em coordenadas hiperesféricas. Você pode querer ver

"> nesta publicação para obter mais detalhes sobre a teoria das árvores vp.

Obviamente, a codificação pode ser um aborrecimento se seu objetivo é realmente usar o algoritmo como uma ferramenta para conduzir a ciência. Nesse caso, sugiro procurar em bibliotecas que já implementam essas estruturas de dados que você pode usar. Uma biblioteca de geometria computacional seria muito útil nessa situação. A biblioteca CGAL possui sub-rotinas para pesquisas no intervalo d-dimensional que podem ser do seu interesse. Aqui está outra lista de bibliotecas com sub-rotinas de consulta de intervalo.

Como alternativa, se você concorda em obter a maioria dos pontos no intervalo esférico que está pesquisando (mas não exatamente todos), convém considerar o uso de um algoritmo de aproximação como o deste artigo .