맨위로가기

결정 트리 학습법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

결정 트리 학습법은 데이터 마이닝에서 사용되는 지도 학습 방법으로, 데이터를 분류하거나 예측하는 데 사용되는 트리 구조를 기반으로 한다. 분류 트리와 회귀 트리 두 가지 유형이 있으며, 분류 트리는 데이터를 클래스로 분류하고, 회귀 트리는 연속적인 값을 예측한다. 결정 트리는 ID3, C4.5, CART, CHAID 등 다양한 알고리즘을 통해 구성되며, 정보 획득량, 지니 불순도, 분산 감소 등의 분할 기준을 사용하여 트리를 분할한다. 앙상블 방법은 여러 개의 결정 트리를 결합하여 예측 성능을 향상시키며, 과적합, 특정 문제 학습의 어려움, 편향된 변수 선택 등의 한계를 가진다. 결정 그래프, 대체 검색 방법, 다양한 소프트웨어 패키지를 통해 구현될 수 있다.

더 읽어볼만한 페이지

  • 결정 트리 - ID3 알고리즘
    ID3 알고리즘은 존 로스 퀸란이 1979년에 개발한 의사 결정 트리 학습 알고리즘으로, 정보량의 기대값을 계산하여 트리의 노드를 생성하며, 학습 효율이 높지만 국소 최적해 문제와 과적합 가능성 등의 단점도 가진다.
  • 결정 트리 - 랜덤 포레스트
    랜덤 포레스트는 결정 트리들을 앙상블하여 분류, 회귀, 검출 등에 활용되며, 랜덤화 기술로 일반화 성능을 향상시키는 기계 학습 알고리즘이다.
  • 분류 알고리즘 - 인공 신경망
  • 분류 알고리즘 - 퍼셉트론
    퍼셉트론은 프랭크 로젠블랫이 고안한 인공신경망 모델로, 입력 벡터에 가중치를 곱하고 편향을 더한 값을 활성화 함수에 통과시켜 이진 분류를 수행하는 선형 분류기 학습 알고리즘이며, 초기 신경망 연구의 중요한 모델로서 역사적 의미를 가진다.
결정 트리 학습법

2. 역사

2. 1. 초기 발전 (1970년대 ~ 1980년대)

2. 2. 발전과 확장 (1990년대 ~ 현재)

3. 종류

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


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

분류 및 회귀 트리(Classification And Regression Tree, CART)는 두 트리를 아울러 일컫는 용어로, 레오 브레이만에 의해 처음 사용되었다.[6] 회귀 트리와 분류 트리는 일정 부분 유사하지만, 입력 자료를 나누는 과정 등에서 차이점이 있다.[6]

앙상블 방법이라고 불리는 아래와 같은 기법들은 입력된 자료로부터 한 개 이상의 결정 트리를 생성한다.

  • 초기 앙상블 방법인 배깅(Bootstrap aggregating) 결정 트리는 반복적으로 교체 과정을 수행하는 것과 함께 훈련 데이터를 재 샘플링하고, 합의 예측을 위한 트리를 선택하는 것으로 다수의 의사 결정 트리를 생성한다.
  • '''랜덤 포레스트''' 분류기에서는 분류 속도를 향상시키기 위해서 결정 트리들을 사용한다.
  • '''부스트 트리'''는 회귀 분석과 분류 문제에 사용될 수 있다.[7][8]
  • '''회전 포레스트'''는 모든 결정 트리가 먼저 입력 트리 중 임의의 부분 집합에 대한 주성분 분석 (PCA)을 적용하여 훈련된다.[12]

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

많은 특정 의사 결정 트리 알고리즘이 있지만 아래의 알고리즘은 그 중에서도 많이 사용되는 알고리즘을 나열한 것이다. 데이터마이닝에서 가장 많이 언급되고 사용되는 알고리즘은 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) : 이 알고리즘은 분류 트리를 계산할 때 다단계 분할을 수행한다.[17][18][19]
  • MARS (Multivariate adaptive regression splines) : 더 많은 수치 데이터를 처리하기 위해 결정 트리를 사용한다.
  • 조건부 추론 트리 (Conditional Inference Trees) : 과적합을 피하기 위해 여러 테스트에 대해 보정 분할 기준으로 비 - 파라미터 테스트를 사용하는 통계 기반의 방법이다. 이 방법은 편견 예측 선택 결과와 가지 치기가 필요하지 않다.[20][21]

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

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

데이터 마이닝에서 사용되는 결정 트리 분석법 중 하나이다. 분류 트리 분석은 예측된 결과로 입력 데이터가 분류되는 클래스를 출력한다.[6] 레오 브레이만이 처음으로 사용한 용어인 분류 및 회귀 트리(CART)는 분류 트리와 회귀 트리를 모두 아우르는 말이다.[6] 회귀 트리와 분류 트리는 일정 부분 유사하지만, 입력 자료를 나누는 과정 등에서 차이점이 존재한다.[6]

분류 트리는 입력 데이터가 어떤 클래스에 속하는지 예측하는 데 사용된다. 예를 들어, 환자의 데이터를 기반으로 특정 질병의 유무를 판단하거나, 고객의 구매 이력을 바탕으로 어떤 상품을 추천할지 결정하는 데 활용될 수 있다.

많이 사용되는 결정트리 알고리즘으로는 ID3, C4.5, CART, CHAID 등이 있다. ID3와 CART는 1970년대와 1980년대 사이에 독립적으로 발명되었으며, 훈련 쌍에 대해 의사 결정 트리 학습을 위한 유사한 접근 방식을 따른다.

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

