协同过滤实现小型推荐系统

协同过滤

假设有以下用户评分表:

\ p1 p2 p3 p4 p5 p6 p7 p8 p9
u1 1 1 0 0 0 0 0 0 0
u2 1 2 1 0 0 1 0 1 0
u3 12 2 1 0 0 1 0 11 0
u4 0 0 0 0 0 0 0 0 1
u5 0 0 0 0 0 0 0 0 2
u6 0 0 0 0 0 0 0 0 0
u7 11 0 0 7 0 14 1 3 19

其中,每一行代表一个用户, 每一列代表一个产品,每一个元素代表某用户对于某产品的评分。 设用户 ui 的评分向量为 vi , 协同过滤的想法是,以两个评分向量的夹角的余弦代表两个用户 之间的相似度:
file
其中 ei 代表向量 vi 的单位向量。 那么,对于每一行表示一个用户的评分矩阵 A, 按行对其做单位化处理得到新矩阵 B , 协方差矩阵 C = BB' (B' 表示 B 的转置,这里上标 T 始终不能正常显示) 就是用户 的相似度矩阵, C 具有以下特征:
file
Cij 代表用户 i 和用户 j 的相似度。 接下来,求与用户 i 相似度最高的若干用户,然后通过这些用户的评分情况向用户 i 推荐产品。

代码实现

构造评分矩阵

实际上,让用户对产品评分,是不容易实现的,可以通过历史记录,构造评分矩阵。 本次实验环境中,存在用户行为记录表 (user_actions)

user_id product_id keywork action created_at
17 1 NULL view 2018-07-04 08:58:10
10 NULL 218 search 2018-07-04 09:26:54
4 109 NULL view 2018-07-04 09:30:38
28 NULL 218 search 2018-07-04 09:35:41
28 56 NULL view 2018-07-04 09:36:28
34 109 NULL view 2018-07-04 10:06:15
34 109 NULL buy 2018-07-04 10:06:38
34 109 NULL buy 2018-07-04 10:06:46

这里不去关注"搜索"(action=search)行为, 取出浏览和购买的行,因为"浏览"和"购买"的比例大概是 50:1 , 所以,浏览一次记 1 分,购买一次记 50 分。 另外,显然还存在用户表和产品表,以下只用到它们的 id, 表结构无所谓。

首先,获取参与计算的用户 id 和产品 id, 因为 id 可能是不连续的,将它们的索引和 id 之间的映射记录下来, 方便后续计算。因为是以用户为基础的,只读取有历史记录的用户,而产品是从产品表中读取,也就是说在此查询执行之后有交互行为 的新用户不会参与计算,而老用户的行为仍会参与计算。 考虑内存限制,将用户分为几块处理,只计算一个块内用户彼此的相似度,推荐也只会在一个块内的用户间产生,代码如下 :

// 取在 users 和 user_actions 中都存在的 user_id
$users = UserAction::select("user_id")->distinct()
    ->join("users", "user_actions.user_id", "=", "users.id")
    ->orderBy("user_id")
    ->get();

// 用户 id
foreach ($users as $u) {
    $ui[] = $u->user_id;
}
// 用户索引
$iu = array_flip($ui);

$products = Product::select("id")->distinct()->orderBy("id")->get();
// 产品 id
foreach ($products as $p) {
    $pi[] = $p->id;
}
// 产品索引
$ip = array_flip($pi);

// 分块
$k = $this->getChunks();
// 每一块的最大数量
$kn = intval(ceil(count($ui) / $k));
$map = [
    "users" => $ui,
    "indexOfUsers" => $iu,
    "products" => $pi,
    "indexOfProducts" => $ip,
    "chunks" => $k,
    "numberPerChunk" => $kn,
];

用户分块,设定每块最多用户数,计算块数应该更合理

函数 getRatingByUser(int $id) 实现从数据库中读一个用户的评分向量, 其中 zerosArray(int $n) 的作用是返回一个长度为 $n 值全为 0 的数组:

// 点击和购买的比例接近 50 : 1
protected $caseSql = "CASE `action` WHEN 'view' THEN 1 WHEN 'buy' THEN 50 ELSE 0 END AS `score`";
/**
 * 获取一个用户对于每一个产品的评分,得到评分向量
 * @var int $id user id
 * @var array  $ratingArr user rating vector
 * @return array
 */
