히스토그램과 일치하는 포인트를 어떻게 생성합니까?

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

문제

시뮬레이션 시스템을 작업 중입니다. 곧 여러 시뮬레이션 입력에 대한 값의 실제 분포에 대한 실험 데이터 (히스토그램)를 가질 것입니다.

시뮬레이션이 실행되면 측정 된 분포와 일치하는 임의의 값을 생성하고 싶습니다. 원래 히스토그램을 저장하지 않고이 작업을 선호합니다. 좋은 방법은 무엇입니까?

  1. 히스토그램을 분포를 나타내는 매개 변수 세트에 매핑 하는가?
  2. 런타임에서 해당 매개 변수를 기반으로하는 값을 생성합니까?

편집 : 입력 데이터는 여러 유형의 이벤트에 대한 이벤트 기간입니다. 다른 유형마다 분포 기능이 다를 것으로 예상됩니다.

도움이 되었습니까?

해결책

최소한 두 가지 옵션 :

  1. 히스토그램을 통합하고 수치 적으로 반전시킵니다.
  2. 배제

숫자 통합

에서 현대 물리학의 계산 William R. Gibbs :

하나는 항상 [함수]를 숫자로 통합하고 [CDF] 그러나 이것은 종종 특히 만족스럽지 않습니다. PDF 빠르게 변화하고 있습니다.

문자 그대로 범위를 번역하는 테이블을 작성합니다. [0-1) 대상 분포에서 적절한 범위로. 그런 다음 평소 (고품질) PRNG를 던지고 테이블로 번역하십시오. 그것은 번거롭지 만 명확하고 실행 가능하며 완전히 일반적입니다.

배제:

그러면 대상 히스토그램을 정규화하십시오

  1. 주사위를 던져 위치를 선택하십시오 (x) 범위를 따라 무작위로.
  2. 다시 던지고 새로운 임의의 숫자 가이 빈의 정규화 된 히스토그램보다 낮 으면이 점을 선택하십시오. 그렇지 않으면 goto (1).

다시 말하지만, 단순한 마음이 있지만 명확하고 일합니다. 매우 낮은 확률 (긴 꼬리가있는 피크)로 분포가 느리게 진행될 수 있습니다.

이 두 가지 방법 모두로, 당신 ~할 수 있다 스텝-기능 히스토그램이 필요하지 않은 경우, 부드러운 곡선을 생성하기 위해 부분 다항식 또는 스플라인으로 데이터를 근사화하십시오.

특별한 경우에는 더 나은 방법이 존재할 수 있습니다.

이 모든 것은 매우 표준이며 자세한 내용이 필요한 경우 숫자 분석 교과서에 나타나야합니다.

다른 팁

문제에 대한 자세한 정보가 유용합니다. 예를 들어, 히스토그램은 어떤 종류의 값을 초과합니까? 그것들은 범주 형 (예 : 색상, 문자) 또는 연속 (예 : 높이, 시간)입니까?

히스토그램이 범주 형 데이터를 초과하는 경우 범주간에 많은 상관 관계가없는 한 분포를 매개 변수화하기가 어려울 수 있습니다.

히스토그램이 연속적 인 데이터 인 경우 가우시안의 혼합물을 사용하여 분포에 맞도록 시도 할 수 있습니다. 즉, $ sum_ {i = 1}^n w_i n (m_i, v_i) $를 사용하여 히스토그램을 맞추십시오. 그런 다음 데이터를 생성하려면 먼저 가중치 w_i에 비례하는 확률로 1에서 1에서 i를 샘플링 한 다음 모든 가우스에서와 같이 x ~ n (m_i, v_i)을 샘플링합니다.

어느 쪽이든, 당신은 혼합 모델.

그래서 주어진 probablity 분포를 생성하기 위해 내가 원하는 것은 양자 기능, 그것은 반대입니다누적 분포 함수, @dmckee가 말한 것처럼.

문제는 다음과 같습니다. 주어진 연속 히스토그램을 설명하는 Quantile 함수를 생성하고 저장하는 가장 좋은 방법은 무엇입니까? 나는 대답이 입력의 모양에 크게 의존 할 것이라고 생각합니다. 어떤 종류의 패턴을 따르는 경우 가장 일반적인 경우에 비해 단순화해야합니다. 내가 갈 때 여기서 업데이트하겠습니다.

편집하다:

이번 주 에이 문제를 생각 나게하는 대화를 나누었습니다. 히스토그램을 방정식으로 묘사하고 테이블을 저장하는 경우 O (1) 시간으로 선택할 수 있습니까? 정밀도 손실없이 O (n lgn) 시공 시간의 비용으로 가능하다는 것이 밝혀졌습니다.

N 항목 배열을 만듭니다. 배열로의 균일 랜덤 선택은 probablilty 1/n의 항목을 찾을 수 있습니다. 각 항목에 대해이 항목을 실제로 선택 해야하는 히트의 일부 와이 항목의 색인을 저장하십시오.

가중 무작위 샘플링, C 구현 :

//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;
}

편집 2 : 약간의 연구 후에, 나는 O (n) 시간으로 건설을 할 수 있음을 알았습니다. 신중한 추적을 사용하면 크고 작은 쓰레기통을 찾기 위해 배열을 정렬 할 필요가 없습니다. 여기에서 업데이트 된 구현

이산 지점의 가중 분포로 많은 수의 샘플을 뽑아야한다면 비슷한 질문에 대한 답.

그러나 히스토그램을 사용하여 연속 랜덤 함수를 근사해야한다면 가장 좋은 방법은 아마도 DMCKEE의 숫자 통합 답변 일 것입니다. 또는 별명을 사용하고 왼쪽에 지점을 저장하고 두 지점 사이에서 균일 한 번호를 선택할 수 있습니다.

히스토그램 (원본 또는 축소) 중에서 선택하려면워커의 별칭 방법빠르고 간단합니다.

정규 분포의 경우 다음이 도움이 될 수 있습니다.

http://en.wikipedia.org/wiki/normal_distribution#generating_values_for_normal_random_variables

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top