데이터 마이닝에서 사용되는 결정 트리 분석법 중 하나인 회귀 트리 분석은 예측된 결과로 특정 의미를 지니는 실수 값을 출력한다.(예: 주택의 가격, 환자의 입원 기간)[6] 레오 브레이만이 처음 사용한 분류 및 회귀 트리(Classification And Regression Tree, CART)는 회귀 트리와 분류 트리를 모두 아우르는 용어다.[6] 회귀 트리와 분류 트리는 입력 자료를 나누는 과정 등에서 차이가 있다.

부스팅 트리는 회귀 분석에 사용될 수 있다.[7][8] MARS는 더 많은 수치 데이터를 처리하기 위해 결정 트리를 사용한다.[17][18][19]

4. 주요 알고리즘 및 방법

결정 트리를 구성하는 알고리즘에는 주로 하향식 기법이 사용되며, 각 진행 단계에서는 주어진 데이터 집합을 가장 적합한 기준으로 분할하는 변수값이 선택된다.[49]

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

4. 1. 분할 기준 (Splitting Criteria)

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

결정 트리를 구성하는 알고리즘은 일반적으로 각 단계에서 항목 집합을 가장 잘 분할하는 변수를 선택하여 위에서 아래로 작동한다.[24] 서로 다른 알고리즘은 "최적"을 측정하기 위해 서로 다른 메트릭을 사용한다. 이는 일반적으로 하위 집합 내의 대상 변수의 동질성을 측정한다. 몇 가지 예가 아래에 나와 있다. 이러한 메트릭은 각 후보 하위 집합에 적용되며 결과 값은 결합(예: 평균)되어 분할의 품질을 측정한다. 기본 메트릭에 따라 결정 트리 학습을 위한 다양한 휴리스틱 알고리즘의 성능이 크게 달라질 수 있다.[25]

  • '''지니 불순도 (Gini Impurity)'''


지니 불순도는 집합에 이질적인 것이 얼마나 섞였는지를 측정하는 지표이며 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^{m}_{i=1} {f_i}^{2}

로 나타낼 수 있다.

'''지니 불순도''', '''지니의 다양성 지수''',[26] 또는 생물 다양성 연구에서 '''지니-심슨 지수'''는 이탈리아 수학자 코라도 지니의 이름을 따서 명명되었으며 분류 트리를 위한 CART(분류 및 회귀 트리) 알고리즘에서 사용된다. 지니 불순도는 집합의 레이블 분포에 따라 무작위로, 독립적으로 레이블이 지정된 경우 집합의 임의로 선택된 요소가 잘못 레이블이 지정될 빈도를 측정한다. 노드의 모든 사례가 단일 대상 범주에 속할 때 최소값(0)에 도달한다.

J개의 클래스와 상대 빈도 p_i, i \in \{1, 2, ...,J\}를 가진 항목 집합의 경우, 레이블 i가 있는 항목을 선택할 확률은 p_i이고, 해당 항목을 잘못 분류할 확률은 \sum_{k \ne i} p_k = 1-p_i이다. 지니 불순도는 각 클래스 레이블에 대해 이러한 확률의 쌍별 곱을 합산하여 계산한다.

:\operatorname{I}_G(p) = \sum_{i=1}^J \left( p_i \sum_{k\neq i} p_k \right)

= \sum_{i=1}^J p_i (1-p_i)

= \sum_{i=1}^J (p_i - p_i^2)

= \sum_{i=1}^J p_i - \sum_{i=1}^J p_i^2

= 1 - \sum^J_{i=1} p_i^2.

지니 불순도는 또한 정보 이론적 척도이며 변형 계수 q=2를 갖는 찰리스 엔트로피에 해당하며, 이는 물리학에서 평형이 아닌, 비확장적, 소산적 및 양자 시스템의 정보 부족과 관련이 있다. q\to 1의 극한에서 일반적인 볼츠만-깁스 또는 섀넌 엔트로피를 회복한다. 이러한 의미에서 지니 불순도는 의사 결정 트리에 대한 일반적인 엔트로피 척도의 변형에 지나지 않는다.

  • '''정보 획득량 (Information Gain)'''


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

엔트로피는 다음과 같이 정의된다.

:\Eta(T) = \operatorname{I}_{E}\left(p_1, p_2, \ldots, p_J\right)

= - \sum^J_{i=1} p_i \log_2 p_i

여기서 p_1, p_2, \ldots는 합이 1이고 트리의 분할로 인해 발생하는 자식 노드에 있는 각 클래스의 백분율을 나타내는 분수이다.[27]

: \overbrace{IG(T,a)}^\text{정보 이득}

= \overbrace{\Eta(T)}^\text{엔트로피 (부모)}

  • \overbrace{\Eta(T\mid a)}^\text{엔트로피 합계 (자식)} =-\sum_{i=1}^J p_i\log_2 p_i - \sum_{i=1}^J - \Pr(i\mid a)\log_2 \Pr(i\mid a)


A의 가능한 값에 대한 평균,

: \overbrace{E_A(\operatorname{IG}(T,a))}^\text{예상 정보 이득}

= \overbrace{I(T; A)}^{\text{T 와 A 사이의 상호 정보}}

= \overbrace{\Eta(T)}^\text{엔트로피 (부모)}

  • \overbrace{\Eta(T\mid A)}^\text{엔트로피의 가중 합계 (자식)} =-\sum_{i=1}^J p_i\log_2 p_i - \sum_a p(a)\sum_{i=1}^J-\Pr(i\mid a) \log_2 \Pr(i\mid a)