public function getRatingByUser(int $id) : array
{
    $map = $this->getMap();

    $userActions = UserAction::select("product_id", DB::raw($this->caseSql))
    ->where("user_id", "=", $id)
    ->whereIn("product_id", $map["products"]) // 过滤掉只存在于 user_actions 中的 product_id
    ->where(function ($query) {
        $query->where("action", "=", "view")
        ->orWhere("action", "=", "buy");
    })
    ->orderBy("product_id")
    ->get();

    $ratingArray = $this->zerosArray(count($map["products"]));
    foreach ($userActions as $ua) {
    $index = $map["indexOfProducts"][$ua->product_id];
    $ratingArray[$index] += $ua->score;
    }
    return $ratingArray;
}

循环调用 getRatingByUser(int $id) 得到评分矩阵, 如下:
file

通过评分矩阵,可以得到一些有用的信息:

  1. 矩阵按行求和,代表用户的活跃度,图中高亮的行所对应的用户,明显比其他的活跃
  2. 矩阵按列求和,代表产品的活跃度,图中第一个产品,明显比第二个产品活跃
  3. 矩阵先按行单位化后按列求和,值越大说明该列对应的产品受越多的用户关注
  4. 每一行数据分布情况反应了这一个用户的偏好

考虑到评分矩阵可能被其他程序使用,在保存的时候,不分块,本实现通过指针处理这个文件,不会造成性能问题。

计算相似度

PHP 实现

getSimilarityMatrix(void) 通过评分矩阵计算相似度(协方差)矩阵。 向量运算使用了 math-php 库, 因为 math-php 只能以列向量构建矩阵, 所以由 B'B 计算协方差。 EPSILON = 1e-9 , 将长度小于 EPSILION 的向量视为 0 :

/**
 * 得到用户评分向量相似度矩阵
 * 考虑内存限制,将用户分成 $k 组, 求协方差
 * 如果初始化类传入存储位置, 则保存数据到文件
 * 生成当前进度
 * test:
 *     cache, chunk=1: 60s
 * @yield array
 * @return Generator
 */
public function getSimilarityMatrix() : Generator
{
    $k = $this->getChunks();
    $dir = $this->getDataDir();
    $users = $this->getMap()["users"];
    $urKey = $this->getCacheKey("user_rating");
    $smKey = $this->getCacheKey("sim_mat");
    $nk = intval(ceil(count($users) / $k));
    if ($dir) {
    $file = $dir . DIRECTORY_SEPARATOR . $urKey . ".csv";
    $isBig = filesize($file) > static::MAX_FILE_SIZE;
    // 大文件按行读, 否则直接读入数组
    if ($isBig) {
        $urCsv = fopen($file, "r");
    } else {
        $urCsv = file($file, FILE_IGNORE_NEW_LINES);
    }
    }

    for ($i = 0; $i < $k; $i++) {
    $vs = [];
    if ($i + 1 < $k) {
        $chunk = $nk;
    } else {
        $chunk = count($users) - $nk * $i;
    }
    for ($j = 0; $j < $chunk; $j++) {
        $index = $i * $nk + $j;
        if ($dir) {
        if ($isBig) {
            $arr = str_getcsv(fgets($urCsv));
        } else {
            $arr = str_getcsv($urCsv[$index]);
        }
        } else {
        $arr = Cache::get("$urKey.{$users[$index]}");
        }
        // 单位化处理
        $v = new Vector($arr);
        $v = $v->length() < static::EPSILON ? $v : $v->normalize();
        $vs[] = $v;
    }

    // 计算协方差
    $M = MatrixFactory::create($vs);
    $covMatrix = $M->transpose()->multiply($M);
    $covArray = $covMatrix->getMatrix();

    // 保存数据
    if ($dir) {
        $file = $dir . DIRECTORY_SEPARATOR . "$smKey.$i.csv";
        $smCsv = fopen($file, "w");
        foreach ($covArray as $row) {
        fputcsv($smCsv, $row);
        }
        fclose($smCsv);
    } else {
        Cache::forever("$smKey.$i", $covArray);
    }
    yield [$i + 1, $k];
    }
    if ($dir && $isBig) {
    fclose($urCsv);
    }
}

执行该函数,本次测试耗时 76 秒:

