[Data Science] Lecture 11 : Machine Learning

naljin

9 min readJun 18, 2019

2019년 1학기 고려대학교 강재우 교수님 데이터 과학 정리

Machine Learning Model의 비교

Dimension 을 평가하는 것은 아래의 사항들을 포함한다.

Power와 expressibility(얼마나 복잡한 모델까지 다룰 수 있는가)
해석 가능성(Interpretability)
사용하기 쉬운가 (Ease of Use)
트레이닝 속도 (Training Speed)
예측 속도 (Prediction Speed)

XOR and Linear Classifiers

Linear Classifier (선형 분류기)는 XOR처럼 간단하지만 비선형적인 함수에 적용될 수 없다. 따라서 아래와 같은 더 강렬한 메소드들이 필요하다.

Decision Tree
Random Forest
Support vector machines
Deep learning

Decision Tree

Decision Tree Classifiers

각 row/instance 는 분류를 위한 고유의 root-to-leaf path 가 있다. 이 tree는 training example들을 비교적 균일한 구성으로 나누어 결정을 쉽게 만든다.

Construction Decision Tree

Tree는 top-down 방식으로 구성된다. 각 feature/dimension 을 따라 데이터를 분류하면서 m개의 클래스로 정보들을 나눈다. Pure split 은 아이템들을 하나의 단일 클래스로 분류하고, Balanced split 은 아이템들을 대략 같은 사이즈의 그룹으로 분류한다.

Information-Theoretic Entropy

Entropy는 class confusion의 정도를 나타낸다. 높은 Entropy는 높은 불확실성(uncertainty)과 낮은 안정성을 의미한다.

Class가 위와 같이 Yes / No 의 두가지로 나눠진 상황일때 Pr(Y)의 값은 9/15, Pr(N)의 값은 6/15가 된다.

엔트로피가 최대가 되는 상황은 Y/N 의 비율이 1:1 일때, 최소가 되는 상황은 Y/N 비율이 1:0 일때이다.

Max : ent(D) = -1/2log1/2–1/2log1/2 =1
Min : ent(D) = -1log1 = 0

Split Criteria

gain 값은 높을수록 좋다. 앞에 있는 entropy는 분류 전의 값, 뒤에 있는 entropy는 Ai 로 분류 후의 값이다. 적절한 Ai로 잘 분류했다면, 낮은 entropyAi 값과 함께 gain 값은 높아질 것이다. 해당 값(gain)은 decision tree에서 root 를 고르는데 사용할 수 있다.

gain(D,Age) = 0.971–0.888 = 0.083
gain(D,Own_house) = 0.971–0.551 = 0.420
gain(D,Has_Job) = 0.971–0.647 = 0.324
gain(D,Credit_Rating) = 0.971–0.608 = 0.363

이런식으로 값을 구하면 own_house의 gain 값이 0.420으로 가장 높으므로 root로 설정할 수 있다.

하지만 현실에서 tree는 big&fat 해질수 있기 때문에 stopping criteria를 정해야 한다.

Stopping Criteria

트리의 마지막에 하나의 원소만 존재하는 것과 같이 leaf가 pure할 때까지 트리를 만든다는 것은 곧 overfit(과적합) 상태라는 의미이다. 따라서 information gain < ε(not zero) 일때 트리 구성을 멈추거나, full tree 를 만든 후 low value nodes를 가지치기 할 수 있다.

Advantages of Decision Trees

비선형성
범주형 변수(Categorical variables) 지원
해석 가능성(Interpretability) — tree 는 읽을 수 있음
Robustness — 서로 다른 트리들의 앙상블 구성 가능 (앙상블 기법은 동일한 학습 알고리즘(지도학습, 비지도 학습 등)을 사용해서 여러 모델을 학습하는 개념)

Ensemble Methods : Bagging

일반적인 모델을 만드는데 집중한다. overfitting 을 방지할 수 있다. 대표적인 Bagging 알고리즘으로 RandomForest 모델이 있다.

Training

k 개의 bootstrap 샘플들 만든다. S[1], S[2], …., S[k] (random selection with replacement)
S[i]마다 별개의 classifier을 만들어 적용한다.

Testing

k classifiers에 대한 투표 방식 (voting)으로 집계를 하며, 이를 통해 새로운 인스턴스를 분류한다. (equal weights)

Bagging

Ensemble Methods : Boosting

맞추기 어려운 문제를 맞추는데 집중한다. AdaBoost, XGBoost, GradientBoost 등 다양한 모델이 있다.

Training

일련의 classifier를 만든다 (the same base learner)
각 classifier 은 이전 것에 dependent 하며 이전 것의 에러에 집중한다.
이전의 classifier 에서 잘못 예측된 example들은 높은 가중치를 받는다

Testing

test case에서 최종 class를 결정하기 위해 classifier들에 대한 결과는 합쳐진다.

Boosting

Random Forest

Bagging with decision tree + split attribute selection on random subspace

학습 과정에서 candidate split을 할 때마다 features의 random subset을 선택하는 변형된 트리 학습 알고리즘을 사용한다.

Step

bootstrapped dataset 생성
bootstrapped dataset 이용해서 의사결정 트리 만들되, 각 step 에서 feature의 random subset을 이용

Inference

Random forest에 있는 모든 tree에 대해 data를 적용시키고 나면 더 많은 표를 받은 선택지가 있을 것이다.

Estimating the accuracy

boostrapped dataset 만들때 대개 1/3의 original data는 포함되지 않음. 같은 데이터가 중복돼서 들어가는 경우가 있기 때문(random selection with replacement). 이러한 잉여 데이터들을 validation set 으로 사용할 수 있다.

Support Vector Machines

SVM은 비선형 분류기(non-linear classifiers)를 만드는 중요한 방법이다. 두 클래스 사이에서 최대 마진을 위한 linear separator 를 찾으면서 동작한다.

non-linear classifier인데 linear separator를 찾으면서 동작 가능한 이유는 SVM은 linear decision boundary를 input space가 아닌 feature space에서 찾기 때문이다.

SVM vs. Logistic Regression

두 방법 모두 separating plane을 찾는다. 하지만 LR 은 모든 포인트들을 고려하는 반면, SVM은 바운더리에 있는 포인트만 고려한다.

Projecting to Higher Dimensions

2D 상황에서linear decision boundary 를 찾을 수 없을지라도, dimension을 더해주면 모든 것이 linearly separable하다.

Kernels and non-linear classification

저차원 공간에서 선형 분리 안되는 데이터들을, 고차원 공간에 매핑시켜서 선형 분리되도록 할 수 있다. 이를 위해 저차원을 고차원으로 매핑해주는 함수가 필요하고 이를 커널함수라고 한다.
다항식(polynomial), RBF (Radial Basis Function), sigmoid func 등 존재한다.