[Artificial Intelligence / Machine Learning] k-Nearest Neighbor Algorithm

지난 글에서 R을 이용한 k-NN 알고리즘에 대하여 살펴본 바 있다. (k-Nearest Neighbor Algorithm)

그러나, R의 라이브러리 중 하나인 class 라이브러리를 이용한 것이며, 실질적으로 R을 이용하여 구체적으로 어떻게 코딩되는지 살펴보지는 않았다.

이번 글에서는 R에서 실질적으로 k-NN 알고리즘을 구현해 보도록 한다.

k-NN 함수

k-NN 함수를 다음과 같이 구현하였다.

R CODE:

##################################################### # @function: KNN() - k-nearest neighbor algorithm # @input: # - df : data frame for training data set # - inX : vector for test data # - k : k-nearest neighbor # @return: result classifier ##################################################### # @author: Geol Choi, ph.D # @email: cinema4dr12@gmail.com # @date: 16/06/2016 ##################################################### kNN <- function(df, inX, k) { # extract group and label len <- dim(df)[2] - 1; # initialize matrix dataSet <- matrix(ncol = len, nrow = dim(df)[1]); for(i in 1:len) { dataSet[,i] <- as.matrix(df[,i]); } # set classes (last column of df) labels <- df[,dim(df)[2]]; # size of dataset dataSetSize <- dim(dataSet)[1]; # create test matrix testMat = matrix(nrow = dataSetSize, ncol = length(inX)); for(i in 1:dataSetSize) { testMat[i,] <- inX; } # difference between testMat and dataSet diffMat <- testMat - dataSet; # squared matrix difference sqDiffMat <- diffMat**2.0; # row sums of sqDiffMat sqDistances <- rowSums(sqDiffMat, na.rm = FALSE, dims = 1); # order of index sortedDistIndicies <- sort.int(sqDistances, index.return = TRUE)$ix; result <- NULL; for(i in 1:k) { iLabel <- labels[sortedDistIndicies[i]]; result <- c(result, iLabel); } uniqueLabels <- unique(labels); # initialize data frame ResultClass <- data.frame(matrix(ncol = 2, nrow = 1)); names(ResultClass) <- c("LABEL", "COUNT"); for(i in 1:length(uniqueLabels)) { label <- uniqueLabels[i]; count <- sum(result == label); ResultClass[i,] <- c(label, count); } # transform COUNT to numeric data ResultClass[,2] <- as.numeric(ResultClass$COUNT); # sorting by COUNT (descending order) ResultClass <- ResultClass[order(-ResultClass$COUNT),]; return(ResultClass$LABEL[1]); }

입력 인수 df는 training dataset의 data frame으로, 마지막 column에는 각 row의 class가 정의되어 있다.

예를 들어, 다음과 같은 형태이다.

X	Y	CLASS
X_1	Y_1	A
X_2	Y_2	B
:	:	:
X_n	Y_n	Z

입력 인수 inX는 test data로써 vector 타입이다.

코드 설명

Line 16

Training dataset df의 데이터 종류의 개수를 알아낸다. 예를 들어, Training dataset이 위의 표와 같다면 데이터 종류의 수는 2개(X와 Y)이다.

Line 18~23

df에서 class를 제외한 data만을 저장하는 dataSet 변수를 matrix 형태로 초기화한다.

따라서, dataSet의 dimension 중 행(row)은 df와 동일하며, 열(column)은 df에서 하나 적게 설정한다.

그리고 df의 모든 행의 element를 dataSet의 행에 저장한다.

Line 26

df의 마지막 열을 label 변수에 저장한다.

Line 29

dataSetSize 변수에 data set의 크기를 저장한다.

Line 31~36

test data 벡터를 dataSet의 행만큼 생성한다.

Line 39

testMat 행렬과  dataSet 행렬의 차이를 구하여 diffMat에 저장한다.

Line 42

diffMat 행렬의 각 요소를 제곱하여 sqDiffMat 행렬에 저장한다.

Line 45

sqDiffMat 행렬의 각 행의 요소에 대하여 합산한 값을 sqDistances 벡터로 저장한다.

Line 48

sqDistances 벡터의 요소를 오름차순으로 정렬하여 이에 해당하는 index를 sortedDistIndices 벡터에 저장한다.

Line 50~55

sortedDistIndices 벡터로부터 k번째까지의 해당 index에 대한 label (또는 class)를 result 벡터에 저장한다.

Line 57~75

k번째까지 추출된 label을 count하고 많이 count된 순서대로 정렬하여 ResultClass 행렬에 저장하고 이 행렬을 리턴한다.

CreateDataSet() 함수

Training data set을 생성하는 함수는 다음과 같다.

R CODE:

################################################## # @function: CreateDataSet() # @input: NONE # @return: dataset(dataframe), labels(class) ################################################## # @author: Geol Choi, ph.D # @email: cinema4dr12@gmail.com # @date: 12/06/2016 ################################################## CreateDataSet <- function() { group <- matrix( c(1.0, 1.2, 0.9, 1.1, 0.8, 1.2, 1.8, 1.9, 2.0, 2.1, 2.1, 2.0, 2.9, 0.9, 3.2, 0.8, 3.1, 1.2), nrow = 9, ncol = 2, byrow = TRUE ); label <- c('A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C'); df <- as.data.frame(group); df[3] <- label; names(df) <- c("X", "Y", "CLASS"); return(df); }

k-NN 테스트

이제 dataset을 생성하고 (CreateDataSet() 호출 ), kNN() 함수를 이용하여 어떤 결과가 나오는지 보도록 하자.

R CODE:

df <- CreateDataSet() inX <- c(0.9, 1.6) k <- 3 result <- kNN(df, inX, k) print(result)

결과는 다음과 같다:

> df <- CreateDataSet()
> inX <- c(0.9, 1.6)
> k <- 3
> 
> result <- kNN(df, inX, k)
> print(result)
[1] "A"

이로써 R에서 k-NN 알고리즘을 구현하는 것에 대하여 알아보았다.

다음 글은 k-NN 알고리즘을 이용하여 숫자 필기 인식하는 방법에 대하여 알아보도록 하겠다.