티스토리 뷰
1부 분류
2장 k-최근접 이웃 알고리즘
이 알고리즘은 영화를 장르별로 분류할 때 주로 사용하는 알고리즘이다. k-최근접 이웃은 거리측정(distance measurement)의 개념을 활용하게 된다. 장점으로 높은 정확도와 오류데이터(outlier)에 둔감하며 데이터에 대한 가정이 없는 반면 단점은 계산 비용이 높은 반면 많은 메모리를 요구한다고 한다.
k-최근접 이웃(KNN)알고리즘은 기존 훈련 집합이었던 예제 데이터 집합이 있다. 모든 데이터에 분류 항목 표시 라벨이 붙어 있으며 각각의 데이터가 어떤 분류 항목으로 구분되는지 알 수 있다. 이후 분류 항목 표시가 붙어 있지 않은 새로운 데이터가 주어졌을 때 기존의 모든 데이터와 새로운 데이터를 비교하게 된다. 그리고 가장 유사한 데이터(가장 근접한 이웃)의 분류 항목 표시를 살펴본다. 이때, 분류 항목을 이미 알고 있는 데이터 집합에서 상위 k개의 가장 유사한 데이터를 살펴보게 된다. 이것이 k의 유래이며, 여기서 k는 일반적으로 20 미만의 정수를 사용한다고 한다. 마지막으로, k개의 가장 유사한 데이터들 중 다수결을 통해 새로운 데이터의 분류 항목을 결정하게 된다.
예를 들어 로맨스 영화와 액션 영화를 분류한다고 보자. 많은 영화를 관람한 누군가는 각 영화마다 발차기 장면과 키스 장면의 출현 횟수를 센다. 그리고 보지 못한 새 영화 한 편을 찾았고 이것이 로맨스영화인지 액션 영화인지를 알고자 한다고 보자. 이러한 결정을 위해 KNN알고리즘을 사용하게 된다.
알지 못하는 새 영화에 얼마나 많은 발차기 장면과 키스 장면이 나오는지 확인하고 이전 예제 영활의 발차기 장면 횟수와 키스 장면 횟수를 참고하여 이 두변를 기준으로 다른 모든 예제 영화들과의 거리를 계산한다. 만약 6편의 영화와의 거리가 20.5, 18.7, 19.2, 115.3, 117.4, 118.9로 측정이 되었다면, 거리를 내림차순으로 정렬하여 가장 가까운 k개의 영화를 찾는다. k=3이라고 한다면 세 개의 가장 가까운 영화는 18.7, 19.2, 20.5로 거리측정된 영화가 된다. 이들의 장르가 로맨스, 로맨스, 액션이라면 미지의 영화의 장르는 다수결로 로맨스가 된다.
이처럼 k-최근접 이웃 알고리즘은 간단하며 데이터를 분류하는데 효과적이다. 이 알고리즘은 데이터 집합 전체를 계산에 활용되기 때문에 큰 데이터 집합을 처리하기 위해서는 큰 저장소가 필요하게 된다. 게다가, 데이터 집합 내의 모든 데이터에 대해 거리 측정을 계산해야 하기 때문에 데이터 크기가 커지면 사용이 힘들어 질 수 있다. 또 데이터 구조에 대한 어떠한 정보도 주지 못한다는 점은 knn의 또 다른 단점이다.