機械学習手習い: k近傍法を使ったレコメンドシステムを作る
「入門 機械学習」手習い、10日目。「10章 k近傍法:推薦システム」です。
k近傍法を使って類似度の高いデータを集める手法を学び、これを使ってRユーザーにRパッケージを推薦するシステムを作ります。
# 前準備 > setwd("10-Recommendations/")
k近傍法の概要
k近傍法は、データ間の距離を使ってデータを分類する手法です。 k近傍法であれば、以下のような、データのばらつきが多く、スパムフィルタを作るときに使った、線形決定境界での分類が難しいデータもうまく分類することができます。
> library('ggplot2') > df <- read.csv(file.path('data', 'example_data.csv')) > head(df) X Y Label 1 2.373546 5.398106 0 2 3.183643 4.387974 0 3 2.164371 5.341120 0 4 4.595281 3.870637 0 5 3.329508 6.433024 0 6 2.179532 6.980400 0 > plot <- ggplot(df, aes(x = X, y = Y)) + geom_point(aes(shape = Label)) + scale_shape_identity() > ggsave(plot, filename = "01.png")
このデータからk近傍法を使って、ある点のデータのLabelを予測してみます。 まずは、各点ごとのユークリッド距離を計算する関数を用意。
# データフレーム内の各点間の距離を格納するマトリックスを作る > distance.matrix <- function(df) { distance <- matrix(rep(NA, nrow(df) ^ 2), nrow = nrow(df)) for (i in 1:nrow(df)) { for (j in 1:nrow(df)) { distance[i, j] <- sqrt((df[i, 'X'] - df[j, 'X']) ^ 2 + (df[i, 'Y'] - df[j, 'Y']) ^ 2) } } return(distance) }
特定の点から最も近い点をk個返す関数を作ります。
# distanceのiの位置にある点に最も近い点をk個返す。 k.nearest.neighbors <- function(i, distance, k = 5) { return(order(distance[i, ])[2:(k + 1)]) }
最後に、予測を行うknn関数を定義。
> knn <- function(df, k = 5) { # 距離行列を計算 distance <- distance.matrix(df) # 結果を格納する行列を作る predictions <- rep(NA, nrow(df)) for (i in 1:nrow(df)) { # もっとも近い5個を取り出し、多数決でラベルの値を推測する indices <- k.nearest.neighbors(i, distance, k = k) predictions[i] <- ifelse(mean(df[indices, 'Label']) > 0.5, 1, 0) } return(predictions) }
準備ができたので、実行して精度を評価してみます。
> df <- transform(df, kNNPredictions = knn(df)) sum(with(df, Label != kNNPredictions)) [1] 7
7つ失敗しました。データ数は100なので、精度は93%。
↑のk近傍法の実装は、実はRに用意されていたりするので、そちらを使ってみます。
> rm('knn') # 自作したknnを削除 > library('class') > df <- read.csv(file.path('data', 'example_data.csv')) # データの半分をランダム抽出し、一方で訓練、他方で評価を行う。 > n <- nrow(df) > set.seed(1) > indices <- sort(sample(1:n, n * (1 / 2))) > training.x <- df[indices, 1:2] > test.x <- df[-indices, 1:2] > training.y <- df[indices, 3] > test.y <- df[-indices, 3] # 推測を実行 > predicted.y <- knn(training.x, test.x, training.y, k = 5) > sum(predicted.y != test.y) [1] 7
7つ失敗。データ数は50なので、86%の精度です。
比較のため、ロジスティック回帰での推測も行ってみます。
> logit.model <- glm(Label ~ X + Y, data = df[indices, ]) > predictions <- as.numeric(predict(logit.model, newdata = df[-indices, ]) > 0) > sum(predictions != test.y) [1] 16
こちらは16個失敗で、精度は68%。このような線形分類が難しいデータの場合、k近傍法は線形分類器よりうまく動作します。
Rパッケージのレコメンドシステムを作る
概要がつかめたところで、k近傍法を使ってRユーザーにお勧めのRパッケージをレコメンドするシステムを作ります。
具体的には、ユーザーがインストールしているパッケージ情報から、それと似たパッケージを探して推薦するアイテムベースのレコメンドを行います。
まずはパッケージデータの読み込み。
> installations <- read.csv(file.path('data', 'installations.csv')) > head(installations) Package User Installed 1 abind 1 1 2 AcceptanceSampling 1 0 3 ACCLMA 1 0 4 accuracy 1 1 5 acepack 1 0 6 aCGH.Spline 1 0
Installed
が 1のものがユーザーがインストールしているパッケージを示します。
まずはこのデータを「パッケージ x ユーザー」の行列に変換します。
> library('reshape') > user.package.matrix <- cast(installations, User ~ Package, value = 'Installed') > user.package.matrix[, 1] > row.names(user.package.matrix) <- user.package.matrix[, 1] > user.package.matrix <- user.package.matrix[, -1] > head(user.package.matrix[1:6, 1:6]) abind AcceptanceSampling ACCLMA accuracy acepack aCGH.Spline 1 1 0 0 1 0 0 3 1 1 0 1 1 1 4 0 1 1 1 1 0 5 1 1 1 0 1 0 6 1 1 1 0 1 0 7 1 1 1 0 1 1
この行列を引数に cor
を実行し、各列の相関係数を計算します。
今回は、これを類似度を測る指標として使います。
> similarities <- cor(user.package.matrix) > similarities[1:6, 1:6] [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1.00000000 -0.04822428 -0.19485928 -0.074935401 0.111369209 0.114616917 [2,] -0.04822428 1.00000000 0.32940392 -0.152710227 -0.151554446 -0.129640745 [3,] -0.19485928 0.32940392 1.00000000 -0.194859284 0.129323382 0.068326672 [4,] -0.07493540 -0.15271023 -0.19485928 1.000000000 -0.129930744 0.006251832 [5,] 0.11136921 -0.15155445 0.12932338 -0.129930744 1.000000000 0.007484812 [6,] 0.11461692 -0.12964074 0.06832667 0.006251832 0.007484812 1.000000000
相関係数は1~-1の数値なので、これを、1が距離ゼロ(最も近い)、-1が距離無限大(最も遠い)になるように変換します。
> distances <- -log((similarities / 2) + 0.5) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 0.0000000 0.7425730 0.9098854 0.7710389 0.5875544 0.5846364 [2,] 0.7425730 0.0000000 0.4084165 0.8588597 0.8574965 0.8319964 [3,] 0.9098854 0.4084165 0.0000000 0.9098854 0.5715285 0.6270536 [4,] 0.7710389 0.8588597 0.9098854 0.0000000 0.8323296 0.6869148 [5,] 0.5875544 0.8574965 0.5715285 0.8323296 0.0000000 0.6856902 [6,] 0.5846364 0.8319964 0.6270536 0.6869148 0.6856902 0.0000000
データができたので、k近傍のパッケージを取り出して、パッケージのインストール確率を算出する関数を書きます。
# distanceのiの位置にある点に最も近い点をk個返す。 > k.nearest.neighbors <- function(i, distances, k = 25) { return(order(distances[i, ])[2:(k + 1)]) } # 指定ユーザーが指定したパッケージをインストールしている確率を計算する > installation.probability <- function(user, package, user.package.matrix, distances, k = 25){ # 近くのパッケージを取得 neighbors <- k.nearest.neighbors(package, distances, k = k) # 近隣パッケージのインストール率の平均をパッケージのインストール率として返す。 return(mean(sapply(neighbors, function (neighbor) {user.package.matrix[user, neighbor]}))) }
動作確認。ユーザー1が1つめのパッケージをインストールする確率は76%。
> installation.probability(1, 1, user.package.matrix, distances) [1] 0.76
あとは、すべてのパッケージのインストール確率を算出し、確率上位のものを取り出せば、レコメンドエンジンの出来上がり。
# 全パッケージのインストール確率を計算し、高い順にソートして返す。 > most.probable.packages <- function(user, user.package.matrix, distances, k = 25){ return(order(sapply(1:ncol(user.package.matrix), function (package) { installation.probability(user, package, user.package.matrix, distances, k = k) }), decreasing = TRUE)) }
実行してみます。
# インストール確率順にソートしたパッケージ一覧を取得 > listing = most.probable.packages(1, user.package.matrix, distances) # 上位5件のパッケージ名を表示 > colnames(user.package.matrix)[listing[1:5]] > colnames(user.package.matrix)[listing[1:5]] [1] "adegenet" "AIGIS" "ConvergenceConcepts" [4] "corcounts" "DBI"