Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.44 No.2 pp.15-23
DOI : https://doi.org/10.11627/jkise.2021.44.2.015

Interpretability Comparison of Popular Decision Tree Algorithms

Jung-Sik Hong^*†

, Geun-Seong Hwang^**

^*Dept. of Industrial Engineering, Seoul National University of Science and Technology
^**Dept. of Data Science, Graduate School, Seoul National University of Science and Technology

^†Corresponding Author : hong@seoultech.ac.kr

Received 23/02/2021 Finally Revised 31/03/2021 Accepted 09/04/2021

Abstract

Most of the open-source decision tree algorithms are based on three splitting criteria (Entropy, Gini Index, and Gain Ratio). Therefore, the advantages and disadvantages of these three popular algorithms need to be studied more thoroughly. Comparisons of the three algorithms were mainly performed with respect to the predictive performance. In this work, we conducted a comparative experiment on the splitting criteria of three decision trees, focusing on their interpretability. Depth, homogeneity, coverage, lift, and stability were used as indicators for measuring interpretability. To measure the stability of decision trees, we present a measure of the stability of the root node and the stability of the dominating rules based on a measure of the similarity of trees. Based on 10 data collected from UCI and Kaggle, we compare the interpretability of DT (Decision Tree) algorithms based on three splitting criteria. The results show that the GR (Gain Ratio) branch-based DT algorithm performs well in terms of lift and homogeneity, while the GINI (Gini Index) and ENT (Entropy) branch-based DT algorithms performs well in terms of coverage. With respect to stability, considering both the similarity of the dominating rule or the similarity of the root node, the DT algorithm according to the ENT splitting criterion shows the best results.

Key Words : Interpretability Comparison , Stability Measure , Decision Tree

대표적인 의사결정나무 알고리즘의 해석력 비교

홍 정식^*†, 황 근성^**

^*서울과학기술대학교 산업공학과
^**서울과학기술대학교 일반대학원 데이터사이언스학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

의사결정나무 알고리즘(Decision Tree algorithm, 이하 DT 알고리즘)은 분류 알고리즘중 가장 대표적인 알고리 즘이며 지난 수십년간 성능 측면의 개선을 다룬 많은 논문 들이 제시되었고[7, 9, 14, 16, 23, 28, 29], 이중 다수의 논 문들은 새로운 분기기준을 제시한 논문이다[9, 14, 16, 28, 29]. 그러나 R이나 Python 기반의 오픈 소스 프로그램들은 여전히 세 개의 분기 기준(엔트로피, 지니지수, 게인 비율) 을 토대로 한 알고리즘이 대부분이다. 따라서 가장 널리 활용되는 이 3가지 분기기준을 토대로 한 DT 알고리즘에 대해서는 장점과 단점이 충분히 연구될 필요가 있다.

그런데 이 3가지 알고리즘의 비교는 주로 정확도 측면 에서 이루어졌다[4, 26, 30]. 해석력 측면에서의 이들 알 고리즘에 대한 비교는 제대로 수행되지 못하였다. 해석 력은 실제로 매우 다양한 현실 문제에서 머신러닝 모델 이 사용될 때 매우 중요한 요소이다[2, 24, 27]. 가령, 대 출 과정이 편향되지 않음을 고객에게 보이기 위해서, 설 명 가능한 대출 규칙이 필요하고[2], 의료 분야에서도 환 자에게 설명을 해야 할 필요성이 있으며[24], 이외에도 다양한 비즈니스에서 고객 유지 등을 위해 고객 이탈 현상 을 설명해주는 머신러닝 모델을 필요로 한다[27]. 따라서, 머신러닝 모델에서 해석력은, 매우 중요한 이슈로 부상하 고 있으며, DT 알고리즘을 포함하여 머신 러닝 알고리즘 에 대한 해석력을 분석하는 연구는 최근에야 집중적으로 이루어지고 있다[11, 13, 17, 18]. 머신 러닝 모델의 해석 력은 설명력과 이해 가능성들의 용어와 혼용되기 시작하 며 다양한 연구가 수행되었다. 이러한 용어들의 혼용성을 지적하며, 머신 러닝 모델에서의 해석력 문제를 비교적 포괄적으로 다룬 논문이 최근 1~2년 사이에 제시되고 있 다[3, 22].

머신 러닝 모델의 해석력에 대한 체계적인 연구를 바탕 으로 본 논문은 DT 알고리즘의 해석력을 다루고자 한다. DT 알고리즘의 해석력에 대한 논문은 두 가지 부분으로 나누어 볼 수 있다. 하나는 DT 알고리즘의 해석력을 다른 분류 알고리즘의 해석력과 비교하는 논문이다[8]. 다른 하 나는 해석력을 높인 새로운 DT 알고리즘을 제시하고 기존 의 DT 알고리즘과 해석력을 비교하는 것이다[17]. 본 논문 은 DT 알고리즘의 해석력에 한정하고 있으므로 후자에 좀 더 가까운 연구이다. 그런데 후자에 속하는 연구의 한계점 은 해석력의 중요한 척도중 하나인 안정성이 제외되어 있 다는 점이며, 또한 새로 제시된 알고리즘에 초점이 맞추어 져 있어서 기존의 대표적인 DT 알고리즘의 해석력 비교가 제대로 수행되지 못하였다는 것이다. 특히 안정성은 정확 도 측면에서도 다루어지고 해석력 측면에서도 다루어지는 척도로, DT 알고리즘의 경우 독자적으로 다루어지는 경우 가 대부분이다[6, 19]. 본 논문은 안정성 척도를 해석력과 연관되는 다른 척도들과 함께 다루고자 한다. 또한, 해석 력 측면에서의 DT 알고리즘의 안정성 척도를 기존의 척도 를 변형하여 새로운 방식으로 제안하고자 한다. 변형된 안 정성 척도와 함께 DT 알고리즘의 해석력을 다루는 다른 척도들(DT의 깊이, 리프 노드의 동질성과 커버리지)을 종 합하여 기존의 가장 대표적인 3가지 DT 알고리즘의 해석 력을 비교하고 분석하는 작업을 수행하여, 해석력 차원에 서 3가지 DT 알고리즘의 장점과 단점을 제시하는 것이 본 논문의 독자적인 기여라고 할 수 있다.

