领域算法进阶

* 领域算法的缺点

  • 受限覆盖：假设受限：由于计算两个用户间的相似性是基于他们对相同物品的评分，而且只有对相同物品做了评分的用户可以作为领域；（例如：很多用户有很少或者没有共同评分过的物品但依然有相似的爱好，而仅仅被领域评价过的物品会被推荐）

  • 稀疏数据： 只是使用了部分数据

* 默认解决

  • 填充数据
  • 填充数据导致推荐的偏差

1. 降维算法

  • 将用户或者物品映射到隐变量空间获取它们之间的最突出特征
  • 降维后，用户和物品之间的关系是在高级特征的密集子空间，而不是之前的评分空间

* 分解方法

  • 评分矩阵分解
  • 相似度矩阵分解

2. 基于图的方法

  • 基于图的方法：数据用图的形式表示出来，图中用户，物品或者两者都可以用点的形式表示，边表示用户和物品之间的交互或者相似性

上图：用户u到物品i的边，表示用户u对物品i进行了评分。给予边权值，表示u对i的评分 @@@a random-walk based scoring algorithm for recommender engines @@@ applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering

* 两种推荐方法

1. 图中的用户u对物品i的相近距离直接用于推荐。找用户u在图中的最近物品

@@@random-walk computation of similarities between nodes of a graph with application to collaborative recommendation @@@a random-walk based scoring algorithm for recommender engines @@@ applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering

2. 将用户间或者物品间的相似距离看成他们之间的相似度权重$w{uv}$或者$w{ij}$,然后使用邻域的方法

@@@random-walk computation of similarities between noedes with application to collaborative recommendation @@@ a collabotive filtering framework based on both local user similarity and global user similarity

2. 基于路径的相似度

最短路径

@@@Horing hatches an egg: A new graph-theoretic approach to collaborative filtering

  • 通过用户结点最短距离来计算他们之间相似度的推荐方法

路径数量

@@@ applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering

  • 计算路径数量来估测连通度

3. 随机游走模型

概率框架

itemrank

@@@a random-walk based scoring algorithm for recommender engines

4. 平均首次通过/往返次数

  • 针对随机游走的测量距离

@@@random-walk computation of similarities between noedes with application to collaborative recommendation

@@@An Emperimental investigation of graph kernels on a collaborative recommendation task.

5. pagerank

1 基本模型

*随机游走模型

  • 针对浏览网页的用户行为建立的抽象模型
  • 直接跳转：打开浏览器，输入网址，然后根据链接跳转

* 转移概率矩阵

可以组织这样一个N维矩阵：其中i行j列的值表示用户从页面j转到页面i的概率

$$M= \left[ \begin{matrix} 0 & 1/2 & 0 & 1/2 & [AA,BA,CA,DA]\ 1/3 & 0 & 0 & 1/2 & [AB,BB,CB,DB]\ 1/3 & 1/2 & 0 & 0 & [AC,BC,CC,DC]\ 1/3 & 0 & 1 & 0 & [AD,BD,CD,DD] \end{matrix} \right]

$$

* 远程跳转：以1/4的概括进入任意页面(rank值)

$$v= \left[ \begin{matrix} 1/4\ 1/4\ 1/4\ 1/4\ \end{matrix} \right]

$$

  • M的第一行是各页面到A页面的概率
  • v的列是ABCD当前的rank值
  • Mv是ABCD的新的rank

$$Mv= \left[ \begin{matrix} 1/4\ 5/24\ 5/24\ 1/3\ \end{matrix} \right]

$$

* 计算

然后用M再乘以这个新的rank向量，又会产生一个更新的rank向量。迭代这个过程，可以证明v最终会收敛，即v约等于Mv，此时计算停止。最终的v就是各个页面的pagerank值。例如上面的向量经过几步迭代后，大约收敛在（1/4, 1/4, 1/5, 1/4），这就是A、B、C、D最后的pagerank。

* pagerank

