1. 베이즈 확률로 위치 예측하기 “실종된 난파선 선원을 찾아라”

221017 작성

<본 블로그는실전 파이썬 핸즈온 프로젝트의 github 를 참고해서 공부하며 작성하였습니다>

https://www.onlybook.co.kr/m/entry/python-projects

실전 파이썬 핸즈온 프로젝트

https://github.com/rlvaugh/Real_World_Python

GitHub - rlvaugh/Real_World_Python: Code and supporting files for book Real World Python

 

 

💕 베이즈 정리

조건부확률

: 데이터라는 조건이 주어졌을 때의 조건부확률을 구하는 공식

: 데이터가 주어지기 전의 사전확률값이 데이터가 주어지면서 어떻게 변하는지 계산

=> 데이터가 주어지기 전에 이미 어느 정도 확률값을 예측하고 있을 때 이를 새로 수집한 데이터와 합쳐서 최종 결과에 반영

=> 매일 전체 데이터를 대상으로 새로 분석작업을 할 필요없이 어제 분석결과에 오늘 들어온 데이터를 합쳐서 업데이트만 하면 되므로 유용하게 활용

 

• P(A|B): 사후확률(posterior). 사건 B가 발생한 후 갱신된 사건 A의 확률
• P(A): 사전확률(prior). 사건 B가 발생하기 전에 가지고 있던 사건 A의 확률
• P(B|A): 가능도(likelihood). 사건 A가 발생한 경우 사건 B의 확률
• P(B): 정규화 상수(normalizing constant) 또는 증거(evidence). 확률의 크기 조정

 

💕 베이즈 확률로 위치 예측하기 - “실종된 난파선 선원을 찾아라”

: 파이썬만에서 발생한 실종 사건에서 해안 경비대가 효율적으로 탐색과 구조 임무를 수행하도록, 베이즈 확률 규칙을 사용해 돕는다

: OpenCV, NumPy, itertools 모듈을 활용한다

import sys
import random
import itertools
import numpy as np
import cv2 as cv

MAP_FILE = 'cape_python.png'

# 이미지 픽셀을 기반으로 검색 영역(SA) 모서리 지점 위치를 지정
SA1_CORNERS = (130, 265, 180, 315)  # (UL-X, UL-Y, LR-X, LR-Y)
SA2_CORNERS = (80, 255, 130, 305)   # (UL-X, UL-Y, LR-X, LR-Y)
SA3_CORNERS = (105, 205, 155, 255)  # (UL-X, UL-Y, LR-X, LR-Y)


# """3개의 수색 영역이 있는 베이지안 수색 및 구조 게임."""
class Search():
    """Bayesian Search & Rescue game with 3 search areas."""

    def __init__(self, name):
        self.name = name
        self.img = cv.imread(MAP_FILE, cv.IMREAD_COLOR)
        if self.img is None:
            print('Could not load map file {}'.format(MAP_FILE),
                  file=sys.stderr)
            sys.exit(1)

        # 선원의 실제 위치에 대한 자리 표시자 설정
        self.area_actual = 0
        self.sailor_actual = [0, 0]  # 검색 영역 내 "로컬" 좌표로

        # 이미지 배열을 인덱싱하여 각 검색 영역에 대해 numpy 배열을 만듭니다.
        self.sa1 = self.img[SA1_CORNERS[1] : SA1_CORNERS[3],
                            SA1_CORNERS[0] : SA1_CORNERS[2]]

        self.sa2 = self.img[SA2_CORNERS[1] : SA2_CORNERS[3],
                            SA2_CORNERS[0] : SA2_CORNERS[2]]

        self.sa3 = self.img[SA3_CORNERS[1] : SA3_CORNERS[3], 
                            SA3_CORNERS[0] : SA3_CORNERS[2]]

        # 선원을 찾기 위한 초기 지역별 목표 확률 설정
        self.p1 = 0.2
        self.p2 = 0.5
        self.p3 = 0.3

        # 검색 효과 확률을 초기화
        self.sep1 = 0
        self.sep2 = 0
        self.sep3 = 0



