4. 데이터 마이닝 - Classification

1. Classification Techniques

 ▪ Decision Tree based Methods(의사결정 트리)

 ▪ Rule-based Methods(규칙 기반 기법)

 ▪ Memory based reasoning

 ▪ Neural Networks

 ▪ Naïve Bayes and Bayesian Belief Networks

 ▪ Support Vector Machines 

2. Decision Tree based Methods

 1. Decision Tree를 생성하는 알고리즘으로는 Hunt's Algorithm, CART 등

 2. 헌트 알고리즘 구조

     ▪ 특정 attribute의 value 값에 대해 특정 값에 대해 class attribute 값이 같다면 자식 노드에 해당 class attribute 값이 들어간다.
     ▪ 값이 다를 시 다른 조건을 자식 노드로 가지고 ①으로 돌아간다.

 

 3. 속성 시험 조건을 어떻게 지정할 것인가 고려해야한다.

▪ 속성 테스트 조건을 명시하는 방법

▪ 최선의 분할을 결정하는 방법 

▪ 속성의 종류(명목형, 서열형, 연속형)에 따라 다르다 

▪ 명목형, 서열형 속성에 대한 분할 : 다중분할은 경우의 수만큼 분할을 하고, 이진분할은 2개로 나누되 여러 경우가 조건으로 들어갈 수있다.

▪ 연속형 속성은 단순 크다 작다중 하나로 2개의 가지를 가질 수 있지만, 구간을 두어 복수의 가지를 가질 수 있다.

 4. 최선의 분할을 어떻게 할것이가?

▪ 분할이란 어떤 attribute를 이용하여 Decision tree의 node를 만드는것

▪ 분할을 하였을 시 비교하는 대상이 반반 나뉘는 것보다 1개, 9개 나뉘는게 순도가 더 높다 또는 불순도가 더 낮다.

 5. 불순도 척도

 6. 불순도 척도 : GINI

 

7. GINI 기반 분할

8. 불순도 척도 : Entropy 

9. 불순도 척도 : Missclassfication

10. Missclassfication 기반 분할

    

 

11. Example

11. 불순도 척도 비교

12. 분할을 언제 멈출 것인가?

▪ 노드에 속한 모든 레코드들이 동일한(유사한) 클래스를 갖는 경우, 더 이상 분할하지 않고 멈춤

▪ 노드의 레코드 수가 임계치 이하로 떨어지는 경우, 분할을 멈춤

▪ 과잉 접학을 막기 위한 사전 혹은 사후 가지치기로 멈춤

13. 의사 결정 트리 기반 분류 장점

▪ 알수 없는 레코드 분류시 매우 빠름

▪ 구축 비용이 싸다.

▪ 작은 트리는 분석하기 쉽다

▪ 정확도가 다른 학습 기술과 비슷하다.

13. Decision tree의 주요 이슈

▪ Overfitting(과잉 접합) : 과하게 자세하게 형성되서 실제 분류되지 않은 데이터에 대해서 오류가 커짐, 또는 노이즈와 데이터 부족으로도 발생할 수 있다.

▪ Missing Values(누락값) : 누락값이 있는 경우 부정확한 트리가 구축됨

▪ Costs of Classification (분류 비용) : 데이터 많을 수록 시간 오래 걸리며 정확도 높은 의사 결정 트리를 생성할려면 많이 비용이 요구됨

3. 일반화 오류에 대한 추정

 1. Re-substitution estimate : 훈련 데이터가 전체 데이터를 잘 대변한다고 생각하고 가장 오류가 작은 모델을 선택한다.

 2. Model Complexity : 모델 복잡도를 조정하여 일반화 오류를 줄인다.

▪ 오컴의 면도날 : 같은 일반화 오류 가질때 2개 모델이 있을떄 단순한 모델이 더 좋다. 

 3. Pessimistic Estimate(비관적 오류 추정) : 일반화 오류를 훈련 오류와 모델 복잡도에 대한 penalty 값의 합이다. 

 4. 최소 서술길이 원리 : 비용이 싼게 좋다.

 5. Statistical Bounds(통계적 한계) 추정하기 : 훈련 오류의 상한으로 일반화 오류 추정 

 6. Using Validation Set(검증 집합) 이용하기 : 훈려 집합 나누어 하나는 검증 집합으로 씀

3. Overfitting 줄이는 법

 1. 사전 가지치기, 조기 정지 규칙

▪ leaf 개수가 임계 수치를 넘으면 멈춤

▪ 분기 된 leaf가 독립적이면 멈춤

▪ 확장시 분순도가 올라가면 멈춤

2. 사후 가지치기

▪ 의사결정 트리를 최대까지 성장시키고 하나씩 정리해감

▪ 완전히 성장시키기위해 비용낭비

3. 가지 치는 법

▪ Post-Pruning : 부모 오류가 자식 하나의 오류보다 작을 경우 자식을 모두 죽인다.

4. Missing Attribute Values 다루는 법

 Missing Attribute Values에 어떤 데이터를 넣느냐에 따라 다른 불순도가 나온다.

 1. 직접 넣어보고 계산해본다.

 2. 다른 애들의 전체에 대해 확률적으로 집어넣는다.

5. Data Fragmentation

 1. Data Fragmentation : 말단 노드로 갈수록 노드당 record 개수가 작어져 잘라야함

 2. Search Strategy : 최적의 트리를 찾기엔 너무 어렵다. 최소 2의 지수승 만큼 증가하기 때문에..

3. Expressiveness : Continuous variable에 대해 트리 만들기 어렵다.

 4. Oblique Decision Trees : linear regression이 더 좋을 때가 있다.

 

 4. Decision Boundary : 시각화 했을때 신기하다.

 5. Tree Replication : 트리를 만들다 보면 똑같은 형태가 반복된다.