추천 시스템에서 사용되는 데이터 마이닝 기법-02

데이터 마이닝 기법

이제부터는 K-평균 클러스터링, 서포트 벡터 머신, 의사결정 나무, 배깅, 부스팅, 랜덤 포레스트와 같이 데이터 마이닝 분야에서 널리 사용되는 알고리즘들을 살펴본다.

 

클러스터링 분석

클러스터링 분석(Cluster Analysis) 기법은 한 그룹의 객체들을 다른 그룹보다 더 유사한 객체들로 구성해 그룹 짓는 방식으로 데이터를 그룹화하는 분류 기법이다.

예를 들어, 여행 포털에서 유사한 형태로 예약한 고객을 구별해 그룹화하는 것이다.

위의 예시에서 각각의 그룹을 클러스터라 하며, 각각의 클러스터 구성원(Dagta Point)들은 그들이 속한 그룹의 사용자들과 유사한 특성을 지닌다.

 

클러스터링 분석은 비지도학습 기법이다. 회귀분석과 같은 지도학습은 입력 변수와 반응 변수를 가지며, 입력 변수에 통계적 모형을 적용해 반응 변수를 예측한다. 그러나 비지도 학습 기법에는 예측을 위한 어떠한 반응 변수도 존재하지 않으며 오직 입력 변수들만이 존재한다. 그래서 입력 변수가 반응 변수들을 예측하도록 설계하는 대신에 데이터 세트 안에서 특정한 패턴을 찾도록 노력한다. 클러스터링 알고리즘을는 계층적 클러스터링 분석, K-평균 클러스터링 분석, 2단계 클러스터링 분석 등이 널리 알려져 있으며, 다음 절에서는 K-평균 클러스터링 기법을 알아볼 것이다.

 

K-평균 클러스터링

K-평균 클러스터링 기법은 비지도 학습 기법으로 데이터로부터 K개의 클러스터를 갖도록 하는 반복적 알고리즘이다.

1. 클러스터 할당 단계 : 이 단계에서는 임의의 두 개 클러스터 포인트를 선택하고각각의 데이터 포인트들을 자신과 가까운 클러스터 포인트로 할당한다.
2. 중심 이동 단계 : 이번 단계에서는 각 클러스터의 데이터 포인트의 평균을 구해 계산된 지점으로 중심점을 이동한다.

위의 두 단계를 모든 데이터 포인트가 두 개 그룹으로 나뉘고 데이터 포인트의 평균값과 중심점이 같아져서 중심점의 이동이 더 이상 없을 때까지 반복한다.

 

iris 데이터 세트를 이용해 K-평균 클러스터링을 R 코드로 구현해보자.

#K-평균 클러스터링
library(cluster)
data(iris)
iris$Species = as.numeric(iris$Species)
kmeans <- kmeans(x = iris, center = 5)
clusplot(iris, kmeans$cluster, color = TRUE, shade = TRUE, labels = 13, lines = 0)

위의 이미지는 iris 데이터 세트의 클러스터를 보여주며, 클러스터들을 통해 95% 정도의 데이터를 설명할 수 있다. 위의 예제엣허 클러스터의 개수 K 값은 Elbow 기법(팔꿈치와 같이 급격히 꺾이는 점을 찾아 모델 생성에 사용할 변수의 개수를 정하는 기법)을 사용해 다음과 같은 방법으로 구할 수 있다.

 

library(ggplot2)
data("iris")
iris$Species = as.numeric(iris$Species)
cost_df <- data.frame()
for (i in 1:!00){
  kmeans <- kmeans(x = iris, centers = i, iter.max = 50)
  cost_df <- rbind(cost_df, cbind(i, kmeans$tot.withinss))
}
names(cost_df) <- c("cluster", "cost")

str(cost_df)

#Elbow 기법으로 유휴한 클러스터의 수를 식별한다.
#비용 그래프
ggplot(data = cost_df, aes(x = cluster, y = cost, group = 1 )) +
  theme_bw(base_family = "Garamond") +
  geom_line(colour = "darkgreen") +
  theme(text = element_text(size = 20)) +
  ggtitle("Reduction In Cost For Values of `k`\n") +
  xlab("\nClusters") +
  ylab("Within-Cluster Sum of Squares \n")

 

 

위의 그림을 통해 클러스터의 개수가 다섯 개인 지점에서 비용 함수의 방향이 급격하게 바뀌는 것을 확인할 수 있다. 따라서 클러스터의 개수를 5로 정하고, 그래프가 꺾이는 지점(Elbow Point)에서 적당한 클러스터의 수를 결정하게 되므로 이를 Elbow 기법이라 한다.

 

서포트 벡터 머신

