데이터 마이닝의 의사 결정 트리 알고리즘 예제

decision tree algorithm examples data mining

이 심층 자습서에서는 데이터 마이닝의 의사 결정 트리 알고리즘에 대한 모든 것을 설명합니다. 의사 결정 트리 예제, 알고리즘 및 분류에 대해 배우게됩니다.

우리는 몇 가지를 보았습니다 데이터 마이닝 예 이전 튜토리얼에서 무료 데이터 마이닝 교육 시리즈 .

의사 결정 트리 마이닝은 분류 모델을 구축하는 데 사용되는 데이터 마이닝 기술 유형입니다. 이름처럼 나무와 같은 구조의 형태로 분류 모델을 구축합니다. 이러한 유형의 채굴은지도 수업에 속합니다.

지도 학습에서는 목표 결과가 이미 알려져 있습니다. 의사 결정 트리는 범주 및 숫자 데이터 모두에 사용할 수 있습니다. 범주 형 데이터는 성별, 결혼 여부 등을 나타내고 숫자 데이터는 나이, 체온 등을 나타냅니다.

devops 인터뷰 질문과 경험이 풍부한

데이터 세트가있는 의사 결정 트리의 예가 아래에 나와 있습니다.

(영상 출처 )

학습 내용 :

• 의사 결정 트리의 사용은 무엇입니까?
• 분류 분석
• 회귀 분석
• 의사 결정 트리는 어떻게 작동합니까?
• 의사 결정 트리 유도 알고리즘
• 의사 결정 트리 유도
• 카트
• 기계 학습을위한 의사 결정 트리 유도 : ID3
• Greedy 재귀 이진 분할이란 무엇입니까?
• 트리 생성을위한 속성 선택 방법
  • # 1) 정보 획득
  • # 2) 이득 비율
  • # 3) 지니 인덱스
• 의사 결정 트리에서 과적 합
• 나무 가지 치기 란?
• 예측 모델링이란?
• 의사 결정 트리 분류의 장점
• 의사 결정 트리 분류의 단점
• 결론
• 추천 도서

의사 결정 트리의 사용은 무엇입니까?

의사 결정 트리는 분류 및 회귀 모델을 구축하는 데 사용됩니다. 의사 결정 프로세스에 대한 클래스 레이블 또는 값을 예측하는 데이터 모델을 만드는 데 사용됩니다. 모델은 시스템에 제공된 학습 데이터 세트 (지도 학습)에서 빌드됩니다.

의사 결정 트리를 사용하면 이해하기 쉬운 의사 결정을 시각화 할 수 있으므로 널리 사용되는 데이터 마이닝 기술입니다.

분류 분석

데이터 분류는 중요한 클래스 변수를 설명하는 모델을 구축하는 분석 형식입니다.예를 들면, 은행 대출 애플리케이션을 안전하거나 위험한 것으로 분류하기 위해 구축 된 모델입니다. 분류 방법은 기계 학습 및 패턴 인식에 사용됩니다.

분류 적용에는 사기 탐지, 의료 진단, 타겟 마케팅 등이 포함됩니다. 분류 문제의 출력은 터미널 노드에서 관찰 된 모든 값의 '모드'로 간주됩니다.

분류 모델을 구축하기 위해 2 단계 프로세스를 따릅니다.

1. 첫 번째 단계, 즉 학습 : 학습 데이터를 기반으로하는 분류 모델이 구축됩니다.
2. 두 번째 단계, 즉 분류에서는 모델의 정확성을 확인한 다음 모델을 사용하여 새 데이터를 분류합니다. 여기에 제시된 클래스 레이블은 '예'또는 '아니오', '안전'또는 '위험'과 같은 개별 값의 형태입니다.

건물 분류 모델에 대한 일반적인 접근 방식은 다음과 같습니다.

(영상 출처 )

회귀 분석

회귀 분석은 숫자 속성의 예측에 사용됩니다.

숫자 속성은 연속 값이라고도합니다. 클래스 레이블 대신 연속 값을 예측하도록 구축 된 모델을 회귀 모델이라고합니다. 회귀 분석의 출력은 노드에서 관찰 된 모든 값의 '평균'입니다.

