Probability and Statistics – Distributions

•

(** 인터넷 익스플로러에서 보면 파이썬 코드 줄이 제대로 적용되어 보이지 않을 수 있습니다.**)

파이썬을 활용하여 확률 분포를 배워보자. 확률 분포는 특정 값에 대한 확률 또는 어떤 범위에 대한 확률을 정의하는 함수이다. 히스토그램은 분포를 보여주는 좋은 방법이다. 분포에 대해 이야기 하기 전에 히스토그램을 그리는 파이썬 프로그램을 먼저 작성해보자.

import pylab
import random
vals = [1,200]
for i in range(1000):
    num1 = random.choice(range(1,100))
    num2 = random.choice(range(1,100))
    vals.append(num1 + num2)
pylab.hist(vals, bins = 10)

리스트 vals에 1부터 100사이에 놓인 1000개의 숫자를 임의로 만들고 히스토그램으로 그 숫자들의 빈도를 보여준다. bins 인자를 10으로 지정하면 10개의 막대 그래프로 구성된 히스토그램을 보여준다. 즉, 숫자들을 10개 그룹으로 만들어 각 그룹에 속한 숫자들의 빈도로 막대의 높이를 지정하는 방식이다. bins를 더 큰 숫자, 예를 들어, 200으로 지정하면 히스토그램이 어떻게 달라지는지 확인하시오.

이제 정규 분포와 관련된 파이썬 프로그램을 작성해보자. 정규 분포(normal distribution)은 가우스 분포라 부르기도 하는데 분포가 알려지지 않은 대상을 모델링할 때 유용하다. 정규 분포는 평균과 표준편차를 모수(parameter)로 지정하여 정의한다. 정규 분포의 그래프는 평균 지점에서 가장 확률이 높고 좌우로 대칭을 이루며 가장 자리로 갈수록 확률이 낮아지는 종 모양이다.

동전 던기기 시뮬레이션을 통해 정규 분포를 만나보자. 동전을 던져 앞 면이 나오는 비율을 x축, 해당 비율이 나오는 시도의 횟수를 y축으로 놓고 그래프를 그리는 파이썬 프로그램을 작성해본다. .

import pylab
import random

''' 표준 편차(standard deviation) 구하는 함수 '''
def stdDev(X):
    mean = float(sum(X))/len(X)
    tot = 0.0
    for x in X:
        tot += (x - mean)**2
    return (tot/len(X))**0.5

''' 동전 던지기 시뮬레이션 '''
''' numFlips 횟수 만큼 동전을 던져 앞 면이 나오는 비율을 계산 '''
def flip(numFlips):
    heads = 0.0
    for i in range(numFlips):
        if random.random() < 0.5:
            heads += 1
    return heads/numFlips

''' numTrials 시도를 하고, 각 시도마다 numFlipsPerTrial 횟수 만큼 동전을 던지고
    각 시도마다 앞 면이 나온 횟수들, 이 횟수들의 평균과 표준편차를 계산 '''
def flipSim(numFlipsPerTrial, numTrials):
    fracHeads = []
    for i in range(numTrials):
        fracHeads.append(flip(numFlipsPerTrial))
    mean = sum(fracHeads)/len(fracHeads)
    sd = stdDev(fracHeads)
    return (fracHeads, mean, sd)

def labelPlot (numFlips, numTrials, mean, sd):
    pylab.title(str(numTrials) + ' trials of '
                + str(numFlips) + ' flips each')
    pylab.xlabel('Fraction of Heads')
    pylab.ylabel('Number of Trials')
    xmin, xmax = pylab.xlim()
    ymin, ymax = pylab.ylim()
    pylab.text(xmin + (xmax-xmin)*0.02, (ymax-ymin)/2,
               'Mean = ' + str(round(mean, 4))
               + '\nSD = ' + str(round(sd, 4)), size='x-large')

def makePlots(numFlips1, numFlips2, numTrials):
    val1, mean1, sd1 = flipSim(numFlips1, numTrials)
    pylab.hist(val1, bins = 20)
    xmin,xmax = pylab.xlim()
    ymin,ymax = pylab.ylim()
    labelPlot(numFlips1, numTrials, mean1, sd1)
    pylab.figure()
    val2, mean2, sd2 = flipSim(numFlips2, numTrials)
    pylab.hist(val2, bins = 20)
    pylab.xlim(xmin, xmax)
    labelPlot(numFlips2, numTrials, mean2, sd2)

