[Algorithm] K-nearest neighbors algorithm: KNN 알고리즘

KNN 알고리즘은 추천 시스템의 기본이 되는 알고리즘이다. 우리는 한 번 쯤 이미 비슷한 경험을 해본 적이 있다. 넷플릭스나 와챠에서 나와 비슷한 성향을 가진 사람이 본 영상을 추천받기도 하고, 유튜브나 페이스북에서 친구들이 봤거나 좋아요, 댓글달기와 같이 참여한 게시물 또는 영상이 추천된다.

 

여기에 조미료처럼 머신러닝 한 스푼을 넣어주면 내가 봐 온 영화를 토대로 어떤 영화를 내가 좋아할 지 추천하는 것도 가능하고, 새로나온 영화에 대해서 내가 별점을 얼마나 줄 지 예측할 수도 있다.

 

하지만 머신러닝은 단순한 조미료가 아니므로 ( 참고로 한국 구글에서 머신러닝 부트캠프를 무료로 진행한다 ) 지금은 아 그렇구나~ 정도로만 하고 넘어가도록 하자.

 

K-nearest neighbors algorithm ( KNN 알고리즘 )

혹시 귤의 종류를 구분할 수 있는가?

제주도에는 우리가 흔히 귤이라고 부르는 과일이 여러 종류 있다.

솔직히 위 사진이랑 조금이라도 다르게 생기면 나는 구분하기를 포기하던지 속의 색깔이나 맛을 보고 판단을 하려고 할테다. 그러나 안타깝게도 우리에게 주어진 것은 위 사진과 같은 이미지 뿐이고, 아래의 이미지를 위의 5가지 종류 중 하나로 구분해야 한다.

대체 이 사진은 어디에 속해야 하는 걸까?

 

이 이미지를 구분하기 위해서는 몇 가지 조건이 필요하다.

1. 수많은 귤이 색상과 크기, 모양에 따라 이미 분류되어 있다.
2. 새로운 사진을 입력받으면 1의 분류조건에 따라 분류한다.

위의 예시를 분류해서 그래프로 나타내면 아래와 같다.

입력 이미지의 위치는 빨갛다고 하기에는 주황색이 선명하고, 가로가 분명히 세로보다 길긴 하지만 외관이 한라봉에 가깝다.

그리고 위의 그래프에서 위치를 잡아보면 천혜향에 가장 가깝다는 것을 확인할 수 있다.

이렇게 그래프를 그려놓고, 가까운 이웃을 검사하여 이미지를 종류로 분류하는 알고리즘이 KNN 알고리즘이다.

 

( 참고로 이미지는 레드향이다. KNN은 만능이 아니다. )

 

가장 앞서 나는 KNN 알고리즘이 추천 시스템에 쓰인다고 언급했다. 분류에 쓰이는 것은 알 수 있는데, 추천 시스템에서는 어떻게 사용될까?

 

우리가 넷플릭스에서 일한다고 가정해보자. A라는 사람에게 영화를 추천하는 알고리즘을 만들어야한다. 크게 보면 이 문제도 위의 귤 분류하기와 다르지 않다는 것을 알 수 있다.

 

A라는 사람을 "분류" 해보자.

위의 예제에서는 귤을 색깔과 모양에 따라 분류했다.

넷플릭스는 영화나 드라마를 제공하는 서비스이므로 우리는 A라는 사람이 선호하는 장르와 같이 취향에 따라 분류해야 한다.

 

먼저, 모든 고객을 그래프에 나타내자.

B ~ i 까지의 사용자를 그래프에 나타내었다. 네모박스의 두번째 줄은 가잘 좋아하는 영화이다.

기억할 지 모르겠지만, 넷플릭스에 가입할 때에는 자신의 취향에 맞는 영화 또는 드라마를 3가지 정도 선택해야한다.

A는 넷플릭스를 이용하기 위해 위의 그래프에 나와있는 영화 3가지를 선택했다고 가정하자. 그리고 그결과가 용의자 X의 헌신, 존윅, 범죄와의 전쟁 이라면 어떤 영화를 추천해줄 수 있을까?

A가 좋아하는 영화		유저 ID
7번방의 선물	<= 을 가장 좋아하는 유저:	F
러브 액츄얼리	<= 을 가장 좋아하는 유저:	B
범죄와의 전쟁	<= 을 가장 좋아하는 유저:	D

A가 좋아하는 영화에 따라 다른 유저들의 포지션과 비슷하게 위치할 수 있고, 그 위치로 부터 가까운 유저의 가장 좋아하는 영화를 추천할 수 있다.

 

말이 어렵다.

그림으로 이해하자.

선택한 결과를 바탕으로 A의 위치를 결정했더니 A와 가장 가까운 곳에 위치한 유저는 i 이고, i의 가장 좋아하는 영화는 '기생충' 이다.

따라서, 우리는 A에게 기생충을 추천해줄 수 있다.

 

만약 자료구조를 구현해본 적이 있다면, 생각한 것을 코드로 옮길 수 있다는 그 가능성을 알게 되었을 것이다.

 

마찬가지로 KNN 알고리즘 또한 코드로 구현할 수 있으리라.

 

그런데, 위에서 만든 추천 시스템에는 아주 큰 맹점이 있다. 만약 모든 유저를 그래프로 나타내고 새로운 유저가 들어왔을 때 영화를 추천해야 한다면, 새로운 유저가 유입될 때마다 기존 유저를 그린 새로운 그래프가 필요할까?

 

만약 그래프의 기준이 유저가 아니라 장르라면 어떻게 될까?

혹은 출연자에 따라 추천영화가 달라질 수도 있을까?

 

꼭 한 번쯤은 고민해보길 바란다.