k-NN 알고리즘은 분류 알고리즘의 하나로 로직이 간단하여 구현하기 쉽다. 하지만 학습 모델이 따로 없고, 전체 데이터를 스캔하여 데이터를 분류하기 때문에 데이터의 양이 많아지면 분류 속도가 현저하게 느려진다. k-NN 알고리즘은 단순 분류 작업 이외에도 협업 필터링을 구현 할 때 사용되기도 한다 (참고: https://github.com/guymorita/recommendationRaccoon).
관련 키워드: kNN, 분류, 기계학습, node.js
k-NN 알고리즘이란?
k-NN 알고리즘은 지도 학습(Supervised Learning)의 한 종류로 레이블이 있는 데이터를 사용하여 분류 작업을 하는 알고리즘이다. 알고리즘의 이름에서 볼 수 있듯이 데이터로부터 거리가 가까운 k개의 다른 데이터의 레이블을 참조하여 분류하는 알고리즘이다. 주로 거리를 측정할 때 유클리디안 거리 계산법을 사용하여 거리를 측정하는데, 벡터의 크기가 커지면 계산이 복잡해진다.
kNN의 장점
- 알고리즘이 간단하여 구현하기 쉽다
- 수치 기반 데이터 분류 작업에서 성능이 좋다
kNN의 단점
- 학습 데이터의 양이 많으면 분류 속도가 느려진다 (사실 사전 계산을 할 수 없기 때문에 학습 과정이 따로 없기 때문에 분류 속도가 느리다)
- 차원(벡터)의 크기가 크면 계산량이 많아진다
nodeml을 사용한 kNN 알고리즘 실험
아래의 코드는 nodeml 라이브러리를 사용하여 kNN 알고리즘을 사용하는 예제이다. nodeml에는 유클리드 거리를 사용하여 k 개의 유사 데이터를 찾고, 가중치 모델을 적용하여 kNN이 구현되어 있다.
'use strict';
const {sample, kNN, evaluate} = require('nodeml');
const bulk = sample.iris();
knn.train(bulk.dataset, bulk.labels);
result = knn.test(bulk.dataset, 5);
let evaluation = evaluate.accuracy(bulk.labels, result);
console.log(evaluation.micro.PRECISION, evaluation.macro.PRECISION);
kNN 구현하기
이 글에서는 node.js를 사용하여 kNN의 구현 방법을 소개하고, 몇 가지 문제 사항에 대한 해결 방법을 다룰 예정이다. 다룰 문제를 요약하면 아래와 같다.
- 벡터 계산시 속도 문제 개선 방법
- 유사 데이터 서칭 속도 개선 방법
- 가중치 모델을 사용한 정확도 개선
알고리즘 구현 순서는 아래와 같다. 알고리즘을 구현하는 과정에서 위의 문제점들을 해결하는 방법을 설명한다.
- 사전 학습 과정
- 유사 데이터 검색 및 k개의 데이터 선택
- 정답 레이블 선정
사전 학습 과정
kNN을 단순하게 구현하면 각 데이터를 분류할때마다 전체 데이터를 탐색해야하기 때문에 데이터가 조금만 커져도 속도가 상당히 느려진다. 학습 데이터에 대해 사전에 사전을 구축하여 유사 데이터를 먼저 검색 할 수 있으면 속도를 개선 할 수 있다.
수치화 된 데이터를 학습할 때에는 벡터 크기가 고정되어 있지만, 텍스트와 같은 데이터를 분류할 때는 벡터가 크고, 데이터에서 대부분의 벡터의 값이 0인 경우가 많다 (값이 존재하는 경우가 희소하다). 이러한 데이터를 전체를 탐색하여 계산하게 될 경우 계산량만 많아지고 정확도는 떨어 질 수도 있다. 이 글에서는 희소 행렬의 경우에 중복되는 feature를 가지고 있는 데이터를 우선 탐색하여, 탐색된 데이터에 대해서만 거리를 계산하여 결과를 도출하는 방법을 사용한다.
[ { "삼성": 1, "갤럭시": 3, "노트": 5 },
{ "갤럭시": 3, "노트": 5 , "폭발": 3},
{ "LG": 1, "G4": 1, "스마트폰": 1 }]
예를들어 위와 같은 데이터가 있다고 하자. “삼성 갤럭시 노트”를 포함한 데이터는 “LG G4 스마트폰”을 포함한 데이터 보다는 “갤럭시 노트 폭발”과 관련이 있을 확률이 높다. 이 때 각 거리는 “삼성 갤럭시 노트”-“갤럭시 노트 폭발”의 거리는 1+(0+0)+9이고, “삼성 갤럭시 노트”-“LG G4 스마트폰”의 거리는 (1+9+25)+(1+1+1)이다 (거리 계산시 루트는 제외한 유클리드 거리값으로 표현하였다). 여기서 굵게 표시한 부분은 “삼성 갤럭시 노트”의 feature가 계산된 부분이다. 두번째 계산과 같이 중복되는 feature가 없는 경우에는 기본적으로 자신의 크기만큼을 가지고 다른 데이터의 크기를 추가적으로 가지게된다. 따라서 다른 데이터가 자신의 feature를 가지고 있을 때 거리가 가까울 가능성이 높다.
let itemBase = {};
let featureBase = {};
for (let i = 0; i < data.length; i++) {
let item = data[i];
if (!itemBase[i]) itemBase[i] = {};
for (let feature in item) {
if (!featureBase[feature]) featureBase[feature] = [];
itemBase[i][feature] = item[feature] * 1;
featureBase[feature].push(i)
}
}
위의 코드는 데이터를 적재 할 때 itemBase에 item 별로 보유 feature 정보를 적재하고, featureBase에 feature 별로 가지고있는 item을 적재한다. itemBase와 featureBase를 사용해서 각 데이터를 분류 할 때, 전체 데이터를 탐색하지 않고 분류 결과를 도출 할 수 있다.
유사 데이터 검색 및 k개의 데이터 선택
let selectedData = {};
for (let feature in testData)
for (let i = 0; i < featureBase[feature].length; i++)
selectedData[featureBase[feature][i]] = true;
먼저 유사 데이터를 선정한다. 원래는 전체 데이터를 탐색하며 거리 계산을 해야하지만, 학습 과정에서 생성한 featureBase를 사용하여 자신과 같은 feature를 가지고 있는 다른 데이터만 추출 할 수 있다.
let selectedData = {};
for (let feature in testData)
for (let i = 0; i < featureBase[feature].length; i++)
selectedData[featureBase[feature][i]] = true;
let list = [];
for (let item in selectedData) {
let thisLabel = labels[item];
let compare = itemBase[item];
let euclidean = 0;
let features = {};
for (let feature in testData)
features[feature] = true;
for (let feature in compare)
features[feature] = true;
for (let feature in features) {
let dist = (testData[feature] ? testData[feature] : 0) - (compare[feature] ? compare[feature] : 0);
dist = dist * dist;
euclidean += dist;
}
euclidean = Math.sqrt(euclidean);
list.push({label: thisLabel, distance: euclidean});
}
list.sort((a, b) => a.distance - b.distance);
list = list.splice(0, k);
위의 코드는 선택된 데이터과 분류 대상의 거리를 구하여 낮은 거리순으로 정렬한 후 k개 만큼을 선택하는 것이다. 희소 행렬의 경우 0인 데이터들은 계산할 필요가 없기 때문에 해시 형태로 데이터를 가공하여 계산하면 유클리디안 거리 계산시 계산량을 줄일 수 있다.
정답 레이블 선정
kNN에서는 기본적으로 k개를 선정한 후 k개의 레이블 중 많이 나온 레이블을 정답으로 선택한다. 이 방법의 경우 k가 짝수이거나 전체 클래스의 수의 배수일 때 선택이 어려울 수 있다.
| 순위 | 레이블 | 대상과의 거리 |
|---|---|---|
| 1 | 경제 | 0.1 |
| 2 | 정치 | 0.2 |
| 2 | 정치 | 0.2 |
| 4 | 경제 | 0.3 |
| 5 | 경제 | 0.4 |
| 6 | 정치 | 0.5 |
예를들면 k를 4로 했을 때, k개의 레이블이 위와 같이 나온다면 정답을 선정하기가 어려워진다. 경제 카테고리의 경우 1등과 4등 2개가 나오고, 정치의 경우 2등과 3등이고 거리의 합도 두 카테고리 모두 0.4이다. 하지만 k가 3일 때에는 정치가 2개이므로 정치를 선정하면 된다. 이와 같이 kNN에서는 k의 값을 전체 클래스의 수를 고려하여 중복되도록 나와도 선정 할 수 있도록 설정해주어야한다. 일반적으로(특히 이진분류에서)는 k 값을 홀수로 설정한다.
let answer = {};
for (let i = 0; i < list.length; i++) {
if (!answer[list[i].label]) answer[list[i].label] = {cnt: 0, val: 0};
answer[list[i].label].val += list[i].distance * Math.log(i + 1);
answer[list[i].label].cnt++;
}
let min = -1, selected = null;
for (let label in answer) {
answer[label].val = answer[label].val / answer[label].cnt;
if (min === -1) {
min = answer[label].val;
selected = label;
continue;
}
if (answer[label].val < min) {
min = answer[label].val;
selected = label;
}
}
위의 코드는 k개의 선정된 데이터를 순위 및 거리를 바탕으로 가중치를 설정하여 레이블을 선정하는 코드이다. 간단히 거리와 순위의 로그 값을 곱하고 전체 등장한 빈도수로 나누어 평균을 계산하여 정답을 선정한 것이다. 이외에도 다양한 가중치 모델을 적용하여 정확도를 향상 시킬 수 있다.