결정 트리 학습법

결정 트리 학습법(decision tree learning)은 어떤 항목에 대한 관측값과 목표값을 연결시켜주는 예측 모델로서 결정 트리를 사용한다. 이는 통계학과 데이터 마이닝, 기계 학습에서 사용하는 예측 모델링 방법 중 하나이다. 트리 모델 중 목표 변수가 유한한 수의 값을 가지는 것을 분류 트리라 한다. 이 트리 구조에서 잎(리프 노드)은 클래스 라벨을 나타내고 가지는 클래스 라벨과 관련있는 특징들의 논리곱을 나타낸다. 결정 트리 중 목표 변수가 연속하는 값, 일반적으로 실수를 가지는 것은 회귀 트리라 한다.

의사 결정 분석에서 결정 트리는 시각적이고 명시적인 방법으로 의사 결정 과정과 결정된 의사를 보여주는데 사용된다. 데이터 마이닝 분야에서 결정 트리는 결정된 의사보다는 자료 자체를 표현하는데 사용된다. 다만, 데이터 마이닝의 결과로서의 분류 트리는 의사 결정 분석의 입력 값으로 사용될 수 있다. 이 페이지는 데이터 마이닝 분야에서의 결정 트리를 주로 다룬다.

일반

타이타닉호 탑승객의 생존 여부를 나타내는 결정 트리. (“sibsp”는 탑승한 배우자와 자녀의 수를 의미한다.) 잎 아래의 숫자는 각각 생존 확률과 탑승객이 그 잎에 해당될 확률을 의미한다.

결정 트리 학습법은 데이터 마이닝에서 일반적으로 사용되는 방법론으로, 몇몇 입력 변수를 바탕으로 목표 변수의 값을 예측하는 모델을 생성하는 것을 목표로 한다. 우측 그림은 그러한 예측 모델의 한 예를 나타내고 있다. 그림의 트리 구조에서, 각 내부 노드들은 하나의 입력 변수에, 자녀 노드들로 이어지는 가지들은 입력 변수의 가능한 값에 대응된다. 잎 노드는 각 입력 변수들이 루트 노드로부터 잎 노드로 이어지는 경로에 해당되는 값들을 가질 때의 목표 변수 값에 해당된다.

결정 트리 학습법은 지도 분류 학습에서 가장 유용하게 사용되고 있는 기법 중 하나이다. 이 글에서는 모든 속성들이 유한한 이산값들로 구성된 정의역을 가지고 있으며, 분류를 단일 대상 속성으로 지니고 있다고 간주한다. 분류의 정의역의 각 원소들은 클래스라고 불린다. 결정 트리 또는 분류 트리의 모든 내부 노드들에는 입력 속성이 일대일로 대응된다. 트리의 내부 노드에 연결된 가지에는 속성이 가질 수 있는 값들이 표시되며, 잎 노드에는 클래스 또는 클래스의 확률 분포가 표시된다.

결정 트리의 ’학습'은 학습에 사용되는 자료 집합을 적절한 분할 기준 또는 분할 테스트에 따라 부분 집합들로 나누는 과정이다. 이러한 과정은 순환 분할이라 불리는 방식으로 각각의 나눠진 자료 부분 집합에 재귀적으로 반복되며, 분할로 인해 더 이상 새로운 예측 값이 추가되지 않거나 부분 집합의 노드가 목표 변수와 같은 값을 지닐 때까지 계속된다. 이러한 하향식 결정 트리 귀납법(top-down induction of decision trees , TDIDT)은 탐욕 알고리즘의 한 예시이며, 데이터로부터 결정 트리를 학습하는 가장 일반적인 방법이다. 데이터 마이닝에서 결정 트리는 주어진 데이터의 일반화와 범주화를 돕기 위해 수학적 표현으로 기술된다. 데이터를 아래와 같이 기술할 때,

({\textbf {x}},Y)=(x_{1},x_{2},x_{3},...,x_{k},Y)

종속 변수 $Y$ 는 분류를 통해 학습하고자 하는 목표 변수이며, 벡터 $x$ 는 $x_{1},x_{2},x_{3}$ 등의 입력 변수로 구성된다.

종류

데이터 마이닝에서 사용되는 결정 트리 분석법은 크게 두 종류가 있다.

분류 트리 분석은 예측된 결과로 입력 데이터가 분류되는 클래스를 출력한다.
회귀 트리 분석은 예측된 결과로 특정 의미를 지니는 실수 값을 출력한다. (예: 주택의 가격, 환자의 입원 기간)

