Decision Tree(결정 트리)

Decision tree
전통적으로 Decision Tree는 수동으로 생성되어 왔습니다.

의사결정 트리는 우연한 사건 결과, 자원 비용 효용을 포함하여 결정의 나무와 같은 모델 및 가능한 결과를 사용하는 의사결정 지원 도구이다.조건부 제어문만 포함하는 알고리즘을 표시하는 방법 중 하나입니다.

의사결정 트리는 운영 연구, 특히 의사결정 분석에서 목표에 도달할 가능성이 가장 높은 전략을 식별하기 위해 일반적으로 사용되지만 기계 학습에서도 널리 사용되는 도구이기도 합니다.

개요

Decision Tree는 각 내부 노드가 속성(예를 들어 코인 플립이 앞면이냐 뒷면이냐)에 대한 "테스트"를 나타내며, 각 분기는 테스트 결과를 나타내며, 각 리프 노드는 클래스 라벨(모든 속성을 계산한 후에 이루어지는 결정)을 나타내는 흐름도 같은 구조이다.루트에서 리프까지의 경로는 분류 규칙을 나타냅니다.

의사결정 분석에서 의사결정 나무와 밀접하게 관련된 영향도는 시각적이고 해석적인 의사결정 지원 도구로 사용되며, 여기에서 경쟁하는 대안의 기대치(또는 기대 효용)가 계산된다.

Decision Tree는 다음 3가지 유형의 [1]노드로 구성됩니다.

  1. 의사결정 노드– 일반적으로 정사각형으로 표시
  2. 찬스 노드– 일반적으로 원으로 표시됨
  3. 엔드 노드– 일반적으로 삼각형으로 표시

Decision Tree는 운영 조사 및 운영 관리일반적으로 사용됩니다.실제로 불완전한 지식 하에서 리콜 없이 온라인으로 결정을 내려야 하는 경우, 의사결정 트리는 최선의 선택 모델 또는 온라인 선택 모델 [citation needed]알고리즘으로서 확률 모델에 의해 병렬화되어야 한다.의사결정 트리의 또 다른 용도는 조건부 확률을 계산하기 위한 설명적 수단이다.

의사결정 트리, 영향도, 효용 기능 및 기타 의사결정 분석 도구와 방법은 경영학, 보건학 및 보건학 학교의 학부생에게 가르치고 있으며 운영 연구 또는 경영 과학 방법의 예입니다.

의사결정 트리 구성 요소

의사결정 트리 요소

Decision-Tree-Elements.png

왼쪽에서 오른쪽으로 그려진 Decision Tree에는 버스트노드(스플리팅 패스)만 있고 싱크노드(컨버전스 패스)는 없습니다.따라서, 수동으로 사용하면, 그것들은 매우 커질 수 있고 손으로 완전히 그리는 것이 종종 어렵다.지금까지는 Decision Tree를 수동으로 작성했습니다(예외의 예에서 알 수 있듯이).다만, 전문 소프트웨어가 채용되고 있는 경우가 증가하고 있습니다.

결정 규칙

결정 트리는 결정 [2]규칙으로 선형화할 수 있으며, 여기서 결과는 리프 노드의 내용이며 경로에 따른 조건은 if 절에서 결합을 형성합니다.일반적으로 규칙은 다음과 같은 형식을 가집니다.

condition1condition2condition3의 경우 결과입니다.

결정 규칙은 오른쪽에 있는 대상 변수와의 연관 규칙을 구성하여 생성할 수 있습니다.시간적 또는 인과적 [3]관계를 나타낼 수도 있습니다.

흐름도 기호를 사용한 의사결정 트리

일반적으로 Decision Tree는 많은 사람이 읽고 이해하기 쉽기 때문에 흐름도 기호를 사용하여 그려집니다.아래에 표시된 트리의 "진행" 계산에 개념적인 오류가 있습니다. 이 오류는 법적 소송에서 부여된 "비용"의 계산과 관련이 있습니다.