여기서 엔트로피의 가중 합계는 다음과 같이 주어진다.

:{\Eta(T\mid A)}= \sum_a p(a)\sum_{i=1}^J-\Pr(i\mid a) \log_2 \Pr(i\mid a)

즉, 예상 정보 이득은 상호 정보이며, 이는 평균적으로 ''T''의 엔트로피 감소가 상호 정보임을 의미한다.

정보 이득은 트리를 구축하는 각 단계에서 어떤 특징으로 분할할지 결정하는 데 사용된다. 단순성이 가장 좋으므로 트리를 작게 유지하려고 한다. 이를 위해 각 단계에서 가장 일관된 자식 노드를 생성하는 분할을 선택해야 한다. 일반적으로 사용되는 일관성 척도는 정보라고 하며, 이는 비트 단위로 측정된다. 트리의 각 노드에 대해 정보 값은 "새로운 인스턴스가 해당 노드에 도달한 경우 예 또는 아니오로 분류되어야 하는지 지정하는 데 필요한 예상 정보량"을 나타낸다.[27]

4개의 속성(''outlook''(맑음, 흐림, 비), ''temperature''(더움, 보통, 시원함), ''humidity''(높음, 보통), ''windy''(참, 거짓))과 이진(예 또는 아니오) 목표 변수 ''play'' 및 14개의 데이터 포인트가 있는 예제 데이터 집합을 고려해 보자. 이 데이터에 대한 결정 트리를 구성하려면 네 가지 특징 중 하나를 기준으로 분할된 네 개의 각 트리의 정보 이득을 비교해야 한다. 정보 이득이 가장 높은 분할이 첫 번째 분할로 사용되고, 모든 자식 노드가 각 일관된 데이터를 갖거나 정보 이득이 0이 될 때까지 프로세스가 계속된다.

''windy''를 사용하여 분할의 정보 이득을 찾으려면 먼저 분할 전 데이터의 정보를 계산해야 한다. 원래 데이터에는 9개의 예와 5개의 아니오가 포함되어 있었다.

: I_E([9,5]) = -\frac 9 {14}\log_2 \frac 9 {14} - \frac 5 {14}\log_2 \frac 5 {14} = 0.94

''windy'' 특징을 사용한 분할은 두 개의 자식 노드를 생성하며, 하나는 참 ''windy'' 값이고 다른 하나는 거짓 ''windy'' 값이다. 이 데이터 집합에는 참 ''windy'' 값을 가진 6개의 데이터 포인트가 있으며, 그 중 3개는 예의 ''play''(여기서 ''play''는 목표 변수) 값을 가지고 있고 3개는 아니오 값을 가지고 있다. 거짓 ''windy'' 값을 가진 나머지 8개의 데이터 포인트에는 2개의 아니오와 6개의 예가 포함되어 있다. ''windy''=true 노드의 정보는 위의 엔트로피 방정식을 사용하여 계산된다. 이 노드에는 예와 아니오의 수가 동일하므로 다음과 같다.

: I_E([3,3]) = -\frac 3 6\log_2 \frac 3 6 - \frac 3 6\log_2 \frac 3 6 = -\frac 1 2\log_2 \frac 1 2 - \frac 1 2\log_2 \frac 1 2 = 1

''windy''=false 노드의 경우 8개의 데이터 포인트, 6개의 예 및 2개의 아니오가 있었다. 따라서 다음과 같다.

: I_E([6,2]) = -\frac 6 8\log_2 \frac 6 8 - \frac 2 8\log_2 \frac 2 8 = -\frac 3 4\log_2 \frac 3 4 - \frac 1 4\log_2 \frac 1 4 = 0.81

분할의 정보를 찾으려면, 이러한 두 숫자의 가중 평균을 어느 노드에 얼마나 많은 관측치가 속했는지에 따라 구한다.

: I_E([3,3],[6,2]) = I_E(\text{바람이 부는지 여부}) = \frac 6 {14} \cdot 1 + \frac 8 {14} \cdot 0.81 = 0.89

이제 ''windy'' 특징으로 분할하여 얻은 정보 이득을 계산할 수 있다.

: \operatorname{IG}(\text{바람이 부는지 여부}) = I_E([9,5]) - I_E([3,3],[6,2]) = 0.94 - 0.89 = 0.05

트리를 구축하려면 각 가능한 첫 번째 분할의 정보 이득을 계산해야 한다. 가장 좋은 첫 번째 분할은 가장 많은 정보 이득을 제공하는 분할이다. 이 프로세스는 트리가 완료될 때까지 각 순수하지 않은 노드에 대해 반복된다. 이 예는 Witten et al.에 나타나는 예에서 적용되었다.[27]

정보 이득은 생물 다양성 연구에서 섀넌 지수로도 알려져 있다.

  • '''분산 감소 (Variance Reduction)'''


CART에서 소개된[6] 분산 감소 기법은 목표 변수가 연속형인 경우(회귀 트리)에 자주 사용되며, 이는 다른 많은 지표를 사용하려면 먼저 이산화가 필요하다는 것을 의미한다. 노드 N의 분산 감소는 이 노드에서 분할로 인한 대상 변수 x의 분산의 총 감소로 정의된다.

:

I_{V}(N) = \frac{1}

\sum_{i\in S} \sum_{j\in S} \frac{1}{2}(x_i - x_j)^2 - \left(\frac{1}

\sum_{i\in S_t} \sum_{j\in S_t} \frac{1}{2}(x_i - x_j)^2 + \frac{1}

\sum_{i\in S_f} \sum_{j\in S_f} \frac{1}{2}(x_i - x_j)^2\right)