분류 및 회귀 트리(Classification And Regression Tree, CART)는 두 트리를 아울러 일컫는 용어로, 레오 브레이만에 의해 처음 사용되었다. 회귀 트리와 분류 트리는 일정 부분 유사하지만, 입력 자료를 나누는 과정 등에서 차이점이 있다. 앙상블 방법이라고 불리는 아래와 같은 기법들은 입력된 자료로부터 한 개 이상의 결정 트리를 생성한다. 초기 앙상블 방법인 배깅(Bootstrap aggregating) 결정 트리는 반복적으로 교체 과정을 수행하는 것과 함께 훈련 데이터를 재 샘플링하고, 합의 예측을 위한 트리를 선택하는 것으로 다수의 의사 결정 트리를 생성한다.

랜덤 포레스트 분류기에서는 분류 속도를 향상시키기 위해서 결정 트리들을 사용한다.
부스트 트리는 회귀 분석과 분류 문제에 사용될 수 있다.
회전 포레스트는 모든 결정 트리가 먼저 입력 트리 중 임의의 부분 집합에 대한 주성분 분석 (PCA)을 적용하여 훈련된다.

의사 결정 트리 학습은 클래스-라벨 훈련 쌍으로부터의 결정 트리에 의해 구성된다. 결정 트리의 각각의 노드는 서로 다른 특성을 가진다. 각각의 내부노드(또는 비 리프노드)는 속성에 대한 테스트를 나타내고, 각각의 가지는 테스트의 결과를 나타낸다. 그리고 각 리프노드(또는 터미널 노드)는 클래스의 라벨을 나타낸다. 마지막으로 트리의 최상위 노드는 루트 노드이다.

많은 특정 의사 결정 트리 알고리즘이 있지만 아래의 알고리즘은 그 중에서도 많이 사용되는 알고리즘을 나열한 것이다. 데이터마이닝에서 가장 많이 언급되고 사용되는 알고리즘은 C4.5 또는 C5.0이다. ID3 알고리즘을 보완하여 C4.5가 개발되었고, C4.5를 보완하여 C5.0이 개발된 것이므로 ID3, C4.5, C5.0 의 순서대로 학습해야 한다.

ID3 (Iterative Dichotomiser 3)
C4.5 (successor of ID3)
C5.0 (successor of ID4)
CART (Classification And Regression Tree)
CHAID (CHi-squared Automatic Interaction Detector) : 이 알고리즘은 분류 트리를 계산할 때 다단계 분할을 수행한다.
MARS (Multivariate adaptive regression splines) : 더 많은 수치 데이터를 처리하기 위해 결정 트리를 사용한다.
조건부 추론 트리 (Conditional Inference Trees) : 과적합을 피하기 위해 여러 테스트에 대해 보정 분할 기준으로 비 - 파라미터 테스트를 사용하는 통계 기반의 방법이다. 이 방법은 편견 예측 선택 결과와 가지 치기가 필요하지 않다.

ID3와 CART방법은 비슷한 시기인 1970년과 1980년 사이에 독립적으로 발명되었으며, 훈련 쌍에 대해 의사 결정 트리 학습을 위한 유사한 접근 방식을 사용한다. 위 알고리즘들 중에서 ID3, C4.5, C5.0 알고리즘들은 인공지능, 기계학습 분야에서 개발되어 발전되어 왔다. 이에 반해, CART 및 CHAID 알고리즘은 통계학에 분야에서 개발된 알고리즘들이다. 인공지능, 기계학습 계열의 알고리즘들은 엔트로피, 정보이득 개념을 사용하여 분리기준을 결정하고, 통계학에 기초한 CART 및 CHAID 알고리즘들은 카이스퀘어, T검정, F검정 등의 통계분석법을 사용한다.

방법

결정 트리를 구성하는 알고리즘에는 주로 하향식 기법이 사용되며, 각 진행 단계에서는 주어진 데이터 집합을 가장 적합한 기준으로 분할하는 변수값이 선택된다.^[1] 서로 다른 알고리즘들은 ”분할의 적합성"을 측정하는 각자의 기준이 있다. 이러한 기준들은 보통 부분 집합 안에서의 목표 변수의 동질성을 측정하며, 아래는 그 예시들이다. 이 기준들은 가능한 데이터 집합 분할의 경우의 수마다 적용되며, 그 결과 값들은 병합되어, 즉 평균 값이 계산되어, 데이터 집합의 분할이 얼마나 ”적합한지" 측정하는데 사용된다.

