구현을 통한 이해: 의사 결정 트리

플라톤에 의해 재발행

팔로워 : 0

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

XGBoost, CatBoost 또는 LightGBM(심지어 오토 인코더!) 중요한 공통 성분에 의존: 의사 결정 트리!

의사 결정 트리를 이해하지 않고는 앞서 언급한 고급 배깅 또는 그래디언트 부스팅 알고리즘을 이해하는 것이 불가능합니다. 이는 모든 데이터 과학자에게 치욕입니다! 따라서 Python으로 구현하여 결정 트리의 내부 작동 방식을 이해해 보겠습니다.

이 기사에서는

의사 결정 트리가 데이터를 분할하는 이유와 방법,
정보 획득,
NumPy를 사용하여 Python에서 결정 트리를 구현하는 방법.

에서 코드를 찾을 수 있습니다. 내 Github.

예측을 하기 위해 결정 트리는 다음에 의존합니다. 파편 재귀 방식으로 데이터 세트를 더 작은 부분으로 나눕니다.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

위의 그림에서 분할의 한 예를 볼 수 있습니다. 원본 데이터 세트가 두 부분으로 분리됩니다. 다음 단계에서 이 두 부분이 다시 분할됩니다. 이것은 어떤 종류의 중지 기준이 충족될 때까지 계속됩니다. 예를 들어,

분할 결과 일부가 비어 있는 경우
특정 재귀 깊이에 도달한 경우
(이전 분할 후) 데이터 세트가 몇 개의 요소로만 구성되어 있으면 추가 분할이 필요하지 않습니다.

이러한 분할을 어떻게 찾을 수 있습니까? 그리고 우리는 왜 신경을 쓰나요? 알아 보자.

자극

해결하고 싶다고 가정해 봅시다. 진 분류 문제 우리가 지금 우리 자신을 창조하는 것:

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

XNUMX차원 데이터는 다음과 같습니다.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

약 75%의 보라색과 약 25%의 경우 노란색의 두 가지 다른 클래스가 있음을 알 수 있습니다. 이 데이터를 의사 결정 트리에 공급하면 분류기, 이 트리는 처음에 다음과 같은 생각을 가지고 있습니다.

“두 개의 서로 다른 레이블이 있는데, 저에게는 너무 지저분합니다. 데이터를 두 부분으로 분할하여 이 난장판을 정리하고 싶습니다. 이 부분은 이전의 완전한 데이터보다 깨끗해야 합니다.” — 의식을 얻은 나무

그래서 나무가 합니다.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

트리는 대략 다음을 따라 분할하기로 결정합니다. x-중심선. 이것은 데이터의 상단 부분이 이제 완벽하게 깨끗한, 당신이 단지 찾을 의미 단일 클래스 (이 경우 보라색) 있습니다.

그래도 바닥 부분은 지저분한, 어떤 의미에서 이전보다 훨씬 더 지저분합니다. 클래스 비율은 전체 데이터 세트에서 약 75:25였지만 이 더 작은 부분에서는 약 50:50이며, 이는 가능한 한 혼합되어 있습니다.

참고 : 여기서 그림에서 보라색과 노란색이 잘 구분되어 있는 것은 중요하지 않습니다. 그냥 그 다른 레이블의 원시 양 두 부품 수에서.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

그래도 이것은 트리의 첫 번째 단계로 충분하므로 계속 진행됩니다. 상단에 또 다른 분할이 생성되지는 않지만 황어 무리 더 이상 하단 부분에 또 다른 분할을 생성하여 정리할 수 있습니다.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

그리고 짜잔, 부품당 단일 색상(라벨)만 찾을 수 있으므로 세 개의 분리된 부품은 각각 완전히 깨끗합니다.

이제 정말 쉽게 예측할 수 있습니다. 새로운 데이터 포인트가 들어오면 세 부분 거짓말하고 해당 색상을 제공합니다. 이것은 각 부분이 황어 무리. 쉽죠?

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

