의사결정나무(Decision Tree) + ID3 알고리즘

인공지능에 학습방법 중 지도학습이 있는데, 지도학습이란❓

정답이 있는 데이터를 가지고 학습을 시켜, 새로운 데이터의 결과를 예측하는 방법이다.

지도학습 종류 중 하나가 의사결정나무(Decision Tree)이다.

📌 의사결정나무(Decision Tree)란❓

아무것도 모르는 상태에서 정답이 있는 데이터를 제시해주고,
제시해준 데이터에서 특징을 찾아 조건문을 제시해 트리를 만들고,
테스트 데이터를 보여주면서 스스로 대답할 수 있는지 확인한다.

음,, 뭔말이져?🤔

예를들어 이미지가 주어지는데 바다 vs 산? 바다에서 해안도로 vs 해수욕장인지 알아내야한다고 가정하자.

아무것도 모르는 AI가 어떻게 알 수 있나?

제시해준 데이터들을 분석해 특징을 찾아낸다. 특징 차이가 가장 큰 값부터 분류하기 시작한다.
세부 특징 차이로 트리가 내려가면서 분류한다.

테스트 데이터를 제시했을때 분류했던 조건으로 테스트 데이터의 결과값을 추출해낸다.

                   ┌────────────────────────────┐
                   │       파란색 비율 > 50% ?     │
                   └────────────────────────────┘
                        /                   \
                      바다                    산
                       |                     
         ┌───────────────────────┐ 
         │      도로 패턴 있음?     │ 
         └───────────────────────┘ 
                /           \      
            해안도로         해수욕장

더 뭔말인지 모르겠는데요..

먼저, 파란색 비율을 조건처리하면서 바다와 산을 구분했다.
만약 도로패턴을 먼저 조건처리 했다면?
도로패턴이 있으면 해안도로로 가정했을것이고, 없다면 파란색 비율을 가지고 바다와 산을 분류했을 것이다.

근데!!!! 도로패턴을 가지고 있는 산이면??? 해안도로로 결과 값이 나오게 된다.

특징 차이가 가장 큰 조건부터 처리한다는 것이 바로 이것때문.
가장 큰 차이인 파란색 비율을 가지고 조건처리를 하여 산과 바다를 분류하고 바다 중에서 도로 패턴이 있는 해안도로를 분류하면 더 정확한 결과 값이 추출될 수 있다.

음,,, 일단 의사결정나무? 알겠어요. ID3는 뭔데요?

📌 ID3 알고리즘이란 ❓

의사결정트리에서 데이터들의 분류할 때 사용하는 가장 대표적인 알고리즘이다.
 ID3 알고리즘은 특징 차이가 가장 큰 조건이 무엇인지 찾아내는 알고리즘이에요. 찾아내기 위해서는 Entropy와 Information Gain을 알아야해요.

Information Gain 계산 수치를 가지고 특징을 분리 할 수 있는 조건이 되는지 안되는지 파악하는데 Information Gain을 계산하기 전에 Entropy를 알고 있어야해요.

Entropy 란 ⁉️

데이터의 불순도를 나타내는데 제시해준 데이터들의 규칙이 명확한지? 아님 알 수 없는 규칙들인지? 파악할 수 있는 수치에요.
Entropy가 낮으면 규칙이 있지만 한쪽으로 치우쳐져있고, 높으면 규칙이 거의 없다는 걸 말합니다.

어떠한 특징을 가지고 규칙성이 있는지 여부를 판단하게 되는거죠.
한 번의 계산으로 끝나는게 아니라 여러번 계산을 통해서 여러 특징을 찾아내는 형태라고 이해했습니다.
잘못 이해했다면 댓글로 알려주세요 ㅎㅎ

Entropy 계산은 아래와 같이 볼 수 있다.
p(+)와 p(-)는 규칙 A로 나누었을 때 분류되는 그룹으로 파란색 많은 그룹 vs 없는 그룹 수치이다.

$$
Entropy = -p(+) \log_2(p(+)) - p(-) \log_2(p(-))
$$

해당 값을 가지고 Information Gain 값을 추출해낼 수 있다. Information Gain은 Entropy에서 찾아낸 특징, 규칙들을 가지고 어떤 규칙이 가장 분류하기 좋고 어떤 규칙이 세부적인 분류 조건인지 파악할 수 있다.

Information Gain 계산법은 주어진 규칙에 대한 Entropy - 하나의 규칙 Entropy으로 계산한다.

$$
IG(S, A) = Entropy(S) - \Big( \frac{|S_{+}|}{|S|} \times Entropy(S_{+}) + \frac{|S_{-}|}{|S|} \times Entropy(S_{-}) \Big)
$$

 

이렇게 계산한 수치들을 가지고 첫번째 규칙을 찾아내고 최상위 트리를 찾아낸 뒤,
하위 규칙들을 찾아내면서 트리를 만들어내는 형태를 의사결정트리 알고리즘이라고 한다.

혹시 잘못된 내용이 있으면 댓글 부탁드립니다🙌