의사결정나무 (Decision Tree) (1/3)

의사결정나무는 분류(Classification) 기법 중에 한 종류이다. 전체적인 분류의 흐름이 나무 구조(Tree Structure)와 유사하여 의사결정나무라고 불리운다. 

* 트리 구조란 노드(node)와 가지(branch)로 구성된 형태를 의미한다.

 

쉽게 설명하면, 스무 고개와 유사한 형태의 분류 방법이라고 할 수 있다.

스무 고개의 단계를 보면 아래와 같다.

1. 정답을 맞히기 위해 적당한 속성 하나를 선택한다.

2. 속성과 기준을 정해 해당하는지를 물어본다.

3. 2번 결과에 따라서 후보를 줄인다.

4. 위 과정을 반복한다.

5. 더 이상 물어볼 내용이 없거나, 정답을 알 것 같으면 게임을 종료한다.

 

아래는 의사결정나무의 예시이다.

그림. 의사결정나무 예시

의사결정나무의 노드는 속성과 속성에 대한 기준들을 가지고 있다. 위 예시에서 첫 번째 노드의 속성은 "색"이고, 속성에 대한 기준은 "흰색/검은색"이다. 가지는 노드의 속성 기준에 대한 결과를 포함한다. 위 예시를 보면, 속성에 대한 결과가 표시되어 있음을 볼 수 있다. 마지막 노드(leaf node)는 분류하고자 하는 클래스(Class)를 나타낸다. 위의 예시는 동물이라는 클래스를 구분하는 의사결정나무이다.

 

	색	크기	다리의 개수	식성	클래스
데이터 1	흰	작다	4	초식	토끼
데이터 2	흰	크다	4	육식	북극곰
...	...	...	...	...	...

의사결정나무는 위와 같이 데이터가 주어지면, 아래와 같은 단계를 거쳐서 생성된다.

1. 클래스를 가장 잘 분류할 수 있는 속성 하나를 선택한다.

2. 속성에 대한 기준을 결정한다.

3. 속성의 기준에 따라서 데이터를 분류한다.

4. 위의 과정을 반복한다.

5. 더 이상 데이터를 구분할 방법이 없으면 생성을 종료한다.

 

1번과 2번 과정은 속성 선택 알고리즘을 통해 계산된다.

4번은 재귀 함수 형태로 구현되고, 5번은 종료 조건이다.

 

종료 조건은 다음과 같다.

• 더 이상 사용할 속성이 없는 경우(속성은 재사용하지 않기 때문에 노드를 생성할수록 줄어든다)
• 이미 분류가 끝난 경우
  - 분류된 데이터 셋이 하나의 클래스만 갖는 경우
  - 분류된 데이터 셋이 없는 경우

 

 

자세한 알고리즘은 다음 페이지에 작성 예정!!!