의사결정 트리 학습

시리즈의 일부
기계 학습 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 검출 데이터 클리닝 자동 ML 어소시에이션 규칙 강화 학습 구조화된 예측 기능 엔지니어링 기능 학습 온라인 학습 준지도 학습 비지도 학습 순위 매기기 학습 문법 유도
지도 학습 (분류 • 회귀) 의사결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 네이비 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) 서포트 벡터 머신(SVM)
클러스터링 버치 치유하다 계층적 k자형 기대 최대화(EM) DBSCAN 광학 평균 이동
치수 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE
구조화된 예측 그래픽 모델 베이즈 네트 조건부 랜덤 필드 히든 마르코프
이상 검출 k-NN 국소 특이치 계수
인공신경망 자동 인코더 인지 컴퓨팅 딥 러닝 딥 드림 다층 퍼셉트론 RNN LSTM GRU ESN 저장고 계산 제한 볼츠만 기계 GAN somerset. 컨볼루션 뉴럴 네트워크 유넷 트랜스포머 비전. 스파이킹 뉴럴 네트워크 메모리 트랜지스터 전기화학 RAM(ECRAM)
강화 학습 Q-러닝 사사 시간차(TD) 멀티 에이전트 셀프 플레이
인간과의 학습 액티브 러닝 크라우드 소싱 휴먼 인 더 루프
모델 진단 학습 곡선
이론. 커널 머신 바이어스-분산 트레이드오프 컴퓨터 학습 이론 경험적 리스크 최소화 오컴 러닝 PAC 학습 통계학 학습 VC 이론
기계학습장 NeurolIPS ICML ML JMLR ArXiv:cs.LG
관련 기사 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 기계학습의 개요
v t

Decision Tree Learning은 통계, 데이터 마이닝 및 기계 학습에 사용되는 감독 학습 접근법입니다.이 형식주의에서는 분류 또는 회귀 결정 트리가 일련의 관측치에 대한 결론을 도출하는 예측 모형으로 사용됩니다.

대상 변수가 이산적인 값 집합을 취할 수 있는 트리 모델을 분류 트리라고 합니다.이 트리 구조에서 잎은 클래스 라벨을 나타내고 분지는 클래스 라벨로 이어지는 피쳐의 결합을 나타냅니다.목표 변수가 연속형 값(일반적으로 실수)을 취할 수 있는 결정 트리를 회귀 트리라고 합니다.

Decision Tree는 그 지능성과 ^[1]단순성을 고려할 때 가장 인기 있는 기계 학습 알고리즘 중 하나입니다.

의사결정 분석에서 의사결정 트리는 의사결정과 의사결정을 시각적이고 명시적으로 표현하기 위해 사용될 수 있다.데이터 마이닝에서 Decision Tree는 데이터를 기술합니다(그러나 결과 분류 트리는 의사결정을 위한 입력이 될 수 있습니다).

일반

Decision Tree 학습은 데이터 ^[2]마이닝에서 일반적으로 사용되는 방법입니다.목표는 여러 입력 변수를 기반으로 목표 변수의 값을 예측하는 모형을 만드는 것입니다.

Decision Tree는 예를 분류하기 위한 간단한 표현입니다.이 섹션에서는 모든 입력 피쳐가 유한 이산 도메인을 가지고 있으며 "분류"라고 불리는 단일 타깃 피쳐가 있다고 가정합니다.분류 도메인의 각 요소를 클래스라고 합니다.Decision Tree 또는 분류 트리는 각 내부(비리프) 노드에 입력 피쳐로 라벨이 지정된 트리입니다.입력 피쳐로 라벨이 붙여진 노드에서 나오는 호는 타겟 피쳐의 가능한 각 값으로 라벨이 지정되거나 다른 입력 피쳐의 하위 결정 노드로 연결됩니다.트리의 각 리프에는 클래스 또는 클래스 전체에 걸친 확률 분포로 라벨이 붙여져 있어 데이터 세트가 특정 클래스 또는 특정 확률 분포(의사결정 트리가 잘 구성되어 있는 경우 클래스의 특정 서브셋으로 치우쳐 있음)로 분류되었음을 나타냅니다.

트리는 트리의 루트노드를 구성하는 소스 세트를 서브셋으로 분할하여 구축됩니다.서브셋은 후속 서브셋을 구성합니다.분할은 분류 ^[3]기능을 기반으로 한 일련의 분할 규칙을 기반으로 합니다.이 프로세스는 재귀 파티션이라고 하는 재귀적인 방법으로 파생된 각 서브셋에서 반복됩니다.재귀는 노드의 하위 집합이 모두 동일한 대상 변수 값을 갖거나 분할하면 예측에 더 이상 값이 추가되지 않을 때 완료됩니다.TDIDT(^[4]Top-down decision tree of decision tree)의 이 프로세스는 탐욕 알고리즘의 한 예이며,^[5] 단연코 데이터에서 의사결정 트리를 학습하는 가장 일반적인 전략이다.

