文档章节

求TopK的Fagin’s Algorithm和Threshold Algortihm

Vegetable
 Vegetable
发布于 2017/07/25 13:35
字数 1029
阅读 34
收藏 0

Fagin算法和Threshold算法都是Top-K排序领域的经典算法(K代表只要对前K个值排序值),不同于传统Top-k对一维数组前K个值排序,Fargin和Threshhold算法适用于参考多个排序指标时对前k个物品排序。

举例 

你想买个手机,问了两个对电子产品比较在行的朋友,朋友1给出了这份推荐列表:

而朋友2却给了这份推荐列表:

假如你对两个朋友都同样信任,你该听谁的建议呢?


暴力法--平均两个列表的推荐指数(全计算再求TopK)


根据原来两个推荐列表每项的推荐指数,重新生成一个列表,新列表的每项参考原来列表的值来重新计算;譬如:
V(iphone 5s)=(V1(iphone 5s)+V2(iphone 5s))/2=(10+7)/2=8.5
V(小米3)=(V1(小米3)+V2(小米3))/2=(9+9)/2=9
...............
然后每个型号来比较,这种方法简单暴力,感觉上不高效,因为你只要买一个手机,却要把每个手机权重都计算出来;感觉上只要每个列表比较前面几个就够了,但具体要比较几个呢?却又说不清,这时候就该的Fagin和Threshold算法出马了!

Fagin算法


1.两个列表都选择各自的第一行的项,生成新列表,推荐指数1和推荐指数2各取第一行的iPhone5s和小米3


2.两个列表再取第二行的每项,放到新列表中,取得推荐指数1的小米3和推荐指数2Find7

3.两个列表再取第三行的每项,放到新列表中
........
(直到新列表有一项的值在原先两个推荐指数列表都取到过;可以看到其实第二步就可以停了,因为新列表的小米3的两个值都取到了)
4.补全每项在其他列表中的值

5.就从已获取项里找最推荐的手机,列表其他值没必要看了

所以小米3是最值得入手的!

  • 疑问1:这里总共只取了三个手机来作比较,原先两个列表其他项都没再比较,真的就可以了?
  • 回答:当小米3从原先两个列表都取到了值,这说明原先两个列表再也找不到一个手机品牌推荐指数能比小米3再高了(因为如果有,它至少在原先某个推荐列表排名比小米3高,会已经出现在新列表中了)
  • 疑问2:小米是第一个原先两个列表都获取到值的,所以平均分最高?
  • 回答:就算小米3首先"出线",也不能说小米3是最值得入手的,还需要把iphone 5s和Find 7在其他列表的推荐指数也找出来,将三个一一比较才能知道最后鹿死谁手~(当然第5步比较了发现还是小米3高)

更一般的有:

Threshold算法


1.两个列表都选择各自的第一行的项,生成新列表(这一步和Fargin算法相同)

2.算出两列表取出的第一行的平均值
(V(iphone 5s)+V(小米3))/2=(10+9)/2=9.5作为Threshold
3.补全每项在其他列表中的值   得到iphone5S --8.5,小米3--9

4.看新列表的各手机推荐指数平均值是否大于第2步算出的9.5

    8.5和9都比9.5小,两列表取出下一行数据,重复1~4步,直到Threshold比新列表最大值

例子中在进行一次即可,可以看出iphone 5s和小米3都已经大于(等于)第6步算出的8.5,因而没必要再找了(原先两列表剩下的各项最大平均分也不会超过8.5);对比ihone 5s和小米3的平均分,还是选择了小米3。

更一般的有:

此时k=2

参考文献 Top-k query.pdf

© 著作权归作者所有

共有 人打赏支持
上一篇: Hadoop中的RPC
Vegetable
粉丝 18
博文 46
码字总数 46625
作品 0
杭州
私信 提问
Point-In-Polygon Algorithm

Figure 1 Figure 1 demonstrates a typical case of a severely concave polygon with 14 sides. The red dot is a point which needs to be tested, to determine if it lies inside the po......

山哥
2016/11/07
14
0
Top K Frequent Items Algorithm

Top K Frequent Items Algorithm Zhipeng Jiang2017-11-141 阅读 Top K frequent elements is a classic interview question that requires a basic understanding of HashMap and Heap. In ......

Zhipeng Jiang
2017/11/14
0
0
Course3 - machine learning strategy 1

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/robinXushuai/article/details/80626132 introduction to ML strategy 1 - why ML strategy? How to structur......

_席达_
2018/06/08
0
0
机器学习中的supervised learning,unsupervised learning

Have You Heard About Unsupervised Decision Trees Posted by William Vorhies on October 17, 2017 at 8:30am View Blog Summary: Unless you’re involved in anomaly detection you may ......

huangsheng2
2017/10/27
0
0
Mahout推荐算法之SlopOne

一、 算法原理 有别于基于用户的协同过滤和基于item的协同过滤,SlopeOne采用简单的线性模型估计用户对item的评分。如下图,估计UserB对ItemJ的偏好 图(1) 在真实情况下,该方法有如下几个...

xiaomin0322
2018/06/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux Wireshark普通用户启动使用方案

当系统安装好Wireshark后请正常启动是否可以进行正常使用,如果不行请参考下列指导 向系统添加一个用户组 sudo groupadd wireshark //如提示此组存在可跳过 将指定用户添加到这个组中 sudo...

CHONGCHEN
今天
2
0
CSS 选择器参考手册

CSS 选择器参考手册 选择器 描述 [attribute] 用于选取带有指定属性的元素。 [attribute=value] 用于选取带有指定属性和值的元素。 [attribute~=value] 用于选取属性值中包含指定词汇的元素。...

Jack088
今天
2
0
数据库篇一

数据库篇 第1章 数据库介绍 1.1 数据库概述  什么是数据库(DB:DataBase) 数据库就是存储数据的仓库,其本质是一个文件系统,数据按照特定的格式将数据存储起来,用户可以对数据库中的数据...

stars永恒
今天
4
0
Intellij IDEA中设置了jsp页面,但是在访问页面时却提示404

在Intellij IDEA中设置了spring boot的jsp页面,但是在访问时,却出现404,Not Found,经过查找资料后解决,步骤如下: 在Run/Debug Configurations面板中设置该程序的Working Directory选项...

uknow8692
昨天
4
0
day24:文档第五行增内容|每月1号压缩/etc/目录|过滤文本重复次数多的10个单词|人员分组|

1、在文本文档1.txt里第五行下面增加如下内容;两个方法; # This is a test file.# Test insert line into this file. 分析:给文档后增加内容,可以用sed 来搞定;也可以用while do done...

芬野de博客
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部