정보 이득

2. 정의

일반적으로, 기대되는 정보 이득은 이전 상태에서 주어진 정보를 갖는 상태로 바뀔 때 정보 엔트로피 H의 변화이다.

:$IG(T,a)\; =\; H(T)\; -\; H(T|a)$

:$T$를 각각 $(\backslash textbf\{x\},y)\; =\; (x\_1,\; x\_2,\; x\_3,\; ...,\; x\_k,\; y)$ 형식으로 나타내보면, $x\_a\backslash in\; vals(a)$는 $\backslash textbf\{x\}$와 $y$ 해당 클래스 라벨인 $a$번째 속성의 값이다. 속성 $a$에 대한 정보 이득은 다음과 같이 엔트로피 $H()$로 정의된다.

:$IG(T,a)\; =\; H(T)-\backslash sum\_\{v\backslash in\; vals(a)\}\backslash frac$

\cdot H(\{\textbf{x}\in T|x_a=v\})

속성값 각각에 대해 결과 속성에 대한 고유한 분류를 만들 수 있는 경우 상호 의존 정보는 속성에 대한 총 엔트로피와 같다. 이 경우 전체 엔트로피에서 빼는 상대 엔트로피는 0이다.

일반적으로, 기대 정보 이득은 사전 상태에서 어떤 정보가 주어졌을 때의 상태로의 정보 엔트로피 Η|에타^영어의 감소이다.

:$IG(T,a)\; =\; \backslash Eta\{(T)\}\; -\; \backslash Eta\{(T|a)\},$

여기서 $\backslash Eta\{(T|a)\}$는 조건부 엔트로피 $T$의 속성$a$의 값을 조건으로 한다.

이것은 엔트로피 Η|에타^영어를 무작위 변수 $T$의 불확실성의 척도로 해석할 때 직관적으로 타당하다. $T$에 대해 $a$를 학습(또는 가정)함으로써, $T$에 대한 우리의 불확실성이 감소한다(즉, $IG(T,a)$는 양수). 물론 $T$가 $a$와 독립적인 경우를 제외하고는, 이 경우 $\backslash Eta(T|a)\; =\; \backslash Eta(T)$이며, 이는 $IG(T,a)\; =\; 0$을 의미한다.

3. 공식

일반적으로, 기대되는 정보 이득은 이전 상태에서 주어진 정보를 갖는 상태로 바뀔 때 정보 엔트로피 H의 변화이다.

:''IG(T,a) = H(T) - H(T|a)''

''T''를 각각 ('''x''',y) = (x₁, x₂, x₃, ..., x_k, y) 형식으로 나타내보면, x_a∈vals(a)는 '''x'''와 ''y'' 해당 클래스 라벨인 ''a''번째 속성의 값이다. 속성 ''a''에 대한 정보 이득은 다음과 같이 엔트로피 H()로 정의된다.

:''IG(T,a) = H(T)-Σ_v∈vals(a)|{'''x'''∈T|x_a=v}| / |T| * H({'''x'''∈T|x_a=v})''

속성값 각각에 대해 결과 속성에 대한 고유한 분류를 만들 수 있는 경우 상호 정보량은 속성에 대한 총 엔트로피와 같다. 이 경우 전체 엔트로피에서 빼는 상대 엔트로피는 0이다.

일반적으로, 기대 정보 이득은 사전 상태에서 어떤 정보가 주어졌을 때의 상태로의 정보 엔트로피 감소이다.

:''IG(T,a) = Η(T) - Η(T|a)''

여기서 Η(T|a)는 조건부 엔트로피 ''T''의 속성 ''a''의 값을 조건으로 한다.

이것은 엔트로피 Η를 무작위 변수 ''T''의 불확실성의 척도로 해석할 때 직관적으로 타당하다. ''T''에 대해 ''a''를 학습(또는 가정)함으로써, ''T''에 대한 우리의 불확실성이 감소한다(즉, ''IG(T,a)''는 양수). 물론 ''T''가 ''a''와 독립적인 경우를 제외하고는, 이 경우 Η(T|a) = Η(T)이며, 이는 ''IG(T,a) = 0''을 의미한다.

Η(T)를 각 ('''x''',y) = (x₁, x₂, x₃, ..., x_k, y) 형태의 훈련 예시 집합으로 나타내며, 여기서 x_a∈vals(a)는 예시 '''x'''의 ''a''^번째 속성 또는 특징의 값이고, y는 해당 클래스 레이블이다. 속성 a에 대한 정보 이득은 다음과 같이 섀넌 엔트로피 Η( - )를 사용하여 정의된다. 속성 a가 취하는 값 v에 대해

S_a(v) = {'''x'''∈T|x_a=v}

를 속성 a가 v와 같은 T의 훈련 입력 집합으로 정의한다. 그러면 속성 a에 대한 T의 정보 이득은 훈련 집합의 사전 섀넌 엔트로피 Η(T)와 조건부 엔트로피 Η(T|a)의 차이이다.

:Η(T|a)= Σ_v∈vals(a)|S_a(v)| / |T| * Η(S_a(v)).

:''IG(T,a) = Η(T) - Η(T|a)''

상호 정보량은 속성의 각 값에 대해 결과 속성에 대한 고유한 통계적 분류를 만들 수 있는 경우 해당 속성에 대한 총 엔트로피와 같다. 이 경우, 총 엔트로피에서 빼는 상대 엔트로피는 0이다. 특히 값 v∈vals(a)는 훈련 집합 데이터 T를 상호 배타적이고 전체를 포함하는 부분 집합으로 분할하여 속성 a의 값에 대한 범주형 확률 분포 P_a(v)를 유도한다. 분포는 P_a(v) := |S_a(v)| / |T| 로 주어진다. 이 표현에서 a가 주어질 때 T의 정보 이득은 T의 무조건부 섀넌 엔트로피와 a의 유도된 분포에 대해 취해진 기대값이 있는 a에 조건화된 T의 예상 엔트로피 간의 차이로 정의될 수 있다.

