결정 트리

결정 트리(Decision Tree)는 기본적인 분류 및 회귀 방법으로 분류 문제에서 특성을 기준으로 인스턴스를 분류하는 과정을 트리 구조로 나타냅니다. 본질적으로 의사결정 트리 모델은 특징 공간과 클래스 공간에서 정의된 조건부 확률 분포입니다. 의사결정 트리 학습에는 일반적으로 특징 선택, 의사결정 트리 생성, 의사결정 트리 가지치기의 세 단계가 포함됩니다.

?분류 결정 트리 모델은 인스턴스의 분류를 설명하는 트리 구조입니다. 결정 트리는 노드와 방향성 에지로 구성됩니다. 노드에는 내부 노드와 리프 노드의 두 가지 유형이 있습니다. 내부 노드는 기능이나 속성을 나타내고 리프 노드는 클래스를 나타냅니다.

?결정 트리를 사용하여 루트 노드부터 시작하여 인스턴스의 특정 기능을 테스트하고 이때 테스트 결과에 따라 인스턴스를 하위 노드에 할당합니다. 특성 값에 해당합니다. 인스턴스는 리프 노드에 도달할 때까지 이러한 방식으로 반복적으로 테스트되고 할당됩니다. 마지막으로 인스턴스는 리프 노드 클래스로 나뉩니다.

?결정 트리는 주어진 특성 조건에서 클래스의 조건부 확률 분포입니다. 이 조건부 확률 분포는 특성 간격의 분할에 정의됩니다. 특징 공간을 분리된 셀 또는 영역으로 나누고 각 셀에 클래스 확률 분포를 정의하는 것은 조건부 확률 분포를 구성합니다. 결정 트리의 한 경로는 파티션의 단위에 해당하며, 결정 트리가 나타내는 조건부 확률 분포는 각 단위의 주어진 조건에서 클래스의 조건부 확률 분포로 구성됩니다. X가 특징을 나타내는 확률변수이고 Y가 클래스를 나타내는 확률변수라고 가정하면 이 조건부 확률 분포는 P(Y|X)로 표현될 수 있습니다. 이때 노드의 인스턴스는 조건부 확률이 높은 카테고리로 분류됩니다. 즉, 결정 트리 학습 과정은 실제로 데이터 세트에서 조건부 확률 모델을 추정하는 과정입니다. 선택을 할 때 피팅뿐만 아니라 클래스를 기반으로 하는 조건부 확률 모델도 무한히 많습니다. 모델의 능력도 고려해야 하며 일반화 능력도 고려해야 합니다.

?모델이 모델의 피팅 및 일반화 기능을 고려하도록 하기 위해 의사결정 트리 학습에서는 손실 함수를 최소화하는 것을 목표로 정규화된 최대 우도 함수를 손실 함수로 사용합니다. 최적의 모델. 분명히 가능한 모든 결정 트리에서 최적의 결정 트리를 선택하는 것은 NP-완전 문제이므로 실제로는 일반적으로 이 최적화 문제를 대략적으로 해결하기 위해 휴리스틱 방법이 사용됩니다. 즉, 최적의 특징을 재귀적으로 선택하고 이러한 특징을 기반으로 훈련하는 것입니다. 데이터 각 하위 데이터 세트가 최상의 분류를 가질 때까지 분할되고 최종적으로 특징 트리가 생성됩니다. 물론 이런 방식으로 얻은 의사결정 트리는 실제로 차선책이다. 또한, 의사결정 트리의 알고리즘적 특성으로 인해 모델의 과적합을 방지하기 위해 생성된 의사결정 트리를 아래에서 위로 잘라내어 트리를 단순화하고 모델의 일반화 능력을 향상시켜야 합니다. 구체적으로는, 너무 세분화된 리프 노드를 제거하고 이를 부모 노드, 심지어는 상위 노드로 되돌린 후, 상위 노드 이상을 새로운 리프 노드로 변경하는 것이다. 데이터 세트에 많은 기능이 있는 경우 의사결정 트리 학습을 수행하기 전에 데이터 세트의 기능을 필터링할 수도 있습니다.

