[Daily Contents] 빅데이터 KNN

KNN

새로운 데이터가 주어졌을 때 기존 데이터 가운데 가장 가까운 K개 이웃의 정보로 새로운 데이터 예측

• (가)

	탕수육	초밥	짜장면
마이콜	2	8	1
길동	7	2	9
사오정	8	1	7
팔계	1	9	1
오공	9	2	9
둘리	1	8	2

• (나)

	탕수육	초밥	짜장면
희동	9	1	??

(가)표를 바탕으로 (나)표의 ?? 칸에 들어갈 데이터를 예측하는 것이 KNN

• 희동과 음식 취향이 닮은 유저의 데이터를 기반으로 ?? 칸 예측
• 탕수육, 초밥 데이터를 기반으로 희동과 닮은 음식 취향 유저 추출
• 해당 유저의 짜장면 데이터들로부터 {평균 혹은 빈도수}를 희동의 짜장면 데이터로 예측

KNN
S1 : 모든 User 데이터와의 거리 계산
S2 : 가까운 거리에 있는 K개의 User 데이터 찾기
S3 : 평균, 빈도 등으로 아이템 선호도 예측

https://github.com/sweetchild222/vanilla-algorithm

k = 3
user = [9, 1, 0]
neighbor_list = [
	[2, 8, 1],
    [7, 2, 9],
    [8, 1, 7],
    [1, 9, 1],
    [9, 2, 9],
    [1, 8, 2]]

prediction = predict(user, neighbor_list, k)

print('Predict %f', % (prediction))

def predict(user, neighbot_list, k):
	k_near_neighbors = get_neighbors(user, neighbors_list, k)

    predict_candidate = [row[-1] for row k_near_neighbors]
    print('predict_candidate : ', predict_candidate)
    prediction = max(set(predict_candidate), key=predict_candidate.count)
    return prediction

def predict(user, neighbot_list, k):
	distances = list()
    for neighbor in neighbor_list:
    	dist = euclidean_distance(user, neighbor)
        distance.append((neighbor, dist))
    distances.sort(key=lambda tup: tup[1])

    print('neighbors distance : ', distances)

    near_neighbors = list()
    for i in range(k)
    	near_neighbors.appned(distances[i][0])

    print('near neighbors : ', near_neighbors)

    return near_neighbors

def euclidean_distance(user, neighbor):
	distance = 0.0
    for i in range(len(user)-1):
    	distance += (user[i] - neighbor[i])**2
    return sqrt(distance)

KNN_Similarity Distance Measure

https://dbrang.tistory.com/1201

Q&A

Q. K가 하나 멀리 떨어져 있을 때는 좋지 않을 듯하다.
A. 좋지 않다. 그런 것은 Noise가 많이 낀 데이터라고 한다.
   그럴 경우 Pre-processing을 거쳐서 Noise를 사전에 제거하는 것 또한 방법.

Q. Euclidean Distance와 Cosine Similarity, Manhattan distance 등과의 차이는?
A. 거리를 재는 방식은 여럿 있고, 위의 예시 외에도 더 있을 수 있다.

Q. 2차원으로 표현되어 간편한데 3, 4차원으로까지 쓰는 경우가 많이 있는가.
A. 3, 4차원, 5차원, 10차원 등 많다. 오히려 2차원인 경우가 적다.

Q. 새로운 데이터가 들어올 때마다 새로 계산해야 하는가?
A. 그렇다.

Q. 데이터 간의 비 수치적 교사성도 점수를 주는 것이 나은가?
A. 수치여야 알고리즘에 적용이 가능.