튜토리얼

필수 데이터사이언스 방법론 가이드
카테고리는 수준별, 언어별, 분야별, 주제별 순으로 정렬되어 있습니다.

k-최근접이웃알고리즘(knn, k-Nearest Neighbors)

작성자
sungkenh
작성일
2017-01-11 16:54
조회
133
카테고리 : [ 고급   |   Python   |   기타   |   군집 분석(클러스터링) ]

1) 제목


k-최근접이웃알고리즘(knn, k-Nearest Neighbors)

2) 작성자


컴퓨터정보통신공학과 홍성은

3) 링크 및 출처


Data Science From Scratch

 

4) 문제 및 개요






5) 데이터


6) 해결방법 및 결과


KNN (k-Nearest Neighbors, k-최근접 이웃 알고리즘)

어떤 사건을 추정할때 단순히 정보를 이용한 추정이 아닌 그와 비슷한 상태에 있는 사건을 통해 이를 추정해 나가는 방식을 말한다. 예를들어 대통령 선거에서 A란 사람이 어느 후보자에게 투표를 할 지 예상해본다고 하자. 우리는 이 사람의 주거지, 혼인여부, 자녀의 수등을 통해 이 사람이 어떤 후보자를 선택할 지 예상할 수 있다. 이를 더 확장하여 이와 비슷한 상황에 있는 사람이 어떤 후보자를 선택했는지 조사한다면 A가 어떤 후보를 선택하게 될 것인지 좀 더 정확하게 예상할 수 있게 된다. 이것을 KNN이라 한다.

 
k-Model
KNN 모델은 가장 간단한 예측모델 중 하나로써 복잡한 수학적 추정이나 많은 연산을 요구하지 않는다. KNN 모델이 요구하는 것은 단 2개이다.

거리에 관한 개념
가까운 점일 수록 유사하다
우리가 이 책에서 다룰 대부분의 기술들은 데이터에 대한 패턴을 보기 위해 데이터의 전체를 보게될 것이다. 그러나 이 모델은 단지 이 점이 어떤 점과 가장 가까운지 만을 보게된다. 또한 KNN 모델은 어떤 현상의 원인에 대해 이해하는데 별다른 도움을 주지 못한다. 가령 이웃을 통해 A가 어떤 후보를 선택 할지는 알수 있겠지만 왜 해당 후보자에게 투표했는지는 알수 없다는 것이다. 일반적으로 우리는 벡터형태의 점으로 표현된 데이터와 일치 유무를 표현하는 라벨을 가진다. 이때 라벨은 참, 거짓의 형태가 될 것이다. 데이터가 벡터형태의 점으로 표현되기 때문에 두 데이터와의 차이는 두 점 사이의 거리로 대표된다. KNN 모델을 시행하기 위해선 3이나 5와같은 숫자형태로 k를 선택해야한다. 그 후 우리가 새로운 점(데이터)를 분류하려 할 때 이를 기준으로 어떤 데이터인지 결정하게 된다. 이를 위해 투표수를 세는 함수가 필요하다.

In [1]:

from __future__ import division
from collections import Counter
from linear_algebra import distance
from statistics import mean
import math, random
import matplotlib.pyplot as plt

def raw_majority_vote(labels):
votes = Counter(labels)
winner, _ = votes.most_common(1)[0]
return winner



그러니 이것은 데이터를 묶는데 그다지 현명한 방법이 아니다. 예를 들어 우리가 가장 인기있는 영화 순위를 정한다고 하자. 투표수는 "주토피아" 2표, "닥터스트레인지" 2표, "럭키"1표 라고 가정하자. "주토피아"와 "닥터스트레인지"가 2표로 같은 득표수를 가지게 되므로 우선순위를 정할 수 가 없다. 이러한 경우 때문에 동등한 투표수를 갖는 데이터에 대해 판단해 주어야 한다. 이 경우에 우리는 몇가지 선택 방법을 가지게 된다.

임의로 우선순위를 정한다.
거리 가중치를 두어 더 큰 가중치를 가지는 것을 우선자로 한다.
유일한 우선자가 나올때 까지 k값을 줄여나간다. 우리는 이 중 3번째 방법을 보완할 것 이며 이 함수는 다음과 같다.

In [2]:
def majority_vote(labels):
"""assumes that labels are ordered from nearest to farthest"""
vote_counts = Counter(labels)
winner, winner_count = vote_counts.most_common(1)[0]
num_winners = len([count
for count in vote_counts.values()
if count == winner_count])

