kNN 알고리즘

최근, 저자는 새로운 식사경험을 제공하는 식당에 대한 기사를 읽었다. 그 식당은 완벽히 어두운 환경에서 식사를 할 수 있는 콘셉트로, 식사할 때 시각적인 요소를 배제 하면 미각과 후각을 향상시킬 수 있다는 아이디어에 근간한 것이었다. 고객은 보이지 않는 음식을 접할 때, 먼저 맛에 대한 빠른 정보수집(양념, 향, 질감 은 어떠한지, 음식이 짠지 달콤한지와 같은 것들) 단계를 거친다. 그리고 이전에 그가 경험했던 음식들과 비교하여 현재 먹고 있는 음식에 대한 경험을 향상시킨다. 이러한 단계는 머신러닝에서 데이터를 분류할 때 가장 비슷하고 가장 근접한 범주로 데이터들을 분류하는 최근접 방식과 비슷하다. 이 챕터에서는 최근접 방식을 이용한 데이터분류에 대해 학습할 것이다. 

• 학습하게 될 내용

1. 최근접 이웃 정의하기와 왜 그들이 lazy leaner들로 간주되는가?
2. 거리를 이용한 두 가지 예시의 일치성 측정방법들
3. 유방암 진단을 해주는 kNN알고리즘을 R로 실습 

kNN분류의 이해

간단히 말해 kNN방식 은 분류되어있지 않은 레코드들을 분류된 레코드들 중 가장 비슷한 속성을 가진 레코드로 할당하는 것이다. 이론은 매우 간단하지만 kNN방식은 매우 효과적이며 다음과 같은 사례에서 성공적으로 사용되었다. 


1. 이미지와 비디오로 구성된 광학적 문자 인식(OCR)과 안면인식을 포함한 컴퓨터 비전응용 분야
2. 사용자가 추천 받은 영화에 대한 선호도 예측(Netflix사)
3. 특정한 단백질 또는 질병 발견을 위한 유전적 데이터 패턴 확인 


일반적으로 최근접이웃 분류방식은 속성들과 목표클래스들의 관계가 많고, 복잡하며 또는 매우 이해하기 힘들지만 비슷한 클래스 타입의 항목들은 꽤 [동질적인 경향]을 보일 때 아주 적합하다 한편, 그룹 간에 명확한 차이가 없으면 이 알고리즘은 대체로 그룹 간 경계를 구분하는데 효과적이지 못하다. 


 


kNN알고리즘은 레코드들이 ‘명목변수’에 의해 몇 가지 그룹으로 분류된 실습 dataset으로 시작된다. 이제 우리는 ‘실습 dataset’과 같은 속성의 변수를 가지고 있지만 레코드들이 분류되지는 않은 ‘테스트 dataset’을 가지고 있다고 가정하자. 테스트 dataset의 각각의 레코드들에 대해, kNN은 실습 dataset의 가장 동일한(동일성 부문으로 가장 가까운) k개의 레코드들에 매칭해준다. 그리고 test 레코드들은 k개의 가장 가까운 이웃의 가장 많은 클래스에 할당된다. 


이 과정을 설명하기위해 다시 처음에 언급된 식당사례로 돌아가자. 우리가 미지의 음식을 먹기 전에, 우리는 과거에 먹은 음식에 대한 기록을 데이터로 가지고 있다. 이것을 감안하여, 우리는 음식에 2가지 속성변수를 고려한다. 
1. 바삭함(범위는 1점~10점) 2. 달콤함(범위는 1점~10점) 그 다음으로 음식들을 과일, 야채, 단백질 3가지 그룹(클래스)으로 분류했다. 
 


kNN알고리즘은 속성변수에 의해 다차원의 공간이 존재 하는데, 이 사례에서는 속성변수가 2개(바삭함, 달콤함)이므로 2차원의 공간이 존재한다. 다음의 표를 보면 비슷한 그룹의 음식끼리 같은 부분에 모여 있는 것을 확인할 수 있다. 
 
