의사결정나무_1 개념

안녕하세요 배도리입니다. 오늘은 의사결정나무(Decision Tree)에 대해서 배워보겠습니다.

 

의사결정 나무 개념

의사결정나무(Decision Tree)는 결정 규칙을 통해 데이터를 분류하거나 회귀분석하는 모델입니다. 이 알고리즘은 데이터를 분석하여 데이터의 패턴을 찾아나가는 과정이 '스무고개' 게임과 비슷하기 때문에 이런 이름이 붙었습니다. 그리고 그 과정을 트리 구조로 시각화하여 이해하기 쉽게 표현할 수 있습니다.

트리의 각 노드는 하나의 특징(feature)에 대한 검사를 나타내고, 각 분기(branch)는 그 특징에 대한 가능한 결과를 나타냅니다. 이런 방식으로, 데이터는 루트 노드에서 시작하여 각 노드의 검사를 통과하며 트리를 타고 내려갑니다. 마지막으로 도달한 리프 노드는 해당 데이터의 예측 클래스(분류 문제의 경우) 또는 예측 값(회귀 문제의 경우)을 나타냅니다.

의사결정나무 알고리즘은 입력 변수를 이용해 목표 변수의 값을 예측하는 데에 목적이 있습니다. 따라서 적절한 분리 기준(질문)과 정지 규칙(트리의 깊이)을 정하여 모델을 구성해야 합니다. 분리 기준은 각 노드에서 데이터를 어떻게 분할할지를 결정하고, 정지 규칙은 트리의 성장을 언제 멈출지를 결정합니다.

 

스무고개 예시

 

장점

의사결정나무의 장점은 다음과 같습니다. 
이해하기 쉽다! 의사결정나무는 간단한 If-then 규칙에 기반한 나무 구조를 가지므로 모델을 이해하기 쉽습니다. 그래프 형태로 시각화가 가능해 어떻게 결정이 이루어지는지를 직관적으로 볼 수 있습니다.

중요 변수 선택에 유용하다! 나무의 상단에 위치하는 설명 변수는 그 변수가 중요하다는 것을 의미합니다. 이는 해당 변수가 데이터 분류에 있어 높은 변별력을 가지는 결정적 요소임을 나타냅니다.

데이터의 통계적 가정이 필요 없다! 이전에 배운 선형 판별 분석(LDA)은 데이터가 정규 분포를 따르는 것을 가정해야 하지만, 의사결정나무는 이런 가정이 필요 없습니다.

의사결정 과정에 대한 설명 가능하다! 예를 들어 야구 경기가 취소된 경우, 의사결정나무를 통해 어떤 변수가 가장 중요한 역할을 했는지를 쉽게 이해하고 설명할 수 있습니다.

전반적인 모양은 뒤집힌 나무와 같습니다. 뿌리 노드에서 시작하여 분기가 거듭될수록 해당 분기에 속하는 데이터의 수는 줄어듭니다(내려갈수록 경기진행수가 줄어드는중). 각 잎 노드(종단 노드)에 속하는 데이터 수의 총합은 뿌리 노드의 데이터 수와 일치합니다(총 경기진행 10, 맑은날 3, 흐린날 4 비오는날 3 합하면 10). 이는 잎 노드 간에는 데이터의 교집합이 없음을 의미하며 잎 노드의 수는 분리된 데이터 집합의 수와 같습니다.

 

단점

그러나 역시 의사결정나무의 단점은 존재합니다.
좋은 모델을 만들기 위해 많은 데이터가 필요하다! 데이터가 충분하지 않을 경우, 모델의 성능이 저하될 수 있습니다.

모델을 만드는 데 상대적으로 시간이 많이 소요된다! 이는 트리를 구성하는 데 많은 계산이 필요하기 때문입니다.

데이터의 변화에 민감하다! 학습 데이터와 테스트 데이터의 도메인이 서로 다를 경우, 모델의 성능이 크게 저하될 수 있습니다. 즉, 도메인 갭이 작아야 합니다.