지니 불순도

지니 불순도는 집합에 이질적인 것이 얼마나 섞였는지를 측정하는 지표이며 CART 알고리즘에서 사용한다. 어떤 집합에서 한 항목을 뽑아 무작위로 라벨을 추정할 때 틀릴 확률을 말한다. 집합에 있는 항목이 모두 같다면 지니 불순도는 최솟값(0)을 갖게 되며 이 집합은 완전히 순수하다고 할 수 있다.

항목의 집합에 대한 지니 불순도를 계산하기 위하여, $i\in \{1,2,...,m\}$ 인 $i$ 를 가정해보자, 그리고 $f_{i}$ 를 $i$ 로 표시된 집합 안의 항목의 부분이라고 했을 때,

I_{G}(f)=\sum _{i=1}^{m}f_{i}(1-f_{i})=\sum _{i=1}^{m}(f_{i}-{f_{i}}^{2})=\sum _{i=1}^{m}f_{i}-\sum _{i=1}^{m}{f_{i}}^{2}=1-\sum _{i=1}^{m}{f_{i}}^{2}

로 나타낼 수 있다.

정보 획득량

ID3, C4.5 그리고 C5.0 트리 생성 알고리즘에서 사용되고 있다. 정보 획득량(information gain)은 정보이론의 엔트로피의 개념에 근거를 두고 있다.

I_{E}(f)=-\sum _{i=1}^{m}f_{i}\log _{2}^{}f_{i}

분산 감소

CART에서 소개된 분산 감소 기법은 목표 변수가 연속적일 경우(회귀 트리)에서 자주 사용된다. 즉, 만약 다른 방법에서 분산 감소 기법을 사용하기 위해서는 목표 변수를 적용하기 이전에 먼저 이산화 과정을 거쳐야함을 의미한다. 노드 N에 대한 분산 감소는 노드의 분할로 인해 발생하는 목표 변수 x의 분산의 총 감소로 정의된다.

$S$ , $S_{t}$ , and $S_{f}$ 를 각각 분할 전 샘플 지표의 설정, 분할 테스트가 참일 때에 해당하는 샘플 인덱스, 분할 테스트가 거짓일 때에 해당하는 샘플 인덱스라 할 때,

I_{V}(N)={\frac {1}{|S|}}\sum _{i\in S}\sum _{j\in S}{\frac {1}{2}}(x_{i}-x_{j})^{2}-\left({\frac {1}{|S_{t}|}}\sum _{i\in S_{t}}\sum _{j\in S_{t}}{\frac {1}{2}}(x_{i}-x_{j})^{2}+{\frac {1}{|S_{f}|}}\sum _{i\in S_{f}}\sum _{j\in S_{f}}{\frac {1}{2}}(x_{i}-x_{j})^{2}\right)

로 나타낼 수 있다.

장점

결정 트리는 다른 데이터 마이닝 기법과 비교했을 때 다음과 같은 장점을 가진다.