위의 2차원 공간을 봤을 때, 토마토는 야채와 과일 중 어느 클래스에 속할까? 이 질문은 kNN알고리즘으로 대답 할 수 있다. 

거리 계산

토마토의 최근접 이웃을 찾으려면 거리계산 함수가 필요하다. 거리계산에는 많은 방법이 있지만 kNN에서는 주로 유클리디안 거리방식을 사용한다. 유클리디안 거리는 단순히 두 개의 점을 잇는 방법으로, 위 그림에서는 토마토와 근접한 다른 음식들의 거리를 계산한 후, 그 중 최소의 거리를 갖는 점이 속한 클래스를 토마토의 클래스로 지정한다. 

TIP. 
유클리디안 거리방식 : 점을 잇는 최소거리를 제공한다.(그냥 ONLY직선으로 선을 그은 것) 다른 일반적인 방법으로는 맨하튼 거리 방식이 있다.(맨하탄 거리 방식 : 건물이 많은 도시에서 블록을 가지고 거리를 재는 방법, Not직선 최단거리) 
 
여기서 p와 q는 비교되어지는 대상(구해지고자 하는 거리의)이며 각각은 n개의 속성을 가지고 있다. 여기서 p1항은 p가가지고 있는 첫 번째 속성값을 뜻하며, q1역시 q가 가지고 있는 첫 번째 속성값을 말한다. 예를 들어, 위의 사례에서 토마토와 껍질콩 사이의 유클리디안 거리를 구하는 공식은 다음과 같다. 여기서는 dataset이 2개의 속성(바삭함, 달콤함)을 가지므로 n값은 2가 된다. 

 


마찬가지로 토마토와 근접한 다른 음식들과의 거리를 구한 표는 다음과 같다. 
 
(유클리디안 거리가 가장 최소화 되는)오렌지가 토마토와 가장 거리가 가까우므로 토마토의 종류를 오렌지의 종류인 과일로 할당한다. 이건 k=1 인 방법이다. 만약 k=3을 한다면, 최근접 이웃 3개(포도, 견과, 오렌지)중에 어떤 그룹이 가장 많이 나왔는지를 투표해야 한다. 이때 3개중 2개가 과일이므로 역시 토마토는 과일그룹에 속하게 된다. 

k개수 최적화

미래 데이터를 얼마나 잘 일반화 시키는 지는 몇 개(k개)의 이웃을 선정하는 지에 달려있다. 학습데이터의 변수가 너무 많은 것(overfitting)과 너무 적은 것(underfitting)의 균형은 항상 문제시되는 것인데 이것을 bias-variance tradeoff문제라고 한다. 큰 k값을 선택하는 것은 노이즈 데이터에 의한 변동을 줄일 수 있지만 작고 중요한 패턴을 무시하는 위험이 있다. 예를 들어, 만약 k를 학습 dataset의 모든 레코드 수만큼의 큰수로 결정했다면, 새로운 레코드의 클래스는 항상 학습 dataset의 레코드들 중 대다수를 차지하는 클래스로 분류 될 것이다. 따라서 새로운 테스트 데이터가 들어와도 ‘최근접 이웃’이 누구냐에 관계없이 그 dataset에 주류 클래스를 택하게 된다. 


반대로 단일한 최근접 이웃을 사용하는 것은(k=1) 분류되는 레코드에 지나치게 영향을 줄 수 있는 노이즈 데이터 및 극단 값을 허용하여 잘못된 클래스 분류를 야기할 수 있다. 예를 들어, 테스트 dataset의 레코드가 잘못 분류된 레코드와 최근접 할 경우, 다른 주변 이웃들(옳게 분류된)의 클래스와는 무관하게 잘못 분류될 수 있다. 그러므로 가장 적합한 k값 선정을 위해서는 두 극단을 피해야한다. 