선형 구조의 데이터를 예측할 때 모델이 복잡해진다! 의사결정나무가 본질적으로 비선형적인 패턴을 찾는데 특화되어 있기 때문입니다.

 

 

 

데이터 분석 절차

그렇다면 의사결정나무의 데이터 분석 절차는 어떤 과정으로 이뤄질까요? 큰 과정으로는 데이터 준비→ 모델학습 → 추론(분류,회귀) 로 이뤄집니다.

1. 데이터 준비: 의사결정나무는 다변량 변수(x1, x2, x3, ...) 사용합니다. 이는 여러 개의 독립 변수를 포함하는 데이터를 의미합니다.

2. 모델 학습: 의사결정나무는 트리 구조를 사용하여 모델을 학습합니다. 모델 학습은 다음의 단계로 이루어집니다:

① 한번에 설명 변수 하나씩 데이터를 선택

② 선택한 설명 변수에 따라 데이터를 두 개 혹은 그 이상의 부분집합으로 분할

③ 분할된 데이터의 순도가 최대화(또는 불순도가 최소화)되는 방향으로 재귀적으로 분할을 반복합니다. 이 과정을 재귀적 분할(Recursive Partitioning)이라고 합니다.

재귀적 분할은 다음의 조건에 따라 종료합니다:
분류 문제의 경우, 각 끝 노드(leaf node)에 같은 범주를 가진 데이터만 존재하게 됩니다.
회귀 문제의 경우, 각 끝 노드에 비슷한 수치를 가진 데이터만 존재하게 됩니다.

3. 추론(판별): 모델 학습이 완료되면, 새로운 데이터에 대한 추론을 수행합니다.

분류 문제의 경우, 끝 노드에서 가장 빈도가 높은 범주로 새로운 데이터를 분류합니다. 예를 들어, '날씨가 맑고 습도가 70을 넘는 날은 경기가 열리지 않을 것'이라는 규칙이 학습되었다면, 이 규칙에 따라 새로운 데이터가 분류됩니다.

회귀 문제의 경우, 끝 노드에 속한 데이터의 평균값이 새로운 데이터의 예측 값으로 사용됩니다.

 

 

분류나무 회귀나무~

의사결정나무는 그 목적에 따라 분류나무와 회귀나무로 나뉩니다.
분류나무(Classification Tree)는 목표 변수가 범주형일 때 사용합니다. 예를 들어, 스팸 메일 필터링이나 질병 진단 등의 문제에 사용될 수 있습니다.

회귀나무(Regression Tree)는 목표 변수가 연속형 수치일 때 사용합니다. 이는 주로 주택 가격 예측, 판매량 예측 등에 활용됩니다.

그렇다면 분할기준은 어떻게 정해질까요? 분할 기준은 주로 불순도나 불확실성을 감소시키는 방향으로 정해집니다. 이를 측정하는 방법으로는 지니 계수, 엔트로피 지수, 정보 이익, 정보 이익 비율, 카이제곱 통계량 등이 있습니다.

그리고 재귀적 분할 알고리즘을 통해 데이터를 분할하게 되는데, 이에는 여러 종류가 있습니다:

CART (Classification And Regression Tree): 분류와 회귀 모두에 사용되며, 지니 계수를 기반으로 분할합니다.
C4.5, C5.0: 주로 분류 문제에 사용되며, 엔트로피를 기반으로 분할합니다.
CHAID (Chi-square Automatic Interaction Detection): 카이제곱 통계량을 기반으로 분할하며, 분류와 회귀 문제 모두에 사용할 수 있습니다. 

 

 

 

분할기준 - 엔트로피 

분할기준중 자주 쓰이는 엔트로피 지수에 대해서 알아보겠습니다. 그전에 우선 '정보량' 이라는 개념을 숙지해야합니다.  정보량은 특정 사건이 일어날 확률에 기반하여 정의됩니다. 특정 사건이 발생할 확률이 낮을수록, 그 사건에 대한 정보량은 높아집니다. 다시 말해, 예기치 않은 사건이 발생하면 그것은 더 많은 정보를 제공한다는 의미입니다.  각 사건이 얼마나 "놀라운" 혹은 "예기치 못한"지를 정보량으로 측정합니다.