본 논문은 다음과 같이 구성된다. 제 2장에서는 본 연구 와 관련된 연구 배경이 다루어진다. 구체적으로는 연구의 자족성을 위해 3가지 DT 알고리즘의 분기 기준이 간단히 소개되고, 머신 러닝 알고리즘의 해석력이 기술된다. 그리 고 DT 알고리즘의 해석력에 대한 척도들과 연구들이 소개 된다. 3절에서는 DT 알고리즘의 안정성 척도를 해석력 차 원에서 고찰하고 기존 척도를 변형한 척도가 기술된다. 4 절에서는 UCI 데이터와 kaggle 데이터를 바탕으로 작성된 10가지 데이터를 대상으로 3가지 DT 알고리즘의 해석력 을 비교하고 분석하는 작업이 수행된다. 마지막으로 5절 에서는 해석력 관점에서 3가지 대표적인 DT 알고리즘의 장점과 단점이 기술된다.

2. 연구배경

2.1 대표적인 DT 알고리즘의 분기기준

R이나 Python 기반의 오픈 소스 프로그램들은 세 개의 분기 기준(엔트로피, 지니지수, 게인 비율)을 토대로 한 알 고리즘이 대부분이다. 이들 분기 기준은 다음과 같다.

2.1.1 지니지수

G (S) = 1 - \sum_{k = 1}^{m} p_{k}

(1)

Δ G = G (S) - (\frac{| S_{l} |}{| S |} G (S_{l}) + \frac{| S_{r} |}{| S |} G (S_{r}))

(2)

여기서, S는 데이터의 집합을 의미한다. 이 집합의 원소 는 설명변수 $(x_{1}, \dots, x_{n})$ 와 목표변수 y로 이루어져 있다. 목 표변수 y의 범주 개수는 n이며, p_k는 데이터 중 목표변수 범주가 k인 데이터의 비율이다. G(S)는 데이터 S의 지니 지수이다. |S|는 집합 S의 크기이고, S_l과 S_r은 S를 분기 기준에 따라 둘로 나눌 때, 각각 왼쪽 노드의 데이터 집합 과 오른쪽 노드의 데이터 집합을 의미한다.

2.1.2 엔트로피

E (S) = - \sum_{k = 1}^{m} p_{k} {log}_{2} (p_{k})

(3)

Δ E = E (S) - (\frac{| S_{l} |}{| S |} E (S_{l}) + \frac{| S_{r} |}{| S |} E (S_{r}))

(4)

여기서, E (S)는 데이터 집합 S의 엔트로피를 의미한다.

2.1.3 게인 비

N (S) = - (\frac{| S_{l} |}{| S |} l o g_{2} \frac{| S_{l} |}{| S |} + \frac{| S_{r} |}{| S |} l o g_{2} \frac{| S_{r} |}{| S |})

(5)

Δ G R = \frac{Δ E}{N (S)}

(6)

여기서, N (S)는 데이터 집합 S의 정규화 인자를 의미 한다.

하나의 노드가 자식 노드로 분기될 때, 분기기준은 위 의 3가지중 하나를 사용하여 부모 노드와 자식 노드간의 동질성 이득이 최대가 되는 변수와 임계치에 의해 정해 진다. 가령 지니 지수를 예로 들면,

Δ G (S) = G (S) - \frac{| S_{l} |}{| S |} G (S_{l}) - \frac{| S_{r} |}{| S |} G (S_{r})

(7)

\underset{x_{i} \in C_{i, j}}{M A X} Δ G (S) = G (S)

(8)

여기서, x_i는 i번째 설명변수이며, C_i,j는 S을 S_l과 S_r을 나누는 j번째 영역을 의미한다.

2.2 머신러닝 알고리즘의 해석력

머신러닝 알고리즘의 해석력은 지난 10년간 부분적으 로 개별 척도를 제시하는 연구가 수행되어 오다가 최근 종합적인 차원에서 머신러닝의 해석력을 다루는 프레임 워크를 제시하는 연구들이 이루어졌다. 이중 대표적인 연 구로는 Murdoch et al.[22]의 연구와 Belle and Papantonis [3]의 연구가 있다. Murdoch et al.[22]은 머신 러닝 알고 리즘의 해석력에 있어 예측적 정확도까지 포함하여 PDR (Predictive Descriptive Relevant) 프레임워크를 제시하고 해석력을 모델 기반 해석력과 모델 정립이후 해석력으로 나누어 설명하고 있다. 이를 도시하면 다음과 같다.

