'Cloud&BigData/Machine Learing'에 해당되는 글 20건

  1. 2015.09.24 OpenCV 이미지 유사도 비교 #2 - 히스토그램 비교 (7)
  2. 2015.09.22 OpenCV 이미지 유사도 비교 #1 - 피처 매칭 (1)
  3. 2015.09.11 OpenCV 자바 이클립스에서의 프로그래밍 시작하기~
  4. 2015.09.08 OpenCV 설치 및 자바 이클립스 환경 설정~
  5. 2015.08.04 OpenCV를 활용한 이미지 유사도 비교 방법~ (1)
  6. 2015.08.03 F Measure - Precision과 Recall을 통합한 정확도 측정
  7. 2015.07.27 정확도와 재현율 (Precision and Recall)에 대하여~
  8. 2015.01.26 몬테카를로 시뮬레이션~
  9. 2013.08.12 Nonparametric Method - 평균/분산을 모를때 확률분포를 만드는 방법
  10. 2013.06.20 Multinomial Variables - 다항 분포와 Dirichlet 분포에 대하여 (1)

OpenCV 이미지 유사도 비교 #2 - 히스토그램 비교

|



OpenCV를 활용한 이미지의 유사도 비교에서 먼저 피처 매칭을 살펴봤다. 

오늘은 히스토그램 비교를 알아보도록 하자. 


히스토그램은 매개변수에 따라 Correlation, Chi-square, Intersection, Bhattacharyya 각각의 결과값을 가질 수 있다. 

그래서 중요한 부분이 각각의 결과값을 어떻게 해석하는 것이다. 

Correlation과 Intersection은 값이 클수록 유사한 것이고, 

Chi-square와 Bhattacharyya는 값이 작을수록 유사한 것으로 판단한다. 


Comparing Histogram

먼저 전체 소스를 살펴보면 다음과 같다. 

마찬가지로 C로 구현되어 있는 Histogram 소스를 자바로 변환한 것이다. 


여기에서도 중요한 부분이 102~105번째 줄에 있는 유사성을 판단할 값이다. 

몇 번의 테스트를 통해서 대략적으로 값을 설정했지만, 좀 더 정교하게 다듬을 필요가 있다. 


히스토그램 방식에서는 4개의 결과값을 자체 기준으로 비교해서 세 개 이상이 적합할  때 

두 이미지가 유사한 것으로 판단하는 형태로 코딩을 했다. 


이런 조건들은 자유롭게 변경하면서 테스트하면 좋을 듯 하다. 


Histogram Test

피처 매칭과 동일하게 아이폰 이미지를 가지고 테스트를 해 봤다. 



먼저 동일한 이미지인 iphone1.jpeg를 비교하면 다음과 같이 동일하다고 나온다. 


이번에는 거의 비슷해 보이는 iphone1.jpeg와 iphone2.jpeg를 비교해보자. 

Chi-square를 제외한 나머지 세개가 조건을 충족해서 유사한 이미지로 판단했다. 


마지막으로 완전히 다른 iphone1.jpeg와 iphone3.jpeg를 비교해 보면 다음과 같다. 

Correlation과 Bhattacharyya이 조건을 만족했지만, 전체적으로 3개가 넘지 않아서 다르다고 판단했다. 

히스토그램을 사용하면 조건에 따라 오판하는 경우도 종종 있을 것으로 보인다. 

하지만, 이런 형태로 히스토그램을 사용할 수 있다는 것을 알아 두면 좋겠다. 


잠시 이미지 유사도 비교를 할 필요가 있어 OpenCV를 테스트를 해봤다. 

OpenCV가 실시간 이미지 프로세싱을 위한 라이브러리여서 이미지 유사도에 최적화되어 있지는 않지만, 

이런 형태로 활용할 수 있다는 점을 참고했으면 한다. 


OpenCV 더보기..

OpenCV를 활용한 이미지 유사도 비교 방법~

OpenCV 설치 및 자바 이클립스 환경 설정~

OpenCV 자바 이클립스에서의 프로그래밍 시작하기~

OpenCV 이미지 유사도 비교 #1 - 피처 매칭

OpenCV 이미지 유사도 비교 #2 - 히스토그램 비교