아래 그림은 k값 따른 ‘결정 경계(decision boundary)’의 형태를 보여준다. 우리는 큰 k값보다 작은 k값에서 나타나는 결정 경계선이 학습데이터에 더 정교하게 맞아 들어가는 걸 볼 수 있다. 하지만 가장 중요한 문제는 직선방향의 경계 혹은 곡선방향의 경계 중 어떤 것이 더 데이터 개념을 잘 설명하는 진 알 수 없다는 것이다. 


 


일반적으로 k값을 정하는 것은 개념의 난이도 그리고 레코드 개수에 따라 달라진다. 보통은 k값을 3에서 10으로 정한다. 또 다른 보편적인 방법으로는 레코드 개수에 루트를 씌운 값을 k로 정하는 방법이 있다. 예를 들어, food 데이터사례를 보면, dataset내 레코드 개수가 15개이기 때문에 15에 루트를 씌운 3.87을 이용하여 k값을 4(3.87에 근사한 정수)로 정하는 식이다. 하지만 이러한 방법이 항상 최적의 k값을 제공하지는 않는다. 다른 대안으로는 k값을 수정하면서 테스트dataset들에 반복하여 분류를 시행해본 후 가장 좋은 분류를 한 k값을 선정하는 방식이 있다. 한편, 데이터에 잡음이 끼어있고(noisy) 방대하여 학습데이터를 잘 설명할 수 없다면 k의 개수를 선정하는 것은 중요하지 않고, 크고 더 대표성을 가지는 테스트 dataset이 더 중요하다. 왜냐하면 모델의 애매한 컨셉들도 최근접 이웃으로 낙점될만한 충분하게 많은 양의 변수들이 있을 것이기 때문이다. 


TIP. 
잘 쓰지는 않지만 또 다른 방법으로는 k의 개수를 크게 선정한 후 가중투표 과정을 통해 분류하는 방법도 있다. 

kNN알고리즘을 위한 사전준비

일반적으로 ‘속성’은 kNN알고리즘을 실행하기 전에 표준화하여 사용한다. 왜냐하면 거리(distance)공식은 속성값을 종속변수로 가지는데, 만약 한 속성의 값이 매우 크다면 계산되어지는 거리 값이 그 하나의 속성에 강한 영향을 받을 수 있기 때문이다. 이전 사례인 FOOD 데이터에는 이러한 문제가 없었는데, 그 이유는 두 속성의 값들이 모두 범위가 1에서 10이었기 때문이다. 


그러나 이번에는 FOOD데이터에 Scoville scale을 사용하여 ‘매움’을 나타내는 속성변수를 하나 추가해보자. Scoville scale은 매움의 정도를 표준화 시킨 것으로 그 값이 0부터 100만까지 존재한다. 이때 유클리드 거리방식에 의해 음식별 거리를 계산한다면 매움 속성값의 넓은 범위(거리 값에 다른 속성들보다 크게 영향을 준다.) 때문에 바삭함,달콤함 속성의 기여도는 무시될 수 있다. 


따라서 우리가 해야 할 일은 다양한 변수들이 거리에 미치는 기여도를 상대적으로 같은 기준에서 볼 수 있도록 줄이거나 재조정하는 것이다. FOOD데이터 사례를 보면 바삭함과 달콤함의 속성값이 1~10까지이었기 때문에 ‘매움’ 속성도 1~10으로 변환할 필요가 있다. 다음은 2가지 데이터 정규화 변환방법이다. 
1. 전통적으로 쓰는 재조정 방법은 최소-최대 정규화변환이다. 이 방법을 쓰면 모든 변수의 값이 0에서 1사이로 조정된다.
2. 또 다른 일반적인 방법은 Z-SCORE 표준화 방식이며 평균과 표준편차로 변수를 정규화한다.
3. 한편, 명목변수로는 유클리드 거리방법을 사용할 수 없기 때문에 명목변수를 숫자화 시켜주는 방법이 필요한데, 이 방법을 가변수 방법이라 한다. 명목변수에서 1은 하나의 그룹을 나타내며 0은 나머지 그룹을 나타낸다. 
 