DecisionCalcs.jpg

분석 예

분석에서는 의사결정자의 선호(예: 회사의) 또는 효용 기능을 고려할 수 있습니다. 예를 들어 다음과 같습니다.

RiskPrefSensitivity2Threshold.png

이 상황의 기본적인 해석은 회사가 현실적인 리스크 선호 계수(위험 회피 범위에서는 40만달러 이상)에 따른 B의 리스크와 보상을 선호한다는 것이다.

운영 연구 코스에서 흔히 사용되는 또 다른 예는 해변의 구조대원의 분포입니다("Life's a Beach"[4] 예).이 예에서는 각 해변에 배치될 인명구조원이 있는 두 개의 해변을 설명합니다.최대 예산 B는 2개의 해변(총)에 배분할 수 있으며, 한계 수익률 표를 사용하여 분석가는 각 해변에 몇 명의 구조대원을 할당할지 결정할 수 있습니다.

각 해변의 구조대원 해수욕장 #1 총체적 익사 방지 익사 방지 종합, 해변 #2
1 3 1
2 0 4

이 예에서는 Decision Tree를 그려서 해변 #1의 수익 감소 원칙을 설명할 수 있습니다.

해변의 Decision Tree

Decision Tree는 구조대원을 순차적으로 분배할 때, 1번 해변에 첫 번째 구조대원을 배치하는 것이 1명의 구조대원을 위한 예산만 있다면 최적임을 보여줍니다.하지만 경비원 2명을 위한 예산이 있다면, 2번 해변에 둘 다 배치하면 더 많은 익사 사고를 막을 수 있을 것이다.

구조대원

영향도

의사결정 트리의 많은 정보는 영향 다이어그램으로 보다 간결하게 표현될 수 있으며, 사건 간의 문제와 관계에 주의를 집중할 수 있다.

왼쪽의 직사각형은 결정을 나타내고, 타원형은 행동을 나타내며, 다이아몬드는 결과를 나타냅니다.

연관 규칙 유도

의사결정 나무는 경험적 데이터에서 유도 규칙의 생성 모델로 볼 수도 있다.그런 다음 최적의 의사결정 트리는 레벨 수(또는 "질문")[5]를 최소화하면서 대부분의 데이터를 설명하는 트리로 정의됩니다.이러한 최적의 트리를 생성하기 위한 알고리즘은 ID3/4/5,[6] CLS, Assistant, CART 등 여러 가지가 고안되어 있습니다.

장점과 단점

의사결정 지원 도구 중 의사결정 트리(및 영향도)에는 몇 가지 장점이 있습니다.의사결정 트리:

  • 이해하기 쉽고 해석하기 쉽다.간단한 설명을 통해 의사결정 트리 모델을 이해할 수 있습니다.
  • 하드 데이터가 거의 없어도 가치가 있습니다.상황(대안, 가능성 및 비용)과 결과에 대한 선호도를 설명하는 전문가에 기초하여 중요한 통찰력을 생성할 수 있습니다.
  • 다양한 시나리오에서 최악의 값, 최선의 값 및 예상되는 값을 결정하는 데 도움이 됩니다.
  • 화이트 박스 모델을 사용합니다.주어진 결과가 모델에 의해 제공되는 경우.
  • 다른 의사결정 기법과 조합할 수 있습니다.
  • 둘 이상의 의사결정자의 행동을 고려할 수 있다.

Decision Tree의 단점:

  • 즉, 데이터의 작은 변화가 최적의 의사결정 트리의 구조에 큰 변화를 가져올 수 있습니다.
  • 그것들은 종종 비교적 부정확하다.다른 많은 예측 변수들은 유사한 데이터를 사용할 때 더 나은 성능을 발휘합니다.이는 단일 의사결정 트리를 랜덤 의사결정 트리로 대체하여 해결할 수 있지만 랜덤 포레스트는 단일 의사결정 트리만큼 해석하기가 쉽지 않다.
  • 수준 수가 다른 범주형 변수를 포함하는 데이터의 경우 의사결정 트리의 정보 게인은 수준[7]더 높은 속성으로 치우칩니다.
  • 계산은 특히 많은 값이 불확실하거나 많은 결과가 연결되어 있는 경우 매우 복잡해질 수 있다.

