1. 개요[편집]
| 결정 트리 Decision Tree | |
|---|---|
| 대표 알고리즘 | CART (Breiman 외 1984) · ID3/C4.5 (Quinlan) |
| 분할 형태 | 축평행 (axis-parallel), $x_j \le c$ |
| 탐색 전략 | 탐욕적 재귀 이분할 — 전역 최적 아님 |
| 불순도 | 지니 · 엔트로피 · (회귀) 분산 |
| 가지치기 | 비용복잡도 $R_\alpha(T)=R(T)+\alpha|\tilde T|$ |
| 결측값 | 대리 분할 (CART) · 분수 인스턴스 (C4.5) |
| 치명적 약점 | 분산이 크다 — 데이터 몇 개에 트리가 통째로 바뀐다 |
결정 트리(decision tree)는 특징 공간을 축에 평행한 초직육면체들로 재귀적으로 쪼갠 뒤, 각 조각(잎)에 상수 하나를 얹어 예측하는 조각별 상수 모형이다. 뿌리에서 “이 변수가 이 값보다 큰가”를 묻고, 답에 따라 왼쪽·오른쪽으로 내려가다 잎에 도착하면 그 잎의 다수결 클래스(분류) 또는 평균(회귀)을 뱉는다. 그게 전부다.
모형 자체가 이렇게 단순한데도 결정 트리가 통계 학습의 중심에 있는 이유는 두 가지다. 첫째, 전처리를 거의 요구하지 않는다 — 스케일링·정규화가 필요 없고, 단조 변환에 완전히 불변하며, 범주형과 결측값을 알고리즘 안에서 직접 처리한다. 둘째, 분산이 매우 커서 앙상블의 재료로 최적이다. 이 두 번째 성질이 랜덤 포레스트와 그래디언트 부스팅을 낳았고, 20년이 지난 지금도 정형 데이터에서 최강자 자리를 지키는 두 방법의 밑바닥에는 전부 이 조각별 상수 트리가 깔려 있다. 단독으로는 거의 안 쓰이지만 아무도 대체하지 못한 부품이라는 것이 결정 트리의 정확한 위치다.
계보는 크게 둘이다. 브레이만·프리드먼·올셴·스톤의 CART(Classification and Regression Trees, 1984)는 통계학 쪽에서 이진 분할 + 비용복잡도 가지치기로 정리했고, 퀸란의 ID3 → C4.5 → C5.0 은 기계학습 쪽에서 정보이득과 다분기 분할로 접근했다. 오늘날 살아남아 실제로 돌아가는 것은 사실상 CART 계열이다.
2. 탐욕적 재귀 이분할[편집]
노드 에 도달한 훈련 표본 집합을 라 하자. CART는 후보 분할 — 즉 ” 인가” — 전부에 대해 불순도 감소량
를 계산하고 이를 최대화하는 를 고른 뒤, 두 자식에서 같은 짓을 재귀적으로 반복한다. 정지 조건(잎 최소 표본 수, 최대 깊이, 불순도 감소 하한)에 걸릴 때까지 키운다.
연속 특징에서 후보 분할점은 관측된 값들 사이의 중점뿐이므로 실질적으로 개다. 특징별로 한 번 정렬해 두고 분할점을 왼쪽에서 오른쪽으로 옮기며 누적 통계량을 갱신하면 노드당 , 트리가 균형 잡히면 전체가 정도로 끝난다. 히스토그램 이진화로 후보를 개쯤으로 줄이면 하나가 날아가는데, 이 아이디어가 그래디언트 부스팅 구현들의 속도 비결이다.
여기서 반드시 못 박아야 할 것: 이 절차는 탐욕적이며, 얻어지는 트리는 전역 최적이 아니다. 주어진 잎 개수에서 오차를 최소화하는 트리를 찾는 문제는 NP-난해이고, 뿌리에서 당장 불순도를 가장 많이 줄이는 분할이 두 단계 뒤에 최악의 선택으로 판명나는 예는 얼마든지 만들 수 있다. XOR 구조가 교과서적 사례다 — 어느 축으로 잘라도 1단계 불순도 감소가 정확히 0이라 탐욕 알고리즘은 뿌리에서 멈추지만, 2단계만 내려가면 완벽히 분리된다.1
3. 불순도 척도[편집]
분류에서 노드 의 클래스 비율을 라 할 때 표준 후보는 셋이다.
| 척도 | 정의 | 성질 |
|---|---|---|
| 오분류율 | 조각별 선형 — 분할해도 감소가 0이 되는 경우가 있다 | |
| 지니 불순도 | 엄밀 오목, CART 기본값 | |
| 엔트로피 | 엄밀 오목, ID3/C4.5 계열 |
핵심은 엄밀 오목성이다. 오분류율은 조각별 선형이라, 두 자식의 다수결 클래스가 부모와 같으면 아무리 순도가 개선돼도 감소량이 정확히 0으로 나온다. 예컨대 (400, 400) 노드를 (300, 100)/(100, 300)으로 가르나 (200, 400)/(200, 0)으로 가르나 오분류율 기준 감소는 둘 다 로 같지만, 후자는 자식 하나가 완전히 순수해졌다. 지니와 엔트로피는 이 차이를 잡아내므로 트리를 키울 때는 이 둘 중 하나를, 다 키운 뒤 가지치기에서 최종 성능을 잴 때는 오분류율을 쓴다. CART가 성장과 가지치기에서 서로 다른 척도를 쓰는 이유가 이것이다.
지니와 엔트로피의 실질적 차이는 거의 없다. 이진 분류에서 에 대해 그려 보면 두 곡선이 에서 최대이고 모양도 거의 겹친다 — 지니는 엔트로피의 2차 근사에 가깝다. 어느 쪽을 고르느냐로 결과가 달라졌다면 그건 척도 탓이 아니라 데이터가 부족한 탓이다.
회귀 트리에서는 불순도를 그냥 노드 내 분산(또는 제곱오차합)으로 둔다.
잎에 상수 를 얹는 것이 제곱오차 최적이라는 것은 자명하고, 그래서 회귀 트리는 계단 함수를 적합한다. 손실을 절대오차로 바꾸면 잎 상수는 중앙값이 되고 이상치에 강건해지지만, 누적 통계량으로 분할점을 훑는 트릭이 안 먹혀 계산이 훨씬 비싸진다.
4. 정보이득은 왜 분할을 편향시키는가[편집]
퀸란의 ID3는 엔트로피 감소량, 즉 정보이득을 그대로 분할 기준으로 썼다. 그런데 이게 취할 수 있는 값이 많은 특징 쪽으로 체계적으로 기운다. 극단적인 예 — 데이터에 “고객 ID” 열이 있으면 그 열로 다분기 분할했을 때 모든 잎이 표본 하나짜리가 되어 엔트로피가 0, 즉 정보이득이 이론상 최댓값이 된다. 예측력은 정확히 0인데도.
원인은 둘로 나눠 보는 게 정확하다.
- 다분기 분할 자체의 문제. 자식 수가 많아지면 각 자식의 표본이 적어지고, 표본이 적으면 우연히 순수해진다. ID3처럼 범주 하나당 가지 하나를 뽑는 설계에서는 이게 바로 치명상이 된다. 퀸란의 대응이 C4.5의 이득비(gain ratio) 로, 정보이득을 분할 자체의 엔트로피 로 나눈다. 분모가 자식 수와 함께 커지니 벌점이 걸린다. 다만 분모가 아주 작을 때 이득비가 폭발하는 새로운 병이 생겨서, 실무 구현은 “평균 이상의 정보이득을 가진 후보 중에서만 이득비를 비교”하는 식의 임시방편을 얹는다.
- 후보 분할점 개수의 문제 — 이쪽이 더 근본적이다. CART처럼 이진 분할만 해도 편향은 남는다. 연속 변수는 후보 분할점이 개, 이진 범주형은 1개이므로, 완전히 무의미한 연속 잡음 변수가 진짜 신호를 가진 이진 변수를 이길 확률이 상당히 높다. 후보를 많이 시험할수록 그중 최대값이 우연히 커지는 것 — 다중비교 문제의 교과서적 발현이다. 범주 개짜리 명목형은 이진 분할 후보가 개나 되니 더 심하다.
이 두 번째 편향은 트리의 특징 중요도를 통째로 오염시킨다. 뿌리 근처에 올라온 변수가 “중요해서” 올라온 것인지 “후보가 많아서” 올라온 것인지 구분이 안 되기 때문인데, 이 문제는 랜덤 포레스트의 불순도 감소 기반 중요도로 그대로 상속된다. 근본적인 해법은 분할 변수 선택과 분할점 선택을 분리하는 것이다. 호톤·호닉·차일라이스(2006)의 조건부 추론 트리(ctree)는 각 변수와 반응의 독립성을 순열검정으로 먼저 검정해 -값이 가장 작은 변수를 고르고, 그 다음에야 분할점을 찾는다. 검정 통계량이 후보 개수에 대해 이미 보정돼 있으므로 변수 선택이 편향되지 않고, 다중검정 보정된 -값이 유의수준을 넘으면 그 자리에서 성장을 멈추므로 가지치기가 필요 없다는 부수적 이득도 있다.
5. 축평행이라는 제약[편집]
분할이 항상 형태이므로 결정 경계는 축에 평행한 면들의 조합뿐이다. 참 경계가 같은 비스듬한 직선이면 트리는 그걸 계단으로 근사하는 수밖에 없고, 계단을 촘촘하게 만들려면 깊이를 계속 늘려야 한다. 결과는 잎마다 표본 몇 개씩 남는 과적합된 트리로, 표현하려던 것은 고작 직선 하나다.
같은 이유로 트리는 가법 구조에 약하다. 같은 순수 선형 함수는 인간 눈에 가장 단순한 모형이지만 조각별 상수로는 지독하게 비효율적이다. 반대로 상호작용, 즉 ” 이 크고 동시에 가 작을 때만 반응이 튄다” 같은 구조는 트리가 자연스럽게 잡는다. 트리와 선형 모형은 잘하는 것이 정확히 반대라고 외워 두면 대체로 맞다.
비스듬한 경계를 직접 다루려는 시도가 없었던 건 아니다. CART 원논문의 선형결합 분할(CART-LC), 머티·카시프·잘츠버그의 OC1(1994) 같은 사각 트리(oblique tree)는 형태의 분할을 쓴다. 표현력은 확실히 좋아지지만 대가가 크다 — 최적 초평면 탐색이 조합 문제라 국소탐색·무작위화에 의존해야 하고, 단조 변환 불변성이 깨지므로 스케일링이 다시 필요해지며, 무엇보다 “이 변수가 이 값보다 크면”이라는 트리의 유일한 미덕이 사라진다. 결국 실무는 사각 트리 대신 축평행 트리를 잔뜩 앙상블하는 쪽을 택했다. 계단을 매끄럽게 만드는 데는 트리 하나를 똑똑하게 만드는 것보다 멍청한 트리 500개를 평균 내는 게 싸게 먹혔기 때문이다.
6. 비용복잡도 가지치기[편집]
트리를 정지 조건으로 적당히 멈춰 세우는 것(pre-pruning)은 위험하다. 앞서 본 XOR처럼 당장의 이득이 0이지만 한 단계 더 가면 큰 이득이 있는 분할을 놓치기 때문이다. CART의 처방은 정반대다 — 일단 과하게 키운 뒤 잘라 낸다.
큰 트리 의 부분트리 에 대해 복잡도 벌점을 붙인 위험을
로 정의한다. 는 재대입 오차(오분류율 또는 SSE), 는 잎 개수, 은 잎 하나의 가격이다. 이면 가, 가 아주 크면 뿌리만 남은 트리가 최적이다.
여기서 CART가 증명한 것이 이 문제의 실질적 내용이다. 를 0에서 무한대로 연속적으로 올릴 때 최적 부분트리는 유한 개의 값에서만 바뀌고, 그렇게 나오는 트리들은 서로 중첩된 사슬을 이룬다.
그리고 다음 트리를 얻는 방법이 가장 약한 고리 자르기(weakest-link pruning)다. 내부 노드 와 그것을 뿌리로 하는 부분트리 에 대해
를 계산한다. 분자는 ” 를 통째로 잎 하나로 접었을 때 늘어나는 오차”, 분모는 “그때 줄어드는 잎 개수”이므로, 는 그 가지가 잎 하나당 벌어들이는 오차 감소다. 이게 가장 작은 노드가 가성비 최악이니 먼저 접는다. 그 시점의 가 곧 다음 임계값 이다.
경로 전체가 번의 접기로 계산되므로, 남은 일은 경로 위의 개 후보 중 하나를 고르는 것뿐이다. 여기에 교차검증을 쓴다 — 다만 폴드마다 트리 구조가 다르니 트리 자체를 비교할 수 없고, 를 공통 눈금으로 삼아 각 폴드에서 로 가지치기한 트리의 검증오차를 평균 낸다. 최종 선택은 최소 CV 오차를 주는 가 아니라 최소값에서 표준오차 하나 이내인 가장 단순한 트리를 고르는 것(1-SE 규칙)이 CART의 권장이다. CV 오차 곡선이 최소 부근에서 평평하기 때문에, 통계적으로 구분되지 않는 것들 중에서는 작은 쪽을 택하겠다는 태도다.2
7. 범주형과 결측값[편집]
범주형. 범주가 개인 명목형 변수를 이진 분할하려면 부분집합 개를 다 봐야 하는데, 이면 50만 개다. 다행히 우회로가 있다. 이진 분류(지니 기준) 또는 제곱오차 회귀에서는, 범주를 클래스 1의 비율(또는 반응 평균) 순으로 정렬한 뒤 인접한 개 절단만 검사해도 전역 최적 분할이 나온다. 회귀 쪽은 피셔(1958), 분류 쪽은 CART 원저의 정리다. 지수적인 탐색이 정렬 한 번으로 붕괴하는 꽤 아름다운 결과인데 — 클래스가 3개 이상이면 성립하지 않는다. 다중 클래스에서는 근사 휴리스틱을 쓰거나 원-핫으로 풀어야 한다.
그리고 이 트릭에는 대가가 있다. 절단이 개뿐이라도 정렬 순서 자체가 반응변수를 보고 정해진 것이라, 고카디널리티 범주형은 여전히 과적합의 온상이다. 앞 절의 후보 개수 편향이 여기서 가장 흉하게 나타난다.
결측값. CART의 답은 대리 분할(surrogate split)이다. 노드 에서 최적 분할 를 찾은 뒤, 다른 변수들로 만든 분할 가운데 의 좌우 배정을 가장 잘 흉내 내는 것들을 예측 연관도 순으로 줄 세워 저장해 둔다. 예측 시점에 의 변수가 결측이면 1순위 대리 분할을 쓰고, 그것도 결측이면 2순위로 내려가고, 전부 결측이면 다수 방향으로 보낸다. 학습 시에도 같은 방식으로 결측 표본을 자식에 배정한다.
경쟁 방식은 셋 더 있다.
- C4.5의 분수 인스턴스. 결측 표본을 자식들의 크기 비율로 쪼개서 동시에 양쪽으로 보낸다. 예측도 가중 평균으로 나온다. 개념은 깔끔하나 표본 수가 정수가 아니게 되어 구현이 지저분해진다.
- 결측을 하나의 범주로. 결측 자체에 정보가 있을 때(설문 무응답, 미측정 센서) 오히려 가장 정직하고, 실제로 강력하다.
- MIA(missing incorporated in attribute). 분할할 때 “결측은 왼쪽” / “결측은 오른쪽” 두 가지를 후보 분할의 일부로 놓고 학습으로 정한다. XGBoost의 기본 방향(default direction) 학습이 정확히 이것이고, 오늘날 그래디언트 부스팅 구현의 사실상 표준이다. 대리 분할보다 싸고 대체로 더 잘 맞는다 — 결측 패턴이 반응과 관련 있으면(MNAR) 대리 분할은 그 정보를 버리지만 MIA는 쓴다.
대리 분할이 밀려난 이유는 성능만이 아니다. 대리 분할은 저장 비용이 분할당 여러 개라 앙상블 수백 그루로 곱해지면 부담이고, 무엇보다 뒤에 나올 해석가능성 이야기를 조용히 망가뜨린다.
8. 해석가능성이라는 흔한 과대선전[편집]
“결정 트리는 화이트박스라서 설명 가능하다”는 문장은 결정 트리를 소개하는 거의 모든 글의 두 번째 문단에 있다. 절반은 맞고 절반은 마케팅이다. 정직하게 나눠 보자.
맞는 부분. 깊이 3~4, 잎 10개 미만의 작은 트리는 실제로 종이에 그려 사람에게 보여 줄 수 있고, 각 예측에 대해 “왜”에 해당하는 규칙 경로가 존재한다. 이건 선형 모형의 계수보다도 직관적인 경우가 많다. 임상 의사결정 규칙이나 심사 기준처럼 사람이 손으로 따라 실행해야 하는 곳에서 트리가 여전히 쓰이는 이유다.
틀린 부분, 넷.
- 실전에서 쓸 만한 트리는 작지 않다. 성능이 나오는 트리는 잎이 수십~수백 개다. 잎이 200개인 트리를 “해석 가능”하다고 부르는 것은, 200줄짜리 중첩 if문을 읽으면 프로그램을 이해한 것이라고 말하는 것과 같다.
- 불안정성이 설명을 무효화한다. 트리는 분산이 크다. 데이터의 몇 퍼센트만 바꿔도 뿌리 분할 변수가 바뀌고, 그 아래 구조 전체가 딸려 바뀐다. 그런데 뿌리 분할은 사람들이 “가장 중요한 변수”로 읽는 자리다. 부트스트랩 재표본 10개로 트리를 10그루 키워 뿌리를 비교해 보면 이 주장의 신뢰도가 어느 정도인지 즉시 알 수 있다 — 대개 서로 다른 변수 서너 개가 나온다. 재현되지 않는 설명은 설명이 아니다.
- 상관된 특징이 이야기를 왜곡한다. 거의 같은 정보를 가진 변수 A, B 중 A가 아슬아슬하게 이겨 분할에 쓰이면, 트리는 “A가 중요하고 B는 무관하다”고 말하는 것처럼 보인다. 실제로는 둘 다 똑같이 중요하거나 둘 다 인과적으로 무관할 수 있다. 트리는 인과를 말하지 않는다. 축평행 분할의 임계값 를 물리적 문턱값으로 읽는 것도 같은 종류의 착각인데, 는 관측된 값들 사이 아무 데나 놓을 수 있어 표본에 따라 흔들린다.
- 대리 분할이 경로를 거짓말로 만든다. 화면에 표시된 규칙 경로는 1순위 분할 기준이지만, 결측이 있는 표본은 실제로 다른 변수를 보고 내려갔다. 보이는 설명과 실행된 계산이 다르다.
여기에 하나 더 얹으면 — 탐욕적으로 키운 트리는 같은 크기에서 최적도 아니다. 잎 개수를 고정하고 오차를 최소화하는 트리를 정수계획법·분기한정·동적계획법으로 실제로 푸는 최적 결정 트리 솔버들(DL8.5, MurTree, GOSDT 등)이 2020년 전후로 실용 단계에 들어섰고, 같은 정확도를 훨씬 작은 트리로 달성한다는 결과가 여럿 나왔다. 루딘(2019)의 논지는 이 지점을 정확히 찌른다 — “복잡한 블랙박스를 사후에 설명하기”보다 “애초에 해석 가능한 모형을 제대로 최적화하기”가 낫다는 것이며, 여기서 “해석 가능한 모형”은 CART가 대충 키운 트리가 아니라 최적화된 희소 트리를 뜻한다. 사후 설명 도구(설명 가능한 인공지능 쪽의 SHAP·LIME 등)를 트리 앙상블에 붙이는 관행이 널리 퍼져 있지만, 그건 이미 해석가능성을 포기하고 다시 사는 행위다.
요약하면 이렇다. 결정 트리의 진짜 강점은 해석가능성이 아니라 전처리 불요·상호작용 자동 포착·계산 효율이다. 해석가능성은 트리를 아주 작게 유지할 때만 진짜이고, 아주 작게 유지하면 성능을 포기해야 하며, 성능을 원해서 앙상블로 가는 순간 해석가능성은 어차피 증발한다. 그리고 대부분의 사람은 성능을 원한다.3
9. 분산이 크다는 것, 그래서 앙상블[편집]
결정 트리의 오차를 편향-분산 분해로 보면 진단이 명확하다. 깊게 키운 트리는 편향이 작고 분산이 크다. 재귀 분할은 데이터가 요구하는 만큼 얼마든지 복잡한 경계를 만들 수 있으니 편향은 작고, 각 분할이 앞선 분할의 결과에 조건부로 정해지므로 위쪽에서 생긴 작은 흔들림이 아래로 증폭되며 내려간다 — 계층적 구조가 곧 분산 증폭기다.
여기서 두 갈래 길이 갈린다.
- 분산을 직접 때린다. 트리를 깊게 키운 채로 여러 그루의 평균을 낸다. 개별 트리의 낮은 편향은 그대로 두고 분산만 깎는 전략이며, 이게 배깅과 랜덤 포레스트다.
- 편향을 때린다. 트리를 아주 얕게(깊이 1~6) 제한해 편향이 큰 약한 학습기로 만든 뒤, 잔차를 보며 순차적으로 쌓아 편향을 줄인다. AdaBoost와 그래디언트 부스팅이다.
같은 부품으로 정반대 방향의 문제를 푸는 두 계열이 결정 트리 하나에서 갈라져 나왔다는 것이, 이 모형이 앙상블 시대까지 살아남은 이유의 전부다.
10. 관련 문서[편집]
- 랜덤 포레스트 · 그래디언트 부스팅 · AdaBoost
- 편향-분산 분해 · 교차검증 · 부트스트랩
- 과적합 · 로지스틱 회귀 · 설명 가능한 인공지능
- 행동 트리 · 몬테카를로 트리 탐색
- 대리 모델 · 능형회귀 · 라쏘
11. Footnotes[편집]
-
그래서 CART는 “일찍 멈추지 말고 크게 키운 뒤 잘라라”를 택했다. 탐욕 알고리즘의 근시안을 알고리즘으로 고치는 대신 일단 다 해 보고 나중에 후회하는 방식으로 우회한 것인데, 인생과 달리 트리에서는 이게 실제로 통한다. ↩
-
1-SE 규칙은 통계학자가 “차이가 유의하지 않으면 단순한 걸 고른다”는 오컴의 면도날을 실무 규칙으로 박아 넣은 것이다. 참고로 이걸 지키면 대회 리더보드에서는 대체로 진다. 그럼에도 CART 원저가 이 규칙을 밀어붙인 것은, 그 책이 겨냥한 독자가 리더보드가 아니라 임상시험 보고서를 쓰는 사람들이었기 때문이다. ↩
-
“우리 모델은 결정 트리라 설명 가능합니다”라는 발표 슬라이드 다음 장에 잎이 300개인 트리 그림이 A4 한 장으로 압축돼 들어가 있는 광경은 이 바닥의 국룰에 가깝다. 아무도 확대해서 읽지 않고, 발표자도 읽어 본 적 없으며, 그 그림의 실제 기능은 “우리는 블랙박스가 아니다”라는 분위기의 전달이다. ↩