Level-wise Tree Growth vs Leaf-wise Tree Growth

트리 기반의 머신러닝 알고리즘에서 Level-wise Tree Growth와 Leaf-wise Tree Growth는 트리 성장 방식의 차이를 설명하는 두 가지 방식입니다. 이 두 방식은 각 단계에서 노드를 확장하는 방식에 차이가 있으며, 알고리즘의 성능과 과적합 방지에 영향을 미칠 수 있습니다.

1. Level-wise Tree Growth

개념

• Level-wise Tree Growth는 트리가 균형 잡힌 형태로 자라도록, 같은 깊이의 모든 노드를 한 번에 확장하는 방식입니다. 트리의 각 레벨에서 모든 노드가 동시에 확장되기 때문에 트리가 고르게 성장합니다.

특징

• 균형 성장: 트리의 모든 노드가 동시에 확장되므로, 트리가 균형 있게 자랍니다.
• 효율성: 병렬 처리가 용이하며, 메모리 관리 측면에서 유리할 수 있습니다.
• 과적합 위험이 적음: 트리가 고르게 자라기 때문에 특정 부분에서만 과도하게 복잡해지는 것을 방지할 수 있습니다.

장점

• 균형 잡힌 트리로 인한 과적합 방지.
• 계산을 병렬화하기 쉽고, 트리 생성 속도가 빠름.

단점

• 깊이가 제한된 경우, 덜 유익한 분기도 포함될 수 있음.
• 복잡한 데이터에서는 성능이 떨어질 수 있음.

---

2. Leaf-wise Tree Growth

개념

• Leaf-wise Tree Growth는 트리에서 가장 높은 손실을 가진 리프 노드(leaf)를 먼저 확장하는 방식입니다. 즉, 전체 트리에서 가장 유용한 정보가 있는 노드를 우선적으로 확장하여 불균형하게 트리가 자랄 수 있습니다.

특징

• 비균형 성장: 트리의 특정 리프 노드가 다른 리프 노드보다 더 많이 확장되므로 트리가 불균형하게 자랄 수 있습니다.
• 성능 향상: 더 큰 손실을 가진 리프를 확장하여 트리의 성능을 더욱 향상시킬 수 있습니다.
• 과적합 위험: 불균형한 트리 구조로 인해 과적합(overfitting)이 발생할 가능성이 큽니다.

장점

• 손실이 큰 리프 노드를 확장하여 성능을 극대화할 수 있음.
• 복잡한 데이터에서 더 높은 예측 성능을 발휘할 수 있음.

단점

• 과적합의 위험이 존재함. 트리의 특정 부분만 깊이 자라게 되어 복잡한 모델이 생성될 수 있음.
• 계산 비용이 더 높고, 메모리 사용량이 많아질 수 있음.

---

주요 차이점

	Level-wise Tree Growth	Leaf-wise Tree Growth
트리 성장 방식	같은 깊이의 모든 노드를 동시에 확장	손실이 가장 큰 리프 노드를 먼저 확장
성장 패턴	균형 잡힌 성장	불균형한 성장
과적합 위험	낮음	높음
성능	일반적으로 적당한 성능	복잡한 데이터에서 높은 성능
계산 효율성	더 효율적 (병렬 처리 가능)	계산 비용이 더 높음
복잡성 제어 방법	최대 깊이나 노드 당 최소 샘플 수에 제한	최대 잎 수나 최소분할 이득에 제한
알고리즘 예시	C4.5, CART, XGBoost	LightGBM

---

예시

• Level-wise Tree Growth는 일반적으로 LightGBM에서 사용되는 방식으로, 데이터가 매우 클 때 메모리 사용량을 줄이고, 병렬 처리로 속도를 향상시키는 데 유리합니다.
• Leaf-wise Tree Growth는 XGBoost와 같은 알고리즘에서 많이 사용되며, 성능을 극대화하려는 경우 유리하지만 과적합의 위험이 크기 때문에 학습률이나 가지치기(pruning) 등의 과적합 방지 기법이 필요합니다.