UVA12420 Item-Based Recommendation

本题中你需要搭一个简单的评价系统。有 $n$ 个用户，每个评价 $m$ 部电影。 例如，对于 $n=7,m=6$，评价在下列的表中呈现： ||$\mathbf{M1}$|$\mathbf{M2}$|$\mathbf{M3}$|$\mathbf{M4}$|$\mathbf{M5}$|$\mathbf{M6}$| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$\mathbf{U1}$|$2.5$|$3.5$|$3.0$|$3.5$|$2.5$|$3.0$| |$\mathbf{U2}$|$3.0$|$3.5$|$1.5$|$5.0$|$3.5$|$3.0$| |$\mathbf{U3}$|$2.5$|$3.0$| |$3.5$| |$4.0$| |$\mathbf{U4}$| |$3.5$|$3.0$|$4.0$|$2.5$|$4.5$| |$\mathbf{U5}$|$3.0$|$4.5$|$2.0$|$3.0$|$2.0$|$3.0$| |$\mathbf{U6}$|$3.0$|$4.5$| |$5.0$|$3.5$|$3.0$| |$\mathbf{U7}$| |$4.5$| |$4.0$|$1.0$| | 我们当然可以看到，$7$ 号用户没看的 $3$ 部电影分别是 $\mathbf{M1},\mathbf{M3}$ 和 $\mathbf{M6}$。 **问题是，** 我们该给他推荐哪一部？ 最好的算法中之一称作“协同过滤”。例如，我们可以 1. 寻找和要被推荐对象对某部电影给出相同分数的人。 2. 使用和被推荐对象思想相似的人的推荐计算出被推荐对象被推荐的电影。 这叫做“基于用户的协同过滤算法”。或者，我们可以使用 Amazon.com 发明的“基于项目的协同过滤算法”。它的步骤如下： 1. 搭建一个项目对项目的矩阵，描述其之间的关系； 2. 使用矩阵以及他的数据来推荐。 这是我们所使用的。 ### 搭建矩阵 相似性矩阵包含 $m$ 行 $m$ 列。第 $i$ 行第 $j$ 列的元素 $S(i,j)$ 是电影 $\mathbf Mi$ 和 $\mathbf Mj$ 的相似性程度。为了计算 $S(i,j)$，我们首先计算每位用户的“评价差异”，即将每位评价过电影 $i,j$ 的用户的评分之差的平方加起来，得到数 $x$，那么 $S(i,j)=(1+x)^{-1}$。 例如，为计算 $S(2,3)$，我们首先计算评价差异：$|3.5-3.0|=0.5,|3.5-1.5|=2.0,|3.5-3.0|=0.5,|4.0-2.0|=2.0$，于是我们愉快地计算出 $x=0.5^2+2.0^2+0.5^2+2.0^2=8.5$，所以 $S(2,3)=(1+8.5)^{-1}\approx 0.105$。 例子中完整的相似矩阵计算如下（由于其是对称的，所以我们略去了部分元素）： ||$\mathbf{M1}$|$\mathbf{M2}$|$\mathbf{M3}$|$\mathbf{M4}$|$\mathbf{M5}$|$\mathbf{M6}$| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$\mathbf{M1}$|$1.000$|$0.222$|$0.222$|$0.091$|$0.400$|$0.286$| |$\mathbf{M2}$| |$1.000$|$0.105$|$0.167$|$0.051$|$0.182$| |$\mathbf{M3}$| | |$1.000$|$0.065$|$0.182$|$0.154$| |$\mathbf{M4}$| | | |$1.000$|$0.053$|$0.103$| |$\mathbf{M5}$| | | | |$1.000$|$0.148$| |$\mathbf{M6}$| | | | | |$1.000$| ### 做出推荐 一旦我们计算出 $S$ 矩阵，做出推荐就很容易了。假设我们想要为用户 $\mathbf Uq$ 做出推荐，那么对他没看过电影的评分是他看过电影评分的加权平均。 形式化的，设 $\mathbf Uq$ 已经看了 $k$ 部电影 $\mathbf Mm_1,\mathbf Mm_2,\cdots,\mathbf Mm_k$，则一部没看过的电影 $i$ 的评分等于（$R(x)$ 代表 $\mathbf Uq$ 对电影 $\mathbf Mx$ 的评价）： $$\left.\sum_{j=1}^kS(i,m_j)R(m_j)\right/\sum_{j=1}^kS(i,m_j)$$ 例如，$\mathbf{U7}$ 对于电影 $\mathbf{M6}$ 的评分是 $$\frac{4.5S(6,2)+4.0S(6,4)+1.0S(6,5)}{S(6,2)+S(6,4)+S(6,5)}\approx 3.183$$ 事实上，这个分数比 $\mathbf {M1}$ 和 $\mathbf {M3}$ 的高，所以我们将 $\mathbf {M7}$ 推荐给 $\mathbf{U6}$。 注意在上式中，如果分母是 $0$，即 $i$ 与其余所有电影都不相似，我们则不会给他推荐这部电影。

只有一组数据（在 UVa 中太罕见了）。首行三个整数 $n,m,c(1\le n\le 50,1\le m\le 200,1\le c\le nm)$。下面 $c$ 行每行包含两个整数 $i,j(1\le i\le n,1\le j\le m)$ 和一个实数 $r\in[0,5]$，代表用户 $\mathbf Ui$ 对电影 $\mathbf Mj$ 的评分是 $r$。没有人会两次评分同一电影。而后是数行，每行包含一个整数 $q$，意味着我们要把至多 $10$ 部电影推荐给他。每个用户至少有一部没看过的电影并与他看过的电影相似。

对于每个 $q$，输出至多 $10$ 部被推荐的电影：电影编号，评分（保留 $3$ 位小数），按照评分下降排序。数据保证最终的输出不会因为浮点误差而改变。如果没看过的电影少于 $10$ 部，则全部输出（排序还是要排的）。格式请参照样例。