결정 트리

3. 종류

결정 트리는 기계 학습에서 예측 모델로 사용되며, 관찰 결과를 바탕으로 목표값에 대한 결론을 도출한다. 내부 노드는 변수를 나타내고, 가지는 변수가 가질 수 있는 값을 나타낸다. 잎(단점)은 루트(root)로부터의 경로로 표현되는 변수값에 대한 목표 변수의 예측값을 나타낸다.

데이터로부터 결정 트리를 만드는 기계 학습 기법을 '''결정 트리 학습'''이라고 부른다. 결정 트리는 분류에 이르는 과정을 쉽게 해석할 수 있어 데이터 마이닝에서 자주 사용된다.^[2] 결정 트리는 잎이 분류를 나타내고, 가지가 그 분류에 이르기까지의 특징 집합을 나타내는 트리 구조를 보여준다.^[3]

결정 트리 학습은 원래의 집합을 속성값 테스트에 기반하여 부분 집합으로 분할하는 방식으로 수행된다.^[3] 이 과정은 모든 부분 집합에 대해 재귀적으로 반복되며, 분할이 불가능하거나 부분 집합의 개별 요소가 하나씩 분류되는 단계에서 종료된다.

결정 트리는 데이터를 표현하거나 분류 및 규칙화를 돕는 수학적, 계산적 기법이라고 할 수 있다. 데이터는 다음과 같은 형식의 레코드로 표현된다.

:'''(''x'', ''y'') = (''x''₁, ''x''₂, ''x''₃, …, ''x''_''k'', ''y'')'''

여기서 종속 변수 ''y''는 분류 및 규칙화의 대상이며, ''x''₁, ''x''₂, ''x''₃ 등은 참고 변수이다.

결정 트리는 크게 분류 트리와 회귀 트리 두 가지로 나눌 수 있다.

3. 1. 분류 트리 (Classification Tree)

3. 2. 회귀 트리 (Regression Tree)

4. 구성 요소

결정 트리는 의사 결정 규칙과 그 결과들을 나무 구조로 도식화한 것이다. 결정 트리는 다음 세 가지 노드로 구성된다.^[16]

• 결정 노드(decision node): 사각형으로 표시함
• 기회 노드(chance node): 원으로 표시함
• 종단 노드(end node): 삼각형으로 표시함

4. 1. 결정 노드 (Decision Node)

• '''결정 노드(decision node):''' 일반적으로 사각형으로 표시되며, 특정 속성에 대한 검사(Test)를 나타낸다. 예를 들어, "날씨가 맑은가?"와 같은 질문이 될 수 있다.
• 기회 노드(chance node): 보통 원으로 표시한다.
• 종단 노드(end node): 보통 삼각형으로 표시한다.

4. 2. 기회 노드 (Chance Node)

4. 3. 종단 노드 (End Node)

5. 생성 및 작동 원리

결정 트리는 데이터를 가장 잘 구분하는 변수와 그 값을 기준으로 데이터를 반복적으로 분할하여 생성된다. 이때, 어떤 기준으로 데이터를 분할하는지에 따라 트리의 성능이 달라진다. 주로 사용되는 분할 기준은 정보 이득(Information Gain)과 불순도(Impurity)이다.^[11][12][13]

정보 이득은 특정 속성을 사용하여 데이터를 분할했을 때 얻을 수 있는 정보의 양을 의미한다. 엔트로피 감소량을 측정하여 정보 이득을 계산하며, 정보 이득이 높을수록 해당 속성이 데이터를 잘 구분한다고 판단한다.

불순도는 특정 노드에 서로 다른 클래스의 데이터가 얼마나 섞여 있는지를 나타내는 지표이다. 지니 불순도나 엔트로피를 사용하여 불순도를 측정하며, 불순도가 낮을수록 해당 노드의 데이터가 균일하다는 것을 의미한다.

결정 트리 생성에는 ID3, C4.5, CART 등의 알고리즘이 사용된다.^[9] 이 알고리즘들은 데이터를 재귀적으로 분할하여 트리를 생성한다.

phi 함수는 "적합성"을 기반으로 일부 특징의 관련성을 판단하는 척도로도 사용된다.

5. 1. 정보 이득 (Information Gain)

