Hello Coding 알고리즘
10. KNN 알고리즘 k-nearest neighbors algorithm
KNN알고리즘은 k개의 가장 가까운 이웃 데이터를 이용해 '분류'와 '회귀분석'을 할 수 있는 알고리즘이다.
보통 N개의 전체 데이터가 있을 때, 살펴볼 이웃 데이터인 k는 N의 제곱근으로 정한다(sqrt(N))
- 분류 : 그룹으로 나누기
- 회귀 : (숫자로 된) 반응을 예측하기
오렌지와 자몽 분류하기
어떤 과일 A가 오렌지인지 자몽인지 어떻게 분류할 수 있는가?
- 일반적으로, 더 크고 붉은 과일이 자몽이다.
KNN알고리즘으로 오렌지/자몽 분류하기
- 색상과 크기를 기준으로 2차원 그래프에 오렌지들과 자몽들을 점으로 나타낸다.
- A의 색상과 크기를 기준으로 그래프에 나타낸다.
- 그래프상에서 A와 가장 가까운 K개의 이웃들을 살펴본다.
- 가까운 이웃의 기준은 거리공식 (피타고라스의 정리, 또는 코사인 유사도)을 이용한다.
- 이 때 거리는 두 숫자 집합의 유사도를 나타낸다. (작을수록 유사함)
- K개의 이웃들 중 오렌지가 더 많다면 오렌지로, 자몽이 더 많다면 자몽으로 분류한다.
추천 시스템 만들기
넷플릭스 영화 추천 시스템은 어떻게 만들어지는가?
- 오렌지와 자몽 분류처럼, 고객 사이의 유사도에 따라서 고객들을 그래프상에 나타낸다.
- 영화를 추천해 주어야 하는 고객 A도 그래프상에 나타낸다.
- A와 취향이 비슷한(거리상 가장 가까운) K명의 고객을 찾는다.
- A와 유사한 K명의 고객들이 좋아하는 영화를 A에게도 추천한다.
그렇다면 고객 사이의 유사도는 어떻게 구하는가?
특징 추출
오렌지/자몽을 분류할 때, '크기'와 '붉은 정도'라는 특징을 기준으로 분류했다.
고객을 좌표 상에 나타내려면 어떻게 해야 하는가?
예를 들어 영화 장르에 대한 선호도를 기준으로 좌표상에 나타낼 수 있다
- 코미디
- 액션
- 드라마
- 공포
- 로맨스
-> 5차원 그래프 상에서의 거리를 계산하게 된다.
회귀 분석 regression
어떤 영화에 대해 A가 어떤 평점을 줄지 예측하고 싶다면?
- A와 유사도가 높은 K명의 고객들을 찾는다.
- K명의 각 고객들이 그 영화에 대해 평점을 몆 점 줬는지 확인한다.
- 그 평점들의 평균을 구한다.
이를 빵집에서 오늘 빵을 몇 개 만들어야 할지 예측하는 데도 사용할 수 있다. (261p)
좋은 특징 고르기
KNN 알고리즘을 사용할 때는 올바른 특징을 고르는 것이 중요하다.
영화추천서비스의 경우..
- 추천하고자 하는 대상과 직접 관련이 있는 특징
- 편향되지 않은 특징
- 예 : 코미디 영화만 평가를 남기거나, 액션 영화만 평가를 남긴 고객의 평점은 편향되어 있다.
but 좋은 특징을 고르는 데 있어 정답은 없다. 여러 다른 관점에서 살펴보아야.
머신러닝의 소개
KNN은 머신러닝에도 사용될 수 있다.
추천 시스템도 머신러닝의 일종이다.
OCR 광학적 문자 인식 Optical Character Recognition
사진을 찍으면 그 사진 속의 글자를 인식해 주는 기술.
- 모든 글자 그림을 살펴보고, 그 그림들의 특징을 뽑아낸다.
- 이를 트레이닝training이라고 한다.
- 새로운 그림이 주어지면, 그 그림의 특징을 뽑아서 가장 가까운 글자를 구별해낸다.
OCR에 사용되는 특징 추출은 오렌지/자몽 문제보다 훨씬 복잡하다. 하지만 원리는 같다!
비슷한 원리가 음성 인식, 얼굴 인식에도 사용된다!
스팸 필터 만들기
'나이브 베이즈 분류기 Naive Bayes classifier' 라는 알고리즘을 사용한다.
- 스팸인/스팸이 아닌 이메일 제목을 받는다. 제목을 단어들로 분리한다.
- 어떤 이메일 제목에 나타난 단어가 스팸메일에 나타날 확률이 높은지, 아닌지 판별한다.
예를 들어 '대출'라는 단어가 스팸 메일에서만 발견될 때, 이 단어가 포함된 메일이 오면 스팸으로 분류될 것이다.
주식 시장 예측하기
과거의 정보만으로 확실히 미래를 맞추기는 어렵다.
예를 들어 주식 시장을 예측하기 위해서 어떤 특징을 골라야 하는가? 정답이 없음.
KNN알고리즘 관련 개념들
- 정규화 normalization
- 스케일링 scaling : 평균값을 구한 다음, 그 값으로 전체 점수 나누기
- 가중치 : 중요 고객이 있다면 그 고객의 점수에 가중치를 주어 비교할 수 있다.
