머신러닝 알고리즘 - KNN & SVM

KNN

 

KNN은 사례 기반 학습 중 하나로 별도의 모델 생성 없이 인접 데이터를 분류/예측하는데 사용할 수 있다.

• Lazy Learning : 모델을 미리 만들지 않고, 새로운 데이터가 들어오면 계산을 시작
  • KNN, Native Bayes
• 데이터로부터 모델을 생성하고 분류/예측하는 것은 Model-Based Learning 이라고 한다.

 

 

K-Nearest Neighbors 

: K 개의 가까운 이웃을 찾고, 학습 데이터 중 K개의 가장 가까운 사례를 사용하여 분류 및 수치를 예측한다.

 

 

 

알고리즘 동작 방식

1. 새로운 데이터를 입력
2. 모든 데이터들과의 거리를 계산
3. 가장 가까운 K개의 데이터를 선택
4. K개의 데이터의 클래스를 확인함
5. 다수의 클래스를 새로운 데이터의 클래스로 예측함

 

K에 따라 달라지는 새로운 데이터 클래스

 

 

KNN에서는 알맞은 K를 선정하는 것이 KNN 알고리즘의 성능에 중요한 영향을 끼친다.

 

 

 

K 값 설정

 

1. K 값에 따른 결정 경계

 

• K가 작을수록 이웃을 적게 사용하므로 Overfitting이 될 가능성이 크다.
• K가 클수록 이웃을 많이 사용하므로 Underfitting이 될 가능성이 크다. 

 

 

 

Cross Validation

• 교차 검증을 통해 제일 성능이 좋은 K를 선택해야 한다.
• 예를 들면 1~10 사이의 K값 설정한 결과 중 성능이 제일 좋은 K를 선택하는 방식
• 이 때, K는 홀수로 지정하는 것이 유리하다.
  • 짝수인 경우 동점인 상황이 발생하고 이를 위한 로직이 추가로 필요함 

 

 

 

KNN에서 사용하는 거리 방식 

 

• 유클리드 거리
  • 두 점 사이의 거리를 계산할 때 흔히 쓰는 방식으로, 두 점 사이의 거리를 의미한다.

유클리드 거리

• 멘허튼 거리
  • 한 번에 한 축 방향으로 움직일 수 있을 때, 두 점 사이의 거리를 의미한다.

맨허튼 거리

 

 

 

 

 

KNN의 장점 

• 학습 과정이 없다
• 결과를 이해하기 쉽다

 

KNN의 단점 

• 데이터가 많을수록 시간이 오래 걸린다.
• 지나치게 데이터에 의존적이다.

 

 

 

---

 

SVM

 

SVM이란

• Support Vector Machine (SVM) 은 결정 경계 ( Decision Boundary)를 정의하는 모델이다
• SVM은 Margin을 최대화하는 Decision Boundary를 찾는 것을 목표로한다. ( 분류 오차를 줄이면서, 동시에 여백을 최대로 하는 결정 경계를 찾는 것 ) 
• Support Vector가 Decision Boundary를 만드는데 영향을 주기 때문에 SVM이라고 불리어진다.

 

SVM의 구성 요소

one-class svm의 예시

Support Vector	두 클래스 사이의 경계에 위치한 포인트
Margin	결정 경계와 서포트 벡터 사이의 거리
Decision Boundary ( hyper-plane : 초 평면 )	데이터를 나누는 기준이 되는 경계

 

 

 

 

1.. SVM의 Margin

 

 

[1] Hard Margin

 

Hard Margin SVM은 모든 훈련 데이터 포인트가 margin 영역 내에 위치하도록 하는 SVM 모델입니다.

Margin은 초평면과 해당 클래스의 가장 가까운 데이터 포인트 간의 거리를 나타냅니다.

이 방법은 데이터가 선형적으로 완벽하게 구분될 때 사용할 수 있습니다. 하지만 이상치(outliers)가 있는 경우나 데이터가 선형적으로 완벽하게 나누어지지 않는 경우에는 모델이 제대로 작동하지 않을 수 있습니다.

 

 

[2] Soft Margin

 

Soft Margin SVM은 일부 이상치나 잘못 분류된 데이터를 허용하는 방법으로, 데이터가 완벽하게 선형적으로 분리되지 않을 때 사용됩니다. 이를 위해 목적 함수에 일부 허용 오차(slack variable)를 도입하여 오차를 최소화하려고 합니다.

 

 

 

패널티의 종류

• 0-1 Loss
  • Error가 발생한 개수만큼 패널티를 계산함
• Hinge Loss
  • 오분류 정도(Support Vector에 떨어진 정도)에 따라 패널티 계산

 

 

 

 

 

2. SVM의 파라미터

 

 (2-1) 커널 

Non-Linear SVM

 

 