여기서 S, S_t, S_f는 분할 전 표본 지수 집합, 분할 테스트가 참인 표본 지수 집합, 분할 테스트가 거짓인 표본 지수 집합을 각각 나타낸다. 위의 각 합은 실제로 분산 추정치이지만, 평균을 직접 참조하지 않는 형식으로 작성되었다.

위 공식의 (y_i - y_j)^2를 두 객체 i와 j 사이의 상이성 d_{ij}로 대체하면 분산 감소 기준이 쌍별 상이성을 계산할 수 있는 모든 종류의 객체에 적용된다.[1]

  • '''"좋음" 척도 ("Goodness" Measure)'''


1984년 CART에서 사용된 "좋음" 척도는 후보 분할이 순수한 자식 노드를 만들 수 있는 능력과 동일한 크기의 자식 노드를 만들 수 있는 능력 사이의 균형을 최적화하려는 함수이다.[28] 이 과정은 트리가 완성될 때까지 각 불순 노드에 대해 반복된다. 함수 \varphi(s\mid t)는 노드 t에서 후보 분할 s이며, 아래와 같이 정의된다.

:

\varphi(s\mid t) = 2P_L P_R \sum_{j=1}^\text{class count}|P(j\mid t_L) - P(j\mid t_R)|



여기서 t_L과 t_R은 분할 s를 사용하여 노드 t의 왼쪽 및 오른쪽 자식 노드이고, P_L과 P_R은 t의 레코드 비율이 각각 t_L과 t_R에 있는 것이며, P(j\mid t_L)과 P(j\mid t_R)은 클래스 j 레코드 비율이 각각 t_L과 t_R에 있는 것이다.

예시 데이터 세트를 고려해 보자. 세 가지 속성이 있다: ''savings''(낮음, 중간, 높음), ''assets''(낮음, 중간, 높음), ''income''(수치), 이진 대상 변수 ''credit risk''(좋음, 나쁨) 및 8개의 데이터 포인트가 있다.[28] 전체 데이터는 아래 표에 제시되어 있다. 의사 결정 트리를 시작하기 위해 각 기능을 사용하여 \varphi(s\mid t)의 최대값을 계산하여 루트 노드를 분할할 기능을 찾을 것이다. 이 프로세스는 모든 자식이 순수하거나 모든 \varphi(s\mid t) 값이 설정된 임계값 미만이 될 때까지 계속된다.

고객저축자산소득 (1,000 달러)신용 위험
1중간높음75좋음
2낮음낮음50나쁨
3높음중간25나쁨
4중간중간50좋음
5낮음중간100좋음
6높음높음25좋음
7낮음낮음25나쁨
8중간중간75좋음



''savings'' 기능의 \varphi(s\mid t)를 찾기 위해 각 값의 양을 기록해야 한다. 원래 데이터에는 3개의 낮음, 3개의 중간, 2개의 높음이 포함되어 있다. 낮음 값 중 하나는 좋은 ''신용 위험''을 가지고 있었고, 중간 및 높음 값 중 4개는 좋은 ''신용 위험''을 가지고 있었다. 낮음 ''savings'' 레코드가 왼쪽 자식 노드에 배치되고 다른 모든 레코드가 오른쪽 자식 노드에 배치되도록 후보 분할 s를 가정한다.

:

\varphi(s\mid\text{root}) = 2\cdot\frac 3 8\cdot\frac 5 8\cdot \left(\left|\left(\frac 1 3 - \frac 4 5\right)\right| + \left|\left(\frac 2 3 - \frac 1 5\right)\right|\right) = 0.44



트리를 구축하려면 루트 노드에 대한 모든 후보 분할의 "좋음"을 계산해야 한다. 최대값을 가진 후보가 루트 노드를 분할하고, 이 프로세스는 트리가 완성될 때까지 각 불순 노드에 대해 계속된다.

정보 이득과 같은 다른 메트릭과 비교하여, "좋음" 척도는 더 균형 잡힌 트리를 만들려고 시도하여 보다 일관된 의사 결정 시간을 이끌어낸다. 그러나 순수한 자식 노드를 만드는 데 약간의 우선 순위를 희생하므로 다른 메트릭에서는 없는 추가 분할을 초래할 수 있다.

4. 1. 1. 지니 불순도 (Gini Impurity)

지니 불순도는 집합에 이질적인 것이 얼마나 섞였는지를 측정하는 지표이며 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^{m}_{i=1} {f_i}^{2}

로 나타낼 수 있다.

'''지니 불순도''', '''지니의 다양성 지수''',[26] 또는 생물 다양성 연구에서 '''지니-심슨 지수'''는 이탈리아 수학자 코라도 지니의 이름을 따서 명명되었으며 분류 트리를 위한 CART(분류 및 회귀 트리) 알고리즘에서 사용된다. 지니 불순도는 집합의 레이블 분포에 따라 무작위로, 독립적으로 레이블이 지정된 경우 집합의 임의로 선택된 요소가 잘못 레이블이 지정될 빈도를 측정한다. 노드의 모든 사례가 단일 대상 범주에 속할 때 최소값(0)에 도달한다.

J개의 클래스와 상대 빈도 p_i, i \in \{1, 2, ...,J\}를 가진 항목 집합의 경우, 레이블 i가 있는 항목을 선택할 확률은 p_i이고, 해당 항목을 잘못 분류할 확률은 \sum_{k \ne i} p_k = 1-p_i이다. 지니 불순도는 각 클래스 레이블에 대해 이러한 확률의 쌍별 곱을 합산하여 계산한다.