의사 결정 트리는 어떻게 작동합니까?

의사 결정 트리는 이산 및 연속 변수 모두에 대해 작동하는지도 학습 알고리즘입니다. 데이터 세트에서 가장 중요한 속성을 기준으로 데이터 세트를 하위 집합으로 분할합니다. 의사 결정 트리가이 속성을 식별하는 방법과이 분할이 수행되는 방법은 알고리즘에 의해 결정됩니다.

가장 중요한 예측자는 루트 노드로 지정되고 분할은 결정 노드라고하는 하위 노드를 형성하기 위해 수행되며 더 이상 분할되지 않는 노드는 터미널 또는 리프 노드입니다.

의사 결정 트리에서 데이터 세트는 동종 영역과 겹치지 않는 영역으로 나뉩니다. 상위 영역은 더 분할되는 두 개 이상의 분기로 분할되는 단일 위치에 모든 관측치를 표시하므로 하향식 접근 방식을 따릅니다. 이 접근 방식은 탐욕스러운 접근 미래 노드에 초점을 맞추지 않고 작업 한 사이의 현재 노드 만 고려하기 때문입니다.

의사 결정 트리 알고리즘은 최소 관찰 수 등과 같은 중지 기준에 도달 할 때까지 계속 실행됩니다.

의사 결정 트리가 구축되면 많은 노드가 이상치 또는 노이즈 데이터를 나타낼 수 있습니다. 불필요한 데이터를 제거하기 위해 나무 가지 치기 방법이 적용됩니다. 결과적으로 분류 모델의 정확성이 향상됩니다.

모델의 정확도를 찾기 위해 테스트 튜플과 클래스 레이블로 구성된 테스트 세트가 사용됩니다. 테스트 세트 튜플의 백분율은 모델의 정확성을 식별하기 위해 모델에 의해 올바르게 분류됩니다. 모델이 정확한 것으로 확인되면 클래스 레이블이 알려지지 않은 데이터 튜플을 분류하는 데 사용됩니다.

의사 결정 트리 알고리즘 중 일부에는 Hunt의 알고리즘, ID3, CD4.5 및 CART가 포함됩니다.

의사 결정 트리 생성 예

(예는 데이터 마이닝 개념에서 발췌 : Han 및 Kimber)

# 1) 학습 단계 : 훈련 데이터는 분류 알고리즘에 의해 분석 될 시스템으로 공급됩니다. 이 예에서 클래스 레이블은 속성 즉, '대출 결정'입니다. 이 훈련 데이터로 구축 된 모델은 의사 결정 규칙의 형태로 표현됩니다.

# 2) 분류 : 분류 규칙의 정확성을 확인하기 위해 테스트 데이터 세트가 모델에 제공됩니다. 모델이 허용 가능한 결과를 제공하면 알 수없는 클래스 변수가있는 새 데이터 세트에 적용됩니다.

의사 결정 트리 유도 알고리즘

의사 결정 트리 유도

의사 결정 트리 유도는 훈련 세트에서 의사 결정 트리를 학습하는 방법입니다. 훈련 세트는 속성과 클래스 레이블로 구성됩니다. 의사 결정 트리 유도의 응용에는 천문학, 재무 분석, 의료 진단, 제조 및 생산이 포함됩니다.

의사 결정 트리는 훈련 세트 튜플에서 만든 순서도 트리와 같은 구조입니다. 데이터 세트는 더 작은 하위 집합으로 나뉘며 트리 노드 형태로 제공됩니다. 트리 구조에는 루트 노드, 내부 노드 또는 결정 노드, 리프 노드 및 분기가 있습니다.

루트 노드는 최상위 노드입니다. 분류를 위해 선택된 최상의 속성을 나타냅니다. 결정 노드의 내부 노드는 분류 또는 결정 레이블을 나타내는 데이터 세트 리프 노드 또는 터미널 노드의 속성 테스트를 나타냅니다. 분기는 수행 된 테스트의 결과를 보여줍니다.

