Classification and Prediction(1)

1. Classification vs Prediction

1) Classification (분류)

- 범주형 (discrete, nominal) attribute의 class label 예측

 

- training set을 이용하여 data를 분류하는 model을 구축, 이를 통해 새로운 데이터를 분류

 

- classifying attribute : model을 구축하는데 사용되는 attribute

 

- target dimension(attribute) : 새로운 데이터의 분류 예측 대상이 되는 attribute

 

-> training set의 class label(예측의 대상이되는 attribute의 값)을 이용하여 model을 만들고, 이를 이용해 새로운 데이터의 target dimension을 class label에 따라 분류함

 

2) Prediction (예측)

- 수치형 (continuous) attribute의 예측

 

- 값을 예측하는 model을 구축하고, 이를 통해 새로운 데이터의 결측치를 예측

 

3) 주요 응용 분야

- 신용카드 발급, 이용 승인

- 타겟 마케팅

- 의학적 진단

- 이상 검출을 통한 사기 적발

 

2. Classification의 2단계 절차

1)  Model Construction (모델 구축) : 미리 결정된 class label 집합을 분류하는 모델

- 모든 데이터(tuple)은 class label attribute의 미리 정해진 class들 중 하나에 속한다고 가정

 

- training set : 모델 구축에 사용되는 tuple 집합

 

- 모델은 classification 규칙이나, decision tree (의사결정 나무), 수학 공식 등의 형태로 나타남

 

2) Model Usage (모델 사용) : 새로운 object나 값이 알려지지 않은 데이터의 분류에 모델을 사용

- 모델의 정확도 측정

        - class label이 알려진 test set을 이용해 모델을 평가

        - test set에서 제대로 분류한 sample의 비율이 정확도가 됨

        - Overfitting이 일어나지 않도록 test set은 training set과 독립적이어야 함

 

- 모델의 정확도가 충분하다면 class label을 모르는 data tuple의 분류에 사용

3. Supervised Learning vs. Unsupervised Learning

1) Supervised Learning (지도 학습)

- 이미 알려진 사례를 바탕으로 일반화된 모델을 만들어 의사결정 process를 자동화

 

- 사용자는 알고리즘에 input (data samples)과 기대되는 output(class labels)를 제공함 (지도)

        -> 알고리즘은 주어진 입력에서 원하는 출력을 만드는 방법을 찾음 (학습)

 

- 학습된 알고리즘은 사람의 도움 없이 새로운 입력에 대해 적절한 출력을 만들어냄

 

- 알고리즘의 평가가 쉬움

 

- ex) 스팸 메일 분류: input = 이메일 data, output = 각 메일의 스팸 여부

        -> 학습된 알고리즘은 특정 이메일이 스팸 메일인지 아닌지를 예측

 

- 손 글씨 판별, 의료 영상에서의 종양 판단, 신용카드 부정 사용 탐지 등에 활용

 

2) Unsupervised Learning (비지도 학습)

-  Supervised learning과는 다르게 알고리즘에 input은 주어지지만 output은 주어지지 않음

 

- 알고리즘의 평가가 어려움 <- output의 정답이 존재하지 않음

 

- ex)

• Blog 글의 주제 구분 : 텍스트 데이터 요약, 핵심 주제 찾기 (어떤 주제인지, 주제가 얼마나 많은지 미리 알수 없음)
• 유사한 성향의 고객 grouping (어떤 그룹이 존재하는지, 얼마나 존재하는지 미리 알 수 없음)
• 비정상적인 웹사이트 접근 탐지 : 비정상 접근의 패턴이 알려져있지 않음

 

3) Supervised learning vs. Unsupervised learning

Supervised learning	Unsupervised learning
분류 (Classification)	군집화 (Clustering)
training data에는 class label이 주어짐	training data의 class label을 알 수 없음
training data를 기반으로 새로운 데이터를 분류	데이터에서 class나 cluster를 찾기 위해 measurement, observation 집합 등이 주어짐

 

4. Classification과 관련된 Issue

1) Data Preparation (데이터 준비)

- Data Cleaning (데이터 정제) : 노이즈를 제거하고 결측치를 채우는 과정이 필요

 

- Relevance Analysis (상관 분석) -> Feature Selection (속성 선택) : 불필요하거나 중복되는 attribute 제거

 

- Data Transformation (데이터 변환) : 데이터의 일반화/정규화

 

2) Evaluation Classification Methods (분류 방법의 평가) 

- Accuracy (정확도)

        - Classifier accuracy : class label 예측의 정확도

        - Predictor accuracy : attribute의 값 예측의 정확도

 

- Speed (속도)

        - traning time : 모델을 구축(학습)하는데에 소모되는 시간

        - Classification/prediction time : 모델을 사용하는데에 소모되는 시간

 

-Robustness (강인성) : 이상치나 노이즈에도 영향을 받지 않음

 

- Scalability (확장성) : 거대한, 디스크에 존재하는 데이터베이스에서의 효율성

 

- Interpretability (해석력) :  학습으로 만들어진 모델을 사람이 이해할 수 있는 정도

 

- decision tree size, compactness of classification rule....

 

5. Decision Tree (의사결정 나무) 유도 알고리즘

- Greedy Algorithm : 전체 데이터에 대한 최적해가 아닌 알고리즘의 각 단계에서 최적해를 찾음

 

- 트리의 Root 노드부터 아래로 내려가며 같은 방식을 재귀적으로 반복하는 하향식 (top-down), recursive의 분할 정복 방식 (divide and conquer)

 

- 트리는 Root 노드와 Intermediate 노드, leaf 노드로 구성

 

- Root 노드와 Intermediate 노드는 각 단계에서의 최적 classifying attribute를 가지고 있으며, leaf 노드는 class label을 가짐

 