Belle and Papantonis[3]는 해석력 용어 대신 ‘설명가능 한’(Explainable)이라는 용어를 사용하여 설명가능한 머 신 러닝의 원칙과 실행 사례를 제시하고 있다. Belle and Papantonis[3]은 설명가능한 머신러닝 모델의 중요 특성 으로, 정합성, 강건성, 개선성, 편향, 호환성 그리고 인간 이해가능성을 제시하고 있다.

이상의 6가지 핵심척도는 다양한 머신러닝 모델의 해 석력이나 설명력을 평가하는 데에 사용된다. 가령, 신경 망 기반의 모델과 같은 블랙 박스 모델은 인간 이해가능 성이 매우 낮은 모델이라고 할 수 있다.

2.3 DT 알고리즘의 해석력

DT 알고리즘은 해석력이 뛰어난 분류 알고리즘이다 [20, 21]. 그러나 해석력이 뛰어난 분류 알고리즘은 DT 알고리즘 외에도 규칙 유도 알고리즘이나 로지스틱 회귀 모델 등이 있다. 따라서 이러한 여러 분류 알고리즘의 해 석력을 비교하는 연구가 수행되고 있다[12]. 또한, DT 알 고리즘의 나무 깊이나 전체 리프 노드의 개수 등에 따라 인간의 이해가능성이 어떻게 영향을 받는지를 연구한 논문도 최근에 등장하고 있다[21]. 한편 DT 알고리즘을 해석력 측면에서 개선시키고자 하는 연구도 최근 이루 어지고 있다[11, 13, 17]. Kotsiantis[17]에서는 기존의 DT 알고리즘이 해석력 측면에서는 기본적인 두 가지 문제점 이 있음을 보이고있다. 첫째, DT 알고리즘의 분기기준이 분기 후 양쪽 노드의 동질성을 기계적으로 가중합하여 부모 노드와 자식 노드간 동질성 감소량을 최대로 하는 것은 어느 한쪽 노드에 동질적인 데이터들이 몰려 있는 것을 조기에 탐지하지 못할 가능성이 매우 크다는 것이 다. 이를 해결하기위해, Kotsiantis[17]은 한쪽 노드만을 최대화하는 분기기준을 제시하고 이러한 분기기준에 기 반한 알고리즘이 DT의 해석력을 높일 수 있음을 입증하 였다. 둘째, DT 알고리즘의 뿌리 노드의 분기기준은 이 후 모든 리프 노드의 규칙에 모두 조건으로 들어가게 된 다. 이는 해석력 측면에서 문제가 된다. 즉, 모든 규칙에 하나의 변수가 들어가는 것은 모든 규칙의 독립성이 성 립할 여지가 전혀 없는 것이다. 목표변수의 클래스를 정 하는 데에 있어 독립적인 규칙이 존재할 수 있는 다수의 사례에 비추어 볼 때, 이는 개선해야 할 문제임을 알 수 있다. 또한 뿌리 노드의 분기기준은 모든 규칙에 포함되 므로 이의 안정성은 특히 문제가 된다. 제 3장에서 DT 알고리즘의 안정성 문제를 다룰 때 이러한 사항이 고려 될 것이다.

3. DT 알고리즘의 해석력 평가척도

3.1 기존의 평가 척도

DT 알고리즘의 해석력은 DT 알고리즘에서 유도되는 규칙의 품질에 좌우된다. 규칙의 품질은 DT 알고리즘외 에도 규칙 유도 알고리즘이나 연관규칙등에서 모두 거론 되는 주제이다.

규칙의 품질을 평가할 때는 규칙의 정확도까지 포함 하므로 제시된 척도가 매우 다양하다[1].

그런데 해석력을 고려할 때 가장 기본적인 평가척도 는 규칙의 커버리지와 동질성이다. An and Cercone[1]에 서는 이 두 가지 척도의 가중합으로 규칙의 품질을 평가 한다. 또한 DT 알고리즘의 경우는 해석력을 평가할 때 DT의 깊이가 중요한 평가요소가 된다[20]. 따라서 해석 력 관점에서 DT 알고리즘을 평가하는 가장 기본적인 평 가척도는 커버리지, 동질성 그리고 DT의 깊이이다. 그런 데 동질성은 목표변수가 불균형 집합인 경우는 한계가 있으므로 동질성을 목표변수의 비율로 나눈 리프트를 추 가하는 것이 바람직하다. 마지막으로 머신 러닝 알고리 즘의 해석력을 평가할 때, 사용되는 안정성 척도를 추가 하고자 한다. 이 경우 DT 알고리즘의 해석력을 평가하는 요소는 다음 5가지 요소가 된다.

(1) 커버리지 : 하나의 리프 노드에 속하는 데이터의 비율
(2) 동질성 : 하나의 리프 노드에 속하는 데이터 중 목표 변수의 최빈 클래스에 속하는 데이터의 비율
(3) 리프트 : 동질성을 최빈 클래스의 사전 비율로 나눈 값
(4) DT의 깊이 : 루트 노드에서 리프 노드에 이르는 경 로의 길이의 최대값
(5) 안정성 : 훈련 데이터의 변화에 따른 DT의 변화정도