일부 의사 결정 트리는 이진 노드 , 이는 노드의 정확히 두 가지 분기를 의미하지만 일부 의사 결정 트리는 이진이 아닙니다.

아래 이미지는 승객의 생존 여부를 예측하기위한 Titanic 데이터 세트의 의사 결정 트리를 보여줍니다.

(영상 출처 )

카트

CART 모델, 즉 분류 및 회귀 모델은 모델 구축을위한 의사 결정 트리 알고리즘입니다. 대상 값이 불연속적인 특성을 갖는 의사 결정 트리 모델을 분류 모델이라고합니다.

이산 값은 유한하거나 셀 수없이 무한한 값 집합입니다. 예를 들어, 연령, 크기 등. 대상 값이 연속 값으로 표시되는 모델은 일반적으로 회귀 모델이라고하는 숫자입니다. 연속 변수는 부동 소수점 변수입니다. 이 두 모델을 함께 CART라고합니다.

CART는 Gini Index를 분류 매트릭스로 사용합니다.

기계 학습을위한 의사 결정 트리 유도 : ID3

1970 년대 후반과 1980 년대 초에 J. Ross Quinlan은 기계 학습을위한 의사 결정 트리 알고리즘을 구축 한 연구원이었습니다. 이 알고리즘은 ID3, 반복 이분법 . 이 알고리즘은 E.B Hunt, J, Marin이 설명한 개념 학습 시스템의 확장입니다.

ID3는 나중에 C4.5로 알려지게되었습니다. ID3 및 C4.5는 의사 결정 트리를 구성하기 위해 탐욕스러운 하향식 접근 방식을 따릅니다. 알고리즘은 트리가 구성 될 때 더 작은 하위 집합으로 분할되는 클래스 레이블이있는 훈련 데이터 세트로 시작합니다.

#1) 처음에는 세 가지 매개 변수가 있습니다. 속성 목록, 속성 선택 방법 및 데이터 파티션 . 속성 목록은 훈련 세트 튜플의 속성을 설명합니다.

#두) 속성 선택 방법은 튜플 간의 구별에 가장 적합한 속성을 선택하는 방법을 설명합니다. 속성 선택에 사용되는 방법은 Information Gain 또는 Gini Index 일 수 있습니다.

#삼) 트리의 구조 (바이너리 또는 비 바이너리)는 속성 선택 방법에 의해 결정됩니다.

# 4) 의사 결정 트리를 구성 할 때 튜플을 나타내는 단일 노드로 시작됩니다.

# 5) 루트 노드 튜플이 다른 클래스 레이블을 나타내는 경우 튜플을 분할하거나 분할하기 위해 속성 선택 메서드를 호출합니다. 이 단계는 분기 및 결정 노드의 형성으로 이어질 것입니다.

# 6) 분할 방법은 데이터 튜플을 분할하기 위해 선택해야하는 속성을 결정합니다. 또한 테스트 결과에 따라 노드에서 성장할 분기를 결정합니다. 분할 기준의 주된 동기는 의사 결정 트리의 각 분기에있는 파티션이 동일한 클래스 레이블을 나타내야한다는 것입니다.

분할 속성의 예는 다음과 같습니다.

ㅏ. 위의 분할은 이산 값입니다.

비. 위의 분할은 연속 값을위한 것입니다.

# 7) 위의 분할 단계는 훈련 데이터 세트 튜플에 대한 결정 트리를 형성하기 위해 반복적으로 수행됩니다.

C ++ 입력 출력 파일

# 8) 분할은 모든 파티션이 만들어 지거나 나머지 튜플을 더 이상 분할 할 수없는 경우에만 중지됩니다.

# 9) 알고리즘의 복잡성은 다음과 같이 설명됩니다. n * | D | * 로그 | D | 여기서 n은 훈련 데이터 세트 D 및 | D |의 속성 수입니다. 튜플의 수입니다.

Greedy 재귀 이진 분할이란 무엇입니까?