- 각 노드는 branch로 연결되며 이 branch는 classifying attribute를 그 값에 따라 분기하는 역할

 

- Classifying attribute들은 범주형이며, 수치형일 경우 미리 이산화(discretization)의 과정이 필요

 

- 기본 알고리즘 과정

        - 모든 training tuple은 트리의 root 노드에서 시작

        - 각 노드에서 최적의 attribute를 선택하여 이에 따라 training tuple을 분류함

        - 최적의 attribute 선택에는 휴리스틱 방법이나 통계 측정 방법이 사용

                - ex) information gain, gain ratio, gini index.....

        - 분기된 노드에서 다시 attribute를 정하고 attribute의 값에 따라 tuple을 분류하는 과정을 반복

        - 종료조건

                1. 한 노드에 존재하는 모든 tuple이 같은 class label에 속함

                2. 더 이상 분기할 attribute가 존재하지 않음

                        -> majority voting으로 더 많은 tuple이 속하는 class label을 leaf node로 정함

                3. 더 이상 분기할 tuple이 존재하지 않음

 

※ 수치형 (연속형, Continuous-value) attribute의 이산화 방법

- 수치형 Attribute A에 대해 가장 적절한 split point (구분 값)을 결정

• 먼저 A의 값을 오름차순으로 정렬
• 일반적으로, 인접한 값들 사이의 중앙값을 구분 값으로 정함 ex) a와 b의 값이 있을 때, (a+b)/2
• 가장 구별성이 강한, 또는 비슷한 값끼리 cluster되도록하는 지점을 split point로 결정

- Split point를 결정했다면 (split point가 하나일때)

• D1 : A에서의 값인 a가 a <= splint point인 tuple들의 집합
• D2 : A에서의 값인 a가 a > splint point인 tuple들의 집합

 

 

6. Attribute Selection Measure (속성 선택 방법)

1) Information gain (정보 소득)

- target dimension의 class label로 데이터를 분류하기 위한 기대 정보량(또는 entropy)을 이용

 

- Attribute를 사용하지 않은 초기 기대 정보량 Info(D)

(이때, p(i)는 전체 tuple인 D에서 임의의 tuple이 class label C(i)에 속할 확률인 |C(i)|/|D|,

m은 class label C의 개수)

- Attribute A를 바탕으로 하여 분류할때의 요구 정보량 InfoA(D)

(이때, v는 A의 서로 다른 값의 개수, I(D(j))는 A의 값이 a(j)일 때의 기대 정보량)

- Attribute A에서의 정보 소득 Gain(A)

- 모든 Classifying attribute에 대해 Gain(A)를 구하여 그 값이 가장 높은 attribute를 해당 노드에서의 최적 spliting attribute로 설정

        - Gain(A)가 가장 높은 속성은 tuple을 분류하는데 필요한 정보가 가장 적은 속성이다.

          (임의성이 가장 적고, 결과 파티션의 불순도(class label이 서로 다름)이 가장 낮음)

 

2) Gain Ratio (소득률)

- Information Gain 수치는 많은 종류의 값을 가진 attribute가 더 크게 나타나도록 치우쳐져있음

 

- 이로 인한 문제를 해결하기 위해 C4.5에서는 Information Gain을 정규화하는 방식인 Gain Ratio를 사용

 

- 모든 Classifying attribute에 대해 GainRatio(A)를 구하여 그 값이 가장 높은 attribute를 해당 노드에서의 최적 spliting attribute로 설정

 

3) Gini Index (지니 계수)

- 데이터셋 T가 n개의 class를 가질 때 지니 계수 gini(D) 

- 이때, pj는 T에서 class j의 상대 빈도

 

- 만약 데이터셋 T가 특정 attribute A로 두 부분집합 T1과 T2로 나뉘어진다면 지니 계수 giniA(T)

 

- 따라서, attribute A를 classifying attribute로 했을 때의 불순도의 감소는

 

- 모든 Classifying attribute에 대해 gini(A)를 구하여 그 값이 가장 낮은 attribute를 (또는 불순도의 감소 정도가 가장 큰 attribute를) 해당 노드에서의 최적 spliting attribute로 설정

 

4) 속성 선택 방법 간 비교

- Information Gain, Gain Ratio, Gini index 모두 일반적으로 좋은 결과를 도출해냄, 그러나

        ● Information Gain : 다양한 값을 가진 attribute에 편중됨

 

        ● Gain Ratio : tuple을 분리할 때 한쪽으로 치우치는 경향이 있음

                => 노드의 한 부분이 다른 부분들에 비해 작은 skewed tree가 만들어질 가능성

 

        ● Gini Index

                - 다양한 값을 가진 attribute에 편중됨

                - class의 수가 많다면 사용이 어려움

                - partition의 크기가 같고 purity(나누어진 partition의 class가 모두 같은 정도)가 비숫할 때

                          좋은 성능을 냄

 

5) 기타 속성 선택 방법

- CHAID : X^2(chi-square)을 이용한 방식

 

- C-SEP : 특정 상황에서는 Information Gain이나 Gini Index보다 뛰어난 성능을 보임

 

- G-statistics : chi-square를 이용한 방식과 비슷한 근사치를 가짐

 

- MDL(Minimal Description Length) 원리에 기반한 측정 ex) 가장 간단한 해결책을 선호

        - 다양한 값을 가진 attribute에 편중됨

 

- Multivariate splits: 하나의 attribute가 아닌 여러 attribute를 이용하여 tuple을 분리

        - ex) CART : attribute들의 선형 결합(linear combination)을 이용

 

-> 이러한 방식은 모두 대체로 좋은 결과를 만들어내며 한 방식이 다른 것에 비해 특별한 우위를 차지하는 것은 아님.