python으로 결정 트리 분류 알고리즘 구현

이 문서는 결정트리 분류 알고리즘을 python으로 구현한 구체적인 코드를 공유하고, 참고용으로 제공합니다. 구체적인 내용은 다음과 같습니다:

1개요

결정트리(decision tree) - 널리 사용되는 분류 알고리즘입니다.

베이즈 알고리즘에 비해, 결정트리의 장점은 구성 과정에 어떤 전문 지식도 필요하지 않으며, 매개변수 설정도 필요하지 않다는 점입니다.

실제 응용에서, 탐색적 지식 발견에 대해 결정트리가 더 적합합니다.

2알고리즘 아이디어

간단히 말해서, 결정트리 분류의 아이디어는 연인을 찾는 것과 비슷합니다. 현실적인 상황에서, 아래와 같은 대화가 나옵니다:

　　　　　 딸: 몇 살이세요?

　　　　　 어머니:26。

　　　　　 딸: 잘생겼나요?

　　　　　 어머니: 매우 좋습니다.

　　　　　 딸: 수입이 높은가요?

　　　　　 어머니: 매우 높지 않고, 중간 정도입니다.

　　　　　 딸: 공무원이죠?

　　　　　 어머니: 예, 세무청에서 일하고 있습니다.

　　　　　 딸: 그렇다면, 나가서 뵙겠습니다.　

이 소녀의 결정 과정은 표준적인 분류 트리 결정입니다.

본질:연령, 외모, 소득 및 공무원 여부에 따라 남자를 두 가지 분류로 나눕니다: 만나거나 만나지 않습니다

이 소녀가 남자에 대한 요구는 다음과 같습니다:30세 미만, 외모가 중상급 이상이고 고소득자나 중상급 이상의 공무원이면, 이를 다음 그림으로 소녀의 결정 논리를 나타냅니다

위의 그림은 이 소녀가 만나러 가기로 결정하는 전략을 완벽하게 나타냅니다. 그 중:

◊ 녹색 노드는 판단 조건을 나타냅니다

◊ 주황색 노드는 결정 결과를 나타냅니다

◊ 화살표는 다른 상황에서의 판단 경로를 나타냅니다

적은 빨간 선은 위의 예제에서 소녀의 결정 과정을 나타냅니다.　

이 그림은 거의 결정 트리입니다. 그러나 그림에서의 판단 조건이 정량화되지 않았기 때문에, strict sense의 결정 트리로는 볼 수 없습니다. 모든 조건을 정량화하면 진정한 결정 트리가 됩니다.　

결정 트리 분류 알고리즘의 핵심은 "선전 데이터"를 사용하여 최적의 결정 트리를 생성하여未知 데이터의 분류를 예측하는 것입니다　

결정 트리: 트리 구조(이진 트리나 비이진 트리가 될 수 있습니다). 각 비잎 노드는 특성 속성에 대한 테스트를 나타내며, 각 가지는 이 특성 속성이 특정 범위에서의 출력을 나타내며, 각 잎 노드는 한 개의 분류를 저장합니다. 결정 트리를 사용하여 결정하는 과정은 뿌리 노드에서 시작하여, 분류 대상의 특성 속성을 테스트하고, 그 값에 따라 가지를 선택하여 잎 노드에 도달하여 잎 노드에 저장된 분류를 결정 결과로 사용하는 것입니다.

3、결정 트리 생성

다음과 같은 사과의 좋고 나쁜을 판단하는 데이터 샘플이 있습니다:

샘플　　　 빨간색　　　　 큰　　　　　 좋은 사과

0　　　　　　　 　1　　　　　 1　　　　　　　　 1

1　　　　　　　 　1　　　　　 0　　　　　　　　 1

2　　　　　　　 　0　　　　　 1　　　　　　　　 0

3　　　　　　　 　0　　　　　 0　　　　　　　　 0

샘플이 있습니다2개의 속성이 있으며, A0은 사과가 빨간 사과인지 여부를 나타냅니다. A1대사과가 되는지 여부를 나타냅니다. 이 데이터 샘플을 사용하여 사과의 좋고 나쁜을 자동으로 판단하는 결정 트리를 생성하려고 하면

이 예제의 데이터는 단지2개의 속성이 있기 때문에, 모든 가능한 결정 트리를 전부 탐색할 수 있습니다.2그림으로 보여집니다:

우선 왼쪽이 A0(빨간색)을 구분 근거로 사용하는 결정 트리가 오른쪽의 A를 사용하는 것보다 우수합니다1(크기) 구분 근거로 사용하는 결정 트리.