이진 분할 방법에서는 튜플이 분할되고 각 분할 비용 함수가 계산됩니다. 최저 비용 분할이 선택됩니다. 분할 방법은 2 개의 분기로 구성된 바이너리입니다. 동일한 방법 (비용 계산)이 데이터 세트의 다른 튜플을 분할하는 데 사용되므로 본질적으로 재귀 적입니다.

이 알고리즘은 현재 노드에만 초점을 맞추기 때문에 욕심쟁이라고합니다. 비용을 낮추는 데 초점을 맞추고 다른 노드는 무시합니다.

트리 생성을위한 속성 선택 방법

속성 선택 측정은 튜플이 분할되는 방법을 결정하는 분할 규칙이라고도합니다. 분할 기준은 데이터 세트를 최적으로 분할하는 데 사용됩니다. 이러한 측정 값은 훈련 튜플을 분할하기위한 속성에 순위를 제공합니다.

속성을 선택하는 가장 일반적인 방법은 정보 획득, Gini 인덱스입니다.

# 1) 정보 획득

이 방법은 의사 결정 트리를 작성하는 데 사용되는 주요 방법입니다. 튜플을 분류하는 데 필요한 정보를 줄입니다. 주어진 튜플을 분류하는 데 필요한 테스트 수를 줄입니다. 정보 이득이 가장 높은 속성이 선택됩니다.

데이터 세트 D의 튜플 분류에 필요한 원래 정보는 다음과 같이 제공됩니다.

여기서 p는 튜플이 클래스 C에 속할 확률입니다. 정보는 비트 단위로 인코딩되므로 기본 2에 대한 로그가 사용됩니다. E (s)는 데이터 세트 D의 클래스 레이블을 찾는 데 필요한 평균 정보량을 나타냅니다.이 정보 이득은 엔트로피 .

분할 후 정확한 분류에 필요한 정보는 다음 공식으로 제공됩니다.

여기서 P (c)는 파티션의 가중치입니다. 이 정보는 X로 분할 할 때 데이터 세트 D를 분류하는 데 필요한 정보를 나타냅니다.

정보 이득은 데이터 세트 D의 튜플을 분류하는 데 필요한 원래 정보와 예상 정보의 차이입니다.

이득은 X의 값을 아는 데 필요한 정보의 감소입니다. 정보 이득이 가장 높은 속성이 '최고'로 선택됩니다.

# 2) 이득 비율

정보 획득은 때때로 분류에 쓸모없는 분할을 초래할 수 있습니다. 그러나 이득 비율은 훈련 데이터 세트를 파티션으로 분할하고 총 튜플에 대한 결과의 튜플 수를 고려합니다. 최대 이득 비율이있는 속성은 분할 속성으로 사용됩니다.

# 3) 지니 인덱스

지니 지수는 이진 변수에 대해서만 계산됩니다. 데이터 세트 D의 학습 튜플에서 불순물을 측정합니다.

P는 튜플이 클래스 C에 속할 확률입니다. 속성 A에 의해 이진 분할 데이터 세트 D에 대해 계산되는 Gini 인덱스는 다음과 같이 지정됩니다.

여기서 n은 데이터 세트 D의 n 번째 파티션입니다.

불순물 감소는 원래 데이터 세트 D의 지니 인덱스와 속성 A에 의한 분할 후 지니 인덱스의 차이에 의해 제공됩니다.

불순물의 최대 감소 또는 최대 지니 지수가 분할을위한 최상의 속성으로 선택됩니다.

의사 결정 트리에서 과적 합

과적 합은 의사 결정 트리가 테스트의 깊이를 증가시켜 오류를 줄여 최대한 완벽하게 만들려고 할 때 발생합니다. 이로 인해 매우 복잡한 나무가 생성되고 과적 합이 발생합니다.

과적 합은 의사 결정 트리의 예측 특성을 감소시킵니다. 나무의 과적 합을 방지하는 방법에는 가지 치기 전과 가지 치기가 포함됩니다.

나무 가지 치기 란?