Decision Tree 최적화

의사결정 트리 분류기의 정확도를 개선할 때 몇 가지 사항을 고려해야 한다.다음은 생성된 의사결정 트리 모델이 올바른 결정 또는 분류를 수행하는지 확인할 때 고려해야 할 몇 가지 최적화입니다.이러한 사항만 고려하는 것이 아니라 일부만 고려해야 합니다.

트리의 수준 수 증가

Decision Tree의 정확도는 Decision Tree의 깊이에 따라 달라질 수 있습니다.대부분의 경우, 나무의 잎은 순수[8]노드입니다.노드가 순수하다는 것은 해당 노드의 모든 데이터가 [9]단일 클래스에 속한다는 것을 의미합니다.예를 들어 데이터 세트의 클래스가 암과 비암인 경우 리프 노드의 모든 샘플 데이터가 암 또는 비암 중 하나의 클래스에만 속할 경우 리프 노드는 순수하다고 간주됩니다.Decision Tree를 최적화할 때는 트리가 깊을수록 좋은 것은 아닙니다.트리가 깊을수록 런타임에 부정적인 영향을 미칠 수 있습니다.특정 분류 알고리즘을 사용하는 경우 트리가 깊어질수록 이 분류 알고리즘의 실행 시간이 상당히 느려질 수 있습니다.또한 Decision Tree를 구축하는 실제 알고리즘은 트리가 깊어질수록 속도가 현저하게 느려질 수 있습니다.사용되는 트리 구축 알고리즘이 순수 노드를 분할할 경우 트리 분류기의 전체 정확도가 저하될 수 있습니다.트리의 깊이가 깊어지면 일반적으로 정확도가 저하될 수 있으므로 Decision Tree의 깊이를 수정하여 최적의 결과를 얻을 수 있는 깊이를 선택하는 것이 매우 중요합니다.아래 관찰 사항을 요약하면 숫자 D를 트리의 깊이로 정의합니다.

숫자 D를 늘리면 얻을 수 있는 이점:

  • 의사결정 트리 분류 모델의 정확도가 높아집니다.

D 증가 시 발생할 수 있는 단점

  • 런타임 문제
  • 일반적으로 정확도 저하
  • 깊이 들어가면서 노드가 완전히 분할되면 문제가 발생할 수 있습니다.

D를 변경할 때 분류 결과의 차이를 테스트할 수 있는 능력은 필수적입니다.의사결정 트리 모델의 정확성과 신뢰성에 영향을 줄 수 있는 변수를 쉽게 변경하고 테스트할 수 있어야 합니다.

노드 분할 기능 선택

사용되는 노드 분할 함수는 Decision Tree의 정확도 향상에 영향을 미칠 수 있습니다.예를 들어, 정보 게인 함수를 사용하면 phi 함수를 사용하는 것보다 더 나은 결과를 얻을 수 있습니다.phi 함수는 Decision Tree의 노드에서 분할된 후보의 "선도" 척도로 알려져 있습니다.정보 게인 함수는 "엔트로피 감소"의 척도로 알려져 있습니다.다음에서는 두 가지 의사결정 트리를 구축합니다.노드를 분할하기 위해 phi 함수를 사용하여 하나의 Decision Tree를 구축하고 노드를 분할하기 위해 정보 게인 함수를 사용하여 하나의 Decision Tree를 구축합니다.

