kNN & Spam Filter

kNN

kNN(k Nearnest Neighbor): 최근접 이웃 알고리즘, 거리를 이용해 분류를 수행하는 알고리즘

 

Machine Learning = Feature Engineering (특징) + Statistics (분포)

 

ex) 토마토는 채소인가? 과일인가?

• Feature로 sweetness, crunchiness를 선정
• Feature Selection: 집단을 구분할 수 있는 변수를 선정하는 것

	과일	채소
Sweetness	大	小
Crunchness	小	大

Feature에 따른 분류

 

 

좌측 그림 - 같은 종류끼리 비슷한 위치에 모여있음

 

토마토가 과일인지 채소인지 알아보기 위해 토마토에서 가장 가까운 k=4개(4-Nearest Neighbor)의 종류를 알아보자.

 

sweetnest of tomato: 6, crunchiness of tomato: 4

 

n차원 공간에서 두 점 (p, q) 거리는 유클리디안 거리를 이용하여 구할 수 있다.

유클리디안 거리

유클리디안 거리 계산 결과

• 1-NN: 가장 가까운 것 하나만 볼 때, 토마토는 과일인 오렌지와 가깝다. 그러므로, 토마토는 과일로 판정한다.
• 3-NN: 토마토와 가장 가까운 3개를 찾고(오렌지, 포도, 땅콩) 이들이 과일 2종류, 단백질 1종류이므로 다수결에 의해 과일로 판정한다.
• Optimal k: 일반적으로 k는 3~10개 사이로 정함 (절대적이지 X)
• 학습 데이터에서 성과를 측정해 오분류가 적은 k를 결정하고 이를 test set에서 검증하여 결정하는 것이 합리적

 

• k가 작으면 몇 개의 잘못된 데이터들이 판단에 영향을 미칠 수 있고, (Overfitting)
• k가 크면 안정적인 판단을 할 수는 있으나 가까이 있는 것과 멀리 있는 것이 같은 정도로 의사결정에 참여하는 단점을 가지고 있다.

 

kNN은 거리에 의해 유사도를 측정하기 때문에 모든 입력변수는 양적변수이고 Scale이 같아야 한다. ( sweetness, crunchiness 둘 다 1~10 사이 )

 

s_i는 표준편차

 

Minimax Standardization

x_max - x_min은 항상 최대의 거리

x는 (x_min, x_max) 사이에 있으므로, 0 ≤ x_new ≤ 1

 

왼쪽 표를 양적인 데이터로 바꾸는 방법, One Hot Encoding이라고 함

 

임의의 k에 대해 테스트 데이터셋에서 위와 같이 정오표를  만들면 분류 정확도, 오분류율, Precision, Recall과 같은 정확도를 구할 수 있다.

• Accuracy (정확도): 옳게 측정한 비율
• Precision: yes라고 한 것(예측한 것, Predicted yes) 중 맞는 것이 얼마인가
• Recall: 맞춰야 하는 것(Actually yes) 중 맞은 것이 얼마인가

false negative & false positive - 잘못 측정된 것

k는 정확도, Precision, Recall이 동시에 높은 값을 선택하는 것이 좋다.