결정 트리 학습법
결정 트리 학습법()은 어떤 항목에 대한 관측값과 목표값을 연결시켜주는 예측 모델로써 결정 트리를 사용한다. 이는 통계학과 데이터 마이닝, 기계 학습에서 사용하는 예측 모델링 방법 중 하나이다. 트리 모델 중 목표 변수가 유한한 수의 값을 가지는 것을 분류 트리라 한다. 이 트리 구조에서 잎(리프 노드)은 클래스 라벨을 나타내고 가지는 클래스 라벨과 관련있는 특징들의 논리곱을 나타낸다. 결정 트리 중 목표 변수가 연속하는 값, 일반적으로 실수를 가지는 것은 회귀 트리라 한다.
의사 결정 분석에서 결정 트리는 시각적이고 명시적인 방법으로 의사 결정 과정과 결정된 의사를 보여주는데 사용된다. 데이터 마이닝 분야에서 결정 트리는 결정된 의사보다는 자료 자체를 표현하는데 사용된다. 다만, 데이터 마이닝의 결과로서의 분류 트리는 의사 결정 분석의 입력 값으로 사용될 수 있다. 이 페이지는 데이터 마이닝 분야에서의 결정 트리를 주로 다룬다.
결정 트리 학습법은 데이터 마이닝에서 일반적으로 사용되는 방법론으로, 몇몇 입력 변수를 바탕으로 목표 변수의 값을 예측하는 모델을 생성하는 것을 목표로 한다. 우측 그림은 그러한 예측 모델의 한 예를 나타내고 있다. 그림의 트리 구조에서, 각 내부 노드들은 하나의 입력 변수에, 자녀 노드들로 이어지는 가지들은 입력 변수의 가능한 값에 대응된다. 잎 노드는 각 입력 변수들이 루트 노드로부터 잎 노드로 이어지는 경로에 해당되는 값들을 가질 때의 목표 변수 값에 해당된다.
결정 트리 학습법은 지도 분류 학습에서 가장 유용하게 사용되고 있는 기법 중 하나이다. 이 글에서는 모든 속성들이 유한한 이산값들로 구성된 정의역을 가지고 있으며, 분류를 단일 대상 속성으로 지니고 있다고 간주한다. 분류의 정의역의 각 원소들은 클래스라고 불린다. 결정 트리 또는 분류 트리의 모든 내부 노드들에는 입력 속성이 일대일로 대응된다. 트리의 내부 노드에 연결된 가지에는 속성이 가질 수 있는 값들이 표시되며, 잎 노드에는 클래스 또는 클래스의 확률 분포가 표시된다.
결정 트리의 ’학습'은 학습에 사용되는 자료 집합을 적절한 분할 기준 또는 분할 테스트에 따라 부분 집합들로 나누는 과정이다. 이러한 과정은 순환 분할이라 불리는 방식으로 각각의 나눠진 자료 부분 집합에 재귀적으로 반복되며, 분할로 인해 더 이상 새로운 예측 값이 추가되지 않거나 부분 집합의 노드가 목표 변수와 같은 값을 지닐 때까지 계속된다. 이러한 하향식 결정 트리 귀납법(top-down induction of decision trees , TDIDT)은 탐욕 알고리즘의 한 예시이며, 데이터로부터 결정 트리를 학습하는 가장 일반적인 방법이다.
데이터 마이닝에서 결정 트리는 주어진 데이터의 일반화와 범주화를 돕기 위해 수학적 표현으로 기술된다.
데이터를 아래와 같이 기술할 때,
종속 변수 는 분류를 통해 학습하고자 하는 목표 변수이며, 벡터 는 formula_2 등의 입력 변수로 구성된다.
데이터 마이닝에서 사용되는 결정 트리 분석법은 크게 두 종류가 있다.
회귀 및 분석 트리(Classification And Regression Tree, CART)는 두 트리를 아울러 일컫는 용어로, 레오 브레이만에 의해 처음 사용되었다. 회귀 트리와 분류 트리는 일정 부분 유사하지만, 입력 자료를 나누는 과정 등에서 차이점이 있다.
앙상블 방법이라고 불리는 아래와 같은 기법들은 입력된 자료로부터 한 개 이상의 결정 트리를 생성한다.
초기 앙상블 방법인 배깅(Bootstrap aggregating) 결정 트리는 반복적으로 교체 과정을 수행하는 것과 함께 훈련 데이터를 재 샘플링하고, 합의 예측을 위한 트리를 선택하는 것으로 다수의 의사 결정 트리를 생성한다.
의사 결정 트리 학습은 클래스-라벨 훈련 쌍으로부터의 결정 트리에 의해 구성된다. 결정 트리의 각각의 노드는 서로 다른 특성을 가진다. 각각의 내부노드(또는 비 리프노드)는 속성에 대한 테스트를 나타내고, 각각의 가지는 테스트의 결과를 나타낸다. 그리고 각 리프노드(또는 터미널 노드)는 클래스의 라벨을 나타낸다. 마지막으로 트리의 최상위 노드는 루트 노드이다.
많은 특정 의사 결정 트리 알고리즘이 있지만 아래의 알고리즘은 그 중에서도 많이 사용되는 알고리즘을 나열한 것이다. 데이터마이닝에서 가장 많이 언급되고 사용되는 알고리즘은 C4.5 또는 C5.0 이다. ID3 알고리즘을 보완하여 C4.5가 개발되었고, C4.5를 보완하여 C5.0이 개발된 것이므로 ID3, C4.5, C5.0 의 순서대로 학습해야 한다.
ID3와 CART방법은 비슷한 시기인 1970년과 1980년 사이에 독립적으로 발명되었으며, 훈련 쌍에 대해 의사 결정 트리 학습을 위한 유사한 접근 방식을 사용한다. 위 알고리즘들 중에서 ID3, C4.5, C5.0 알고리즘들은 인공지능, 기계학습 분야에서 개발되어 발전되어 왔다. 이에 반해, CART 및 CHAID 알고리즘은 통계학에 분야에서 개발된 알고리즘들이다. 인공지능, 기계학습 계열의 알고리즘들은 엔트로피, 정보이득 개념을 사용하여 분리기준을 결정하고, 통계학에 기초한 CART 및 CHAID 알고리즘들은 카이스퀘어, T검정, F검정 등의 통계분석법을 사용한다.
결정 트리를 구성하는 알고리즘에는 주로 하향식 기법이 사용되며, 각 진행 단계에서는 주어진 데이터 집합을 가장 적합한 기준으로 분할하는 변수값이 선택된다.
서로 다른 알고리즘들은 ”분할의 적합성"을 측정하는 각자의 기준이 있다. 이러한 기준들은 보통 부분 집합 안에서의 목표 변수의 동질성을 측정하며, 아래는 그 예시들이다. 이 기준들은 가능한 데이터 집합 분할의 경우의 수마다 적용되며, 그 결과 값들은 병합되어, 즉 평균 값이 계산되어, 데이터 집합의 분할이 얼마나 ”적합한지" 측정하는데 사용된다.
지니 불순도는 집합에 이질적인 것이 얼마나 섞였는지를 측정하는 지표이며 CART 알고리즘에서 사용한다. 어떤 집합에서 한 항목을 뽑아 무작위로 라벨을 추정할 때 틀릴 확률을 말한다. 집합에 있는 항목이 모두 같다면 지니 불순도는 최솟값(0)을 갖게 되며 이 집합은 완전히 순수하다고 할 수 있다.
항목의 집합에 대한 지니 불순도를 계산하기 위하여, formula_3 인 formula_4를 가정해보자, 그리고 formula_5를 formula_4로 표시된 집합 안의 항목의 부분이라고 했을 때,
로 나타낼 수 있다.
ID3, C4.5 그리고 C5.0 트리 생성 알고리즘에서 사용되고 있다. 정보 획득량(information gain)은 정보 이론의 엔트로피의 개념에 근거를 두고 있다.
CART에서 소개된 분산 감소 기법은 목표 변수가 연속적일 경우(회귀 트리)에서 자주 사용된다. 즉, 만약 다른 방법에서 분산 감소 기법을 사용하기 위해서는 목표 변수를 적용하기 이전에 먼저 이산화 과정을 거쳐야함을 의미한다.
노드 N에 대한 분산 감소는 노드의 분할로 인해 발생하는 목표 변수 x의 분산의 총 감소로 정의된다.
formula_9, formula_10, and formula_11 를 각각 분할 전 샘플 지표의 설정, 분할 테스트가 참일 때에 해당하는 샘플 인덱스, 분할 테스트가 거짓일 때에 해당하는 샘플 인덱스라 할 때,
로 나타낼 수 있다.
결정 트리는 다른 데이터 마이닝 기법과 비교했을 때 다음과 같은 장점을 가진다.결정 트리에서, 뿌리 노드로부터 잎 노드까지 가는 모든 경로는 논리곱을 통해 진행된다. 결정 그래프에서는, MML 을 이용하여 두 개 이상의 경로를 하나로 연결하는 것에 논리합을 사용하는 것이 가능하다. 결정 그래프는 이전에 합의되지 않은 새로운 특성들이 동적으로 학습되고 그래프 안의 다른 곳에서 사용될 수 있게 확장되어왔다. 보다 일반적인 프로그래밍 구조는 보다 나은 예상 정확도와 확률적 점수를 가져온다. 대개 결정 그래프는 결정 트리보다 적은 잎 노드를 갖는 모델을 선호한다.
진화 알고리즘은 지역 최적점을 피하거나 연역적인 편향을 거의 갖지 않는 결정 트리 공간을 찾기 위하여 사용되어 왔다.
트리가 MCMC를 사용하여 표본 조사되는 것 또한 가능하다.
트리는 상향식 방식으로 볼 수 있다.
대부분의 데이터 마이닝 소프트웨어 패키지는 하나 또는 그 이상의 결정 트리 알고리즘에 대한 라이브러리 및 구현을 제공한다. 몇 가지 예로는 샐포드 시스템사의 CART, IBM사의 SPSS Modeler, RapidMiner, SAS 엔터프라이즈사의 Miner, Matlab, R , 웨카 (무료 및 오픈 소스 데이터 마이닝 모음), Orange(무료 데이터 마이닝 소프트웨어 제품군으로서 트리 모듈인 orngTree를 포함), KNIME, 마이크로 소프트사의 SQL 서버, 그리고 scikit-learn (파이썬 프로그래밍 언어에 대한 무료 및 오픈 소스 기계 학습 라이브러리)가 있다.