예를 들어, 하나의 리프 노드에 데이터가 100개 있고, 이 중 목표변수가 1인 데이터가 90개, 목표변수가 0인 데이터가 10개 있다고 하자. 데이터 전체는 1000개이며 목표변수가 1인 비율은 30%라고 하자. 이 경우, 이 리프 노드의 커버리지는 10%이고, 동질성은 90%이며, 리프트 는 0.9/0.3이므로 3이다.

위의 5가지 평가 척도를 2.2절의 머신러닝 모델의 해 석력을 평가하는 6개 척도와 관련하여 설명하면 다음과 같다.

첫째, 정합성(correctness)은 정확도(accuracy)를 포함한, 보다 폭넓은 개념이다. DT에서 도출된 규칙이 적절한 의 미를 갖고 신뢰할만한가를 뜻하는 척도이다. 따라서 커 버리지와 동질성이 이 척도와 연관이 있다고 할 수 있다. 규칙이 커버하는 비율이 너무 작으면 규칙으로써의 적절 한 의미를 잃고, 또한 동질성이 어느 정도 확보되어야 규 칙의 적절성이 확보되기 때문이다. 둘째, 강건성은 안정 성과 연관되는 개념이다. 강건하다는 것은 입력 요소의 작은 변화에도 규칙이 변화하지 않는다는 것을 의미하는 데, 훈련데이터가 변해도 DT 변화가 적은 것을 안정성이 높다고 할 때, 이는 바로 강건성이 높다는 것을 의미하기 때문이다. 셋째, 개선성이나 편향 그리고 호환성은 DT 전체에 해당되는 척도이고 분기 기준에 따라 그 정도가 달라지는 척도가 아니다. 따라서 3개의 DT 알고리즘의 해석력을 비교하는 데에 사용될 척도는 아니라고 할 수 있다. 마지막으로 인간 이해가능성은 DT의 깊이에 해당 한다고 할 수 있다. DT의 깊이가 낮은 곳에서 생성되는 리프 노드일수록 규칙의 조건의 개수가 줄어들고 이는 인간 이해가능성을 높이기 때문이다.

5가지 평가척도중 안정성을 제외한 4가지 평가척도의 계산은 간단하다. 리프 노드 k에 속하는 데이터의 집합을 S_k라 하면, 커버리지는 $\frac{| S_{k} |}{| S |}$ 가 된다. 리프 노드 k에 속하 는 데이터 중 y = 1의 비율과 y = 0의 비율 중 높은 값이 동질성이다. 리프트나 DT의 깊이는 정의에 따라 간단히 계산된다.

안정성은 다른 4개의 척도처럼 간단하게 계산되지 않 는다. 본 논문은 해석적 관점에서 안정성을 평가하는 척 도를 새로이 제시하고자 한다.

3.2 해석력 관점에서 DT 알고리즘의 안정성

DT 알고리즘의 안정성 문제는 해석력 차원보다 정확 도 차원에서 먼저 연구되기 시작했다[5]. 이 연구를 바탕 으로 최근까지 DT 알고리즘의 안정성 연구는 주로 정확 도 차원에서 안정성을 평가하고 이를 개선하는 알고리즘 을 제시하고 있다. 해석력 차원에서 안정성을 다룬 논문 은 Jacobucci[15]가 있다. 이 논문은 DT의 유사성을 평가 하는 Briand의 논문[6]을 바탕으로 안정성을 다음과 같이 정의한다.

S T (D T_{1}, \dots, D T_{N}) = 1 - \frac{q}{N}

(9)

여기서,

∙DT_i는 i번째 부스팅된 훈련 데이터로 생성된 DT
∙ $S T (D T_{1}, \dots, D T_{N})$ 는 총 N번 부스팅된 훈련 데이터로 계산된 DT의 안정성
∙q는 N개의 DT 중 서로 다른 형태의 DT의 개수

식 (9)는 분기 기준이 되는 변수뿐 아니라 분기되는 변수의 값이 다를 경우는 다른 패턴의 DT로 규정하므로 수치형 변수가 많을 경우에는 안정성이 매우 낮게 나오 게 되는 단점을 가지고 있다. 따라서 수치형 변수가 분기 기준으로 사용될 경우, 분기하는 임계값만 다른 경우는 그 임계값간의 차이를 반영하는 방식으로 두 개의 분기 노드의 유사성이 정해져야 한다. 본 논문은 Jacobucci[15] 의 DT간 유사도를 바탕으로 두 가지 방식으로 DT간 유 사도를 정의하고자 한다.

첫째, 해석력 관점에서 DT 알고리즘의 핵심적인 결과 는 규칙들의 집합이다. 이 중에서도 커버리지가 가장 높 은 규칙이 가장 의미가 있는 규칙이므로 이를 지배적인 규칙이라 정의하고, 이들간의 유사도로 DT 알고리즘의 안정성을 평가하고자 한다. 두 개의 규칙간의 유사도는 한 개의 분기기준간의 유사도를 바탕으로 정의된다. 하 나의 분기기준이 X_i 라고 하자. X_i 가 범주형일 경우는 두 개의 DT에서 발생한 두 분기기준이 임계치 범주가 같으 면 유사도는 1이고 그렇지 않으면 0이다. X_i 가 수치형인 경우, 두 개의 DT에서 발생한 두 분기기준의 임계치가 각각 δ₁과 δ₂라고 하면, 분기기준 x_i의 유사도는 다음과 같이 정의된다.