좋아, 우리는 그것에 대해 이야기하고 있었다 황어 무리 및 지저분한 데이터이지만 지금까지 이러한 단어는 모호한 아이디어만을 나타냅니다. 무엇이든 구현하려면 다음을 정의하는 방법을 찾아야 합니다. 청결.

청결을 위한 조치

예를 들어 레이블이 있다고 가정해 보겠습니다.

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

직관적으로 y₁ 가장 깨끗한 라벨 세트이며, y² 그리고 y₃. 지금까지는 좋았지만 이 행동에 어떻게 숫자를 매길 수 있을까요? 가장 쉽게 떠오르는 것은 다음과 같습니다.

XNUMX의 수와 XNUMX의 수를 세어보세요. 절대 차이를 계산합니다. 더 좋게 만들려면 배열의 길이로 나누어 정규화하십시오.

예를 들어, y² 8개의 6과 2개의 XNUMX로 총 XNUMX개의 항목이 있습니다. 따라서 우리의 맞춤형 정의 청결 점수 |6 – 2| /8 = 0.5. 청결도 점수를 쉽게 계산할 수 있습니다. y₁ 및 y₃ 각각 1.0과 0.0입니다. 여기에서 일반 공식을 볼 수 있습니다.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

여기 ㄴ₀ 및 ₁ 는 각각 XNUMX과 XNUMX의 수입니다. n = n₀ + n₁ 배열의 길이이고 p₁ = n₁ / n 1 레이블의 점유율입니다.

이 공식의 문제는 특히 두 클래스의 경우에 맞게, 그러나 매우 자주 우리는 다중 클래스 분류에 관심이 있습니다. 꽤 잘 작동하는 한 가지 공식은 지니 불순물 측정:

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

또는 일반적인 경우:

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

그것은 scikit-learn이 잘 작동합니다. 기본 조치로 채택 의에 대한 DecisionTreeClassifier 클래스입니다.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

참고 : 지니 측정 지저분함 청결 대신. 예: 목록이 단일 클래스(=매우 깨끗한 데이터!)만 포함하는 경우 합계의 모든 용어는 1이므로 합계는 1입니다. 최악의 경우는 모든 클래스가 정확한 횟수로 나타나는 경우이며, 이 경우 Gini는 XNUMX–XNUMX/C 어디에 C 클래스의 수입니다.

이제 우리는 깨끗함/어지러움에 대한 척도를 가지고 있으므로 좋은 분할을 찾는 데 어떻게 사용할 수 있는지 살펴보겠습니다.

분할 찾기

우리가 선택하는 많은 분할이 있지만 어느 것이 좋은 분할입니까? Gini 불순도 측정과 함께 초기 데이터 세트를 다시 사용하겠습니다.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

지금은 점수를 계산하지 않겠지만 75%가 보라색이고 25%가 노란색이라고 가정해 보겠습니다. Gini의 정의를 사용하면 전체 데이터 세트의 불순물은 다음과 같습니다.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

데이터 세트를 다음과 같이 분할하면 x-축, 이전과 같이:

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

XNUMXD덴탈의 상단 부분의 지니 불순물은 0.0입니다. 그리고 밑부분

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

평균적으로 두 부분의 지니 불순도는 (0.0 + 0.5) / 2 = 0.25로 전체 데이터 세트의 이전 0.375보다 좋습니다. 우리는 또한 그것을 소위 용어로 표현할 수 있습니다. 정보 획득:

이 분할의 정보 이득은 0.375 – 0.25 = 0.125입니다.

그렇게 쉽습니다. 정보 획득이 높을수록(즉, 지니 불순도가 낮을수록) 더 좋습니다.

참고 : 똑같이 좋은 또 다른 초기 분할은 y축을 따라 있을 것입니다.

명심해야 할 중요한 점은 부품의 크기로 부품의 지니 불순물을 칭량. 예를 들어,

