Decision Tree - 의사결정나무에 대한 기초 질문들

1. What is the approximate depth of a Decision Tree trained (without restrictions) on a training set with 1 million instances?

The depth of a well-balanced binary tree containing m leaves is equal to log2(m)3, rounded up. A binary Decision Tree (one that makes only binary decisions, as is the case of all trees in Scikit-Learn) will end up more or less well balanced at the end of training, with one leaf per training instance if it is trained without restrictions. Thus, if the training set contains one million instances, the Decision Tree will have a depth of log2(106) ≈ 20 (actually a bit more since the tree will generally not be perfectly well balanced).

 

m 개의 잎을 포함하는 균형 잡힌 이진 트리의 깊이는 log2 (m)과 같으며 반올림됩니다. 바이너리 결정 트리 (Scikit-Learn의 모든 트리의 경우와 같이 바이너리 결정 만하는 바이너리 결정 트리)는 교육 종료시 다소 균형이 잘 잡히게됩니다. 제한없이 교육을받는 경우 트레이닝 인스턴스 당 하나의 리프가됩니다. . 따라서 훈련 세트에 백만 인스턴스가 포함되어있는 경우 의사 결정 트리의 깊이는 log2 (106) ≈ 20입니다 (실제로 트리가 일반적으로 완벽하게 균형을 이루지 못하기 때문에 실제로는 조금 더 많음). (그냥 로그 2 해주면 되는듯)

*여기서 log2는 밑이 2라는 것을 뜻함. 어떻게 쓰는지 모르겠다 컴퓨터로..

 

2. Is a node’s Gini impurity generally lower or greater than its parent’s? Is it generally lower/greater, or always lower/greater?

일반적으로 노드의 Gini 불순도가 부모도다 높나 낮나? 일반적으로 낮/높은지 항상 낮/높은지

노드의 지니 불순물은 일반적으로 부모보다 낮습니다. 이것은 CART 교육 알고리즘의 비용으로 보장됩니다. 함수는 각 노드를 자식 Gini 불순물의 가중치 합을 최소화하는 방식으로 분할합니다.

그러나 한 자식이 다른 자식(의 지니 불순도)보다 작으면, 그 부모보다 지니 불순도가 높을 수 있다 만약 이 증가분이 다른 자식의 지니 불순물 감소보다 크다면)

 

그러나 한 자식의 불순이 다른 자식보다 작으면, 다른 아이의 불순물 감소로 인해 지니 불순물이 부모보다 더 클수도 있다.

 

예를 들어, 클래스 A에 네 개의 인스턴스가 있고, 클래스 B에는 한 개의 인스턴스가 있다고 가정해 보자. 지니 불순도는 1-(1/5)^2 – (4/5)^2 = 0.32 이다. 이 때 데이터 셋은 일차원이고 모든 인스턴스들이 A B A A A 순서라고 해보자. 너는 알고리즘이 두번째 인스턴스 이후 이 노드를 분리할 것임을 알 수 있다(그냥 클래스 나누는것) – 자식 노드 A, B를 만들면서.  그리고 다른 자식 노드의 인스턴스는 A, A, A이다.

첫번째 자식의 불순도는 1 – (1/2)^2 – (1/2)^2 = 0.5이다 = 부모보다 높음.

 

이 것은 다른 노두가 순수하다는 것에 대한 보상이므로, 전체 지니 불순도는 2/5 * 0.5 + 3/5 * 0 = 0.2이다. (두번째 노드는 모두가 A이므로 순수 = 불순도는 0) à 이 때 부모의 지니 불순도보다 낮다 

*즉 보통 자식노드가 부모노드보다 지니불순도가 낮지만 항상 낮은건 아니다.

 

3. If a Decision Tree is overfitting the training set, is it a good idea to try decreasing max_depth?

If a Decision Tree is overfitting the training set, it may be a good idea to decrease max_depth, since this will constrain the model, regularizing it. // 모델의 깊이가 낮아질수록 모델을 제약하고 regularizing 하는 것.

 

 

4. If a Decision Tree is underfitting the training set, is it a good idea to try scaling the input features? 만약 underfit하다면 scaling 해주는 것이 좋냐?

Decision Trees don’t care whether or not the training data is scaled or centered; that’s one of the nice things about them. So if a Decision Tree underfits the training set, scaling the input features will just be a waste of time.

해봤자 소용없음 

 

5. If it takes one hour to train a Decision Tree on a training set containing 1 million instances, roughly how much time will it take to train another Decision Tree on a training set containing 10 million instances?

1 백만 개의 인스턴스가 포함 된 교육 세트에서 의사 결정 트리를 교육하는 데 1 시간이 소요되는 경우 1 천만 개의 인스턴스가 포함 된 교육 세트에서 다른 의사 결정 트리를 교육하는 데 대략 어느 정도의 시간이 걸립니까?

 

The computational complexity of training a Decision Tree is O(n × m log(m)). So if you multiply the training set size by 10, the training time will be multiplied by K = (n × 10m × log(10m)) / (n × m × log(m)) = 10 × log(10m) / log(m). If m = 106, then K ≈ 11.7, so you can expect the training time to be roughly 11.7 hours.

 

의사 결정 트리 트레이닝의 계산 복잡도는 O (n × m log (m))입니다. 따라서 훈련 세트 크기에 10을 곱하면 훈련 시간에 K = (n × 10m × log (10m)) / (n × m × log (m)) = 10 × log (10m) / log (m). m = 10^6이면 K ≈ 11.7이므로 약 11.7 시간의 교육 시간을 기대할 수 있습니다.

 

6. If your training set contains 100,000 instances, will setting presort=True speed up training?

너의 교육 세트에 100,000 개의 인스턴스가 포함되어 있다면 presort = True로 설정하여 교육을 가속화해야 하는가?

 

Presorting the training set speeds up training only if the dataset is smaller than a few thousand instances. If it contains 100,000 instances, setting presort=True will considerably slow down training.

교육 세트를 미리 할당하면 데이터 세트가 수천 개보다 작은 경우에만 교육이 가속화됩니다. 인스턴스가 100,000 개 포함되어 있으면 presort = True로 설정하면 교육 속도가 상당히 느려집니다.