[R] KNN(K-Nearest Neighbors) 알고리즘 - 승차식 잔디깎이

 

백신 휴가로 평일임에도 시간이 붕뜨게 되어 오랜만에 R과 관련된 글을 올려보려고 한다.

오늘은 KNN 알고리즘과 예제 문제를 하나 풀어보자.

 

---

 

K-최근접이웃(K-Nearest Neighbors) 알고리즘은 범주형 결과를 위한 분류 문제나 수치형 결과를 위한 예측 문제에 사용될 수 있다.

KNN의 아이디어는 학습 데이터세트로 부터 분류하고자 하는 새로운 레코드와 유사한 k개의 레코드를 식별하는 것으로부터 시작된다.

또한, 소속된 클래스(y)와 예측 변수들 x1, x2, x3,... 간의 관계에 대한 가정을 만들지 않는 분류 기법이다.

KNN은 비모수적인 방법으로서, 미리 가정된 함수에 대한 모수 추정을 포함하지 않으며, 데이터세트간의 유사성으로 정보를 얻는다.

 

여기서의 이슈는 예측변수 값들에 기반하여 어떻게 레코드 간의 거리를 측정하는가 하는 문제이다.

가장 보편적으로 측정되는 거리 측도는 유클리드 거리(Euclidean Distance)이다.

 

대부분의 경우, 다양한 예측변수들의 척도를 균등하게 하기 위하여 거리 계산에 앞서 예측변수들을 표준화 한다.

 

k > 1 의 이웃을 갖는 경우의 최근접 이웃 알고리즘은 다음과 같은 분류규칙으로 나타낼 수 있다.

 

1. 분류될 레코드와 가장 가까운 k개의 이웃을 찾는다.
2. 레코드를 분류하기 위해 다수결 결정규칙을 사용한다. 즉, 레코드는 k개의 이웃들의 다수가 속하는 클래스로 분류된다.

 

---

 

이제 예제를 하나 풀어보도록 하자.

승차식 잔디깎이 기계를 구입할 가구와 구입하지 않을 가구를 알아보는 예제이다.

데이터는 25개의 데이터 세트 밖에 없어서 불안정한 결과를 도출할 수도 있다.

알고리즘의 참고용으로 확인하자.

 

컬럼은 소득(Income)과 주택대지 크기(Lot_Size)를 사용하여 기계 소유 여부를 판단하겠다.

 

 

 

우선 데이터를 불러오고 데이터를 산점도로 나타내 보자.

 

mower.df <- read.csv("D:/R 실습/datasets-master/RidingMowers.csv")
set.seed(111)

train_index <- sample(row.names(mower.df), 0.6*dim(mower.df)[1])
valid.index <- setdiff(row.names(mower.df), train_index)

train.df <- mower.df[train_index, ]
valid.df <- mower.df[valid.index, ]

# 새로운 데이터 생성(예측을 위함)
new.df <- data.frame(Income=60, Lot_Size = 20)

# 데이터를 산점도로 확인
plot(Lot_Size ~ Income, data=train.df, pch=ifelse(train.df$Ownership=="Owner", 1, 3))
text(train.df$Income, train.df$Lot_Size, rownames(train.df), pos=4)
text(60, 20, "X") # 위에서 만든 새로운 데이터
legend("topright", c("owner", "non-owner", "newhousehold"), pch = c(1,3,4))

 

그림 상 보면 우리가 찾고자 하는 값(60, 20)에 가장 가까운 값은 4번으로 소유하고 있는 사람이다.

그럼 정규화한 데이터와 가까운 이웃을 결정해 보자.

 

 

train.norm.df <- train.df
valid.norm.df <- valid.df
mower.norm.df <- mower.df

library(caret)
norm.values <- preProcess(train.df[, 1:2], method=c("center", "scale"))

train.norm.df[, 1:2] <- predict(norm.values, train.df[,1:2])
valid.norm.df[, 1:2] <- predict(norm.values, valid.df[,1:2])
mower.norm.df[, 1:2] <- predict(norm.values, mower.df[,1:2])
new.norm.df <- predict(norm.values, new.df)

library(FNN)
nn <- knn(train = train.norm.df[, 1:2], test = new.norm.df,
          cl = train.norm.df[, 3], k = 3)
row.names(train.df)[attr(nn, "nn.index")]

 

결과 값은 위와 같다.

즉, 우리가 찾고자 하는 값(60, 20)에 해당하는 집은 잔디깎이 기계를 소유하고 있을 것이다.

 

 

여기서 끝내기는 아쉬우니 k에 따른 검증 정확도를 알아 보려고 한다.

k값이 커질수록 학습데이터에 존재하는 잡음으로 인해 발생하는 과적합의 위험을 줄여주는 효과를 얻을 수 있다.

일반적으로 k가 너무 작으면 데이터에 잡음이 생길 위험이 있다.

반면에 k값이 너무 크면 이 알고리즘의 장점 중 하나인 지역적 구조를 파악할 수 있는 능력을 놓칠 수 있다.

 

데이터가 복잡하고 불규칙한 구조를 가질수록 k의 최적값은 더 작아지게 된다.

일반적으로 k의 값은 1~20의 범위 내에서 결정된다.

 

그럼 각기 다른 k값에 대하여 정확도를 측정해 보자.

 

accuracy.df <- data.frame(k = seq(1, 14, 1), accuracy = rep(0, 14))
for(i in 1:14) {
    knn.pred <- knn(train.norm.df[, 1:2], valid.norm.df[, 1:2],
                    cl = train.norm.df[, 3], k = i)
    accuracy.df[i, 2] <- confusionMatrix(factor(knn.pred),
                                         factor(valid.norm.df[, 3]))$overall[1]
}
accuracy.df

 

정확도가 대체적으로 높진 않지만 k = 3일 때와 k = 5일때의 정확도가 높은것을 확인할 수 있다.

 

 

마지막으로 KNN 알고리즘의 장단점에 대해서 알아보고 마무리 하자.

 

<장점>

• 단순하다.
• 모수에 대한 가정이 거의없다. 충분히 많은 학습데이터가 있을 때, 각 클래스들의 특성이 얘측변수 값들의 여러가지 조합으로 결정지어질 때 놀랍도록 좋은 성능을 발휘한다.

 

<단점>

• 학습세트가 클 경우 근접이웃들을 찾는 데 걸리는 시간이 엄청나게 소요될 수 있다. 이때 주성분 분석과 같이 차원 축소 방법으로 차원을 감소시켜 시간을 감소시킨다.
• 학습세트에 필요한 레코드의 개수는 예측변수의 개수가 증가함에 따라 기하급수적으로 증가한다. 이는 차원의 저주라고 불린다. 이때문에 주성분 분석이나 특이값 분해와 같이 예측변수들을 결합해 줄이는 것이 필요하다.
• 나태 학습법(Lazy Learner)이다. -> 많은 학습시간이 소요 디는 계산들은 예측에 집중되어 있다. 동시에 수많은 레코드를 실시간으로 예측하는 데 적합하지 않다.

 

 

 

이상!