使用SQL语句写的Tanimoto系数

一个简单的推荐机制

最近，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.的数据和API，可惜他们最近更改了API，所以无法使用书中的代码做练习。但想起了CSDN的网摘功能，花了点时间把大部分的网摘记录爬了下来（感谢CSDN的曾登高提供其中几个人的数据）。我把记录都放在一个名叫Post的表里了，它包含URL（用户保存的文章的地址），Title（用户保存使用的标题），UserName（用户名），PostDate（保存网址的日期）这些字段。

得到的数据集中包括3753个用户，不同的链接数为68304，最多的一个人保存了7519个链接，平均每个人保存了23个链接。保存人数最多的是这篇贴子，

40种网站设计常用技巧

链接的来源是这样的，

网站	链接数
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.	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需要非常大的内存/硬盘，可惜这个机器上的容量很小，所以只好放弃。