데이터 마이닝에서 의사결정 트리는 주어진 데이터 세트의 설명, 분류 및 일반화를 지원하는 수학적 및 계산 기술의 조합으로도 설명할 수 있습니다.

데이터는 다음 형식의 레코드로 제공됩니다.

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

종속 변수 $(\displaystyle$ Y$)$는 우리가 이해, 분류 또는 일반화하려는 대상 변수입니다.$벡터{\displaystyle }$x(\$displaystyle\textbf$ {x$})$는 해당 작업에 사용되는 기능 ${\displaystyle {x1\mathrm{}}_{}}$ ${\displaystyle {x2\mathrm{}}_{}}$ $(\$$}$ 등)으로 구성됩니다.

Decision Tree 유형

데이터 마이닝에 사용되는 의사결정 트리는 크게 두 가지 유형으로 구성됩니다.

• 분류 트리 분석은 예측 결과가 데이터가 속한 클래스(이산)인 경우입니다.
• 회귀 트리 분석은 예측 결과를 실수(예: 집값 또는 환자의 병원 체류 기간)로 간주할 수 있는 경우이다.

분류 및 회귀 나무(CART) 분석이라는 용어는 ^[6]Breiman 등이 1984년에 처음 도입한 위의 절차 중 하나를 가리키는 데 사용되는 포괄적인 용어이다.회귀에 사용되는 나무와 분류에 사용되는 나무는 몇 가지 유사점이 있지만, ^[6]분할 위치를 결정하는 데 사용되는 절차와 같은 차이점도 있다.

종종 앙상블 방식이라고 불리는 일부 기술은 둘 이상의 의사결정 트리를 구성합니다.

• 부스트 트리 이전에 잘못 모델링된 트레이닝 인스턴스를 강조하기 위해 새로운 각 인스턴스를 트레이닝함으로써 단계적으로 앙상블을 구축합니다.일반적인 예로는 AdaBoost가 있습니다.이것들은 회귀형 ^[7][8]및 분류형 문제에 사용할 수 있습니다.
• 초기 앙상블 방법인 부트스트랩 통합(또는 백지화) 의사결정 트리는 대체와 함께 훈련 데이터를 반복적으로 재샘플링하고 합의 ^[9]예측을 위해 트리를 투표함으로써 여러 의사결정 트리를 구축한다.
  • 랜덤 포레스트 분류자는 부트스트랩 집약의 특정 유형입니다.
• 회전 포레스트 – 모든 의사결정 트리가 우선 입력 ^[10]기능의 랜덤 서브셋에 주성분 분석(PCA)을 적용하여 훈련됩니다.

Decision Tree의 특별한 경우는 Decision ^[11]List입니다.이는 일방적인 Decision Tree로, 모든 내부 노드는 정확히 1개의 리프 노드와 정확히 1개의 내부 노드를 자식으로 가지고 있습니다(단, 단일 리프 노드인 bottommost 노드 제외).의사 결정 목록은 표현력은 떨어지지만, 추가된 희소성^{[citation needed]}, 욕심이 없는 학습^[12] 방법 및 ^[13]단조로운 제약으로 인해 일반 의사 결정 트리보다 이해하기 쉽다.

주목할 만한 Decision Tree 알고리즘은 다음과 같습니다.

• ID3(반복 이분법 3)
• C4.5(ID3의 후계자)
• CART(분류 및 회귀 트리)^[6]
• 카이-제곱 자동 상호 작용 탐지(CHAID). 분류 ^[14][15][16]트리를 계산할 때 다단계 분할을 수행합니다.
• MARS: 수치 데이터를 더 잘 처리할 수 있도록 의사결정 트리를 확장합니다.
• 조건부 추론 트리.비모수 검정을 분할 기준으로 사용하는 통계 기반 접근법으로, 과적합을 방지하기 위해 다중 검정을 위해 수정되었습니다.이 접근방식은 편향되지 않은 예측 변수를 선택할 수 있으며 플루닝이 ^[17][18]필요하지 않습니다.

ID3와 ^{[citation needed]}CART는 거의 동시에 독립적으로 발명되었지만(1970년과 1980년 사이) 교육 튜플에서 의사결정 트리를 학습하기 위해 유사한 접근방식을 따른다.