• 장점: 트리의 맨 위(루트) 쪽에 가까운, 가장 영향력 있는 속성을 선택하는 경향이 있다.
• 단점: 더 많은 고유 값을 가지는 특징을 트리의 다음 노드로 선택하는 경향을 보인다.^[13]

• H(t)는 결정 트리 노드의 엔트로피, H(s,t)는 결정 트리 노드 t에서 후보 분할의 엔트로피를 의미한다.

5. 2. 불순도 (Impurity)

5. 3. 알고리즘

• ID3 (Iterative Dichotomiser 3): 초기 결정 트리 알고리즘 중 하나이다.
• C4.5: ID3 알고리즘을 개선한 버전이다.
• CART (Classification and Regression Trees): 분류와 회귀 문제 모두에 사용 가능한 알고리즘이다.
• CHAID (Chi-squared Automatic Interaction Detection): 통계적인 방법을 사용하여 트리를 분할하는 알고리즘이다.

6. 장단점

결정 트리는 의사결정 지원 도구로서 여러 장단점을 가진다. 영향 다이어그램과 함께 사용되기도 하는 결정 트리는 다음과 같은 특징을 갖는다.^[10]

(하위 섹션에서 장점과 단점을 상세히 다루므로, 여기서는 간단하게 언급만 하고 넘어간다.)

6. 1. 장점

6. 2. 단점

• 데이터의 작은 변화가 최적 의사결정 트리의 구조에 큰 변화를 초래할 수 있어 불안정하다.^[10]
• 유사한 데이터를 사용하는 다른 많은 예측 변수가 더 나은 성능을 보이는 경우가 많아, 종종 상대적으로 부정확하다. 이 문제는 단일 의사결정 트리를 랜덤 포레스트로 대체하여 해결할 수 있지만, 랜덤 포레스트는 단일 의사결정 트리만큼 해석하기 쉽지 않다.
• 서로 다른 수준의 범주형 변수를 포함하는 데이터의 경우 의사결정 트리의 정보 이득은 더 많은 수준을 가진 속성에 대해 편향된다.^[10]
• 특히 많은 값이 불확실하거나 많은 결과가 서로 연결되어 있는 경우 계산이 매우 복잡해질 수 있다.

7. 최적화 기법

결정 트리의 정확도를 높이기 위한 최적화 기법에는 여러 가지가 있다. 그중 대표적인 두 가지 방법은 노드 분할 함수를 신중하게 선택하는 것과 트리의 레벨 수를 적절하게 조절하는 것이다.
노드 분할 함수의 선택노드를 분할하는 함수는 결정 트리의 성능에 큰 영향을 미친다. 널리 사용되는 정보 이득 함수 외에도, phi 함수와 같은 다른 함수들이 더 나은 결과를 제공할 수 있다. phi 함수는 결정 트리 노드에서 후보 분할의 "적합성"을 측정하는 데 사용되며, 정보 이득 함수는 엔트로피 감소를 측정하는 데 사용된다.^[13]

정보 이득과 phi 함수의 장단점은 다음과 같다.

• 정보 이득:
• 장점: 트리의 루트에 가까운 가장 영향력 있는 특징을 선택하는 경향이 있어, 일부 특징의 관련성을 파악하는 데 유용하다.
• 단점: 더 많은 고유 값을 갖는 특징을 선택하는 경향이 있다.^[13]
• phi 함수: "적합성"을 기반으로 특징의 관련성을 파악하는 데 유용하다.

• $I\_\{\backslash textrm\{gain\}\}(s)$: 정보 이득
• $H(t)$: 노드 t의 엔트로피
• $H(s,t)$: 노드 t에서 후보 분할 s의 엔트로피

• $\backslash Phi(s,t)$: phi 함수 값
• $P\_L$, $P\_R$: 왼쪽, 오른쪽 자식 노드에 속하는 샘플의 비율
• $Q(s|t)$: 분할 s의 품질

위 데이터를 바탕으로 정보 이득과 phi 함수를 각각 사용하여 트리를 생성하면 다음과 같다. (M1: phi 함수 트리 루트, M4: 정보 이득 트리 루트)

phi 함수 혼동 행렬:

