Decision Tree

개요

One model for performing decision tree analysis was created by J. Ross Quinlan at the University of Sydney and presented in his book Machine Learning, vol.1, no. 1, in 1975 (10). His first algorithm for decision tree creation was called the Iterative Dichotomiser 3 (ID3). (A Brief History of Decision Tree Analysis)

책 출간 연도가 1975로 되어 있는데, 책 정보에 따르면 1986년이 맞다. (책 본문 PDF) 위키피디어에도 1986으로 기입되어 있다. Quinlan은 첫 ID3 이후 C4.5(1993), C5.0 상업적 모델로 발전 시켰다. C5.0은 책 『Applied Predictive Modeling』에도 나온다. 번역서는 『실전 예측 분석 모델링』 CART 부터 C4.5, PART등을 다룬다. p.429 ~ 446

노드에 포함된 모든 example들이 원하는 y값에 대해 같은 y값을 가지고 있을때 pure하다. 아래는 타이타닉 데이타 분석 결과. dtreeviz가 보다 직관적이다.

decision trees는 80.9%, random forest는 81.6%. 데이타의 변별력이 부족하므로 큰 차이는 없으나, 전처리를 통해 92%까지 높일 수 있다.

ID3

ID3, C4.5에서는 Entropy를 기준으로 하는 Information gain을 사용한다.

information gain is a synonym for Kullback–Leibler divergence (Wikipedia)

(What is Entropy and why Information gain matter in Decision Trees?)

(ID3 수도 코드와 선행 지식, ID3 코드 구현)

CART

CART 알고리즘에서는(scikit-learn은 CART를 최적화한 알고리즘 사용) Gini impurity를 디폴트로 사용한다. Not to be confused with Gini coefficient. CART는 greedy 알고리즘이다. ID3도 동일. CART는 Leo Breiman et. al(1984) (Who invented the decision tree?)

수식대로 계산해보면 균등하게 분류될수록 Gini impurity가 높다. 한쪽으로 쏠릴 수록 Gini impurity가 낮다. e.g. {0.5, 0.5} = 0.5, {0.1, 0.9} = 0.18. A perfect separation results in a Gini score of 0. 기본적으로 Gini impurity와 Entropy는 동일한 패턴을 보인다.

응용

테러리스트 구분에 Decision Trees를 사용했다. 신용카드 사기 검출과 얼굴 인식에는 신경망을 이용했다. (넘버스 2017)

Random Forest

넷플릭스 프라이즈의 우승자는 머신러닝 알고리즘 수백 가지를 통합한 메타학습 알고리즘을 사용했다. 왓슨은 메타학습 알고리즘을 사용해 후보로 올라온 대답들 중에서 최종 대답을 선택했다. 이런 종류의 메타학습을 스택킹 stacking이라 부르며 ‘세상에 공짜는 없다’라는 정리의 창시자 데이비드 월퍼트가 생각해낸 방식이다. 이보다 훨씬 더 간단한 메타학습은 통계학자 레오 브라이먼Leo Breiman et al., 2001이 발명한 배깅 bagging이 있다. 배깅은 여러 학습 예제를 무작위로 만들어 알고리즘에 적용 후 그 결과들을 투표 방식으로 통합한다. 이렇게 하는 까닭은 분산이 줄어들기 때문이다. 배깅은 데이터가 예상 밖의 변화가 생겼을때 단일 모델보다 훨씬 덜 민감하므로 정확도를 향상하는 매우 쉬운 방법이다. 키넥트는 랜덤 포레스트를 사용한다.
p.384 『마스터 알고리즘』 2015, 2016

  • bagging trees
    • b=1…B random sampling
    • tree 구성(ID3)
    • classification B개 모든 tree를 사용해서 분류, majority vote로 결정.
    • decrease variance while bias stays same.
  • attributes random

