▲

의사결정나무 – 중첩된 결정 규칙의 놀라운 힘

 (mlu-explain.github.io)
1P by GN⁺ 13시간전 | ★ favorite | 댓글 1개
  • 데이터 분류를 위해 특징 공간을 반복적으로 분할하는 구조로, 각 단계에서 가장 정보 이득이 큰 분할을 선택함
  • 엔트로피(Entropy) 를 이용해 데이터의 순도(purity) 를 측정하고, 이를 기반으로 정보 이득(Information Gain) 을 계산함
  • ID3 알고리듬 은 부모 노드와 자식 노드의 엔트로피 차이를 계산해 최적의 분할 지점을 찾으며, 재귀적으로 트리를 확장함
  • 엔트로피 대신 Gini 불순도 를 사용할 수도 있으며, 두 방법은 대부분 유사한 결과를 보이지만 계산 효율이 다름
  • 과도한 분할은 과적합(overfitting) 과 불안정성 을 초래하므로, 가지치기(pruning) 나 랜덤 포레스트(Random Forest) 로 이를 완화함

의사결정나무의 기본 개념

  • 의사결정나무는 데이터를 위에서 아래로 분할하며, 각 단계에서 조건 규칙을 적용해 데이터를 잘 구분되는 영역으로 나눔
    • 각 분할은 데이터의 특정 특징(feature) 과 임계값(cutoff value) 에 따라 결정됨
    • 목표는 분류(classification) 시 클래스가 잘 구분되는 순수한 노드를 만드는 것임

엔트로피(Entropy)의 정의와 성질

  • 엔트로피는 정보의 불확실성을 측정하는 지표로, 확률 (p_i) 에 대해 (H = -\sum p_i \log_2(p_i)) 로 정의됨
  • 주요 성질
    1. 하나의 사건만 확률 1이고 나머지가 0일 때 (H=0), 즉 불확실성이 없음
    2. 모든 사건의 확률이 동일할 때 엔트로피가 최대가 되어 가장 불순한 상태를 나타냄
    3. 확률이 균등해질수록 엔트로피가 증가함
  • 따라서 순수한 노드는 엔트로피가 0이고, 혼합된 노드는 높은 엔트로피 값을 가짐

정보 이득(Information Gain)과 ID3 알고리듬

  • 정보 이득은 분할 전후의 엔트로피 차이로 계산되며, 데이터 분할의 효율성을 나타냄
    • 수식: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
  • ID3 알고리듬 단계
    1. 각 특징의 엔트로피 계산
    2. 다양한 분할 기준으로 데이터셋을 나누고 정보 이득 계산
    3. 정보 이득이 최대인 분할을 선택해 결정 노드 생성
    4. 더 이상 분할할 수 없을 때 리프 노드 생성
    5. 모든 하위 집합에 대해 재귀 수행, 단 모든 요소가 동일 클래스일 경우 중단
  • 예시로, Diameter ≤ 0.45 조건이 정보 이득 0.574로 최대였기 때문에 첫 번째 분할로 선택됨

Gini 불순도와 대안적 측정

  • Gini 불순도(Gini impurity) 는 엔트로피의 대안으로, 정보의 불순도를 측정하는 또 다른 방식임
    • 로그 계산이 없어 계산 속도가 빠름
    • 불균형 데이터셋에서는 엔트로피가 더 신중한 선택이 될 수 있음
  • 두 방법 모두 일반적으로 유사한 결과를 산출함

과적합과 불안정성 문제

  • ID3 알고리듬은 엔트로피를 최소화하기 위해 계속 분할을 수행하므로, 트리가 지나치게 깊어질 수 있음
    • 이는 과적합(overfitting) 을 유발해 새로운 데이터에 대한 일반화 성능이 저하됨
  • 또한 데이터의 작은 변화에도 트리 구조가 크게 달라지는 불안정성(high variance) 문제가 존재함
    • 예: 훈련 데이터의 5%에 작은 가우시안 노이즈를 추가해도 완전히 다른 트리가 생성됨
  • 해결책으로 가지치기(pruning) 를 통해 트리의 깊이, 리프 수, 최소 샘플 수 등을 제한할 수 있음

