머신러닝 / knn 알고리즘

39 knn 이론 설명

 

ㅇ머신러닝의 종류

1. 지도 학습 : 결과(정답)가 있는 데이터

   - 분류

   - 회귀

2. 비지도 학습 : 결과(정답)가 없는 데이터

3. 강화학습 : 데이터를 스스로 만들어내면서 학습. 주어진 환경에 대한 데이터를 스스로 생성하면서 학습

 

knn은 머신러닝 지도학습의 분류에 해당하는 알고리즘.

분류문제란 새로운 데이터가 들어왔을 때 이 데이터가 기존에 있던 데이터의 그룹중에 어느 그룹에 속한건지를 분류하는 것을 말함.

knn(K Nearest Neighbor) : 여기서 k는 몇번째로 가까운 데이터를 살펴볼 것인가 정한 숫자

새로 들어온 데이터가 기존 데이터의 그룹에 어느 그룹에 속하는지 찾을 때, 거리가 가까운 데이터의 그룹을 자기 그룹으로 선택하는 아주 간단한 알고리즘

k의 개수는 의사결정을 해야하기 때문에 항상 홀수를 선택해야함. k를 하이퍼 파라미터라고 함.

사람이 k의 적정한 값을 알아내는 것이 중요

오버피팅 : k값이 너무 작아서 학습한 data만 잘 맞추고 그 외의 데이터는 잘 맞추지 못하는 것.

언더피팅 : k값이 너무 커서 학습한 data의 정답도 못 맞추는 것.

 

ex) 가구거리에 새로운 건물이 들어왔을 경우, k값이 작으면 가구점이라고 분류하겠지만 k값이 클 경우 식당으로 분류할 수 있음.

 

ㅇknn알고리즘 장단점 - p117

  - 장점 : 단순하고 효율적

  - 단점 : 적절한 k값을 모델 개발자가 직업 알아내야 함

 

ㅇknn의 원리

새로 들어온 데이터가 기존 데이터 중에서 (악성종양, 양성종양) 어느 데이터에 더 인접해 있는지 거리를 계산해서 가장 가까운 거리에 있는 데이터를 자기의 이웃으로 선택하는 것

거리를 계산할 때 사용하는 수학식 => 유클리드 거리

 

 

40 knn 알고리즘을 R 로 구현하기

예제1. 두점의 좌표를 지정

a <- c(2,4)
b <- c(5,6)

예제2. 두점 사이의 거리를 구한다

sqrt( sum(a-b)^2 )

R에서 루트함수 : sqrt()

 

예제3. 3차원에서의 두점 사이의 거리를 구한다

a = c(0,3,2)
b = c(2,0,0)

sqrt( sum((a-b)^2) )

4.123106

 

예제4. a지점과 b지점 사이의 거리를 구하는 함수를 생성하시오.

a = c(0,3,2)
b = c(2,0,0)

distance <- function(a,b){ return (sqrt( sum((a-b)^2) ) ) }
distance(a,b)

4.123106

 

예제5. 책 118페이지의 표를 코드로 구현해서 위에서 만든 distance함수를 이용해 책 118 페이지의 있는 좌표들과 c(4,4)와의 거리를 구하시오.

temp <- c()

for (i in 1:6){
  temp <- append(temp,distance(c(x[i],y[i]),c(4,4)))
}
print(temp)

7.810250 3.000000 6.708204 6.708204 6.082763 4.242641

 

예제6. (점심시간 문제) 위의 temp의 거리들 중에 가장 작은 값을 출력하시오.

# R
x <- c(10,1,10,7,3,1)
y <- c(9,4,1,10,10,1)

distance <- function(a,b){ return (sqrt( sum((a-b)^2) ) ) }

temp <- c()
for (i in 1:6){
  temp <- append(temp,distance(c(x[i],y[i]),c(4,4)))
}
print( min(temp) )