수학적으로, 정보량 I(x)는 다음과 같이 정의됩니다.

여기서 P(x)는 사건 x가 발생할 확률이며, log2는 밑이 2인 로그를 의미합니다. 이제 직관적인 해석 드갑니다.

P(x)가 1인 경우, 즉 사건 x가 항상 발생하는 경우, I(x)는 0이 됩니다. 이는 "역시는 역시군"과 같은 사건이 새로운 정보를 제공하지 않는다는 개념을 반영합니다.

반대로, P(x)가 0에 가까운 경우, 즉 사건 x가 거의 발생하지 않는 경우, I(x)는 매우 큽니다. 이는 "놀라운" 사건이 많은 정보를 제공한다는 개념을 반영합니다.

정보량의 단위는 '비트(bit)'입니다. 비트는 정보의 양을 측정하는 기본 단위로, 이진 로그를 사용함으로써 자연스럽게 도출됩니다. 따라서, 정보량 I(x)는 사건 x를 설명하는 데 필요한 최소 비트 수를 나타냅니다.

 

따라서 이 식을 해석하면, "사건 𝑥를 표현하기 위해 필요한 비트 수(정보량)은 사건 𝑥가 발생할 확률의 역수의 로그값이다"라고 할 수 있습니다. 마이너스 부호는 정보량이 항상 0 이상의 값을 가지도록 하기 위해 사용됩니다.

 

 

다시 돌아와서 엔트로피입니다.

엔트로피는 랜덤변수의 불확실성을 측정하는 지표로, 정보 이론에서 많이 사용됩니다. 이는 랜덤변수의 값이 얼마나 예측하기 어려운지를 나타내는 척도입니다.(랜덤변수(random variable)는 확률적인 실험에서 얻은 결과에 대응하는 수치 값, 주사위 1~6, 동전앞뒤)

엔트로피 공식은 아래와 같습니다:

이 공식에서, X는 랜덤변수를, x=k는 랜덤변수 X가 가질 수 있는 각각의 값을 나타냅니다. P(x=k)는 각 값 x=k가 발생할 확률입니다. 따라서 ∑ [ P(x=k) * log2(P(x=k)) ] 는 각각의 값 x=k에 대해 "해당 값이 발생할 확률 * 해당 값이 발생했을 때의 정보량"을 모두 합한 것을 의미합니다. 이를 '평균 정보의 양'이라고도 할 수 있습니다. 이 값이 클수록 불확실성이 높다는 것을 나타냅니다. 정보의 양이 많다면 위에 설명처럼 놀라운, 예기치 못한 사건이 많으니 불확실하다고 생각하시면 됩니다.

즉, 이 식은 랜덤변수 X가 특정 확률분포를 따를 때, 각 사건에 대한 평균 정보량을 계산하는 것입니다. 이때 평균 정보량은 'bit'로 표현되며, 이는 사건의 발생 확률에 따라 그 사건을 표현하는데 필요한 평균적인 비트 수를 의미합니다. 이 정보량이 클수록 해당 랜덤변수의 불확실성이 높아지는 것을 의미합니다.

 

 

아 ㅇㅋ 이제 엔트로피를 감소시켜야 불확실성이 줄어들겠네요 ㅎㅎ그래서 분할하겠습니다

 

 

흠 왜 분할 하면 엔트로피가 감소할까요? 의사결정나무에서 분할이 일어날 때, 그 분할은 주로 한 변수의 특정 값에 따라 데이터를 두 그룹으로 나눕니다. 이렇게 하면 각 그룹 내의 데이터는 더 비슷해지고(즉, 더 순수해지고), 그 결과 각 그룹 내의 엔트로피가 감소하게 됩니다.

예를 들어, 우리가 동물의 종류를 예측하는 모델을 만들고 있다고 가정해 봅시다. 우리는 동물이 '물 속에서 살 수 있는지'라는 변수를 기준으로 분할을 결정하게 됩니다. 이렇게 분할하면, 한 그룹에는 물 속에서 살 수 있는 동물만 모이고, 다른 그룹에는 물 속에서 살 수 없는 동물만 모일 것입니다. 이렇게 되면 각 그룹 내의 동물들은 이전보다 더 비슷해지므로 엔트로피가 감소하게 됩니다.