Trackback 0 And Comment 7
  1. 2015.09.25 15:05 address edit & del reply

    비밀댓글입니다

    • 미니~ 2015.09.25 23:53 신고 address edit & del

      문의한 부분은 저도 사용해보지 않은 것이네요 ㅠㅠ

  2. 한가위 2015.09.27 09:39 address edit & del reply

    미니님 답변감사합니다 .
    말씀해주신 답변을 토대로 공부해보겠습니다

    • 미니~ 2015.09.29 18:49 신고 address edit & del

      한가위인데도 열심히 하시네요. ^^
      꼭 해결하시길 바랄께요~~

  3. 2015.10.10 23:26 address edit & del reply

    비밀댓글입니다

    • 미니~ 2015.09.25 23:52 신고 address edit & del

      직접 해보지는 않았지만 다음 글을 참고하면 x, y 좌표를 구할 수 있지 않을까 합니다.

      http://stackoverflow.com/questions/8436647/opencv-getting-pixel-coordinates-from-feature-matching

      위 글의 답변을 그대로 옮겨봅니다.
      The DMatch class gives you the distance between the two matching KeyPoints (train and query). So, the best pairs detected should have the smallest distance. The tutorial grabs all matches that are less than 2*(minimum pair distance) and considers those the best.

      So, to get the (x, y) coordinates of the best matches. You should use the good_matches (which is a list of DMatch objects) to look up the corresponding indices from the two different KeyPoint vectors (keypoints_1 and keypoints_2). Something like:

      for(size_t i = 0; i < good_matches.size(); i++)
      {
      Point2f point1 = keypoints_1[good_matches[i].queryIdx].pt;
      Point2f point2 = keypoints_2[good_matches[i].trainIdx].pt;
      // do something with the best points...
      }

  4. Lll 2019.08.19 18:30 address edit & del reply

    C언어로 된 소스 볼 수 있을까요?

OpenCV 이미지 유사도 비교 #1 - 피처 매칭

|



OpenCV의 설치자바 프로그래밍 테스트를 살펴봤으니, 

이제 이미지 유사도 비교를 해보도록 하자. 

OpenCV를 활용한 이미지의 유사도 비교는 

히스토그램 비교, 템플릿 매칭, 피처 매칭의 세 가지 방법이 있다. 

오늘은 이 중에서 피처 매칭(Feature Matching)을 알아보도록 하자. 


Feature Matching

먼저 전체 소스를 살펴보면 다음과 같다. 

일반적으로 C로 구현되어 있는 Feature Matching 소스를 자바로 변환한 것이다. 


이미지 파일 2개를 받아서 서로 비교하는 compareFeature라는 메소드를 만들었다. 

핵심은 이미지에서 KeyPoint를 지정해서 서로 비교해서 거리를 계산한다. 

각 피처의 거리가 어느정도 일때, 두 이미지가 유사하다고 볼 건지를 결정하는 것이 가장 중요하다. 


90~94번째 소스를 보면, 10 이하일 때를 유사하다고 판단하는 것으로 우선 설정했다. 

다양한 이미지로 테스트하면서 이 값을 정하는 것이 필요할 것으로 보인다. 


위 로직에 따라 유사한 것으로 판단된 피처의 개수를 리턴했고, 

메인함수에서는 유사한 피처가 한개 이상이면 동일한 이미지라고 판단하도록 구성했다. 


추가로 76번째의 if 문은 완전히 서로 다른 이미지를 함수에 넣었을 때 발생하는 Assert 오류를 피하기 위해 적용했다. 


Feature Matching Test

다음의 세 개의 아이폰 이미지를 가지고 테스트를 해 봤다. 


먼저 동일한 이미지인 iphone1.jpeg를 비교하면 다음과 같이 동일하다고 나온다. 

 

이번에는 거의 비슷해 보이는 iphone1.jpeg와 iphone2.jpeg를 비교해보자. 

두 이미지의 피처간 거리가 있기는 하지만, 10 이하의 값이 2개가 나와서 유사한 이미지로 판단했다. 


마지막으로 완전히 다른 iphone1.jpeg와 iphone3.jpeg를 비교해 보면 다음과 같다. 

최소 거리값이 24가 나오면서 전혀 다른 이미지라고 나타났다. 


위 예제를 잘 활용하면, 피처 매칭으로 이미지 유사도를 비교해 볼 수 있을 것 같다. 

다음에는 히스토그램을 이용한 비교를 살펴보려고 한다. 


OpenCV 더보기..

OpenCV를 활용한 이미지 유사도 비교 방법~

OpenCV 설치 및 자바 이클립스 환경 설정~

OpenCV 자바 이클립스에서의 프로그래밍 시작하기~

OpenCV 이미지 유사도 비교 #1 - 피처 매칭

OpenCV 이미지 유사도 비교 #2 - 히스토그램 비교





Trackback 0 And Comment 1
  1. Choigy 2019.05.29 17:04 address edit & del reply

    C++로 변환된것은 없나요? 좋은자료감사합니다

OpenCV 자바 이클립스에서의 프로그래밍 시작하기~

|



OpenCV를 자바 환경에 설정하는 것은 지난번에 살펴봤다. 

이번에는 실제 자바 프로젝트에서 프로그래밍하는 방법을 알아보기로 하자. 


OpenCV 라이브러리를 자바프로젝트에 설정하기

먼저 일반적인 자바 프로젝트를 하나 생성한다. 

여기에서는 "Mini"라는 이름의 프로젝트를 생성했다. 

