[머신러닝 분류] Decision Tree / 의사결정트리
머신러닝을 접해본 사람들이라면 아마 한번쯤은 들어본 적이 있을거라고 생각되는 Decision Tree 알고리즘에 대해 다뤄보고자 한다.
학교수업을 통해서 여러번 배워본 적이 있지만, 항상 지나고 나면 잊어버리기 때문에(...)
이번 보아즈 분석 세션과 멘토멘티 스터디를 통해 배운 내용들을 토대로 기록을 남겨보고자 한다.
우선 DecisionTree는 머신러닝 알고리즘이므로 머신러닝의 큰 틀에서부터 시작해보자.
먼저, '머신러닝'을 사람이 감독하는가 그렇지 않은가로 나누어 보자.
이때 사람이 감독하는 학습을 지도학습, 사람이 감독하지 않는 학습을 비지도 학습이라고 한다.
우리는 이러한 두가지 학습 중 지도학습에 대해 살펴볼것이다.
지도학습은 알고리즘에 주입하는 훈련데이터에 레이블이라고 하는 원하는 답이 포함된 것이다.
그리고 이렇게 지도학습은 다음과 같이 다시 분류와 회귀로 나누어진다.
분류란, 전형적인 지도학습으로 예측하고 싶은 종속변수가 범주형일 때 class를 예측하는 것이다.
대표적으로 스팸을 거르는 모델을 떠올리면 이해하기 쉽다.
(수신한 메일이 스팸인지, 스팸이 아닌지를 class로 분류하는 모델이다.)
다음으로 회귀란, 예측변수라고 부르는 특성(feature)들을 활용해서 연속형인 종속변수를 예측하게 되는데 이때 분류와 달리 그 클래스에 속하게 될 확률을 수치화해서 표현해준다. 예를 들어, 우리가 중고차 가격을 예측하고 싶을 때 주행거리, 연식, 브랜드와 같은
feature들이 예측변수가 되고 이것들을 이용해서 중고차 가격을 예측하게 된다.
이 중에서 의사결정트리는 분류에 속하고 있다.
분류에서 가장 각광받는 방법인 앙상블 분류 방법은 두가지로 나눌 수 있는데,
Bagging과 Boosting으로 나눌 수 있다.
Bagging의 대표적인 예로 랜덤포레스트가 있으며, Boosting에는 Gradient boosting, Xgboost, LightGBM 과 같은 것들이 있다.
이때 앙상블은 서로 다른 또는 같은 알고리즘을 결합하는 것이다.
다시말해 매우 많은 여러개의 약한 학습기를 결합해서 확률적인 보완을 수행하고
오류가 발생하는 부분에 대한 가중치를 update 해나가며 예측 성능을 높이는 것이다.
이때 바로 오늘 살펴볼 의사결정트리가 아주 좋은 '약한 학습기'가 된다.
그 이유를 간단히 먼저 살펴보면, 의사결정트리는 데이터의 scailing이나 정규화 등의
사전 가공 영향을 받지 않는다는 장점이 있는 대신, 과적합이 발생한다는 단점이 있는 약한 학습기이기 때문에,
이 단점이 앙상블에서는 장점으로 작용한다. (과적합에 대해서는 뒤에서 다룬다)
그렇다면 이러한 의사결정트리의 특징들을 추가적으로 더 살펴보자.
의사결정트리의 가장 큰 특징 3가지를 다음과 같이 정리할 수 있다.
먼저 위의 분류, 회귀 그림을 살펴보면 괄호안의 예시에 모두 TREE가 있는 것을 확인할 수 있듯이
DecisionTree는 분류와 회귀 문제에 모두 사용할 수 있다.
(분류에는 DecisionTreeClassifier, 회귀에는 DecisionTreeRegressor이라는 이름으로 사용한다_)
또한 의사결정트리는 뒤에서 살펴보겠지만 어떤 질문을 던지고, 그 질문에 맞는지 틀리는지에 따라 가지를 뻗쳐가며 대상을 좁혀간다.
(마치 스무고개 놀이를 한다고 생각하면 이해하기 쉽다.)
마지막으로 DecisionTree는 RandomForest의 기본 구성요소이다.
(구체적으로는 randomforest 정리에서 다루도록 할 것이다.)
도대체 Decision Tree가 무엇이길래 이러한 특징들을 가지고 있는 것일까?
본격적으로 이 친구가 어떻게 생겨먹은 친구인지를 함께 살펴보자.
일단 나무를 보기 전에 숲을 보라는 말이 있듯이,, 전체적인 의사결정나무의 모델개요를 나타낸 그림을 들고왔다.
(위와 같이 크게 데이터, 알고리즘, 모델 이렇게 3가지로 나누어진 그림이다.)
즉, 의사결정트리는 여러개의 input data와 하나의 output data가 필요하며,
데이터가 균일해지도록 분할하는 알고리즘을 통해 모델을 형성하게 된다는 것이다.
하지만.. 이렇게 말하면 조금 감이 안오기 때문에, 간단한 iris dataset을 통해서 이해해보자.
sklearn에 내장되어있는 iris 데이터를 앞의 5개 행만 불러온 것이다.
따라서 왼쪽의 초록색 박스가 총 5개의 input data들이며 각각의 데이터들은 4가지의 feature를 가지고 있는 것을 확인할 수 있다.
이렇게 decision tree는 여러개의 input data와 빨간색 박스안의 target이라고 되어있는 output데이터를 이용해서 데이터를 2개 혹은 그 이상으로 분할하는 알고리즘을 통해 나무의 형태를 만들어간다.
이 때, 분류의 경우에는 비슷한 범주를 가지고 있는 관측치끼리 균일해지도록, 회귀는 비슷한 수치를 가지고 있는 관측치끼리 균일해지도록 데이터를 분할한다.
그럼 위와 같은 방법으로 주어진 데이터에 분할을 수행한 최종 모델의 모습을 살펴보자.
위의 iris data를 이용해서 max depth를 2로 설정한 후 수행한 decision tree의 모습이다.
(max depth란 트리의 깊이를 말하며, 수행 코드의 parameter들에 대해서는 마지막에 살펴보도록 하자.)
보는 것과 같이 실제 모델이 나무처럼 가지를 뻗어가며 형성되고 있는 것을 확인할 수 있다.
그렇다면, 위에서 가지를 어떤 기준으로 뻗어나갈지 그 기준을 어떻게 정하는 것일까?
예를 들어, 첫번째 박스(제일 위의 박스)를 살펴보면 x[2]<=2.45(꽃잎 길이<=2.45)라는 조건을 만족하면 즉 주어진 조건에 참이면
왼쪽 화살표를 따라서 내려와서 setosa라는 종이 된다. 하지만 주어진 조건에 거짓이면 오른쪽 노드로 내려와 다시 새로운 조건에 맞춰 분할이 되는 것을 볼 수 있다.
여기서 x[2]<=2.45, 와 같은 조건들을 어떻게 판단하는 것일지,
의사결정나무의 형성과정에 대해서 살펴보자.
의사결정나무이 어떻게 형성될지를 결정하는 4가지의 단계가 있다.
바로 분리규칙, 정지규칙, 가지치기, 예측값 할당이다.
이중에서 먼저 위에서 살펴본 위의 노드에서 아래의 노드로 나누어주는 x[2]<=2.45와 같은 기준이 어떻게 생기는 것인지를 결정해주는 분리규칙에 대해서 살펴볼 것이다.
이때 등장하는 것이 바로 CART 훈련 알고리즘(Classification and regression tree)이다.
이 CART 알고리즘은 의사결정나무를 분리하기 위해서 사용되는 알고리즘이다.
이 알고리즘의 기본원리는 다음과 같다.(계속 iris dataset을 예시로 들어 설명하겠다)
'훈련세트를 하나의 특성 K(iris에서 꽃잎의 길이와 같은 특성)의
임곗값 tk( 위에서 2.45와 같은 기준값)를 사용해서 서브셋으로 나누기'
이때 이 식을 수식으로 표현해보면 다음과 같다.
여기서 m은 전체샘플 수를 나타내며, m left는 왼쪽 서브셋의 샘플수, m right는 오른쪽 서브셋의 샘플수를 나타낸다.
또한 G는 불순도를 나타내며, G left는 왼쪽 서브셋의 불순도, G right는 오른쪽 서브셋의 불순도를 나타낸다.
여기서 새로운 개념인 ' 불순도'가 등장한다.
순도/ 불순도의 개념을 살펴보기 위해서 아래 두개의 데이터 셋을 살펴보자.
먼저 위의 박스를 살펴보면 총 8개의 데이터 중 빨간색이 7개, 파란색이 1개이다.
즉 이런 경우 순도가 높다고 표현하며, 다른 말로 불순도가 낮다고 표현한다,
하지만 옆에 불순도와 순도 이외에 지니계수라는 단어가 등장한다.
이 지니계수는 바로 불순도를 측정하는 지표이다,
0에 가까울수록 순도가 높고, 높아질수록 불순도가 높다는 의미를 가지고 있다.
즉 하나의 범주에 한 종류의 데이터만 있으면 불순도가 최소, 순도가 최대, 또는 지니계수가 0에 가깝다고 할 수 있는 것이다.
하지만 그 아래의 박스에는 총 8개 중 파란색이 5개, 빨간색이 3개로 다른 종류의 데이터가 거의 반반이 존재한다.
따라서 불순도가 높고, 순도가 낮으며 지니계수가 높다고 볼 수 있다.
만약 하나의 범주안에 다른 종류의 데이터가 '정확히 반반' 있다면
불순도는 최대가 되고 순도가 최소가 되는 것이다.
이렇게 불순도와 순도의 개념을 이용해 의사결정트리는 지니계수가 0에 가까워지도록,
즉 불순도를 최소화하는 방향으로 학습을 진행하게 된다.
그런데 이렇게 불순도를 측정하는 지표는 지니계수만 있는 것은 아니고, 다른 것들도 존재한다.
이번에 살펴볼 것은 엔트로피라는 개념이다.
엔트로피를 살펴보기 이전에 먼저 정보이론이라는 것에 대해 가볍게 알아야한다.
정보이론이란, 데이터를 정량화하기 위한 응용수학의 분야 중 하나로,
정보이론에서 말하는 정보량은 불확실성의 정도를 의미한다.
즉 정보량이 높다는 것은 어떤 일이 일어날 확률이 낮다는 것이고, 따라서 불확실하다는 것을 의미한다.
다시말해, 정보량이 높다는 상황은 어떤 답을 알기위해서 질문을 더 많이 해야한다는 것을 의미하는데,
다시 생각해보면 이것은 그 답이 나올 확률이 낮다, 즉 불확실하다는 것을 의미한다고 이해하면 편하다.
이때 정보량이 높은 문장이 맞을수록 해당 정보의 중요도가 높아지는데,
예를들어 올 여름의 평균기온이 영하 10도로 예상됩니다. 라는 뉴스를 보았다고 하자.
이것은 매우 불확실한 정보이기 때문에 정보량이 높다고 할 수 있는데, 이 정보가 맞을 수록
그 문제는 중요한 정보가 된다는 것이다.
지금까지 정보량의 개념을 살펴보았는데,
엔트로피란 바로 이 '정보량의 평균'을 나타낸다.
즉 불확실성을 측정해주는 척도가 되는것이다.
이 수식이 바로 m개의 레코드가 속하는 A 영역에 대한 엔트로피의 수식이다.
이때 Pk는 A영역에 속하는 레코드 가운데 k에 속하는 레코드의 비율을 나타낸다.
특히, 머신러닝에서는 엔트로피가 불순도의 측정방법으로 자주 사용이 되기 때문에
식을 외울필요는 없지만 어떤 것을 의미하는지 그 개념을 잘 알아두면 좋다.
이제는 이 의사결정트리를 언제 정지시킬 것인가를 결정하는 규칙인 정지규칙에 대해 살펴보자.
먼저 이것이 의사결정트리에서 더이상 분리가 일어나지 않는 기준 3가지이다.
1,2 번은 지금까지 의사결정트리의 구조를 이해했다면 직관적으로 이해할 수 있을 것이다.
그렇다면 3번, 규제 매개변수 즉 parameter들에 어떤 것들이 있는지 알아보자.
먼저 규제 매개변수란 오버피팅 즉 과적합을 방지하기 위해서 제약을 걸어주는 것을 말한다.
처음에 잠깐 언급했듯이 의사결정트리는 과적합의 위험이 아주 큰 모델이다.
따라서 사용자가 규제 매개변수를 적절히 이용해주는 것이 중요하다.
바로 이것들이 의사결정트리의 규제 매개변수들이다.
그럼 이 매개변수를 이용하면 어떻게 과적합을 막을 수 있는지
한눈에 알기 위해 시각화를 해보았다.
이 데이터는 사이킷런의 make_classification을 이용해 피처는 2개, 클래스는 3가지 유형의 분류 샘플 데이터 생성한 후
그래프의 형태로 2개의 피처를 2차원 자표에 시각화하고 각 클래스 값을 다른 색으로 표시한 것이다.
먼저 이 데이터를 아무런 규제 매개변수를 사용하지 않고 DecisionTreeClassifier()를 이용해 분류한 뒤
Classifier의 Decision Boundary를 시각화 하는 함수를 이용해보았다.
위의 그림을 보면 일부 이상치 데이터까지 완벽하게 분류하기 위해 분할이 자주 일어나, 결정 기준경계가 매우 많아진 것을 볼 수 있다.
즉 오버피팅, 과적합이 일어난 것을 확인할 수 있다.
그렇다면 이번에는 min_samples_leaf=6 (6개 이하의 데이터는 리프노드를 생성할 수 있다)이라는 제약을 준 뒤
결정경계를 시각화해보았다.
이렇게 보는 것과 같이 이상치 하나하나에 크게 반응하지 않으면서 좀 더 일반화된 분류 규칙을 찾아낸 것을 확인할 수 있다.
위의 오버피팅 된 모델 처럼 학습데이터에만 지나치게 최적화된 분류 기준은 오히려 테스트 데이터 세트에서
정확도를 떨어뜨릴 수 있기 때문에, 적절하게 매개변수를 잘 설정해주는 것은 매우 중요하다는 것을
눈으로 확인해 볼 수 있었다.
다음으로 살펴보 것은 의사결정트리의 부적절한 마디를 잘라내 모양을 단순화하는 '가지치기'이다.
방금 위에서 살펴보았듯이
depth가 깊어질수록 (즉 나무가 복잡해질수록) 오버피팅의 위험성이 매우 높다.
따라서 이럴때 불필요한 마디를 제거하는 과정이 바로 가지치기이다.
이때 주의해야할 것은 가지치기가 데이터를 버리는 것이 아닌 합치는 merge개념이라는 것이다.
마지막으로 살펴볼 것은 예측값 할당이다.
의사결정트리는 분류와 회귀 모두에 이용가능하기 때문에
분류의 경우에는 class를 , 회귀의 경우에는 특정 값을 예측하게 된다.
tree를 생성한 후에는 cross validation과 같은 평가 지표를 통해 모델을 평가하고,
최종적으로 예측하고자하는 새로운 데이터를 트리 모델에 대입해 결과를 예측하게 된다.
최종적으로 지금까지 살펴본 의사결정트리의 장점과 단점을 정리한 표이다.
의사결정트리가 어떻게 분류를 해나가는지 그 과정을 제대로 이해했다면
트리의 장점과 단점 또한 이해하기 어렵진 않을 것이다.