S T (X_{i}) = 1 - \frac{| δ_{1} - δ_{2} |}{r a n g e (X_{1})}

(10)

여기서, ST (X_i)는 두 분기기준 X_i의 유사도이며, range (X_i)는 X_i 가 취하는 값의 범위이다. 이제 두 개의 DT에서 발생한 두 지배규칙 R_p,q의 유사도는 다음과 같이 정의된다. 지배규칙을 이루는 분기 기준 변수들의 집합을 D_p,q라 하자.

S T (R_{p, q}) = S T (\underset{i \in D p, q}{II X_{i}}) = \underset{i \in D p, q}{II} S T (X_{i})

(11)

여기서, 두 지배규칙을 이루는 분기기준 변수가 하나라 도 다르면, 유사도는 0으로 정의된다.

식 (10)의 ST (X_i)와 식 (11)의 ST (R_p,q) 를 예를 통해서 계산 과정을 간략히 보이기로 한다. <Figure 2>에 두 개의 DT가 나와 있다.

DT₁과 DT₂의 지배 규칙은 두 DT 모두 리프노드 ① 에 대응한다고 하자. DT₁과 DT₂ 의 지배 규칙의 유사도 를 측정하기 위해 먼저 ST (X₁)과 ST (X₅)를 구해보자. X₁의 범위는 10이며 X₅의 범위는 20이다. 이 경우,

\begin{array}{l} S T (X_{1}) = 1 - \frac{| 3 - 5 |}{10} = 0.8 \\ S T (X_{5}) = 1 - \frac{| 8 - 7 |}{20} = 0.95 \end{array}

따라서,

$S T (R_{1, 2}) = S T (X_{1}) \times S T (X_{5}) = 0.8 \times 0.95 = 0.76$

N번 부스팅한 경우, N개의 DT가 형성되며 또한 N개의 지배규칙이 생성된다. 이들 간의 유사도를 계산하게 되는 조합의 가지 수는 _nC₂개다. 따라서, 지배규칙간 유사도를 바탕으로 안정성은 다음과 같이 정의 된다.

S T (R) = \frac{\sum_{p} \sum_{q < p} S T (R_{p, q})}{_{n} C_{2}}

(12)

둘째, 해석력 관점에서 DT 알고리즘의 모든 규칙에는 뿌리 노드의 분기기준이 들어간다. 따라서 뿌리 노드의 유사성이 높을수록 DT 알고리즘의 안정성이 높다고 할 수 있다. N번 부스팅을 시행하여 N개의 DT를 발생시켰 다면, N개의 뿌리 노드가 만들어진다. 이 경우 비교적 간 단하게 N개의 뿌리노드의 동질성을 평가하는 방법은 분 기의 임계값은 무시하고 분기 변수만을 판단기준으로 분 기기준이 같은 변수이면 동질 노드로 보고 다른 변수이면 이질로 판단한다. 이 경우 지니지수로 간단하게 동질성을 계산할 수 있다. 가령 N개의 뿌리 노드가 분기기준이 같 은 변수끼리 하나의 그룹으로 묶을 때, $N_{1}, N_{2}, \dots N_{k}$ 개의 그룹으로 나누어진다면, 지니지수는 다음과 같다.

S T (R N) = 1 - \sum_{k = 1}^{K} p_{k}^{2}

(13)

여기서, ST(RN)은 뿌리 노드 RN의 안정성이고 p_k는 $\frac{N_{k}}{N}$ 이다.

유사도와 달리 지니지수는 0에 가까울수록 동질성이 높아지며, 따라서 안정성이 높아진다. 이 경우는 임계값 이 무시되는 단점이 있으므로, 임계값을 고려할 경우, 식 (10)을 토대로 뿌리 노드 분기기준의 안정성을 측정할 수 있다. 따라서 뿌리 노드의 안정성은 식 (13)과 식 (10), 두 가지 방식에 의해 측정된다.

4. 세 개의 DT 알고리즘의 해석력 비교실험

세 개의 DT 알고리즘의 해석력을 비교하는 실험을 수 행하기 위해 수집된 데이터의 특성이 <Table 1>에 나와 있다. <Table 1>의 속성(Attributes)에서 N은 수치형 변수 (Numerical variable)을 의미하고 C는 범주형 변수(Categorical variable)을 의미한다. <Table 1>에 나타난 데이터 는 UCI DATASET 7개, Kaggle DATASET 3개로 총 10개 이다. 훈련 데이터와 검증 데이터를 8:2로 분리하여 실험 을 30번 반복 시행했다. 예측적 정확도를 비교하는 실험이 아니므로, 가지치기는 가장 간단한 방식인 종료 조건으로 대체되었다. 본 예제 실험에서 종료 조건은 다음과 같다. 하나의 노드에서 분기되는 두 개의 자식노드의 데이터 개 수가 각각 전체 데이터 개수의 3% 미만이면 분기하지 않 고, 그 노드는 리프노드가 된다.