환경 설정을 위해 생성된 프로젝트의 "Properties"에 들어가서 좌측의 "Java Build Path"를 선택하고

상단의 "Libraries"를 클릭한 후, 우측의 "Add Library.."를 통해 앞서 설정한 OpenCV를 지정하면 된다. 



이어서 "User Library"를 선택한 후, OpenCV-3.0.0을 지정하면 된다. 



최종적으로 다음과 같이 라이브러리가 설정된 것을 확인할 수 있다. 



OpenCV 자바 프로그래밍 시작하기

자~ 이제 테스트 프로그래밍을 시작해 보자!!

가장 중요한 것은 opencv를 사용하기 위해서는 우선 다음과 같이 System.loadLibrary()를 실행해야 한다는 것이다. 


System.loadLibrary( Core.NATIVE_LIBRARY_NAME );


간단한 첫번째 프로그래밍 소스를 살펴보자. 


먼저 opencv 관련 클래스로 Core, CvType, Mat을 import한 것을 알 수 있다.

그리고 Core.NATIVE_LIBRARY_NAME 라이브러리를 호출한 후, 

MAT 클래스 통해 3x3 행렬을 생성하고 출력하는 예제이다. 

실행하면 다음과 같은 결과가 나온다. 



OpenCV의 자바 클래스에 대한 문서는 http://docs.opencv.org/java/ 에서 확인할 수 있다.  


앞으로 OpenCV를 활용하여 이전에 정리한 이미지 유사도 비교 방법을 각각 테스트해보기로 한다. 


OpenCV 더보기..

OpenCV를 활용한 이미지 유사도 비교 방법~

OpenCV 설치 및 자바 이클립스 환경 설정~

OpenCV 자바 이클립스에서의 프로그래밍 시작하기~

OpenCV 이미지 유사도 비교 #1 - 피처 매칭

OpenCV 이미지 유사도 비교 #2 - 히스토그램 비교





Trackback 0 And Comment 0

OpenCV 설치 및 자바 이클립스 환경 설정~

|



OpenCV는 2.4.4버전 이후로 자바를 지원하기 시작했다. 

OpenCV를 윈도우즈에 설정해서 이클립스 기반의 자바 프로젝트로 테스트를 해보도록 하자. 


OpenCV 3.0 설정

최신 버전의 OpenCV는 3.0으로 윈도우즈, 맥, 리눅스, 안드로이드, iOS등 다양한 운영체제를 지원한다. 



우측의 OpenCV for Windows를 클릭하면, opencv-3.0.0.exe 파일을 다운로드한다. 

이 파일은 압축 실행파일이라 별도의 설치를 하지 않고 압축만 풀게 된다. 

OpenCV의 폴더 구조와 자바 버전에서 사용할 jar파일의 위치를 빨간 테두리로 표시해봤다. 



압축이 풀린 opencv 폴더를 c:\opencv로 복사하고 시스템 환경변수의 PATH에 다음 사항을 추가한다. 

C:\opencv\build\x86\vc12\bin



OpenCV 이클립스 설정

이제 이클립스 환경에서 opencv를 사용할 수 있도록 설정해 보자. 

이클립스를 실행하고 상단 메뉴에서 "windows > preference..."를 선택한다. 



왼쪽 메뉴에서 "java > Build Path > User Libraries"를 선택하고 "New..." 버튼을 선택해 OpenCV-3.0.0을 등록한다. 




이어서 "Add External JARs..."를 선택해서 opencv가 설치된 폴더의 build\java\opencv-300.jar 파일을 선택한다. 



 

이제 마지막으로 "Native library location"을 지정해주면 된다. 

32비트 윈도우인 경우에는 c:\opencv\build\java\x86 폴더를 지정하고, 

64비트 윈도우는 c:\opencv\build\java\x64 폴더를 지정한다. 



여기까지 하면 기본적인 환경 설정이 완료되었다. 

앞으로 틈틈히 자바에서 OpenCV를 활용한 예제들을 정리해 보려고 한다. 


OpenCV 더보기..

OpenCV를 활용한 이미지 유사도 비교 방법~

OpenCV 설치 및 자바 이클립스 환경 설정~

OpenCV 자바 이클립스에서의 프로그래밍 시작하기~

OpenCV 이미지 유사도 비교 #1 - 피처 매칭

OpenCV 이미지 유사도 비교 #2 - 히스토그램 비교





Trackback 0 And Comment 0

OpenCV를 활용한 이미지 유사도 비교 방법~

|



OpenCV는 인텔이 개발한 오픈소스 컴퓨터비전 C 라이브러리이다. 

실시간 이미지 프로세싱을 위한 라이브러리로 윈도우, 리눅스 등 여러 플랫폼에서 활용할 수 있다. 

원래 C 언어로 되어 있지만 최근에는 Java 언어로도 적용할 수 있고, 안드로이드 및 아이폰과 같은 모바일 환경도 지원한다. 



