Leaf-wise VS Level-wise

🔻Reference

Decision trees: leaf-wise (best-first) and level-wise tree traverse

Shi, H. (2007). Best-first Decision Tree Learning (Thesis, Master of Science (MSc)). The University of Waikato, Hamilton, New Zealand.

🔻개요

결정트리가 데이터를 분할하는 방식으로 리프 중심 분할과 레벨 중심 분할이 있다. 각각 leaf-wise 는 그래프 탐색 알고리즘에서 DFS와, level-wise는 그래프 탐색 알고리즘에서 BFS와 대응한다고 볼 수 있다.. (그러나 개인적인 생각으로, 그래프 탐색 알고리즘과 정확히 일치한다고 보긴 어려울 것 같다. 위의 stack exchange 답변자도 BFS, DFS보다 tree growth 관점에서의 용어들로만 설명한 걸 보면 그래프 탐색 알고리즘 관점으로 보는 걸 탐탁치 않아 하는 것 같다.)

tree growth 관점 그래프 탐색 관점 분류 알고리즘

best-first = leaf-wise DFS LightGBM

depth-first = level-wise BFS C4.5, CART, XGBoost

⚠️트리 분할 관점에서 Depth-first는 오히려 그래프 탐색 관점에서 BFS에 해당한다. 혼동하면 안 된다.
중요한 점은 두 방식 모두 특별한 하이퍼 파라미터 설정 없이 사용한다면, 결국(eventually) 똑같은 트리 구조(same tree)를 보일 것이라는 점이다.
- 그러나 일반적으로 full depth를 사용하는 경우가 적기 때문에, 대부분의 경우에 leaf-wise의 트리 완성 속도가 더 빠르고 때론 성능도 좋다.

tree growth 관점	그래프 탐색 관점	분류 알고리즘
best-first = leaf-wise	DFS	LightGBM
depth-first = level-wise	BFS	C4.5, CART, XGBoost

🔻구분

🔸Standard Decision Tree (Level-wise, depth-first)

대표적인 결정트리 알고리즘인 C4.5, CART는 깊이을 우선으로(레벨 중심으로) 분할-정복 알고리즘을 사용하여 노드를 확장해나간다.

+) 분할정복(Devide-Conquer Strategy) : 하나의 문제를 작은 여러 개의 문제로 쪼갠 후 재귀적으로 각 문제를 해결한 후에, 다시 합쳐서 원래의 문제를 해결하는 방법을 뜻한다.
- 비슷한 탐색 유형의 다른 알고리즘으로는 모든 경우의 수를 다 탐색하는 브루트포스(Brute-Force) 알고리즘이 있다.
- 장점 : 병렬적으로 문제를 해결하기 때문에 속도가 빠르다.
- 단점 : 병렬처리를 하기 위한 충분한 메모리가 없다면 Stack Overflow 에러가 발생한다.
basic idea of standard decision tree - Depth First
1. 루트 노드의 규칙으로 사용할 속성(attribute)을 하나 고르고 IG지수나 지니계수 같은 지표를 토대로 불순도가 가장 작아지도록 가지(branches)를 나눈다.
2. 그리고 해당 규칙대로 각 가지에 데이터셋을 분할한다.
3. 1번과 2번을 반복한다.
  - 노드를 확장하기 위해 fixed order가 사용된다. → 일반적으로 해당 층(level, depth)에서 왼쪽에서 오른쪽으로 노드들을 탐색하며 불순도가 0이 아닌 노드들을 expansion(확장, 분할)의 대상으로 선정한다.
  - 그리고 expansion의 대상인 chosen branch에 대해 또 1,2번을 반복하는 것이다. >> 그래프 탐색 알고리즘 관점에서 BFS인 이유이다. 한 층, 한 층씩 반복한다.

🔸Best-First Decision Tree (Leaf-wise, best-first)

Best-First decision trees
1. depth-first의 1번과 동일. 속성을 정하고 혼잡도 지표를 기준으로 트리를 분할한다.
  - 단, 이때 트리는 항상 이진 분할을 한다.
2. 마찬가지로 train instance를 가지를 뻗은 노드들에 분할한다.
3. 3번에서 Depth-first와 차이점을 보이는데, 바로 expansion이 가능한 노드들(이진 분류니까 둘 중 하나) 중 단 하나의 ‘Best’ subset만을 chosen branch로 선택하고 해당 노드만 expansion의 대상으로 선정한다는 것이다. >> 노드 확장을 위해 best-first order 를 사용
  - Best-first order : 두 개의 expansion 대상 subsets(=dataset) 중에서 최대 손실값(max delta loss)을 가지는 노드를 chosen branch로 결정한다.
    - max delta loss : 사용하는 지표에 따라 다르겠지만, 혼잡도가 가장 높은 경우를 의미한다.