정보 게인과 피 함수의 주요 장점과 단점

  • Information Gain의 주요 단점 중 하나는 트리의 다음 노드로 선택된 기능이 [10]더 고유한 값을 갖는 경향이 있다는 것입니다.
  • 정보 게인의 장점은 트리의 루트에 가까운 가장 영향력 있는 기능을 선택하는 경향이 있다는 것입니다.이는 일부 기능의 관련성을 판단하기 위한 매우 좋은 방법입니다.
  • 또한 phi 함수는 "선도"를 기준으로 일부 기능의 관련성을 결정하는 데에도 적합합니다.

정보 게인 함수 공식입니다.공식은 정보 게인이 의사결정 트리의 노드의 엔트로피에서 의사결정 트리의 노드 t에서 분할된 후보의 엔트로피를 뺀 함수임을 나타냅니다.

이것이 파이 함수 공식입니다.phi 함수는 선택한 피쳐가 균질 분할을 생성하고 각 분할에 동일한 수의 샘플이 있는 방식으로 샘플을 분할할 때 최대화됩니다.

구축 중인 의사결정 트리의 깊이인 D를 3(D = 3)으로 설정합니다.또한 다음과 같은 암 및 비암 검체의 데이터 세트와 검체가 가지고 있거나 가지고 있지 않은 돌연변이 특징을 가지고 있습니다.샘플에 피쳐 변환이 있는 경우 샘플은 해당 변환에 대해 양수이며 1로 표시됩니다.샘플에 피쳐 변환이 없는 경우 샘플은 해당 변환에 대해 음이 되며 0으로 표시됩니다.

요약하자면, C는 Cancer, NC는 Non-Cancer를 나타냅니다.문자 M은 변환의 약자로 샘플에 특정 변환이 있는 경우 테이블에는 1로 표시되고 그렇지 않은 경우 0으로 표시됩니다.

샘플 데이터
M1 M2 M3 M4 M5
C1 0 1 0 1 1
NC1 0 0 0 0 0
NC2 0 0 1 1 0
NC3 0 0 0 0 0
C2 1 1 1 1 1
NC4 0 0 0 1 0

이제 공식을 사용하여 데이터 집합의 각 M에 대한 phi 함수 값과 정보 게인 값을 계산할 수 있습니다.모든 값이 계산되면 트리를 생성할 수 있습니다.가장 먼저 수행해야 할 작업은 루트 노드를 선택하는 것입니다.정보 게인과 phi 함수에서 우리는 최적의 분할이 정보 게인을 위해 가장 높은 값을 생성하는 돌연변이 또는 phi 함수라고 생각한다.이제 M1의 phi 함수 값이 가장 높고 M4의 정보 게인 값이 가장 높다고 가정합니다.M1 돌연변이는 phi 함수 트리의 루트가 되고 M4는 정보 게인 트리의 루트가 됩니다.아래 루트 노드를 관찰할 수 있습니다.

Figure 1: The left node is the root node of the tree we are building using the phi function to split the nodes. The right node is the root node of the tree we are building using information gain to split the nodes.

루트 노드를 선택하면 샘플이 루트 노드 변환에 대해 양수인지 음수인지에 따라 샘플을 2개의 그룹으로 분할할 수 있습니다.그룹은 그룹 A 및 그룹 B라고 불립니다.예를 들어 M1을 사용하여 루트 노드의 샘플을 분할하면 NC2 및 C2 샘플이 그룹 A에 있고 나머지 샘플 NC4, NC3, NC1, C1은 그룹 B에 있습니다.

루트 노드에 대해 선택된 변환을 무시하고 정보 게인 또는 phi 함수가 가장 높은 다음 최적의 기능을 Decision Tree의 왼쪽 또는 오른쪽 자식 노드에 배치합니다.깊이 트리 = 3에 대해 루트 노드와 두 개의 하위 노드를 선택하면 잎을 추가할 수 있습니다.잎은 표본에 있거나 없는 돌연변이를 기반으로 모델이 생성한 최종 분류 결정을 나타냅니다.왼쪽 트리는 노드 분할을 위해 정보 게인을 사용하여 얻은 결정 트리이며 오른쪽 트리는 노드를 분할하기 위해 phi 함수를 사용하여 얻은 것입니다.