또한 퍼지 의사결정 트리(FDT)^[19]로 알려진 특별한 버전의 의사결정 트리의 정의를 위해 퍼지 집합 이론의 개념을 활용하는 것이 제안되었다.이러한 유형의 퍼지 분류에서는 일반적으로 입력 $벡터{\displaystyle }$x(\$displaystyle\textbf {x})$는 각각 다른 신뢰값을 갖는 여러 클래스와 관련지어진다.최근 FDT의 부스트 앙상블도 조사되었으며, 매우 효율적인 다른 퍼지 분류기와 ^[20]견줄 만한 성능을 보였다.

측정 기준

의사결정 트리를 구성하는 알고리즘은 일반적으로 항목 ^[5]집합을 가장 잘 분할하는 각 단계에서 변수를 선택하여 하향식으로 작동합니다.알고리즘에 따라 "최적"을 측정하기 위해 서로 다른 메트릭을 사용합니다.이 값은 일반적으로 부분 집합 내에서 목표 변수의 동질성을 측정합니다.몇 가지 예를 다음에 제시하겠습니다.이러한 메트릭은 각 후보 서브셋에 적용되며, 결과 값은 (예를 들어 평균) 결합되어 분할 품질의 측정치를 제공한다.기본 메트릭에 따라 의사결정 트리 학습을 위한 다양한 휴리스틱 알고리즘의 성능이 ^[21]크게 달라질 수 있습니다.

양의 정확성 평가

암 연구를 위해 의사결정 나무를 사용할 때와 같이 참된 긍정을 정확하게 식별하는 것이 참된 부정을 식별하는 것보다 중요하다(혼란 매트릭스 참조). 단순하지만 효과적인 메트릭을 사용할 수 있다.

이 메트릭인 "긍정적 정확성 추정"은 다음과 같이 정의됩니다.

${\displaystyle E_{P}=TP-FP}$

이 방정식에서는 total false positive(FP; 총 false positive)가 total true positive(TP; 총 참 긍정)에서 감산됩니다.결과 수치는 기능이 데이터 내에서 얼마나 많은 양의 예를 정확하게 식별할 수 있었는지에 대한 추정치를 제공하며, 이는 기능이 더 많은 양의 샘플을 올바르게 분류할 수 있었다는 것을 의미합니다.다음으로 특정 기능의 완전한 혼돈 매트릭스를 지정했을 때 메트릭을 사용하는 예를 나타냅니다.

특징 A 혼란 매트릭스

예측된 학급 실제 클래스	암	비암
암	8	3
비암	2	5