예제7. 책 118페이지에 나온 표를 데이터 프레임으로 생성하시오.

 

질문 : 토마토와 가장 가까운 거리의 음식 종류가 무엇인가 ?

# R
item <- data.frame('ingredient'=c('apple','bacon','banana','carrot','celery','cheese'),
                     'sweetness'=c(10,1,10,7,3,1),
                     'crunchiness'=c(9,4,1,10,10,1),
                     'food type' = c('fruit','protein','fruit','vegetable','vegetable','protein'))
tomato = c(8,4)

x <- item$sweetness
y <- item$crunchiness

distance <- function(a,b){ return (sqrt( sum((a-b)^2) ) ) }

temp <- c()
for (i in 1:6){
  temp <- append(temp, distance(c(x[i],y[i]),tomato))
}

print(temp)

5.385165 7.000000 3.605551 6.082763 7.810250 7.615773

 

예제8. 위의 6개의 거리를 item데이터 프레임의 dist라는 파생변수로 생성하시오.

item$dist <- temp
item

예제9. 위의 거리정보로 데이터프레임에 rnk라는 순위 데이터 파생변수를 생성하시오.

library(dplyr)
item$rnk <- dense_rank(item$dist)
item

예제10. 위의 결과에서 순위가 1 ~ 3등까지의 음식종류를 출력하시오.

item[item$rnk <= 3, c("food_type")]

"fruit"     "fruit"     "vegetable"

> 즉, knn에서 k값 3을 줬을 때의 결과로 보면 됨

 

예제11. 위의 결과에서 최빈값을 출력하시오.

a <- item[item$rnk <= 3, c("food_type")]
b <- table(a)[table(a)== max(table(a))]
names(b)

"fruit"

> 결론 : 토마토와 가장 가까운 거리의 음식종류는 k를 3으로 했을 때 "과일"이었음.

 

 

41 knn 알고리즘을 파이썬으로 구현하기

예제1. R로 구현한 데이터 프레임을 파이썬 판다스 데이터 프레임으로 생성하시오

# python
import pandas as pd

item = pd.DataFrame( {'ingredient': ['apple','bacon','banana','carrot','celery','cheese'],
       'sweetness':[10,1,10,7,3,1],
       'crunchiness':[9,4,1,10,10,1],
       'food_type':['fruit','protein','fruit','vegetable','vegetable','protein']} )
item

예제2. 아래의 a지점과 b지점 사이의 유클리드 거리를 구하는 distance 함수를 파이썬으로 생성하시오.

import math

a=[0,3,2]
b=[2,0,0]

def distance(a,b):
    sum = 0
    for i in range(len(a)):
        sum += (a[i]-b[i])**2
    return math.sqrt(sum)

distance(a,b)

예제3. 위에서 만든 distance 함수를 이용해서 아래의 토마토 좌표와의 fruits음식 좌표들과의 거리들을 구하시오

import pandas as pd

item = pd.DataFrame( {'ingredient': ['apple','bacon','banana','carrot','celery','cheese'],
       'sweetness':[10,1,10,7,3,1],
       'crunchiness':[9,4,1,10,10,1],
       'food_type':['fruit','protein','fruit','vegetable','vegetable','protein']} )

def distance(a,b):
    sum = 0
    for i in range(len(a)):
        sum += (a[i]-b[i])**2
    return math.sqrt(sum)

tomato = [8,4]
dist = []
for i in range(6):
    x = item.iloc[i,1]  # sweetness
    y = item.iloc[i,2]  # crunchiness
    dist.append( distance([x,y], tomato) )
    
print(dist)

예제4. 위의 dist 리스트의 데이터를 item 데이터 프레임의 파생변수로 생성하시오. 파생변수명은 dist로 하세요.

item['dist'] = dist
item

문제231. 음식종류와 순위를 출력하시오. 순위는 거리(dist)가 작은것부터 높은순으로 순위가 부여되게 하시오.