if num_winners == 1:
return winner # unique winner, so return it
else:
return majority_vote(labels[:-1]) # try again without the farthest


이러한 접근법은 결과적으로 잘 작동하지만, 최악의 경우 우리는 한 가지 라벨이 우선자가 될때까지 모든 점의 거리를 계산해 주어야 한다. 이 함수를 좀더 간단히 만들면 다음과 같다.

In [11]:

def knn_classify(k, labeled_points, new_point):
"""each labeled point should be a pair (point, label)"""

# order the labeled points from nearest to farthest
by_distance = sorted(labeled_points,
key=lambda point_label: distance(point_label[0], new_point))

# find the labels for the k closest
k_nearest_labels = [label for _, label in by_distance[:k]]

# and let them vote
return majority_vote(k_nearest_labels)



cf. def와 같은 기능을 하지만 상대적으로 간단한 함수를 정의할 때 사용한다. C언어의 매크로와 비슷한 기능을 한다. 예를들어 lambda는 이런식으로 구현 할 수 있다. lambda x, y : x + y 앞의 x,y는 파라미터를 말하고 콜론(:)뒤는 함수식을 말한다.
다음장 부터는 이것이 어떻게 작동하는지 알아보자.

예시 : 가장 인기있는 프로그래밍 언어

우리는 처음 데이터사이언티스터가 조사한 결과를 받았고 우리는 많은 도시에서 가장 인기있는 프로그래밍 언어에 대해서 알게 되었다.

 

In [12]:

cities = [(-86.75,33.5666666666667,'Python'),(-88.25,30.6833333333333,'Python'),(-112.016666666667,33.4333333333333,'Java'),(-110.933333333333,32.1166666666667,'Java'),(-92.2333333333333,34.7333333333333,'R'),(-121.95,37.7,'R'),(-118.15,33.8166666666667,'Python'),(-118.233333333333,34.05,'Java'),(-122.316666666667,37.8166666666667,'R'),(-117.6,34.05,'Python'),(-116.533333333333,33.8166666666667,'Python'),(-121.5,38.5166666666667,'R'),(-117.166666666667,32.7333333333333,'R'),(-122.383333333333,37.6166666666667,'R'),(-121.933333333333,37.3666666666667,'R'),(-122.016666666667,36.9833333333333,'Python'),(-104.716666666667,38.8166666666667,'Python'),(-104.866666666667,39.75,'Python'),(-72.65,41.7333333333333,'R'),(-75.6,39.6666666666667,'Python'),(-77.0333333333333,38.85,'Python'),(-80.2666666666667,25.8,'Java'),(-81.3833333333333,28.55,'Java'),(-82.5333333333333,27.9666666666667,'Java'),(-84.4333333333333,33.65,'Python'),(-116.216666666667,43.5666666666667,'Python'),(-87.75,41.7833333333333,'Java'),(-86.2833333333333,39.7333333333333,'Java'),(-93.65,41.5333333333333,'Java'),(-97.4166666666667,37.65,'Java'),(-85.7333333333333,38.1833333333333,'Python'),(-90.25,29.9833333333333,'Java'),(-70.3166666666667,43.65,'R'),(-76.6666666666667,39.1833333333333,'R'),(-71.0333333333333,42.3666666666667,'R'),(-72.5333333333333,42.2,'R'),(-83.0166666666667,42.4166666666667,'Python'),(-84.6,42.7833333333333,'Python'),(-93.2166666666667,44.8833333333333,'Python'),(-90.0833333333333,32.3166666666667,'Java'),(-94.5833333333333,39.1166666666667,'Java'),(-90.3833333333333,38.75,'Python'),(-108.533333333333,45.8,'Python'),(-95.9,41.3,'Python'),(-115.166666666667,36.0833333333333,'Java'),(-71.4333333333333,42.9333333333333,'R'),(-74.1666666666667,40.7,'R'),(-106.616666666667,35.05,'Python'),(-78.7333333333333,42.9333333333333,'R'),(-73.9666666666667,40.7833333333333,'R'),(-80.9333333333333,35.2166666666667,'Python'),(-78.7833333333333,35.8666666666667,'Python'),(-100.75,46.7666666666667,'Java'),(-84.5166666666667,39.15,'Java'),(-81.85,41.4,'Java'),(-82.8833333333333,40,'Java'),(-97.6,35.4,'Python'),(-122.666666666667,45.5333333333333,'Python'),(-75.25,39.8833333333333,'Python'),(-80.2166666666667,40.5,'Python'),(-71.4333333333333,41.7333333333333,'R'),(-81.1166666666667,33.95,'R'),(-96.7333333333333,43.5666666666667,'Python'),(-90,35.05,'R'),(-86.6833333333333,36.1166666666667,'R'),(-97.7,30.3,'Python'),(-96.85,32.85,'Java'),(-95.35,29.9666666666667,'Java'),(-98.4666666666667,29.5333333333333,'Java'),(-111.966666666667,40.7666666666667,'Python'),(-73.15,44.4666666666667,'R'),(-77.3333333333333,37.5,'Python'),(-122.3,47.5333333333333,'Python'),(-89.3333333333333,43.1333333333333,'R'),(-104.816666666667,41.15,'Java')]