:\operatorname{I}_G(p) = \sum_{i=1}^J \left( p_i \sum_{k\neq i} p_k \right)

= \sum_{i=1}^J p_i (1-p_i)

= \sum_{i=1}^J (p_i - p_i^2)

= \sum_{i=1}^J p_i - \sum_{i=1}^J p_i^2

= 1 - \sum^J_{i=1} p_i^2.

지니 불순도는 또한 정보 이론적 척도이며 변형 계수 q=2를 갖는 찰리스 엔트로피에 해당하며, 이는 물리학에서 평형이 아닌, 비확장적, 소산적 및 양자 시스템의 정보 부족과 관련이 있다. q\to 1의 극한에서 일반적인 볼츠만-깁스 또는 섀넌 엔트로피를 회복한다. 이러한 의미에서 지니 불순도는 의사 결정 트리에 대한 일반적인 엔트로피 척도의 변형에 지나지 않는다.

4. 1. 2. 정보 획득량 (Information Gain)

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

엔트로피는 다음과 같이 정의된다.

:\Eta(T) = \operatorname{I}_{E}\left(p_1, p_2, \ldots, p_J\right)

= - \sum^J_{i=1} p_i \log_2 p_i

여기서 p_1, p_2, \ldots는 합이 1이고 트리의 분할로 인해 발생하는 자식 노드에 있는 각 클래스의 백분율을 나타내는 분수이다.[27]

: \overbrace{IG(T,a)}^\text{정보 이득}

= \overbrace{\Eta(T)}^\text{엔트로피 (부모)}

  • \overbrace{\Eta(T\mid a)}^\text{엔트로피 합계 (자식)} =-\sum_{i=1}^J p_i\log_2 p_i - \sum_{i=1}^J - \Pr(i\mid a)\log_2 \Pr(i\mid a)


A의 가능한 값에 대한 평균,

: \overbrace{E_A(\operatorname{IG}(T,a))}^\text{예상 정보 이득}

= \overbrace{I(T; A)}^{\text{T 와 A 사이의 상호 정보}}

= \overbrace{\Eta(T)}^\text{엔트로피 (부모)}

  • \overbrace{\Eta(T\mid A)}^\text{엔트로피의 가중 합계 (자식)} =-\sum_{i=1}^J p_i\log_2 p_i - \sum_a p(a)\sum_{i=1}^J-\Pr(i\mid a) \log_2 \Pr(i\mid a)


여기서 엔트로피의 가중 합계는 다음과 같이 주어진다.

:{\Eta(T\mid A)}= \sum_a p(a)\sum_{i=1}^J-\Pr(i\mid a) \log_2 \Pr(i\mid a)

즉, 예상 정보 이득은 상호 정보이며, 이는 평균적으로 ''T''의 엔트로피 감소가 상호 정보임을 의미한다.

정보 이득은 트리를 구축하는 각 단계에서 어떤 특징으로 분할할지 결정하는 데 사용된다. 단순성이 가장 좋으므로 트리를 작게 유지하려고 한다. 이를 위해 각 단계에서 가장 일관된 자식 노드를 생성하는 분할을 선택해야 한다. 일반적으로 사용되는 일관성 척도는 정보라고 하며, 이는 비트 단위로 측정된다. 트리의 각 노드에 대해 정보 값은 "새로운 인스턴스가 해당 노드에 도달한 경우 예 또는 아니오로 분류되어야 하는지 지정하는 데 필요한 예상 정보량"을 나타낸다.[27]

4개의 속성(''outlook''(맑음, 흐림, 비), ''temperature''(더움, 보통, 시원함), ''humidity''(높음, 보통), ''windy''(참, 거짓))과 이진(예 또는 아니오) 목표 변수 ''play'' 및 14개의 데이터 포인트가 있는 예제 데이터 집합을 고려해 보자. 이 데이터에 대한 결정 트리를 구성하려면 네 가지 특징 중 하나를 기준으로 분할된 네 개의 각 트리의 정보 이득을 비교해야 한다. 정보 이득이 가장 높은 분할이 첫 번째 분할로 사용되고, 모든 자식 노드가 각 일관된 데이터를 갖거나 정보 이득이 0이 될 때까지 프로세스가 계속된다.

''windy''를 사용하여 분할의 정보 이득을 찾으려면 먼저 분할 전 데이터의 정보를 계산해야 한다. 원래 데이터에는 9개의 예와 5개의 아니오가 포함되어 있었다.

: I_E([9,5]) = -\frac 9 {14}\log_2 \frac 9 {14} - \frac 5 {14}\log_2 \frac 5 {14} = 0.94

''windy'' 특징을 사용한 분할은 두 개의 자식 노드를 생성하며, 하나는 참 ''windy'' 값이고 다른 하나는 거짓 ''windy'' 값이다. 이 데이터 집합에는 참 ''windy'' 값을 가진 6개의 데이터 포인트가 있으며, 그 중 3개는 예의 ''play''(여기서 ''play''는 목표 변수) 값을 가지고 있고 3개는 아니오 값을 가지고 있다. 거짓 ''windy'' 값을 가진 나머지 8개의 데이터 포인트에는 2개의 아니오와 6개의 예가 포함되어 있다. ''windy''=true 노드의 정보는 위의 엔트로피 방정식을 사용하여 계산된다. 이 노드에는 예와 아니오의 수가 동일하므로 다음과 같다.

: I_E([3,3]) = -\frac 3 6\log_2 \frac 3 6 - \frac 3 6\log_2 \frac 3 6 = -\frac 1 2\log_2 \frac 1 2 - \frac 1 2\log_2 \frac 1 2 = 1

