K-NN 최근접 이웃 (K-Nearest Neighbor) 알고리즘

분류와 군집화

분류(Classification)

소속집단의 정보를 이미 알고 있는 상태에서, 비슷한 집단으로 묶는 방법

-> 지도 학습

분류

위 그림에는 사전 정보인 색깔이 존재한다. 이런 데이터의 분포에서 비슷한 집단으로 묶을 때는 분류를 사용한다.

군집화(Clustering)

소속집단의 정보가 없고, 모르는 상태에서, 비슷한 집단으로 묶는 방법

-> 비지도 학습

군집화

위 그림에서는 각 데이터들의 사전 정보가 주어지지 않는데 이럴 때 군집화를 사용한다.

K-Nearest Neighbor 알고리즘

정답이 없는 예시를 "분류" 하기 위한 알고리즘

가장 고전적이고 직관적인 특징이 있다.

새로운 데이터를 입력받았을 때, 가장 가까이에 존재하는 데이터가 무엇이냐를 중심으로 새로운 데이터를 분류한다.

물음표에는 별이 들어가야 할까 세모가 들어가야 할까?

최근접으로 3개 만을 생각한다면 세모가 맞겠지만, 7개로 생각한다면 별이 들어가야 할 것이다.

KNN에서 K는 주변의 개수를 의미한다. -> K의 개수가 짝수일 경우에는 동점이 나올 수 있어 보통 k를 홀수로 설정한다.

알고리즘 구현

1. 두 점 사이의 거리 계산

2. 가장 근처에 있는 요소 뽑기

3. 예측하기

Numpy, matplotlib.pyplot를 사용한 예제

1. Numpy, matplotlib.pyplot모듈을 불러온다

import numpy as np
import matplotlib.pyplot as plt

 

2. 단맛과, 아삭거림을 기준으로 임의의 데이터셋을 넣고 사용자가 입력한 데이터는 target변수에 리스트의 형태로 넣는다.

grape = [8,5]
fish = [2,3]
carrot = [7,10]
orange = [7,3]
celery =[3,8]
cheese = [1,1]
category =['과일', '단백질', '채소', '과일', '채소', '단백질']

dan = int(input('단맛 입력(1~10) >>'))
asac = int(input('아삭거림 입력(1~10) >>'))
target = [dan, asac]

 

3. 각각의 데이터들을 넘파이 배열 하나로 합친다.

# tile()함수는 array요소를 지정한 값만큼 반복한다, 지금 위에서는 target(입력값)을 dataset사이즈 만큼 반복한다.

def data_set():
    dataset = np.array([grape,fish, carrot, orange, celery, cheese]) #분류 집단
    size = len(dataset)
    class_target = np.tile(target,(size, 1)) #분류 대상
    class_category = np.array(category) #분류 범주

    return dataset, class_target, class_category
dataset, class_target, class_category = data_set()

 

##출력값##

dataset(분류 집단) #각 데이터의 좌표
[[ 8  5]
 [ 2  3]
 [ 7 10]
 [ 7  3]
 [ 3  8]
 [ 1  1]]

 

class_target(분류 대상) #사용자의 입력값
[[8 2]
 [8 2]
 [8 2]
 [8 2]
 [8 2]
 [8 2]] #8과 2는 사용자의 입력값이다, 사용자의 단맛과 아삭거림의 입력에 따라 바뀐다

 

class_category(분류 범주)
['과일' '단백질' '채소' '과일' '채소' '단백질']

 

3. 유클리드 거리 계산식을 이용하여 사용자 값과 데이터셋 각각 간의 거리를 정렬한다. 그리고 k개만큼 딕셔너리 안에 주변 데이터를 넣는다.

# argsort()함수는 numpy에서 작은 값부터 순서대로 데이터의 index를 반환해주는 함수

# get(x) 함수는 x라는 Key에 대응되는 Value를 돌려준다. 콤마(,)를 쓸고 두 번째 인자를 넣으면 첫 번째 인자의 키가 없을 때 반환된다.

 

유클리드 거리계산

def classify(dataset, class_target, class_category, k):
    #유클리드 거리계산
    diffMat = class_target - data_set #두점의 차
    sqDiffMat = diffMat**2 #차에 대한 제곱
    row_sum = sqDiffMat.sum(axis = 1) #차의 제곱의 합
    distance = np.sqrt(row_sum) #제곱의 합의 제곱근(최종값)

    #가까운거리 오름차순
    sortDist = distance.argsort()
    class_result = {} # 빈 딕셔너리 생성
    for i in range(k): #이웃한 k개 딕셔너리 안에 넣음
        c = class_category[sortDist[i]] #딕셔너리의 키에 분류 범주 넣음
        class_result[c] = class_result.get(c,0)+1
    return class_result

 

4. 함수 호출

k = int(input('k값 입력(1~3) >>'))
class_result = classify(dataset, class_target, class_category, k)
print(class_result)

 

##출력##

단맛 입력(1~10) >>8
아삭거림 입력(1~10) >>2
k값 입력(1~3) >>3
{'과일': 2, '단백질': 1}

 

5. 출력을 함수화