이들 데이터에 대해 세 개의 DT 알고리즘을 적용한 결과의 해석력을 비교하는 작업은 두 가지로 나누어진 다. 안정성을 제외한 나머지 해석력 평가척도는 서로 긴 밀하게 얽혀 있다. 즉, DT의 깊이가 낮은 리프 노드에서 동질성(리프트)이나 커버리지가 높은 리프 노드가 많은 것이 해석력 차원에서 바람직한 것이기 때문이다. 따라 서 안정성을 제외한 나머지 4가지 평가 척도는 동시에 비교가 이루어질 것이다. 다음 DT 알고리즘의 안정성은 별도로 비교분석이 이루어질 것이다.

4.1 DT의 깊이에 따른 3가지 분기기준의 동질성, 커버리지 그리고 리프트 비교

<Table 2>에 각 데이터마다 30번 부스팅하여 DT 알고 리즘을 적용한 결과의 평균값이 나와 있다.

여기서 엔트로피를 사용한 분기기준은 약어로 ENT로 표시되었고, 마찬가지로 GINI, GR은 각각 지니지수와 게인비율을 사용한 분기기준을 의미한다. 일단 깊이 1에 서 보면 10개 중 3개의 데이터에서 GR 분기기준에 따른 DT 알고리즘만 리프노드가 생성됨을 알 수 있다. 2개의 데이터에서는 모든 DT 알고리즘에서 리프 노드가 형성 되지 않았다. 5개의 데이터를 보면 동질성이나 리프트는 3개의 데이터에서 GR이 우수하고 하나는 ENT가 나머지 하나는 3가지가 거의 같은 결과를 보인다. 커버리지 측 면에서는 5개중 4개의 데이터에서 GINI가 우수하고 나 머지 하나에서 ENT가 우수한 결과를 보임을 알 수 있다.

DT의 깊이가 2부터는 깊이 1과 같이 GR만 리프 노드 가 생성되는 현상은 보이지 않는다. 또한 모든 평가척도 에서 우월한 분기기준이 존재하지 않으며, 특정 척도에서 도 전체 10가지 데이터에 대해서 전체적으로 우수한 분기 기준이 깊이 1에서와 같이 분명하지 않다. 따라서 나머지 깊이에서는 이들을 평균한 값을 토대로 평가척도별 분기 기준의 성능을 비교해 보고자 한다. 깊이 1부터 깊이 5까 지의 평가척도별로 각 분기기준의 성능을 비교하면, 첫째 리프트의 경우 GR이 매우 우수한 성능을 보인다. 10개의 데이터 중 8개에서 GR이 가장 우수한 성능을 보였다. 리 프트와 유사한 개념인 동질성에서는 리프트만큼은 아니 지만 GR이 5개의 데이터에서 가장 우수한 결과를 보였 고, ENT는 3개의 데이터, 그리고 GINI는 2개의 데이터에 서 우수한 결과를 보인다. 커버리지는 평균값은 의미가 없고 깊이 5까지의 누적 커버리지가 의미가 있으므로 깊 이 5에서의 누적 커버리지를 보면 모든 데이터가 깊이 5 이전 리프 노드로 수렴된 한 개 데이터를 제외한 9개의 데이터중 8개의 데이터에서 GINI가 가장 좋은 결과를 보 인다. 이중 4개의 데이터에서는 GINI와 ENT간의 차이가 경미함을 알 수 있다. 특징적인 것은 9개의 데이터중 6개 의 데이터에서 GR은 나머지 분기기준에 비추어 커버리 지가 20%에서 30% 떨어지는 점을 보인다는 것이다. 이 는 GR의 경우 매우 많은 규칙들이 깊이 6 이상에서 형성 됨을 보여, 해석력이 떨어짐을 알 수 있다. 이상을 종합 하면, GR은 리프트와 동질성 측면에서 우수한 성능을 보 이나 커버리지에서는 매우 낮은 성능을 보이고, GINI와 ENT는 그 반대의 특징을 보임을 알 수 있다.

4.2 3가지 분기기준의 안정성 비교

안정성 비교를 위해 먼저 지배 규칙의 안정성을 비교해 보자. <Table 3>에 지배 규칙의 유사성이 세 가지 분기기준 에 대해 나와 있다. <Table 3>을 보면 3가지 분기기준에 대해 모두 안정성이 1로 나온 ‘australian’ 데이터를 제외한 9개의 데이터중 4개의 데이터에서 ENT의 안정성이 가장 높게 나왔다. 나머지 4개 데이터에서는 GINI가 가장 높게 나왔다. 그런데 ENT가 높은 데이터에서는 GINI와의 차이 가 GINI가 높은 데이터에서의 GINI와 ENT와의 차이보다 더 커서 10개 데이터의 평균값을 비교 기준으로 하면 ENT 가 지배 규칙의 안정성 측면에서 가장 좋은 결과를 보인다.

다음으로 뿌리 노드의 안정성을 비교해 보자.