# """표시, 마지막으로 알려진 xy 위치, 검색 영역으로 베이스맵을 표시"""
    def draw_map(self, last_known):
        """Display basemap with scale, last known xy location, search areas."""
        # Draw the scale bar.
        cv.line(self.img, (20, 370), (70, 370), (0, 0, 0), 2)
        cv.putText(self.img, '0', (8, 370), cv.FONT_HERSHEY_PLAIN, 1, (0, 0, 0))
        cv.putText(self.img, '50 Nautical Miles', (71, 370),
                   cv.FONT_HERSHEY_PLAIN, 1, (0, 0, 0))
            # cv.FONT_HERSHEY_PLAIN : 이미지에 글자 합성

        # Draw and number the search areas.
        cv.rectangle(self.img, (SA1_CORNERS[0], SA1_CORNERS[1]),
                     (SA1_CORNERS[2], SA1_CORNERS[3]), (0, 0, 0), 1)
        cv.putText(self.img, '1',
                   (SA1_CORNERS[0] + 3, SA1_CORNERS[1] + 15),
                   cv.FONT_HERSHEY_PLAIN, 1, 0)

        cv.rectangle(self.img, (SA2_CORNERS[0], SA2_CORNERS[1]),
                     (SA2_CORNERS[2], SA2_CORNERS[3]), (0, 0, 0), 1)
        cv.putText(self.img, '2',
                   (SA2_CORNERS[0] + 3, SA2_CORNERS[1] + 15),
                   cv.FONT_HERSHEY_PLAIN, 1, 0)

        cv.rectangle(self.img, (SA3_CORNERS[0], SA3_CORNERS[1]),
                     (SA3_CORNERS[2], SA3_CORNERS[3]), (0, 0, 0), 1)
        cv.putText(self.img, '3',
                   (SA3_CORNERS[0] + 3, SA3_CORNERS[1] + 15),
                   cv.FONT_HERSHEY_PLAIN, 1, 0)

        # 마지막으로 알려진 선원의 위치를 ​​게시
        cv.putText(self.img, '+', (last_known),
                   cv.FONT_HERSHEY_PLAIN, 1, (0, 0, 255))
        cv.putText(self.img, '+ = Last Known Position', (274, 355),
                   cv.FONT_HERSHEY_PLAIN, 1, (0, 0, 255))
        cv.putText(self.img, '* = Actual Position', (275, 370),
                   cv.FONT_HERSHEY_PLAIN, 1, (255, 0, 0))

        cv.imshow('Search Area', self.img)
        cv.moveWindow('Search Area', 750, 10)
        cv.waitKey(500)


# """실종된 선원의 실제 x,y 위치를 반환"""
    def sailor_final_location(self, num_search_areas):
        """Return the actual x,y location of the missing sailor."""
        # 검색 영역 하위 배열에 대한 선원 좌표를 찾습니다.
        self.sailor_actual[0] = np.random.choice(self.sa1.shape[1])
        self.sailor_actual[1] = np.random.choice(self.sa1.shape[0])

        # 무작위로 검색 영역을 선택
        area = int(random.triangular(1, num_search_areas + 1))

        # 지역 검색 지역 좌표를 지도 좌표로 변환
        if area == 1:
            x = self.sailor_actual[0] + SA1_CORNERS[0]
            y = self.sailor_actual[1] + SA1_CORNERS[1]
            self.area_actual = 1

        elif area == 2:
            x = self.sailor_actual[0] + SA2_CORNERS[0]
            y = self.sailor_actual[1] + SA2_CORNERS[1]
            self.area_actual = 2

        elif area == 3:
            x = self.sailor_actual[0] + SA3_CORNERS[0]
            y = self.sailor_actual[1] + SA3_CORNERS[1]
            self.area_actual = 3
        return x, y


# """검색 영역별로 소수(or 십진법의) 검색 효율성 값을 설정"""
    def calc_search_effectiveness(self):
        """Set decimal search effectiveness value per search area."""
        self.sep1 = random.uniform(0.2, 0.9)
        self.sep2 = random.uniform(0.2, 0.9)
        self.sep3 = random.uniform(0.2, 0.9)


# """검색 결과와 검색된 좌표 목록을 반환"""
    def conduct_search(self, area_num, area_array, effectiveness_prob):
        """Return search results and list of searched coordinates."""
        local_y_range = range(area_array.shape[0])
        local_x_range = range(area_array.shape[1])
        coords = list(itertools.product(local_x_range, local_y_range))
        random.shuffle(coords)
        coords = coords[:int((len(coords) * effectiveness_prob))]
        loc_actual = (self.sailor_actual[0], self.sailor_actual[1])
        if area_num == self.area_actual and loc_actual in coords:
            return 'Found in Area {}.'.format(area_num), coords
        return 'Not Found', coords


# """검색 효율성에 따라 지역 타겟 확률을 업데이트"""
    def revise_target_probs(self):
        """Update area target probabilities based on search effectiveness."""
        denom = self.p1 * (1 - self.sep1) + self.p2 * (1 - self.sep2) \
                + self.p3 * (1 - self.sep3)

        self.p1 = self.p1 * (1 - self.sep1) / denom
        self.p2 = self.p2 * (1 - self.sep2) / denom
        self.p3 = self.p3 * (1 - self.sep3) / denom