다양한 이미지 프로세싱 알고리즘을 지원하기 때문에 

처음에는 두 이미지가 동일한지 비교하는 메소드 같은 것이 존재할 줄 알았다. 

그러나 두 이미지의 동일성을 OpenCV로 비교하는 것은 생각보다 쉽지 않았다. 


히스토그램 비교, 템플릿 매칭, 피처 매칭의 세 가지 방법이 있다고 하는데

각각의 방법으로 구현한 다음 많은 테스트를 통해 실제 어느 정도 값이 나오면 일치한다고 판단할지를 정해야 한다. 

이 부분은 다음 번 글에서 자바 기반의 소스와 함께 정리하면서 한번 더 논의해 보기로 한다. 


OpenCV를 활용한 이미지 비교와 관련해 위에서 언급한 세 가지 기술에 대해 살펴보도록 하자. 


Comparing histograms

히스토그램을 이용한 비교는 간단하면서 처리 속도가 빠른 방식으로 가장 오래된 방식이기도 하다. 

이 방식은 숲 이미지는 녹색 계열로 되어 있고, 바다는 청색 계열로 되어 있을 것이라는 아이디어에서 출발한다. 

그래서 숲과 관련된 두 장의 사진을 비교한다면, 두 이미지 모두 녹색을 많이 가지고 있기 때문에 히스토그램 사이에 유사성이 나타나게 된다. 


하지만 이 방식을 사용할 경우, 바나나와 노란색으로 이루어진 벤치를 같은 이미지로 착각하는 오류를 일으킬 수 있다. 

OpenCV 메소드는 compareHist()이며 C 언어 기반의 사용 예제는 여기를 참고하기 바란다. 

매개변수에 따라 Correlation, Chi-square, Intersection, Bhattacharyya 형태의 결과값을 제공한다. 


혹시 자바로 만든 예제를 원할 경우, OpenCV 이미지 유사도 비교 #1 - 피처 매칭 을 참고하기 바란다. 


Template matching

템플릿 매칭은 큰 이미지에서 주어진 작은 이미지가 존재하는지를 검색하는데 주로 사용한다.

아래 그림처럼 작은 이미지의 강아지가 큰 이미지에서 있는 부분(우측의 빨간색 사각형 부분)을 찾을 때 효과적이다. 


 

그러나 템플릿 매칭은 동일한 크기와 방향을 가진 똑같은 이미지를 가지고 검색할 때 좋은 결과가 나온다. 

즉, 서로 다른 이미지가 얼마나 유사한지를 확인하는 것은 쉽지 않다. 

OpenCV 메소드는 matchTemplate()이며, C 언어 기반의 사용 예제는 여기를 참고한다. 


Feature matching

피처 매칭은 개인적으로 이미지 유사성 비교를 할 때 가장 효과적인 방식이라고 본다. 

이미지로부터 수 많은 피처(feature)를 추출하는데, 해당 부분이 회전되거나, 확대/축소되거나, 찌그러져도 동일한 피처으로 인식하도록 보장한다. 

이런 방식으로 추출된 피처들을 다른 이미지의 피처셋과 비교하면서 유사성을 검사하게 된다. 

두 개의 이미지에서 추출한 피처들이 높은 비율로 일치한다면 동일한 또는 유사한 이미지로 볼 수 있다는 것이다.  



그러나 세가지 방식 중 가장 속도가 느리고, 완전히 정확하지는 않다는 단점이 있다. 

피처 매칭과 관련된 예제는 여기를 참고하면 된다. 


실제 피처 매칭을 적용하려고 해도 결과값을 수치화해서 유사하다고 판단할 수 있는 범위를 산정해야 한다. 

이를 위해서는 많은 테스트가 필요하지 않을까 한다. 


마찬가지로 자바로 만든 예제를 원할 경우, OpenCV 이미지 유사도 비교 #2 - 히스토그램 비교 을 참고하기 바란다. 


다음 글에서는 히스토그램과 피처 매칭을 자바로 구현한 다음 그 값의 범위를 정하는 것에 대해서 정리해 보려고 한다. 


OpenCV 더보기..

OpenCV를 활용한 이미지 유사도 비교 방법~

OpenCV 설치 및 자바 이클립스 환경 설정~

OpenCV 자바 이클립스에서의 프로그래밍 시작하기~

OpenCV 이미지 유사도 비교 #1 - 피처 매칭

OpenCV 이미지 유사도 비교 #2 - 히스토그램 비교





Trackback 0 And Comment 1
  1. 정원영 2015.11.12 15:59 address edit & del reply

    안녕하세요! 요새 OpenCV를 다시 써보고 있습니다. 예전에 학교에서 잠깐 실습했을 때,
    Feature매칭에서 A(작은),B(큰)를 비교할 때 A가 2개이상 B에 있을 경우엔 유일성에 실패하여 매칭이 안되는 이슈가 있었던 걸로 기억하는데..
    (예를들어 하트10카드에서 하트모양 찾기 등)
    유일성 검사 같은 방법으로 걸러낼 수가 있을까요? 좋은 글 감사합니다.