결과를 해석하고 이해하기 쉽다.간략한 설명만으로 결정 트리를 이해하는 것이 가능하다.
자료를 가공할 필요가 거의 없다.다른 기법들의 경우 자료를 정규화하거나 임의의 변수를 생성하거나 값이 없는 변수를 제거해야 하는 경우가 있다.
수치 자료와 범주 자료 모두에 적용할 수 있다.다른 기법들은 일반적으로 오직 한 종류의 변수를 갖는 데이터 셋을 분석하는 것에 특화되어 있다. (일례로 신경망 학습은 숫자로 표현된 변수만을 다룰 수 있는 것에 반해 관계식(relation rules)은 오직 명목 변수만을 다룰 수 있다.
화이트박스 모델을 사용한다. 모델에서 주어진 상황이 관측 가능하다면 불 논리를 이용하여 조건에 대해 쉽게 설명할 수 있다. (결과에 대한 설명을 이해하기 어렵기 때문에 인공신경망은 대표적인 블랙 박스 모델이다.)
안정적이다. 해당 모델 추리의 기반이 되는 명제가 다소 손상되었더라도 잘 동작한다.
대규모의 데이터 셋에서도 잘 동작한다. 방대한 분량의 데이터를 일반적인 컴퓨터 환경에서 합리적인 시간 안에 분석할 수 있다.

한계

최적의 결정 트리를 학습하는 문제는 NP-완전 문제로 알려져 있고, 이는 최적화의 관점에서나 아니면 더 간단한 개념의 측면에서도 마찬가지이다.^[2]^[3] 결과적으로, 실질적인 결정 트리 학습 알고리즘은 각 노드에서의 부분 최적값을 찾아내는 탐욕 알고리즘 같은 휴리스틱 기법을 기반으로 하고 있다. 이런 알고리즘들은 최적 결정 트리를 알아낸다고 보장할 수는 없다. 부분 최적화에 의한 영향을 줄이기 위하여 이중 정보 거리(dual information distance, DID)와 같은 방법을 사용하기도 한다.^[4]
결정 트리 학습자가 훈련 데이터를 제대로 일반화하지 못할 경우 너무 복잡한 결정 트리를 만들 수 있다. (이를 과적합 문제라 한다.) 이 문제를 해결하기 위해서 가지치기 같은 방법을 사용하여야 한다.
결정 트리로는 배타적 논리합이나 패리티, 멀티플렉서와 같은 문제를 학습하기 어렵다. 이런 문제를 학습하기 위해서는 결정 트리가 엄청나게 커지기 때문에 문제의 표현 방법을 바꾸거나 통계 관련 학습법이나 귀납 논리 프로그래밍처럼 더 많은 것을 표현할 수 있는 학습 알고리즘을 사용하여야 한다.
각각 서로 다른 수의 단계로 분류가 가능한 변수를 포함하는 데이터에 대하여 더 많은 단계를 가지는 속성 쪽으로 정보 획득량이 편향되는 문제가 있다.^[5] 하지만 이 문제는 조건부 추론을 통해 해결이 가능하다.
데이터의 특성이 특정 변수에 수직/수평적으로 구분되지 못할 때 분류율이 떨어지고, 트리가 복잡해지는 문제가 발생한다. 신경망 등의 알고리즘이 여러 변수를 동시에 고려하지만 결정트리는 한 개의 변수만을 선택하기 때문에 발생하는 당연한 문제이다.
약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다. 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이 후의 트리 구성이 크게 달라질 수 있다.

확장

결정 그래프

결정 트리에서, 뿌리 노드로부터 잎 노드까지 가는 모든 경로는 논리곱을 통해 진행된다. 결정 그래프에서는, MML^[6]을 이용하여 두 개 이상의 경로를 하나로 연결하는 것에 논리합을 사용하는 것이 가능하다. 결정 그래프는 이전에 합의되지 않은 새로운 특성들이 동적으로 학습되고 그래프 안의 다른 곳에서 사용될 수 있게 확장되어왔다.^[7] 보다 일반적인 프로그래밍 구조는 보다 나은 예상 정확도와 확률적 점수를 가져온다.^{[출처 필요]} 대개 결정 그래프는 결정 트리보다 적은 잎 노드를 갖는 모델을 선호한다.

대체 가능한 검색 방법

진화 알고리즘은 지역 최적점을 피하거나 연역적인 편향을 거의 갖지 않는 결정 트리 공간을 찾기 위하여 사용되어 왔다.^[8]^[9]

트리가 MCMC를 사용하여 표본 조사되는 것 또한 가능하다.^[10]

트리는 상향식 방식으로 볼 수 있다.^[11]

구현

대부분의 데이터 마이닝 소프트웨어 패키지는 하나 또는 그 이상의 결정 트리 알고리즘에 대한 라이브러리 및 구현을 제공한다. 몇 가지 예로는 샐포드 시스템사의 CART, IBM사의 SPSS Modeler, RapidMiner, SAS 엔터프라이즈사의 Miner, Matlab, R , 웨카 (무료 및 오픈 소스 데이터 마이닝 모음), Orange(무료 데이터 마이닝 소프트웨어 제품군으로서 트리 모듈인 orngTree를 포함), KNIME, 마이크로소프트사의 SQL 서버, 그리고 scikit-learn (파이썬 프로그래밍 언어에 대한 무료 및 오픈 소스 기계 학습 라이브러리)가 있다.

같이 보기

각주

↑ Rokach, L.; Maimon, O. (2005). “Top-down induction of decision trees classifiers-a survey”. 《IEEE Transactions on Systems, Man, and Cybernetics, Part C》 35 (4): 476–487. doi:10.1109/TSMCC.2004.843247.
↑ Hyafil, Laurent; Rivest, RL (1976). “Constructing Optimal Binary Decision Trees is NP-complete”. 《Information Processing Letters》 5 (1): 15–17. doi:10.1016/0020-0190(76)90095-8.
↑ Murthy S. (1998). Automatic construction of decision trees from data: A multidisciplinary survey. Data Mining and Knowledge Discovery
↑ Ben-Gal I. Dana A., Shkolnik N. and Singer (20). “Efficient Construction of Decision Trees by the Dual Information Distance Method” (PDF). Quality Technology & Quantitative Management (QTQM), 11( 1), 133-147. 2016년 6월 4일에 원본 문서 (PDF)에서 보존된 문서. 2015년 4월 27일에 확인함.
↑ Deng,H.; Runger, G.; Tuv, E. (2011). 《Bias of importance measures for multi-valued attributes and solutions》. Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). 293–300쪽.
↑ http://citeseer.ist.psu.edu/oliver93decision.html
↑ Tan & Dowe (2003)
↑ Papagelis A., Kalles D.(2001). Breeding Decision Trees Using Evolutionary Techniques, Proceedings of the Eighteenth International Conference on Machine Learning, p.393-400, June 28-July 01, 2001
↑ Barros, Rodrigo C., Basgalupp, M. P., Carvalho, A. C. P. L. F., Freitas, Alex A. (2011). A Survey of Evolutionary Algorithms for Decision-Tree Induction. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, vol. 42, n. 3, p. 291-312, May 2012.
↑ Chipman, Hugh A., Edward I. George, and Robert E. McCulloch. "Bayesian CART model search." Journal of the American Statistical Association 93.443 (1998): 935-948.
↑ Barros R. C., Cerri R., Jaskowiak P. A., Carvalho, A. C. P. L. F., A bottom-up oblique decision tree induction algorithm. Proceedings of the 11th International Conference on Intelligent Systems Design and Applications (ISDA 2011).

