基于物品的协同过滤

fyh 2022年03月09日 48次浏览

基于物品的协同过滤

题目完成情况向量：

对于一道题目完成了为0，这样就不会出现在前k大里，不会推荐该题目，未完成为1。

题目相似矩阵：

题目相似矩阵采用基于余弦的相似度计算，构造一道题目的向量$i$为每个用户对该道题的时间权重和难度权重的相关占比和。计算两个向量的相似度可用余弦公式计算：
$$
sim(i,j) = cos(i,j) = \frac{i * j}{|i|*|j|}= \frac{\sum_(x_i \cdot y_i)}{\sqrt{\sum_x_i2} \cdot \sqrt{\sum_y_i^2}}
$$
可以计算出任意$(i,j)$的相似度，从而得到相似矩阵。

假设用户数为$n$，题目数为$m$，得到该矩阵是时间复杂度为$O(nm^2)$

推荐列表

推荐列表 = 题目完成情况向量 * 题目相似矩阵

矩阵乘法$O(m^2)$计算出推荐列表，已完成题目用题目完成情况向量筛去，对于指定用户选取推荐列表中前k大值进行推荐。

时间效率

假设每个用户选择25道题，有$n$个用户，那么最坏情况下有$25n$道题目，即$m=25n$，假设计算上限$107$次，$n \cdot (25n)2 \le 10^7$，即$n \le 25$，那么就选取最近有过AC记录的25位用户，每位用户选最近AC的25道题进行计算。

将协同过滤应用于userinfo.php中的Recommend

将需要推荐的题目放在/OJ/userinfo.php里的$hznu_recommend_set变量中，该变量是一个array

大致的步骤为：

  • 查询最近有提交记录的25个不同的用户（包括当前用户在内）
  • 查询每个用户最近AC的25道不同的题目
  • 对当前用户建立题目完成情况01行向量
  • 对每道题目按时间权重$10 / log(n+1)$,计算权值,构造向量（倒数第n次正确提交，若没有提交则n为100）
  • $O(m^2)$枚举题目，计算余弦值得到相似矩阵
  • 题目完成情况行向量和相似矩阵相乘得到推荐列表

1.查询最近有提交记录的25个不同的用户

CREATE index `idx_solution_judgetime` ON solution(judgetime); -- 添加BTREE索引
SELECT DISTINCT `user_id` FROM `solution` WHERE `result` = 4 ORDER BY `judgetime` DESC LIMIT 25;

2.查询每个用户最近AC的25道不同的题目

SELECT DISTINCT `problem_id` FROM `solution` WHERE `user_id` = '$tmp_user_id' AND `result` = 4 ORDER BY `judgetime` LIMIT 25

3.对当前用户建立题目完成情况01行向量

SELECT count(*) FROM solution WHERE problem_id=$recommand_problems[$i] AND result = 4 AND user_id = '$user'

$solved_vector[$i] = 1;
if (intval($mysqli->query($sql_accepted)->fetch_array()[0]) > 0) $solved_vector[$i] = 0;

这样完成了记为0，未完成记为1，最后将该向量和推荐列表的每一项相乘就可筛去已经AC的题目。

4.对每道题目构造向量

构造方法为$10 / log(n+1)$（只考虑时间权重，还需要调整）,存在一个二维数组中可以方便构造

$problems_vector = array();
$problems_vector[$row_problems['problem_id']][$users_cnt] = 10.0 / log($j + 2);

其中前一维代表题目，后一维代表用户，值代表该用户对该道题的权值。

5.计算相似矩阵

枚举$(i,j)$后用公式计算余弦值即可。

6.得到推荐列表

矩阵乘法，将已AC题目筛去。使用php的arsort函数按值排序（键会跟着变），可以很方便的得到topk个结果。

相关代码