def classify_result(class_result):
    protein = fruit = vegetable = 0
    for c in class_result.keys(): #c안에 딕셔너리의 키값을 넣는다
        if c=='단백질':
            protein = class_result[c] #protein에 단백질 개수
        elif c=='과일':
            fruit = class_result[c] #fruit에 과일개수
        else:
            vegetable = class_result[c] #vegetable 채소 개수

    #서로의 값을 비교하여 리턴
    if protein>fruit and protein>vegetable:
        result = "분류대상은 단백질 입니다"
    elif fruit>protein and fruit>vegetable:
        result = "분류대상은 과일 입니다"
    else:
        result = "분류대상은 채소 입니다"
    return result 

a = classify_result(class_result) 
print(a)

 

##출력##

단맛 입력(1~10) >>8
아삭거림 입력(1~10) >>2
k값 입력(1~3) >>3
{'과일': 2, '단백질': 1}
분류대상은 과일 입니다

산점도로 표현

#과일 = o
#단백질 = +
#채소 = *
print('과일 = o'); print('단백질 = +'); print('채소 = *')
plt.scatter(8, 5, marker='o', color = 'black') 
plt.scatter(2, 3, marker='+', color = 'green') 
plt.scatter(7, 10, marker='*', color = 'blue') 
plt.scatter(7, 3, marker='o', color = 'black')
plt.scatter(3, 8, marker='+', color = 'green') 
plt.scatter(1, 1, marker='*', color = 'blue') 
plt.scatter(target[0], target[1], color='red') # 분류대상 -> B집단
plt.xlabel("dan") #x축 이름설정
plt.ylabel("asac") #y축 이름설정
plt.show()

최종코드

import numpy as np
import matplotlib.pyplot as plt

grape = [8,5]
fish = [2,3]
carrot = [7,10]
orange = [7,3]
celery =[3,8]
cheese = [1,1]
category =['과일', '단백질', '채소', '과일', '채소', '단백질']

dan = int(input('단맛 입력(1~10) >>'))
asac = int(input('아삭거림 입력(1~10) >>'))
target = [dan, asac]

def data_set():
    dataset = np.array([grape,fish, carrot, orange, celery, cheese]) #나눠져있는 데이터를 넘파이 리스트로 합침
    size = len(dataset) #데이터셋 길이
    class_target = np.tile(target,(size, 1)) #타겟은 사용자의 입력값, 사용자의 입력값으로 데이터셋과 똑같은 길이의 리스트 생성
    class_category = np.array(category) #분류 범주

    return dataset, class_target, class_category
dataset, class_target, class_category = data_set()

def classify(dataset, class_target, class_category, k):
    #유클리드 거리계산
    diffMat = class_target - dataset #두점의 차
    sqDiffMat = diffMat**2 #차에 대한 제곱
    row_sum = sqDiffMat.sum(axis = 1) #차의 제곱의 합
    distance = np.sqrt(row_sum) #제곱의 합의 제곱근(최종값)

    #가까운거리 오름차순
    sortDist = distance.argsort()
    class_result = {} # 빈 딕셔너리 생성
    for i in range(k): #이웃한 k개 딕셔너리 안에 넣음
        c = class_category[sortDist[i]] #딕셔너리의 키에 분류 범주 넣음
        class_result[c] = class_result.get(c,0)+1 #c의 값에 인덱스값을 넣는다.
    return class_result

k = int(input('k값 입력(1~3) >>'))
class_result = classify(dataset, class_target, class_category, k)
print(class_result)

def classify_result(class_result):
    protein = fruit = vegetable = 0
    for c in class_result.keys(): #c안에 딕셔너리의 키값을 넣는다
        if c=='단백질':
            protein = class_result[c] #protein에 단백질 개수
        elif c=='과일':
            fruit = class_result[c] #fruit에 과일개수
        else:
            vegetable = class_result[c] #vegetable 채소 개수

    #서로의 값을 비교하여 리턴
    if protein>fruit and protein>vegetable:
        result = "분류대상은 단백질 입니다"
    elif fruit>protein and fruit>vegetable:
        result = "분류대상은 과일 입니다"
    else:
        result = "분류대상은 채소 입니다"
    return result 

a = classify_result(class_result) 
print(a)

#과일 = o
#단백질 = +
#채소 = *
print('과일 = o'); print('단백질 = +'); print('채소 = *')
plt.scatter(8, 5, marker='o', color = 'black') 
plt.scatter(2, 3, marker='+', color = 'green') 
plt.scatter(7, 10, marker='*', color = 'blue') 
plt.scatter(7, 3, marker='o', color = 'black')
plt.scatter(3, 8, marker='+', color = 'green') 
plt.scatter(1, 1, marker='*', color = 'blue') 
plt.scatter(target[0], target[1], color='red') # 분류대상 -> B집단
plt.xlabel("dan") #x축 이름설정
plt.ylabel("asac") #y축 이름설정
plt.show()

###최종출력###

단맛 입력(1~10) >>8
아삭거림 입력(1~10) >>2
k값 입력(1~3) >>3
{'과일': 2, '단백질': 1}
분류대상은 과일 입니다
과일 = o
단백질 = +
채소 = *

산점도

과일 = 검은 동그라미

단백질 = 초록 +

채소 = 파란 ★

사용자의 타겟 값 = 빨간 동그라미

빨간 동그라미에서 가장 주위에 있는 데이터 3개를 뽑으면 과일 둘, 단백질 하나이기 때문에 사용자의 입력값은 과일이 된다.

###실행파일###

K_NN_1.py

0.00MB