일반화를 시켜서 말하자면, 만약 명목변수에서 N개의 그룹이 있다면 이것은 가변수 방법을 통해 N-1개의 레벨을 가진 속성으로 표현된다. 가변수 방법의 가장 편리한 측면은 명목변수를 0과 1의 값으로 표현하기 때문에 유클리디안거리 계산 시 정규화 된 다른 변수와 동일하게 평가될 수 있다는 점이다. 

kNN알고리즘이 lazy하다고 불리는 이유는?

kNN알고리즘 분류 방법은 일반적으로 lazy하다고 평가된다. 그 의미는 기술적으로 보았을 때, 추상화 과정과 일반화 과정이 모두 생략되기 때문이다. 추상화와 일반화의 과정을 쉽게 설명하자면 학습데이터가 들어왔을 때, 컴퓨터가 데 이터셋의 중요 부분을 판단하여 학습 데이터 내에 일반화된 모델을 자체적으로 만드는 것이다. 하지만 kNN알고리즘은 어떠한 모델도 만들지 않고 사용자가 분석 명령문을 입력할 때까지 데이터를 저장만하고 기다린다. 따라서 정확한 정 의를 따르자면, lazy learning은 어쨌든 learning이 아니다. 대신 말 그대로 학습데이터를 ‘저장’만하는 것이다. 때문에 학습데이터 저장은 매우 빠른데 비해 예측하는 과정은 상당히 오래 걸린다. 이렇듯 학습데이터에 강력히 의존하는 성향 때문에 lazy 러닝은 instance-based learning or rote learning 이라고도 불린다. 

knn {class}

R Documentation

k-Nearest Neighbour Classification

Description

k-nearest neighbour classification for test set from training set. For each row of the test set, the k nearest (in Euclidean distance) training set vectors are found, and the classification is decided by majority vote, with ties broken at random. If there are ties for the kth nearest vector, all candidates are included in the vote.

Usage

knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all = TRUE)

Arguments

train	matrix or data frame of training set cases.
test	matrix or data frame of test set cases. A vector will be interpreted as a row vector for a single case.
cl	factor of true classifications of training set
k	number of neighbours considered.
l	minimum vote for definite decision, otherwise doubt. (More precisely, less than k-l dissenting votes are allowed, even if k is increased by ties.)
prob	If this is true, the proportion of the votes for the winning class are returned as attribute prob.
use.all	controls handling of ties. If true, all distances equal to the kth largest are included. If false, a random selection of distances equal to the kth is chosen to use exactly kneighbours.

Value

Factor of classifications of test set. doubt will be returned as NA.

References

Ripley, B. D. (1996) Pattern Recognition and Neural Networks. Cambridge.

Venables, W. N. and Ripley, B. D. (2002) Modern Applied Statistics with S. Fourth edition. Springer.

See Also

knn1, knn.cv

Examples

train <- rbind(iris3[1:25,,1], iris3[1:25,,2], iris3[1:25,,3])
test <- rbind(iris3[26:50,,1], iris3[26:50,,2], iris3[26:50,,3])
cl <- factor(c(rep("s",25), rep("c",25), rep("v",25)))
knn(train, test, cl, k = 3, prob=TRUE)
attributes(.Last.value)

---

[Package class version 7.3-5 Index]

 

-------------------------------------------------------------------------------------------------------------------------

출처

http://wiki.boazbigdata.com/index.php/3)_%EA%B8%B0%EA%B3%84_%ED%95%99%EC%8A%B5#kNN.EC.95.8C.EA.B3.A0.EB.A6.AC.EC.A6.98.EC.9D.B4_lazy.ED.95.98.EB.8B.A4.EA.B3.A0_.EB.B6.88.EB.A6.AC.EB.8A.94_.EC.9D.B4.EC.9C.A0.EB.8A.94.3F

http://stat.ethz.ch/R-manual/R-patched/library/class/html/knn.html