랜덤 포레스트로의 확장

  • 단일 의사결정나무의 불안정성을 완화하기 위해, 여러 개의 트리를 서로 다른 데이터 샘플로 학습시켜 예측을 결합하는 방식이 사용됨
    • 이 접근법이 랜덤 포레스트(Random Forest) 로, 높은 안정성과 일반화 성능을 제공함
  • 이는 의사결정나무의 단점을 보완하며, 현재까지 가장 성공적인 머신러닝 알고리듬 중 하나로 평가됨

결론 및 추가 학습

  • 의사결정나무는 해석이 용이하고 학습 속도가 빠르며 전처리가 간단한 모델임
  • 그러나 과적합과 불안정성 문제를 해결하기 위해 가지치기나 앙상블 기법이 필요함
  • 글에서는 회귀용 트리, 엔드컷 선호(end-cut preference), 하이퍼파라미터 등은 다루지 않았으며, 관련 자료를 통해 추가 학습을 권장함
▲
GN⁺ 13시간전  [-]
Hacker News 의견들

  • 분류기를 배울 때 나에게 아주 잘 통했던 비밀 무기는 먼저 좋은 선형 분류기를 학습하는 것임
    그 선형 분류기의 비임계 출력값을 하나의 추가 특성 차원으로 사용해 결정 트리를 학습하고, 이를 부스팅된 트리 시스템으로 감싸는 방식임
    이렇게 하면 결정 트리의 약점을 선형 모델이 보완하고, 반대로 선형 모델이 어려워하는 부분을 트리가 처리하게 됨
    데이터 회전이나 축 정규화도 고려할 수 있지만 대부분 필요하지 않았음
    다만, 특성이 매우 희소할 때는 트리가 분할점을 찾기 어려워함

    • 생각해보면 이건 강화학습에서도 비슷하게 쓰이는 접근임
      원래 상태(raw state)에 추가 계산을 더해 관찰된 상태(observed state) 를 만들고 학습하는 식임
      예를 들어 스네이크 게임에서 뱀의 좌표뿐 아니라 탈출 경로 수 같은 파생 특성을 계산해 학습함
    • 결정 트리의 아킬레스건은 결국 피처 엔지니어링임
      데이터를 정제하고 특성을 잘 설계하지 않으면, 신경망 같은 블랙박스 모델보다 훨씬 나쁜 결과가 나옴
      아이러니하게도 신경망은 이런 잠재 특성을 스스로 찾아내지만, 왜 그렇게 작동하는지는 해석하기 어려움
    • 원하는 목적에 맞는 다양한 트리 변형이 있음
      Oblique Decision Tree, Model Tree (M5), Logistic Model Tree (LMT), Hierarchical Mixture of Experts (HME) 등이 그 예임
    • “equi-label 영역이 분할된 구조를 가진다”는 표현이 정확히 무슨 뜻인지 궁금함
    • 이 아이디어는 Arjovsky와 Bottou 등이 쓴 IRM 논문의 핵심과도 닮아 있음

  • 2010년경 CERN에서 일할 때, Boosted Decision Tree가 가장 인기 있는 분류기였음
    설명 가능성과 표현력의 균형 덕분이었고, 당시에는 물리 분석에 신경망을 쓰는 걸 문화적으로 꺼렸음
    지금은 시대가 많이 변했음

    • 이런 변화가 조금 걱정스러움
      물리학에서는 단순히 곡선을 잘 맞추는 것보다 인과적 메커니즘을 이해하는 게 중요함
      프톨레마이오스의 주전원(epicycle) 체계가 천체 운동을 더 잘 맞췄지만, 원인을 설명하지는 못했던 것처럼 말임
    • 나도 물리학(이론) 출신인데, 다른 분야에서 결정 트리를 써보니 “설명 가능성”이 과대평가된 면이 있음
      깊이가 조금만 깊어져도 해석이 거의 불가능한 정글이 되어버림
      신경망도 마찬가지로 내부 연산을 따라갈 수는 있지만, 결국 왜 그런 결정을 내렸는지는 알 수 없음
    • Boosted Decision Tree와 Boosted Random Forest는 같은 것인지 궁금함

  • 같은 사이트에 Random Forest 설명도 있음 → mlu-explain/random-forest

  • 흥미로운 사실: 1비트 신경망(single-bit neural network) 은 사실상 결정 트리임
    이론적으로 대부분의 신경망을 if-else 체인으로 “컴파일”할 수 있지만, 언제 잘 작동하는지는 아직 명확하지 않음

    • “신경망이 결정 트리다”라는 논문(arXiv:2210.05189)을 읽어봤는데, 실제로는 트리가 엄청 거대해짐
      개념을 확장한 수준이라 직접적인 매핑은 어려움
      그래서 구체적으로 어떤 의미로 말한 건지 더 설명해주면 좋겠음
    • 이런 변환을 실제로 해주는 소프트웨어나 논문이 있는지 궁금함. 주말 프로젝트로 해보면 재밌을 듯함

  • 결정 트리의 가장 큰 장점은 속도임
    저지연 환경에서 트리 기반 분류기를 작은 신경망으로 대체하려 했지만, 신경망은 정확도는 조금 높아도 추론 지연(latency) 이 100배 이상 높았음

    • 또한 단일 결정 트리는 엣지 디바이스로 직접 포팅하기 쉬움
      반면 부스팅이나 배깅된 트리는 복잡하고, 다른 고전적 ML 알고리즘도 이식성이 떨어짐

  • 어떤 ML 교재(아마 ESL)에서는 결정 트리를 이렇게 표현했음
    “해석 가능하고, 빠르고, 다양한 데이터에 잘 작동하고, 스케일링에 둔감하고, 튜닝 파라미터도 적지만... 잘 작동하지 않는다”
    다만 배깅이나 부스팅으로 이 단점을 보완할 수 있지만, 그 과정에서 원래의 장점을 일부 잃게 됨

  • 결정 트리를 정말 좋아함. 내가 가장 선호하는 고전적 ML 알고리즘임
    GNU Guile로 순수 함수형 병렬 구현을 만들어봤음 → 코드 링크
    다만 Guile에는 NumPy나 DataFrame 같은 게 없어 데이터 표현이 비효율적임

    • NumPy나 DataFrame이 Guile보다 어떤 점에서 유리한지 궁금함
      Guile은 트리 조작에 적합하므로, 결정 트리 구현에는 자연스러움
      다만 머신 코드로 컴파일하면 더 효율적일 것임
      참고로 Lush(https://lush.sourceforge.net/)나 aiscm(https://wedesoft.github.io/aiscm/)도 살펴볼 만함

  • 전문가의 모호한 의사결정도 종종 단순한 결정 트리나 결정 체인으로 모델링할 수 있음
    전문가 본인은 복잡하다고 생각하지만, 실제로는 간단한 트리가 더 잘 설명하는 경우가 많음
    예전엔 회귀나 거리 기반 클러스터링이 더 세련돼 보였지만, 트리가 훨씬 효과적임
    관련 내용은 Oxford Handbook of Expertise 7장에 자세히 나와 있음

    • 예전에 본 시각화에서는 결정을 2D 평면에서 공간 분할로 표현했음
      결국 결정 트리는 kD-Tree처럼 가능성 공간을 나누고 각 영역에 행동을 부여하는 구조임
      전문가의 미묘한 판단은 경계면의 세밀함에서 오지만, 트리도 꽤 좋은 근사치를 제공함

  • 사이트가 흥미롭고 프레젠테이션도 좋았음
    다만 일부 텍스트의 색상 대비가 낮아 읽기 어려웠음

    • 나도 같은 생각임. Firefox Reader View가 큰 도움이 됨
      접근성은 단지 장애인을 위한 게 아니라, 가독성을 높이는 기본 요소임

  • 요즘 딥러닝 시대에 결정 트리가 과소평가되고 있음
    하지만 여전히 해석 가능하고 빠르며 충분히 실용적임
    나는 웹사이트 분석용 점수 시스템을 트리 기반으로 만들었는데,
    “메타 설명이 있는가?”, “3초 안에 로드되는가?”, “모바일 대응이 되는가?” 같은 조건을 평가함
    사용자는 왜 그런 점수를 받았는지 바로 이해할 수 있음
    신경망이 73점을 준 이유를 설명하는 건 불가능하지만, 트리는 그게 쉬움

답변달기