The resulting tree from using information gain to split the nodes.
Phi Function Tree.jpg

이제 두 나무의 분류 결과가 혼동 행렬을 사용하여 제공된다고 가정합니다.

정보 게인 혼란 매트릭스:

예측:c 예측: NC
실제: C 1 1
실제: NC 0 4

Phi 함수 혼란 행렬:

예측:c 예측: NC
실제: C 2 0
실제: NC 1 3

정확도를 계산할 때 phi 함수를 사용할 때 정보 게인을 사용하는 트리의 결과는 동일합니다.정보 게인을 사용하여 모델을 기준으로 샘플을 분류하면 참 긍정 1개, 거짓 긍정 1개, 거짓 부정 0개, 참 부정 4개를 얻을 수 있습니다.phi 함수를 사용하는 모델의 경우 거짓 긍정 0개, 거짓 부정 1개, 참 부정 3개 등 두 개의 참 긍정 값을 얻을 수 있습니다.다음 단계에서는 아래의 "Decision Tree 평가" 섹션에서 설명하는 몇 가지 주요 메트릭을 사용하여 Decision Tree의 효과를 평가합니다.다음에 설명하는 메트릭은 Decision Tree를 최적화할 때 수행할 다음 단계를 결정하는 데 도움이 됩니다.

기타 테크닉

위의 정보는 Decision Tree 구축 및 최적화에 도움이 되지 않습니다.우리가 구축한 의사결정 트리 분류 모델을 개선하기 위한 많은 기법이 있다.기술 중 하나는 부트스트랩된 데이터셋에서 의사결정 트리 모델을 만드는 것입니다.부트스트랩된 데이터셋은 모델이 테스트된 것과 동일한 데이터로 의사결정 트리 모델을 구축할 때 발생하는 편견을 제거하는 데 도움이 됩니다.랜덤 포레스트의 성능을 활용하는 능력도 구축 중인 모델의 전반적인 정확도를 크게 향상시키는 데 도움이 됩니다.이 방법은 많은 의사 결정 트리에서 많은 의사 결정을 생성하고 각 의사 결정 트리에서 표를 집계하여 최종 분류합니다.많은 기법이 있지만 주요 목적은 다양한 방법으로 Decision Tree 모델을 구축하여 최고의 퍼포먼스 수준에 도달하도록 하는 것입니다.

Decision Tree 평가

의사결정 트리를 평가하는 데 사용되는 측정값을 아는 것이 중요합니다.사용되는 주요 메트릭은 정확도, 감도, 특수성, 정밀도, 미스 레이트, 오검출 레이트 및 오검출 레이트입니다.이러한 모든 측정은 의사결정 트리 분류 모델을 통해 샘플 세트를 실행할 때 얻은 참 긍정, 거짓 긍정, 참 부정거짓 부정의 수에서 파생됩니다.또, 이러한 결과를 표시하기 위해서 혼돈 행렬을 작성할 수도 있다.이러한 모든 주요 지표는 의사결정 트리를 기반으로 구축된 분류 모델의 장점과 단점에 대해 서로 다른 점을 보여 줍니다.예를 들어, 높은 특이성과 함께 낮은 민감도는 의사결정 트리에서 구축된 분류 모델이 비암 샘플에 대한 암 샘플을 잘 식별하지 못한다는 것을 나타낼 수 있다.

아래 혼돈 매트릭스를 봅시다.혼돈 매트릭스는 구축된 의사결정 트리 모델 분류기가 11개의 참 긍정, 1개의 거짓 긍정, 45개의 거짓 부정, 105개의 참 음성을 제공했음을 보여준다.

