분류(Classification) – 의사결정 나무(Decision Tree)

지난 글에서 다룬 kNN, Rocchio, Naive Bayes는 분류(Classification) 중에서도 게으른 모델(lazy model)에 해당한다. 오늘 다룰 의사결정나무(Decision Tree)는 분류 중에서도 열정적 모델(eager model)에 해당한다.

■ 게으른 모델(Lazy Model)과 열정적 모델(Eager Model)의 차이점

먼저 게으른 모델과 열정적 모델에 대해 알아보자.

게으른 모델은 훈련 데이터(training data)를 단순히 저장(학습은 이때 일어나지 않음)한 뒤, 테스트 데이터가 들어올 때 비로소 분류를 시작한다. 만약 새로운 테스트 데이터가 들어온다면 다시 전체 훈련 데이터를 훑어야 분류가 가능하다. 즉, 분류 단계에서 계산이 더 비싸다는 것을 알 수 있다. kNN의 경우, 매번 k번째 이웃을 다시 찾아야 한다.

열정적 모델은 훈련 데이터를 받을 때 학습이 일어난다. 따라서 테스트 데이터가 들어오면 그 즉시 분류가 가능하다. 즉, 열정적 모델은 게으른 모델에 비해 학습에는 더 오랜 시간이 걸리나 분류 자체에 걸리는 시간은 더 적다.

■ 의사결정 나무(Decision Tree)

의사결정 나무는 어떤 기준에 의해 훈련 데이터를 ‘나무’ 구조로 나눠가는 모델을 말한다.

위 이미지는 사람이 짜증나는 조건을 각각 배고픔, 졸림, 더움의 여부로 분류해놓은 훈련 데이터를 의사결정 나무로 구현한 것이다. 회색 도형은 나누는 기준을, 주황색 도형은 최종적으로 내려진 의사결정(decision)을 뜻한다.

만약 위의 모델에 테스터 데이터 배고픔 = N, 졸림 = Y, 더움 = 5°C 가 들어온다면 어떻게 될까? 가장 위부터 그대로 넣으면 된다. 첫 번째 기준인 배고픔에서는 N 가지를 타고 내려와 두 번째 기준인 졸림에서 Y 가지를 타고 그대로 ‘짜증남’으로 분류가 된다. 즉, 우리는 여기서 모델이 무엇을 예측하는지 뿐만 아니라 왜 그렇게 예측하는지도 쉽게 알 수 있다.

위 이미지를 보면, 동일한 데이터를 어떤 규칙과 순서로 나누는지에 따라 결과가 달라짐을 보여준다. 즉, 동일한 데이터여도 나무 모형은 여러개가 나올 수 있다.

■ 헌트 알고리즘 (Hunt’s Algorithm)

당연히 우리의 관심사는 최적의 의사결정나무를 찾는 방법이다. 여러 가지 알고리즘이 있는데 이 글에서는 헌트 알고리즘을 소개하려 한다. (다른 알고리즘으로는 ID3, CHAID, C4.5 등이 있다.)

헌트 알고리즘은 먼저 속성(Feature)를 하나 랜덤하게 고른다. 만약 해당 속성의 클래스(위의 예시에서 짜증남의 여부)가 같다면 그대로 해당 클래스를 잎노드로 가져온다. 만약 해당 속성의 레이블이 1개 이상의 클래스를 갖는다면, 다른 속성을 가져와 분리한다. 이 과정을 끝까지 반복해나간다.

위의 예시로 헌트 알고리즘을 적용한다면, 일단 졸림이란 속성을 하나 고른 뒤 짜증 여부를 확인한다. 졸림이 Y일 때 모든 상태가 ‘짜증’이므로 Y의 잎노드로 ‘짜증’을 가져온다. 이 상태에서 졸림이 N일 때 짜증의 클래스는 Y, N 섞여 있다. 따라서 다른 속성인 더움을 가져와 또 한 번 짜증의 여부를 비교해나간다. 이런식으로 끝까지 나무를 그리면 된다.

■ 명목형/순서형 속성일 때 구분법

그렇다면, 속성은 어떻게 고르는 것이 좋을까? 속성의 타입이 명목형(nominal)인지, 순서형(ordinal)인지, 연속형(continuous)인지에 따라 그 방법이 달라진다.

먼저 명목형/순서형 속성일 땐 이분법(binary split)과 다분법(multi-way split)이 있다. 위의 예시는 Yes, No라는 카테고리를 이용해 이분법으로 가지를 나누었다.

예를 들어 훈련 데이터에 티셔츠의 사이즈: 스몰, 미디움, 라지가 있다고 하자. 3개의 레이블은 순서형 속성이다. 이분법으로 나누려면 {스몰, 미디움}, {라지} 또는 {스몰}, {미디움, 라지} 로 나눌 수 있다. 이 때 중요한 것은 순서를 유지해야한다는 것이다. 즉, 크기 순서를 무시하고 {스몰, 라지}, {미디움}으로 분리하지 않는다.

다분법은 고유값마다 나누는 방식을 말한다. 티셔츠의 사이즈라면, 각각의 레이블인 스몰, 미디움, 라지로 3개로 가지를 나누는 방식을 다분법이라고 한다. 보통 이분법을 이용한다.

■ 연속형 속성일 때 구분법

연속형 속성일 때 역시 이분법과 다분법이 그대로 적용된다. 위의 예시에서 더움은 숫자로 이뤄진 연속형 속성인데, 25°C 이상/이하라는 기준을 이용해 이분했다. 만약 다분법을 적용한다면 구간을 좀 더 나누어서 <18°C, [18°C, 24°C), [24°C, 28°C), [28°C, 32°C), >32°C 로 나눌 수 있겠다.

이 때 구분하는 것을 비닝(binning) 또는 이산화(discretization) 한다고 말한다. 비닝은 위의 예시처럼 각 기준이 동일한 구간(equal-interval)을 갖게끔 할 수도 있고, 해당 구간에 속하는 데이터의 빈도가 같도록(equal-frequency)하거나 자유롭게 설정(user-defined boundaries)할 수 있다.

연속형일 때 역시 보통 이분법을 사용한다. 모든 가능한 구분 기준을 고려해서 가장 적절한 기준을 찾는 것이 우리의 관심사이다. 이를 계산하는 것은 때때로 계산이 비싸질 수 있는데 어떤 것이 최적의 구분인지 찾는 방법은 다음 글에서 좀 더 자세히 알아보도록 하자.