by
Apr 01. 2020
의사결정트리 알고리즘의 역사, 랜덤포레스트와 XGB까지
[야만인] 인공지능 탄생의 뒷이야기
로스 퀸란이 만든 알고리즘은 반복이진분류법인 ID3(Iterative Dichotomizer 3)이며,
이후 C4.5에서 C5.0으로 발전합니다.
이 알고리즘들은 집합을 분류할 때 엔트로피 Entropy라는 '집합의 불확실성 정도'로 판단합니다.
이 엔트로피의 개념은 클로드 섀넌의 정보엔트로피에서 가져온 것입니다.
이런 집합의 분류법은 엔트로피 외에도 더 있습니다.
존 하티건 J. A. Hartigan이 만든 CHAID(Chi-squared Automatic Intersection Detection)에서는
카이제곱 χ2을 썼고,
레오 브라이먼 Leo Breiman의 CART(Classification And Regression Trees) 알고리즘에서는
지니계수(Gini Index)를 썼습니다.
지니계수란 이탈리아 통계학자이자 경제학자인 코라도 지니 Corrado Gini가 만든 불평등지수로서
같은 모집단에서 무작위로 선택된 두 항목들이 같은 집합에 있을 확률을 나타냅니다.
가장 분류가 잘 안될 경우는 50:50으로 분류된 경우가 됩니다.
이 CART 알고리즘이 발전하여 선풍적인 인기를 가져온 것이
Random Forest (2001) 입니다.
이 알고리즘은 레오 브라이먼과 그의 제자 아델 커틀러 Adele Cutler가 만들었습니다.
랜덤 포레스트는 성능측면으로도 매우 뛰어나 활용이 많이 되고 있는 알고리즘입니다.
또 Sample Data를 조정하여 정확성을 더욱 높인
Boosting 알고리즘이 등장합니다.(1997)
이 알고리즘은 AdaBoost (Adaptive Boosting)이라고 하며,
요하브 프룬드 Yoav Freund와 로버트 사파이어 Robert Schapire가 만들었습니다.
최근에는 여러 개의 의사결정트리를 조합하여 사용하는
앙상블 Ensemble 알고리즘으로 XGBoost (eXtreme Gradient Boosting)가 인기입니다.
앙상블이란 프랑스어로 각 부분의 총체로서 전체적 효과를 나타내는 것을 의미하는 부사입니다.
인공지능에서는 Bagging과 Boosting을 조합하여
하나의 결정 트리보다 더 좋은 성능을 내는 머신러닝 기법을 말합니다.
이 XGBoost는 중국의 진천기 陳天奇 Tiangi Chen이 만들었습니다.
이 의사결정트리 알고리즘의 기원을 따라가보니
결국 '인공지능'이라는 용어를 처음 세상에 내놓은 1956년 Dartmouth AI Project까지 올라가네요.
마빈 민스키 Marvin Minsky나 존 메카시 John McCathy로부터 시작된 기호주의가
현재까지 맹활약을 하고 있다고 봐야겠습니다.