정리는 의사 결정 트리에서 사용되지 않는 분기를 제거하는 방법입니다. 의사 결정 트리의 일부 분기는 이상 값 또는 잡음이있는 데이터를 나타낼 수 있습니다.

나무 가지 치기는 나무의 원치 않는 가지를 줄이는 방법입니다. 이것은 트리의 복잡성을 줄이고 효과적인 예측 분석에 도움이됩니다. 나무에서 중요하지 않은 가지를 제거하므로 과적 합을 줄입니다.

나무를 가지 치는 방법에는 두 가지가 있습니다.

# 1) 사전 정리 :이 접근 방식에서는 의사 결정 트리의 구성이 조기에 중지됩니다. 분기를 더 이상 분할하지 않기로 결정했음을 의미합니다. 생성 된 마지막 노드는 리프 노드가되고이 리프 노드는 튜플 중에서 가장 빈번한 클래스를 보유 할 수 있습니다.

속성 선택 측정은 분할의 가중치를 찾는 데 사용됩니다. 임계 값은 유용한 것으로 간주되는 분할을 결정하기 위해 규정됩니다. 노드 분할로 인해 임계 값 아래로 떨어져 분할이 발생하면 프로세스가 중지됩니다.

# 2) 사후 정리 :이 방법은 완전히 자란 트리에서 이상치 가지를 제거합니다. 원하지 않는 분기는 제거되고 가장 빈번한 클래스 레이블을 나타내는 리프 노드로 대체됩니다. 이 기술은 사전 정리보다 더 많은 계산이 필요하지만 더 안정적입니다.

가지 치기 된 나무는 가지 치기되지 않은 나무에 비해 더 정확하고 간결하지만 복제와 반복이라는 단점이 있습니다.

동일한 속성이 트리 분기를 따라 반복해서 테스트 될 때 반복이 발생합니다. 복제 트리 내에 중복 하위 트리가있을 때 발생합니다. 이러한 문제는 다변량 분할로 해결할 수 있습니다.

아래 이미지는 가지 치기 및 가지 치기되지 않은 나무를 보여줍니다.

의사 결정 트리 알고리즘의 예

예 출처

의사 결정 트리 구성

전망, 온도, 바람 및 습도 속성이 포함 된 지난 10 일 날씨 데이터 세트의 예를 들어 보겠습니다. 결과 변수는 크리켓 경기 여부입니다. ID3 알고리즘을 사용하여 의사 결정 트리를 만듭니다.

1 단계: 첫 번째 단계는 루트 노드를 만드는 것입니다.

2 단계: 모든 결과가 예이면 리프 노드 '예'가 반환되고 그렇지 않으면 리프 노드 '아니오'가 반환됩니다.

Step3 : 모든 관측치의 엔트로피와 E (S) 및 E (S, x) 속성 'x'를 사용하여 엔트로피를 찾습니다.

Step4 : 정보 이득을 찾고 정보 이득이 높은 속성을 선택하십시오.

Step5 : 모든 속성이 적용될 때까지 위의 단계를 반복하십시오.

엔트로피 계산 :

예 아니오

9 5

엔트로피가 0이면 모든 멤버가 동일한 클래스에 속하고 엔트로피가 1이면 튜플의 절반이 한 클래스에 속하고 그중 하나가 다른 클래스에 속함을 의미합니다. 0.94는 공정한 분배를 의미합니다.

최대 정보 이득을 제공하는 정보 이득 속성을 찾으십시오.

예를 들어 'Wind'는 강함과 약함의 두 가지 값을 취하므로 x = {강함, 약함}입니다.

x = 약함 및 x = 강함에 대해 H (x), P (x)를 찾으십시오. H (S)는 이미 위에서 계산되었습니다.

약함 = 8

강함 = 8

'약한'바람의 경우 6 명은 크리켓 경기에 '예'라고 말하고 2 명은 '아니오'라고 답했습니다. 따라서 엔트로피는 다음과 같습니다.

'강한'바람의 경우 3 명은 크리켓 경기를 '아니오', 3 명은 '예'라고 대답했습니다.

최고의 파이썬 IDE Mac OS X

