Decision Tree란 무엇인가요?

아래 다이어그램에서 볼 수 있듯이 Decision Tree는 들어오는 가지가 없는 루트 노드로 시작합니다. 그런 다음 루트 노드에서 나가는 가지는 의사 결정 노드라고도 하는 내부 노드로 피드됩니다. 사용 가능한 기능에 따라 두 노드 유형 모두 평가를 수행하여 리프 노드 또는 터미널 노드로 표시되는 동종 하위 집합을 형성합니다. 리프 노드는 데이터 세트 내에서 가능한 모든 결과를 나타냅니다.

예를 들어, 서핑을 해야 하는지 여부를 평가하려고 한다고 가정하면 다음과 같은 결정 규칙을 사용하여 선택할 수 있습니다.

이러한 유형의 순서도 구조는 의사 결정을 이해하기 쉽게 표현하여 조직 내 여러 그룹이 의사 결정이 내려진 이유를 더 잘 이해할 수 있게 해줍니다.

Decision Tree 학습은 트리 내에서 최적의 분할 지점을 식별하기 위해 탐욕스러운 검색을 수행하여 분할 및 정복 전략을 사용합니다. 그런 다음 이 분할 프로세스는 모든 레코드 또는 대다수의 레코드가 특정 클래스 라벨로 분류될 때까지 하향식 재귀 방식으로 반복됩니다.

모든 데이터 요소가 동종 세트로 분류될지 여부는 Decision Tree의 복잡성에 따라 크게 달라집니다. 트리가 작을수록 순수한 리프 노드(예: 단일 클래스의 데이터 포인트)를 더 쉽게 얻을 수 있습니다. 그러나 트리의 크기가 커지면 이러한 순수성을 유지하기가 점점 더 어려워지고 일반적으로 주어진 하위 트리에 속하는 데이터가 너무 적어지게 됩니다. 이런 현상이 발생하는 것을 데이터 단편화라고 하며, 종종 과적합으로 이어질 수 있습니다.

결과적으로 Decision Tree는 작은 트리를 선호하는데, 이는 "개체를 필요 이상으로 늘려서는 안 된다"는 Occam’s Razor의 간결성 원칙과도 일치합니다. 다르게 말하면, Decision Tree는 가장 간단한 설명이 가장 좋은 경우가 많기 때문에 필요한 경우에만 복잡성을 추가해야 합니다. 복잡성을 줄이고 과적합을 방지하기 위해 일반적으로 가지치기를 사용하는데, 이는 중요도가 낮은 항목에서 분할되는 가지를 제거하는 프로세스입니다. 그런 다음 교차 검증 프로세스를 통해 모델의 적합성을 평가할 수 있습니다.

Decision Tree가 정확도를 유지할 수 있는 또 다른 방법은 랜덤 포레스트 알고리즘을 통해 앙상블을 형성하는 것입니다. 이 분류기는 특히 개별 트리가 서로 연관성이 없을 때 더 정확한 결과를 예측합니다.

1960년대에 심리학에서 인간의 학습을 모델링하기 위해 개발된 Hunt 알고리즘은 다음과 같이 널리 사용되는 많은 Decision Tree 알고리즘의 기초를 형성합니다.

- ID3: Ross Quinlan은 "반복적 이분법 3"의 줄임말인 ID3를 개발한 공로를 인정받았습니다. 이 알고리즘은 엔트로피와 정보 획득을 메트릭으로 활용하여 후보 분할을 평가합니다. 1986년 이 알고리즘에 대한 Quinlan의 연구 중 일부는 여기에서 찾을 수 있습니다.

- C4.5: 이 알고리즘은 Quinlan이 개발한 ID3의 후기 반복으로 간주됩니다. 이 알고리즘은 정보 획득 또는 획득 비율을 사용하여 Decision Tree 내에서 분할 지점을 평가할 수 있습니다.

- CART: CART라는 용어는 '분류 및 회귀 트리'의 약자로, Leo Breiman이 소개한 용어입니다. 이 알고리즘은 일반적으로 지니 불순도를 사용하여 분할할 이상적인 속성을 식별합니다. 지니 불순도는 무작위로 선택한 속성이 얼마나 자주 잘못 분류되는지 측정합니다. 지니 불순도를 사용하여 평가할 때는 값이 낮을수록 더 이상적입니다.

각 노드에서 최상의 속성을 선택하는 방법에는 여러 가지가 있지만, 정보 획득과 지니 불순도라는 두 가지 방법이 Decision Tree 모델에서 널리 사용되는 분할 기준으로 사용됩니다. 각 테스트 조건의 품질과 샘플을 클래스로 얼마나 잘 분류할 수 있는지 평가하는 데 도움이 됩니다.

엔트로피를 먼저 논의하지 않고는 정보 획득을 설명하기 어렵습니다. 엔트로피는 샘플 값의 불순도를 측정하는 정보 이론에서 파생된 개념입니다. 이는 다음 공식으로 정의됩니다.

• S는 엔트로피가 계산되는 데이터 세트를 나타냅니다. 
• c는 세트 S의 클래스를 나타냅니다.
• p(c)는 세트 S의 총 데이터 포인트 수에 대한 클래스 c에 속하는 데이터 포인트의 비율을 나타냅니다.

엔트로피 값은 0과 1 사이일 수 있습니다. 데이터 세트 S의 모든 샘플이 하나의 클래스에 속하면 엔트로피는 0이 됩니다. 샘플의 절반이 한 클래스로 분류되고 나머지 절반이 다른 클래스로 분류되면 엔트로피는 1로 가장 높습니다. 분할할 최상의 항목을 선택하고 최적의 Decision Tree를 찾으려면 엔트로피가 가장 적은 속성을 사용해야 합니다.

