Classification (1/2)
ITE4005_DS > (6-7) 6
[Data Science]6 Classification PART 1
목차
(part1)
- What is classification?
- Issues regarding classification
- Classification by decision tree induction
- Random Forest
(part2)
Rule-based classificationAssociative classificationLazy learners (or learning from your neighbors)Accuracy and error measuresEnsemble methodsSummary
What is classification?
- classification
: categorical class label 예측
(당연한 이야기지만) 모델을 training 데이터로 construct 후, 새로운 데이터로 classification
이때 train data에는 label 있고, test에는 class label 없음.
- regression
: 연속적인 값 다룸 (수업에서 많이 다루지X)
Classification
모델 만들기
- 목표: train data를 사용하여 predetermined class를 describe하는 것
- Training data
- 모델 train때 사용
-
<feat-1, feat-2, …., feat-n, class label> (feature / attribute) 형태.
각 데이터마다 n개의 feature value와 class label (class label 꼭 있어야 한다)
- training 후에 model은 각 data를 어떻게 map 할지 배움
- Model
- <feat-1, feat-2, …., feat-n> 형태의 각 데이터를 특정 → class label로 map.
- classification rules, decision trees, networks, mathematical formula등으로 표현됨
- 프로그래머의 선택
모델 사용
- 목표: 미래의 unknown samples를 모델을 사용해 분류(classify)하는 것
Supervised vs. Unsupervised Learning
- Supervised learning(classification):
- class label 같은 것에 의해 supervised
- training set에 기반하여 새로운 데이터 classified.
- Unsupervised learning(clustering):
- training data의 class label은 unknown
- class label은 없지만, 대신 data가 어떻게 생겼는지에 관심.
- (더 fundamental(기초적인) 문제)
→ 둘이 aim 하는게 다르다.
Issues in Classification:
1. Data Preparation
- Data cleaning
- 깨끗한 데이터 준비해야함. 지저분한 데이터로는 유용한 결과 얻기 힘들 것임
- Relevance analysis (feature selection)
- 매우 많은 feature 중에 관련 있는 것 찾기
- (attributes = feature = dimension)
- Remove the irrelevant (index, ID, etc…) or redundant attributes (year-salary and monthly salary, etc…)
- Data transformation
- Generalize and/or normalize data
2. Evaluating Points
- Accuracy (정확도)
- # of correctly classified data / # of entire test data
- Speed
- time to construct the model (training time)
- time to use the model (testing time)
- Robustness: handling noise, error, outliers and missing values
-
- Scalability
- handling a growing size of data
- Interpretability
- understanding and insight provided by the model
Decision Tree
: 특정 조건에 기초한 decision에 가능한 모든 솔루션을 그래픽으로 표현한 것
![1][1]
- 각 branch node는 alternative사이의 choice를 나타내고,
- 각 leaf node는 decision을 나타낸다.
Decision tree induction = decision tree 만드는 법
- Algorithm over view
- greedy 알고리즘:
- 미래 고려 없이 그 시점에 best choice 하고 넘어가는 greedy 알고리즘
- top-down, recursive, dive-and-conquer manner
- 모든 training example은 root에서 시작(이 시점에는 root밖에 없는 상황. 아무런 node없음), 이후 선택된 feature에 의해 partition되는 과정이 재귀적으로 일어남
- (feature 선택에 관한건 다음 슬라이드에서)
- greedy 알고리즘:
- Stop 하는 조건 (이 재귀적인 프로세스로 진행하는 알고리즘이)
- 첫번째 조건
- 그 브랜치에 분류된 training 데이터들이 모두다 같은 클래스로 분류 된 경우 → leaf되는 거임
위 예시에서 마지막 노드 생각하면 됨. 맨 좌측 노드의 경우 학생이 아닌 경우 라벨이 모두 no인 상황이었을 수 있음
- 두 번째 조건
- 분류 한 노드에 다른 label 섞여 있지만 더 이상 분류 할 feature가 없을 때 → 이 경우 중지하고 majority voting
- 첫번째 조건
![2][2]
- Algorithms
- ID3 : entropy
- C4.5 : Gain Ratio
- CART : Gini index
위 세 가지가 Decision tree를 만드는 알고리즘들
위 알고리즘들은 같은 컨셉에 기반하고 있음(greedy, top-down, recursive, dive-and-conquer manner…) = Share common idea
매우 유사한 아이디어를 가지고 있고, 유일한 차이는 어떻게 feature를 선택하는지.
하지만 그 시점에서 어떤 기준이 가장 좋은지는 같은 아이디어에 기반했음에도 매우 다름.
- Common idea
- 모든 feature A에 대해 얼마나 heterogeneous(이질적) 이도록 분류가 되었는지
- heterogeneous : feature A로 분류를 한 후 얼마나 다른 클래스의 데이터가 섞여있는지 측정함. 수치가 낮다면, 안 섞여 있는 것. Pure하게 나뉠수록 수치 낮게 나옴(우리가 원하는것 = not heterogeneous = homogeneous) The lower the better
- 모든 feature A에 대해 얼마나 heterogeneous(이질적) 이도록 분류가 되었는지
- Feature types
- simplicity를 위해 모든 feature는 categorical 하다.
- 만약 연속적인 값이라면 미리 discretize
Heterogeneous vs Homogeneous
Heterogeneous : 이질적인
Homogeneous : 동종
Feature Selection
- greedy 하게 진행하므로 매번 “어떤 feature가 best?” 라는 질문을 계속 하게 된다.
- more homogeneous
- 유사한 키워드: entropy, impurity, heterogeneity
![3][3]
좌측의 경우가 더 좋은 경우
ID3 (Iterative Dichotomiser 3)
: Entropy에 기반한 Information Gain이 사용됨.
Entropy
: 확률 분포에서 정보의 양을 나타내는 수치 표현.
![4][4]
중앙에 물리적으로 분리가 되어있는 상황이라면, (물리적 boundary)
우측은 매우 messy(=mixed) → entropy $\uparrow$.
만약 well partition 되어있다면 엔트로피는 $\downarrow$.
-
Given data D로 엔트로피를 수학적으로 계산하는 법
![5][5]
pi는 class i에 속하는 랜덤 example의 확률
예를 들어 위 이미지에서 i=1이면 class red일 확률, i=2이면 흰색일 확률 등이 될 수 있음
좌측 이미지의 경우 위가 Red zone이라면 red 일 확률이 매우 높게 나오고,
zone이 바뀌어서 위가 White zone이라면 red일 확률이 매우 낮아진다.
하지만 우측처럼 섞인 경우는 바뀌기 전 후 모두 0.5정도의 확률을 보일것임.
→ 확률이 0 또는 1에 가깝다는 건 Data partition이 잘 되어있다는 것
→ 확률이 0.5에 가깝다는 건 엔트로피가 $\uparrow$.
⇒ 따라서 위의 엔트로피는 주어진 데이터의 heterogeneity 수치를 나타낸
Information gain (GAIN)
: feature A에 의한 information gain은, A로 분할하기 전과 후의 entropy 차이를 계산한다
$Gain(A) = Info(D) - Info_A(D)$
$Info(D) = -\sum_{i=1}^{m}{p_i log_2(p_i)}$ : 분리 전의 엔트로피
$Info_A(D) = -\sum_{j=1}^{v} \frac{\vert D_j \vert}{\vert D \vert} \times Info(D_j) $ : 분리 후의 엔트로피
![6][6]
위의 경우,
앞의 두 박스의 엔트로피는 0이고 마지막 박스의 엔트로피는
$Info_A(D) = \frac{4}{12} (-\frac{3}{4}log_2(\frac{3}{4})$ $-\frac{1}{4}log_2(\frac{1}{4}))$ 이렇게 구할 수 있다.
분할 전 엔트로피는, $Info(D) = -\sum_{i=1}^{2}{p_i log_2(p_i)}$ $= -\frac{1}{2}log_2(\frac{1}{2})-\frac{1}{2}log_2(\frac{1}{2})$
위의 경우 분리 전의 엔트로피는 높을 것이고, 분리 후에는 낮아진 값을 얻을 것이다.
만약 6+6 을 3+3씩으로, 즉 분할이 잘 안 된 경우를 생각해보면 1이 됨.
따라서 gain이 1-1 = 0이 된다.
⇒ information gain 높은 것 선택한다.
(완료)
[[ part 1-2 ]]
이전 시간에 decision tree induction보았음
Information gain은 엔트로피에 기반.
Gain은, 분리되기 이전의 엔트로피에서 분리된 후의 엔트로피를 빼서 계산 했었음
결국 엔트로피의 결과는 각 separation의 weighted average
Example
« example »
C4.5 (an Evolution of ID3)
C4.5는 ID3의 extension 버전.
기존에 ID3이 데이터 partition할 때 partition 되는 덩어리 개수가 많은 경우에 더 높은 점수를 주는 문제(biased towards features with a large number of values)가 있었음
파티션이 많은 경우 (즉 여러개의 덩어리로 나누는 경우) mixed data가 적을 확률이 올라감
진짜 separation 퀄리티 높이고 싶음(여러 개로 많이 나누는 경우 모델의 복잡도도 올라가고, 오버피팅 같은 문제도 발생)
따라서 bias problem 없애고 싶음.
이를 해결하고자 C4.5는 “Gain Ratio” 사용
Gain ratio
key idea : 페널티 주어짐
![7][7]
위와 같이 계산되고, ID3과 SplitInfo 구하는 부분이 다름.
Gain ratio는 split에 대한 엔트로피를 계산. 섞임 정도와 무관하게 Feature A에 의해 얼마나 많은 partition이 생성 되었는지에만 집중
마지막에 final gain ratio를 구할 때 첫줄인 penalty term을 이용해서 Gain을 나눔
따라서 penalty가 작아지면 작은 값으로 나누니 최종 gain ratio가 크게 나옴.
Example
« example »
CART (Classification and Regression Trees)
« SKIP : ID3와 유사»
Overfitting
(Decision tree의 big limitation)
언제 멈춰야 하는가?
하나의 방법으론 모든 data가 다른 node에 들어가는 것이 있음. 이 경우 test data의 정확도는 100이 나올 것임. 하지만 이게 잘 분류한건가? NO!
Test data에는 잘 맞겠지만 train data에는 좋지 않은 결과가 나올 것임.
궁극적으로는 사용하지 않았던 데이터에 대해 적절한 값이 나와야 하는데 이게 안될것임
(Decision tree의 overfitting 해결책으로) Tree Pruning
Tree pruning
말 그대로 fully grown decision tree의 branch를 자르는 것
→ training 정확도는 조금 하락할 수 있음. 하지만 모델이 light 해지고, 더 general 한 모델이 됨. (test data에 서 더 높은 정확도)
Tree pruning의 두 종류
- pre-pruning
- tree를 construct하면서 prune 하는 방법
- 방법: goodness measure가 threshold 값을 넘지 못하면 split 안함 (leaf node 되는 것)
- goodness의 예시로, split 후 sample의 minimum 수, depth of tree(일정 depth 넘으면 멈춤, minimum gain(split이후의 gain이 매우 작은 경우 멈춤)…
- 한계 : 어떻게 goodness, threshold 값을 정할 것인가?
- optimal(최적의) 값이 아님. 데이터마다 다름
- post-pruning
- fully grown tree에서 branch 제거 (먼저 decesion tree 만든 후 pruning)
- 이를 위해 validation set을 사용함
validation data는 기존 training data에서 분리된 것.
train data와 다른 validation set- 어떤 결정들의 정확도를 판단하기 위한 데이터
- 특정 pruning의 효과를 검증하고 싶은 경우, pruning 전 후의 정확도를 validation set으로 평가.
- 주의해야 할 것은 decision 평가하기 위한 용도로 test set 쓰면 안됨!!(test set은 최종 평가 시에만! 모든 pruning과 decision들이 결정된 후에.)
- 기존 tree를 validation set으로 accuracy 계산해서 prune 한 것의 accuracy가 나은 경우 prune.
validation set은 training set과 겹치지 않음!!
추가적으로 이러한 validation set은 pre-pruning의 결정에서도 사용할 수 있음
(threshold 값 정하는 등에)
Random Forest
위의 두 방법도 오버피팅 막는 방법이었지만 이 Random forest가 overfitting 피하는 더 효과적인 방법이다.
- 여러 decision tree의 앙상블 (500~10000이상의 decision tree)
- majority of voting이 classification의 result
- Forest의 각각 tree가 각기의 방법으로 class lable 결정. 이후 결과들의 aggregation이 모델의 최종 decision.