''windy''=false 노드의 경우 8개의 데이터 포인트, 6개의 예 및 2개의 아니오가 있었다. 따라서 다음과 같다.

: I_E([6,2]) = -\frac 6 8\log_2 \frac 6 8 - \frac 2 8\log_2 \frac 2 8 = -\frac 3 4\log_2 \frac 3 4 - \frac 1 4\log_2 \frac 1 4 = 0.81

분할의 정보를 찾으려면, 이러한 두 숫자의 가중 평균을 어느 노드에 얼마나 많은 관측치가 속했는지에 따라 구한다.

: I_E([3,3],[6,2]) = I_E(\text{바람이 부는지 여부}) = \frac 6 {14} \cdot 1 + \frac 8 {14} \cdot 0.81 = 0.89

이제 ''windy'' 특징으로 분할하여 얻은 정보 이득을 계산할 수 있다.

: \operatorname{IG}(\text{바람이 부는지 여부}) = I_E([9,5]) - I_E([3,3],[6,2]) = 0.94 - 0.89 = 0.05

트리를 구축하려면 각 가능한 첫 번째 분할의 정보 이득을 계산해야 한다. 가장 좋은 첫 번째 분할은 가장 많은 정보 이득을 제공하는 분할이다. 이 프로세스는 트리가 완료될 때까지 각 순수하지 않은 노드에 대해 반복된다. 이 예는 Witten et al.에 나타나는 예에서 적용되었다.[27]

정보 이득은 생물 다양성 연구에서 섀넌 지수로도 알려져 있다.

4. 1. 3. 분산 감소 (Variance Reduction)

CART에서 소개된[6] 분산 감소 기법은 목표 변수가 연속형인 경우(회귀 트리)에 자주 사용되며, 이는 다른 많은 지표를 사용하려면 먼저 이산화가 필요하다는 것을 의미한다. 노드 N의 분산 감소는 이 노드에서 분할로 인한 대상 변수 x의 분산의 총 감소로 정의된다.

:

I_{V}(N) = \frac{1}

\sum_{i\in S} \sum_{j\in S} \frac{1}{2}(x_i - x_j)^2 - \left(\frac{1}

\sum_{i\in S_t} \sum_{j\in S_t} \frac{1}{2}(x_i - x_j)^2 + \frac{1}

\sum_{i\in S_f} \sum_{j\in S_f} \frac{1}{2}(x_i - x_j)^2\right)



여기서 S, S_t, S_f는 분할 전 표본 지수 집합, 분할 테스트가 참인 표본 지수 집합, 분할 테스트가 거짓인 표본 지수 집합을 각각 나타낸다. 위의 각 합은 실제로 분산 추정치이지만, 평균을 직접 참조하지 않는 형식으로 작성되었다.

위 공식의 (y_i - y_j)^2를 두 객체 i와 j 사이의 상이성 d_{ij}로 대체하면 분산 감소 기준이 쌍별 상이성을 계산할 수 있는 모든 종류의 객체에 적용된다.[1]

4. 1. 4. "좋음" 척도 ("Goodness" Measure)

1984년 CART에서 사용된 "좋음" 척도는 후보 분할이 순수한 자식 노드를 만들 수 있는 능력과 동일한 크기의 자식 노드를 만들 수 있는 능력 사이의 균형을 최적화하려는 함수이다.[28] 이 과정은 트리가 완성될 때까지 각 불순 노드에 대해 반복된다. 함수 \varphi(s\mid t)는 노드 t에서 후보 분할 s이며, 아래와 같이 정의된다.

:

\varphi(s\mid t) = 2P_L P_R \sum_{j=1}^\text{class count}|P(j\mid t_L) - P(j\mid t_R)|



여기서 t_L과 t_R은 분할 s를 사용하여 노드 t의 왼쪽 및 오른쪽 자식 노드이고, P_L과 P_R은 t의 레코드 비율이 각각 t_L과 t_R에 있는 것이며, P(j\mid t_L)과 P(j\mid t_R)은 클래스 j 레코드 비율이 각각 t_L과 t_R에 있는 것이다.

예시 데이터 세트를 고려해 보자. 세 가지 속성이 있다: ''savings''(낮음, 중간, 높음), ''assets''(낮음, 중간, 높음), ''income''(수치), 이진 대상 변수 ''credit risk''(좋음, 나쁨) 및 8개의 데이터 포인트가 있다.[28] 전체 데이터는 아래 표에 제시되어 있다. 의사 결정 트리를 시작하기 위해 각 기능을 사용하여 \varphi(s\mid t)의 최대값을 계산하여 루트 노드를 분할할 기능을 찾을 것이다. 이 프로세스는 모든 자식이 순수하거나 모든 \varphi(s\mid t) 값이 설정된 임계값 미만이 될 때까지 계속된다.

고객저축자산소득 (1,000 달러)신용 위험
1중간높음75좋음
2낮음낮음50나쁨
3높음중간25나쁨
4중간중간50좋음
5낮음중간100좋음
6높음높음25좋음
7낮음낮음25나쁨
8중간중간75좋음



''savings'' 기능의 \varphi(s\mid t)를 찾기 위해 각 값의 양을 기록해야 한다. 원래 데이터에는 3개의 낮음, 3개의 중간, 2개의 높음이 포함되어 있다. 낮음 값 중 하나는 좋은 ''신용 위험''을 가지고 있었고, 중간 및 높음 값 중 4개는 좋은 ''신용 위험''을 가지고 있었다. 낮음 ''savings'' 레코드가 왼쪽 자식 노드에 배치되고 다른 모든 레코드가 오른쪽 자식 노드에 배치되도록 후보 분할 s를 가정한다.