random.seed(0)
makePlots(100, 1000, 100000)

makePlots(100, 1000, 100000)으로 두 가지 동전 던지기 시뮬레이션을 수행하고 그 결과를 각각 그래프로 만든다. 첫 번째 시뮬레이션은 100번 동전 던지기를 100,000번 시도하고, 두 번재 시뮬레이션은 1000번 동전 던지기를 동일한 횟수로 시도한다.

파이썬 프로그램을 실행하고 pylab.show()를 실행하여 그래프를 보자. 우선 두 그래프 모두 종 모양임을 볼 수 있다. 동전 던지기 실험에서 앞 면이 나오는 빈도는 그 시도의 횟수가 늘어나면 정규 분포로 근사할 수 있다고 알려져 있다.

첫 번째 그래프의 평균과 두 번째 그래프의 평균이 0.5로 비슷하지만, 각 시도에서 100번 동전을 던져 얻은 첫 번째 그래프의 표준 편차(SD, Standard Deviation)가 각 시도에서 1000번 동전을 던져 얻은 두 번째 그래프의 표준 편차 보다 크다는 것을 알 수 있다. 표준편차는 데이터가 평균을 중심으로 펼쳐져 있는 정도를 나타낸다. 따라서 두 번째 시뮬레이션에서 앞 면이 나오는 비율이 평균 0.5와 가까운 시도가 더 많았음을 뜻한다. 상식적으로 각 시도에서 던지는 횟수가 더 많았기 때문에 시뮬레이션 결과가 확률 이론적 결과에 가까워졌다.

각 시도에 동전을 던지는 횟수를 100회 보다 더 적은 10회로 설정하고 히스토그램 그래프를 만들어 살펴보자.

파이썬은 라이브러리로 정규분포 함수 random.gauss(mu,sigma)를 제공한다. 인자 mu와 sigma는 정규분포의 모수인 평균과 표준 편차다. 이번에는 이 함수와 앞에서 얻은 평균 0.5와 표준편차 0.05를 가지고 10만개의 확률 값을 임의로 얻어 히스토그램을 그려보자.

p = []
for i in range(1,1000000):
    p.append(random.gauss(0.5,0.05))
    
pylab.hist(p, bins=1000)
pylab.show()

평균을 중심으로 대칭형인 종 모양의 정규분포 그래프를 얻을 수 있다.
히스토그램 함수의 인자 bins를 1000으로 지정하여 많은 수의 막대 그래프를 그리고자 의도하였다. 막대 그래프의 수를 줄이면 종 모양이 제대로 표시되지 않는다. bins를 10으로 지정하여 히스토그램을 그려보라.

정규분포 함수 외에도 균등분포 함수 random.uniform(min, max), 지수분포 함수 random.expovariate(lambd) 등 다양한 분포 함수들을 파이썬에서 제공한다.

마지막으로 해쉬함수에서 충돌이 나는 확률을 파이썬 프로그램을 작성해 실험해보자. 먼저 해쉬와 해쉬함수에 대해서 간단하게 설명하자. 10개의 원소를 갖는 배열이 있고 각 원소는 리스트를 가리킨다고 가정하자. 처음에는 비어있는 리스트를 모두 가리키고 있다. 1부터 100사이의 숫자들을 임의로 나열해보자.

  • 45, 72, 36, 20, 66, 3, 32, 97, 46, 80, 77, 8, 21, 50, 40, 75, 33

가장 간단한 해쉬함수는 나머지 연산을 사용하여 정의할 수 있다.

  • h(x) = x % N    (N은 배열 크기, 예:10)
  • h(45) = 5
  • h(72) =2
  • h(36) = 6
  • ...

각 숫자에 해쉬함수를 적용해 얻은 해쉬값을 그 숫자를 저장할 배열의 첨자로 사용하고자 한다. 45, 72, 36, 20까지는 각각 5, 2, 6, 0 첨자 위치에 충돌 없이 저장하지만 66의 해쉬값이 6이므로 6번째 첨자에 이미 들어있는 36과 충돌이 발생한다. 이 경우 6번째 첨자의 원소가 가리키는 리스트의 첫 번째 원소를 36, 두 번째 원소를 66으로 저장한다. 그 다음에 46도 같은 첨자의 해쉬값을 갖게 되므로 이 리스트 뒤에 46을 추가할 것이다.

