1. kNN(k-Nearest Neighbors), 최근접 알고리즘

 

-녹색 영화가 액션 영화이냐 로맨틱 영화이냐

-녹색별 데이터를 제외한 기존의 데이터 -> 판단 -> knn

-knn 알고리즘 

(1) k를 정해야 함 : 최근접점을 몇 개까지 볼 것인가, 보통 홀수를 사용  ex) k=3

(2) 예측값을 판단 

-이와 같이 녹색별을 기준으로 한 특정 위치 내부에 존재하는 최근접점의 개수가 액션 영화가 더 많기 때문에, 녹색 별은 액션 영화일 것이다, 라는 prediction을 내놓을 수 있게 된다

 

-최근접점을 프로그램 상에서 어떻게 구하느냐 -> 피타고라스의 원리

 

-이를 구현하는 파이썬 코드

from numpy import *
import operator

def createDataSet():
    group = array([ [1.0, 2.0], [1.0,4.0], [4.0, 1.0], [4.0, 2.0] ])
    labels = ['Action', 'Action', 'Romantic', 'Romantic']
    return group, labels

def calcDistance(inX, dataSet, labels, k):
    # shape is a tuple that gives dimensions of the array
    # shape[0] returns the number of rows, here will return 4
    dataSetSize = dataSet.shape[0]  # dataSetSize = 4

    # numpy.tile(A, reps): construct an array by repeating A the number of times given by reps
    # if reps has length d, the result will have dimension of max(d, A.ndim)
    # tile(inX, (dataSetSize,1)) will return [ [0,0] [0,0] [0,0] [0,0] ]
    # diffMat is [ [1, 1], [1, -1], [-2, 2], [-2, 1] ]
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet

    # **2 means square
    sqDiffMat = diffMat ** 2

    # sqDistances = x^2 + y^2
    sqDistances = sqDiffMat.sum(axis=1)
    # distance is equal to the square root of the sum of the squares of the coordinates
    # distance = [2, 2, 8, 5]
    distances = sqDistances ** 0.5

    # numpy.argsort() returns the indices that would sort an array
    # here returns [0 1 3 2]
    sortedDistIndices = distances.argsort()
    return sortedDistIndices

def findMajorityClass(inX, dataSet, labels, k, sortedDistIndices):
    classCount = {}

    # iterate k times from the closest item
    for i in range(k):
        voteIlabel = labels[sortedDistIndices[i]]
        # increase +1 on the selected label
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

    # classCount dictionary : {'Action': 2, 'Romantic': 1}
    # sort ClassCount Descending order

    return sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)


def classify0(inX, dataSet, labels, k):
    # calculate the distance between inX and the current point
    sortedDistIndices = calcDistance(inX, dataSet, labels, k)
    # take k items with lowest distances to inX and find the majority class among k items
    sortedClassCount = findMajorityClass(inX, dataSet, labels, k, sortedDistIndices)
    # sortedClassCount is now [('Action', 2)], therefore return Action
    return sortedClassCount[0][0]


group, labels = createDataSet()
result = classify0([2.0, 3.0], group, labels,3)
print result