엔트로피, 정보이득 계산과 ID3알고리즘

위와 같이 8개의 사진 중 겨울 가족 여행사진을 찾으라고 했을 때의 엔트로피와 정보이득을 구해보자.

 

 

엔트로피

총 8개의 사진에서 1개의 사진만 겨울 가족여행 사진이고 나머지 7장은 아닐 때의 엔트로피를 Entropy([1+,7-])라고 나타낼 수 있다. p(+)의 경우 1/8, p(-)의 경우 7/8을 Entropy식에 대입해보면 0.543이라는 결과가 나온다. 따라서 엔트로피는 0.543이다.

 

 

정보이득(Information Gain)

정보이득은 주어진 상황에서 하나의 속성을 잡았을 때의 엔트로피를 빼면 된다.

Information Gain(winter family photo), cartoon)은 cartoon을 속성으로 잡았을 때이다. E(winter family photo)는 앞서 구한 0.543이다. 이제 여기서 cartoon을 속성으로 잡았을 때의 엔트로피(E(winter family photo, cartoon))를 빼주면 된다. 이제 E(winter family photo, cartoon)을 구해보자.

• 주어진 8개의 사진에서 cartoon은 총 4개가 있으며 cartoon은 겨울 가족 여행사진이 아니다. 따라서 cartoon의 엔트로피는 E([0+,4-])이다.
• 주어진 8개의 사진에 cartoon이 아닌 사진 4개 중 겨울 가족 여행사진인 것은 1개이다. 이에 대해 엔트로피를 구해보면 E([1+,3-])이다.

따라서 E(winter family photo, cartoon) = 4/8 * E([0+,4-]) + 4/8 * E([1+,3-])이며 계산한 결과는 0.405이다.

최종적으로 Information Gain(winter family photo), cartoon) = E(winter family photo) - E(winter family photo, cartoon)임으로 0.543-0.405는 0.138이나온다.

 

나머지 다른 속성에 대한 엔트로피 계산도 이와 같이 진행하면 된다. 위와 같이 정보이득이 구해지면 ID3 알고리즘은 정보이득이 가장 높은 cartoon을 첫번째 속성으로 지정한다.

 

 

ID3 알고리즘

ID3 알고리즘은 대표적인 의사결정트리 기반 분류 알고리즘이다.

1. 전체 데이터를 포함하는 루트 노드를 생성
2. 만약 샘플들이 모두 같은 클래스라면, 노드는 잎이 되고, 해당 클래스로 레이블을 부여
3. 그렇지 않으면 정보이득이 높은(즉, 데이터를 가장 잘 구분할 수 있는) 속성을 선택(이때 정보이득은 엔트로피의 변화를 가지고 계산)
4. 선택된 속성으로 가지(Branch)를 뻗어 하위 노드들을 생성(각 하위 노드들은 가지의 조건을 만족하는 레코드들)
5. 각 노드에 대해여 2단계로 이동한다.

 

 

 

www.inflearn.com/course/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D%EC%9D%B4%EB%A1%A0-%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%8B%A4%EC%8A%B5/lecture/9538?tab=note

머신러닝 이론 및 파이썬 실습 - 인프런 | 학습 페이지