Classification and Prediction(2)

7. Overfitting (과적합) 과 Tree Pruning (가지 치기)

1) Overfitting : 유도된 Decision tree는 training data로 인해 과적합의 문제를 포함할 수 있음

training data에 노이즈나 이상치(outlier)가 있다면 tree에도 반영되어 분기 branch가 지나치게 많아짐

        ->이는 아직 학습하지 못한 sample에 대해 낮은 정확성을 가져옴

 

2) Pruning : Overfitting 문제를 해결하기 위한 방법으로, 가장 신뢰성이 떨어지는 분기 branch를 제거

- Prepruning : Tree를 유도하는 과정에서 잠시 중단하여 가지치기를 진행

        - 특정 노드의 분기가 Tree의 적합도를 일정 threshold (한도) 이하로 내린다면 분기하지 않음

        - 적정 수준의 threshold를 선택하는 것이 어려움

        (threshold가 너무 높다면 분류가 단순해지고, 반대로 너무 낮다면 쓸모 없어짐)

 

- Postpruning : 완성된 Tree를 바탕으로 branch를 제거

        - 제거할 가지를 결정하는 데에 training data와는 다른 별개의 data set을 사용

        - 제거 대상의 하위 Tree는 majority voting을 통해서 하나의 리프노드로 대체

        - Prepruning에 비해 더 많은 계산을 요구하지만 더 신뢰성 있는 Tree를 만들 수 있음

 

3) Subtree Repetition(반복) 과 Replication(중첩)

- Repetition : 한 분기 안에서 같은 속성을 반복적으로 테스트하는 현상

A1 속성에 대한 Repetition

 

- Replication : Tree안에 동일한 subtree가 두 개 이상 존재하는 현상

 

-> Tree의 Repetition과 Replication은 Decision tree의 정확성과 이해 가능성을 해칠 수 있으므로 적절한 pruning을 통해 제거하거나 단변수 분기(여러 attribute를 사용하여 분기)로 방지할 수 있음

 

 

8. 기본 Decision tree 유도의 강화

- 수치형(연속형) attribute의 허용 : 수치형 attribute 값을 이산 구간으로 나누어 동적으로 새로운 범주형(이산형) attribute를 정의

 

- 결측치의 처리 : 가장 빈도가 큰 값이나 가능한 값들에 확률을 부여하여 결측치를 채움

 

- Attribute Construction (속성 구축) : 희소하게 존재하는 값을 가진 attribute들을 기반으로 새로운 attribute를 생성

        -> Tree의 단편화 (fragmentation), 반복 (repetition), 중첩 (replication)을 감소시킴

 

 

9. 거대 데이터베이스에서의 Classification

- Scalability (확장성) : 수백만개의 example과 수백개의 attribute를 가진 거대한 data set에도 적절한 속도로 분류가 가능한 것

 

- Data mining에서 decision tree가 주로 이용되는 이유

• 다른 classification 방식에 비해 빠른 학습 속도 + 다른 방식과 유사한 정확도
• Interpretability (이해 가능성) : classification rule이 간단하고 이해하기에 쉬움
• 데이터베이스에 접근하는데에 SQL query를 사용할 수 있음

 

- Scalable (확장성 있는) Decision Tree의 유도 방법

• SLIQ (EDBT'96, Mehta et al.) : 각 attribute에 index를 부여하고 class의 list와 현재 사용하는 attribute의 list만 memory에 상주시키는 방식
• SPRINT(VLDB'96, J. Shafer et al.) : Attribute list를 자료구조로 생성
• PUBLIC(VLDB'98, Rastogi & Shim) : Tree의 분기와 pruning을 병합 (Prepruning)
• RainForest(VLDB'98, Gehrke, Ramakrishnan & Ganti) : AVC-list (attribute, value, class label)의 자료구조 생성
• BOAT(PODS'99, Gehrke, Ganti, Ramakrishnan & Loh) : sample의 생성에 있어 bootstrapping을 이용

 

10. Model Evaluation (모델 평가) 

- 모델의 평가는 test data set을 통해 이루어짐       cf) 모델의 구축 - training data set

 

10-1. Model Evaluation - Classifier (분류자 모델 평가)

1) Confusion Matrix (contingency table, cross tab) (진리표)

(target attribute에 yes/no, benign/malignant 등의 두가지 class만 있을 때)

 

- True Positive (TP) : 정확하게 예측한 긍정 tuple의 수

- True Negative (TN) : 정확하게 예측한 부정 tuple의 수

- False Positive (FP) : 본래 부정 tuple이지만 긍정 tuple로 잘못 예측한 tuple의 수

- False Negative (FN) : 본래 긍정 tuple이지만 부정 tuple로 잘못 예측한 tuple의 수

 

- 위의 네가지를 이용하여 모델을 평가하는 다양한 수치를 측정

 

2) 측정법

- Accuracy (정확성, Recognition rate) : Classifier가 적절하게 분류한 test set tuple의 비율

Accuracy = (TP + TN) / (P + N)

 

- Recall (재현율, sensitivity, true positive rate) : 긍정 tuple을 정확하게 구분한 비율

Recall = TP / P

 

- Precision (정밀도) : 분류의 정확성 정도

Precision = TP / (TP + FP)

 

- F-score : Precision과 Recall의 가중치 조화 평균

        - 위 공식에서 특히 β = 1인 공식이 모델 평가에서 흔히 사용됨

 

10-2. Model Evaluation - Predictor (예측자 모델 평가)

- 수치형 Attribute를 예측하는 predictor model의 경우 예측된 값이 실제 값에서 얼마나 멀리 떨어져 있는지를 측정하여 평가

 

- Loss function (손실 함수) : 실제 값 x와 이에 대한 예측 값 x'의 차를 계산

• Absolute error : |x - x'|
• Squared error : (x - x')^2

 

- Test error : test set에서의 평균 차를 계산

        - ex) Mean Absolute Error (MAE), Mean Square Error (MSE), Relative Absolute Error (RAE), Relative Square Error (RSE)...

 

        - square error의 경우 이상치의 영향을 확대하므로 주로 Root Mean/Relative Square Error를 사용