F Measure - Precision과 Recall을 통합한 정확도 측정

|



동전을 10번 던져서 계속 앞면이 나왔다고 하면, 앞면이 나올 확률을 1이라고 할 수 있을까? 

분명 동전을 던진 회수가 너무 적기 때문에 1이 아니라고 이야기할 것이다. 

즉, 계속해서 반복했을 때도 동일하게 나오는지 체크하는 것이 필요하다. 


그래서 일반적인 정확도(Precision) 뿐만 아니라 재현율(Recall)이 정보검색, 패턴인식, 기계학습에서 의미가 있는 것이다. 

이러한 정확도와 재현율을 하나의 지표로 통합해서 정확성을 측정하는 방법들이 존재한다. 


F-Measure

정확성을 측정하는데 가장 많이 사용하는 F-Measure에 대해 살펴보기로 하자. 

F-Measure는 Precision과 Recall의 트레이드오프를 잘 통합하여 정확성을 한번에 나타내는 지표라 할 수 있다. 

보통 가중치를 가진 조화 평균(weighted harmonic mean)이라고도 한다. 


조화 평균

일반적으로 계산하는 평균은 산술 평균(Arithmetic Mean)이라고 한다. 

조화 평균(Harmonic Mean)은 주어진 수들의 역수의 산술 평균을 구한 값의 역수를 말한다. 



조화 평균은 평균속력을 구할 때 주로 사용한다. 

예를 들어, 똑같은 거리를 갈 때는 40 km/h의 속력이었고, 올 때는 60 km/h였다고 하자. 

왕복 평균 속력은 50 km/h가 아니라 조화 평균값인 48 km/h가 된다. 

왜냐하면 이동하는데 걸린 시간은 평균 48 km/h로 달린 시간과 동일하기 때문이다. 


두 수 사이의 조화 평균은 다음과 같다. 



F-Measure 수식

F-Measure를 구하기 위해 Precision과 Recall에 대한 조화 평균에 가중치 알파를 적용하면 다음과 같다. 



여기에서 Precision과 Recall에 적용한 가중치를 0.5로 동일하게 부여하면, 우측 식의 베타 값은 1이 된다. 

이것을 F1 Measure라 하고 자주 사용하는 F-Measure 값이기도 하다. 

아래 수식을 보면 앞의 두 수 사이의 조화 평균과 동일한 것을 알 수 있다. 



F-Measure 활용

F1 Measure는 Precision과 Recall의 중요성을 동일하게 보고 있다. 

만약 Recall이 Precision보다 더 중요하다면 F2 Measure를, Precision이 Recall보다 더 중요하다면 F0.5 Measure를 사용할 수 있다. 

여기서 2나 0.5는 베타의 값이라는 것을 기억해 두기 바란다. 


G-Measure

조화 평균과 함께 자주 이야기하는 것으로 기하 평균(Geometric Mean)이 있다. 

마찬가지로 F-Measure대신 기하 평균을 활용한 G-Measure도 사용할 수 있다고 한다. 

하지만 보통 F-Measure를 주로 사용하니 참고하기 바란다. 



마지막으로 Precision, Recall, F-Measure에 대한 다음 동영상 강의를 참고하자.







Trackback 0 And Comment 0

정확도와 재현율 (Precision and Recall)에 대하여~

|



정보검색이나 패턴인식에서 정확도(Precision)과 재현율(Recall)이라는 용어를 자주 사용한다. 

기계학습에서도 정확도와 재현율에 기반해서 예측의 정확성을 검증하기도 하므로 기본적인 개념을 살펴보도록 한다. 


정보검색에서의 정확도와 재현율

만약 정보검색을 위해 100개의 문서를 색인한 "미니" 검색엔진이 있다고 가정해 보자. 

여기에 "빅데이터"란 키워드로 검색을 했는데, 검색 결과로 20개의 문서가 나왔다.

20개의 문서 중 16개의 문서가 실제로 "빅데이터"와 관련된 문서였고, 

전체 100개의 문서 중 "빅데이터"와 관련된 문서는 총 32개라고 하자. 


이 경우, 정확도(precision)와 재현율(recall)은 어떻게 될까?  

정확도는 검색 결과로 가져온 문서 중 실제 관련된 문서의 비율로 나타낸다. 



그리고 재현율은 관련된 문서 중 검색된 문서의 비율로 나타낸다. 



위 예제에 이 식을 적용하면, 정확도와 재현율은 다음과 같다. 

정확도 = 16/20 = 0.8

재현율 = 16/32 = 0.5


기계학습에서의 정확도와 재현율

통계에 기반을 둔 기계학습에서도 모델이나 패턴을 통한 예측을 수행할 때, 정확도와 재현율을 활용한다. 