?결정 트리는 조건부 확률 분포이므로 깊이가 다른 결정 트리는 복잡성이 다른 확률 모델에 해당합니다. 결정 트리의 생성은 모델의 로컬 선택 및 가지치기에 해당합니다. 의사결정 트리는 전역 선택에 해당합니다.

엔트로피 개념은 물리학에서 유래되었습니다. 처음에는 물리학자들이 이 개념을 사용하여 열역학 시스템의 무질서 정도를 측정했습니다. 1948년 클로드 엘우드 섀넌(Claude Elwood Shannon)은 정보 이론에 열역학적 엔트로피를 도입하여 섀넌 엔트로피라고도 합니다.

정보 이론에서 엔트로피는 불확실성의 척도입니다. 정보의 엔트로피가 높을수록 더 많은 정보를 전송할 수 있습니다.

? 앞면과 뒷면이 나올 확률이 동일한 이상적인 동전이 있다면 동전 던지기 이벤트의 엔트로피는 달성할 수 있는 최대값과 같습니다. 우리는 다음 동전 던지기의 결과가 어떻게 될지 알 수 없으므로 모든 동전 던지기는 예측할 수 없습니다. 따라서 일반적인 동전 던지기를 여러 번 사용하면 이 이벤트의 엔트로피는 1비트입니다. 왜냐하면 앞면 또는 뒷면이라는 두 가지 결과만 있고 0, 1 인코딩으로 표현될 수 있고 두 결과는 서로 독립적이기 때문입니다. . n개의 독립적인 실험을 하면 엔트로피는 길이 n의 비트열로 표현될 수 있으므로 n이 된다. 그러나 동전의 양면이 정확히 같다면 일련의 동전 던지기 이벤트의 엔트로피는 0과 같습니다. 결과를 정확하게 예측할 수 있기 때문입니다. 실제 세계에서 우리가 수집하는 데이터의 엔트로피는 위의 두 경우 사이 어딘가에 있습니다.

?약간 더 복잡한 또 다른 예는 무작위 변수가 엔트로피는 이다. 따라서 엔트로피는 실제로 랜덤변수의 비트량과 순차적 발생 확률을 곱하고 합한 수학적 기대값이다.

?볼츠만의 H 정리에 따라 Shannon은 확률 변수 X의 엔트로피를 다음과 같이 정의합니다.

? 확률 변수 X의 정보량은 어디에 있습니까? 확률 변수는 유한 샘플에서 가져오며, 엔트로피는 다음과 같이 표현될 수 있습니다:

?If, then 정의.

?조건부 엔트로피는 같은 방식으로 정의할 수 있습니다.

?조건부 엔트로피(조건부 엔트로피)는 Y의 조건부 확률 분포의 엔트로피임을 쉽게 알 수 있습니다. 주어진 수학적 기대 조건. 최대 우도 추정을 통해 엔트로피와 조건부 엔트로피의 확률을 구할 때 해당 엔트로피와 조건부 엔트로피를 각각 테스트 엔트로피(경험적 엔트로피)와 경험적 조건부 엔트로피(경험적 조건부 엔트로피)라고 합니다.

? 엔트로피가 클수록 확률 변수의 불확실성은 다음 정의에서 확인할 수 있습니다.

? 베이스가 이면 엔트로피의 단위는 예입니다. 예를 들어, 영어에는 26개의 문자가 있습니다. 각 문자가 기사에 동일하게 자주 나타나면 각 문자의 정보량은 다음과 같습니다.

? 마찬가지로 일반적으로 사용되는 문자는 2500개입니다. 한자. 기사에 각 한자가 등장하는 횟수를 평균이라고 가정하면 각 한자의 정보량은 다음과 같다.