예측:c 예측: NC
실제: C 11 45
실제: NC 1 105

이제 정밀도, 감도, 특이도, 정밀도, 미스율, 오검출률, 오검출률, 오검출률의 값을 계산합니다.

정확도:

감도(TPR - True Positive Rate):[11]

특이성(TNR - True Negative Rate):

정밀도(PPV - 양의 예측 값):

미스 레이트(FNR - False Negative Rate):

FDR(False Discovery Rate):

잘못된 누락률(FOR):

주요 지표가 계산되면 구축된 Decision Tree 모델의 성능에 대해 몇 가지 초기 결론을 내릴 수 있습니다.저희가 계산한 정확도는 71.60%였습니다.정확도 값은 시작하기에 좋지만, 전체적인 성능을 유지하면서 최대한 정확한 모델을 만들고 싶습니다.민감도 값이 19.64%라는 것은 실제로 게자리 양성 반응이 나온 모든 사람 중 양성 반응이 나왔다는 것을 의미합니다.99.06%의 특이성 값을 보면 암의 음성이었던 모든 검체 중 실제로 음성이었다는 것을 알 수 있습니다.민감성과 특이성에 관해서라면, 두 가치 사이의 균형을 유지하는 것이 중요합니다. 그래서 만약 우리가 [12]이로운 것으로 판명될 민감성을 증가시키기 위해 우리의 특이성을 줄일 수 있다면.이것들은 의사결정 트리 모델을 평가하고 다음 반복을 개선하기 위해 이러한 값과 그 뒤에 있는 의미를 사용하는 방법에 대한 몇 가지 예시일 뿐이다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Kamiński, B.; Jakubczyk, M.; Szufel, P. (2017). "A framework for sensitivity analysis of decision trees". Central European Journal of Operations Research. 26 (1): 135–159. doi:10.1007/s10100-017-0479-6. PMC 5767274. PMID 29375266.
  2. ^ Quinlan, J. R. (1987). "Simplifying decision trees". International Journal of Man-Machine Studies. 27 (3): 221–234. CiteSeerX 10.1.1.18.4267. doi:10.1016/S0020-7373(87)80053-6.
  3. ^ K. Karimi와 H.J. Hamilton(2011), "시간적 의사결정 규칙의 생성과 해석", 컴퓨터 정보 시스템과 산업 관리 응용 분야 국제 저널, 제3권
  4. ^ Wagner, Harvey M. (1 September 1975). Principles of Operations Research: With Applications to Managerial Decisions (2nd ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 9780137095926.
  5. ^ R. Quinlan, "효율적인 분류 절차 학습", 기계학습: 인공지능 접근법, Michalski, Carbonell & Mitchell(ed.), Morgan Kaufmann, 1983년 페이지 463-482.doi: 10.1007/978-3-662-12-45-15405
  6. ^ 우트고프, P.E. (1989)의사결정 트리의 증분 유도.머신러닝, 4(2), 161~186.doi:10.1023/A:1022699900025
  7. ^ Deng,H.; Runger, G.; Tuv, E. (2011). Bias of importance measures for multi-valued attributes and solutions. Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN).
  8. ^ Larose, Chantal, Daniel (2014). Discovering Knowledge in Data. Hoboken, NJ: John Wiley & Sons. p. 167. ISBN 9780470908747.
  9. ^ Plapinger, Thomas (29 July 2017). "What is a Decision Tree?". Towards Data Science. Archived from the original on 10 December 2021. Retrieved 5 December 2021.
  10. ^ Tao, Christopher (6 September 2020). "Do Not Use Decision Tree Like Thus". Towards Data Science. Archived from the original on 10 December 2021. Retrieved 10 December 2021.
  11. ^ "False Positive Rate Split Glossary". Split. Retrieved 10 December 2021.
  12. ^ "Sensitivity vs Specificity". Analysis & Separations from Technology Networks. Retrieved 10 December 2021.

외부 링크