機械学習手習い: k近傍法を使ったレコメンドシステムを作る

「入門 機械学習」手習い、10日目。「10章 k近傍法:推薦システム」です。

www.amazon.co.jp

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"