cities = [([longitude, latitude], language) for longitude, latitude, language in cities]

한 공동체의 부대표가 우리가 조사하지 않은 지역의 인기있는 프로그래밍 언어에 대해 추정해주는 것을 요청했다. 가장먼저 산점도를 통해 데이터를 분석해 보자.

In [13]:

def plot_state_borders(plt, color='0.8'):
pass

def plot_cities():

# key is language, value is pair (longitudes, latitudes)
plots = { 'Java' : ([], []), 'Python' : ([], []), 'R' : ([], []) }

# we want each language to have a different marker and color
markers = { 'Java' : 'o', 'Python' : 's', 'R' : '^' }
colors = { 'Java' : 'r', 'Python' : 'b', 'R' : 'g' }

for (longitude, latitude), language in cities:
plots[language][0].append(longitude)
plots[language][1].append(latitude)

# create a scatter series for each language
for language, (x, y) in plots.items():
plt.scatter(x, y, color=colors[language], marker=markers[language],
label=language, zorder=10)

plot_state_borders(plt) # assume we have a function that does this

plt.legend(loc=0) # let matplotlib choose the location
plt.axis([-130,-60,20,55]) # set the axes
plt.title("Favorite Programming Languages")
plt.show()

plot_cities()


점이 가까울수록 같은 언어일 가능성이 높으므로, KNN은 적합한 예측모델이라 할 수 있다.

KNN을 시작하기 위해서 조사할 데이터에 대한 정보 외에 그 이웃들로만 결과를 추정해 보자

In [14]:

# try several different values
for k in [1, 3, 5, 7]:
num_correct = 0
for city in cities:
location, actual_language = city
other_cities = [other_city
for other_city in cities
if other_city != city]

predicted_language = knn_classify(k, other_cities, location)

if predicted_language == actual_language:
num_correct += 1
print(k, "neighbor[s]:", num_correct, "correct out of", len(cities))

1 neighbor[s]: 40 correct out of 75
3 neighbor[s]: 44 correct out of 75
5 neighbor[s]: 41 correct out of 75
7 neighbor[s]: 35 correct out of 75

결과를 보면 3개의 이웃들이 가장 좋은 것으로 형성되고 59퍼센트 정도의 정확도를 보인다.
In [16]:

def classify_and_plot_grid(k=1):
plots = { "Java" : ([], []), "Python" : ([], []), "R" : ([], []) }
markers = { "Java" : "o", "Python" : "s", "R" : "^" }
colors = { "Java" : "r", "Python" : "b", "R" : "g" }

for longitude in range(-130, -60):
for latitude in range(20, 55):
predicted_language = knn_classify(k, cities, [longitude, latitude])
plots[predicted_language][0].append(longitude)
plots[predicted_language][1].append(latitude)

# create a scatter series for each language
for language, (x, y) in plots.items():
plt.scatter(x, y, color=colors[language], marker=markers[language],
label=language, zorder=0)

plot_state_borders(plt, color='black') # assume we have a function that does this

plt.legend(loc=0) # let matplotlib choose the location
plt.axis([-130,-60,20,55]) # set the axes
plt.title(str(k) + "-Nearest Neighbor Programming Languages")
plt.show()

classify_and_plot_grid()

a2