분할은 데이터를 더 균일한 그룹으로 나누는 작업이므로, 그 결과로 엔트로피가 감소하게 됩니다. 

 

의사결정나무 모델은 각 분할을 결정할 때, 해당 분기가 불확실성을 얼마나 감소시키는지를 평가합니다. 만약 분기 후의 불확실성이 분기 전보다 적게 되면, 그 분기는 유용한 분기라고 판단하고 모델에 포함시킵니다. 다시 말해, 분기 후의 엔트로피가 분기 전의 엔트로피보다 낮아지는 방향으로 의사결정나무는 성장하게 됩니다. 이러한 방법으로 의사결정나무는 최적의 분기를 찾아 나가면서 불확실성을 최소화하고 순도를 최대화하려고 노력합니다. 근데 불확실성 이야기하는데 순도는 뭐죠? 그건 지니계수와 관련이 있습니다. ㅎㅎ

 

분할기준 - 지니계수

지니 계수(Gini Index)는 경제학에서 원래 불평등 지수로 사용되었으나, 머신 러닝에서는 의사 결정 트리 알고리즘에서 데이터 분할 기준을 결정하는 데 주로 사용됩니다.

지니 계수는 한 노드의 순도를 측정하는 데 사용되며 즉 데이터의 통계적 분산 정도를 정량화하여 표현하는 값입니다. 노드의 모든 클래스가 동일하게 분포되어 있을 경우(즉, 노드가 불순한 상태인 경우) 최대값을 가집니다. 반대로, 노드가 순수한 상태(즉, 하나의 클래스만 존재하는 경우)일 때는 0의 값을 가집니다.

각 클래스의 데이터 비율을 p라고 할 때, 지니 계수는 다음과 같이 정의됩니다

GI(A) : 𝑚개의 범주(class)가 속하는 A영역에 대한 지니계수

𝑝𝑘: A영역에 속하는 레코드 가운데 𝑘 범주에 속하는 레코드의 비율

각 클래스의 비율의 제곱합을 1에서 뺀 값입니다. 이 값이 작을수록 그 노드는 순수하다고 볼 수 있습니다.

 

그럼 여기서 왜 제곱을 사용하는 것일까요? 직접 찾아봤습니다.

계산의 편의성: 제곱을 사용하면 계산이 간단해지고, 미분과 같은 수학적 연산을 수행하기도 편리합니다.

강조 효과: 제곱을 사용하면 높은 확률값을 가진 클래스의 비중이 더욱 강조됩니다. 즉, 한 클래스의 샘플이 훨씬 많을 경우, 그 불순도는 제곱을 통해 더욱 강조되어, 결정 트리 알고리즘이 더욱 "순수한" 노드를 만들도록 유도합니다.

 

일단 알겠지만 아직 배고픕니다. 예시갑니다.

이런 버켓이 3개가 있습니다.  각 지니계수를 구하면
GI(B1) = 1 − {(파란색 공을 뽑을 확률)^2 + (빨간색 공을 뽑을 확률)^2} = 1 − (1^2 + 0^2) = 0

GI(B2) = 1 − {(파란색 공을 뽑을 확률)^2 + (빨간색 공을 뽑을 확률)^2} = 1 − (0.5^2 + 0.5^2 )= 0.5

GI(B3) = 1 − {(파란색 공을 뽑을 확률)^2 + (빨간색 공을 뽑을 확률)^2} = 1− (0^2 + 1^2) = 0

 

역시 지니계수가 0인 값은 딱봐도 순수하네요 즉 지니계수가 작을수록 순수하며 이는 불순도가 작다는것을 의미합니다.

 

저 B2의 지니계수를 작게 만들어 불순도를 줄이고 싶습니다. 파란색과 빨간색으로 분할 하면 지니계수가 줄어들겠죠? 그래서 분할 하는겁니다 ㅎㅎ