SVD와 Decision Tree

SVM(Support Vector Machine) - 선형 이론

 각 클래스의 데이터 샘플로부터 가장 멀리 위치해 있는 분류선일수록 일반화 성능이 좋다. 샘플로부터 분류 선까지의 거리를 마진(margin)이라고 한다.  샘플은 학습 데이터 중 일부에 해당하며 마진을 구성하는 이 데이터를 서포트 벡터(support vector)라고 한다. SVM은 두 데이터를 나누는 직선을 찾고자 하고 마진을 최대화하는 최적 직선(최대 마진 초평면)을 만드는 것이 목적이다.

최대 마진 초평면의 선형 방정식

 

평행한 두 직선위에 서포트 벡터가 존재하고 서포트 벡터에 대해 최대 마진 초평면과의 거리가 1이라면 마진은 아래와 같이 표현 가능하다.(점과 직선 사이의 거리)

  최적화 목표는 마진을 키우면서 모든 데이터를 알맞게 분류하는 것이다. 이를 간단히 표현하면 다음과 같다. 라그랑주 승수법 및 쌍대 문제 방식으로 해결할 수 있다.

 

어떠한 오분류도 허용하지 않고 완벽한 선형 모델로 분리 가능한 것을 하드 마진 SVM이라 한다. 하지만 일반적으로 어느 정도 데이터가 섞인 경우가 흔하다. 따라서 완벽한 선형 분리가 불가능한 경우가 많으므로 어느 정도의 오분류를 허용하면서 오차 발생에 따른 페널티를 비용 함수에 부과하여 일반화 성능을 높이는 것을 소프트 마진 SVM이라 한다.

 

 슬랙 변수(slack variabel)은 소프트 마진 SVM에서 사용하는 개념으로 완벽하게 선형 분리되지 않는 데이터에 대해 SVM을 적용할 수 있도록 한다. 각 데이터 포인터(i)당 하나의 슬랙 변수 ξ_i 가 할당되며 이 변수는 해당 데이터 포인트가 마진을 얼마나 위반하는지를 수치적으로 나타낸다.

• 마진을 위반하지 않은 데이터 : ξ_i = 0
  • 서포트 벡터와
  • 서포트 벡터보다 멀리 있는 데이터
• 마진을 위반한 데이터
  • 마진 경계 ~ 결정 경계 : 0 < ξ_i ≤ 1
  • 결정 경계 이후 : 1 < ξ_i , 이 경우는 올바르지 못한 클래스로 분류 됨

소프트 마진 SVM은 하드 마진 SVM 최적화 과정에 규제 페널티(ξ_i)를 도입해 일반화한 최적화 식을 사용한다. 목적은 마진의 크기를 최대화하고 마진 위반을 최소화하기 위함이다. C는 일반화를 위한 하이퍼파라미터로 마진 크기와 규제 사이의 중요도 변수이고 1 − ξ_i은 규제가 적용될 데이터 포인트에 대해, 결정 경계에서 ξ_i의 거리만큼 벗어날 수 있음을 허용하는 과정이다.

 SVM(Support Vector Machine) - 선형 실습

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_classification
from sklearn.svm import SVC

# 랜덤 데이터 통일
seed = 1234
np.random.seed(seed)