서포트 벡터 머신(SVM, Support Vector Machine)은 지도 학습 알고리즘으로 분류 문제를 해결하는 경우 사용되며, 일반적으로 분류 문제를 해결하는 데 가장 좋은 알고리즘 중 하나로 여겨진다. 트레이닝 데이터가 두 가지 카테고리 중 한 곳에 속하는 구성을 가진다면, SVM 트레이닝 알고리즘은 새로운 입력 값을 어느 한쪽의 카테고리로 할당하는 모델을 생성한다. 이 모델은 데이터들을 각 카테고리의 데이터들이 경계 지역에 가능한 한 넓은 여백을 갖도록 공간상에 점으로 표현한 것이며 다음 그림과 같다. 그리고 새로운 데이터들이 입력되면 같은 공간상에서 데이터가 속한 곳의 여백을 기초로 해서 어느 데이터들이 입력되면 같은 공간상에서 데이터가 속한 곳의 여백을 기초로 해서 어느 카테고리에 속하게 되는지 예측된다. 여기서는 복잡한 수식을 다루지 않고 간략한 개요를 살펴보며 실제로 SVM을 구해볼 것이다.

SVM을 p 차원의 데이터 세트에 적용할 때 데이터들은 p-1 차원의 초평면상에 표현되며, 알고리즘은 각각의 분류들 사이에 충분한 여백의 공간을 확보하도록 하는 명확한 경계선을 찾아낸다. 다른 분류 알고리즘들과는 다르게 SVM은 데이터들을 구분하는 경계를 만들어내며, 다음 그림에서 보는 것과 같이 최대한의 여백을 갖는 경계선을 찾도록 한다.

 

위의 그림과 같이 두 개의 분류 값을 갖는 2차원의 데이터를 생각해보자. SVM 알고리즘을 적용할 때, 먼저 모든 데이터 포인트들을 표시할 수 있는 1차원 초평면이 존재하는지 확인한다. 만약 그러한 초평면이 존재한다면, 이 선형 분류기(Linear classifier)는 그룹을 경계 짓는 여백을 포함해 카테고리의 구분하는 의사결정을 위한 경계선을 만든다.

 

위의 그림에서 굵은 선이 의사결정 경계며, 이 경계 좌우의 파란색과 빨간색의 가는 선들을 공간으로 분류된 그룹들이 갖는 여백 공간이다. 새로운 데이터를 분류 예측할 때, 입력 값은 두 카테고리 중 한쪽으로 분류될 것이다.

 

여기서 핵심적인 사항은 다음과 같다.

• 무한한 수의 초평면을 생성할 수 있지만, SVM은 최대한의 여백 공간을 갖도록 하는 오직 단 한개만의 초평면을 선택한다. 다시 말해, 경게를 짓는 초평면은 트레이닝 데이터들로부터 가장 멀리 있는 유일한 초평면이다.
• 분류기는 오직 초평면의 경계 지역에 위치한 데이터 지점들에만 의존한다. 즉, 위의 그림에서 가는 경계선 및 가장 가까운 데이터와만 관계가 있으며 데이터 세트의 다른 관측치들과는 관계가 없다. 이러한 데이터 점들을 서포트 벡터라 한다.
• 의사결정 경계는 오직 서포트 벡터에만 영향을 받으며 경계 밖에 위치한 다른 관측치들에는 영향을 받지 않는다. 서포트 벡터가 아닌 데이터의 위치를 변경하더라도 의사 결정 경계에는 아무런 영향이 없다. 하지만 서포트 벡터의 위치가 변한다면, 의사결정 경계 역시 달라진다.
• 트레이닝 데이터의 가장 넓은 여백 공간은 테스트 데이터에서도 테스트 데이터를 정확하게 분리하도록 하는 가장 넓은 여백 공간이다.
• SVM은 빗너형 데이터 세트(Non-linear Dataset)에도 잘 작동한다. 이러한 방사형 커털 함수(Radial Kernel Function)를 사용한다.

iris 데이터 세트상에서 SVM을 구현한 다음의 R 코드를 본다. 여기서는 e1071 패키지를 사용해 SVM을 실행할 것이며, R에서 e1071 패키지의 SVM 함수는 서포트 벡터 머신을 구현하는 내용을 포함하고 있다.

그리고 SVM이 tune 함수 내부에서 호출돼 비용 함수에 다양한 인수 값들을 사용함으로써 교차 검증을 수행하는 것을 볼 수 있다.

교차 검증은 아직 보지 못한 데이터에 테스트를 진행하기 전에 예측 모델의 정확도를 평가하기 위해 사용된다.

#SVM
library(e1071)
data("iris")
sample = iris[sample(nrow(iris)),]
train = sample[1:105,]
test = sample[106:150,]
tune = tune(svm, Species~., data = train, kernel = "radial", scale = FALSE,
            ranges = list(cost = c(0.001, 0.01, 0.1, 1, 5, 10, 100)))

tune$best.model

Call:
best.tune(method = svm, train.x = Species ~ ., data = train, ranges = list(cost = c(0.001, 0.01, 0.1, 1, 5, 10, 100)), kernel = "radial", 
    scale = FALSE)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  radial 
       cost:  1 