xl@xl:~/apps/blog$ ./artisan tinker
Psy Shell v0.9.9 (PHP 7.2.10 — cli) by Justin Hileman
>>> $rs = new App\Tools\RecommenderSystem(1, storage_path('rsdata'))
=> App\Tools\RecommenderSystem {#2906}
>>> $start = time(); foreach ($rs->getSimilarityMatrix() as $arr){}; $end = time(); echo $end-$start;
76⏎

math-php 的效率

math-php 是未经线性代数优化的库,查看源代码可知,计算矩阵乘法的时间复杂度为 O(n^3) 。 而线性代数优化过的库,在一定规模内(视硬件性能)矩阵操作的时间复杂度可以视为 O(1) 。 实验环境下, 计算 1000 阶矩阵乘法, math-php 效率为 IntelMTK 的 1 / 10000, NumPy 的 1/1000 .

PYTHON 实现

下面是一个简单的 python 实现, 使用了 sklearn.preprocessing.normalize 和 NumPy 库。

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from sklearn.preprocessing import normalize
import numpy as np

# 载入数据
A = np.loadtxt('rs.user_rating.csv', delimiter=',')
# 按行单位化
B = normalize(A, norm='l2', axis=1)
# 求协方差
C = B @ B.transpose()
# 保存数据
np.savetxt('covmat.csv', C)

执行效果:

xl@xl:~/apps/blog/storage/rsdata$ ls -lh
total 14M
-rw-rw-r-- 1 xl xl  313 Nov 17 12:44 covMat.py
-rw-rw-r-- 1 xl xl  35K Nov 17 12:51 rs.map.json
-rw-rw-r-- 1 xl xl  13M Nov 17 12:53 rs.sim_mat.0.csv
-rw-rw-r-- 1 xl xl 632K Nov 16 19:44 rs.user_rating.csv
xl@xl:~/apps/blog/storage/rsdata$ time python3 covMat.py 

real    0m2.206s
user    0m2.315s
sys 0m0.660s
xl@xl:~/apps/blog/storage/rsdata$ ls -lh
total 119M
-rw-rw-r-- 1 xl xl 106M Nov 17 13:03 covmat.csv
-rw-rw-r-- 1 xl xl  313 Nov 17 12:44 covMat.py
-rw-rw-r-- 1 xl xl  35K Nov 17 12:51 rs.map.json
-rw-rw-r-- 1 xl xl  13M Nov 17 12:53 rs.sim_mat.0.csv
-rw-rw-r-- 1 xl xl 632K Nov 16 19:44 rs.user_rating.csv

因为 numpy 使用了更高的精度,矩阵文件 ( covmat.csv ) 比php生成 ( rs.sim_mat.0.csv ) 的大很多,本次测试耗时 2 秒,可以看到,效率提升是很明显的。

最后,得到协方差矩阵如下:
file
可以看到,矩阵是关于对角线对称的,且在对角线上为最大值 1.

实际上,评分矩阵可能是非常稀疏的,可以使用 scipy.sparse 处理。

投票推荐

协方差矩阵中的第 i 行对应用户 i 和其他用户的相似度。 userLikes($uid, $n) 找出和用户 $uid 最相似的 $n 个用户, 其中 getSimVecByUser($uid) 实现取出行向量, userIdToLocation($id) 实现根据用户 id 找到数据位置:

/**
 * 计算和用户 $uid 相似度最高的 $n 个用户, 返回由用户 id 组成的数组
 * @var int $uid user's id
 * @var int $n number of user
 * @return array
 */
public function userLikes($uid, $n = 10) : array
{
    $likes = [];
    $map = $this->getMap();
    $users = $map["users"];
    $kn = $map["numberPerChunk"];
    // 获取相似度向量
    $vec = $this->getSimVecByUser($uid);
    if (!$vec) {
    return [];
    }
    // 逆排序
    arsort($vec);
    // 前 $n 个索引
    $topNI = array_slice(array_keys($vec), 0, $n);
    // 索引转 id
    $location = $this->userIdToLocation($uid);
    $i = $location[0];
    foreach ($topNI as $j) {
    $likes[] = $users[$i * $kn + $j];
    }

    return $likes;
}

python 实现:

# 协方差矩阵按行逆向排序,返回索引
U = np.argsort(-C, axis=1)

接着, getUserFavouriteProducts(int $id, int $n) 实现从评分矩阵中找到 用户 $id 评分最高 的 $n 个产品:

/**
 * 得到用户 $id 评分最高的 $n 个产品, 返回产品 id 数组
 * @var int $id user's id
 * @var int $n number of products
 * @return array
 */
public function getUserFavouriteProducts(int $id, int $n = 10) : array
{
    $dir = $this->getDataDir();
    $key = $this->getCacheKey("user_rating");
    $map = $this->getMap();
    $pi = $map["products"];
    $iu = $map["indexOfUsers"];
    $m = count($iu);
    $index = $iu[$id];
    if ($dir) {
    $file = $dir . DIRECTORY_SEPARATOR . "$key.csv";
    if (filesize($file) > static::MAX_FILE_SIZE) {
        $csv = fopen($file, "r");
        for ($i = 0; $i < $index; $i++) {
        fgets($csv);
        }
        $vec = str_getcsv(fgets($csv));
        fclose($csv);
    } else {
        $arr = file($file, FILE_IGNORE_NEW_LINES);
        $vec = str_getcsv($arr[$index]);
    }
    } else {
    $vec = Cache::get("$key.$id");
    }

    arsort($vec);
    $rn = array_slice($vec, 0, $n, true);
    // 删除评分为 0 的项
    $rn = array_filter($rn, function ($item) {
    return abs($item) > 1e-9;
    });
    $fps = [];
    foreach ($rn as $pid => $score) {
    $fps[] = $pi[$pid];
    }

    return $fps;
}

python 实现:

# 评分矩阵按行逆向排序,返回索引
RI = np.argsort(-R, axis=1)

最后,通过投票,产生推荐产品, 以下投票策略比较粗糙,没有考虑选民的权重:

/**
 * 为用户 $uid 产生至多 $numberOfVoter * $numberOfVote 个推荐产品
 * @var int $uid user id
 * @var int $numberOfVoter 选民数
 * @var int $numberOfVote 每个选民的票数
 * @return array
 */
public function vote($uid, $numberOfVoter, $numberOfVote) : array
{
    $likes = $this->userLikes($uid, $numberOfVoter);
    $ps = [];
    foreach ($likes as $id) {
    $fps = $this->getUserFavouriteProducts($id, $numberOfVote);
    $ps = array_merge($ps, $fps);
    }
    $ps = array_unique($ps);
    // 推荐产品没有必要存储到文件
    $key = $this->getCacheKey("user_recommender_products");
    Cache::forever("$key.$uid", $ps);
    return $ps;
}

artisan 命令

以下 artisan 命令类,显示了训练的步骤:

<?php

namespace App\Console\Commands;

use Illuminate\Console\Command;
use App\Tools\RecommenderSystem as RS;
use Cache;

class RecommenderSystem extends Command
{
    protected $signature = 'resys:train {--D|datadir= : where to save data, default is cache} {--K|chunk=1 : number of users chunk} {--U|vu=10 : number of voter} {--N|vn=10 : number of votes}';

    protected $description = 'recommender system';

    public function __construct()
    {
    parent::__construct();
    }

    public function handle() : void
    {
    $k= intval($this->option("chunk"));
    $vu = intval($this->option("vu"));
    $vn = intval($this->option("vn"));
    $dir = $this->hasOption("datadir") ? $this->option("datadir") : null;
    $rs = new RS($k, $dir);
    // 1. 得到用户评分矩阵, O(n^2)
    $this->info("1. Compute user rating:");
    foreach ($rs->getRatingVectors() as $rv) {
        $bar1 = $bar1 ?? $this->output->createProgressBar($rv[1]);
        $bar1->setProgress($rv[0]);
    }
    $bar1->finish();
    $this->line("");

    // 2. 计算用户相似度矩阵, O(n^3)
    $this->info("2. Compute user similarity:");
    $bar2 = $this->output->createProgressBar($k);
    foreach ($rs->getSimilarityMatrix() as $sm) {
        $bar2->setProgress($sm[0]);
    }
    $bar2->finish();
    $this->line("");

    // 3. 投票决定为每一个用户推荐的产品, O(n)
    $this->info("3. vote:");
    $users = $rs->getMap()["users"];
    $bar3 = $this->output->createProgressBar(count($users));
    foreach ($users as $id) {
        $rs->vote($id, $vu, $vn);
        $bar3->advance();
    }
    $bar3->finish();
    $this->line("");

    // 4. 清除中间数据
    $this->info("4. clear cache:");
    foreach ($rs->clearCache() as $arr) {
        $bar4 = $bar4 ?? $this->output->createProgressBar($arr[1]);
        $bar4->setProgress($arr[0]);
    }
    $this->info("\nTrain done");

    }
}

执行效果如下:

xl@xl:~/apps/blog$ ll storage/rsdata/
total 8
drwxrwxr-x 2 xl xl 4096 Nov 17 13:28 ./
drwxr-xr-x 6 xl xl 4096 Nov 15 16:02 ../
xl@xl:~/apps/blog$ redis-cli 
127.0.0.1:6379> SELECT 1
OK
127.0.0.1:6379[1]> FLUSHALL
OK
127.0.0.1:6379[1]> exit
xl@xl:~/apps/blog$ time ./artisan resys:train -D storage/rsdata/ -K 4 -U 5 -N 5
1. Compute user rating:
 2099/2099 [▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓] 100%
2. Compute user similarity:
 4/4 [▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓] 100%
3. vote:
 2099/2099 [▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓] 100%
4. clear cache:
 4/4 [▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓] 100%
Train done

real    0m42.890s
user    0m23.208s
sys 0m2.285s
xl@xl:~/apps/blog$ ls -lh storage/rsdata/
total 668K
-rw-rw-r-- 1 xl xl  35K Nov 17 13:30 rs.map.json
-rw-rw-r-- 1 xl xl 632K Nov 17 13:30 rs.user_rating.csv
xl@xl:~/apps/blog$ redis-cli 
127.0.0.1:6379> SELECT 1
OK
127.0.0.1:6379[1]> KEYS *
   1) "laravel_cache:rs.user_recommender_products.705"
   2) "laravel_cache:rs.user_recommender_products.2957"
   3) "laravel_cache:rs.user_recommender_products.1697"
   4) "laravel_cache:rs.user_recommender_products.1625"
   5) "laravel_cache:rs.user_recommender_products.2844"
   6) "laravel_cache:rs.user_recommender_products.637"
   7) "laravel_cache:rs.user_recommender_products.1275"
   8) "laravel_cache:rs.user_recommender_products.2049"

