Digg 最近完成了新一轮的融资，总共 $28.7 million，不过目前国内关注 Digg 的人似乎已经不多了。在官方 blog 里吸引我的是他们提到的一些 new features，“… personalizing the Digg experience, enhancing the recommendation system across other areas of the site, creating deeper category …”。Personalization 越来越成为主流，这是个好事情！
2008年6月底，Digg 终于放出了大家期待已久的 recommendation engine。在运行1个多月之后，他们公布了统计效果：
- 用户活跃度显著提高：增长了40％。
- 运转的很好很强大：平均每个用户会得到200条推荐，这些推荐，平均来自于34个“像你”的用户；整个站点会产生54,000,000条推荐。
- 友邻活动/添加友邻增长了24％。
- 评论增长了11％。
我不是 Digg 的深度用户，基本是在他们放出 recommendation engine 之后，才逐渐增加了 Digg 的使用频度，而且也还是断断续续的。但就简单体验来看，效果还是蛮不错的。如果你是 Digg 的忠实用户，非常欢迎到这里来讨论。
另外，最近在使用各类 SNS 的过程中，被好友动态折腾到不行。而且清一色的流水帐布局，乱，没有效率，也缺乏新意。我简单地提了个小设想，“在好友范围内，统计一天里最 popular 的东西”。回头却发现，FriendFeed 早在8月份的时候就已经推出了这个 feature。最近基本上没怎么使用 FriendFeed，疏忽了，看来接下来需要提高 FriendFeed 的使用频率，跟踪研究一下效果。
淘宝数据仓库团队，在“HADOOP中一种非典型两表JOIN的处理方法”这篇文章里， 无私地 share 了他们的方法。我就着他们的写一个续，权当讨论，抛砖引玉。淘宝团队的文章主要说的是大规模数据情况下如何计算，我这篇接着他们最后的问题，即“多对多”的情况说一下思路。
要解决的问题可以简化描述一下：
- 有两组数据，input1 { P1, U1; P1, U2; P2, U3; P3, U4; P4, U4 }，input2 { P1, C1; P1, C2; P2, C3; P3, C3; P3, C4; P4, C4 }。
- 要求执行类似于数据库两表 Inner Join 的操作，以 P 为 key，建立起 U 和 C 直接的对应关系，即最终结果为 output { U1, C1; U1, C2; U2, C1; U2, C2; U3, C3; U4, C3; U4, C4 }。
在数据库里，使用类似的 SQL 可以达到要求：SELECT DISTINCT(U, C) FROM input1 INNER JOIN input2 ON input1.P=input2.P。但如果要放在 Hadoop 里面求解，就需要动些脑筋了。
研究这个问题，首先需要理解 Hadoop 的运行机制。简单来讲，Hadoop 分为 Map 和 Reduce 两个操作：Map 操作将输入（如一行数据）格式化为 <key: value1><key: value2><key: value3> … <key: valueN>这样的一组结果，作为 Map 的输出。Hadoop 在 Map 和 Reduce 之间，会自动把 Map 的输出按照 key 合并起来，作为 Reduce 的输入。Reduce 得到这样一个 {key: [value1, value2, value3, ..., valueN]} 的输入之后，就可以进行自己的处理，完成最终计算了。
针对于我们这里要解决的问题，步骤如下。
- 将 Map 的输入构造为下面的格式：来自于 input1 的输入格式化为 {<input1, P1>: U1, U2}；来自于 input2 的输入格式化为 {<input2, P1>: C1, C2}。
- 在 Map 操作内，将数据转化为 {P1: <input1, U1>}，{P1: <input1, U2>}，{P1: <input2, C1>}，{P1: <input2, C2>}，作为 Reduce 操作的输入。
- 经过 Hadoop 内部自己的操作，实际 Reduce 操作的输入为：{P1: <input1, U1>, <input1, U2>, <input2, C1>, <input2, C2>}。
- Reduce 里操作会复杂一下。首先需要执行一次 regroup，得到如下的结果 {<input1>: <input1, U1>, <input1, U2>; <input2>: <input2, C1>, <input2, C2>}。把这个结果拆开，可以得到两个集合：{<input1>, <input2>} 与 {[<input1, U1>, <input1, U2>], [<input2, C1>, <input2, C2>]}。
- 循环集合2，即可以得到最终结果。不过在 Reduce 里面作这个循环是需要一定技巧的，讲起来比较绕，大家就直接看后面的代码吧。
- 在此 Reduce 的结果之上，再跑一个 Map/Reduce，还可以得到 <U, C>的次数，作为每个组合的权重。
对于大数据量，需要启用 Hadoop 的数据压缩功能。
这是一个通用地解决 Inner Join 问题的思路，在 Hadoop 的 contrib package 里有具体的代码实现，参见 org.apache.hadoop.contrib.utils.join。
国内还有哪个 team 在用 Hadoop？欢迎交流！
中国有句老话，叫做“知易行难”。
作算法的朋友应该更有体会，想把 paper 上的公式转变为可以运行的代码，这是件考验功力的事情。
Toby Segaran 写的这本《Programming Collective Intelligence》，是修炼此种功力的武林秘笈之一。
这本书最显著的特点是，实战性极强！
针对每个算法，他从头到尾演示了一个完整的实现过程：从获取数据，组织存储，到算法实现，加载运算，再到最后的结果的分析利用。书中所有的例子均基于实际系统的真实数据，作者演示了大量的开放 API 的使用，Delicious、Amazon、Last.fm、Google News，各个都是大名鼎鼎，每步都是真刀真枪。跟着书中的操作这样一趟走下来，你会豁然开朗，原来这些看似神秘复杂的系统，也不过如此。但不幸的是，其中的大部分 API 已经不能工作了。比如 del.icio.us API，你就得换这个了。
从纯粹算法的角度来讲，这本书里讲解的算法，基本都是入门级的。但即使是这样，能把细节讲述地如此传神，也实属不易。换一个角度来看，简单，也同时意味着常用，熟练掌握了书中的这些算法，也足以解决不少的现实问题。而且，在拥有大规模数据的情况下，简单的算法，往往也可以取得令人吃惊的效果 [1]。
另外一个方面，此书作者用英文遣词造句的能力出神入化，读起来简直行云流水。时常会让自己产生英文超牛的幻觉，体验很爽。
没时间细读的朋友，也建议至少看一下 Toby Segaran 写的 Social Data Mining 这个 slide，一定会有收获。
我得知此书，需感谢个性化技术相关资料后面，KaKa 网友的推荐。
豆瓣猜没有帮助我发现这本书。
这曾让我思考，基于 SNS 的推荐，是否比传统的推荐更有效呢？
五星！
