关于豆瓣的口味相似度算法

2006-04-25 20:17:54 　　来自:enjoy (成都)
大家好，我是豆瓣的忠实用户。前段时间抄袭豆瓣的界面做了个网站：
http://www.miantuan.com
基本功能完成了，现在问题在于类似豆瓣的口味匹配运算，这个也是我比较挠头的. 目前只是简单建立模型如下:
A集合中有若干成员a1,a2,a3……
B集合中有若干成员b1,b2,b3……
A和B中的每一个成员都可能会发生最多一个关系，这个关系有一个权重，为了初期算法分析的简单，我们忽略权重的问题，仅考虑关系的有无。
现在的问题是，得到A集合中与某个成员A[n]口味最相似的前m个成员列表。
从我的模型中可以猜到我大概是怎么实现算法的了，就是比较每个A成员的关联集合B[x]，然后得到与B[n]重合率最高的前几个A成员。
没有时间仔细考虑，这样的结果是算法效率很低，时间复杂度太高，数据量大的话简直是灾难。 不可能实现实时的运算和展现。
我简单做了测试，2000用户2000评论对象，评价数据20000条，输入1用户id，输出口味最相似的前5用户id，运算平均完成时间在6秒左右。这基本是不能接受的。目前只能又写一个单独的运算程序，在CPU空闲时间较多的时段整体运算，然后存入数据库备用。每天定时执行，一般都在凌晨3点到5点。
不知道大家有没有更好的办法？
想问阿北的是，我这样做，在模型上是不是就已经很笨了？出在算法实现上的问题好解决，可以慢慢来，在模型建立上出问题，就是硬伤了……
2006-04-26 11:48:29:enjoy (成都)
昨天在现有模型下对算法做了改进,时间上缩短了很多,但是还是不能达到实时运算的效果.
这应该是模型本身的问题,如果坚持这样的算法,在现有条件下,只能定期采取集中运算,然后使用运算结果的方法.
2006-04-26 14:04:49:enjoy (成都)
没人给句话啊?我也知道算法问题可能不适合在这个组讨论,可是没地方啊.....
2006-04-26 14:06:11:.
呵呵
昨天看到这个帖子
俺就估计木回应了
算法是命根呐
2006-04-26 14:15:56:enjoy (成都)
风向标,我不是来讨算法来了......
我的本意是来探讨,我目前也能初步解决客户的需求,问题在于自己不满意.
而且我探讨的也不是算法的实现,而是模型的建立,这个是我非常关心的,从模型到算法实现还有很多路要走,这样的探讨也不会泄露什么吧?
2006-04-26 14:33:52:.
老实说俺对算法一窍不通
不过群内一定有高人
HOHO 迟些时候应该有大牛浮出来的
2006-04-26 15:43:47:傻大猫 (北京)
偶觉得这肯定应该在后台跑 然后保存起来 而不是在打开页面时候在计算的
2006-04-26 15:48:22:enjoy (成都)
傻大猫:照我的模型和算法,肯定只能这样跑.而且就这样,效果也不是很好,当然这个具体算法可以改进.
我很关心的是,有没有更加优美的模型来解决这个问题.
2006-04-26 16:10:30:enjoy (成都)
掉出第一页,我就放弃.
等我找到更好的模型或者更好的算法,一定发出来给大家看.
2006-04-26 21:16:55:.
enjoy兄如果有了结果
一定要共享呐~!
2006-04-26 22:04:12:111111 (扬州)
可能要把你说的a集合和b集合针对你这个特定的需求做成特定的数据结构才好，普通的集合肯定不行
2006-04-27 12:22:04:吕粉|妾有绣腰襦 (淮北)
http://www.miantuan.com 不错.
2006-04-27 13:41:27:die();
界面完全照抄，I服了u，能不能有一点不一样的地方，毕竟主体完全不一样，照搬UI没有任何好处。
2006-04-27 14:21:03:enjoy (成都)
http://www.miantuan.com/About/
我真的干不来UI的活儿,就连图标都是央求朋友帮忙做的.
而且做得过程中,还在帮豆瓣检查HTML语法错误呢,:)
2006-04-27 14:27:34:enjoy (成都)
http://www.douban.com/forum/2/102546
http://www.douban.com/forum/2/102560
2006-04-27 15:45:12:enjoy (成都)
找了几个朋友,最新的讨论结果公布如下:
1.豆瓣的口味推荐数据也不是实时的.原因如下:
1.1 据我们使用一个帐号进行的测试,首先使用该用户选择一些书籍电影和音乐并评分,然后迅速换掉.结果是推荐在一段时间(几小时)内没有改变.
1.2http://www.douban.com/group/topic/1015820/ 阿北的话.其中有几句值得玩味:"不过豆瓣有很多后台的程序和处理，用php不是很有效。当初不想对付两套语言，所以决定用python的。";"菜贩子, 豆瓣的后台数据处理有的一天跑一次。".纵观豆瓣,目前几乎没有其他的运算达到这样的运算量,需要一天跑一次的.
2.关于模型.
至少目前从豆瓣的结构上来看,使用的既然是MYSQL这种RMDBS,那么数据存储的物理结构不会有什么特别的地方,顶多就是在索引性能和冗余设计等方面有一些小技巧,这个可以慢慢总结不着急.但是从豆瓣的系统框架来看,没有引入类似人工智能算法框架这种的新东西,那么就是说,目前还是处于一般性问题领域.从这几点分析,豆瓣的基本模型可能会在我们预计的模型上有一些小的变化,包括在算法实现上可能会有很多小的技巧性的东西,但是问题模型,还是在我们估计的范围内.这么自信的原因主要是今天收到MS工程院工作的一个朋友的邮件,讲他在处理这种问题时也没有更好的办法,那我就更没辙了,不知道阿北是不是真有突破.
这个算法就豆瓣而言,只是推荐臭味相投的人,以及合乎用户口味的产品.但是它适用的领域应该很广,应用前景也应该不是这么一点.如果对问题模型能有根本的改进,那会是件很让人激动的事情.
ok,这个问题到此为止,我也不再让阿北难办了.我把我知道的都公布了出来,希望对感兴趣的朋友有所帮助.如果有兴趣,可以发邮件给我继续讨论.
2006-04-27 16:23:42:phsoft
你的页面的viewstate数据比较大，估计是你的分页方式引起的，这块还可以推敲推敲
:P
2006-04-27 16:24:56:phsoft
呵呵，当然这个和你本贴的问题毫无关系
2006-04-27 16:32:28:phsoft
尽快换了这个界面，这个直接影响你的网站的发展
2006-04-27 17:10:48:enjoy (成都)
TO:phsoft:
多谢,数据比较少,分页暂时把数据取全了,有时间加个存储过程就解决了.主要是我比较懒,知道怎么做的东西就懒得去做,2.0嘛,随时升级也算符合2.0精神.^_^
我这个网站没想他怎么发展,目前的流量报表来看,每天都在给几百从搜索引擎来的校园用户提供情报,这就够了,他们参与与否不重要,本来我就是玩票.我的主业不是这个,只是找个东西可以下班玩儿.^_^
2006-04-27 23:22:57:吕粉|妾有绣腰襦 (淮北)
我欣赏这种玩票性质~
2006-05-01 10:31:56:大熊 (北京)
这种计算显然是offline的
并且你猜测的那种办法是最简单的
国际上对collaborative recommendation方面的研究已经开展了很多年了
2006-05-01 10:35:18:大熊 (北京)
另外，面试这种主题不可能对用户产生很高粘性的吧
一个人能面几次啊
这样注定了他没办法分享几次就不会再考虑这搭事了
比如我毕业一年了，就不会再去看这些面试相关的东西了
2006-06-03 16:25:19:Jim (保定)
enjoy同学、同志、先生，我觉得你应该请阿北喝酒
2006-06-04 19:45:31:alex (上海)
复杂的问题简单看，简单的问题复杂想。
enjoy，做了这么多工作，也是高手！
定义a是一个元素，a可以是小组成员或者书，属性{标签，点击次数，点击者}，统计所有点击者的所看的其他元素的个数，排序出前6名（计算算法中可以只取前6最大概率的元素），复杂度分析，设a属于n，与a有关的点击者为m，与点击者相关的元素为p,m*P为与a相关的推荐，m最大为所有用户，p为所有用户或者产品，实际上，m最多为500左右（历史经验），p的数量级别大概数十位左右，这样至多对于每次关于a的数据统计为5000次左右，大概2秒可以计算出。如果按照现在网站的规模1万产品，对于买个产品的计算，应该2万秒，折合3个小时左右。
采取策略，针对活跃性a元素，采取实时计算，并采用多线程计算返回实时更新。对于非活跃性a元素，采取夜间大规模另外的数据仓库计算。
我想总有解决办法。
另外，建议关注 数据挖掘“关联规则算法”。
瞎说，大家别信。
2006-06-05 13:31:33:中医药
PHP5有本书里有类似的推荐算法
2006-06-05 13:37:45:NJ.G (石家庄)
头大ing
2006-06-06 11:36:41:ptree (暂居北京)
数据巨大时，实时是不可能的
模型是正确的，算法可简化考虑：先统计对象的收藏人数，只选择那些少数人收藏的对象关系来计算．对每个用户来说，也只选择其评价最高的，或标签频次最高的一些对象，作其独特的＼稳定的＼兴趣特征
2006-06-07 11:25:17:薛定锷的猫 (北京)
enjoy兄,7位数啊~~~
2006-06-07 14:55:21:enjoy (成都)
我晕，帖子又被翻出来了。
汇报一下，最近在做一些数据挖掘方面的研究，发现这个东西其实已经有很成熟的理论和产品了。比如使用SQL Analysis Server做面向主题的Data Report，然后使用Web做前端展现等等。这个东西在商业领域其实应用很广泛，比如零售商可以根据每位顾客的购买习惯、时段、顾客背景、地域、体育比赛时刻等等数据分析出这些数据背后的隐藏结论，从而做出诸如调整货架摆放顺序等策略以争取最大利润。这是数据挖掘理论的典型应用.感兴趣的朋友可以去看看相关资料.
2006-06-07 15:05:24:enjoy (成都)
对了,索性再啰嗦几句.
1.面团纯粹是我个人kill time用途的小东西,没有任何商业目的和计划.借用豆瓣界面的原因我在"关于面团"页面中已经说了,不再赘述.如果豆瓣官方任何人出面联系我,不希望我借用豆瓣界面,我会马上修改.所以那些好心的朋友不用再发邮件骂我了,我又不会回,又不会计较,浪费您的时间实在是不划算.楼上好心提醒的朋友在此谢过了.
2.关于这个讨论,占用了大量的豆瓣小组版面,实在抱歉,当然也给面团拉来不少流量,实在是无心之举.豆瓣过来的,绝大多数都不是对面团的内容感兴趣的朋友,呵呵,实在对不起,浪费您的眼球了.
但愿这个帖子沉下去,不影响大家讨论python.
2006-06-07 23:41:30:alex (上海)
我很佩服和喜欢enjoy的风格。
是个男人！
2006-06-17 09:42:47:小力 (深圳)
想得太复杂了，tag是简化口味相似度算法的关键。
没有tag/keyword，那么你得用分词技术，把用户输入的帖子/评价等等等按照词的单位分割开，然后按照某些词在哪些用户那里出现的重复频率来计算相似度。
但现在信息过载严重，每个用户输入的帖子/评价，太多了，按照上面的方法，大概3万注册用户，50万条左右的帖子/评价数据(db字段是text文本，有长有短)，一台双PIII，2G内存的机器需要12个小时才能计算完，这是个大概情况，有可能程序代码可以更加优化。
但是，这已经无法接受了。
我闪了，免得被暗算......
2006-07-02 23:36:03:David 大伟 (广州)
2006-06-07 23:41:30: alex (上海)
我很佩服和喜欢enjoy的风格。
是个男人！
2006-09-19 10:45:57:guotie (南京)
对，小力的方法我很欣赏。
从tag的角度去简化模型，而不是直接对集合进行分析。而且，你的假设只有两个集合，如果有200个集合呢？
2006-09-20 09:07:56:111111 (扬州)
看这个：
数学之美系列五 -- 简单之美：布尔代数和搜索引擎的索引
2006年5月10日 上午 09:10:00
发表者: 吴军，Google 研究员
[建立一个搜索引擎大致需要做这样几件事：自动下载尽可能多的网页；建立快速有效的索引；根据相关性对网页进行公平准确的排序。我们在介绍 Google Page Rank (网页排名) 时已经谈到了一些排序的问题，这里我们谈谈索引问题，以后我们还会谈如何度量网页的相关性，和进行网页自动下载。］
世界上不可能有比二进制更简单的计数方法了，也不可能有比布尔运算更简单的运算了。尽管今天每个搜索引擎都宣称自己如何聪明、多么智能化，其实从根本上讲都没有逃出布尔运算的框框。
布尔（George Boole) 是十九世纪英国一位小学数学老师。他生前没有人认为他是数学家。布尔在工作之余，喜欢阅读数学论著、思考数学问题。1854 年“思维规律”（An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities）一书，第一次向人们展示了如何用数学的方法解决逻辑问题。
布尔代数简单得不能再简单了。运算的元素只有两个1 （TRUE， 真) 和 0
（FALSE，假)。基本的运算只有“与”（AND)、“或” (OR) 和“非”（NOT) 三种（后来发现，这三种运算都可以转换成“与”“非” ＡＮＤ－ＮＯＴ一种运算）。全部运算只用下列几张真值表就能完全地描述清楚。
AND | 1 0
-----------------------
1 | 1 0
0 | 0 0
这张表说明如果 AND 运算的两个元素有一个是 0，则运算结果总是 0。如果两个元素都是 1，运算结果是 1。例如，“太阳从西边升起”这个判断是假的(0),“水可以流动”这个判断是真的（1），那么，“太阳从西边升起并且水可以流动”就是假的（0）。
OR | 1 0
-----------------------
1 | 1 1
0 | 1 0
这张表说明如果OR运算的两个元素有一个是 1，则运算结果总是 1。如果两个元素都是 0，运算结果是 0。比如说，“张三是比赛第一名”这个结论是假的（0），“李四是比赛第一名”是真的（1），那么“张三或者李四是第一名”就是真的（1）。
NOT |
--------------
1 | 0
0 | 1
这张表说明 NOT 运算把 1 变成 0，把 0 变成 1。比如，如果“象牙是白的”是真的（1），那么“象牙不是白的”必定是假的（0）。
读者也许会问这么简单的理论能解决什么实际问题。布尔同时代的数学家们也有同样的问题。事实上在布尔代数提出后80 多年里，它确实没有什么像样的应用，直到 1938 年香农在他的硕士论文中指出用布尔代数来实现开关电路，才使得布尔代数成为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、乘方、开方等等，全部能转换成二值的布尔运算。
现在我们看看文献检索和布尔运算的关系。对于一个用户输入的关键词，搜索引擎要判断每篇文献是否含有这个关键词，如果一篇文献含有它，我们相应地给这篇文献一个逻辑值 -- 真（TRUE,或 1），否则，给一个逻辑值 -- 假（FALSE, 或0）。比如我们要找有关原子能应用的文献，但并不想知道如何造原子弹。我们可以这样写一个查询语句“原子能 AND 应用 AND (NOT 原子弹)”，表示符合要求的文献必须同时满足三个条件：
- 包含原子能
- 包含应用
- 不包含原子弹
一篇文献对于上面每一个条件，都有一个 True 或者 False 的答案，根据上述真值表就能算出每篇文献是否是要找的。
早期的文献检索查询系统大多基于数据库，严格要求查询语句符合布尔运算。今天的搜索引擎相比之下要聪明的多，它自动把用户的查询语句转换成布尔运算的算式。当然在查询时，不能将每篇文献扫描一遍，来看看它是否满足上面三个条件，因此需要建立一个索引。
最简单索引的结构是用一个很长的二进制数表示一个关键字是否出现在每篇文献中。有多少篇文献，就有多少位数，每一位对应一篇文献，1 代表相应的文献有这个关键字，0 代表没有。比如关键字“原子能”对应的二进制数是0100100001100001...，表示第二、第五、第九、第十、第十六篇文献包含着个关键字。注意，这个二进制数非常之长。同样，我们假定“应用”对应的二进制数是 0010100110000001...。那么要找到同时包含“原子能”和“应用”的文献时，只要将这两个二进制数进行布尔运算 AND。根据上面的真值表，我们知道运算结果是0000100000000001...。表示第五篇，第十六篇文献满足要求。
注意，计算机作布尔运算是非常非常快的。现在最便宜的微机都可以一次进行三十二位布尔运算，一秒钟进行十亿次以上。当然，由于这些二进制数中绝大部分位数都是零，我们只需要记录那些等于1的位数即可。于是，搜索引擎的索引就变成了一张大表：表的每一行对应一个关键词，而每一个关键词后面跟着一组数字，是包含该关键词的文献序号。
对于互联网的搜索引擎来讲，每一个网页就是一个文献。互联网的网页数量是巨大的，网络中所用的词也非常非常多。因此这个索引是巨大的，在万亿字节这个量级。早期的搜索引擎（比如 Alta Vista 以前的所有搜索引擎），由于受计算机速度和容量的限制，只能对重要的关键的主题词建立索引。至今很多学术杂志还要求作者提供 3-5 个关键词。这样所有不常见的词和太常见的虚词就找不到了。现在，为了保证对任何搜索都能提供相关的网页，所有的搜索引擎都是对所有的词进行索引。为了网页排名方便，索引中还需存有大量附加信息，诸如每个词出现的位置、次数等等。因此，整个索引就变得非常之大，以至于不可能用一台计算机存下。大家普遍的做法就是根据网页的序号将索引分成很多份（Shards)，分别存储在不同的服务器中。每当接受一个查询时，这个查询就被分送到许许多多服务器中，这些服务器同时并行处理用户请求，并把结果送到主服务器进行合并处理，最后将结果返回给用户。
不管索引如何复杂，查找的基本操作仍然是布尔运算。布尔运算把逻辑和数学联系起来了。它的最大好处是容易实现，速度快，这对于海量的信息查找是至关重要的。它的不足是只能给出是与否的判断，而不能给出量化的度量。因此，所有搜索引擎在内部检索完毕后，都要对符合要求的网页根据相关性排序，然后才返回给用户。
2006-09-21 23:09:31:月亮上的石头 (深圳)
很好的论题呀，学到了不少好东西