127.0.0.1:6379[1]> get laravel_cache:rs.user_recommender_products.1060
"a:3:{i:0;i:9;i:1;i:1;i:2;i:10;}"

训练完成后,缓存中以 xxx.$user_id 保存着推荐产品 id 组成的数组。

更多

尚待优化

  1. 未实现冷启动,就是说,不存在交互行为的用户不会产生推荐值,不存在交互的产品不会被推荐;
  2. 总认为调用者的参数是合理的,不会对其做判断;
  3. 总认为文件系统是稳定可靠的,读写文件不做检测;
  4. 构造评分矩阵的过程中,一次只读一个用户的历史行为,数据库查询次数可能很多;
  5. 推荐产品的数量并不保证下限,因为实际中评分矩阵往往是非常稀疏的,过小的参数可能会导致推荐产品数量非常少;

svd 与相似度矩阵

因为求相似度矩阵,其实就是求矩阵 BB' ,自然考虑使用 svd , [u, s, v] = svd(A) , u 就是 AA' 的特征矩阵, 而 u 本身是规范正交的 , 使用 svd 可以省去单位化的步骤, 这么做的问题在于丢掉了产品 id 和索引之间的映射,尚未想到如何解决。

代码下载

  1. src/app/Tools/RecommenderSystem.php , 训练类
  2. src/app/Console/Commands/RecommenderSystem.php , artisan 命令类

