一个简单的推荐机制
最近，O'Reilly出版了Toby Segaran著的《Programming Collective Intelligence - Building Smart Web 2.0 Applications》（据说该书将由博文视点翻译出版），讨论如何从数据（譬如用户生成的数据）里挖掘信息的各种算法和技术，非常实用，对正在建造Web 2.0网站的开发人员尤其有用。跟大多数数据挖掘和机器学习的书不一样，书里包含了大量Python代码，使用网上现有的数据集或可以轻易采集的数据（譬如blog）或公开的API（譬如Digg，eBay的），助你理解各种算法，解释如何从大量的数据中获取关于用户体验，营销性，个人趣味，和人类行为的认识。该书得到了首创“Web 2.0”一词的O'Reilly公司CEO Tim O'Reilly的大力推荐。
其中的第二章《Making Recommendations》讨论了协作性过滤技术（Collaborative Filtering），通过搜寻一个很大的群体，从中找出与你趣味相似的人，然后把这些人喜爱的其他东西，聚合起来，创建一个推荐的排行榜（譬如电影推荐，产品推荐等等）。书中使用了del.icio.us的数据和API，可惜他们最近更改了API，所以无法使用书中的代码做练习。但想起了CSDN的网摘功能，花了点时间把大部分的网摘记录爬了下来（感谢CSDN的曾登高提供其中几个人的数据）。我把记录都放在一个名叫Post的表里了，它包含URL（用户保存的文章的地址），Title（用户保存使用的标题），UserName（用户名），PostDate（保存网址的日期）这些字段。
得到的数据集中包括3753个用户，不同的链接数为68304，最多的一个人保存了7519个链接，平均每个人保存了23个链接。保存人数最多的是这篇贴子，
链接的来源是这样的，
| 网站 | 链接数 |
|---|---|
| community.csdn.net | 21770 |
| blog.csdn.net | 12260 |
| blog.donews.com | 1865 |
| topic.csdn.net | 1836 |
| news.csdn.net | 1526 |
| www.cnblogs.com | 1237 |
| book.csdn.net | 831 |
| dev.csdn.net | 810 |
| download.csdn.net | 773 |
| spaces.msn.com | 758 |
| tech.sina.com.cn | 719 |
| www.donews.net | 491 |
| blog.sina.com.cn | 438 |
| club.book.csdn.net | 378 |
| www.infoq.com | 336 |
前十位CSDN网站占了7个，好像不是很健康啊，
。
言归正传，那么针对CSDN网摘记录怎么来定义用户间的相似性？作者在这一章里讨论了欧几里德距离和Pearson相似性公式，其他的公式可以参考《数据挖掘导论》一书2.4节中的讨论（CSDN免费提供了几个章节）。在这个练习中，我将采用Tanimoto系数来定义相似性(图片来自原书网站），
在这里Na代表用户a保存的所有链接数，Nb代表用户b保存的所有链接数，Nc则代表用户Na和Nb间共同拥有的链接数。譬如，如果我保存了10个链接，你保存了20个链接，我们共有的链接为5个，那么我们间的相似性为5/(10+20-5）=0.2。
使用Tanimoto系数的的原因是对链接这样要么有，要么无的二元性的数据感觉很直观，而且容易计算（用数据库操作即可）。
先生成一个表，
create table RelatedUser (username1 nvarchar(50), username2 nvarchar(50), urlcount1 int, urlcount2 int, commoncount int, coeff decimal(18,16))
然后填充其中的数据，针对用户做个cross product，然后更新共有的链接数以及各自的链接数，
insert into relateduser (username1, username2, commoncount)
select username1, username2, count(url)
from
(
select p1.username as username1, p2.username as username2, p1.url
from post p1, post p2
where p1.url=p2.url
and p1.username <> p2.username
) t
group by username1, username2
go
update relateduser set urlcount1 = ps.urlcount
from relateduser u
inner join (select count(*) urlcount, username from post group by username) ps
on u.username1 = ps.username
go
update relateduser set urlcount2 = ps.urlcount
from relateduser u
inner join (select count(*) urlcount, username from post group by username) ps
on u.username2 = ps.username
go
生成Tanimoto系数，
update relateduser set coeff = convert(decimal,commoncount)/(urlcount1+urlcount2-commoncount)
go
让我们来看一下与用户jiangtao相似的用户，
select username2, commoncount, coeff from relateduser where username1 = 'jiangtao' order by coeff desc
go
其中前十个为
| 用户名 | 共有的链接数 | Tanimoto系数 |
|---|---|---|
| zdg | 78 | 0.017165493 |
| 94smart | 80 | 0.009725261 |
| rjchen | 14 | 0.009504413 |
| hcat1999 | 4 | 0.004561003 |
| waynehuge | 4 | 0.003910068 |
| grhunter | 4 | 0.003710575 |
| tq85 | 10 | 0.002983294 |
| tonywjd | 3 | 0.002811621 |
| flyfish10000 | 2 | 0.002538071 |
| bluebubble | 2 | 0.002427184 |
假如我们指定只有共有的链接数超过10个才算相似，那么很明显，与jiangtao趣味相似的用户依次为(难怪啊，恐怕生活中他们就是jiangtao的朋友），
zdg
94smart
rjchen
tq85
据此，我们可以向jiangtao推荐他还没有读过的文章，
select title,url from post where username in (
select top 10 username2 from relateduser
where username1 = 'jiangtao' and commoncount >=10
order by coeff desc
) and url not in (
select url from post where username = 'jiangtao')
order by postdate desc, title, url
其中前十篇为
“正略一品”系列之六：在美国研究草原上的狗尾巴??赵民 - 新浪BLOG
The Podium ''08 - Election Guide 2008 - MSN
卓越亚马逊:WIKINOMICS维基经济:Management:Business & Investing 经管与理财:进口原版:图书:Don Tapscott
理念随笔之八：换位思考，假如咱是庄家
微软的.NET源代码：可远观而不可亵玩也
TechMeme：聚合的力量
传统媒体和新媒体的对决：Techmeme Leaderboard上线
Facebook开放平台完全解析
Google为何收购Jaiku而非Twitter？
Google首页的CSS Sprite
这是基于用户的过滤，还可以做基于item（这里是URL）的过滤。可惜，因为URL数太多，在数据库里对URL做cross product需要非常大的内存/硬盘，可惜这个机器上的容量很小，所以只好放弃。
posted on 2007-10-24 12:47:00 by saucer 评论(10) 阅读(6308)