정보 획득은 주어진 속성에 대한 분할 전과 후의 엔트로피 차이를 나타냅니다. 정보 획득이 가장 높은 특성은 대상 분류에 따라 학습 데이터를 분류하는 데 가장 적합한 작업을 수행하므로 최상의 분할을 생성합니다. 정보 획득은 일반적으로 다음 공식으로 표현됩니다.

여기서

• a는 특정 속성 또는 클래스 라벨을 나타냅니다.
• Entropy(S)는 데이터 세트 S의 엔트로피입니다.
• |Sv|/|S|는 데이터 세트 S의 값 수에 대한 S_v의 값의 비율을 나타냅니다.

이러한 개념을 보다 명확히 이해할 수 있도록 한 가지 예를 살펴보겠습니다. 다음과 같은 임의의 데이터 세트가 있다고 가정해 보겠습니다.

이 데이터 세트의 경우 엔트로피는 0.94입니다. 이는 '테니스 플레이'가 '예'인 날의 비율인 9/14와 '테니스 플레이'가 '아니요'인 날의 비율인 5/14를 구하여 계산할 수 있습니다. 그런 다음 이 값을 위의 엔트로피 공식에 대입하면 됩니다.

엔트로피(테니스) = -(9/14) log2(9/14) – (5/14) log2 (5/14) = 0.94

그런 다음 각 속성에 대한 정보 획득을 개별적으로 계산할 수 있습니다. 예를 들어, '습도' 속성에 대한 정보 획득은 다음과 같습니다.

획득(테니스, 습도) = (0.94)-(7/14)*(0.985) – (7/14)*(0.592) = 0.151

요약하면 다음과 같습니다.

- 7/14는 전체 습도 값 수에 대한 습도가 '높음'인 값의 비율을 나타냅니다. 이 경우 습도가 '높음'인 값의 수는 습도가 '보통'인 값의 수와 동일합니다.

- 0.985는 습도 = '높음'일 때의 엔트로피입니다.

- 0.59는 습도 = '보통'일 때의 엔트로피입니다.

그런 다음, 위 표의 각 속성에 대해 정보 획득에 대한 계산을 반복하고 정보 획득이 가장 높은 속성을 Decision Tree의 첫 번째 분할 지점으로 선택합니다. 이 경우 Outlook에서 가장 높은 정보 획득을 얻을 수 있습니다. 여기서부터 각 하위 트리에 대해 이 과정을 반복합니다.

지니 불순도는 데이터 세트의 클래스 분포에 따라 라벨이 지정된 경우 데이터 세트의 임의 데이터 포인트를 잘못 분류할 확률입니다. 엔트로피와 마찬가지로, 세트 S가 순수하면(예: 한 클래스에 속함) 불순도는 0입니다. 이는 다음 공식으로 표시됩니다.

Decision Tree는 다양한 사용 사례에서 사용될 수 있지만, 일반적으로 다른 알고리즘이 Decision Tree 알고리즘보다 성능이 뛰어납니다. 즉, Decision Tree는 데이터 마이닝 및 지식 검색 작업에 특히 유용합니다. 아래에서 Decision Tree 활용의 주요 이점과 과제를 자세히 살펴보겠습니다.

• 쉽게 이해할 수 있음: 부울 논리와 Decision Tree의 시각적 표현은 Decision Tree를 더 쉽게 이해하고 사용할 수 있도록 합니다. Decision Tree의 계층적 특성은 어떤 속성이 가장 중요한지 쉽게 파악할 수 있게 해주는데, 이는 신경망과 같은 다른 알고리즘에서는 항상 명확하게 드러나지 않는 사항입니다.
  
  
• 데이터 준비가 거의 또는 전혀 필요하지 않음: Decision Tree에는 다른 분류기보다 더 유연하게 사용할 수 있도록 해주는 여러 가지 특성이 있습니다. 다양한 데이터 유형을 처리할 수 있습니다(예: 불연속 또는 연속 값). 연속 값은 임계값을 사용하여 범주형 값으로 변환할 수 있습니다. 또한 Naïve Bayes와 같은 다른 분류기에서는 문제가 될 수 있는 누락된 값이 있는 값도 처리할 수 있습니다.
  
  
• 더 유연함: Decision Tree는 분류 및 회귀 작업 모두에 활용할 수 있으므로 다른 알고리즘보다 더 유연합니다. 또한 속성 간의 기본 관계에 둔감합니다. 즉, 두 변수의 상관 관계가 높은 경우 알고리즘은 분할할 기능 중 하나만 선택합니다.

• 과적합이 발생하기 쉬움: 복잡한 Decision Tree는 과적합하기 쉬우며 새 데이터에 잘 일반화되지 않습니다. 이 시나리오는 사전 가지치기 또는 사후 가지치기 프로세스를 통해 피할 수 있습니다. 사전 가지치기는 데이터가 충분하지 않은 경우 트리의 성장을 멈추고, 사후 가지치기는 트리를 구성한 후 데이터가 충분하지 않은 하위 트리를 제거합니다.
  
  
• 높은 분산 추정치: 데이터 내의 작은 변화는 매우 다른 Decision Tree를 생성할 수 있습니다. 배깅 또는 추정치의 평균화는 Decision Tree의 변동을 줄이는 방법이 될 수 있습니다. 그러나 이 접근 방식은 상관관계가 높은 예측 변수로 이어질 수 있다는 점에서 한계가 있습니다.
  
  
• 더 비싼 비용: Decision Tree는 구축 과정에서 탐욕스러운 검색 방식을 취하기 때문에 다른 알고리즘에 비해 훈련 비용이 더 많이 들 수 있습니다.