1.基于用户的协同过滤算法

• 仅仅基于用户行为数据设计的推荐算法一般称为协同过滤算法。学术界对协同过滤算法 进行了深入研究，提出了很多方法，比如基于邻域的方法（neighborhood-based）、隐语义模型（latent factor model）、基于图的随机游走算法（random walk on graph）等。

• 基于邻域的算法是推荐系统中最基本的算法，该算法不仅在学术界得到了深入研究，而且在 业界得到了广泛应用。基于邻域的算法分为两大类，一类是基于用户的协同过滤算法，另一类是 基于物品的协同过滤算法。

• 基于用户的协同过滤算法是推荐系统中最古老的算法，这个算法是1992年提出的，是用在了邮件过滤系统中，后面被用到了新闻过滤系统中。

• 简单的来说，在一个在线个性化推荐系统中，基于用户的协同过滤就是，当一个用户A需要个性化推荐 时，可以先找到和他有相似兴趣的其他用户，然后把那些用户喜欢的、而用户A没有听说过的物品推荐给A。这种方法称为基于用户的协同过滤算法。

• 协同过滤算法主要利用行为的相似度 计算兴趣的相似度。余弦相似度是一种计算方法。

2.余弦相似度原理

• 用向量空间中的两个向量夹角的余弦值作为衡量两个个体间差异大小的度量，值越接近1，就说明夹角角度越接近0°，也就是两个向量越相似，就叫做余弦相似.衡量的是两个变量在各个方向(属性)上的比例的相似度。

3.余弦相似度公式

• 给定用户u和用户v，令N(u)表示用户u曾经有过正反馈的物品集合，令N(v) 为用户v曾经有过正反馈的物品集合。

• 《推荐系统实践》书中的计算公式：

$$W_{uv}=\frac{|N(u)\cap N(v)|}{\sqrt{|N(u)|\ast |N(v)|}}$$

4.推导公式的过程

4.1 二维变量余弦相似度的计算：

• 如图$\vec{a}=(x_a,y_a)$、$\vec{b}=(x_b,y_b)$，夹角为$\theta$，图中c是一条辅助线：

• 上述a、b、c边的长度分别为：
  $$\{\begin{array}{l}a=\sqrt{x_a^2+y_a^2}\\ b=\sqrt{x_b^2+y_b^2}\\ c=\sqrt{(x_a-x_b{)}^2+(y_a-y_b{)}^2}\end{array}$$

• 根据余弦定理有:
  $$\begin{array}{rl}cos\theta & =\frac{\vec{a}\cdot \vec{b}}{|\vec{a}|\ast |\vec{b}|}\\ & \\ cos\theta & =\frac{a^2+b^2-c^2}{2\ast a\ast b}\\ & =\frac{(x_a^2+y_a^2)+(x_b^2+y_b^2)-((x_a-x_b{)}^2+(y_a-y_b{)}^2)}{2\ast \sqrt{x_a^2+y_a^2}\ast \sqrt{x_b^2+y_b^2}}\\ & =\frac{x_a\ast x_b+y_a\ast y_b}{\sqrt{x_a^2+y_a^2}\ast \sqrt{x_b^2+y_b^2}}\\ & =\frac{\vec{a}\cdot \vec{b}}{|\vec{a}|\ast |\vec{b}|}\end{array}$$

4.2 $n$维变量余弦相似度的计算：

$$\begin{array}{rl}\vec{x}& =(x_1,x_2,x_3,...,x_n)\\ \vec{y}& =(y_1,y_2,y_3,...,y_n)\\ cos\theta & =\frac{\vec{x}\cdot \vec{y}}{|\vec{x}|\ast |\vec{y}|}\\ & =\frac{x_1\ast y_1+x_2\ast y_2+\cdot \cdot \cdot +x_n\ast y_n}{\sqrt{x_1^2+x_2^2+\cdot \cdot \cdot +x_n^2}\ast \sqrt{y_1^2+y_2^2+\cdot \cdot \cdot +y_n^2}}\end{array}$$

5.应用实例

• 在《推荐系统实践》书中的描述，A用户对a、b、d物品有兴趣，B用户对a、c物品有兴趣，C用户对b、e物品有兴趣，D用户对c、d、e物品有兴趣，可把上述关系转化为A、B、C、D向量在各个方向上的长度:

• 代入公式计算得出A、B之间的余弦相似度，计算过程如下所示：
  $$\begin{array}{rl}\vec{A}& =(1,1,0,1,0)\\ \vec{B}& =(1,0,1,0,0)\\ \vec{C}& =(0,1,0,0,1)\\ \vec{D}& =(0,0,1,1,1)\\ cos<\vec{A},\vec{B}>& =\frac{\vec{A}\cdot \vec{B}}{|\vec{A}|\ast |\vec{B}|}\\ & =\frac{1\ast 1+1\ast 0+0\ast 1+1\ast 0+0\ast 0}{\sqrt{1^2+1^2+0^2+1^2+0^2}\ast \sqrt{1^2+0^2+1^2+0^2+0^2}}\\ & =\frac{1}{\sqrt{6}}\end{array}$$
• 此处因为每个用户对于某物品是否有兴趣，是用0，1来衡量。当类似于这种用0，1来衡量属性值的时候，余弦相似度公式可做等价变换。假设用户A和用户B，令N(A)表示用户A曾经有过正反馈的物品集合，令N(B) 为用户B曾经有过正反馈的物品集合。则用户A和用户B的兴趣相似度为：
  A={a,b,d}B={a,c}WAB=∣N(A)∩N(B)∣∣N(A)∣∗∣N(B)∣=∣{a,b,d}∩{a,c}∣∣{a,b,d}∣∗∣{a,c}∣=∣{a}∣3∗2=16 \begin{aligned}A&=\{a,b,d\}\\B&=\{a,c\}\\W_{AB}&=\frac{|N(A)\cap N(B)|}{\sqrt{|N(A)|* |N(B)|}}\\&=\frac{|\{a,b,d\}\cap\{a,c\}|}{\sqrt{|\{a,b,d\}|*|\{a,c\}|}}\\&=\frac{|\{a\}|}{\sqrt{3*2}}\\&=\frac{1}{\sqrt{6}}\end{aligned} ABWAB​​={a,b,d}={a,c}=∣N(A)∣∗∣N(B)∣ ​∣N(A)∩N(B)∣​=∣{a,b,d}∣∗∣{a,c}∣ ​∣{a,b,d}∩{a,c}∣​=3∗2 ​∣{a}∣​=6 ​1​​