인공지능개론 | Classification

⚠ Before reading the post ⚠

본 포스팅은 컴퓨터 공학 계열 전공자 대학교 4학년에서 대학원생 기준으로 작성하였습니다.
기본적인 자료구조나 알고리즘 내용은 생략하였습니다.

KNN Classification | KNN 분류

KNN은 K Nearest Neighbor의 준말로 이번 포스팅에서 알아볼 방법은 데이터 분포 상 기준에서 가장 가까운 데이터 K개를 자신과 같은 항목으로 분류하는 방법이다. 분류할 때는 euclidean 방법으로 거리 반경 내 유무로 판단하게 된다. 아래는 거리 계산 방법 중 두 가지를 소개한다.

결론부터 말하자면 이러한 방법은 instance based learning으로 꽤나 게으른 방법 중 하나기에 단순하지만 분류하는데 시간이 꽤나 오래 걸리는 방법이다.

Euclidean 방법을 사용하기 위해서 추상적인 attribute들을 하나의 숫자 값으로 치환하여 계산하게 된다.
계산하기 전에 더 나은 분류를 위해 전처리로 정규화(attribute scaling)를 하게 된다.

사진과 같이 모호한 부분들의 분류를 더 명확하게 하게 한다.
아래 추상적인 attribute들을 KNN으로 분류해보자.

숫자 값으로 치환한 추상적인 dataset을 정규화(attribute scaling)를 거친 모습이다. 궁금한 query 중심으로 테니스 치기에 적합한지의 여부를 조사하기 위해, query 중심으로 dataset table와의 거리를 계산하여 가장 가까운 이웃들을 순으로 재정렬을 하게 된다. K=3일 때 가장 가까운 3개를 조사하면 Day2, 7, 11이 나오게 되는데, 이 때 Day 2, 7, 11의 분류 상태 중 가장 많이 따르는 것이 query가 속한 카테고리이므로, 이미지에서 보이는 것과 같이 2/3 확률로 테니스치기 적합한 날씨로 분류가 된다.

Distance weighted nearest neighbor algorithm

거리가 아닌, 이웃들의 무게 중심으로 더 가까운 이웃일 수록 결과에 영향을 미치게 된다. 무게 할당 시에는 거리 제곱의 역수( $\frac{1}{distance^2}$ )로 할당하게 된다.

만약 k=all 일 경우?

위 투표에서 보이는 것과 같이 K개로 제한할 경우 투표에 참여할 데이터는 K개로 좁혀지는데, 이를 전체로 확장하게 되면 query가 어디에 속하는지에 대한 결과에 모든 이웃들이 영향을 미치게 된다.
마치 모든 양을 모는 모습과 비슷해서 Shepard 방법이라고 한다. 하지만 이 경우 분류하는 데 있어서 overhead 문제가 발생할 수 있다고 한다.

Voronoi diagram

벡터 공간 상에서 distance-weight nearest neighbor 방법이라고 이해하면 쉽다.

Wrap up & Conclusion

이번 시간에는 아마 배웠던 알고리즘 중 가장 쉽고 간단한 방법이나 instance-based learning으로 계산량이 많아 K의 상태에 따라 overhead가 발생하는 lazy learning 방법이다.

KNN 분류 순서

추상적인 특성들을 숫자로 치환하여 데이터 테이블 형성 후 모든 특성 값들을 scaling하여 정규화 전처리를 거치게 된다.
궁금한 지점(query)에서 모든 데이터들과의 거리 계산 후 가장 가까운 거리 순인 top k개 중심으로 각 k개 데이터가 속한 분류 투표를 한다.
가장 많이 나온 분류 투표가 곧 query의 카테고리이다.

정규화를 하는 이유는 같은 공간 상에서 판단하기 위함도 있고 분류하는데 있어서 거리 계산이 명확해지기 때문이다.
KNN 방법에는 이웃들을 각 무게를 할당하여 계산하는 방법도 있다.