머신러닝 알고리즘 정리 (K-NN, SVM)

1. K-NN (K-nearest neighborhood)

k-nn 그림 설명.

classification 알고리즘의 일종으로 user가 직접 정의하는 parameter인 K에 따라 데이터들 간의 거리를 기반으로 가까운 K개의 데이터들의 투표를 통해 분류를 진행한다. 이 때, k는 sqrt(n)보다 작은 값으로 정하며, 너무 작을 시에는 noise가 심하고(variance가 커서 신뢰도가 떨어짐), 너무 클 경우에는 다른 클래스의 데이터가 포함될 가능성이 크므로(bias가 커지므로 부정확해 질 수 있음) k를 잘 정하는 것이 중요하다. 데이터들 간의 거리는 Euclidean, Manhattan, Minkowski, correlation 등 다양한 거리 계산 방법을 활용할 수 있으며, 사전지식이나 cross-validation을 활용하여 거리에  weighting을 줄 수도 있다. 거리 계산을 할 때에는 feature를  normalization 해 줄 수 있도록 한다.

이 때, variable의 타입에 따라서 거리 계산을 다르게 하는데, 
euclidean 거리는 data의 크기에 초점을 둔다면,
correlation 계산은 variable들 간의 경향성을 보여준다.

차원의 저주(curse of dimensionality)
차원이 커짐에 따라 가장 가까운 이웃이 실제로는 가장 가깝지 않을 수 있다. (데이터와의 거리가 차원이 커질 수록 더 멀어지기 때문에) 

2. SVM (Support Vector Machine)

SVM

SVM의 중요 개념은 data class 사이에 margin을 최대로 하는 plane을 찾는 것이다. 이를 decision boundary 라고 하며, decision boundary를 기준으로 가장 가까이에 위치한 data들을 support vector라고 한다.  이 때, decision boundary는 f(x) = w^(T)x + b로 표현한다. SVM 알고리즘에서는 오로지 support vector만을 고려하여 support vector사이와의 거리를 기준으로 크거나 작은 것들을 분류한다. 이처럼 support vector만 고려하는 것은 SVM이 일반화에 강력한 알고리즘인 이유이다.

Objective function (목적함수)
마진을 최대화. (maximizing margin)
M(margin) = 2/(sqrt(w^(T)*w))
따라서 Q: 1/2 * (w^(T)*w) 를 최소화하는 것이 목적함수이다. 
이 때, SVM은 trainin set가 noisy할 경우 overfitting이 일어나기 쉬우므로 slack variable을 활용하여 noise sample에 대한 penalty를 줄 수 있다.

Parameter
w and b.
목적함수 Q는 quadratic function이므로 dual problem을 활용하여 f(x)를 변환하여 풀어나간다. 이 방법은 따로 자료를 찾아보길 바란다.

 

TISTORY는 수식을 적는 데 너무 불편해서 생략하게 되는 정보가 많다.. 어떻게 하면 좋을까.