의사결정나무법(Decision Tree)

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

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

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

 

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

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

 

종속 변수 Y는 분류를 통해 학습하고자 하는 목표 변수이며, 벡터 x는

 

등의 입력 변수로 구성된다.

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

● 분류 트리 분석은 예측된 결과로 입력 데이터가 분류되는 클래스를 출력한다.

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

회귀 및 분석 트리(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] 서로 다른 알고리즘들은 ”분할의 적합성"을 측정하는 각자의 기준이 있다. 이러한 기준들은 보통 부분 집합 안에서의 목표 변수의 동질성을 측정하며, 아래는 그 예시들이다. 이 기준들은 가능한 데이터 집합 분할의 경우의 수마다 적용되며, 그 결과 값들은 병합되어, 즉 평균 값이 계산되어, 데이터 집합의 분할이 얼마나 ”적합한지" 측정하는데 사용된다.

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

● 결과를 해석하고 이해하기 쉽다.간략한 설명만으로 결정 트리를 이해하는 것이 가능하다.

● 자료를 가공할 필요가 거의 없다.다른 기법들의 경우 자료를 정규화하거나 임의의 변수를 생성하거나 값이 없는 변수를 제거해야 하는 경우가 있다.

● 수치 자료와 범주 자료 모두에 적용할 수 있다.다른 기법들은 일반적으로 오직 한 종류의 변수를 갖는 데이터 셋을 분석하는 것에 특화되어 있다. (일례로 신경망 학습은 숫자로 표현된 변수만을 다룰 수 있는 것에 반해 관계식(relation rules)은 오직 명목 변수만을 다룰 수 있다.

● 화이트박스 모델을 사용한다. 모델에서 주어진 상황이 관측 가능하다면 불 논리를 이용하여 조건에 대해 쉽게 설명할 수 있다. (결과에 대한 설명을 이해하기 어렵기 때문에 인공신경망은 대표적인 블랙 박스 모델이다.)

● 안정적이다. 해당 모델 추리의 기반이 되는 명제가 다소 손상되었더라도 잘 동작한다.

● 대규모의 데이터 셋에서도 잘 동작한다. 방대한 분량의 데이터를 일반적인 컴퓨터 환경에서 합리적인 시간 안에 분석할 수 있다.

한계

● 최적의 결정 트리를 학습하는 문제는 NP-완전 문제로 알려져 있고, 이는 최적화의 관점에서나 아니면 더 간단한 개념의 측면에서도 마찬가지이다.[2][3] 결과적으로, 실질적인 결정 트리 학습 알고리즘은 각 노드에서의 부분 최적값을 찾아내는 탐욕 알고리즘 같은 휴리스틱 기법을 기반으로 하고 있다. 이런 알고리즘들은 최적 결정 트리를 알아낸다고 보장할 수는 없다. 부분 최적화에 의한 영향을 줄이기 위하여 이중 정보 거리(dual information distance, DID)와 같은 방법을 사용하기도 한다.

● 결정 트리 학습자가 훈련 데이터를 제대로 일반화하지 못할 경우 너무 복잡한 결정 트리를 만들 수 있다. (이를 과적합 문제라 한다.) 이 문제를 해결하기 위해서 가지치기 같은 방법을 사용하여야 한다.

● 결정 트리로는 배타적 논리합이나 패리티, 멀티플렉서와 같은 문제를 학습하기 어렵다. 이런 문제를 학습하기 위해서는 결정 트리가 엄청나게 커지기 때문에 문제의 표현 방법을 바꾸거나 통계 관련 학습법이나 귀납 논리 프로그래밍처럼 더 많은 것을 표현할 수 있는 학습 알고리즘을 사용하여야 한다.

● 각각 서로 다른 수의 단계로 분류가 가능한 변수를 포함하는 데이터에 대하여 더 많은 단계를 가지는 속성 쪽으로 정보 획득량이 편향되는 문제가 있다.[5] 하지만 이 문제는 조건부 추론을 통해 해결이 가능하다.

● 데이터의 특성이 특정 변수에 수직/수평적으로 구분되지 못할 때 분류율이 떨어지고, 트리가 복잡해지는 문제가 발생한다. 신경망 등의 알고리즘이 여러 변수를 동시에 고려하지만 결정트리는 한 개의 변수만을 선택하기 때문에 발생하는 당연한 문제이다.

● 약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다. 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이 후의 트리 구성이 크게 달라질 수 있다.

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

(출처 : 위키백과)

scikit-learn에서 의사결정트리를 설명하는 문서를 보면 다음과 같이 설명한다.

의사 결정 트리 (DT) 는 분류 및 회귀에 사용되는 비모수 감독 학습 방법 입니다. 목표는 데이터 기능에서 유추 된 간단한 결정 규칙을 학습하여 대상 변수의 값을 예측하는 모델을 만드는 것입니다.

예를 들어, 아래 예에서 의사 결정 트리는 데이터에서 학습하여 if-then-else 결정 규칙 세트로 사인 곡선을 근사화합니다. 나무가 깊을수록 의사 결정 규칙이 더 복잡하고 모델이 더 적합합니다.

​

의사 결정 트리의 장점은 다음과 같습니다.

● 이해하고 해석하기 간단합니다. 나무를 시각화 할 수 있습니다.

● 데이터 준비가 거의 필요하지 않습니다. 다른 기술에는 종종 데이터 정규화, 더미 변수 생성 및 공백 값 제거가 필요합니다. 그러나이 모듈은 결 측값을 지원하지 않습니다.

● 트리를 사용하는 비용 (즉, 데이터 예측)은 트리를 훈련시키는 데 사용되는 데이터 포인트 수에 로그입니다.

● 수치 데이터와 범주 데이터를 모두 처리 할 수 ​​있습니다. 다른 기술은 일반적으로 한 가지 유형의 변수 만있는 데이터 세트를 분석하는 데 특화되어 있습니다. 자세한 내용은 알고리즘 을 참조하십시오.

● 다중 출력 문제를 처리 할 수 ​​있습니다.

● 화이트 박스 모델을 사용합니다. 주어진 상황이 모델에서 관찰 가능한 경우 조건에 대한 설명은 부울 논리에 의해 쉽게 설명됩니다. 대조적으로, (예를 들어, 인공 신경 네트워크에서) 블랙 박스 모델에서, 결과를 해석하기가 더 어려울 수있다.

● 통계 테스트를 사용하여 모델을 검증 할 수 있습니다. 따라서 모델의 신뢰성을 설명 할 수 있습니다.

● 데이터가 생성 된 실제 모델이 가정을 다소 위반하더라도 성능이 우수합니다.

의사 결정 트리의 단점은 다음과 같습니다.

● 의사 결정 트리 학습자는 데이터를 일반화하지 않는 복잡한 트리를 만들 수 있습니다. 이것을 오버 피팅이라고합니다. 잘라 내기 (현재 지원되지 않음), 리프 노드에 필요한 최소 샘플 수 설정 또는 트리의 최대 깊이 설정과 같은 메커니즘이이 문제를 방지해야합니다.

● 데이터의 작은 변형으로 인해 완전히 다른 트리가 생성 될 수 있으므로 의사 결정 트리가 불안정 할 수 있습니다. 이 문제는 앙상블 내 의사 결정 트리를 사용하여 완화됩니다.

● 최적의 의사 결정 트리를 학습하는 문제는 최적의 여러 측면에서 단순한 개념으로 NP 완료된 것으로 알려져 있습니다. 결과적으로 실용적인 의사 결정 트리 학습 알고리즘은 각 노드에서 로컬로 최적의 결정을 내리는 욕심 알고리즘과 같은 휴리스틱 알고리즘을 기반으로합니다. 이러한 알고리즘은 최적의 의사 결정 트리를 반환한다고 보장 할 수 없습니다. 이 기능은 앙상블 학습자에서 여러 트리를 학습하여 완화 할 수 있으며, 기능과 샘플은 임의로 교체하여 샘플링됩니다.

● 의사 결정 트리가 XOR, 패리티 또는 멀티플렉서 문제와 같이 의사 결정 트리를 쉽게 표현하지 못하기 때문에 배우기가 어려운 개념이 있습니다.

● 의사 결정 트리 학습자는 일부 클래스가 지배하는 경우 편향 트리를 만듭니다. 따라서 의사 결정 트리에 맞추기 전에 데이터 집합의 균형을 유지하는 것이 좋습니다.

(출처 : Scikit-learn: Machine Learning in Python, Pedregosa et al., JMLR 12, pp. 2825-2830, 2011.)

(https://scikit-learn.org/stable/modules/tree.html)