Como faço para gerar pontos que correspondem um histograma?

StackOverflow https://stackoverflow.com/questions/423006

Pergunta

Eu estou trabalhando em um sistema de simulação. Em breve vou ter dados experimentais (histogramas) para a distribuição do mundo real de valores para várias entradas de simulação.

Quando a simulação é executada, eu gostaria de ser capaz de produzir valores aleatórios que correspondem a distribuição medido. Eu prefiro fazer isso sem armazenar os histogramas originais. Quais são algumas boas maneiras de

  1. Mapeamento de um histograma para um conjunto de parâmetros que representam a distribuição?
  2. Geração de valores que, com base nesses parâmetros em tempo de execução?

EDIT: Os dados de entrada são durações de eventos para vários tipos diferentes de eventos. Espero que diferentes tipos terão diferentes funções de distribuição.

Foi útil?

Solução

Pelo menos duas opções:

  1. Integrar o histograma e inverter numericamente.
  2. Rejeição

Integração Numeric

De Computação em Física Moderna por William R. Gibbs:

Pode-se sempre numericamente integrar [a função] e inverta a [ cdf ] mas isso muitas vezes não é muito satisfatório, especialmente se o pdf está mudando rapidamente.

Você literalmente construir uma tabela que traduz o [0-1) intervalo em intervalos apropriados na distribuição alvo. Depois, jogue o seu PRNG usual (de alta qualidade) e traduzir com a tabela. É complicado, mas claro, funcional, e completamente geral.

Rejeição:

Normalize o histograma alvo, então

  1. Lance os dados para seleccionar uma posição (x) ao longo da gama de forma aleatória.
  2. Lance novamente e selecione este ponto se o novo número aleatório é menor do que o histograma normalizado neste bin. Caso contrário, Goto (1).

Mais uma vez, simplista, mas clara e de trabalho. Ele pode ser lento para distribuição com um monte de muito baixa probabilidade (picos com caudas longas).

Com ambos os métodos, você pode aproximar os dados com segmentadas fits polinomiais ou splines para gerar uma curva suave se um histograma em função degrau não é desejada --- mas deixar isso para mais tarde como pode ser optimização prematura.

melhores métodos podem existir em casos especiais.

Tudo isso é bastante normal e deve aparecer em qualquer livro Análise Numérica se mais detalhadamente é necessário.

Outras dicas

Mais informação sobre o problema seria útil. Por exemplo, que tipo de valores são os histogramas de novo? eles são categóricos (por exemplo, cores, letras) ou contínua (por exemplo, alturas, tempo)?

Se os histogramas são dados através categóricas eu acho que pode ser difícil para parametrizar as distribuições a menos que há muitas correlações entre as categorias.

Se os histogramas são dados através de contínuas que você pode tentar encaixar a distribuição utilizando misturas de gaussianas. Isto é, tentar encaixar o histograma usando um $ \ sum_ {i = 1} ^ n N w_i (m_i, v_i) $ onde m_i e v_i são a média e variância. Então, quando você deseja gerar dados que você primeira amostra de um i de 1..n com probabilidade proporcional aos pesos w_i e depois saborear um x ~ n (m_i, v_i) como faria a partir de qualquer Gaussian.

De qualquer maneira, você pode querer ler mais sobre modelos de mistura .

Assim, parece que o que eu quero, a fim de gerar uma dada distribuição probablity é um Quantile Função , que é o inverso da cumulativo função de distribuição , como @dmckee diz.

A pergunta é: Qual é a melhor maneira de gerar e armazenar uma função quantil descrevendo um determinado histograma contínua? Tenho a sensação de que a resposta vai depender muito da forma da entrada - se ele segue qualquer tipo de padrão deve haver simplificações sobre o caso mais geral. Vou atualizar aqui como eu ir.

Editar:

Eu tive uma conversa esta semana que me fez lembrar deste problema. Se eu renunciar descrevendo o histograma como uma equação, e apenas armazenar a tabela, eu posso fazer seleções em O (1) tempo? Acontece que você pode, sem qualquer perda de precisão, com o custo de O (N LGN) o tempo de construção.

Crie uma matriz de itens N. Uma selecção aleatório uniforme para a matriz vai encontrar um item com probablilty 1 / N. Para cada item, armazenar a fração de visitas para que este item deve realmente ser selecionada, eo índice de outro item que será selecionado, se este não é.

Weighted Random Sampling, C implementação: 

//data structure
typedef struct wrs_data {
  double share; 
  int pair;
  int idx;
} wrs_t;


//sort helper
int wrs_sharecmp(const void* a, const void* b) {
  double delta = ((wrs_t*)a)->share - ((wrs_t*)b)->share;
  return (delta<0) ? -1 : (delta>0);
}


//Initialize the data structure
wrs_t* wrs_create(int* weights, size_t N) {
  wrs_t* data = malloc(sizeof(wrs_t));
  double sum = 0;
  int i;
  for (i=0;i<N;i++) { sum+=weights[i]; }
  for (i=0;i<N;i++) {
    //what percent of the ideal distribution is in this bucket?
    data[i].share = weights[i]/(sum/N); 
    data[i].pair = N;
    data[i].idx = i;
  }
  //sort ascending by size
  qsort(data,N, sizeof(wrs_t),wrs_sharecmp);

  int j=N-1; //the biggest bucket
  for (i=0;i<j;i++) {
    int check = i;
    double excess = 1.0 - data[check].share;
    while (excess>0 && i<j) {
      //If this bucket has less samples than a flat distribution,
      //it will be hit more frequently than it should be.  
      //So send excess hits to a bucket which has too many samples.
      data[check].pair=j; 
      // Account for the fact that the paired bucket will be hit more often,
      data[j].share -= excess;  
      excess = 1.0 - data[j].share;
      // If paired bucket now has excess hits, send to new largest bucket at j-1
      if (excess >= 0) { check=j--;} 
    }
  }
  return data;
}


int wrs_pick(wrs_t* collection, size_t N)
//O(1) weighted random sampling (after preparing the collection).
//Randomly select a bucket, and a percentage.
//If the percentage is greater than that bucket's share of hits, 
// use it's paired bucket.
{
  int idx = rand_in_range(0,N);
  double pct = rand_percent();
  if (pct > collection[idx].share) { idx = collection[idx].pair; }
  return collection[idx].idx;
}

Edit 2: Após uma pequena pesquisa, descobri que é possível até mesmo fazer a construção em O (N) tempo. Com o monitoramento cuidadoso, você não precisa classificar a matriz de encontrar as grandes e pequenas caixas. implementação Atualizado aqui

Se você precisa puxar um grande número de amostras com uma distribuição ponderada de pontos discretos, em seguida olhar para uma resposta a uma pergunta similar.

No entanto, se você precisa para aproximar alguma função aleatória contínua usando um histograma, em seguida, sua melhor aposta é provavelmente resposta integração numérica de dmckee. Alternativamente, você pode usar o aliasing, e armazene o ponto para a esquerda, e escolher um número uniforme entre os dois pontos.

Para escolher a partir de um histograma (original ou reduzido), de Walker apelido método é rápido e simples.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top