나는 의사 결정 트리 를 구축 할 때 엔트로피가 언급되었다고 가정한다 .

설명하기 위해하는 작업 상상 학습 을 분류 남성 / 여성 그룹으로 처음 이름을. 여기에는 각각 m또는로 레이블이 지정된 이름 목록이 제공되며 , 데이터에 맞는 모델f 을 배우고 보이지 않는 새로운 이름의 성별을 예측하는 데 사용할 수 있습니다.

name       gender
-----------------        Now we want to predict
Ashley        f              the gender of "Amro" (my name)
Brian         m
Caroline      f
David         m

첫 번째 단계는 예측하고자하는 대상 클래스와 관련된 데이터 기능 을 결정하는 것 입니다. 특징의 예는 다음과 같습니다 : 첫 글자 / 마지막 글자, 길이, 모음 수, 모음으로 끝나는가 등. 특징 추출 후 데이터는 다음과 같습니다.

# name    ends-vowel  num-vowels   length   gender
# ------------------------------------------------
Ashley        1         3           6        f
Brian         0         2           5        m
Caroline      1         4           8        f
David         0         2           5        m

목표는 의사 결정 트리 를 구축하는 것 입니다 . 나무 의 예 는 다음과 같습니다.

length<7
|   num-vowels<3: male
|   num-vowels>=3
|   |   ends-vowel=1: female
|   |   ends-vowel=0: male
length>=7
|   length=5: male

기본적으로 각 노드는 단일 속성에서 수행되는 테스트를 나타내며 테스트 결과에 따라 왼쪽 또는 오른쪽으로 이동합니다. 클래스 예측 ( m또는 f) 이 포함 된 리프 노드에 도달 할 때까지 트리를 계속 탐색합니다.

따라서이 트리에서 Amro 라는 이름을 실행하면 ” is length <7? ” 테스트를 시작 하고 대답은 yes 이므로 해당 분기로 내려갑니다. 분기 후, 다음 테스트는 ” 모음 수 <3? ” 이며 다시 true로 평가됩니다 . 이것은이라는 레이블이 붙은 리프 노드로 이어지고 m, 따라서 예측은 남성입니다 (그래서 나는 나무가 결과를 정확하게 예측했습니다 ).

의사 결정 트리는 하향식으로 작성 되지만 문제는 각 노드에서 분할 할 속성을 어떻게 선택합니까? 답은 대상 클래스를 가장 순수한 가능한 하위 노드로 가장 잘 분할하는 기능을 찾는 것입니다.

이 순도 를 정보 라고합니다 . 그것은 나타냅니다 예상 양의 정보를 노드에 도달 예를 주어, 새로운 인스턴스 (첫 번째 이름) 남성 또는 여성으로 분류해야하는지 여부를 지정하는 데 필요하다. 노드의 남성 및 여성 클래스 수를 기반으로 계산합니다.

반면 엔트로피 는 불순물 의 측정치입니다(반대). 값이/ 인 이진 클래스에 대해 정의됩니다.ab

Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))

이 이진 엔트로피 함수 는 아래 그림에 나와 있습니다 (무작위 변수는 두 값 중 하나를 사용할 수 있음). 이 확률이 최대 일 때 최대 값에 도달합니다 p=1/2. 즉, p(X=a)=0.5또는 p(X=b)=0.550 % / 50 %의 확률로 a또는 b불확실성이 최대 임을 의미합니다 . 확률이 경우 엔트로피 함수 제로 최소 인 p=1또는 p=0완전한 확실성 ( p(X=a)=1또는 p(X=a)=0각각 후자는 의미 p(X=b)=1).

물론 엔트로피의 정의는 N 개의 결과 (2 개가 아닌)를 갖는 불연속 랜덤 변수 X에 대해 일반화 될 수 있습니다.

( log공식에서는 일반적으로 밑이 2 인 로그로 간주 됨 )

이름 분류 작업으로 돌아가서 예를 살펴 보겠습니다. 나무를 만드는 과정에서 어느 시점에서 다음과 같은 분할을 고려한다고 상상해보십시오.

     ends-vowel
      [9m,5f]          <--- the [..,..] notation represents the class
    /          \            distribution of instances that reached a node
   =1          =0
 -------     -------
 [3m,4f]     [6m,1f]