:IG(T,a) = Η(T) - Σ_v∈vals(a)P_a(v)Η(S_a(v))

:= Η(T) - 𝔼_Pa[Η(S_a(v))]

:= Η(T) - Η(T|a).

4. 정보 이득의 활용과 장점

정보 이득은 결정 트리 학습에서 특정 속성이 데이터를 얼마나 잘 분류하는지를 나타내는 척도이다. 정보 이득은 의사 결정 트리의 각 노드에서 어떤 속성으로 분할할지를 결정하는 데 사용된다.

정보 이득은 엔트로피 개념을 기반으로 한다. 엔트로피는 데이터 집합의 불순도 또는 무작위성을 나타내는 지표이다.

그림에서 볼 수 있듯이, 데이터가 균일할수록 엔트로피는 낮아지고, 데이터가 혼잡할수록 엔트로피는 높아진다.

정보 이득은 특정 속성으로 데이터를 분할했을 때 엔트로피가 얼마나 감소하는지를 나타낸다. 즉, 상위 노드의 엔트로피에서 하위 노드의 평균 엔트로피를 뺀 값이다.^[2]

:(1) 획득 = (상위 노드의 엔트로피) – (자식 노드의 평균 엔트로피)

예를 들어, 유전자 돌연변이와 암 발생 여부의 관계를 나타내는 간단한 데이터 세트를 생각해 보자.

샘플	돌연변이 1	돌연변이 2	돌연변이 3	돌연변이 4
C1	1	1	1	0
C2	1	1	0	1
C3	1	0	1	1
C4	0	1	1	0
NC1	0	0	0	0
NC2	0	1	0	0
NC3	1	1	0	0

이 데이터 세트에서 1은 샘플에 돌연변이가 있음을 의미하고(참), 0은 샘플에 돌연변이가 없음을 의미한다(거짓). C가 있는 샘플은 암으로 확인되었음을 나타내고, NC는 암이 아님을 의미한다.

이 데이터를 사용하여 의사 결정 트리를 만들 때, 각 노드에서 어떤 돌연변이를 기준으로 분할할지를 정보 이득을 통해 결정할 수 있다.

먼저, 루트 노드의 엔트로피를 계산한다. 루트 노드에는 7개의 샘플이 있으며, 그 중 4개는 암(C), 3개는 암이 아니다(NC). 따라서 루트 노드의 엔트로피는 다음과 같다.

:$\backslash Eta\{(t)\}$ = −(4/7log₂(4/7) + 3/7log₂(3/7)) = 0.985

다음으로, 각 돌연변이로 분할했을 때 자식 노드들의 엔트로피를 계산하고, 이를 바탕으로 정보 이득을 계산한다. 예를 들어, 돌연변이 1로 분할하면 다음과 같다.

• 왼쪽 자식 노드 (돌연변이 1이 1인 샘플): C 3개, NC 1개
• 오른쪽 자식 노드 (돌연변이 1이 0인 샘플): C 1개, NC 2개

정보 이득이 가장 큰 돌연변이 3으로 루트 노드를 분할하는 것이 가장 좋다.

• 연속형 및 이산형 변수 모두에 적용할 수 있다.
• 엔트로피 기반으로 불순도를 측정하므로, 데이터의 특징을 잘 반영한다.

5. 정보 이득의 단점 및 해결 방안

정보 이득은 일반적으로 속성의 관련성을 결정하는 데 좋은 척도이지만 완벽하지는 않다. 정보 이득이 많은 수의 고유 값을 가질 수 있는 속성에 적용될 때 문제가 발생한다. 예를 들어, 어떤 사업체의 고객을 설명하는 데이터를 기반으로 의사 결정 트리를 구축한다고 가정해 보자. 정보 이득은 어떤 속성이 가장 관련성이 높은지 결정하는 데 자주 사용되므로 트리의 루트 근처에서 테스트할 수 있다. 입력 속성 중 하나는 고객이 사업체의 멤버십 프로그램의 회원인 경우 고객의 멤버십 번호일 수 있다. 이 속성은 각 고객을 고유하게 식별하므로 상호 정보가 높지만, 의사 결정 트리에 포함하고 싶지는 않다. 멤버십 번호를 기반으로 고객을 처리하는 방식을 결정하는 것은 아직 보지 못한 고객에게 일반화될 가능성이 낮다(과적합).^[5]

이 문제를 해결하기 위해 로스 퀸란은 정보 이득이 평균 이상인 속성 중에서 정보 이득률이 가장 높은 속성을 선택하는 것을 제안했다.^[5] 이렇게 하면 많은 수의 고유 값을 가진 속성을 고려하는 것에 대해 의사 결정 트리가 편향되지만, 정보 값이 정보 이득보다 높거나 같으므로 정보 값이 매우 낮은 속성에 불공정한 이점을 주지 않는다.^[6]

참조

_[1] 서적 Discovering Knowledge in Data: An Introduction to Data Mining Wiley (publisher)|Wiley
_[2] 웹사이트 What is Entropy and Information Gain? How are they used to construct decision trees? https://www.numpynin[...] 2020-12-10
_[3] 간행물 Predicting Life time of Heart Attack Patient using Improved C4.5 Classification Algorithm https://rjptonline.o[...] 2018
_[4] 웹사이트 machine learning - Why we use information gain over accuracy as splitting criterion in decision tree? https://datascience.[...] 2021-12-09
_[5] 간행물 Induction of Decision Trees
_[6] 웹사이트 What is the range of information gain ratio? https://stats.stacke[...] 2018-08-06