물론 이는 직관적인 인식입니다. 그러나 직관은 프로그램 구현으로 전환되기에 적합하지 않으므로, 두 트리의 성능을 평가하기 위해 정량적인 검토가 필요합니다.

결정 트리 평가에 사용되는 정량적인 검토 방법은각 구분 상황의 정보 엔트로피 증가를 계산합니다:

선택된 특성을 통해 데이터 구분 후 정보 엔트로피가 가장 많이 감소하면, 이 구분 특성이 최적 선택입니다　

속성 구분 선택(즉, 결정 트리 생성)의 근거:

간단히 말해서, 엔트로피는 "무질서, 혼란"의 정도입니다.

계산을 통해 이해할 수 있습니다:

1、원본 샘플 데이터의 엔트로피:

예제 총 수:4

좋은 사과:2

부패한 사과:2

엔트로피: -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1

정보 엔트로피는1현재 가장 혼란스럽고 무질서한 상태를 나타냅니다.

2、두 그래프 트리의 분류 결과 엔트로피 증가 계산

트리1먼저 A0를 선택한 후 각 서브 노드의 정보 엔트로피 계산은 다음과 같습니다：

0，1잎 노드에는2개의 긍정 예제，0개의 음성 예제. 정보 엔트로피는 e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0。

2，3잎 노드에는 0개의 긍정 예제가 있으며，2개의 음성 예제. 정보 엔트로피는 e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0。

따라서 A0 분류 후의 정보 엔트로피는 각 서브 노드의 정보 엔트로피가 서브 노드 비율의 가중 평균입니다: E = e1*2/4 + e2*2/4 = 0。

A0를 선택한 후 분류의 정보 엔트로피 증가 G(S, A0) = S - E = 1 - 0 = 1.

실제로, 결정 트리의 잎 노드는 모두 동일한 분류에 속하므로, 정보 엔트로피는 항상 0입니다.　

트리2먼저 A를 선택합니다1분류를 한 후, 각 서브 노드의 정보 엔트로피 계산은 다음과 같습니다：

0，2서브 노드가1개의 긍정 예제，1개의 음성 예제. 정보 엔트로피는 e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

1，3서브 노드가1개의 긍정 예제，1개의 음성 예제. 정보 엔트로피는 e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

따라서 A를 선택합니다1분류 후의 정보 엔트로피는 각 서브 노드의 정보 엔트로피가 서브 노드 비율의 가중 평균입니다: E = e1*2/4 + e2*2/4 = 1也就是说分了跟没分一样！

A를 선택합니다1분류의 정보 엔트로피 증가 G(S, A1）=S - E = 1 - 1 = 0.　

따라서, 각 번째 분류 전에 정보 엔트로피 증가가 가장 큰 분류를 계산하는 것만으로도 충분합니다.

먼저 A0 분류를 할 때의 정보 엔트로피 증가는1> 먼저 A를1분류 시의 정보 엔트로피 증가로 인해, A0 분류를 먼저 할 것은 최적의 선택입니다!!!

4、알고리즘 지도思想

결정 속성의 분류 후, 데이터의 불규칙도가 점점 낮아지며, 즉 정보 엔트로피가 점점 작아집니다.　

5、알고리즘 구현

데이터 속성을 정리합니다

특정 속성에 따라 데이터를 분류한 정보 엔트로피 증가를 비교하여, 정보 엔트로피 증가가 가장 큰 속성을 첫 번째 분류 기준으로 선택하고, 그 다음 속성을 선택하여 이를 계속 반복합니다.

이상이 이 문서의 전체 내용입니다. 많은 도움이 되길 바라며, 많이 지지해 주시길 부탁드립니다. 노래教程.

선언: 이 문서의 내용은 인터넷에서 가져왔으며, 저작권자는 모두입니다. 내용은 인터넷 사용자가 자발적으로 기여하고 업로드한 것이며, 이 사이트는 소유권을 가지지 않으며, 인공 편집 처리를 하지 않았으며, 관련 법적 책임도 부담하지 않습니다. 저작권 문제가 의심되는 내용이 있으면 notice#w로 이메일을 보내 주시기 바랍니다.3codebox.com（보고할 때는 #을 @으로 변경하십시오.）을 통해 신고하시고 관련 증거를 제공하시면, 사실이 확인되면 이 사이트는 즉시 의심스러운 저작권 내용을 삭제할 것입니다.