뿌리 노드의 안전성은 두 가지 방식으로 측정하고자 한 다. 첫째, 식 (10)을 이용하여 뿌리 노드의 분기기준의 변수 와 임계값을 토대로 뿌리 노드 분기기준의 유사도를 측정하 는 것이다. 둘째, 임계값을 고려하지 않고, 분기 변수만을 고려하여 식 (13)을 사용한 지니계수를 구하여 뿌리 노드의 동질성을 측정하는 것이다. <Table 4>에 식(10)을 이용한 측정 결과가 나와있다. 모든 분기기준이 유사도 1을 보여준 두 개의 데이터를 제외한 8개의 데이터를 보면 유사도가 가장 높은 분기기준이 데이터별로 고르게 나누어져 있는 것을 볼 수 있다. 즉, 뿌리 노드의 유사성 측면에서 안정성이 타 분기기준에 비해 우월한 분기기준이 보이지 않는다. 그 러나 ENT분기기준은 유사도가 타 분기기준에 비해 낮은 경우 그 차이가 크지 않다. 결과적으로 10개 데이터의 유사 도의 평균값을 보면 ENT가 가장 좋은 결과를 보이고 있다. <Table 5>에 식 (1)을 사용한 측정 결과가 나와있다. 임계값 의 차이를 고려하지 않으므로 5개 데이터에서 지니계수가 모든 분기기준에 대하여 0으로 나왔다. 나머지 데이터의 경우, ENT는 ‘yeast’와 ‘breast-cancer-wisconsin’에서 가장 동질성이 높았고, GiNi는 ‘abalone’ 그리고 GR는 ‘churn’, ‘ionosphere’와 ‘breast-cancer-wisconsin’에서 가장 동질성이 높은 결과를 보였다. 그러나 10개 데이터의 평균을 보면 ENT가 가장 좋은 결과를 보인다. 따라서 지배 규칙의 유사 성이나 뿌리 노드의 유사성 두 가지를 모두 고려하면 ENT 가 가장 안정성이 우수한 분기기준이라고 할 수 있다.

5. 결론 및 추후 연구방향

DT 알고리즘에서 가장 널리 사용되는 3가지 분기기준 의 해석력을 평가하는 척도로 본 논문은 리프트, 동질성, 커버리지, DT의 깊이, 그리고 안정성이라는 5가지 척도 를 제시하였다. 5개의 평가척도중 안정성은 별도로 측정 되어야 하는 개념으로 DT 알고리즘의 안정성을 평가하 기 위해, 본 논문은 지배규칙의 유사도와 뿌리 노드의 유 사도라는 두 개의 개념과 측정 방법을 제시하였다. UCI 와 Kaggle에서 수집한 10개의 데이터를 토대로 3개의 분 기기준에 따른 DT 알고리즘의 해석력을 비교한 결과는 다음과 같다.

첫째, 깊이가 1로 가장 단순한 규칙을 생성하는 경우 는 GR 분기기준에 따른 DT 알고리즘이 가장 좋은 결과 를 보였다.

둘째, 깊이 1부터 깊이 5까지 종합한 결과, GR 분기기 준에 따른 DT 알고리즘은 리프트와 동질성 측면에서 우 수한 성능을 보이나 커버리지에서는 매우 낮은 성능을 보이고, GINI와 ENT 분기기준에 따른 DT 알고리즘은 그 반대의 특징을 보임을 알 수 있다.

셋째, 지배 규칙의 유사성이나 뿌리 노드의 유사성 두 가지를 모두 고려하면 ENT 분기기준에 따른 DT 알고리 즘이 가장 안정성이 우수한 결과를 보였다.

이러한 결과를 보면, GR 분기기준에 따른 DT 알고리 즘은 안정성을 개선시키는 방법[10]과 함께 사용해야 한 다는 것을 알 수 있다. 또한 데이터의 일부분이라도 동질 성이 높은 규칙을 찾고 싶으면 GR을 사용하고 비교적 데 이터의 많은 부분을 특정 규칙으로 설명하고자 할 때는 ENT나 GINI 분기기준에 따른 DT 알고리즘을 사용하는 것이 바람직하다고 할 수 있다.

본 논문은 가장 널리 사용되는 분기기준에 따른 DT 알고리즘의 해석력을 비교하였으나, 비교의 대상을 규칙 유도 알고리즘 등으로 넓히는 것이 향후 중요한 연구과 제가 될 것이다.

Acknowledgement

This study was supported by the Research Program funded by the SeoulTech (Seoul National University of Science and Technology).

Figure

<Figure 1>.

PDR Framework[22]

<Figure 2>.

Example Decision Trees

Table

<Table 1>.

Description of Datasets

<Table 2>.

Performance of 3 Splitting Criteria

<Table 3>.

Stability of Dominant Rules in 3 Splitting Criteria

<Table 4>.

Stability of Root Node Spliiting Variables in 3 Splitting Criteria

<Table 5>.

Gini Index of Root Nodes in 3 Splitting Criteria

Reference