item['rnk'] = item['dist'].rank(method = 'dense', ascending = True).astype(int)
item[['food_type','rnk']].sort_values('rnk', ascending = True)

문제232. item 데이터 프레임에 rnk란 이름으로 거리에 대한 순위를 컬럼을 생성하시오.

item['rnk'] = item['dist'].rank(method = 'dense', ascending = True).astype(int)

문제233. item에서 순위1~3등까지의 음식종류를 출력하시오.

item[['food_type']][item.rnk <= 3]

 

문제234. 위의 결과에서 최빈값을 출력하시오.

item[['food_type']][item.rnk <= 3].mode()

mode() : 최빈값 출력하는 함수

 

 

42 knn 머신러닝 알고리즘을 이용하여 유방암 데이터 분류 - p.128

1단계 : 데이터 수집 -> 데이터 불러오기, 데이터에 대한 출처와 설면

2단계 : 데이터 탐색 -> 결측치, 이상치, 데이터 분포 확인(히스토그램 + 정규분포),

                                 수치형 데이터의 정규화 또는 표준화 작업을 수행

3단계 : 데이터 모델 훈련과 분류 -> 모델 설정, 모델훈련, 모델 예측(분류)

4단계 : 모델 성능평가 -> 이원교차표를 통해서 정확도 확인

5단계 : 모델 성능개선 -> 모델의 예측능력, 분류 능력을 높이는 작업

 

- 1단계 : 데이터 수집( 유방암 데이터 :wisc_bc_data.csv)

# R
wbcd <- read.csv("c:\\data\\wisc_bc_data.csv")
head(wbcd) # 데이터 확인
nrow(wbcd) # 행의 갯수
ncol(wbcd) # 열의 갯수

위스콘신 유방암 진단 데이터셋으로 이 데이터는 569개의 암조직 검사 예시가 들어있으며, 각 예시는 32개의 특징을 가짐. 그 특징은 디지털 이미지에 존재하는 세포핵의 특성을 나타냄.

 

독립변수 = 반지름, 조밀성, 질감, 오목함, 둘레, 오목점, 넓이, 대칭성, 매끄러움, 프랙탈 차원...........

종속변수(정답) = diagnosis : 양성(B) / 악성(M)

str(wbcd)  # 데이터 프레임의 구조 확인

정답(diagnosis)만 문자형이고 나머지는 전부 숫자형 데이터. 그러면 knn 알고리즘으로 분류하기 딱 좋음.

 

- 2단계 : 데이터 탐색

1. 정답 데이터인 diagnosis에서 양성이 몇개이고 악성이 몇개인지 출력하시오

table(wbcd$diagnosis)

  B   M 
357 212 

악성데이터와 양성 데이터가 50:50으로 분포되어 있는 것이 가장 이상적이나 보통 그렇게 분포되어 있지 않음.

 

2. 결측치 확인

colSums(is.na(wbcd))

모든 컬럼들이 전부 결측치가 없는 데이터

 

3. 이상치가 많은 컬럼이 무엇인지 확인하시오.

# 이상치 찾는 코드
install.packages("outliers")
library(outliers)

grubbs.flag <- function(x) {
  outliers <- NULL
  test <- x
  grubbs.result <- grubbs.test(test)
  pv <- grubbs.result$p.value
  while(pv < 0.05) {
    outliers <- c(outliers,as.numeric(strsplit(grubbs.result$alternative," ")[[1]][3]))
    test <- x[!x %in% outliers]
    grubbs.result <- grubbs.test(test)
    pv <- grubbs.result$p.value
  }
  return(data.frame(X=x,Outlier=(x %in% outliers)))
}

colnames(wbcd)  # wbcd 의 컬럼명 확인 

a <- grubbs.flag(wbcd$radius_mean)  # wbcd 의 radius_mean 컬럼에 이상치가 있는지 확인 
#  하기위해 데이터 프레임을 생성 
a[a$Outlier==TRUE,     ]               

