K-Nearest Neighbor Algorithm
17 Apr 2017 | K-NN
이번 글에서는 K-최근접이웃(K-Nearest Neighbor, KNN) 알고리즘을 살펴보도록 하겠습니다. 이번 글은 고려대 강필성 교수님, 김성범 교수님 강의를 참고했습니다. 그럼 시작하겠습니다.
모델 개요
KNN은 새로운 데이터가 주어졌을 때 기존 데이터 가운데 가장 가까운 $k$개 이웃의 정보로 새로운 데이터를 예측하는 방법론입니다. 아래 그림처럼 검은색 점의 범주 정보는 주변 이웃들을 가지고 추론해낼 수 있습니다. 만약 $k$가 1이라면 오렌지색, $k$가 3이라면 녹색으로 분류(classification)하는 것이지요. 만약 회귀(regression) 문제라면 이웃들 종속변수($y$)의 평균이 예측값이 됩니다.
사실 KNN은 학습이라고 할 만한 절차가 없습니다. 그도 그럴 것이 새로운 데이터가 들어왔을 때, 그제야 기존 데이터 사이의 거리를 재서 이웃들을 뽑기 때문입니다. 그래서 KNN을 모델을 별도로 구축하지 않는다는 뜻으로 게으른 모델(Lazy model)이라고 부르는 사람도 있습니다. 조금 점잖게 Instance-based Learning이라고 불리기도 합니다. 데이터로부터 모델을 생성해 과업을 수행하는 Model-based learning과 대비되는 개념으로, 별도 모델 생성과정 없이 각각의 관측치(instance)만을 이용하여 분류/회귀 등 과업을 수행한다는 취지입니다.
KNN의 하이퍼파라메터(Hyper parameter)는 탐색할 이웃 수($k$), 거리 측정 방법 두 가지입니다. $k$가 작을 경우 데이터의 지역적 특성을 지나치게 반영하게 됩니다(overfitting). 반대로 매우 클 경우 모델이 과하게 정규화되는 경향이 있습니다(underfitting). 아래 그림은 범주가 두 개인 데이터의 분류 경계면을 나타낸 것입니다. $k$의 크기에 따라 분류 경계면에 단순해지는 걸 확인할 수 있습니다.
다만 KNN 알고리즘이 이러한 경계면을 직접 만드는 것은 절대 아니고, 새로운 데이터가 주어졌을 때 어느 범주로 분류되는지를 보기 좋게 시각화했다는 점에 주의하셔야 합니다.
거리 지표
KNN은 거리 측정 방법에 따라 그 결과가 크게 달라지는 알고리즘입니다. 몇 가지 살펴보겠습니다.
Euclidean Distance
가장 흔히 사용하는 거리 척도입니다. 두 관측치 사이의 직선 최단거리를 의미합니다.
\(\begin{align*}
X&=({ x }_{ 1 },{ x }_{ 2 },...,{ x }_{ n })\\ Y&=({y }_{ 1 },{ y }_{ 2 },...,{ y }_{ n })\\ { d }_{ (X,Y) }&=\sqrt { { ({ x }_{ 1 }-{y }_{ 1 }) }^{ 2 }+...+{ ({ x }_{ n }-{ y }_{ n }) }^{ 2 } } \\ &=\sqrt { \sum _{ i=1 }^{ n }{ { ({ x }_{ i }-{ y }_{ i }) }^{ 2 } } }
\end{align*}\)
예시는 아래와 같습니다.
\[{ d }_{ (A,B) }=\sqrt { { (0-2) }^{ 2 }+{ (3-0) }^{ 2 }+{ (2-0) }^{ 2 } } =\sqrt { 17 }\]
Manhattan Distance
A에서 B로 이동할 때 각 좌표축 방향으로만 이동할 경우에 계산되는 거리입니다. 뉴욕 맨해튼의 한 빌딩에서 다른 빌딩으로 이동하려면 격자 모양의 길을 따라가야 하는데요, 이를 떠올려보면 쉽습니다. Taxi cab Distance라고도 불립니다.
\[{ d }_{ Manhattan(X,Y) }=\sum _{ i=1 }^{ n }{ \left| { x }_{ i }-{ y }_{ i } \right| }\]
아래 그림(출처)의 세 경로는 맨해튼 거리 기준으로는 같은 거리입니다.
Mahalanobis Distance
변수 내 분산, 변수 간 공분산을 모두 반영하여 거리를 계산하는 방식입니다. 변수 간 상관관계를 고려한 거리 지표입니다.
\[{ d }_{ Mahalanobis(X,Y) }=\sqrt { { (\overrightarrow { X } -\overrightarrow { Y } ) }^{ T }{ \Sigma }^{ -1 }(\overrightarrow { X } -\overrightarrow { Y } ) } \\ { \Sigma }^{ -1 }=inverse\quad of\quad covariance\quad matrix\]
$X, Y$ 사이의 마할라노비스 거리를 $c$, $X$를 $(x_1, x_2)$, $Y$를 $(0,0)$로 두고 위 식을 풀면 아래와 같이 쓸 수 있습니다. 타원의 방정식 꼴입니다.
\[{ x }_{ 1 }^{ 2 }{ s }_{ 1 }+2{ x}_{ 1 }{ x }_{ 2 }{ s }_{ 2 }+{ x }_{ 2 }^{ 2 }{ s }_{ 4 }={ c }^{ 2 }\\ { \Sigma }^{ -1 }=\begin{bmatrix} { s }_{ 1 } & { s }_{ 2 } \\ { s }_{ 3 } & { s }_{ 4 } \end{bmatrix}\]
위 식에서 $c$를 1로 고정시켜 놓고, 공분산행렬을 바꾸면 마할라노비스 거리가 어떻게 달라지는지 살펴보겠습니다. 아래 그림들에 나오는 타원 위의 점들은 마할라노비스 거리 기준으로는 모두 같은 거리입니다. 공분산행렬이 항등행렬(identity matrix)일 때 마할라노비스 거리는 유클리디언 거리와 동일합니다.
\[\Sigma ={ \Sigma }^{ -1 }=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\]
\[\Sigma =\begin{bmatrix} 4 & 0 \\ 0 & 1 \end{bmatrix},\quad { \Sigma }^{ -1 }=\begin{bmatrix} 1/4 & 0 \\ 0 & 1 \end{bmatrix}\]
\[\Sigma =\begin{bmatrix} 4 & \sqrt { 2 } \\ \sqrt { 2 } & 1 \end{bmatrix},\quad { \Sigma }^{ -1 }=\begin{bmatrix} 1/2 & -\sqrt { 2 } \\ -\sqrt { 2 } & 2 \end{bmatrix}\]
바로 위 그림의 공분산은 그대로 두고, 이제는 $c$를 바꿔보겠습니다. $c$의 값에 따른 변화는 아래 그림과 같습니다.
마지막으로 유클리디언 거리와 비교해 보겠습니다. 아래와 같은 데이터가 주어졌을 때 유클리디언 거리 측정 기준으로는 데이터의 중심과 $A$와의 거리는 $B$와의 거리보다 멉니다. 하지만 마할라노비스 거리 기준으로는 $A$가 가깝습니다. 변수 간 양의 상관관계가 강해서 그 방향과 동떨어진 $B$가 마할라노비스상 거리가 꽤 멀게 계산되기 때문입니다. 이렇듯 마할라노비스 거리는 거리 측정시 변수 내 분산, 변수 간 공분산/상관관계를 모두 고려합니다.
Correlation Distance
데이터의 pearson correlation을 거리 척도로 직접 사용합니다. 개별 관측치 하나하나가 아니라 데이터 전체의 경향성을 비교하기 위한 척도입니다. 다시 말해 두 개 데이터 패턴의 유사도를 반영할 수 있습니다. 상관계수는 -1에서 1 사이의 범위를 가지므로, Correlation Distance의 범위는 0에서 2 사이입니다. 0이면 두 데이터의 패턴이 매우 유사한 것이고 2이면 그렇지 않다고 해석할 수 있습니다.
\[{ d }_{ Corr(X,Y) }=1-\rho _{ XY }\]
예컨대 아래 그림의 경우 좌측은 Correlation Distance가 가깝게(패턴이 유사), 우측은 멀게 나타날 것입니다.
Rank Correlation Distance
데이터의 Spearman Rank Correlation을 거리 척도로 직접 사용합니다. 나머지 특징은 correlation distance와 같습니다.
\[{ d }_{ RankCorr(X,Y) }=1-\rho _{ XY }\\ \rho _{ XY }=1-\frac { 6 }{ n({ n }^{ 2 }-1) } \sum _{ i=1 }^{ n }{ { (rank({ x }_{ i })-rank({ y }_{ i })) }^{ 2 } }\]
예컨대 지역별 계절 기온 순위(rank)가 아래처럼 주어졌다고 가정해 봅시다.
지역
봄
여름
가을
겨울
서울
3
1
2
4
뉴욕
3
1
2
4
시드니
2
4
3
1
그렇다면 서울-뉴욕 간 Rank correlation distance는 아래와 같습니다.
\[{ d }_{ RankCorr(Seoul,NewYork) }=1-\rho =1-1=0\\ \rho =1-\frac { 6 }{ 4({ 4 }^{ 2 }-1) } \left\{ { (3-3) }^{ 2 }+{ (1-1) }^{ 2 }+{ (2-2) }^{ 2 }+{ { (4-4 }) }^{ 2 } \right\} =1\]
서울-시드니 간 Rank correlation distance는 아래와 같습니다.
\[{ d }_{ RankCorr(Seoul,Sydney) }=1-\rho =1-(-1)=2\\ \rho =1-\frac { 6 }{ 4({ 4 }^{ 2 }-1) } \left\{ { (3-2) }^{ 2 }+{ (1-4) }^{ 2 }+{ (2-3) }^{ 2 }+{ { (4-1 }) }^{ 2 } \right\} =-1\]
best K 찾기
R 내장 데이터인 iris에 대해 KNN을 수행하였습니다. best K는 데이터마다 다르기 때문에 탐욕적인 방식으로 찾아야 합니다. 아래 그림을 볼까요?
$k$를 1부터 10까지 1씩 증가시키면서 오분류율을 점검했습니다. 그 결과 best K는 7로 확인이 되네요. 그런데 iris 말고 다른 데이터에서 $k$가 증가할 수록 오분류율이 계속 낮아진다면 $k$ 범위를 더 넓혀서 탐색할 필요가 있습니다.
아울러 best K를 찾기 위해서는 학습데이터와 검증데이터를 나누고, $k$값에 변화를 주면서 실험을 해야 하는데요. 이런 모든 과정을 대신 해주는 패키지가 R에 있어서 편리하게 사용할 수 있습니다. 분류 문제에 best K를 찾기 위한 코드는 아래와 같습니다.
# find best k (classification)
library(kknn)
knntr <- train.kknn(Target ~ ., data, kmax=10, distance=2, kernel="rectangular")
knntr$MISCLASS
knntr$best.parameters
combining rule
1-NN을 제외한 KNN은 주변 이웃의 분포에 따라 예측 결과가 충분히 달라질 수 있습니다. 가장 단순한 결정 방식은 다수결(Majority voting)입니다. 이웃들 범주 가운데 빈도 기준 제일 많은 범주로 새 데이터의 범주를 예측하는 것입니다.
가중합(weighted voting) 방식도 있습니다. 거리($d$)가 가까운(=유사도가 높은) 이웃의 정보에 좀 더 가중치를 줍니다. $1/(1+d)$, $1/(1+d^2)$, $exp(-d)$ 등 단조감소함수이기만 하면 무엇이든 가중치 산출 함수로 쓸 수 있다고 합니다.
cut-off 기준 설정
이진분류 문제를 푼다고 할 때 우리가 예측해야 할 관측치 주변 이웃의 범주 비율 정보가 ‘A : 0.7, B : 0.3’이라고 가정해 봅시다. 별 다른 처리를 하지 않는다면 우리는 이 관측치를 A로 분류하게 됩니다. 두 범주가 절반씩 있을 거라는 상식에서 비롯된 생각입니다.
그런데 범주 간 비율이 불균형한 데이터일 땐 여기에 주의를 해야 합니다. 예컨대 제조업 정상/불량 데이터를 분류하는 문제의 경우 학습데이터에선 정상 관측치가 대다수일 겁니다. 여기에서 새 관측치 주변 이웃의 범주 비율 정보가 ‘정상 : 0.8, 불량 : 0.2’이라면 불량으로 판정하는 게 합리적일 것입니다.
요컨대 컷오프 기준을 설정할 때 학습데이터 범주의 사전확률(prior probability)을 고려해야 한다는 것입니다.
KNN 수행시 주의점
KNN 수행 전 반드시 변수를 정규화(Normalization)해 주어야 합니다. 가상의 아래 표를 보시죠.
도시
인구(명)
미세먼지농도(㎍/㎥)
서울
1000만
200
시애틀
67만
40
도시별 정보를 모아서 유사한 환경을 지닌 도시를 뽑는 문제를 풀어봅시다. 위 표 기준으로는 거리/유사성 측정시 미세먼지농도 정보는 전혀 반영이 되지 않을 겁니다. 인구 변수에 해당하는 숫자가 훨씬 크기 때문입니다. 따라서 변수별로 평균과 분산을 일치시키는 정규화 작업을 반드시 KNN 적용 전 수행해 주어야 합니다.
KNN의 장단점
KNN은 학습데이터 내에 끼어있는 노이즈의 영향을 크게 받지 않으며 학습데이터 수가 많다면 꽤 효과적인 알고리즘이라고 합니다. 특히 마할라노비스 거리와 같이 데이터의 분산을 고려할 경우 매우 강건(robust)한 방법론으로 알려져 있습니다. 네이버, 카카오 등 현업에서도 KNN을 두루 사용하고 있는 것으로 전해집니다.
아울러 $k$가 1인 1-NN의 오차 범위는 다음과 같다는 사실이 증명되어 있습니다. (Idealerr=주어진 데이터에 적합 가능한 가장 이상적인 모형의 오차) 바꿔 말해 1-NN에 한해서는 모델 성능을 어느 정도 보장할 수 있다는 이야기입니다.
\[Err(1-NN)\le 2\times IdealErr\]
그러나 최적 이웃의 수(k)와 어떤 거리척도가 분석에 적합한지 불분명해 데이터 각각의 특성에 맞게 연구자가 임의로 선정해야 하는 단점이 있습니다.
또 새로운 관측치와 각각의 학습 데이터 사이의 거리를 전부 측정해야 하므로 계산 시간이 오래 걸리는 한계점이 존재합니다.
이 때문에 Locality Sensitive Hashing, Network based Indexer, Optimized product quantization 등 KNN의 계산복잡성을 줄이려는 시도들이 여럿 제안되었습니다. 인스턴스 간 거리를 모두 계산하지 않고도 마치 그렇게 한 것처럼 결과를 내는 방법론들입니다. 이에 대해서는 추후에 다시 정리할 계획입니다.
여기까지 읽어주셔서 감사합니다.
이번 글에서는 K-최근접이웃(K-Nearest Neighbor, KNN) 알고리즘을 살펴보도록 하겠습니다. 이번 글은 고려대 강필성 교수님, 김성범 교수님 강의를 참고했습니다. 그럼 시작하겠습니다.
모델 개요
KNN은 새로운 데이터가 주어졌을 때 기존 데이터 가운데 가장 가까운 $k$개 이웃의 정보로 새로운 데이터를 예측하는 방법론입니다. 아래 그림처럼 검은색 점의 범주 정보는 주변 이웃들을 가지고 추론해낼 수 있습니다. 만약 $k$가 1이라면 오렌지색, $k$가 3이라면 녹색으로 분류(classification)하는 것이지요. 만약 회귀(regression) 문제라면 이웃들 종속변수($y$)의 평균이 예측값이 됩니다.
사실 KNN은 학습이라고 할 만한 절차가 없습니다. 그도 그럴 것이 새로운 데이터가 들어왔을 때, 그제야 기존 데이터 사이의 거리를 재서 이웃들을 뽑기 때문입니다. 그래서 KNN을 모델을 별도로 구축하지 않는다는 뜻으로 게으른 모델(Lazy model)이라고 부르는 사람도 있습니다. 조금 점잖게 Instance-based Learning이라고 불리기도 합니다. 데이터로부터 모델을 생성해 과업을 수행하는 Model-based learning과 대비되는 개념으로, 별도 모델 생성과정 없이 각각의 관측치(instance)만을 이용하여 분류/회귀 등 과업을 수행한다는 취지입니다.
KNN의 하이퍼파라메터(Hyper parameter)는 탐색할 이웃 수($k$), 거리 측정 방법 두 가지입니다. $k$가 작을 경우 데이터의 지역적 특성을 지나치게 반영하게 됩니다(overfitting). 반대로 매우 클 경우 모델이 과하게 정규화되는 경향이 있습니다(underfitting). 아래 그림은 범주가 두 개인 데이터의 분류 경계면을 나타낸 것입니다. $k$의 크기에 따라 분류 경계면에 단순해지는 걸 확인할 수 있습니다.
다만 KNN 알고리즘이 이러한 경계면을 직접 만드는 것은 절대 아니고, 새로운 데이터가 주어졌을 때 어느 범주로 분류되는지를 보기 좋게 시각화했다는 점에 주의하셔야 합니다.
거리 지표
KNN은 거리 측정 방법에 따라 그 결과가 크게 달라지는 알고리즘입니다. 몇 가지 살펴보겠습니다.
Euclidean Distance
가장 흔히 사용하는 거리 척도입니다. 두 관측치 사이의 직선 최단거리를 의미합니다. \(\begin{align*} X&=({ x }_{ 1 },{ x }_{ 2 },...,{ x }_{ n })\\ Y&=({y }_{ 1 },{ y }_{ 2 },...,{ y }_{ n })\\ { d }_{ (X,Y) }&=\sqrt { { ({ x }_{ 1 }-{y }_{ 1 }) }^{ 2 }+...+{ ({ x }_{ n }-{ y }_{ n }) }^{ 2 } } \\ &=\sqrt { \sum _{ i=1 }^{ n }{ { ({ x }_{ i }-{ y }_{ i }) }^{ 2 } } } \end{align*}\)
예시는 아래와 같습니다.
Manhattan Distance
A에서 B로 이동할 때 각 좌표축 방향으로만 이동할 경우에 계산되는 거리입니다. 뉴욕 맨해튼의 한 빌딩에서 다른 빌딩으로 이동하려면 격자 모양의 길을 따라가야 하는데요, 이를 떠올려보면 쉽습니다. Taxi cab Distance라고도 불립니다.
\[{ d }_{ Manhattan(X,Y) }=\sum _{ i=1 }^{ n }{ \left| { x }_{ i }-{ y }_{ i } \right| }\]아래 그림(출처)의 세 경로는 맨해튼 거리 기준으로는 같은 거리입니다.
Mahalanobis Distance
변수 내 분산, 변수 간 공분산을 모두 반영하여 거리를 계산하는 방식입니다. 변수 간 상관관계를 고려한 거리 지표입니다.
\[{ d }_{ Mahalanobis(X,Y) }=\sqrt { { (\overrightarrow { X } -\overrightarrow { Y } ) }^{ T }{ \Sigma }^{ -1 }(\overrightarrow { X } -\overrightarrow { Y } ) } \\ { \Sigma }^{ -1 }=inverse\quad of\quad covariance\quad matrix\]$X, Y$ 사이의 마할라노비스 거리를 $c$, $X$를 $(x_1, x_2)$, $Y$를 $(0,0)$로 두고 위 식을 풀면 아래와 같이 쓸 수 있습니다. 타원의 방정식 꼴입니다.
\[{ x }_{ 1 }^{ 2 }{ s }_{ 1 }+2{ x}_{ 1 }{ x }_{ 2 }{ s }_{ 2 }+{ x }_{ 2 }^{ 2 }{ s }_{ 4 }={ c }^{ 2 }\\ { \Sigma }^{ -1 }=\begin{bmatrix} { s }_{ 1 } & { s }_{ 2 } \\ { s }_{ 3 } & { s }_{ 4 } \end{bmatrix}\]위 식에서 $c$를 1로 고정시켜 놓고, 공분산행렬을 바꾸면 마할라노비스 거리가 어떻게 달라지는지 살펴보겠습니다. 아래 그림들에 나오는 타원 위의 점들은 마할라노비스 거리 기준으로는 모두 같은 거리입니다. 공분산행렬이 항등행렬(identity matrix)일 때 마할라노비스 거리는 유클리디언 거리와 동일합니다.
\[\Sigma ={ \Sigma }^{ -1 }=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\]
바로 위 그림의 공분산은 그대로 두고, 이제는 $c$를 바꿔보겠습니다. $c$의 값에 따른 변화는 아래 그림과 같습니다.
마지막으로 유클리디언 거리와 비교해 보겠습니다. 아래와 같은 데이터가 주어졌을 때 유클리디언 거리 측정 기준으로는 데이터의 중심과 $A$와의 거리는 $B$와의 거리보다 멉니다. 하지만 마할라노비스 거리 기준으로는 $A$가 가깝습니다. 변수 간 양의 상관관계가 강해서 그 방향과 동떨어진 $B$가 마할라노비스상 거리가 꽤 멀게 계산되기 때문입니다. 이렇듯 마할라노비스 거리는 거리 측정시 변수 내 분산, 변수 간 공분산/상관관계를 모두 고려합니다.
Correlation Distance
데이터의 pearson correlation을 거리 척도로 직접 사용합니다. 개별 관측치 하나하나가 아니라 데이터 전체의 경향성을 비교하기 위한 척도입니다. 다시 말해 두 개 데이터 패턴의 유사도를 반영할 수 있습니다. 상관계수는 -1에서 1 사이의 범위를 가지므로, Correlation Distance의 범위는 0에서 2 사이입니다. 0이면 두 데이터의 패턴이 매우 유사한 것이고 2이면 그렇지 않다고 해석할 수 있습니다.
\[{ d }_{ Corr(X,Y) }=1-\rho _{ XY }\]예컨대 아래 그림의 경우 좌측은 Correlation Distance가 가깝게(패턴이 유사), 우측은 멀게 나타날 것입니다.
Rank Correlation Distance
데이터의 Spearman Rank Correlation을 거리 척도로 직접 사용합니다. 나머지 특징은 correlation distance와 같습니다.
\[{ d }_{ RankCorr(X,Y) }=1-\rho _{ XY }\\ \rho _{ XY }=1-\frac { 6 }{ n({ n }^{ 2 }-1) } \sum _{ i=1 }^{ n }{ { (rank({ x }_{ i })-rank({ y }_{ i })) }^{ 2 } }\]예컨대 지역별 계절 기온 순위(rank)가 아래처럼 주어졌다고 가정해 봅시다.
| 지역 | 봄 | 여름 | 가을 | 겨울 |
|---|---|---|---|---|
| 서울 | 3 | 1 | 2 | 4 |
| 뉴욕 | 3 | 1 | 2 | 4 |
| 시드니 | 2 | 4 | 3 | 1 |
그렇다면 서울-뉴욕 간 Rank correlation distance는 아래와 같습니다.
\[{ d }_{ RankCorr(Seoul,NewYork) }=1-\rho =1-1=0\\ \rho =1-\frac { 6 }{ 4({ 4 }^{ 2 }-1) } \left\{ { (3-3) }^{ 2 }+{ (1-1) }^{ 2 }+{ (2-2) }^{ 2 }+{ { (4-4 }) }^{ 2 } \right\} =1\]서울-시드니 간 Rank correlation distance는 아래와 같습니다.
\[{ d }_{ RankCorr(Seoul,Sydney) }=1-\rho =1-(-1)=2\\ \rho =1-\frac { 6 }{ 4({ 4 }^{ 2 }-1) } \left\{ { (3-2) }^{ 2 }+{ (1-4) }^{ 2 }+{ (2-3) }^{ 2 }+{ { (4-1 }) }^{ 2 } \right\} =-1\]best K 찾기
R 내장 데이터인 iris에 대해 KNN을 수행하였습니다. best K는 데이터마다 다르기 때문에 탐욕적인 방식으로 찾아야 합니다. 아래 그림을 볼까요?
$k$를 1부터 10까지 1씩 증가시키면서 오분류율을 점검했습니다. 그 결과 best K는 7로 확인이 되네요. 그런데 iris 말고 다른 데이터에서 $k$가 증가할 수록 오분류율이 계속 낮아진다면 $k$ 범위를 더 넓혀서 탐색할 필요가 있습니다.
아울러 best K를 찾기 위해서는 학습데이터와 검증데이터를 나누고, $k$값에 변화를 주면서 실험을 해야 하는데요. 이런 모든 과정을 대신 해주는 패키지가 R에 있어서 편리하게 사용할 수 있습니다. 분류 문제에 best K를 찾기 위한 코드는 아래와 같습니다.
# find best k (classification)
library(kknn)
knntr <- train.kknn(Target ~ ., data, kmax=10, distance=2, kernel="rectangular")
knntr$MISCLASS
knntr$best.parameters
combining rule
1-NN을 제외한 KNN은 주변 이웃의 분포에 따라 예측 결과가 충분히 달라질 수 있습니다. 가장 단순한 결정 방식은 다수결(Majority voting)입니다. 이웃들 범주 가운데 빈도 기준 제일 많은 범주로 새 데이터의 범주를 예측하는 것입니다.
가중합(weighted voting) 방식도 있습니다. 거리($d$)가 가까운(=유사도가 높은) 이웃의 정보에 좀 더 가중치를 줍니다. $1/(1+d)$, $1/(1+d^2)$, $exp(-d)$ 등 단조감소함수이기만 하면 무엇이든 가중치 산출 함수로 쓸 수 있다고 합니다.
cut-off 기준 설정
이진분류 문제를 푼다고 할 때 우리가 예측해야 할 관측치 주변 이웃의 범주 비율 정보가 ‘A : 0.7, B : 0.3’이라고 가정해 봅시다. 별 다른 처리를 하지 않는다면 우리는 이 관측치를 A로 분류하게 됩니다. 두 범주가 절반씩 있을 거라는 상식에서 비롯된 생각입니다.
그런데 범주 간 비율이 불균형한 데이터일 땐 여기에 주의를 해야 합니다. 예컨대 제조업 정상/불량 데이터를 분류하는 문제의 경우 학습데이터에선 정상 관측치가 대다수일 겁니다. 여기에서 새 관측치 주변 이웃의 범주 비율 정보가 ‘정상 : 0.8, 불량 : 0.2’이라면 불량으로 판정하는 게 합리적일 것입니다.
요컨대 컷오프 기준을 설정할 때 학습데이터 범주의 사전확률(prior probability)을 고려해야 한다는 것입니다.
KNN 수행시 주의점
KNN 수행 전 반드시 변수를 정규화(Normalization)해 주어야 합니다. 가상의 아래 표를 보시죠.
| 도시 | 인구(명) | 미세먼지농도(㎍/㎥) |
|---|---|---|
| 서울 | 1000만 | 200 |
| 시애틀 | 67만 | 40 |
도시별 정보를 모아서 유사한 환경을 지닌 도시를 뽑는 문제를 풀어봅시다. 위 표 기준으로는 거리/유사성 측정시 미세먼지농도 정보는 전혀 반영이 되지 않을 겁니다. 인구 변수에 해당하는 숫자가 훨씬 크기 때문입니다. 따라서 변수별로 평균과 분산을 일치시키는 정규화 작업을 반드시 KNN 적용 전 수행해 주어야 합니다.
KNN의 장단점
KNN은 학습데이터 내에 끼어있는 노이즈의 영향을 크게 받지 않으며 학습데이터 수가 많다면 꽤 효과적인 알고리즘이라고 합니다. 특히 마할라노비스 거리와 같이 데이터의 분산을 고려할 경우 매우 강건(robust)한 방법론으로 알려져 있습니다. 네이버, 카카오 등 현업에서도 KNN을 두루 사용하고 있는 것으로 전해집니다.
아울러 $k$가 1인 1-NN의 오차 범위는 다음과 같다는 사실이 증명되어 있습니다. (Idealerr=주어진 데이터에 적합 가능한 가장 이상적인 모형의 오차) 바꿔 말해 1-NN에 한해서는 모델 성능을 어느 정도 보장할 수 있다는 이야기입니다.
\[Err(1-NN)\le 2\times IdealErr\]그러나 최적 이웃의 수(k)와 어떤 거리척도가 분석에 적합한지 불분명해 데이터 각각의 특성에 맞게 연구자가 임의로 선정해야 하는 단점이 있습니다.
또 새로운 관측치와 각각의 학습 데이터 사이의 거리를 전부 측정해야 하므로 계산 시간이 오래 걸리는 한계점이 존재합니다.
이 때문에 Locality Sensitive Hashing, Network based Indexer, Optimized product quantization 등 KNN의 계산복잡성을 줄이려는 시도들이 여럿 제안되었습니다. 인스턴스 간 거리를 모두 계산하지 않고도 마치 그렇게 한 것처럼 결과를 내는 방법론들입니다. 이에 대해서는 추후에 다시 정리할 계획입니다.
여기까지 읽어주셔서 감사합니다.
Comments