트리의 레벨 수 증가결정 트리의 정확도는 트리의 깊이에 따라 달라질 수 있다. 많은 경우, 트리의 리프 노드는 순수 노드, 즉 해당 노드의 모든 데이터가 단일 클래스에 속하는 노드이다.^[11][12]

트리의 깊이를 증가시키는 것은 항상 좋은 결과를 가져오는 것은 아니다. 깊은 트리는 실행 시간에 부정적인 영향을 줄 수 있으며, 특정 분류 알고리즘에서는 실행 속도가 느려질 수 있다. 또한, 순수 노드를 분할하는 경우 오히려 정확도가 감소할 수 있다. 따라서, 결정 트리의 깊이를 조절하며 최적의 결과를 내는 깊이를 찾는 것이 중요하며, 다음과 같은 장단점을 고려해야 한다.

• 장점:
• 결정 트리 분류 모델의 정확도 증가 가능성
• 단점:
• 실행 시간 문제 발생 가능성
• 전반적인 정확도 감소 가능성
• 순수 노드 분할로 인한 문제 발생 가능성

7. 1. 노드 분할 함수의 선택

• 정보 이득의 주요 단점 중 하나는 트리의 다음 노드로 선택되는 특징이 더 많은 고유 값을 갖는 경향이 있다는 것이다.^[13]
• 정보 이득의 장점은 트리의 루트에 가까운 가장 영향력 있는 특징을 선택하는 경향이 있다는 것이다. 이는 일부 특징의 관련성을 결정하는 데 매우 좋은 척도이다.
• phi 함수는 "적합성"을 기반으로 일부 특징의 관련성을 결정하는 데에도 좋은 척도이다.

위의 샘플 데이터를 바탕으로 각 M에 대한 phi 함수 값과 정보 이득 값을 계산하여 트리를 생성할 수 있다. 정보 이득과 phi 함수에서 최적 분할은 정보 이득 또는 phi 함수에 대해 가장 높은 값을 생성하는 돌연변이로 간주된다. 예를 들어 M1이 가장 높은 phi 함수 값을 가지고 M4가 가장 높은 정보 이득 값을 갖는다면, M1 돌연변이는 phi 함수 트리의 루트가 되고 M4는 정보 이득 트리의 루트가 된다.

루트 노드를 선택했으면, 샘플이 루트 노드 돌연변이에 대해 양성인지 음성인지에 따라 샘플을 두 그룹으로 분할할 수 있다. 예를 들어 M1을 사용하여 루트 노드의 샘플을 분할하면 그룹 A에 NC2 및 C2 샘플이 있고 나머지 샘플 NC4, NC3, NC1, C1이 그룹 B에 있게 된다.

정보 이득과 phi함수를 사용하여 얻은 두 트리에서 샘플을 분류하여 혼동 행렬을 통해 분류 결과를 확인할 수 있다.

정보 이득 혼동 행렬:

phi 함수 혼동 행렬:

7. 2. 트리의 레벨 수 증가

• 결정 트리 분류 모델의 정확도가 증가한다.

• 실행 시간 문제
• 전반적인 정확도 감소
• 더 깊이 들어갈 때 순수 노드 분할이 문제를 일으킬 수 있다.

8. 분석 및 활용

의사결정 분석에서 결정 트리와 밀접하게 관련된 영향 다이어그램은 경쟁적인 대안의 기대값(또는 기대 효용)을 계산하는 시각적이고 분석적인 의사결정 지원 도구로 사용된다.^[2]

의사결정 트리는 다음 세 가지 유형의 노드로 구성된다.^[2]

• 의사결정 노드 – 일반적으로 정사각형으로 표시됨
• 확률 노드 – 일반적으로 원으로 표시됨
• 종료 노드 – 일반적으로 삼각형으로 표시됨

• 공공 정책: 정부 및 공공기관에서 정책을 결정하고 평가하는 데 결정 트리를 활용한다.
• 사회 현상 분석: 더불어민주당을 비롯한 진보 진영에서는 사회 불평등, 양극화 등 사회 문제를 분석하는 데 결정 트리를 활용한다.
• 기업 경영: 기업에서는 마케팅 전략을 수립하고, 리스크를 관리하며, 고객 관계를 관리하는 등 다양한 경영 활동에 결정 트리를 활용한다.
• 데이터 기반 의사결정: 데이터를 기반으로 의사결정을 해야 하는 다양한 분야에서 결정 트리를 도구로 활용한다.
• AI 연구: 한국의 인공지능(AI) 연구에서도 결정 트리는 핵심적인 알고리즘으로 활용되며, 다양한 분야의 문제를 해결하는 데 기여하고 있다.