실험 결과와 실제 정답 사이의 관계를 아래와 같이 나타낼 수 있다. 



True Positive와 True Negative는 실험 결과 정답을 맞춘 것이고, 

False Positive는 True로 예측했지만 False 경우이고, False Negative는 False로 예측했지만 True인 경우를 나타낸다. 


이 경우의 정확도와 재현율은 다음과 같다. 




정확도는 True로 예측한 것 중에서 실제 True인 것의 비율로 보면 되고, 

재현율은 실제 True인 것 중에서 True로 예측한 것의 비율로 보면 된다. 


위의 정보검색에서 분모가 검색된 문서(정확도)와 관련된 문서(재현율)에 따라 다르듯이, 

통계에서도 분모가 예측한 결과 True인 것(정확도)인지 실제 True인 것(재현율)인지에 따라 다른 것이다. 


그러나 정확도와 재현율의 두 가지 값으로 예측 결과의 정확성을 나타내면 복잡하므로 

이 둘의 비율을 조합한 하나의 새로운 값이 필요하게 되었다. 

그것이 바로 F-Measure이다. 

다음에는 이 F-Measure에 대해 세부적으로 정리해 보기로 한다. 





Trackback 0 And Comment 0

몬테카를로 시뮬레이션~

|



분석을 하면서 "몬테카를로 시뮬레이션"을 한번쯤은 들어봤을 것이다. 

몬테카를로는 무작위 값을 활용하여 확률적으로 계산하는 알고리즘을 이야기한다. 

이렇게 확률적으로 계산함으로써 원하는 수치의 확률적 분포를 구할 수 있게 된다. 

이를 위해 많은 수의 실험을 바탕으로 한 통계를 이용해 확률적 분포를 알게 되므로, 이것을 바로 몬테카를로 시뮬레이션이라고 한다. 


몬테카를로 시뮬레이션 개념

몬테카를로는 통계 자료가 많고 입력값의 분포가 고를수록 정밀하게 시뮬레이션 할 수 있다. 

그래서 컴퓨터를 이용해 시뮬레이션을 주로 한다. 

또한 이론적 배경이나 복잡한 수식으로 계산해야 하는 경우, 근사치를 계산하기 위해서도 몬테카를로를 많이 사용한다. 


몬테카를로 시뮬레이션은 모나코의 유명한 도박 도시이름을 따서 만들었다고 한다. 

초기 도박사들이 여러번의 임의 추출을 바탕으로 특정한 카드 조합이 나올때까지 계산했다고 한다. 



또한 폰 노이만은 원자폭탄 개발 계획인 맨해탄 프로젝트에서 중성자 확산 시뮬레이션에 이 기법을 사용했다고 한다. 

최근에도 위험관리, 품질관리, 금융공학 등에서도 몬테카를로를 널리 사용한다. 


몬테카를로 시뮬레이션 예제

몬테카를로는 임의의 수를 반복적으로 발생시켜서 계산하는 방식이다. 

위키피디아에 따르면 몬테카를로 시뮬레이션은 다음과 같은 절차를 따른다고 되어 있다. 


1. Define a domain of possible inputs. (입력값의 범위를 정한다.)

2. Generate inputs randomly from a probability distribution over the domain. (확률분포에 따라 입력값을 랜덤하게 만든다.)

3. Perform a deterministic computation on the inputs. (입력값에 대한 계산을 한다.)

4. Aggregate the results.(계산 결과를 통합한다.)


절차만 보면 그리 어려워보이지 않지만, 실제 적용하려면 난감한 것이 사실이다. 

그래서 위키피디아의 원주율 파이를 구하는 예제를 통해서 설명해 보려고 한다. 



원주율 파이 값을 구하기 위한 많은 수학적 알고리즘이 있다. 

"아르키메데스의 부등식", "비에타의 공식", "라이프니츠 급수", "마친의 공식", "오일러의 공식", "BBP 공식"등 ...


그리고 실제 값은 다음과 같다고 한다. 

π=3.141592653589793238462643383279502884197169399375⋯


몬테카를로 시뮬레이션으로 파이 값을 어떻게 구할까?

1. 정사각형을 그리고 그 안에 원을 그린다.  

2. 정사각형 안에 수많은 점을 고르게 분포한다. 

3. 분포한 전체 점의 개수와 원 안에 분포한 점의 개수를 센다. 

4. 전체 점의 개수(N)과 원 안의 점 개수(n)의 비율로 원주율 파이를 계산한다. 


다음 그림을 보면 쉽게 이해할 수 있을 것이다. 

가로와 세로의 길이가 2인 정사각형을 그리면, 사각형의 넓이는 2x2 = 4가 된다. 

그리고 수많은 임의의 점을 만들어서 원점으로부터 거리가 1이내인지를 확인하면 원 안에 분포하는지를 알 수 있다. 