Number of Support Vectors:  30

summary(tune)

Parameter tuning of ‘svm’:

- sampling method: 10-fold cross validation 

- best parameters:
 cost
    1

- best performance: 0.03727273 

- Detailed performance results:
   cost      error dispersion
1 1e-03 0.60818182 0.07635522
2 1e-02 0.60818182 0.07635522
3 1e-01 0.07363636 0.11195319
4 1e+00 0.03727273 0.04819039
5 5e+00 0.04818182 0.06937343
6 1e+01 0.04818182 0.06937343
7 1e+02 0.06636364 0.07856028

model = svm(Species~., data=train, kernel = "radial", cost = 10, scale = FALSE)
#summary(tune)의 결과로부터 cost=1을 선택했다.

 

tune$best.model 객체를 통해 비용 함수의 인수가 1일 때 모델이 가장 좋은 성능을 발휘하며 이때 총 서포트 벡터의 수가 30인 것을 알 수 있다.

pred = predict(model, test)

 

의사결정 나무

의사결정 나무는 간단하고 빠르며 트리 구조 형태의 지도 학습 알고리즘으로 분류 문제를 해결하는 알고리즘이다. 이 알고리즘은 다른 로지스틱 회귀 분석 방법들에 비해 다소 성능이 낮음에도 불구하고 추천 시스템을 다룰 떄 꽤 쓸모가 있다.

예를 들어 의사결정 나무를 정의해본다. iris 데이터 세트에서 꽃입과 꽃받침의 폭과 길이 같은 특징들을 바탕으로 꽃의 종류를 분류하는 상황을 가정하고 이러한 문제를 해결하는 방법으로 의사결정 나무를 적용해본다.

1. 알고리즘을 시작할 때 모든 데이터를 활용한다.
2. 다음으로 데이터들을 두 분류로 나눌 수 있는 적당한 질문이나 변수를 선택한다. 우리가 사용한 예시의 경우, 꽃잎의 길이가 Petal.Length > 2.45 이거나 <=2.45인 경우로 나눌 것이다. 이는 다른 꽃들로부터 setosa 종류를 구분하는 기준이 된다.
3. 이번에는 Petal.Length > 2.45인 데이터들을 다음 그림과 같이 같은 변수인 꽃잎의 길이가 Petal.Length <4.85인 경우로 추가롤 분류한다.
4. 이와 같은 데이터 분류를 의사결정 나무 제일 하단의 데이터들이 각각의 반응변수를 나타내거나 데이터를 더는 논리적으로 분류할 수 없을 때까지 계속해서 수행한다.

다음 그림에서 의사결정 나무는 한 개의 루트 노드와 ㄱ데이터가 분류되는 세 개의 내부 노드, 그리고 더 이상 분류를 진행할 수 없는 다섯 개의 단말 노드를 갖는다. 이는 다음과 같이 정의될 수 있다.

• Petal.Length<2.45가 루트노드
• Petal.Length>4.85, Sepal.Length < 5.15와 Petal.Width < 1.75는 내부노드
• 꽃들의 분류 값을 갖는 단말 노드들
• 각 노드를 연결하는 의사결정 나무의 가지 노드들

다음 그림과 같이 생성된 모델을 사용해 새로운 데이터들을 분류할 때 각각의 입력 데이터는 질문에 따라 특정 노드로 분류되고 논리적인 방식을 통해 분류된다.

 

다음은 CRAN에서 다운로드해 설치한 tree 패키지로 iris 데이터 세트를 가지고 의사결정 나무를 구현하는 R 코드다.

 

summary 함수를 통해 모델의 정확도를 나타내는 오분류 비율이 0.0381임을 알 수 있다.

library(tree)
sample = iris[sample(nrow(iris)),]
train = sample[1:105,]
test = sample[106:150,]
model = tree(Species~.,train)
summary(model)

Classification tree:
tree(formula = Species ~ ., data = train)
Variables actually used in tree construction:
[1] "Petal.Length" "Petal.Width"  "Sepal.Length"
Number of terminal nodes:  5 
Residual mean deviance:  0.1332 = 13.32 / 100 
Misclassification error rate: 0.0381 = 4 / 105 

#의사결정 나무 표 그리기
plot(model)
text(model)
pred = predict(model, test[,-5], type="class")
pred
 [1] virginica  versicolor versicolor versicolor versicolor versicolor virginica  virginica  setosa     virginica  virginica  setosa     setosa    
[14] versicolor virginica  setosa     setosa     virginica  setosa     virginica  versicolor setosa     virginica  versicolor setosa     virginica 
[27] virginica  setosa     virginica  versicolor setosa     versicolor virginica  virginica  versicolor versicolor versicolor versicolor virginica 
[40] setosa     virginica  setosa     virginica  virginica  virginica 
Levels: setosa versicolor virginica