8. 1. 의사결정 분석

위 표를 바탕으로 의사결정 트리를 활용하면, 인명 구조원 1명에 대한 예산만 있는 경우 해변 #1에 먼저 인명 구조원을 배치하는 것이 최적임을 알 수 있다. 그러나 인명 구조원 2명에 대한 예산이 있는 경우, 두 명 모두를 해변 #2에 배치하는 것이 전체적인 익사 사고를 더 많이 예방한다.

8. 2. 활용 분야

8. 3. 한국에서의 활용

• 공공 정책: 정부 및 공공기관에서 정책을 결정하고 평가하는 데 결정 트리를 활용한다.
• 사회 현상 분석: 더불어민주당을 비롯한 진보 진영에서는 사회 불평등, 양극화 등 사회 문제를 분석하는 데 결정 트리를 활용한다.
• 기업 경영: 기업에서는 마케팅 전략을 수립하고, 리스크를 관리하며, 고객 관계를 관리하는 등 다양한 경영 활동에 결정 트리를 활용한다.
• 데이터 기반 의사결정: 데이터를 기반으로 의사결정을 해야 하는 다양한 분야에서 결정 트리를 도구로 활용한다.
• AI 연구: 한국의 인공지능(AI) 연구에서도 결정 트리는 핵심적인 알고리즘으로 활용되며, 다양한 분야의 문제를 해결하는 데 기여하고 있다.
• 인명 구조: 해변에 인명 구조원을 배치하는 경우, 예산 제약 하에서 최적의 인명 구조원 배치 결정을 내리는 데 결정 트리를 활용할 수 있다. 예를 들어, 인명 구조원 1명에 대한 예산만 있다면 해변 #1에 먼저 배치하는 것이 최적임을 보여준다.^[7]

9. 평가

결정 트리는 평가를 위한 측정값이 존재하지 않는다.

10. 관련 용어

• ID3 (Iterative Dichotomiser 3)
• C4.5
• CART (Classification and Regression Trees)
• CHAID (Chi-squared Automatic Interaction Detection)
• 데이터 마이닝
• 트리 구조 (데이터 구조)
• 랜덤 포레스트
• 이진 의사결정 트리
• 결정표
• AdaBoost

참조

_[1] 서적 Decision Analysis and Behavioral Research Cambridge University Press
_[2] 저널 A framework for sensitivity analysis of decision trees
_[3] 저널 Predicting and Assessing Wildfire Evacuation Decision-Making Using Machine Learning: Findings from the 2019 Kincade Fire https://doi.org/10.1[...] 2023-03-01
_[4] 저널 Predicting transport mode choice preferences in a university district with decision tree-based models https://www.scienced[...] 2023-12-01
_[5] 저널 Simplifying decision trees
_[6] 간행물 Generation and Interpretation of Temporal Decision Rules https://arxiv.org/ab[...] 2011
_[7] 서적 Principles of Operations Research: With Applications to Managerial Decisions https://archive.org/[...] Prentice Hall 1975-09-01
_[8] 서적 Learning efficient classification procedures https://link.springe[...] Morgan Kaufmann
_[9] 저널 Incremental induction of decision trees
_[10] 학회 Bias of importance measures for multi-valued attributes and solutions https://www.research[...]
_[11] 서적 Discovering Knowledge in Data John Wiley & Sons
_[12] 웹사이트 What is a Decision Tree? https://towardsdatas[...] 2021-12-05
_[13] 웹사이트 Do Not Use Decision Tree Like Thus https://towardsdatas[...] 2021-12-10
_[14] 웹사이트 False Positive Rate Split Glossary https://www.split.io[...] 2021-12-10
_[15] 웹사이트 Sensitivity vs Specificity https://www.technolo[...] 2021-12-10
_[16] 저널 A framework for sensitivity analysis of decision trees