An, A. and Cercone, N., Rule Quality Measures for Rule Induction Systems, Computational Intelligence, 2001, Vol. 17, No. 3, pp. 409-424.
Baesens, B., Mues, C., De Backer, M., and Vanthienen, J., Building Intelligent Credit Scoring Systems Using Decision Tables, In : Enterprise Information Systems V, 2004, pp. 131-137.
Belle, V. and Papantonis, I., Principles and Practice of Explainable Machine Learning, arXiv preprint arXiv: 2009.11698, 2020.
Breiman, L., Friedman, J.H., Olshen, R.A., and Stone, C.J., Classification and Regression Trees, Monterey, CA, USA : Wadsworth and Brooks, 1984.
Breiman, L., Heuristics of Instability and Stabilization in Model Selection, The Annals of Statistics, 1996, Vol. 24, No. 6, pp. 2350-2383.
Briand, B., Ducharme, G.R., Parache, V., and Mercat- Rommens, C., A Similarity Measureto Assess the Stability of Classification Trees, Computational Statistics and Data Analysis, 2009, Vol. 53, No. 4, pp. 1208-1217.
Buntine, W. and Niblett, T., A Further Comparison of Splitting Rules for Decision-Tree Induction, Machine Learning, 1992, Vol. 8, No. 1, pp. 75-85.
Cano, A., Zafra, A., and Ventura, S., An Interpretable Classification Rule Mining Algorithm, Information Sciences, 2013, Vol. 240, pp. 1-20.
Chandra, B., Kothari, R., and Paul, P., A New Node Splitting Measure for Decision Tree Construction, Pattern Recognition, 2010, Vol. 43, No. 8, pp. 2725-2731.
Dannegger, F., Tree Stability Diagnotics and Some Remedies for Instability, Statistics in Medicine, 2000, Vol. 19, No. 4, pp. 475-491.
Freitas, A.A., Comprehensible Classification Models : A Position Paper, ACM SIGKDD Explorations Newsletter, 2014, Vol. 15, No. 1, pp. 1-10.
Garcia, S., Fernandez, A., and Herrera, F., Enhancing the Effectiveness and Interpretability of Decision Tree and Rule Induction Classifiers with Evolutionary Training Set Selection over Imbalanced Problems, Applied Soft Computing, 2009, Vol. 9, No. 4, pp. 1304-1314.
Goldstein, A. and Buja, A., Penalized Split Criteria for Interpretable Trees, arXiv preprint arXiv:1310.5677, 2013.
Harris, E., Information Gain Versus Gain Ratio : A Study of Split Method Biases, The MITRE Corp., McLean, VI, USA, Tech. Rep., 2001.
Jacobucci, R., Decision Tree Stability and its Effect on Interpretation, Retrieved from osf.io/m5p2v, 2018.
Jaworski, M., Duda, P., and Rutkowski, L., New Splitting Criteria for Decision Trees in Stationary Data Streams, IEEE Trans. Neural Netw. Learn. Syst., 2018, Vol. 29, No. 6, pp. 2516-2529.
Kotsiantis, S.B., Supervised Machine Learning : A Review of Classification Techniques, Informatica, 2007, Vol. 31, No. 3, pp. 249-268.
Leiva, R.G., Anta, A.F., Mancuso, V., and Casari, P., A Novel Hyperparameter-Free Approach to Decision Tree Construction that Avoids Overfitting by Design, IEEE Access, 2019, Vol. 7, pp. 99978-99987.
Li, R.-H. and Belford, G.G., Instability of Decision Tree Classification Algorithms, In Proceedings of the 8^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, Alberta, Canada, 2002, pp. 570-575.
Lustrek, M., Gams, M., and Martincic-Ipsic, S., What Makes Classification Trees Comprehensible?, Expert Syst. Appl., 2016, Vol. 62, pp. 333-346.
Martens, D., Vanthienen, J., Verbeke, W., and Baesens, B., Performance of Classification Models from a User Perspective, Decision Support Systems, 2011, Vol. 51, No. 4, pp. 782-793.
Murdoch, W.J., Singh, C., Kumbier, K., Abbasi-Asl, R., and Yu, B., Interpretable Machine Learning : Definitions, Methods, and Applications, arXiv e-prints, p. arXiv:1901.04592, 2019.
Norouzi, M., Collins, M., Johnson, M.A., Fleet, D.J., and Kohli, P., Efficient Non-Greedy Optimization of Decision Trees, Proceedings of the 28^th International Conference on Neural Informsation Processing, 2015, pp. 1729-1737.
Pazzani, M.J., Mani, S., and Shankle, W.R., Acceptance of Rules Generated by Machine Learning Among Medical Experts, Methods of Information in Medicine, 2001, Vol. 40, No. 5, pp. 380-385.
Quinlan, J.R., C4.5 : Programs for Machine Learning, San Francisco, CA, USA : Morgan Kaufmann, 1993.
Quinlan, J.R., Induction of Decision Trees, Machine Learning, 1986, Vol. 1, No. 1, pp. 81-106.
Verbeke, W., Marteens, D., Mues, C., and Baesens, B., Building Comprehensible Customer Churn Prediction Models with Advanced Rule Induction Techniques, Expert Systems with Applications, 2011, Vol. 38, No. 3, pp. 2354-2364.
Wang, Y. and Xia, S.-T., Unifying Attribute Splitting Criteria of Decision Trees by Tsallis Entropy, in Proc. IEEE Int. Conf. Acoust., Speech Signal Process(ICASSP), 2017, pp. 2507-2511.
Wang, Y., Xia, S.-T., and Wu, J., A Less-Greedy Two- Term Tsallis Entropy Information Metric Approach for Decision Tree Classification, Knowledge-Based Systems, 2017, Vol. 120, pp. 34-42.
Zhao, Y. and Zhang, Y., Comparison of Decision Tree Methods for Finding Active Objects, Advances in Space Research, 2008, Vol. 41, No. 12, pp. 1955-1959.