예를 들어, 위 표는 k가 1일때 무슨일이 일어나는지 보여준다. 이를 보면 한 언어에서 다른언어로 날카로운 경계를 가진 갑작스러운 변화를 볼 수있다. 만약 우리가 k값을 3개로 증가시키면, 이전 보다 부드러운 경계를 가진 언어의 구역을 볼 수있다. 그리고 만약 우리가 k값을 5개까지 늘리게 된다면 이 경계는 더운 부드러워 질 것이다.
KNN은 고차원의 데이터를 다룰때 '차원의 저주'로 인해서 문제가 발생하게 된다. 고차원 공간에서 한 점은 다른점과 거리가 멀어지게 된다. 이를 확인하기 위한 방법 중 하나로

< cf. 차원의 저주 >

기계학습(machine learning), 데이터 마이닝(data mining) 등에서 사용하는 용어로 '차 원의 저주'란 말이 있다. 데이터의 차원(dimensionality)이 증가할수록 해당 공간의 크 기(부피)가 기하급수적으로 증가하기 때문에 동일한 개수의 데이터의 밀도는 차원이 증 가할수록 급속도로 희박(sparse)해진다. 따라서, 차원이 증가할수록 데이터의 분포 분 석 또는 모델추정에 필요한 샘플 데이터의 개수가 기하급수적으로 증가하게 되는데 이 러한 어려움을 표현한 용어가 '차원의 저주'이다. 따라서 데이터 분석 등의 차원에 관계된 문제에 있어서는 어떻게든 핵심이 되는 파라미 터만을 선별하여 문제의 차원을 낮추고자 하는 것이 일반적이다.

In [17]:

def random_point(dim):
return [random.random() for _ in range(dim)]

def random_distances(dim, num_pairs):
return [distance(random_point(dim), random_point(dim))
for _ in range(num_pairs)]


In [18]:

dimensions = range(1, 101, 5)

avg_distances = []
min_distances = []

random.seed(0)
for dim in dimensions:
distances = random_distances(dim, 10000) # 10,000 random pairs
avg_distances.append(mean(distances)) # track the average
min_distances.append(min(distances)) # track the minimum
print (dim, min(distances), mean(distances), min(distances) / mean(distances))



1 7.947421226228712e-06 0.33100099028943963 2.4010264196730017e-05
6 0.18647467260473205 0.9677679968196347 0.1926853060005515
11 0.315888574043911 1.333439579654304 0.2368975534128105
16 0.7209190490469604 1.6154152410436058 0.4462747600308794
21 0.9694045860570238 1.857496077372409 0.5218878240800011
26 1.1698067560262715 2.063221470005646 0.5669807013122398
31 1.2930748713962408 2.257299829279515 0.5728414340991487
36 1.5123637311959328 2.4376709133165604 0.6204134130387167
41 1.5514668006745476 2.6039686964057926 0.5958085451703037
46 1.6688006850159558 2.756796053135491 0.6053406392242602
51 2.0135369208019926 2.9029973365343897 0.6936061895274631
56 2.1422705294432887 3.046195309569519 0.7032610557548358
61 2.2891825062886793 3.178371787765626 0.7202374860928272
66 2.3805561409678484 3.3055795715248353 0.7201630121006944
71 2.428355816745725 3.43294841393377 0.707367406655291
76 2.5356413086431617 3.5584750622227586 0.7125640237195604
81 2.682272988673655 3.6698733685779983 0.7308897935388385
86 2.8348947533212074 3.779672772114332 0.7500370863415723
91 3.015796748953059 3.888554628876586 0.7755572537306312
96 2.976216447967502 3.991278273562552 0.7456800162698198

차원의 숫자를 증가시킬수록 점과의 평균거리가 늘어나게 된다. 그러나 더 큰 문제는 가장 가까운 거리와 평균거리와의 비율이다.
낮은 차원의 데이터셋에서, 가장 가까운점은 평균보다 훨씬 유사한 경향을 띈다. 그러나 두 점이 모든 차원에서 가까운 것은 고 차원에서 가장 가까운점일지라도 평균 점의 거리보다 훨씬 거리가 멀 수가 있으며, 이는 점이 가까운것이 별 의미가 없다는 것을 뜻한다.

이 문제에 대해 다른 방식으로 생각해보자. 만약에 당신이 임의로 0과 1사이의 숫자를 선택한다면, 훨씬 좋은 데이터간의 차이샘플을 구할 수 있을것이다. 또, 50개의 임의의 점을 뽑는다면 낮은 범위값을 얻게 될 것이다.
그리고 3차원 이하에서는 더 잠잠할 것이다.