:

\varphi(s\mid\text{root}) = 2\cdot\frac 3 8\cdot\frac 5 8\cdot \left(\left|\left(\frac 1 3 - \frac 4 5\right)\right| + \left|\left(\frac 2 3 - \frac 1 5\right)\right|\right) = 0.44



트리를 구축하려면 루트 노드에 대한 모든 후보 분할의 "좋음"을 계산해야 한다. 최대값을 가진 후보가 루트 노드를 분할하고, 이 프로세스는 트리가 완성될 때까지 각 불순 노드에 대해 계속된다.

정보 이득과 같은 다른 메트릭과 비교하여, "좋음" 척도는 더 균형 잡힌 트리를 만들려고 시도하여 보다 일관된 의사 결정 시간을 이끌어낸다. 그러나 순수한 자식 노드를 만드는 데 약간의 우선 순위를 희생하므로 다른 메트릭에서는 없는 추가 분할을 초래할 수 있다.

4. 2. 가지치기 (Pruning)

4. 3. 앙상블 방법 (Ensemble Methods)

5. 한계

최적의 결정 트리를 학습하는 문제는 여러 최적성 측면에서, 심지어 단순한 개념에 대해서도 NP-완전으로 알려져 있다.[50][51][34][35] 결과적으로 실용적인 결정 트리 학습 알고리즘은 각 노드에서 지역적으로 최적의 결정을 내리는 탐욕 알고리즘과 같은 휴리스틱에 기반한다. 이러한 알고리즘은 전역적으로 최적의 결정 트리를 반환한다고 보장할 수 없다.[52][36] 국소적 최적성의 탐욕적인 영향을 줄이기 위해 이중 정보 거리(DID) 트리와 같은 일부 방법이 제안되었다.[36]

결정 트리 학습자는 훈련 데이터에서 일반화가 잘 되지 않는 과도하게 복잡한 트리를 생성할 수 있다. 이를 과적합이라고 한다.[37] 이 문제를 피하기 위해 가지치기와 같은 메커니즘이 필요하다(가지치기를 필요로 하지 않는 조건부 추론 접근 방식은 제외).[20][21]

결정 트리는 배타적 논리합이나 패리티, 멀티플렉서와 같은 문제를 학습하기 어렵다.

분류까지의 노드 또는 테스트 수를 정의하는 트리의 평균 깊이는 다양한 분할 기준에서 최소이거나 작을 것이 보장되지 않는다.[38]

서로 다른 레벨 수를 가진 범주형 변수를 포함하는 데이터의 경우, 결정 트리에서의 정보 이득은 더 많은 레벨을 가진 속성을 선호하는 편향을 갖는다.[53][39] 이 문제를 해결하기 위해 정보 이득 비율을 사용할 수 있다.[40] 또는 편향된 예측 변수 선택 문제는 조건부 추론 접근 방식,[20] 2단계 접근 방식,[41] 또는 적응형 교차 검증 특징 선택을 통해 피할 수 있다.[42]

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

약간의 차이에 따라 트리의 모양이 많이 달라질 수 있다. 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이후의 트리 구성이 크게 달라질 수 있다. 결정 트리는 매우 견고하지 않을 수 있으며, 훈련 데이터의 작은 변화는 트리의 큰 변화와 결과적으로 최종 예측의 큰 변화를 초래할 수 있다.[29]

6. 확장

6. 1. 결정 그래프 (Decision Graphs)

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

6. 2. 대체 검색 방법 (Alternative Search Methods)

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

MCMC를 사용하여 트리를 샘플링하는 것도 가능하다.[58][47]

트리는 상향식 방식으로 검색될 수 있다.[59][48] 또는 분류까지 예상되는 테스트 횟수를 줄이기 위해 여러 트리를 병렬로 구성할 수 있다.[38]

7. 구현

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

다수의 데이터 마이닝 소프트웨어 패키지는 하나 이상의 결정 트리 알고리즘(예: 랜덤 포레스트) 구현을 제공한다.

오픈 소스 예시는 다음과 같다.


  • ALGLIB, 데이터 분석 기능을 갖춘 C++, C# 및 Java 수치 해석 라이브러리 (랜덤 포레스트)
  • KNIME, 무료 오픈 소스 데이터 분석, 보고 및 통합 플랫폼 (결정 트리, 랜덤 포레스트)
  • Orange, 오픈 소스 데이터 시각화, 머신 러닝 및 데이터 마이닝 툴킷 (랜덤 포레스트)
  • R (통계 컴퓨팅을 위한 오픈 소스 소프트웨어 환경으로, rpart, party 및 randomForest 패키지와 같은 여러 CART 구현을 포함)
  • scikit-learn (Python 프로그래밍 언어를 위한 무료 오픈 소스 머신 러닝 라이브러리).
  • Weka (무료 오픈 소스 데이터 마이닝 제품군으로, 많은 결정 트리 알고리즘을 포함)


주목할 만한 상용 소프트웨어는 다음과 같다.

  • MATLAB
  • Microsoft SQL Server
  • RapidMiner
  • SAS Enterprise Miner
  • IBM SPSS Modeler

참조

