Classification: Decision Tree

Classification: Decision Tree

Classification은 미리 정의된 카테고리들 안으로 어떤 하나의 object를 어사인하는 작업을 말한다.

이것은 많은 응용들이 가지는 문제에 적용 되어 질 수 있다.

예를 들면, spam 찾기, 세포의 malignant 구분, galaxy의 종류 구분 등에 적용 할 수 있다.

이러한 것들은 supervised learning의 한 종류이며,

가장 간단한 형태인 Decision Tree에 대해서 다루도록 하겠다.

Hunt's Algorithm

---

해당 알고리즘을 이해하기 위해서 채무 불이행 (Defaulted Borrower)문제를 풀어 보도록 하자.

D_t는 node t와 연관된 training record들의 set이라고 하자.

y = {y1, y2, ... yc}는 class label들 이라고 하자.

위와 같은 조건하에서 아래와 같이 Algorithm을 정의 한다.

Step1: 

D_t에 있는 모든 레코드가 같은 class y_t륵 가진다면, t는 어떤 leaf node가 되고 y_t로써 labeling 되어 진다.

Attribute test를 또 할필요도 없이 impurity가 0이므로, 즉 100%인 것이다. 논란의 여지 없이 leaf node를 y_t로 만들면 된다.

Step2: 

    만약 D_t가 empty set이라면, t에서의 leaf node는 default class y_d로 라벨 되어 진다.

y_d는 전체에서 다수의 test set을 가지는 것을 말한다.

Step3:

D_t에 있는 레코들이 두개 이상의 y_t 클래스를 가진다면, attribute test를 사용해서 data를 더 작은 subset들로 분할 한다.

이 작업을 나눠진 각각의 subset에대가 반복 한다.

핵심은 이 attribute test로 적절한 condition을 찾는 것이다.

위의 이전 데이터를 가지고 아래의 Decision Tree를 생성하는 과정을 보여 준다.

(a)를 보면 채부 불이행(Defaulted)가 No이다. 이러한 의미는 모든 사용자가 대출이 가능하다는 것을 뜻한다.

(b)와 같이, Home Owner를 Root로 해서 더 작은 Subset으로 나눠지는 형태의 트리를 구성 한다.

이렇게 어떤 Root 노드를 선택할 것인지에 대한 Attribute test에 관한 이야기는 나중에 다룬다. 일단 저렇게 했다고 생각하자. 

단지, HomeOwner는 spliting을 하기 위환 best criterion이라고 생각하자.

Hunt's Algorithm은 이제 다시, 각각의 child node들의 root에 똑같은 방법을 다시 적용하게 된다 (recursively).

(c)에서 HomeOnwer =yes 인 사람들은 모두 Defaulted = No 이므로 더이상 분할 하지 않는다.

하지만 오른쪽의 경우 즉 HomeOwner=No인 경우를 보면, 

총 7개의 Training Data중에서 

3개의 Defaulted = Yes

4개의 Defaulted = No 로 구성 되어 진다.

따라서 단일 class로 구성 될 때 까지 계속 분할 해야 한다.

이러한 작업을 반복하면 (d)와 같은 모습을 나타내게 된다.

Measures for Selecting the Best Split

---

가장 최적의 split way를 찾는 문제는 많이들 연구를 해왔다. 이중 몇가지를 소개 하겠다.

p(i|t)라는 것을 t 노드에서의 i class의 비율이라고 생각하자.

C0에 대해서 10개의 레코드가 있고,

C1에 대해서 10개의 레코드가 있다고 하면

P(C0,C1)은 P(0.5, 0.5)가 된다. 동일한 수의 레코드가 각각의 class에 대해서 존재하기 때문이다.

하지만, 이것을 하나의 Attribute를 기준으로 Split하게 된다면 아래와 같은 Tree 형태로 나타내어 진다.

이떄 과연 우리는 무엇이 더 좋은 구조라고 말 할 수 있는가.

이것을 measure 하기 위해서 impurity라는 개념을 도입 한다.

impurity란 class의 분포가 skewed (편향됨) 한 정도를 나타낸다.

즉, impurity가 높다는 것은 평향되지 않다는 것을 의미한다.