당신이 볼 수 있듯이, 분할 전에 우리는 9 명의 남성과 5 명의 여성, 즉 한 P(m)=9/14과 P(f)=5/14. 엔트로피의 정의에 따르면 :

Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403

다음으로 우리는 그것을 두 개의 자식 가지를 보면서 분할을 고려한 후 계산 된 엔트로피와 비교합니다. 의 왼쪽 지점 ends-vowel=1에는 다음이 있습니다.

Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852

의 오른쪽 지점 ends-vowel=0에는 다음이 있습니다.

Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917

각 브랜치 아래에있는 인스턴스 수를 가중치 요소 (7 개의 인스턴스가 왼쪽, 7 개의 인스턴스가 오른쪽)로 사용하여 왼쪽 / 오른쪽 엔트로피를 결합 하고 분할 후 최종 엔트로피를 얻습니다.

Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885

이제 분할 전후의 엔트로피를 비교하여 정보 획득 척도 또는 특정 기능을 사용하여 분할을 수행하여 얻은 정보량을 얻습니다.

Information_Gain = Entropy_before - Entropy_after = 0.1518

위의 계산을 다음과 같이 해석 할 수 있습니다.이 end-vowels기능 을 사용하여 분할을 수행하면 하위 트리 예측 결과의 불확실성을 소량의 0.1518 ( 정보 단위로 비트 단위 로 측정)로 줄일 수있었습니다 .

트리의 각 노드에서이 계산은 모든 기능에 대해 수행되며, 정보 게인 이 가장 큰 기능 은 탐욕스러운 방식으로 분할에 대해 선택됩니다 (따라서 불확실성 / 엔트로피가 낮은 순수한 분할 을 생성하는 기능을 선호 함 ). 이 프로세스는 루트 노드 다운에서 재귀 적으로 적용되며 리프 노드에 동일한 클래스를 가진 인스턴스가 모두 포함 된 경우 중지됩니다 (더 이상 분할 할 필요 없음).

숫자 기능 , 누락 값 , 과적 합 및 가지 치기 트리 등 을 처리하는 방법을 포함 하여이 게시물의 범위를 벗어난 일부 세부 정보 는 건너 뛰었습니다 .

답변

I(X) = -log_2(p)

H(Y) = E[ I(Y)]

H(Y) = E[I(Y)] = p I(Y==1) + (1-p) I(Y==0)
     = - p log p - (1-p) log (1-p)

-log p i

I = -Σ p i log (p i )

빨간색 전구가 타 버림 : p 빨간색 = 0, p 녹색 = 1, I =-(0 + 0) = 0
빨간색과 초록색 같음 : p 빨간색 = 1/2, p 녹색 = 1/2 , I =-(2 * 1/2 * log (1/2)) = log (2)
가능한 세 가지 색상 : p i = 1/3, I =-(3 * 1/3 * log (1/3)) = log (3)
녹색과 적색, 녹색, 두 배 가능성 : p 적색 = 1/3, p 녹색 = 2 / 3, I =-(1/3 log (1/3) + 2/3 log (2/3)) = log ( 3)-2/3 로그 (2)

//Loop over image array elements and count occurrences of each possible
//pixel to pixel difference value. Store these values in prob_array
for j = 0, ysize-1 do $
    for i = 0, xsize-2 do begin
       diff = array(i+1,j) - array(i,j)
       if diff lt (array_size+1)/2 and diff gt -(array_size+1)/2 then begin
            prob_array(diff+(array_size-1)/2) = prob_array(diff+(array_size-1)/2) + 1
       endif
     endfor

//Convert values in prob_array to probabilities and compute entropy
n = total(prob_array)

entrop = 0
for i = 0, array_size-1 do begin
    prob_array(i) = prob_array(i)/n

    //Base 2 log of x is Ln(x)/Ln(2). Take Ln of array element
    //here and divide final sum by Ln(2)
    if prob_array(i) ne 0 then begin
        entrop = entrop - prob_array(i)*alog(prob_array(i))
    endif
endfor

entrop = entrop/alog(2)