http://blog.jobbole.com/71431/ http://blog.codinglabs.org/articles/intro-to-pagerank.html http://ibillxia.github.io/blog/2012/07/08/Google-PageRank-Algorithm/

  • 数量假说：在web图模型中，如果一个页面节点接收到其他网页指向的入链数量越多，那么这个页面越重要
  • 质量假说：指向A的入链质量不同，质量高的页面会通过链接转向其他页面传递更高的权重。所以越是质量高的页面指向A，A越重要

* pagerank的计算

  • $$M^iv$$
  • 本质是马尔科夫过程，如果收敛需要满足：图是强连通的，即从任意网页可以到达其他任意网页；

* pagerank的问题

  • 避免终止点 互联网上的网页不满足强连通的特性，因为有一些网页不指向任何网页，如果按照上面的计算，上网者到达这样的网页后便走投无路、四顾茫然，导致前面累计得到的转移概率被清零，这样下去，最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉，C变成了一个终止点
  • 避免陷阱问题 即有些网页不存在指向其他网页的链接，但存在指向自己的链接。

* 抽税的做法

  • 原来的公式： $$v^{'}=M*v$$

  • 较小概率的随机跳转到一个随机的网页 一是以概率（1-$$\beta$$）随机访问任何一个页面( 遇到上述0的情况，人为的跳出)，二是以概率（$$\beta$$）访问 页面i中的某个链接。

$$v^{'}=\beta Mv+(1-\beta)e/n$$

$$\beta$$取值（0.8~0.9）一般常取值0.85

e为N维单位向量，加入e的原因是这个公式的前半部分是向量，e是维度是n，数值是1的列向量

$$e= \left[ \begin{matrix} 1/n\ 1/n\ 1/n\ 1/n\ \end{matrix} \right]

$$

n是web图所有节点的数目 这样，整个计算就变得平滑，因为每次迭代的结果除了依赖转移矩阵外，还依赖一个小概率的心灵转移。

* 面向主题的pagerank

6 基于路径相似度

  • 图中两个节点的距离，通过计算，用于连接两个节点的路径的数目和这些路径的长度所构成的函数来获得。

* 最短路径的方法

@@@Horting Hatchers an Egg:A new graph-theoretic approach o coll

计算用户u到其他用户v的最短路。 最短路径的计算：用户A，horts，用户B（A，B对相同的物品评过分） 满足一个可预测性的关系，就是吧将用户u和用户v的评分尺度，做映射 最后，计算u到其他队物品j评分过的用户的路径上。计算路径 同时将路径转换为刻度表示（0~13）

* 路径数量

  • 通过路径数量计算连通性
  • 将物品的路径数表示为2部图
  • 那么标准的cf方法，k=3
  • 可以设置M的数值
  • 计算用户-物品关联矩阵（$$\alpha 是为了衰减较长距离的贡献度 \in [0,1]$$ ,取0.5 ）

$$sk=\sum{k=1}^M \alpha^kA^k=(I-\alpha A)^{-1} (\alpha A-\alpha^k A^k)$$

=>

* 快速计算

  • 无限制的扩散激活方法
    1. 激活c1，传递给，（p2,p3）
    2. 激活(p2,p3) 传递给(c2)
    3. 激活c2，传递给p3
    4. 激活p3，传递给c1
    5. 激活c1，传递给p1

* 无约束 扩散激活理论

  • 源于人类的记忆
  • 三个过程：预调节，传播，调节后的处理(1,3可选)

$Ij = \sum_i O_i w{ij}$ $ij$ 是节点 $j$ 的输出 $O_i$ 是和节点$j$ 有连接的，节点$i$ 的输出 $w{ij}$是权重

  • 计算激活水平(f是激活函数-阈值函数)

$A_j = f(I_j) $ （1） $I_iI_j$ $A_j$=1

* 加以约束的传播扩散理论

  • 距离约束
  • 遇到扇形的节点(节点的出度非常大)
  • 沿着确定的权重方向
  • 阈值激活

* 迭代计算矩阵

  • 根据传播算法 和 约束 迭代计算矩阵

results matching ""

    No results matching ""