원의 넓이는 "파이 x 반지름의 제곱"이므로 위 예제에서는 반지름이 1이므로 원의 넓이가 곧 파이값이 된다. 

그러므로 사각형의 넓이와 원의 넓이의 비율을 계산하면 원주율 파이가 나온다는 것이다. 


1개 점으로 하면 0 또는 4가 나올 것이다. 

그러나 100,000 정도의 점으로 하면 원주율 파이와 비슷한 3.14xxx 값이 나오게 된다. 


몬테카를로 시뮬레이션은 불확실성을 확률 분포에 의해 해결하기 위해서 데이터 분석에서도 많이 사용한다. 

이것도 일반적인 데이터 분석과 마찬가지로 미리 가정을 수립하고, 시뮬레이션과 같은 실험으로 이를 증명해 나가는 것이다. 





Trackback 0 And Comment 0

Nonparametric Method - 평균/분산을 모를때 확률분포를 만드는 방법

|



지금까지 살펴본 확률분포는 모두 평균이나 분산과 같은 매개변수들을 기반으로 확률분포를 정하게 됩니다. 

예를 들어, 정규분포(Normal Distribution)에서는 평균과 분산을 알고서 확률분포를 구하게 되죠.. 



그런데 만약 평균과 분산과 같은 매개변수를 모를 경우, 확률 분포를 어떻게 알 수 있을까요?

특히 정규분포와 달리 여러개의 봉으로 이루어진 데이터라면, 기존의 방식으로 확률 분포를 알수는 없을 겁니다. 

이렇게 매개변수가 없을 때, 확률 분포를 구하는 방법을 Nonparamtric Method라고 합니다. 

(보통 비모수적 방법이라고 이야기 하는 것 같습니다.)


Nonparametric Method는 보통 Histogram, Kernel Density, Nearest Neighbour 세가지가 있는데요. 

각각에 대해서 간략하게 정리해보도록 하겠습니다. 


Histogram Density Model

히스토그램은 많이 들어봤을 겁니다. 

막대그래프와 달리 각 영역이 붙어 있는 것이 특징인데요. 

바로 이 영역의 넓이를 Δ라고 하는데, 이 Δ값에 따라서 확률 분포가 결정되게 됩니다.



위 그림과 같이 초록색과 같은 데이터 분포에 대해, 히스토그램을 그려보면 Δ값에 따라 다르게 나타나는 것을 알 수 있습니다. 

원래 데이터는 봉이 두개인 그래프인데요.. 

Δ값이 너무 작거나 너무 크면 해당 그래프의 모습을 반영하지 못하고 있습니다. 

위 그림에서는 Δ값이 0.08일때, 적절하게 확률 분포를 나타내 주고 있는 것을 알 수 있습니다. 

이와같이 적절한 Δ의 값을 결정하는 것은 Histogram Density Model에서는 중요한 부분이라 할 수 있습니다. 


하지만 히스토그램은 빠르고 쉽게 그릴 수 있다는 장점이 있지만 다음과 같은 문제점도 가지고 있습니다. 

먼저 경계값에 데이터가 몰려 있을 경우, 제대로 확률분포를 만들어 내지 못할 수 있습니다. 

그리고 예전에 Curve Fitting에서 Dimension의 저주라고 이야기한 것처럼, 차원이 늘어날 수록 문제가 발생하게 됩니다. 

(2013/04/22 - [Cloud&BigData/Machine Learing] - Curve Fitting으로 살펴보는 Frequentest와 Bayesian Treatment)


이러한 문제를 해결하기 위해 Kernel density나 Nearest neighbour 를 사용하게 됩니다. 


Kernel Density Estimators

Kernel Density는 히스토그램의 경계 문제를 해결한 것인데요. 

어떤 값 x가 R이라고 하는 영역에 들어갈 확률을 P라고 하면 다음과 같이 나타낼 수 있습니다. 



이때 전체 N 중에서 K개가 R에 들어갈 확률을 P라고 하면, 앞서 배운 Binomial Distribution이 되고 기대값은 다음과 같이 나타낼 수 있습니다. 



만약 N이 상당히 크다고 가정하면 다음과 같이 이야기할 수 있습니다. 


 

또한 전체 확률 P는 개별적인 확률인 p(x)와 R의 볼륨을 V라고 하면 둘의 곱으로 나타낼 수 있습니다. 



위 두 식을 결합하면 다음과 같이 p(x)를 나타낼 수 있습니다. 



여기에서 K를 고정해놓고 V값을 결정해서 확률분포를 알아내는 것이 K-nearest-neighbour 방식이고, 

V를 고정해 놓은 상태에서 K값을 결정해서 확률분포를 만드는 것을 Kernel 방식이라고 합니다. 


Kernel 방식에서 K값을 결정하기 위해서 다음과 같은 수식을 사용합니다. 