for  ( i  in  3 : length(colnames(wbcd) ) ) {
  
  a <- grubbs.flag( wbcd[  ,  colnames(wbcd)[i] ]  )
  b <- a[a$Outlier==TRUE, "Outlier" ]
  print ( paste( colnames(wbcd)[i], ' --->', length(b) )  )
  
}

dimension_se, symmetry_se, perimeter_se가 상대적으로 다른 컬럼들에 비해 이상치가 많이 있음.

 

4. 정규분포 + 히스토그램 그래프를 그려서 데이터들이 정규성을 보이는지 확인

par(mfrow = c(1,3))
m<-sort(wbcd$dimension_se)

hist(m, xlab="dimension_se",ylab="cnt",main='wbcd dimension_se',
     col = 'pink')
par(new=T)
plot(m,dnorm(m,mean=mean(m),sd=sd(m)),type="l",axes=FALSE,ann=FALSE,
     lwd=1.2)
####
m<-sort(wbcd$symmetry_se)

hist(m, xlab="symmetry_se",ylab="cnt",main='wbcd symmetry_se',
     col = 'pink')
par(new=T)
plot(m,dnorm(m,mean=mean(m),sd=sd(m)),type="l",axes=FALSE,ann=FALSE,
     lwd=1.2)
####
m<-sort(wbcd$perimeter_se)

hist(m, xlab="perimeter_se",ylab="cnt",main='wbcd perimeter_se',
     col = 'pink')
par(new=T)
plot(m,dnorm(m,mean=mean(m),sd=sd(m)),type="l",axes=FALSE,ann=FALSE,
     lwd=1.2)

이상치가 많은 컬럼에 대해서 히스토그램 그래프와 정규분포 그래프를 같이 확인해보니 왼쪽으로 데이터가 치우쳐져 있고 오른쪽으로 꼬리가 긴(왜도가 0보다 큰)  데이터의 분포를 보이고 있음.

 

- 3단계 : 데이터로 모델 훈련

1. 데이터의 구조를 확인하여 라벨(정답) 컬럼이 factor형인지 확인하시오.

str(wbcd)
# diagnosis 컬럼이 벡터형임을 확인

wbcd <- read.csv("c:\\data\\wisc_bc_data.csv", stringsAsFactors = TRUE)
# 데이터를 다시 factor로 불러옴
str(wbcd)
# 데이터 구조 factor 확인함

2. 데이터를 양성과 악성이 잘 섞일 수 있도록 데이터를 섞어줘야함.

sample(10)

위와 같이 수행하면 숫자 1~10번의 위치가 수행할 때마다 변경됨

sample(nrow(wbcd))

 

wbcd의 데이터 인덱스들이 sample() 함수로 인해 수행할 때마다 랜덤으로 위치가 변경됨

wbcd_shuffle <- wbcd[sample(nrow(wbcd)), ]
wbcd_shuffle

3. 훈련할 때 필요한 컬럼만 선택함

wbcd_shuffle2 <- wbcd_shuffle[ , c(-1,-2)] #1,2번 컬럼 제외(1:id, 2:diagnosis)
ncol(wbcd_shuffle2)  # 이전에는 32개였는데 지금 확인해보면 30개 나옴

4. 컬럼들의 단위가 다 다르므로 데이터를 정규화 함

normalize <- function(x){return ( (x-min(x)) / (max(x)-min(x)) )}
wbcd_n <- as.data.frame(lapply(wbcd_shuffle2, normalize))
summary(wbcd_n)

summary(wbcd_n)해서 값을 확인하면 모든 컬럼의 min은 0, max는 1로 정규화 되어있음을 확인할 수 있음.

 

5. 전체569개 행의 데이터를 훈련(공부할) 데이터와 테스트(시험볼) 데이터로 나눕니다.

(훈련 데이터 9, 테스트 데이터 1)