외부 링크

Building Decision Trees in Python From O'Reilly.
An Addendum to "Building Decision Trees in Python" From O'Reilly.
Decision Trees Tutorial using Microsoft Excel.
Decision Trees page at aitopics.org, a page with commented links.
Decision tree implementation in Ruby (AI4R)
Evolutionary Learning of Decision Trees in C++
Java implementation of Decision Trees based on Information Gain
A very explicit explanation of information gain as splitting criterion

[1] Rokach, L.; Maimon, O. (2005). “Top-down induction of decision trees classifiers-a survey”. 《IEEE Transactions on Systems, Man, and Cybernetics, Part C》 35 (4): 476–487. doi:10.1109/TSMCC.2004.843247.

[2] Hyafil, Laurent; Rivest, RL (1976). “Constructing Optimal Binary Decision Trees is NP-complete”. 《Information Processing Letters》 5 (1): 15–17. doi:10.1016/0020-0190(76)90095-8.

[3] Murthy S. (1998). Automatic construction of decision trees from data: A multidisciplinary survey. Data Mining and Knowledge Discovery

[4] Ben-Gal I. Dana A., Shkolnik N. and Singer (20). “Efficient Construction of Decision Trees by the Dual Information Distance Method” (PDF). Quality Technology & Quantitative Management (QTQM), 11( 1), 133-147. 2016년 6월 4일에 원본 문서 (PDF)에서 보존된 문서. 2015년 4월 27일에 확인함.

[5] Deng,H.; Runger, G.; Tuv, E. (2011). 《Bias of importance measures for multi-valued attributes and solutions》. Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). 293–300쪽.

[6] ttp://citeseer.ist.psu.edu/oliver93decision.html

[7] Tan & Dowe (2003)

[8] Papagelis A., Kalles D.(2001). Breeding Decision Trees Using Evolutionary Techniques, Proceedings of the Eighteenth International Conference on Machine Learning, p.393-400, June 28-July 01, 2001

[9] Barros, Rodrigo C., Basgalupp, M. P., Carvalho, A. C. P. L. F., Freitas, Alex A. (2011). A Survey of Evolutionary Algorithms for Decision-Tree Induction. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, vol. 42, n. 3, p. 291-312, May 2012.

[10] Chipman, Hugh A., Edward I. George, and Robert E. McCulloch. "Bayesian CART model search." Journal of the American Statistical Association 93.443 (1998): 935-948.

[11] Barros R. C., Cerri R., Jaskowiak P. A., Carvalho, A. C. P. L. F., A bottom-up oblique decision tree induction algorithm. Proceedings of the 11th International Conference on Intelligent Systems Design and Applications (ISDA 2011).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]