의사결정 트리에서의 휴리스틱 함수(ing)

엔트로피(Entropty)

• 쉽게 말해서 불확실성.
• 값이 클수록 유용한 정보가 적다.
• 모델이 같은 확률만 갖고 있는 것보다, 다양한 확률값을 가질수록 엔트로피가 작아진다.
  
  확률이 같다면, 무엇이 나올지 예측을 하기가 더 힘들다.
  A는 90% 확률로 1, 10% 확률로 0, B는 50% 확률로 1 과 0 이라는 상황 가정. 이때 우리는 A가 1이 나올 것이라고 더 추측해볼 수 있기 때문에 불확실성이 적어진다.

크로스 엔트로피(Cross Entropy)

• p 와 q 두 경우가 나오기 때문에 Cross Entropy. p와 q는 실제값, 예측값을 의미.

• 예측값이 실제값의 Entropy와 가까워 질수록 더 정확해진다고 볼 수 있다.

• 기본적으로 Binary Cross Entropy 를 사용하는 모습을 많이 볼 수 있는데, 이것이 Cross Etropy 와 같다. 식만 풀어서 쓴 것. 위키피디아 수식 부분

• 또한 log loss 라고 부르기도 한다. cross entropy 값이 커질수록 log likelihood 가 작아진다. 그렇기 때문에 cross entropy 값을 작게 만들어 likelihood 를 작게 만든다. 결국 이렇게 또 negatvie log likelihood 로 불리기도 한다고 함

쿨백-라이블러 발산(Kullback-Leibler Divergence)

KLD는 두 확률분포의 차이를 계산하는 데에 사용하는 함수로, 
어떤 이상적인 분포에 대해, 그 분포를 근사하는 다른 분포를 사용해 
샘플링을 한다면 발생할 수 있는 정보 엔트로피 차이를 계산한다. 
상대 엔트로피(relative entropy), 정보 획득량(information gain), 
인포메이션 다이버전스(information divergence)라고도 한다. 
정보이론에서는 상대 엔트로피, 기계학습의 결정 트리에서는 정보 획득량을 주로 사용한다. 
쿨백-라이블러 발산은 비대칭으로, 두 값의 위치를 바꾸면 함수값도 달라진다. 
따라서 이 함수는 거리 함수는 아니다. 

[위키피디아]

• 정보 엔트로피 차이. 앞에서 배웠던 엔트로피가 두 분포의 차이를 파악하는 것에 쓰인다.

• 수리통계학 책의 내용에서 시작해서 개념과 증명을 적어보자.
• 책에서는 어떠한 부분에서 중점을 두는지
• 문제에서 적용될 때는 어떻게 사용되는지
• 데이터 분야에서는 어떻게 적용을 하는지?
  https://engineer-mole.tistory.com/91
  https://hyunw.kim/blog/2017/10/27/KL_divergence.html
  
  

정보 이득(Information gain)

• Information gain은 사전 엔트로피에서 사후 엔트로피를 뺀 값을 의미한다.
• 값이 클수록 정보 이득이 크다(=불확실성이 줄었다.)
• 사후 노드는 세부적인 하위 노드들로 보면 좋겠다.
  
  

정보 이득비(Information gain ratio)

• Information Gain 의 단점으로는, Node의 갯수가 많은 쪽이 더 좋은 곳으로 볼 수 있다는 것이다. (split 을 많이 할수록 information gain 이 더 높아지기 때문)
• 이러한 문제를 해결하기 위해서 Ratio 개념을 적용한다.
  
  
  $G_R(D,A) = g(사전, 사후) /H_A(D)$

지니 계수

• 불순도(impurity) 라는 개념이 쓰인다. 이는 엔트로피와 유사한 개념이다.

• 의사결정나무는 불순도를 낮추는 방향으로 진행된다.

• 결국 이 또한 (A:50%, B:50%) 인 경우보다는 (A:10%, B:90%) 인 형태가 더 불순도가 낮게 된다.
  
  

  $Gini(D) = 1 - \displaystyle\sum_{H}[p(H|D)]^2$

• (A:50%, B:50%) : Gini = 1 - [(0.5)^2 + (0.5)^2] = 1 - 0.5 = 0.5

• (A:10%, B:90%) : Gini = 1 - [(0.1)^2 + (0.9)^2] = 1 - 0.82 = 0.18

• 클래스가 한 쪽에 몰려있는 경우가 지니계수가 더 낮은 것을 볼 수 있다.

• 이진 트리 분할 방법
• 특징 A의 값에 따라 둘로 나누어 각각을 좌우 하위 트리로 보낸다.
• |D| 는 샘플 집합의 원소 개수

Reference

데이터 과학자와 데이터 엔지니어를 위한 인터뷰 문답집
Information gain
Kullback-Leibler divergence
https://process-mining.tistory.com/106
https://lucy-the-marketer.kr/ko/growth/decision-tree-and-impurity/

• 순록님 글을 참고 많이 하였음
  초보를 위한 정보이론 안내서 - Entropy란 무엇일까 SERIES 1/3
  초보를 위한 정보이론 안내서 - Cross Entropy 파헤쳐보기 SERIES 2/3