# """지역 검색을 수행하기 위한 선택 메뉴를 출력"""
def draw_menu(search_num):
    """Print menu of choices for conducting area searches."""
    print('\nSearch {}'.format(search_num))
    print(
        """
        Choose next areas to search:
        0 - Quit
        1 - Search Area 1 twice
        2 - Search Area 2 twice
        3 - Search Area 3 twice
        4 - Search Areas 1 & 2
        5 - Search Areas 1 & 3
        6 - Search Areas 2 & 3
        7 - Start Over
        """
        )


def main():
    app = Search('Cape_Python')
    # 표시, 마지막으로 알려진 xy 위치, 검색 영역으로 베이스맵을 표시
    app.draw_map(last_known=(160, 290))
    
    # 실종된 선원의 실제 x,y 위치를 반환
    sailor_x, sailor_y = app.sailor_final_location(num_search_areas=3)
    print("-" * 65)
    print("\nInitial Target (P) Probabilities:")
    
    # 선원을 찾기 위한 초기 지역별 목표 확률 설정
    print("P1 = {:.3f}, P2 = {:.3f}, P3 = {:.3f}".format(app.p1, app.p2, app.p3))
    search_num = 1

    while True:
        # 검색 영역별로 소수(or 십진법의) 검색 효율성 값을 설정
        app.calc_search_effectiveness()
        draw_menu(search_num)
        choice = input("Choice: ")

        # 0 - Quit
        if choice == "0":
            sys.exit()

        # 1 - Search Area 1 twice
        elif choice == "1":
            results_1, coords_1 = app.conduct_search(1, app.sa1, app.sep1)
            results_2, coords_2 = app.conduct_search(1, app.sa1, app.sep1)
            app.sep1 = (len(set(coords_1 + coords_2))) / (len(app.sa1)**2)
            app.sep2 = 0
            app.sep3 = 0

        # 2 - Search Area 2 twice
        elif choice == "2":
            # 검색 결과와 검색된 좌표 목록을 반환
            results_1, coords_1 = app.conduct_search(2, app.sa2, app.sep2)
            results_2, coords_2 = app.conduct_search(2, app.sa2, app.sep2)
            app.sep1 = 0
            app.sep2 = (len(set(coords_1 + coords_2))) / (len(app.sa2)**2)
            app.sep3 = 0

        # 3 - Search Area 3 twice
        elif choice == "3":
            results_1, coords_1 = app.conduct_search(3, app.sa3, app.sep3)
            results_2, coords_2 = app.conduct_search(3, app.sa3, app.sep3)
            app.sep1 = 0
            app.sep2 = 0
            app.sep3 = (len(set(coords_1 + coords_2))) / (len(app.sa3)**2)

        # 4 - Search Areas 1 & 2
        elif choice == "4":
            results_1, coords_1 = app.conduct_search(1, app.sa1, app.sep1)
            results_2, coords_2 = app.conduct_search(2, app.sa2, app.sep2)
            app.sep3 = 0

        # 5 - Search Areas 1 & 3
        elif choice == "5":
            results_1, coords_1 = app.conduct_search(1, app.sa1, app.sep1)
            results_2, coords_2 = app.conduct_search(3, app.sa3, app.sep3)
            app.sep2 = 0

        # 6 - Search Areas 2 & 3
        elif choice == "6":
            results_1, coords_1 = app.conduct_search(2, app.sa2, app.sep2)
            results_2, coords_2 = app.conduct_search(3, app.sa3, app.sep3)
            app.sep1 = 0

        # 7 - Start Over
        elif choice == "7":
            main()

        else:
            print("\nSorry, but that isn't a valid choice.", file=sys.stderr)
            continue
        
        # 검색 효율성에 따라 지역 타겟 확률을 업데이트
        app.revise_target_probs()  # Bayes의 규칙을 사용하여 대상 확률을 업데이트

        print("\nSearch {} Results 1 = {}"
              .format(search_num, results_1), file=sys.stderr)
        print("Search {} Results 2 = {}\n"
              .format(search_num, results_2), file=sys.stderr)

        print("Search {} Effectiveness (E):".format(search_num))
        print("E1 = {:.3f}, E2 = {:.3f}, E3 = {:.3f}"
              .format(app.sep1, app.sep2, app.sep3))

        # 선원이 발견되지 않으면 목표 확률을 출력. 그렇지 않으면 위치를 표시
        if results_1 == 'Not Found' and results_2 == 'Not Found':
            print("\nNew Target Probabilities (P) for Search {}:"
                  .format(search_num + 1))
            print("P1 = {:.3f}, P2 = {:.3f}, P3 = {:.3f}"
                  .format(app.p1, app.p2, app.p3))
        else:
            cv.circle(app.img, (sailor_x, sailor_y), 3, (255, 0, 0), -1)
            cv.imshow('Search Area', app.img)
            cv.waitKey(1500)
            main()
        search_num += 1

if __name__ == '__main__':
    main()