# 데이터 생성
X1, y1 = make_classification(n_samples=100, # 생성할 데이터 수
                             n_features=2, # 사용할 특성의 수
                             n_redundant=0, # 중복 특성(다른 특성으로부터 파생된 특성) 수
                             n_clusters_per_class=1, # 클래스 당 클러스터의 수
                             flip_y=0, #  클래스 레이블이 뒤바뀔 확률, 노이즈에 해당
                             class_sep=2, # 클래스 간 분리도를 조절, 높을수록 분리가 잘 됨을 의미
                             random_state=5

# 하드 마진 SVM
svm_hard_margin = SVC(kernel='linear', C=1000)
svm_hard_margin.fit(X1, y1)

# 결정 경계와 마진 직선 시각화
plt.scatter(X1[:, 0], X1[:, 1], c=y1, cmap=plt.cm.Paired)

plt.xlabel('feature1')
plt.ylabel('featuer2')

plt.margins(0.2)

# 현재 그래프의 x축과 y축 범위를 가져옴
xlim = plt.gca().get_xlim()
ylim = plt.gca().get_ylim()

# 그래프의 x & y축 범위를 바탕으로 모든 x,y 조합의 좌표 그리드를 생성
xx, yy = np.meshgrid(np.linspace(xlim[0], xlim[1], 50),
                     np.linspace(ylim[0], ylim[1], 50))

# 그리드 포인트를 이용해 각 포인트에서의 Desicion 결과값을 출력
Z = svm_hard_margin.decision_function(
    np.column_stack(
        (xx.ravel(), # xx matrix를 1차원 행렬로 flatten
        yy.ravel())  # yy matrix를 1차원 행렬로 flatten
     ) # 1 차원 행렬을 열 방향으로 묶어줌
) # 입력된 각 (x, y) 포인트에 대해 결정 경계로부터의 거리를 계산
Z = Z.reshape(xx.shape)

# 결정 경계와 마진 직선을 그리는 함수
plt.contour(xx, yy, # xx와 yy 공간 안에
            Z, # Z를 그릴건데
            levels=[-1, 0, 1], # Z가 -1, 0, 1 인 부분만 그릴것!
            colors=['orange', 'blue', 'orange'],
            alpha=0.5,
            linestyles=['--', '-', '--'] # -1, 0, 1 의 직선 개형을 표시
)

# 데이터 생성
X2, y2 = make_classification(n_samples=100, # 생성할 데이터 수
                             n_features=2, # 사용할 특성의 수
                             n_redundant=0, # 중복 특성(다른 특성으로부터 파생된 특성) 수
                             n_clusters_per_class=1, # 클래스 당 클러스터의 수
                             flip_y=0.06, #  클래스 레이블이 뒤바뀔 확률, 노이즈에 해당
                             class_sep=1.5, # 클래스 간 분리도를 조절, 높을수록 분리가 잘 됨을 의미
                             random_state=5)
                             
# 소프트 마진 SVM
svm_soft_margin = SVC(kernel='linear', C=0.1)
svm_soft_margin.fit(X2, y2)

# 결정 경계와 마진 직선 시각화
plt.scatter(X2[:, 0], X2[:, 1], c=y2, cmap=plt.cm.Paired)

plt.xlabel('feature1')
plt.ylabel('featuer2')

plt.margins(0.2)

# 현재 그래프의 x축과 y축 범위를 가져옴
xlim = plt.gca().get_xlim()
ylim = plt.gca().get_ylim()

# 그래프의 x & y축 범위를 바탕으로 모든 x,y 조합의 좌표 그리드를 생성
xx, yy = np.meshgrid(np.linspace(xlim[0], xlim[1], 50),
                     np.linspace(ylim[0], ylim[1], 50))

# 그리드 포인트를 이용해 각 포인트에서의 Desicion 결과값을 출력
Z = svm_soft_margin.decision_function(
    np.column_stack(
        (xx.ravel(), # xx matrix를 1차원 행렬로 flatten
        yy.ravel())  # yy matrix를 1차원 행렬로 flatten
     ) # 1 차원 행렬을 열 방향으로 묶어줌
) # 입력된 각 (x, y) 포인트에 대해 결정 경계로부터의 거리를 계산
Z = Z.reshape(xx.shape)

# 결정 경계와 마진 직선을 그리는 함수
plt.contour(xx, yy, # xx와 yy 공간 안에
            Z, # Z를 그릴건데
            levels=[-1, 0, 1], # Z가 -1, 0, 1 인 부분만 그릴것!
            colors=['orange', 'blue', 'orange'],
            alpha=0.5,
            linestyles=['--', '-', '--'] # -1, 0, 1 의 직선 개형을 표시
)

 

SVM(Support Vector Machine) - 비선형

 데이터의 복잡성으로 인해 선형 결정 경계로 데이터를 분류할 수 없는 경우가 있다. 특히 데이터가 휘어진 진 형태로 분포한다면 선형 SVM으로는 분류할 수 없다. 비선형 SVM은 이러한 데이터에 대해 효과적으로 작동한다. 선형적으로 분리할 수 없는 데이터를 고차원으로 변형하면 고차원의 초평면으로 분리할 수 있는 형태로 변환이 가능하다. 왜냐하면 차원이 증가하면 데이터 포인트 간의 상대 거리는 증가하고 각 차원에서 데이터끼리 차지하는 공간이 확장되기 때문이다. 그러면서 비슷한 특성을 공유하는 데이터들은 특정한 축 혹은 방향으로 군집될 가능성이 높아진다. 저차원의 데이터를 고차원의 데이터로 옮기는 과정 함수를 정의할 수 있고 이를 Mapping function(ϕ)라고 부른다. 

 

고차원의 데이터는 선형 분류할 수 있는 가능성이 있지만 계산량이 늘어난다는 단점이 있다. 확장한 고차원이 원본 데이터의 차원보다 훨씬 크다면 모델의 복잡도가 늘어나고 효율성이 떨어진다. 이를 해결하기 위해 커널 트릭이 제시된다. 고차원에서 선형 분류를 해야 하는 비선형 SVM에서도 데이터 포인트 사이의 내적 계산이 수행되어야 한다. 이때, 고차원의 내적 연산의 결과와 똑같은 결과를 보여주는 저차원 벡터끼리의 연산 함수가 있다면 고차원으로 데이터를 변형하지 않고도, 저차원의 데이터만으로도 고차원 데이터를 활용한 내적 연산의 효과를 누릴 수 있다. 바로 커널 트릭(Kernel Trick)이다.

 

 고차원의 내적 연산과 똑같은 결과를 보여주는 함수를 커널이라고 하며 일반적으로 비선형 SVM에서 많이 사용되는 커널 함수는 아래와 같다.

• 다항 커널 (Polynomial Kernel): 다양한 차수 설정으로 여러 식을 근사할 수 있지만 과적합의 위험이 있음

• RBF 커널 (Radial Basis Function Kernel) 혹은 가우시안 커널 (Gaussian Kernel): 다양한 데이터에 적용하면서도 유연성이 높아 범용성이 높음

• 시그모이드 커널 (Sigmoid Kernel): 이진 분류에 최적화되며 RBF 커널에 비해 성능이 떨어짐

 비선형 SVM의 최적화 문제도 소프트 마진 SVM과 비슷한 구조를 갖고 있다. 다만 저차원이 아니라 고차원에서의 데이터 분류가 가능하도록 하는 조건이 들어간다.

고차원 데이터에서 선형 분류가 가능하도록 하는 조건

SVR (Support Vector Regresson)

 회귀 문제로 확장한 SVM 방법을 SVR (Support Vector Regresson)이라고 한다. 주어진 데이터에서 가능한 많은 데이터 포인트를 포함하는 마진 구역을 설정하고 이 마진 구역은 사용자가 선언한 허용 오차(ε) 내부의 영역이다. 그 마진 구역 안에서 회귀선(혹은 초평면)을 찾는 것이 목표이다. 커널 함수를 적용한 SVR의 최적화 함수는 아래와 같다.

Decision Tree - 용어

• 노드
  • 데이터에 대한 특정 질문이나 조건
  • 데이터를 분류하는 과정에서 사용
• 엣지
  • 노드와 노드를 연결하는 선
  • 상위 노드의 특정 질문에 대한 가능한 답변
• 루트 노드
  • 트리의 가장 상단에 위치한 노드
  • 분류 또는 예측을 시작하는 지점
• 분할 노드 (= 결정 노드) \
  • 데이터를 더 작은 하위 집합으로 나누는 데 사용되는 중간 노드
• 리프 노드 (= 터미널 노드)
  • 트리에 말단에 위치한 노드
  • 더 이상의 분기가 없고 자식 노드를 갖지 않음

Decision Tree - 분류

 결정 기준(Decision Criteria)은 데이터를 분할하는 기준을 결정하는데 사용되는 방법론이다. 좋은 결정 기준은 트리를 더욱 간결하고 효율적으로 만들며 과적합을 방지하고 일반화 성능을 향상한다. 분류 과정에서 사용되는 결정 기준은 정보 이득, 지니 불순도가 있고 회귀 과정에서 사용되는 결정 기준은 MSE 최소화가 있다. 

 

 엔트로피(Entropy)는 어떤 상황이나 현상이 품고 있는 불확실성을 의미하며, 포함하는 정보의 양과 반비례한다. 엔트로피는 수치적으로 구할 수 있으며 아래와 같다.

 각 상황은 특정한 정도의 엔트로피를 갖고 있음을 알 수 있다. 따라서 각 노드에 포함되는 데이터의 순도에 따라 엔트로피가 계산될 수 있다. 정보 이득(information gain)이란 노드들의 엔트로피를 계산해 엔트로피가 낮아지는 방향으로 결정 경계를 선정하는 것을 의미한다.

 

 지니 불순도(Gini Impurity)는 데이터 집합의 순도를 측정하는 또 다른 방법으로 데이터 안에 존재하는 클래스 분포의 불균형을 평가하는 방법이다. p_i는 데이터 집합 안에 존재하는 i번째 클래스가 나타나는 확률로 지니 불순도는 0 이상 1 미만의 값을 갖는다. 0이면 모든 데이터가 하나의 클래스에 속하는 제일 순도가 높은 상태이고 1에 가까운 값은 모든 클래스의 데이터가 고루 섞인 상태로 불순도가 제일 높다.

 

 Decision Tree - 회귀

 MSE 최소화 방식은 Decision Tree에서 회귀 문제를 푸는 주요한 방식 중 하나이다. 각 노드에서 실제 정답과 예측 값 사이의 평균 제곱 오차(MSE)의 평균을 계산하고 이 값을 최소화하는 노드를 찾아가는 방식으로 Tree가 만들어진다.

 

  트리 구조는 해석 용이성, 사용 편리함, 적당히 괜찮은 성능, 스케일링에 둔감함 등 많은 장점을 가지고 있다. 하지만 트리 기반 모델은 축에 수직인 방향으로 데이터가 분할되어 축에 수직한 데이터는 쉽게 해결하지만 경계면이 회전되어 있다면 구불구불한 경계면이 생성되어 일반화에 어려움이 있을 수 있다. 필요시 주성분 분석을 통한 데이터 회전이 필요할 수 있다. 데이터 노이즈에도 굉장히 민감하여 특정 데이터의 추가가 전체 모델 결과에 큰 변화를 줄 수 있다. Depth가 깊다면 강한 Overfit 위험이 크다. 

 

SVM과 Decision Tree 실습

 선형 분류 실습에서 사용한 비행 경험 만족도 데이터로 실습을 해볼 것이다. 데이터 전처리로 NA 값 제거, 지연 시간 5시간 이상 제거, 범주형 데이터 인코딩, 상관도를 바탕으로 15개 특성 추출, 20% 학습 및 평가 데이터 분할을 하였다. 이론 시간에 좋은 성능을 보였던 RBF 커널을 활용해 학습하였다. SVM 학습 시간은 비행 만족도 데이터 기준 약 30분 정도로 선형 모델에 비해 오래 걸렸다. 

 

 SVM을 활용한 정확도는 학습 데이터 : 90.7 % , 평가 데이터 : 90.4 % 이다. Logistic Regression을 활용한 정확도는 학습 데이터 : 82.8 % , 평가 데이터 : 82.9 % 이었다. 정확도 이외에도 분류 평가 척도로 정밀도(Precision), 재현율(Recall), F1 점수가 있다.

• 정밀도 (precision) 
  • 예측한 양성 결과가 실제로 얼마나 진짜 양성인지를 계산
  • 모델이 양성 결과를 잘 찾아내야 하는 상황에서 중요
• 재현율 (recall)
  • 실제 양성 중 얼마나 양성을 잘 찾아냈는지를 계산
  • 정답을 잘 찾아내는 과정에서 중요
• F1 점수
  • 정밀도와 재현율의 조화 평균
  • 조화 평균을 사용해 낮음 점수에 대한 페널티를 늘림
  • 정밀도와 재현율이 전반적으로 좋아야 좋은 F1값을 가질 수 있음

 Decision Tree 학습으로 Entropy 결정 경계를 사용하는 최대 깊이 5의 트리를 생성하였다. Decision Tree 학습 시간은 SVM에 비해 짧았다. DT를 활용한 정확도는 학습 데이터 : 95.5 %, 평가 데이터 : 93.0 %이었다.

 

 머신러닝 모델의 크기가 커지고 복잡도가 증가하면 모델의 성능이 올라간다. 하지만 과적합 현상이 발생하면 학습 데이터에 대한 성능이 지속적으로 상승하면서 단순히 학습 데이터를 암기하게 되어 평가 데이터에 대한 성능이 하락한다. 따라서 평가 데이터에 대한 성능이 낮아지기 시작하는 지점의 세팅을 이용해 최적의 모델을 선택해야 한다.