nrow(wbcd_n)  # 569
n_90 <- round(0.9*nrow(wbcd_n))
n_90  # 512

wbcd_train <- wbcd_n[1:512, ] # 훈련데이터 구성
wbcd_test <- wbcd_n[513:569, ] # 테스트데이터 구성

nrow(wbcd_train) # 512
nrow(wbcd_test) # 57

6. 정답도 훈련과 테스트로 나눕니다.

head(wbcd_shuffle[,2]) # 정답 컬럼이 2번이 맞는지 확인
wbcd_train_label <- wbcd_shuffle[1:512,2]
wbcd_test_label <- wbcd_shuffle[513:569,2]

length( wbcd_train_label)  # 벡터라서 length()사용, 512
length( wbcd_test_label) # 57 데이터 확인 완

7. 512개의 훈련 데이터와 훈련 데이터의 정답으로 거리계산한 모델로 테스트 데이터 57개를 분류합니다.

install.packages("class")  #knn알고리즘 돌리기 위한 패키지 설치
library(class) # class 라이브러리
result1 <- knn(train = wbcd_train, test=wbcd_test, cl = wbcd_train_label, k = 1)
result1

> knn 함수 설명(p.137) :

   result(변수에 예측값을 담음) <- knn(train = 훈련데이터, test = 테스트 데이터, cl = 훈련 데이터의 정답, k = 1)

 

- 4단계 : 모델 성능평가

예측값인 result1과 실제 정답인 wbcd_test_label이 서로 몇개나 같은지 확인합니다.

result1 == wbcd_test_label  # TRUE/FALSE로 결과가 출력됨
sum(result1 == wbcd_test_label) # TRUE의 갯수가 출력됨

57개 중 55개를 맞췄음. 2개 틀리고 다 맞춤.

 

> sample() 랜덤으로 훈련데이터와 테스트데이터를 나눴기 때문에, 프로그램을 돌릴때마다 컴퓨터마다 결과가 다를 수 있음. 똑같이 섞이려면 아래의 코드를 반복해서 돌리면 똑같은 결과가 나옴.

set.seed(1) # seed 숫자를 특정 숫자 하나로 지정하면 sample()할때 컴퓨터마다 동일한 결과가 나옴
sample(10)

 

문제235. (오늘의 마지막 문제) 위의 머신러닝 모델의 성능을 높이는데 sedd값은 1로 두고 가장 좋은 k값이 몇인지 알아내시오.

정확도 100%가 나오는 k값이 몇인지 알아내세요~~~

test_k <- unique(length(wbcd_test_label)%/%2)  # k값 의 범위
find_k <- c()  # wbcd_test_label와 일치하는 데이터의 갯수 담을 빈 변수 생성
for (i in 1:test_k){
  if(i%%2 == 1){
  result <- knn(train = wbcd_train, test=wbcd_test, cl = wbcd_train_label, k = i)
  find_k[i] <- sum(result==wbcd_test_label)}
}  # 홀수인 데이터만 변수의 홀수자리에 넣음

k <- which.max(find_k) # 가장 큰 값의 위치 찾기
pct <- find_k[k]/length(wbcd_test_label) * 100

print(paste('k값은',k,'이고, 정확도는',pct,'% 입니다.'))

library(class) # class 라이브러리

test_k <- unique(length(wbcd_test_label)%/%2)  # k값 의 범위
find_k <- c()  # wbcd_test_label와 일치하는 데이터의 갯수 담을 빈 변수 생성
for (i in 1:test_k){
  if(i%%2 == 1){
  result <- knn(train = wbcd_train, test=wbcd_test, cl = wbcd_train_label, k = i)
  correct <- sum(result==wbcd_test_label)
  pct <- correct/length(wbcd_test_label) * 100
  find_k <- append(find_k,paste('k=',i,'---->',round(pct),'%')) } }

find_k

 

+) 코드 정리

