沈阳网站建设服务器,icp备案系统,上海明鹏建设集团有限公司网站,飞沐网站设计在基于物品的协通过滤算法中#xff0c;当用户历史行为数据有很多时#xff0c;对计算会有很大挑战#xff0c;对此可以使用剪枝对数据进行化简来达到减少计算量。 不是每个物品对都需要进行增量计算。对于两个物品的相似度#xff0c;每次更新都能够得到一个新的相… 在基于物品的协通过滤算法中当用户历史行为数据有很多时对计算会有很大挑战对此可以使用剪枝对数据进行化简来达到减少计算量。 不是每个物品对都需要进行增量计算。对于两个物品的相似度每次更新都能够得到一个新的相似度这个新的相似度可以看做是一个随机变量那么这个随机变量就有一个期望值。一旦物品之间的相似度可以以较高的置信度确认它已经在期望值附近小幅度波动就没必要再去更新了。如果进一步确定是一个比较小的相似度甚至可以之间去掉这个物品对其相似度不再参与计算更新。 对于确定这个物品什么时候不用再更新就可以用到Hoeffding不等式。Hoeffding不等式又称为霍夫丁不等式。该不等式给出了随机变量的和与其期望值偏差的概率上限。 x^1n(x1....xn)\hat{x} \frac{1}{n}(x_1....x_n) x^n1(x1....xn) p(x^−E[x^≥ϵ])≤e−2nϵ2p(\hat{x}-E[\hat{x}\geq\epsilon])\leq e^{-2n\epsilon^2} p(x^−E[x^≥ϵ])≤e−2nϵ2 不等式中x^\hat{x}x^是随机变量X的n个样本的均值E[x^]E[\hat{x}]E[x^]是随机变量X的期望值。Hoeffding不等式反应的是随机变量的真实期望值不会超过x^ϵ\hat{x}\epsilonx^ϵ的概率是1−δ1-\delta1−δ其中ϵ\epsilonϵ就是与真实相似度的误差ϵ\epsilonϵ、δ\deltaδ及n之间的关系是 ϵln(1δ)2n\epsilon \sqrt{\frac{ln(\frac{1}{\delta})}{2n}} ϵ2nln(δ1) Hoeffding不等式适用于有界的随机变量。x^\hat{x}x^在实时推荐系统中就是历次更新得到的相似度平均值公式中的n是相似度的更新次数。这样一来选定了δ\deltaδ和ϵ\epsilonϵ之后就可以知道多少次后就能够逼近相似度期望值。假设δ0.05\delta0.05δ0.05。 那么有
与真实相似度误差最少更新次数0.11500.056000.0114979有了上面的表那么在一个物品对的更新次数已经达到最少更新次数时且满足相似度误差时就可以不用再更新了。
参考推荐系统: 关键模块 陈开江