특징은 아래와 같다.

  • easy to interpret. 『수학 없이 배우는 데이터 과학과 알고리즘』 에서는 ‘블랙박스’ 모델이라고 언급했으나 어렵게나마 도식화가 가능하다는 점에서 딥러닝 처럼 완전한 블랙박스로 보긴 힘들다. 다만, decision trees에 비해서는 해석하기 어렵다.
  • can induce non-linear decision boundaries.
  • fast at prediction(O(height of tree))

scikit-learn의 random forest에서 tree.tree_.threshold[x]의 값을 직접 수정하여 decision rule을 변경해서 원본 decision tree(상단), decision tree의 rule을 수정(하단)한 것과 decision boundaries의 변화를 도식화한 모습이다.

Gradient Boosting

학습이론가 요아브 프로인트 Yoav Freund와 롭 샤피르 Rob Schapire가 발명한 부스팅 boosting이 있다. 부스팅은 여러 학습 알고리즘을 결합하는 대신 이전 모형들이 저지른 실수를 바로잡는 새 모형을 이용하면서 같은 분류기를 데이터에 반복 적용한다. 학습을 할 때마다 잘못 분류한 사례의 가중치를 증가시켜 다음번 학습에서는 이 사례에 더욱 집중하도록 한다. 부스팅이라는 이름은 이 과정이 처음에는 무작위 추측보다 그저 약간 좋기만 한 분류기를 지속적으로 강화하여 거의 완전한 분류기로 만든다는 개념에서 나왔다.
p.384 『마스터 알고리즘』 2015, 2016

이전 예측기가 만든 잔여 오차residual error에 새로운 예측기를 학습시킨다. Decision Trees를 기반 예측기로 하는 회귀 문제 풀이를 gradient tree boosting 또는 gradient boosted regression tree(GBRT)라고 한다.

Adaboost

(Yoav Freund and Robert Schapire, 2003)

부스팅은 모든 분류 기법에 적용할 수 있지만, 트리의 가지를 거의 두지 않음으로써 트리 깊이에 제약을 두어 약 분류기로 만들 수 있기 때문에 분류 트리를 가장 많이 쓴다. 브레이먼(1998)은 부스팅에 왜 분류 트리가 적합한지를 설명했다. 분류 트리는 편향성이 낮고, 분산이 높은 기법으로 트리 앙상블을 통해 분산을 낮출 수 있으므로 그 결과 편향성과 분산 모두 낮은 결과를 구한다. (p.451 실전 예측 분석 모델링, 2013, 2018)

C5.0

C5.0은 퀸란이 C4.5 분류 모델에 부스팅이나 각 오차별로 각각 다른 비용을 매기는 방식 등의 기능을 추가해서 개선한 버전이다.

(실전 예측 분석 모델링, 2013, 2018)

여기서는 C5.0의 테스트셋 점수가 가장 높다.


2017 Book Reports · 2018 Book Reports · 2019 Book Reports · AWS · Activation, Cost Functions · CNN, RNN · C++ · Decision Tree · Docker · Go · HTML, CSS, JavaScript · Hadoop, Spark · Information Retrieval · Java · Jupyter Notebooks · Keras · LeetCode · LifeHacks · MySQL · NLP 실험 · NLP · Naive Bayes · OAuth 2.0 · OOP · Python Data Structure Cheatsheet · Python · RSA · Software Deployment · Support Vector Machine · Word Embedding · XGBoost · Scikit Learn · 거리 · 데이터 마이닝 · 데이터 사이언스 · 딥러닝 · 머신러닝 분류기 · 머신러닝 · 비지니스 · 사회심리학 · 수학 · 알고리즘 · 영어 · 운영체제 · 이산수학 · 인공지능 · 자료구조 · 진화생물학 · 컴파일러 · 컴퓨터시스템구조 · 통계학 응용 · 통계학 ·
is a collection of Papers I have written.
© 2000 - Sang-Kil Park Except where otherwise noted, content on this site is licensed under a CC BY-NC 4.0.
This site design was brought from Distill.