여기서 TP 값은 8, FP 값은 2(표에서 밑줄이 그어진 숫자)가 되는 것을 알 수 있습니다.이 수치를 방정식에 대입하면 추정치를 계산할 수 있습니다.$displaystyle E_{p$$TP-FP=8-2=6$즉, 이 기능에 대한 견적을 사용하면 6점을 받을 수 있습니다.

그러나 이 수치는 추정치일 뿐이라는 점에 유의해야 한다.예를 들어, 두 기능 모두 FP 값이 2이고 두 기능 중 하나의 TP 값이 더 높으면 방정식을 사용할 때 결과 추정치가 더 높기 때문에 해당 기능이 다른 기능보다 순위가 높아집니다.따라서 일부 피쳐가 다른 피쳐보다 더 많은 양의 샘플을 가질 경우 메트릭을 사용할 때 일부 오류가 발생할 수 있습니다.이 문제를 해결하기 위해, 실제 실제 실제 양수 비율(TPR)을 제공하기 위해 혼란 매트릭스에서 값의 비율을 고려하는 감도(Sensitivity)로 알려진 보다 강력한 메트릭을 사용할 수 있다.이들 메트릭의 차이는 다음 예에 나타나 있습니다.

특징 A 혼란 매트릭스 예측된 학급 실제 클래스 암 비암 암 8 3 비암 2 5	기능 B 혼란 매트릭스 예측된 학급 실제 클래스 암 비암 암 6 2 비암 2 8
${\displaystyle E_{p}=TP-FP=8-2=6}$ ${\displaystyle TPR=TP/(TP+FN)=8/(8+3)\약 0.73}$	${\displaystyle E_{p}=TP-FP=6-2=4}$ ${\displaystyle TPR=TP/(TP+FN)=6/(6+2)=0.75}$

이 예에서 기능 A의 추정치는 6이고 TPR은 약 0.73인 반면 기능 B의 추정치는 4이고 TPR은 0.75입니다.이는 일부 기능에 대한 양의 추정치가 높을 수 있지만 양의 추정치가 낮은 다른 기능에 비해 해당 기능의 정확한 TPR 값이 낮을 수 있음을 나타냅니다.데이터 및 의사결정 트리의 상황 및 지식에 따라 문제의 신속하고 쉬운 해결을 위해 양의 추정치를 사용할 수도 있습니다.한편, 보다 경험이 풍부한 사용자는 TPR 값을 사용하여 기능의 순위를 매기는 것을 선호할 가능성이 높다.이는 데이터의 비율과 양성으로 분류되어야 할 모든 샘플을 고려하기 때문이다.

지니 불순물

지니 더러움과 지니의 다양성 index,[22]또는 Gini-Simpson 지수 생명 다양성 연구에서, CART(분류와 회귀 나무)알고리즘에서 분류 나무도 wa 집합에서 얼마나 자주 임의 선택된 요소의 지니 불순물(이탈리아 수학자 코르라도 지니의 이름을 딴)은 라벨이 부정확할 것 사용된다.sra부분 집합의 레이블 분포에 따라 레이블이 지정됩니다.지니 불순물은 라벨$i$가 선택된 아이템의 $확률{\displaystyle {}_{}}$ $({$$displaystyle$$p_{i$})에$$ 해당 아이템 분류에서 오류가 발생할 확률${\displaystyle \underset{k}{}}$ k${\displaystyle \underset{}{}{}_{}}$ ${\displaystyle {ip}_{}}$ ${\displaystyle \mathrm{k}}$ ${\displaystyle =}$ ${\displaystyle {}_{}}$ -$$ i ( \ $displaystyle$ \$sum$_ {$k$ \ $neq$i } p _ { k } =$$1 - p$_$ { k $}$ 를$$ 곱하여 계산할 수 있습니다.노드내의 모든 케이스가 단일의 타겟카테고리에 속하는 경우는, 최소(0)에 달합니다.

지니 불순물은 또한 정보 이론적인 측정치이며 변형 $계수{\displaystyle }$ ${\displaystyle \mathrm{q}}$ $=$ 2({$displaystyle$ q$=2$의 Tsallis Entropy에 해당하며, 물리학에서는 불균형, 비불순물, 산란성 및 양자 시스템의 정보 부족과 관련이 있습니다.$제한{\displaystyle }$ ${\displaystyle \mathrm{q}}$ ${\displaystyle \to }$ 1$($표시 $스타일 q$ 대$1$)의$$ 경우 일반적인 볼츠만-집스 또는 섀넌 엔트로피를 복구합니다.그런 의미에서 지니 불순물은 의사결정 트리에 대한 일반적인 엔트로피 측정값의 변형에 불과하다.

J$(\displaystyle$ J$)$ 클래스의$$ 항목 $세트$에 대한 Gini 불순도를 계산하려면 i$({$${\displaystyle 1}$,${\displaystyle }$2, ${\displaystyle ...,}$ $J})$ {$style$ i$\in,$ {$1,$ 2, ..., J$\backslash \})$ {$display style$p_$$${i$})를 클래스 $(\style$i)로$$ 라벨이 붙은 항목의 분수로 $합니다{\displaystyle {}_{}}$.

${\displaystyle \operatorname {I}_{G}(p)=\sum _{i=1}^{J}\sum _{k}\sum _{i}{k}\sum _{i}{i}={i}(1-p_i}={i}\sum_{i}^{i}_{i}_{i}_{i}_{i}_{i}_{i}_{i}{{{i}}}{{i}}{i}}{{i}}}{{i}}{{{{{$

정보 획득

ID3, C4.5 및 C5.0 트리 생성 알고리즘에서 사용됩니다.정보 획득은 엔트로피 개념과 정보 이론의 정보 내용에 기초한다.

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

$\displaystyle \mathrm {H}(T)=\operatorname {I}_{E}\left(p_{1},p_{2},\ldots,p_{J}\right)=-\sum _{i=1}{J}p_{i}\log _{2}p_i}$

${\displaystyle {여기}_{}}$서 p${\displaystyle {}_{}}$1, ${\displaystyle {}_{}{2\mathrm{}}_{}}$,$…({style p_{1}, p_{2},\ldots})$는 최대 1을 더한 분수로 ^[23]트리의 분할로 인해 자노드에 존재하는 각 클래스의 백분율을 나타냅니다.

$${\displaystyle {IG(T,a)} ^{\text{time{H}(T)} ^{\text{mathrm{H}(부모)} ^{\mid a} ^{\text{entropies(자녀)}}}}$$

${\displaystyle =-\sum _{i=1}^{i}\log _{2}p_{i}-\sum _{i=1}^J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

A$(\style$ A$)$의 $가능$한 값에 대한 평균값,

$${\displaystyle {E_{A}(\operatorname {IG}(T,a)}) ^{\text{\text{와 }}A} =\overbrace {\text{\text{와 }}}} =\brace {\mathrm{T} ^H}}}}$$

${\displaystyle =-\sum _{i}^{i}-\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

엔트로피의 가중치 합계가 주어지는 경우,

${\displaystyle {\mathrm {H}(T\mid A)}=\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

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

정보 게인은 트리 구축의 각 단계에서 분할할 피쳐를 결정하는 데 사용됩니다.심플함이 최선이기 때문에 우리는 나무를 작게 유지하고 싶다.그러기 위해서는 각 단계에서 가장 일관된 자노드가 되는 분할을 선택해야 합니다.일반적으로 사용되는 일관성의 척도는 비트 단위로 측정되는 정보라고 합니다.트리의 각 노드에 대해 정보 값은 "예가 해당 노드에 도달한 경우 새 인스턴스가 예 또는 아니오로 분류되어야 하는지 여부를 지정하는 데 필요한 예상 정보량을 나타냅니다."^[23]

전망(맑음, 흐림, 비), 온도(덥음, 온화, 서늘함), 습도(높음, 정상) 및 바람(참, 거짓)의 네 가지 속성이 포함된 데이터 집합의 예와 2진수(예 또는 아니오) 목표 변수, 놀이 및 14개의 데이터 점을 고려합니다.이 데이터에 대한 의사결정 트리를 구축하기 위해서는 4가지 특징 중 하나로 분할된 4가지 트리의 정보 게인을 각각 비교할 필요가 있다.정보 게인이 가장 높은 분할이 첫 번째 분할로 간주되며 모든 자식 노드가 일관된 데이터를 갖거나 정보 게인이 0이 될 때까지 프로세스가 계속됩니다.

windy를 사용하여 분할의 정보 게인을 구하려면 먼저 분할 전에 데이터 내의 정보를 계산해야 합니다.원본 데이터에는 9개의 예스와 5개의 아니오가 포함되어 있었다.

${\displaystyle I_{E}([9,5])=-{\frac {9}{14}\log _{2}{14}-{\frac {5}{14}}\log _{2}{5}{14}=0.94}$

windy 기능을 사용하여 분할하면 두 개의 자식 노드가 생성됩니다.하나는 windy 값이 true이고 다른 하나는 windy 값이 false입니다.이 데이터 세트에는 진정한 바람 값을 가진 6개의 데이터 포인트가 있으며, 이 중 3개는 재생 값(목표 변수가 놀이)인 yes와 3개는 재생 값 no가 있습니다.windy 값이 false인 나머지 8개의 데이터 포인트에는 2개의 no와 6개의 yes가 포함됩니다.windy=true 노드의 정보는 위의 엔트로피 방정식을 사용하여 계산됩니다.이 노드에는 '예'와 '아니오'의 수가 같기 때문에

${\displaystyle I_{E}([3,3])=-{\frac {3}{6}\log _{2}{6}-{\frac {3}{6}-{\log {2}{frac {6}}=-{\frac {1}{2}{6}}-{frac {2}}{frac}$

windy=false 노드의 경우 데이터 포인트가 8개(예 6개, 아니요 2개)였습니다.이렇게 해서

${\displaystyle I_{E}([6,2])=-{\frac {6}{8}\log _{2}{8}-{\frac {2}{8}=-{\frac {3}{2}{8}}}-{\log {3}frac}{8}$

분할 정보를 찾기 위해 각 노드에 포함된 관측치의 수에 따라 이 두 숫자의 가중 평균을 구합니다.

${\displaystyle I_{E}([3,3], [6,2])=I_{E}({\text{windy or not})=cdot1+{\frac{8}{14}\cdot0.81=0.89}$

이제 윈디 기능으로 분할하여 얻을 수 있는 정보 게인을 계산할 수 있습니다.

${\displaystyle \operatorname {IG}({\text{param}})=I_{E}([9,5])-I_{E}([3,3],[6,2])=0.94-0.89=0.05}$

트리를 구축하려면 가능한 각 첫 번째 분할의 정보 이득을 계산해야 합니다.최적의 첫 번째 분할은 가장 많은 정보를 얻을 수 있는 분할입니다.이 프로세스는 트리가 완료될 때까지 각 불순 노드에 대해 반복됩니다.이 예는 Witten ^[23]등에 나타난 예에서 수정되었다.

정보 획득은 생물 다양성 연구에서 섀넌 지수라고도 한다.

분산감소

CART에서 ^[6]도입된 분산 감소는 종종 대상 변수가 연속형(회귀 트리)인 경우에 사용됩니다. 즉, 다른 많은 메트릭을 사용하기 전에 먼저 이산화가 필요합니다.노드 N의 분산 감소는 이 노드에서의 분할에 의한 타깃 변수 Y의 분산의 합계 감소로 정의됩니다.

${\displaystyle I_{V}(N)=black {1}{S ^{2}\sum _{i\in S}\sum _{j\in S}{\flac {1}{2}-y_{j}^2}-\flac {S_{t}^2}{2}}{{}}}S}\sum{2}\right)}$

$여기$서 S$(\displaystyle$ S$),$ $(\$ $및{\displaystyle {}_{}}$ ${\displaystyle S_{}}$f(\$displaystyle S_{$f$$})는 각각 프리플릿 샘플 인덱스 세트, 분할 테스트가 참인 샘플 인덱스 세트 및 분할 테스트가 거짓인 샘플 인덱스 세트입니다.그러나 위의 각 합계는 실제로 평균을 직접 참조하지 않고 형식으로 작성된 분산 추정치입니다.

'선도'의 척도

1984년 ^[24]CART에서 사용된 '선도'는 후보 분할의 역량의 균형을 최적화하여 같은 크기의 아이를 만들 수 있는 역량의 순자녀를 만드는 기능이다.이 프로세스는 트리가 완료될 때까지 각 불순 노드에 대해 반복됩니다.$함수{\displaystyle }$" ( ${\displaystyle st}$t )$${ $displaystyle$\ $varphi ( s$ \ $mid$ t$$)$$。$여기서$s { \ $displaystyle$s }는 노드$$t { $displaystyle$t $\}$에서 후보 분할입니다.

$\displaystyle \varphi (s\mid t)=2P_{L}P_{R}\sum _{j=1}^{\text{class count} P(j\mid t_{L})-P(j\mid t_{R})}$

${\displaystyle {여기}_{}}$서 t L$(\$ $및$ ${\displaystyle t_{}}$ R$(\$은 $분할{\displaystyle }$s(\$displaystyle$ s$)$를 사용하는 $노드{\displaystyle }$ t$(\displaystyle$t_{R})의$$ 왼쪽 자식이며, ${\displaystyle P_{}}$$$L$(\$})과$$PR$(\displaystyle P_{$R})은$$tyledisplaystyle P_{R})의$$tyledisplaystyle P_{R}에 $있는{\displaystyle }$ 레코드의 비율입니다.$(\$ $및$${\displaystyle }T{\displaystyle (\backslash {}_{}}$ $t_{R$에서는 각각 j$(\$displaystyle$$$t_${$L})$와$displaystyle t_{R$})에서는 j${\displaystyle {}_{}\mathrm{mid<img\; alt="\{\backslash displaystyle\; P(j\backslash mid\; t\_\{L\})\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/8269ba3fd961b4706fb5374d321e4c310e1efcbb"\; style="vertical-align:\; -0.838ex;\; width:8.641ex;\; height:2.843ex;">}}$ t_${R})$ $클래스$ $jdisplaystyle$ records의 비율입니다.$play style$t_${R$를 선택합니다.

저축(낮음, 중간, 높음), 자산(낮음, 중간, 높음), 소득(숫자 값), 이진 목표 가변 신용 위험(양호, 낮음, 중간, 높음)과 8개의 데이터 ^[24]포인트가 있는 데이터 세트의 예를 생각해 보십시오.전체 데이터는 아래 표에 나와 있습니다.Decision Tree를 시작하려면 각 기능을 사용하여 루트노드를 분할하는 ${\displaystyle \mathrm{최대값}}$ "${\displaystyle }$( s${\displaystyle t}$t )$$\ $displaystyle$\ $varphi ($ s \ $mid$ t$$)"를 계산합니다.이 프로세스는 모든 자녀가 순수하거나 모든${\displaystyle }$"${\displaystyle s"}$ $"$ {$displaystyle \varphi (s\mid$ t$)}$ 값이$$ 설정된 임계값을 밑돌 때까지 계속됩니다.

고객.	비용 절감	자산	수입(1,000달러)	신용위험
1	중간의	높은	75	좋아요.
2	낮다	낮다	50	나빠
3	높은	중간의	25	나빠
4	중간의	중간의	50	좋아요.
5	낮다	중간의	100	좋아요.
6	높은	높은	25	좋아요.
7	낮다	낮다	25	나빠
8	중간의	중간의	75	좋아요.

기능 절약량 $중{\displaystyle }$" " ( ${\displaystyle st}$t$$) \ $displaystyle$\$varphi ( s$ \ $mid$ t $)"$를 찾으려면 각 값의 수량을 기록해야 합니다.원래 데이터에는 로우 3개, 미디어 3개 및 하이 2개가 포함되어 있습니다.저신용자 중에는 신용위험이 좋은 사람이 1명, 중신용위험과 고신용자 중에는 4명이 신용위험이 좋은 사람이 4명이었다.$한$ 후보자가 저축률이 낮은 레코드가 왼쪽 아이에 삽입되고 다른 모든 레코드가 오른쪽 아이에 삽입되도록$분할$한다고 가정합니다.

$\displaystyle \varphi ( s \ mid \ text { root } = 2 \ cdot { frac { 3 } \ cdot \ left \ frac { 5 } \ cdot \ left ( \ left \ frac { 1 } { 3 } ) - { right } \ left + \ frac 2 \ frac 2 \ frac }$

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

정보 획득과 같은 다른 지표와 비교하여 "선량성"의 척도는 보다 균형 잡힌 트리를 생성하려고 시도하며, 보다 일관된 의사결정 시간을 가져옵니다.그러나 순수 하위 항목을 생성하는 데 일부 우선 순위가 희생되어 다른 메트릭에는 없는 추가 분할이 발생할 수 있습니다.

사용하다

이점

다른 데이터 마이닝 방법 중에서 의사결정 트리에는 다음과 같은 다양한 이점이 있습니다.

• 이해하기 쉽고 해석하기 쉽다.간단한 설명을 통해 의사결정 트리 모델을 이해할 수 있습니다.트리는 전문가가 아닌 사람이 쉽게 ^[25]해석할 수 있도록 그래픽으로 표시할 수도 있습니다.
• 수치 ^[25]및 범주형 데이터를 모두 처리할 수 있습니다.다른 기법은 보통 한 가지 변수만 있는 데이터 세트를 분석하는 데 특화되어 있다(예를 들어, 관계 규칙은 명목 변수에만 사용할 수 있고 신경 네트워크는 숫자 변수나 0-1 값으로 변환된 범주형에만 사용할 수 있다).초기 의사결정 트리는 범주형 변수만 처리할 수 있었지만 C4.5와 같은 최신 버전에는 이러한 ^[2]제한이 없습니다.
• 데이터 준비가 거의 필요 없습니다.다른 기술에서는 데이터 정규화가 필요한 경우가 많습니다.나무는 정성적 예측 변수를 처리할 수 있기 때문에 더미 ^[25]변수를 생성할 필요가 없다.
• 흰색 상자 또는 개방형^[2] 상자 모델을 사용합니다.모델에서 주어진 상황을 관찰할 수 있는 경우 조건에 대한 설명은 부울 논리로 쉽게 설명할 수 있습니다.반면 블랙박스 모델에서 결과에 대한 설명은 일반적으로 이해하기 어렵다(예를 들어 인공 신경망).
• 통계적 검정을 사용하여 모형을 검증할 수 있습니다.따라서 모델의 신뢰성을 고려할 수 있습니다.
• 교육 데이터 또는 예측 잔차를 가정하지 않는 비모수적 접근법. 예를 들어 분포, 독립성 또는 일정 분산 가정 없음
• 대규모 데이터셋에서 뛰어난 성능을 발휘합니다.표준 컴퓨팅 리소스를 사용하여 합리적인 시간에 대량의 데이터를 분석할 수 있습니다.
• 인간의 의사결정을 다른 ^[25]접근법보다 더 밀접하게 반영합니다.이는 인간의 의사결정/행동을 모델링할 때 유용할 수 있습니다.
• 동일 선형성에 강하며, 특히 부스팅에 강합니다.
• 빌트 기능 선택.관련 없는 추가 기능은 이후 실행 시 제거할 수 있도록 덜 사용됩니다.Decision Tree 속성의 계층은 ^[26]속성의 중요성을 반영합니다.즉, 위에 있는 기능이 가장 ^[27]유용한 정보입니다.
• 의사결정 트리는 XOR와 ^[28]같은 부울 함수에 근사할 수 있습니다.

제한 사항

• 나무는 매우 강하지 않을 수 있다.트레이닝 데이터의 작은 변경은 트리의 큰 변경과 결과적으로 최종 ^[25]예측으로 이어질 수 있습니다.
• 최적 의사결정 트리를 학습하는 문제는 최적성의 몇 가지 측면에서 그리고 단순한 ^[29][30]개념에 대해서도 NP-완전하다고 알려져 있다.결과적으로 실용적인 의사결정 트리 학습 알고리즘은 각 노드에서 국소적으로 최적의 결정이 이루어지는 탐욕 알고리즘과 같은 휴리스틱스에 기초한다.이러한 알고리즘에서는 글로벌하게 최적의 Decision Tree를 반환할 수 없습니다.로컬 최적성의 탐욕스러운 효과를 줄이기 위해, 이중 정보 거리(DID) 트리와 같은 몇 가지 방법이 ^[31]제안되었습니다.
• 의사결정 트리 학습자는 교육 데이터에서 잘 일반화되지 않는 지나치게 복잡한 트리를 생성할 수 있습니다(이것을 과적합이라고 합니다).^[32]이 문제를 피하기 위해서는 플루닝 등의 메커니즘이 필요합니다(조건부 추론 접근법 등의 일부 알고리즘을 제외하고 ^[17][18]플루닝이 필요하지 않습니다).
• 분류될 때까지 노드 수 또는 테스트 수로 정의되는 트리의 평균 깊이는 다양한 분할 ^[33]기준에서 최소 또는 작음을 보장하지 않습니다.
• 수준 수가 다른 범주형 변수를 포함하는 데이터의 경우 의사결정 트리의 정보 게인은 수준이 ^[34]더 높은 속성으로 치우칩니다.이 문제에 대처하려면 정보 게인이 가장 높은 Atribute를 선택하는 대신 정보 게인이 평균 정보 게인보다 큰 Atribute 중 정보 게인 비율이 가장 높은 Atribute를 선택할 수 있습니다.^[35] 이는 정보 이득이 매우 낮은 속성에는 부당한 이점을 주지 않으면서 많은 수의 구별된 값을 가진 속성을 고려하는 것에 대해 의사결정 트리를 편향시킨다.또는 조건부 추론 접근법,^[17] 2단계 ^[36]접근법 또는 적응형 이탈원아웃 특성 ^[37]선택을 통해 편향된 예측 변수 선택 문제를 피할 수 있다.

실장

많은 데이터 마이닝 소프트웨어 패키지는 하나 이상의 Decision Tree 알고리즘을 구현합니다.

예를 들면 다음과 같습니다.

• Salford Systems CART(원래 CART ^[6]작성자의 고유 코드를 라이선스한 것),
• IBM SPSS Modeler,
• Rapid Miner,
• SAS Enterprise Miner,
• 매트랩,
• R(rpart, party, random 등의 여러 CART 구현을 포함하는 통계 컴퓨팅용 오픈 소스 소프트웨어 환경)포레스트 패키지)
• Weka(자유롭고 오픈 소스 데이터 마이닝 스위트로 많은 Decision Tree 알고리즘이 포함되어 있습니다),
• 오렌지색
• KNIME,
• Microsoft SQL Server [ 1 ]및
• skikit-learn(Python 프로그래밍 언어용 무료 오픈 소스 머신 러닝 라이브러리)

내선번호

의사결정 그래프

Decision Tree에서는 루트 노드에서 리프 노드까지의 모든 경로가 결합 또는 AND를 통해 진행됩니다.결정 그래프에서는 Disjunctions(OR; 분리)를 사용하여 Minimum Message Length(MML;^[38] 최소 메시지 길이)를 사용하여 2개의 경로를 추가로 결합할 수 있습니다.의사결정 그래프는 이전에 기술되지 않은 새로운 속성을 동적으로 학습하고 그래프 ^[39]내의 다른 장소에서 사용할 수 있도록 더욱 확장되었다.보다 일반적인 코딩 방식은 더 나은 예측 정확도와 로그 손실 확률론적 ^{[citation needed]}스코어링을 가져온다.일반적으로 의사결정 그래프는 의사결정 나무보다 잎이 적은 모형을 추론한다.

대체 검색 방법

진화 알고리즘은 국지적 최적 결정을 피하고 선입견 ^[40][41]없이 의사결정 트리 공간을 탐색하기 위해 사용되어 왔다.

MCMC를 ^[42]사용하여 트리를 샘플링할 수도 있습니다.

트리는 상향식으로 ^[43]검색할 수 있습니다.또는 여러 ^[33]개의 트리를 병렬로 구성하여 분류할 때까지 예상되는 테스트 횟수를 줄일 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

추가 정보

• James, Gareth; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2017). "Tree-Based Methods" (PDF). An Introduction to Statistical Learning: with Applications in R. New York: Springer. pp. 303–336. ISBN 978-1-4614-7137-0.

외부 링크

• C++에서의 의사결정 트리의 진화적 학습
• 분할 기준으로서의 정보 게인에 대한 매우 상세한 설명