반 항목은 한 클래스에 속하고 나머지 반은 다른 클래스에 속하므로 완벽한 임의성을 보여줍니다.

정보 이득을 계산하고,

마찬가지로 다른 속성에 대한 정보 획득은 다음과 같습니다.

속성 전망에는 최고의 정보 획득 0.246이므로 루트로 선택됩니다.

흐림에는 Sunny, Overcast 및 Rain의 세 가지 값이 있습니다. 크리켓으로 흐린 날씨는 항상 '예'입니다. 따라서 리프 노드 '예'로 끝납니다. 다른 값은 '맑음'및 '비'입니다.

Outlook의 'Sunny'표는 다음과 같습니다.

'Outlook' 'Sunny'의 엔트로피는 다음과 같습니다.

Sunny와 관련된 속성에 대한 정보 획득은 다음과 같습니다.

습도에 대한 정보 이득이 가장 높으므로 다음 노드로 선택됩니다. 마찬가지로 비에 대해 엔트로피가 계산됩니다. 바람은 최고의 정보 이득을 제공합니다 .

의사 결정 트리는 다음과 같습니다.

예측 모델링이란?

분류 모델은 알려지지 않은 속성 집합의 결과를 예측하는 데 사용할 수 있습니다.

알 수없는 클래스 레이블이있는 데이터 세트가 모델에 입력되면 자동으로 클래스 레이블이 할당됩니다. 결과를 예측하기 위해 확률을 적용하는이 방법을 예측 모델링이라고합니다.

의사 결정 트리 분류의 장점

다음은 의사 결정 트리 분류의 다양한 장점입니다.

1. 의사 결정 트리 분류에는 도메인 지식이 필요하지 않으므로 지식 검색 프로세스에 적합합니다.
2. 트리 형태의 데이터 표현은 사람이 쉽게 이해할 수 있으며 직관적입니다.
3. 다차원 데이터를 처리 할 수 ​​있습니다.
4. 매우 정확하고 빠른 프로세스입니다.

의사 결정 트리 분류의 단점

다음은 의사 결정 트리 분류의 다양한 단점입니다.

1. 때때로 의사 결정 트리는 매우 복잡해지며이를 과적 합 트리라고합니다.
2. 의사 결정 트리 알고리즘은 최적의 솔루션이 아닐 수 있습니다.
3. 의사 결정 트리는 일부 클래스 레이블이이를 지배하는 경우 편향된 솔루션을 반환 할 수 있습니다.

결론

의사 결정 트리는 분류 및 회귀 분석을위한 데이터 마이닝 기술입니다.

이 기술은 현재 의료 진단, 타겟 마케팅 등과 같은 많은 영역에 걸쳐 있습니다. 이러한 트리는 ID3, CART와 같은 알고리즘을 따라 구성됩니다. 이러한 알고리즘은 데이터를 파티션으로 분할하는 다양한 방법을 찾습니다.

기계 학습 및 패턴 분석에 사용되는 가장 널리 알려진지도 학습 기술입니다. 의사 결정 트리는 시스템에 제공된 학습 세트에서 학습을 통해 모델을 구축하여 대상 변수의 값을 예측합니다.

이 유익한 튜토리얼에서 의사 결정 트리 마이닝에 대한 모든 것을 배우 셨기를 바랍니다 !!

이전 튜토리얼 | NEXT 튜토리얼

추천 도서

• 데이터 마이닝 예 : 데이터 마이닝의 가장 일반적인 애플리케이션 2021
• 데이터 마이닝 기술 : 알고리즘, 방법 및 최고의 데이터 마이닝 도구
• 데이터 마이닝 : 데이터 분석의 프로세스, 기술 및 주요 문제
• C ++의 B 트리 및 B + 트리 데이터 구조
• C ++의 이진 트리 데이터 구조
• 데이터 마이닝 프로세스 : 관련된 모델, 프로세스 단계 및 과제
• C ++의 AVL 트리 및 힙 데이터 구조
• 데이터 마이닝 대 기계 학습 대 인공 지능 대 딥 러닝