下载地址

本作品采用《CC 协议》,转载必须注明作者和本文链接
本帖由系统于 5年前 自动加精
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 11
nff93

真的是不明觉厉了,看到一半发现自己看不懂。。。 :joy:

5年前 评论
coldwinters

@nff93 你也好厉害,看到一半才看不懂,我一开始就看不懂了!

5年前 评论

@nff93 应该是我把这个事搞得太复杂了,核心的就第一段和这2句代码:

# 按行单位化
B = normalize(A, norm='l2', axis=1)
# 求协方差
C = B @ B.transpose()

剩下的都是数据读写操作。

5年前 评论

厉害,持续关注这块的内容。

5年前 评论
sssword

打初中开始,数学就没过30分,我是不是有点为难我自己了。:-(

5年前 评论

@OneLight 我看都没看就知道不会懂了

5年前 评论

楼主拿laravel举个更易懂的实际例子

5年前 评论

协同过滤推荐(Collaborative Filtering Recommendation)技术是推荐系统中应用最早和最为成功的技术之一。它一般采用最近邻技术,利用用户的历史喜好信息计算用户之间的距离,然后 利用目标用户的最近邻居用户对商品评价的加权评价值来预测目标用户对特定商品的喜好程度,系统从而根据这一喜好程度来对目标用户进行推荐。协同过滤最大优 点是对推荐对象没有特殊的要求,能处理非结构化的复杂对象,如音乐、电影。

协同过滤是基于这样的假设:为一用户找到他真正感兴趣的内容的好方法是首先找到与此用户有相似兴趣的其他用户,然后将他们感兴趣的内容推荐给此用户。其基 本思想非常易于理解,在日常生活中,我们往往会利用好朋友的推荐来进行一些选择。协同过滤正是把这一思想运用到电子商务推荐系统中来,基于其他用户对某一 内容的评价来向目标用户进行推荐。

5年前 评论

太棒了,最近项目正需要个小型的推荐系统,正考虑怎么设计呢,楼主给了很大的启发,谢谢!@Tresdin ,最近有更新吗?

4年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!