/* 基于物品的协同过滤推荐算法 */
$sql_users = "SELECT DISTINCT `user_id` FROM `solution` WHERE `result` = 4 ORDER BY `judgetime` DESC LIMIT 25";
$result_users = $mysqli->query($sql_users);
$recommend_vis = array();
$problems_vector = array(); // 每道题的向量
$users_cnt = 0;
$user_hasvis = 0;
for ($i = 0; $row_users=$result_users->fetch_array(); ++$i) {
    $tmp_user_id = $row_users['user_id'];
    $sql_problems = "SELECT DISTINCT `problem_id` FROM `solution` WHERE `user_id` = '$tmp_user_id' AND `result` = 4 ORDER BY `judgetime` DESC LIMIT 25";
    $result_problems = $mysqli->query($sql_problems);
    for ($j = 0; $row_problems=$result_problems->fetch_array(); ++$j) {
        if ($row_problems['problem_id']) {
            $recommend_vis[$row_problems['problem_id']] = 1;
            $problems_vector[$row_problems['problem_id']][$users_cnt] = 10.0 / log($j + 2); // 以时间作为权重
        }
    }
    if ($user == $tmp_user_id) $user_hasvis = 1;
    $users_cnt++;
}
if ($user_hasvis == 0) {
    $sql_problems = "SELECT DISTINCT `problem_id` FROM `solution` WHERE `user_id` = '$user' AND `result` = 4 ORDER BY `judgetime` DESC LIMIT 25";
    $result_problems = $mysqli->query($sql_problems);
    for ($j = 0; $row_problems=$result_problems->fetch_array(); ++$j) {
        if ($row_problems['problem_id']) {
            $recommend_vis[$row_problems['problem_id']] = 1;
            $problems_vector[$row_problems['problem_id']][$users_cnt] = 10.0 / log($j + 2);
        }
    }
    $users_cnt++;
}
$recommand_problems = array_keys($recommend_vis);
$problem_cnt = count($recommand_problems);
$solved_vector = array(); // 题目完成情况向量
for ($i = 0; $i < $problem_cnt; ++$i) {
    $solved_vector[$i] = 1;
    $sql_accepted = "SELECT count(*) FROM solution WHERE problem_id=$recommand_problems[$i] AND result = 4 AND user_id = '$user'";
    if (intval($mysqli->query($sql_accepted)->fetch_array()[0]) > 0) $solved_vector[$i] = 0;
}
$sim_matrix = array(); // 题目相似矩阵
for ($i = 0; $i < $problem_cnt; ++$i) {
    for ($j = $i; $j < $problem_cnt; ++$j) {
        if ($i == $j) $sim_matrix[$i][$j] = 1.0; 
        else {
            $fz = 0.0;
            $fmx = 0.0;
            $fmy = 0.0;
            for ($k = 0; $k < $users_cnt; ++$k) {
                $xi = $problems_vector[$recommand_problems[$i]][$k];
                $yi = $problems_vector[$recommand_problems[$j]][$k];
                $fz += $xi * $yi;
                $fmx += $xi * $xi;
                $fmy += $yi * $yi;
            }
            $fm = sqrt($fmx) + sqrt($fmy);
            $ret = $fz / $fm; // 两个向量的余弦值用于判断相似度
            $sim_matrix[$i][$j] = $ret;
            $sim_matrix[$j][$i] = $ret;
        }
    }
}
$recommend_list = array(); // 推荐列表
for ($i = 0; $i < $problem_cnt; ++$i) {
    $recommend_list[$i] = 0.0;
    for ($j = 0; $j < $problem_cnt; ++$j)
        $recommend_list[$i] += $solved_vector[$j] * $sim_matrix[$j][$i];
}
for ($i = 0; $i < $problem_cnt; $i++) $recommend_list[$i] = $recommend_list[$i] * $solved_vector[$i];
arsort($recommend_list);
$recommend_list_key = array_keys($recommend_list);
$topk = 10; // 推荐权值最大的k道题目
$recommend_cnt = 0;
for ($i = 0; $i < $problem_cnt && $recommend_cnt < $topk; ++$i) {
    if ($recommend_list[$recommend_list_key[$i]] > 0)
        $hznu_recommend_set[$recommend_cnt++] = $recommand_problems[$recommend_list_key[$i]];
    else break;
}
上一篇： sqlite3简单管理