Non-Linear SVM은 입력 데이터가 선형적으로 분리되지 않는 경우에 사용되는 SVM의 확장입니다. 

선형적인 결정 경계로는 데이터를 분류할 수 없는 경우, 데이터를 고차원 특징 공간으로 매핑하고, 그 공간에서 선형적인 결정 경계를 찾는 방식을 채택합니다. 

이를 커널 트릭(kernel trick)이라고도 부릅니다. 

 

커널 트릭 (Kernel Trick): 커널 트릭은 데이터를 높은 차원의 특징 공간으로 매핑하는 것을 피하기 위해 사용됩니다. 

높은 차원의 공간에서 선형적인 결정 경계를 찾는 것이 원래의 입력 공간에서 비선형 결정 경계를 찾는 것과 동일한 효과를 가져옵니다.

 

 

 

 

커널의 종류 

 

1. 선형 커널

선형 커널은 입력 벡터의 내적을 사용하여 데이터를 변환.

이 커널은 고차원 공간으로의 변환 없이도 데이터가 선형적으로 분리 가능한 경우에 사용됩니다.

  -  다항식 커널은 입력 벡터의 내적에 다항식을 적용한 커널로, 데이터의 비선형 관계를 학습할 수 있음

  -  차수를 조절하여 고차원 공간에서의 변환을 수행함

 

2. 다항식 커널(Polynomial Kernel)

다항식 커널은 입력 벡터의 내적에 다항식을 적용한 커널로, 데이터의 비선형 관계를 학습할 수 있습니다. 차수를 조절하여 고차원 공간에서의 변환을 수행합니다.

  -   복잡한 비선형 관계를 학습할 수 있으며, 차수를 높일수록 더 복잡한 패턴을 학습할 수 있음.

  -   차수가 너무 높으면 모델이 과적합될 수 있음.

 

 

3. 가우시안 라디언스 기반 커널 (Gaussian RBF Kernel)

가우시안 RBF 커널은 고차원 공간에서 데이터 포인트 간의 유사도를 측정하는 커널로, 비선형 데이터를 잘 처리합니다.

  -  RBF 커널은 매우 강력한 비선형 커널로, 대부분의 비선형 분류 문제에 적합함

  -  𝛾 값이 너무 크면 모델이 과적합되고, 너무 작으면 과소적합될 가능성이 있음

 

 

4. 시그모이드 커널 

시그모이드 커널은 신경망에서 사용하는 활성화 함수와 유사하며, 두 입력 벡터의 내적을 시그모이드 함수에 적용합니다.

  - 시그모이드 커널은 뉴럴 네트워크의 뉴런과 유사한 방식으로 작동

  - 𝛾와 𝑟값의 조합에 따라 모델의 성능이 크게 달라질 수 있음

  - 보통 다른 커널에 비해 잘 사용되지 않지만 특정 문제에서는 유용할 수 있음

 

 

 

 

 

 (2-2) 정규화 (Regularization) 파라미터

Regularization Parameter ( C ) 

 

SVM 모델의 목적 함수는 2가지 항으로 구성된다. 

1. 마진의 최대화 :  SVM은 데이터를 분리하는 초평면을 찾을 떄, 클래스 간의 마진을 최대화하려 함
2. 분류 오류의 최소화 : C 파라미터는 마진을 침범하는 서포트 벡터의 허용 범위를 조절함 

 

SVM 목적 함수

 

w : 결정 경계의 가중치 벡터

 ξ i ​ (slack variable) : 포인트가 마진을 벗어난 정도

C :  정규화 파라미터입니다.

 

w는 결정 경계의 가중치 벡터

 ξ i ​ 는 슬랙 변수(slack variable) : 각 데이터 포인트가 마진을 얼마나 벗어나는지를 나타냅니다.

C는 정규화 파라미터입니다.

 

C값에 따른 결정 경계

 

 

 

 

 (2-3) γ (Gama) 파라미터

Gaussian RBF 커널을 사용할 때 사용된다. ( 선형 또는 다항식 커널을 사용하는 경우에는 요구되지 않 ) 

데이터 포인트 간의 거리 척도에 영행을 줌, 이는 포인트 간의 영향 범위를 제어하는 역할을 한다.

 

큰 감마 값은 데이터 포인트 간의 거리에 민감하게 반응하며, 결정 경계가 매우 복잡해져 과 적합될 가능성이 높아진다.

작은 감 값은 덜 민감하게 반응하며, 결정 경계가 더욱 단순해지며 과소 적합될 가능성이 높아진다.

 

 

 

 

 

SVM의 장점 

• 비선형 분리 데이터도 커널을 사용하여 분류 가능
• 고차원 데이터에도 사용이 가능하다.

 

SVM의 단점

• 데이터가 많을수록 속도가 느려진다.
• 확률 추정치를 제공하지 않는다.