?실제로 기사에 등장하는 각 글자와 한자의 수는 다음과 같다. 희귀 문자와 희귀 한자는 상대적으로 정보 함량이 높습니다. 분명히 기대의 정의에 따르면 엔트로피는 전체 메시지 시스템의 평균 메시지 양입니다.

?엔트로피는 데이터 세트의 불확실성을 나타내는 데 사용할 수 있습니다. 엔트로피가 클수록 데이터 세트의 불확실성도 커집니다. 따라서 분할 전과 후의 데이터 세트의 엔트로피 차이를 사용하여 현재 기능을 사용하여 데이터 세트를 분할하는 효과를 측정합니다(딥러닝의 비용 함수와 유사). 분할할 데이터 세트의 경우 분할 전 데이터 세트의 엔트로피는 확실하지만 분할 후 엔트로피는 확실하지 않습니다. 이 값이 작을수록 이 특징 분할을 사용하여 얻은 하위 집합의 불확실성(즉, 더 순수하다). 따라서 값이 클수록 현재의 특징을 사용하여 데이터 세트를 분할할 때 순도가 더 빨리 상승합니다. 최적의 의사결정 트리를 구축할 때 우리는 항상 더 높은 순도의 데이터 하위 집합에 더 빨리 도달하기를 희망합니다. 이 점에 대해 최적화 알고리즘의 경사하강법을 참조할 수 있는데, 그 이유는 각 단계에 따라 손실 함수를 최소화하는 것입니다. 음의 기울기 방법 즉, 음의 기울기 방향은 함수 값이 가장 빠르게 감소하는 방향입니다.

같은 방식으로, 의사결정 트리를 구축하는 과정에서 우리는 항상 집합이 가능한 한 빨리 더 순도가 높은 하위 집합 방향으로 전개되기를 희망하므로 항상 정보 획득을 최대화하는 기능을 선택합니다. 현재 데이터 세트를 나눕니다.

?이 분할 방법에는 분명히 단점이 있습니다. 정보 획득 기준에 따르면 데이터 세트의 특정 특성 B가 큰 값을 가질 때 이 특성에 따라 분할하는 것이 더 쉽습니다. 더 높은 순도 데이터 하위 집합이 너무 작으면 정보 이득이 너무 커져 결국 정보 이득이 더 많은 값을 가진 기능 쪽으로 편향되게 됩니다.

? 카테고리 속성에 다른 값이 있다고 가정하고 데이터 샘플 모음이라고 가정합니다. , 클래스의 샘플 수라고 가정합니다. 주어진 표본에 대한 정보 엔트로피는 다음과 같습니다.

? 그 중 임의의 표본이 에 속할 확률은 일반적으로 로 추정할 수 있습니다.

?속성 A에 다른 값이 있다고 가정하고, 속성 A를 사용하여 집합을 하위 집합으로 나누고, 여기에는 집합의 속성 값 샘플이 포함됩니다. 속성 A가 테스트 속성으로 선택된 경우 이러한 하위 집합은 집합의 노드에서 성장한 새로운 리프 노드입니다. 가 하위 집합에 카테고리가 있는 샘플의 수라고 가정하면 속성 A에 따라 샘플을 나누는 정보 엔트로피는 다음과 같습니다.

그 중 하위 집합에 카테고리가 있는 샘플의 확률은 다음과 같습니다. 마지막으로, 샘플 하위 집합을 속성 A로 분할한 후 얻은 정보 이득(Gain)은 다음과 같습니다.

즉, 속성 A의 정보 이득 = 분할 전 데이터의 엔트로피 - 속성 A로 분할한 후 datalt;/ugt; 하위 집합의 엔트로피입니다. 상호 정보(matual information)라고도 알려진 정보 이득(information Gain)은 특성 X의 정보를 아는 것이 클래스 Y 정보의 불확실성을 줄이는 정도를 나타냅니다. 정보 이득은 분명히 작고 값은 더 큽니다. 이는 테스트 속성 A를 선택하면 분류에 더 많은 정보를 제공하고 A를 선택한 후 분류의 불확실성이 더 작다는 것을 의미합니다.

