2022/07/01~2022/07/08

[givitallugot]

07/08(금) 10시

[njs03332]

6.5 계산 복잡도

• 예측
  • 루트 노드에서부터 리프 노드까지 탐색
  • 일반적으로 결정 트리는 거의 균형을 이루고 있음
  • O(log₂(m)) 개의 노드를 탐색, 각 노드는 하나의 특성값만 확인
  • 예측에 필요한 전체 복잡도 = O(log₂(m))
• 훈련
  • 훈련 알고리즘은 각 노드에서 모든 훈련 샘플의 모든 특성을 비교함 -> 훈련 복잡도는 O(n*mlog₂m))
  • 훈련 세트가 작을 경우 사이킷런은 미리 데이터를 정렬하여 훈련 속도를 높일 수 있음 (presort=True, 사이킷런 0.24 버전에서는 삭제됨)
  • 훈련 세트가 큰 경우에는 속도가 많이 느려짐

[givitallugot]

6.6 지니 불순도 또는 엔트로피?

• 지니 불순도(DecisionTreeClassifier criterion="gini"), 엔트로피 불순도(DecisionTreeClassifier criterion="entropy") 사용 가능

• 엔트로피는 분자의 무질서함을 측정하는 것 = 어떤 세트가 한 클래스 샘플만 담고 있다면 엔트로피는 0, 여러 클래스 샘플이 담겨있다면 더욱 다양하므로 >0일 것

• i번째 노드의 엔트로피 식 (k개의 클래스)

  

• 지니 불순도

  

• 지니 불순도와 엔트로피 불순도 사용 시 큰 차이 없음

  • 그러나 지니 불순도 계산이 조금 더 빠름
  • 그리고 지니 불순도가 가장 빈도 높은 클래스 한쪽 가지로 고립시키는 경향, 엔트로피 불순도는 조금 더 균형 잡힌 트리 만드는 편

[danbi5228]

6.4 CART 훈련 알고리즘

• 사이킷런은 결정 트리를 훈련시키기 위해 CART 알고리즘 사용
• CART : Classification And Regression Tree
  • 가장 널리 사용되는 Decision Tree 알고리즘
  • 분류와 회귀 모두에서 사용할 수 있음
• 먼저 훈련 세트를 하나의 특성 k의 임곗값 t_k를 사용해 두 개의 subset으로 나눈다.
• 그 다음, (크기에 따른 가중치가 적용된) 가장 순수한(gini = 0에 가까운) subset으로 나눌 수 있는 (k, t_k) 짝을 찾는다.
  • 
• CART 알고리즘이 subset을 나누는 과정은 (max_depth 매개변수로 정의된) 최대 깊이가 되면 중지하거나, 불순도를 줄이는 분할을 찾을 수 없을 때 멈추게 된다.
• CART 알고리즘은 Greedy 알고리즘. 최적 트리를 찾는 것은 NP-Complete 문제 ; 납득할 만한 좋은 솔루션으로 만족해야 함