> For the complete documentation index, see [llms.txt](https://ykkim.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ykkim.gitbook.io/wiki/machine-learning/lecture-notes/decision_tree.md).
# Decision Tree
## Decision Tree
* 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타냄.
* 분류(Classification)와 회귀(Regression) 문제에 적용 가능.
* 계산복잡성 대비 높은 예측 성능을 지님.
### Example (Process of Decsion Tree)
* Find the feature and criteria that best differentiate the data.
* Q) How to findd the criteria that best differentiate the data?
* -> Maximize the **information gain**. (Minimize the **Impurity (Entropy)**)
  
### Entropy, Impurity
* 불순도 (Impruty)
* 해당 범주 안에 서로 다른 데이터가 얼마나 섞여 있는가?
* Entropy
* 불순도를 수치적으로 나타낸 척도
$$Entropy = - \sum\nolimits\_i {({p\_i}){{\log }\_2}({p\_i})}$$
#### Entropy Example
### Impurity Indicator
* Entropy $$Entropy(A) = \sum\limits\_{i = 1}^d {{R\_i}\left( { - \sum\limits\_{k = 1}^m {{p\_k}{{\log }\_2}({p\_k})} } \right)}$$
* Gini-Index $$G.I(A) = \sum\limits\_{i = 1}^d {\left( {{R\_i}\left( {1 - \sum\limits\_{k = 1}^m {{p\_{ik}}^2} } \right)} \right)}$$
### Rish of Overfitting
* Decision trees tend to overfit on data with a large number of features. Getting the right ratio of samples to number of features is important, since a tree with few samples in high dimensional space is very likely to overfit.
* We have to limit **the maximum depth, the maximum number of nodes, minimum number of data for one node to split**.
### Pruning
* Prevent overfitting using pruning. 
#### Cost Function of Pruning
* 𝐶𝐶(𝑇)=𝐸𝑟𝑟(𝑇)+𝛼×𝐿(𝑇)
* 𝐶𝐶(𝑇): 의사결정나무의 비용 복잡도 (=오류가 적으면서 terminal node 수가 적은 단순한 모델일수록 작은 값)
* 𝐸𝑅𝑅(𝑇): 검증 데이터에 대한 오분류율
* 𝐿(𝑇): terminal node의 수 (구조 복잡도)
* 𝐴𝑙𝑝ℎ𝑎: 𝐸𝑅𝑅(𝑇)와 𝐿(𝑇)를 결합하는 가중치 (사용자에 의해 부여, 보통 0.01\~0.1의 값을 사용)
### Summary
* 의사결정나무는 한번에 하나씩의 설명변수를 사용하여 예측 가능한 규칙들의 집합을 생성하는 알고리즘.
* 한번 분기 때마다 변수 영역을 두개로 구분한 뒤 각 영역의 순도가 증가(엔트로피가 감소)하는 방향으로 학습을 진행함.
* 입력 변수 영역을 두 개로 구분하는 \*\*재귀적 분기(recursive partioning)\*\*와 구분된 영역을 통합하는 \*\*가지치기(pruning)\*\*의 두가지 과정으로 나뉨.
* 의사결정나무는 계산복잡성 대비 높은 예측 성능을 내는 장점을 지님.
* 하지만, 결정경계(decision boundary)가 데이터 축에 수직이어서 특정 데이터에만 잘 작동하는 한계가 있음.
* 이러한 문제를 극복하기 위해 **랜덤포레스트**와 같은 기법을 사용.
* 랜덤포레스트란?
* 같은 데이터에 대해 의사결정나무를 여러 개 만들어서 그 결과를 조합해서 예측 성능을 높이는 기법
* 동일한 데이터로부터 복원추출을 통해 30개 이상의 데이터셋을 만들어서 각각에 의사결정나무를 적욯안 뒤 학습 결과를 취합하는 방식으로 동작
## References
* Theoretical Explanation
*
*
* Python Implementation of Decision Tree
*
* Scikit-learn documentation
*
* MATHLAB Example
* fitctree & fitrtree (instruction & algorithm)
*
*
* View Decision Tree
*
* Prediction Using Classification and Regression Trees
*