?고전적인 알고리즘 ID3에서 사용하는 정보 획득 특징 선택 기준은 이러한 상황을 피하기 위해 더 많은 값을 가진 특징으로 구분을 더 편향되게 만듭니다. ID3의 제안자인 J. Ross Quinlan은 특징 선택 기준을 정보 획득에서 ID3 기반의 정보 획득률로 변경한 C4.5를 제안했습니다. 정보 이득을 기준으로 페널티 매개변수를 곱한다. 특성 수가 많으면 페널티 매개변수가 작고, 특성 수가 적으면 페널티 매개변수가 커집니다(정규화와 유사). 이 페널티 매개변수는 분할 정보 측정항목의 반대입니다.

?ID3 및 C4.5와 달리 CART는 Gini 불순물을 기능 선택 기준으로 사용합니다. 지니 불순물은 지니 지수라고도 하는데, 이는 무작위로 선택된 샘플이 샘플 세트에서 잘못 분류될 확률을 의미합니다. 지니 지수(지니 불순물) = 선택된 샘플의 확률 * 샘플이 잘못 분류될 확률 lt;ugt; ;/ugt;. 지니 지수가 작을수록 세트에서 선택된 샘플이 잘못 분류될 확률이 작아집니다. 즉, 세트의 순도가 높을수록 세트의 순수성이 낮아집니다.

샘플 세트의 지니 지수:

샘플 세트에는 m개의 카테고리가 있으며, 이는 번째 카테고리의 샘플 수를 나타냅니다. 지니 지수는 다음과 같습니다.

샘플 세트 S를 특징으로 나눈 후 특정 지니 지수를 기준으로:

?CART는 이진 트리입니다. 즉, 특정 특징을 사용하여 샘플 세트를 나누면 두 세트가 됩니다. a. 주어진 특성 값과 동일함. b. 주어진 특성 값과 동일하지 않은 샘플 세트. 본질적으로 이는 여러 값을 가진 기능을 이진 처리하는 것입니다.

위의 각 구분에 대해 특정 특성 값을 기준으로 샘플 세트를 두 개의 하위 세트로 나누는 순도를 계산할 수 있습니다.

따라서 여러 For 기능이 있는 샘플의 경우 2 이상의 값을 갖는 경우, 각 값을 구분점으로 하여 샘플 세트(특징의 가능한 값을 나타냄)를 나눈 후 하위 세트의 순도를 계산한 후 전체에서 지니 지수를 구해야 합니다. 가능한 분할. 이 분할의 분할 지점인 가장 작은 분할은 샘플 세트를 분할하기 위해 특징을 사용하는 최상의 분할 지점입니다.

참고자료:

의사결정트리 - 정보 획득의 이해, 정보 획득 비율, Geni 지수

머신러닝의 심층적인 이해 - 정보 엔트로피 )

p>

통계적 학습 방법(Li Hang)

?이해를 돕기 위해 다음 데이터 세트를 사용하여 세 가지 방법으로 분류합니다.

?구체적으로 분석 전 , 소득이 숫자형이라는 점을 고려하여 의사결정나무 알고리즘을 사용하려면 먼저 속성을 이산화해야 합니다.

?머신러닝 알고리즘 중 일부 분류 알고리즘(ID3, Apriori 등)에서는 데이터가 범주형 속성 형식이어야 하므로 분류 문제를 처리할 때 일부를 변환해야 하는 경우가 많습니다. 연속 속성을 범주형 속성으로 변환합니다. 일반적으로 연속형 속성의 이산화는 데이터 세트의 값 범위 내에 여러 개의 개별 구분점을 설정하고 값 범위를 여러 간격으로 나눈 다음 서로 다른 기호 또는 정수 값을 사용하여 각 하위 항목을 나타내는 방식으로 수행됩니다. 간격. 데이터 값. 따라서 이산화의 두 가지 핵심 문제는 범주 수를 결정하는 방법과 연속 속성을 이러한 범주 값에 매핑하는 방법입니다. 일반적으로 사용되는 이산화 방법에는 동일 폭 방법, 동일 빈도 방법 및 1차원 클러스터링 방법이 있습니다.