P(0,1)이 zero impurity를 가지며, P(0.5, 0.5)가 가장 높은 impurity를 가진다.

Gain이 클려면 결국, M12, M34와 같은 Impurity가 낮아야한다.

그리고 M12, M34를 구하기 위해서는 weighted average를 이용해서 구하게 된다.

결국 impurity가 높다는것은 error가 높다는 것을 의미한다, 편향됨의 정도가 높아야 prediction 했을 떄의 error가 적게 된다.

이러한 impurity를 measure는 지표는 아래와 같다.

위 식에서 c는 number of classes가 된다.

위식과 weighted average를 이용해서 각각을 split node를 찾기위한 수식은 아래와 같다.

주어진 Node t에서의 GIni Index는 아래와 같다.

P(j|t)는 t의 노드에서 j 클래스의 빈도를 나타낸다.

최대의 경우 n_c가 클래스의 총 숫자를 나타내는데, 모든 래코드가 모든 클래스에 대해서 분포를 가진다면, 그 때 GINI indext가 가장 큰 값을 나타낸다. 즉, 10개의 클래스가 존재하는데 해당 노드 t에서 포함되는 모든 레코들이 10개의 클래스에 대해서 모두 분포를 가지고 있다며, 이때 가장 impurity가 높게 되는 것이다. 이러한 때를, least interesting information 이라 한다.

최소의 경우, 모든 record가 단 하나의 클래스만을 가지고 있을 때이다. 이때는 0이되며, most interesting information 이라고 한다.

어떤 노드 p에서 k partitions (children)으로 split 할때 split의 quality를 다음의 수식으로 계산 한다.

n_i / n은 weighted average를 구하기 위한 수식 이다.

주어진 노드 t에 대해서 Entropy 계산은 아래와 같다.

위 식의 의미를 살펴 보면,

의 식이 계속 확률에다가 곱해지는 형태가 된다. 즉 확률이 크면 클수록 로그값이 작아진다,

따라서 확률이 높은 것들은 확률을 낮춰주고, 확률이 낮은것들은 확률을 높여주게 된다.

이것을 이용해서 사용되어지는 평균 비트수를 줄일 수 있다고 한다.

허프만 코드 적용에 유용하게 사용 할 수 있다.

Information Gain

Parent Node p is split into k partitions

n_i is number of records in partition i

node t에서 Classification error를 이용하는 방법.

계산 방법 예제

Binary Classification Problem에 대해서 3개의 measures를 기하학 적으로 표현 하면 아래와 같다.

x축은 p의 확률 이며,

y축은 impurity 이다.

Gini의 경우에 살펴보면,

C0: P

C1: 1-P

Gini Index의 정의에 따르면 Impurity 수식은

의사결정트리 분석의 장점

결정트리를 통한 데이터 분석의 결과는 나무(Tree) 구조로 표현되기 때문에 분석가가 결과를 쉽게 이해하고 설명할 수 있는 장점이 있다. 

분류율에 대한 정확도만 따지자면 신경망(Neural Network) 또는 로지스틱 회귀분석 등의 분류 방법들 보다 낮게 평가되기도 하지만 결과를 쉽게 이해하고 설명할 수 있으며 의사결정을 하는데 직접적으로 사용할 수 있는 장점이 있기 때문에 데이터마이닝 적용시 매우 많이 사용되고 있다. 

의사결정트리 분석의 한계

일반적인 결정트리 알고리즘은 갖는 한계, 단점을 아래에 나열하였다. 

[1] 데이터의 특성이 특정 변수에 수직/수평적으로 구분되지 못할 때 분류율이 떨어지고, 트리가 복잡해지는 문제가 발생한다. 신경망 등의 알고리즘이 여러 변수를 동시에 고려하지만 결정트리는 한 개의 변수만을 선택하기 때문에 발생하는 당연한 문제이다. 

[2] 결정트리는 Hill Climbing 방식 및 Greedy 방식을 사용하고 있다. 일반적인 Greedy 방식의 알고리즘이 그렇듯이 이 방식은 최적의 해를 보장하지는 못한다. 

[3] 약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다. 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이 후의 트리 구성이 크게 달라질 수 있다.