파트 1은 50개의 데이터 포인트로 구성되며 지니 불순도는 0.0이고
파트 2는 450개의 데이터 포인트로 구성되며 지니 불순도는 0.5입니다.

그러면 평균 지니 불순도는 (0.0 + 0.5) / 2 = 0.25가 아니라 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

좋아요, 어떻게 최고의 분할을 찾을 수 있을까요? 간단하지만 진지한 대답은 다음과 같습니다.

모든 분할을 시도하고 정보 획득이 가장 높은 분할을 선택하십시오. 기본적으로 무차별 대입 방식입니다.

더 정확히 말하면 표준 결정 트리는 다음을 사용합니다. 좌표축을 따라 분할, ie xᵢ = c 일부 기능에 대해 i 및 임계값 c. 즉

분할 데이터의 한 부분은 모든 데이터 포인트로 구성됩니다. x 과 xᵢc및
모든 포인트의 다른 부분 x 과 xᵢ ≥ c.

이러한 간단한 분할 규칙은 실제로 충분히 좋은 것으로 입증되었지만 물론 이 논리를 확장하여 다른 분할(예: 다음과 같은 대각선)을 생성할 수도 있습니다. xᵢ + 2xⱼ = 3예를 들어,).

좋아, 이것들은 우리가 지금 시작하는 데 필요한 모든 재료입니다!

이제 결정 트리를 구현할 것입니다. 노드로 구성되어 있으므로 Node 먼저 수업.

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

노드는 분할에 사용하는 기능을 알고 있습니다(feature) 및 분할 값(value). value 의사 결정 트리의 최종 예측을 위한 저장소로도 사용됩니다. 이진 트리를 만들 것이므로 각 노드는 왼쪽 및 오른쪽 자식을 알아야 합니다. left 및 right .

이제 실제 의사 결정 트리 구현을 수행해 보겠습니다. 나는 그것을 scikit-learn과 호환되도록 만들고 있으므로 다음의 일부 클래스를 사용합니다. sklearn.base . 그것에 익숙하지 않다면 내 기사를 확인하십시오. scikit-learn 호환 모델을 구축하는 방법.

구현하자!

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

그리고 그게 다야! 이제 scikit-learn에 대해 좋아하는 모든 것을 할 수 있습니다.

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

트리가 정규화되지 않았기 때문에 과대적합이 많으므로 완벽한 열차 점수입니다. 보이지 않는 데이터에서는 정확도가 더 나빠집니다. 우리는 또한 다음을 통해 나무가 어떻게 보이는지 확인할 수 있습니다.

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

그림으로 나타내면 다음과 같습니다.

구현을 통한 이해: 의사 결정 트리
작성자 별 이미지

이 기사에서는 의사 결정 트리가 어떻게 작동하는지 자세히 살펴보았습니다. 우리는 모호하지만 직관적인 아이디어로 시작하여 공식과 알고리즘으로 전환했습니다. 결국 처음부터 의사 결정 트리를 구현할 수 있었습니다.

그러나 주의 사항: 우리의 결정 트리는 아직 정규화할 수 없습니다. 일반적으로 다음과 같은 매개변수를 지정하고 싶습니다.

최대 깊이
잎 크기
최소한의 정보 획득

다른 많은 것들 중에서. 운 좋게도 이러한 것들은 구현하기가 그리 어렵지 않기 때문에 이것은 당신에게 완벽한 숙제입니다. 예를 들어 다음을 지정하는 경우 leaf_size=10 매개변수로 10개 이상의 샘플을 포함하는 노드는 더 이상 분할되지 않아야 합니다. 또한, 이 구현은 비효율적. 일반적으로 데이터 세트의 일부를 노드에 저장하지 않고 대신 인덱스만 저장하려고 합니다. 따라서 (잠재적으로 큰) 데이터 세트는 메모리에 한 번만 있습니다.

좋은 점은 이 의사 결정 트리 템플릿을 사용하여 지금 열광할 수 있다는 것입니다. 다음을 수행할 수 있습니다.