[1] 논문 Discrepancy Analysis of State Sequences http://journals.sage[...] 2011
[2] 논문 Top 10 algorithms in data mining 2008-01-01
[3] 서적 Data mining with decision trees: theory and applications, 2nd Edition World Scientific Pub Co Inc
[4] 서적 Understanding Machine Learning http://www.cs.huji.a[...] Cambridge University Press 2014
[5] 논문 Induction of decision trees https://link.springe[...]
[6] 서적 Classification and regression trees Wadsworth & Brooks/Cole Advanced Books & Software
[7] 문서 Stochastic gradient boosting https://astro.temple[...] Stanford University 1999
[8] 서적 The elements of statistical learning : Data mining, inference, and prediction. Springer Verlag 2001
[9] 문서 k-DT: A multi-tree learning method. Proceedings of the Second Intl. Workshop on Multistrategy Learning 1993
[10] 문서 Committees of decision trees. Cognitive Technology: In Search of a Humane Interface 1996
[11] 논문 Bagging Predictors
[12] 논문 Rotation forest: A new classifier ensemble method
[13] 논문 Learning Decision Lists http://people.csail.[...] 1987-11
[14] 논문 Interpretable Classifiers Using Rules And Bayesian Analysis: Building A Better Stroke Prediction Model 2015
[15] 논문 Falling Rule Lists http://www.jmlr.org/[...] 2016-01-22
[16] 논문 A System for Induction of Oblique Decision Trees
[17] 논문 An exploratory technique for investigating large quantities of categorical data
[18] 논문 A method of choosing multiway partitions for classification and decision trees https://doi.org/10.1[...] 1991
[19] 문서 '"CHAID and Earlier Supervised Tree Methods' https://www.research[...] Contemporary Issues in Exploratory Data Mining in the Behavioral Sciences 2013
[20] 논문 Unbiased Recursive Partitioning: A Conditional Inference Framework
[21] 논문 An Introduction to Recursive Partitioning: Rationale, Application and Characteristics of Classification and Regression Trees, Bagging and Random Forests
[22] 논문 Fuzzy decision trees: issues and methods
[23] 논문 An analysis of boosted ensembles of binary fuzzy decision trees http://www.sciencedi[...]
[24] 논문 Top-down induction of decision trees classifiers-a survey
[25] 학위논문 Techniques and heuristics for acquiring symbolic knowledge from examples. https://d-nb.info/92[...] Doctoral thesis
[26] 웹사이트 Growing Decision Trees https://www.mathwork[...]
[27] 서적 Data Mining https://archive.org/[...] Morgan Kaufmann
[28] 서적 Discovering knowledge in data: an introduction to data mining John Wiley & Sons, Inc
[29] 서적 An Introduction to Statistical Learning https://archive.org/[...] Springer
[30] 논문 Using Tree-Based Machine Learning for Health Studies: Literature Review and Case Series 2022-12-01
[31] 서적 Data science for business : [what you need to know about data mining and data-analytic thinking] O'Reilly 2013
[32] 논문 Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems 2020-06-01
[33] 논문 Decision tree approximations of Boolean functions
[34] 논문 Constructing Optimal Binary Decision Trees is NP-complete
[35] 문서 Automatic construction of decision trees from data: A multidisciplinary survey https://cs.nyu.edu/~[...] Data Mining and Knowledge Discovery 1998
[36] 저널 Efficient Construction of Decision Trees by the Dual Information Distance Method http://www.eng.tau.a[...] 2014-02-13
[37] 서적 Principles of Data Mining
[38] 웹사이트 Parallel Construction of Decision Trees with Consistently Non Increasing Expected Number of Tests http://www.eng.tau.a[...] Applied Stochastic Models in Business and Industry, Vol. 31(1) 64-78 2021-01-30
[39] 학술대회 Bias of importance measures for multi-valued attributes and solutions https://www.research[...]
[40] 저널 Induction of Decision Trees
[41] 저널 Structural equation model trees.
[42] 저널 Cross-Validated Variable Selection in Tree-Based Methods Improves Predictive Performance 2017
[43] 웹사이트 CiteSeerX http://citeseer.ist.[...]
[44] 문서 Tan & Dowe (2003) http://www.csse.mona[...]
[45] 서적 Proceedings of the Eighteenth International Conference on Machine Learning, June 28–July 1, 2001
[46] 저널 A Survey of Evolutionary Algorithms for Decision-Tree Induction
[47] 서적 Bayesian CART model search
[48] 서적 Proceedings of the 11th International Conference on Intelligent Systems Design and Applications (ISDA 2011)
[49] 저널 Top-down induction of decision trees classifiers-a survey
[50] 저널 Constructing Optimal Binary Decision Trees is NP-complete
[51] 문서 Automatic construction of decision trees from data: A multidisciplinary survey. Data Mining and Knowledge Discovery
[52] 저널 Efficient Construction of Decision Trees by the Dual Information Distance Method http://www.eng.tau.a[...] Quality Technology & Quantitative Management (QTQM), 11( 1), 133-147 2015-04-27
[53] 학술대회 Bias of importance measures for multi-valued attributes and solutions
[54] URL http://citeseer.ist.psu.edu/oliver93decision.html
[55] 문서 Tan & Dowe (2003) http://www.csse.mona[...]
[56] 문서 Breeding Decision Trees Using Evolutionary Techniques, Proceedings of the Eighteenth International Conference on Machine Learning, p.393-400, June 28-July 01, 2001
[57] 문서 A Survey of Evolutionary Algorithms for Decision-Tree Induction http://ieeexplore.ie[...] IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, vol. 42, n. 3, p. 291-312, May 2012.
[58] 문서 Bayesian CART model search. Journal of the American Statistical Association 93.443 (1998): 935-948.
[59] 문서 A bottom-up oblique decision tree induction algorithm http://dx.doi.org/10[...] Proceedings of the 11th International Conference on Intelligent Systems Design and Applications (ISDA 2011).


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com