Xn이 X를 중심으로 h라는 큐브 영역에 들어가는지 확인하는 것입니다. 

이러한 Kernel function을 Parzen window라고 한다네요.. 



이 식을 위 p(x)를 구하는 곳에 대입하면 다음과 같습니다. 

V를 hD로 표시해서 점 하나가 아닌 전체를 고려한 것이라고 보면 됩니다. 



원래 목적이었던 경계값 측면에서 보면 이 식도 h라는 영역에 들어가면 1, 아니면 0이 되므로 약간 보정할 필요가 있습니다. 

만약 정규분포와 같은 수식을 활용하면 경계값에 들어가느냐 아니냐를 판단하기 보다 얼마나 가까운지로 결정할 수 있으므로 

히스토그램의 경계값 문제를 어느정도 해결한다고 생각해도 됩니다. 

정규분포의 수식으로 대체한 것은 너무 복잡하니 생략할 께요. 


히스토그램이 Δ값에 영향을 받은 것처럼, Kernel 방식도 h 값에 의해 Fitting이 다음과 같이 달라집니다. 



Nearest-neighbour methods

이름 그대로 가까운 것을 찾아서 확률분포를 구성하는 것입니다. 

앞의 식에서 K를 정해놓고 V(volumn)을 늘려가면서 결정하는 방식이 바로 Nearest-neighbour 입니다. 

쉽게 설명하면 점 x가 있는데, 주위에 K/3가 빨간점이고 2K/3가 파란점이라면 x를 파란점으로 판단하는 것이죠. 

이럴 경우, K가 바로 영역의 크기를 나타내게 되는데요.. 

K를 어떻게 고정하느냐에 따라서 판단 영역의 차이가 발생하게 됩니다. 


 

x가 주어졌을 때, 클래스에 속할 확률을 구하는 것은 베이즈 정리를 잘 활용하면 되겠죠. 

이 부분은 이전의 의사결정이론에서도 한번 다뤘기 때문에 해당 내용을 참고해 보기 바랍니다. 


실제로 K값에 따른 확률분포를 구성하면 다음과 같습니다. 






Trackback 0 And Comment 0

Multinomial Variables - 다항 분포와 Dirichlet 분포에 대하여

|



Binary Variables에 이어 Multinomial에 대해서 정리해 보도록 하죠. 

Binary가 동전의 앞면/뒷면과 같은 경우를 이야기한다면, Multinomial은 주사위를 던지는 경우를 생각하면 될 것 같습니다. 

즉 K=6의 상태를 가지고 있고, X3 = 1인 경우, 다음과 같이 나타낼 수 있습니다. 



확률이므로 K=1부터 6까지의 X의 전체 합은 1이 되겠죠. 

독립이므로 여러번 주사위를 던질때 확률은 다음과 같이 곱으로 계산할 수 있습니다. 

(k에 대한 평균이 파라미터로 주어졌을 때, Xk가 나올 확률을 의미합니다.)



이때, 파라미터로 사용하는 평균은 다음과 같은 조건을 가지고 있습니다. 



이번에는 X1에서 Xn까지의 독립 관측에서의 데이터 셋을 D라고 할 때, 다음과 같은 likelihood 함수를 생각할 수 있습니다. 

Binary Variables와 비교해서 보면 이해가 잘 될 겁니다. (결과가 나오는 중간 과정은 생략했습니다.)


     

이어서 Maximum likelihood를 계산하기 위해서 로그(ln)를 취하고 미분해서 계산하면 되겠죠. 

(이 경우에도 조건들을 명확하게 하기 위해 Lagrange multiplier인 람다를 사용합니다.)

최종적으로 maximum likelihood는 다음과 같은 식으로 나옵니다. 



Multinomial Distribution (다항 분포)

이항 분포 (Binomial Distribution)과 비교해서 비슷한 Multinomial Distribution을 만들 수 있습니다. 

경우의 수 계산을 위해 순서에 상관없으므로 조합을 사용하고, 위의 조건부 확률을 곱해주면 되겠죠. 



Dirichlet Distribution 

Binomial에 대응하는 것이 Multinomial이라면, 

Beta에 대응하는 분포가 바로 Dirichlet 라고 할 수 있습니다. 

이와 관련해서는 Conjugate Prior와 다음 그림을 살펴보기 바랍니다. 



Dirichlet 분포의 공식은 다음과 같습니다. 



위 그림에서 보는 것처럼 likelihood로 Multinomial이 사용되고, Prior로 Dirichlet를 사용하면, 

Posterior도 계속 Dirichlet가 나오면서 Bayesian을 보다 쉽게 사용할 수 있다고 합니다. 





Trackback 0 And Comment 1
  1. 미니~ 2013.08.11 15:17 신고 address edit & del reply

    다음 글을 참고하면 좋을 듯 합니다.
    http://www.4four.us/article/2010/11/latent-dirichlet-allocation-simply

prev | 1 | 2 | next