실제 사용에서는 Pandas의 cut() 함수를 사용하여 등폭 이산화를 달성하는 경우가 많습니다.

이산화 결과가 수동으로 계산된 결과와 동일한 것을 확인할 수 있습니다. lt; ugt; 동일 너비 방법은 이상치에 민감하며 속성 값을 다양한 간격에 고르게 분포하는 경향이 있어 일부 간격에서는 더 많은 데이터가 발생하고 일부 간격에서는 데이터가 줄어듭니다. 의사결정 모델의 확립을 활용하십시오. lt;/ugt;

간격을 나누기 위해 4개의 분위수를 사용합니다.

lt; 불균등한 데이터 분포는 각 간격이 동일한 수의 속성 값을 가져야 한다는 요구 사항을 충족하기 위해 동일한 데이터 값을 서로 다른 간격으로 나누는 것일 수 있습니다. lt;/ugt;

1차원 클러스터링 이산화 방법을 사용한 후의 데이터 세트는 다음과 같습니다.

이 예에서는 클러스터링 기반 이산화 방법을 사용하기로 선택한 후 획득된 데이터 세트는 지표 계산에 사용됩니다. 고객이 채무를 상환할 수 있는지 예측하기 위해 A(부동산 소유), B(결혼 여부), C(연간 소득) 등의 속성을 사용하여 데이터 세트를 나누고 최종적으로 의사결정 트리를 구축합니다.

미혼:

이혼:

기혼:

분명히 B 속성 값 '결혼'으로 나눈 자녀 데이터 세트 동일한 리프 노드에 속하므로 더 이상 분류할 수 없습니다.

다음으로 B 속성 값 'single'로 나눈 하위 데이터 세트에 대해 최적의 특징 선택을 수행합니다.

1) 데이터 세트의 전체 정보 엔트로피를 계산합니다. 4개의 데이터 중, 부채 상환 여부에 대한 '예' 데이터가 3개, '아니요' 데이터 1개가 있을 경우 전체 정보 엔트로피는 다음과 같습니다.

2) 속성 A(부동산 소유)의 경우, 해당 속성 값에는 '예'와 '아니오'의 두 가지 유형이 있습니다.

그 중 A가 '예'이면 부채 상환 가능 여부는 '예'이고, '아니요'이면 A가 '아니요'이면 부채 상환 가능 여부는 0이다. is 'yes' 2개가 있고, 'No'는 1개이면 속성 A의 정보 엔트로피는 다음과 같습니다.

3) 속성 B(결혼 여부)에 대해서는 결정되었으므로, 이 데이터 하위 집합의 정보 엔트로피는 0입니다.

4) C(연간 소득) 속성의 경우 해당 속성 값에는 '중간 입력'과 '저소득'이 포함됩니다. C가 '중소득'이라는 전제 하에 상환 가능 여부에 대한 답은 '예'이고, C가 '저소득'이라는 전제 하에 상환 가능 여부에 대한 답은 '0'이다. 상환 가능 여부는 '예'입니다. '아니오'는 2개입니다. 그러면 속성 C의 정보 엔트로피는 다음과 같습니다.

5) 마지막으로 두 속성의 정보 이득 값을 각각 계산합니다.

정보 이득 값 이는 데이터 하위 집합을 두 개의 속성으로 나눈 후 의사결정 트리의 순도가 높아진다는 의미이며, 이때 둘 중 하나를 리프 노드로 선택할 수 있습니다.

같은 방법으로 데이터 하위 집합에 대해 최적의 특징 선택을 수행한 결과 정보 엔트로피가 0인 것으로 나타났습니다.

최종 결정 트리가 컴파일되었습니다.