####데이터 수집
wbcd <- read.csv("c:\\data\\wisc_bc_data.csv")
head(wbcd) # 데이터 확인
nrow(wbcd) # 행의 갯수
ncol(wbcd) # 열의 갯수

str(wbcd)  # 데이터 프레임의 구조 확인

####데이터 탐색
table(wbcd$diagnosis)

colSums(is.na(wbcd))

# 이상치 확인
install.packages("outliers")
library(outliers)

grubbs.flag <- function(x) {
  outliers <- NULL
  test <- x
  grubbs.result <- grubbs.test(test)
  pv <- grubbs.result$p.value
  while(pv < 0.05) {
    outliers <- c(outliers,as.numeric(strsplit(grubbs.result$alternative," ")[[1]][3]))
    test <- x[!x %in% outliers]
    grubbs.result <- grubbs.test(test)
    pv <- grubbs.result$p.value
  }
  return(data.frame(X=x,Outlier=(x %in% outliers)))
}

colnames(wbcd)  # wbcd 의 컬럼명 확인 

a <- grubbs.flag(wbcd$radius_mean)  # wbcd 의 radius_mean 컬럼에 이상치가 있는지 확인 
#  하기위해 데이터 프레임을 생성 
a[a$Outlier==TRUE,     ]               

for  ( i  in  3 : length(colnames(wbcd) ) ) {
  
  a <- grubbs.flag( wbcd[  ,  colnames(wbcd)[i] ]  )
  b <- a[a$Outlier==TRUE, "Outlier" ]
  print ( paste( colnames(wbcd)[i], ' --->', length(b) )  )
  
}


#### 데이터로 모델 훈련
wbcd <- read.csv("c:\\data\\wisc_bc_data.csv", stringsAsFactors = TRUE)
str(wbcd)

table(wbcd$diagnosis)
colSums(is.na(wbcd))

set.seed(1)
wbcd_shuffle <- wbcd[sample(nrow(wbcd)), ]

wbcd_shuffle2 <- wbcd_shuffle[ , c(-1,-2)] #1,2번 컬럼 제외(1:id, 2:diagnosis)
ncol(wbcd_shuffle2)  # 이전에는 32개였는데 지금 확인해보면 30개 나옴

normalize <- function(x){return ( (x-min(x)) / (max(x)-min(x)) )}
wbcd_n <- as.data.frame(lapply(wbcd_shuffle2, normalize))
summary(wbcd_n)

nrow(wbcd_n)  # 569
n_90 <- round(0.9*nrow(wbcd_n))
n_90  # 512

wbcd_train <- wbcd_n[1:512, ] # 훈련데이터 구성
wbcd_test <- wbcd_n[513:569, ] # 테스트데이터 구성

nrow(wbcd_train) # 512
nrow(wbcd_test) # 57

head(wbcd_shuffle[,2]) # 정답 컬럼이 2번이 맞는지 확인
wbcd_train_label <- wbcd_shuffle[1:512,2]
wbcd_test_label <- wbcd_shuffle[513:569,2]

length( wbcd_train_label)  # 벡터라서 length()사용, 512
length( wbcd_test_label) # 57 데이터 확인 완

library(class) # class 라이브러리

test_k <- unique(length(wbcd_test_label)%/%2)  # k값 의 범위
find_k <- c()  # wbcd_test_label와 일치하는 데이터의 갯수 담을 빈 변수 생성
for (i in 1:test_k){
  if(i%%2 == 1){
    result <- knn(train = wbcd_train, test=wbcd_test, cl = wbcd_train_label, k = i)
    find_k[i] <- sum(result==wbcd_test_label)}
}  # 홀수인 데이터만 변수의 홀수자리에 넣음

k <- which.max(find_k) # 가장 큰 값의 위치 찾기
pct <- find_k[k]/length(wbcd_test_label) * 100

print(paste('k값은',k,'이고, 정확도는',pct,'% 입니다.'))