해쉬 함수의 충돌이 많이 발생하면 동일한 첨자의 배열 원소에 몰려서 숫자들을 저장하게 되고 충돌이 적게 발생하면 여러 첨자들의 원소에 골고루 퍼뜨려 숫자들을 저장하게 될 것이다. 동일한 첨자의 배열 원소에 많은 숫자가 리스트에 매달려 있으면 그 리스트에 있는 숫자를 찾기 위해 해쉬함수를 적용한 다음 최악의 경우 리스트의 길이만큼 따라가야하므로 탐색 시간이 오래 걸릴 수 있다. 따라서 해쉬 함수 충돌이 날 확률이 낮을 수록 탐색 시간이 줄어들 것이므로 더 좋다라고 할 수 있다.

이러한 배경에서 해쉬함수 충돌 확률을 collisionProb 파이선 함수로 수학적으로 계산해보고 findprobl 파이썬 함수로 실험적으로 시뮬레이션해서 구해본다.

  • collisionProb(1000, 50)
  • findProb(1000, 50, 10000)
import random
""" Probability by simulating a hash table
"""
def simInsertions(numIndices, numInsertions):
    choices = range(numIndices)
    used = []
    for i in range(numInsertions):
        hashVal = random.choice(choices)
        if hashVal in used:
            return 1
        else:
            used.append(hashVal)
    return 0
def findProb(numIndices, numInsertions, numTrials):
    collisions = 0
    for t in range(numTrials):
        collisions += simInsertions(numIndices, numInsertions)
    return collisions/numTrials
""" Probability by calculation
"""
def collisionProb(n, k):
    prob = 1.0
    for i in range(1,k):
        prob = prob * ((n - i)/n)
    return 1 - prob

collisionProb 함수에서 해쉬함수 충돌 확률을 수학적으로 계산하는 방법에 대한 아이디어는 다음과 같다. 크기 N의 배열에 K개 데이터를 넣는다고 가정하자. 단 N<K인 경우만 고려한다.

K번째 데이터까지 적어도 한 번 충돌이 날 확률은 K번째 데이터까지 넣어도 한 번도 충돌나지 않을 확률을 1에서 뺀 것이다.

  • 1번째 데이터를 삽입할 때 충돌이 나지 않을 확률: 1
  • 2번째 데이터를 삽입할 때 충돌이 나지 않을 확률: 1 x (N-1)/N
  • 3번째 데이터를 삽입할 때 충돌이 나지 않을 확률: 1 x (N-1)/N x (N-2)/N
  • ...
  • K번째 데이터를 삽입할 때 충돌이 나지 않을 확률: 1 x (N-1)/N x ... x (N-(K-1))/N
  • 즉, 적어도 한 번 충돌이 날 확률은: 1 - 1 x (N-1)/N x ... x (N-(K-1))/N

collisionProb 파이썬 함수는 numIndices (N)과 numInsertions(K)를 받아 위 식으로 확률을 계산한다.

findProb(numIndices, numInsertions, numTrials) 파이썬 함수는 동일한 N과 K를 numTrials 횟수만큼 해쉬함수 계산을 시뮬레이션해서 충돌 확률을 계산한다.

N을 1000, K를 50으로 두고 두 파이선 함수들을 실행하면 둘 다 0.71정도를 계산하고, K를 200으로 변경하면 둘 다 1이거나 1에 가까운 확률을 계산해낸다. 이 숫자를 해석해보면, 1000 크기의 배열에 50개 데이터를 집어넣을 경우 충돌나지 않게 골고루 퍼뜨려서 저장할 수 있을 것 같지만 그러한 확률은 1-0.71, 즉 0.3 밖에 되지 않는다. 만일 1000 크기의 배열에 200개 데이터를 넣는다면 거의 100% 충돌이 생긴다는 것을 얘기해주고 있다.

>>> collisionProb(1000,50)
0.7122686568799875
>>> findProb(1000, 50, 10000)
0.7154
>>> collisionProb(1000, 200)
0.9999999994781328
>>> findProb(1000, 200, 10000)
1.0

이제까지 다양한 파이썬 라이브러리 함수들을 사용하였다. 각 라이브러리 함수의 자세한 쓰임새를 더 알고 싶은 경우 매뉴얼을 살펴보면 된다. 파이썬 라이브러리 함수에 대한 매뉴얼을 보려면 다음 명령어를 실행하면 웹 브라우져에서 웹 페이지 형식으로 매뉴얼을 보여줄 것이다.

python.exe -m pydoc -b