协同推荐系统简介
最近几年搜索引擎理念可谓渗入人心，对于互联网产品设计人员来说，张口必言搜索。同事基于搜索技术的各种产品也在Web2.0的浪潮下如雨后春笋，刷刷往 外冒。在这些林林总总的产品里面，几乎都能见到“ tag , 相关新闻, 相似产品 ” 类推荐链接的踪影。稍加留意这些产品的实现就可以发现，大多还是基于关键词的搜索机制实现的。很显然基于关键词技术的相关推荐是最直观的，似乎也是最有效 的一种实现方式，如同机枪中的AK-47，那他冲锋陷阵总是屡试不爽。 对于文字类产品的推荐，基于关键词的实现方式，目前还是主流；但在电子商务，智能阅读推荐，商务搜索方面单纯的关键字相关性实现机制还不那么让人满意，这也就有了协同推荐过滤系统。Collaborative filtering 。 所谓协同推荐，很显然弥补了单纯依赖关键词相关性的不足，把获取相关性数据的视角放大到数据从产生到消费的各个环节。 有2种最基础类型的协同推荐系统： 1 基于当前活跃用户 和 上一个用户的相似性 来进行分析（一般是计算用户购买或者感兴趣的商品来进行）；侧重于用户 2 基于当前用户选择（或感兴趣）的商品 和 上一个用户感兴趣的商品的相似性来进行分析； 这也就是大家所熟知的user-based 和item-based协同推荐。 根据实现机制物理载体划分，以上两类协同推荐系统可以分为：内存型 和 模式型的协同推荐。一般内存型的都比较直观，适合于小型的数据集合，而模式型的一般都是利用 机器学习的方法，适用于大规模的数据分析，也可以称之为离线分析。模式型的是我比较关心的，因为做基于SEO的日志分析 ，比较适合。 我们在进行协同分析的时候，要考虑协同的意义。一般来说协同就是指多个用户或多个数据项的交叉作用。如果数据项较多的情况下，如何定义数据项的关系就是个重要问题了。 下面说一下协同系统的设计要素吧： 1 数据项 Item 2 项集合 ItemCollection 3 数据项的关系权重 DirectedEdge 4 数据项在数据集合中的存储方式 具体的算法实现过程，可以参考：Beyond Search 的推荐系统：关联规则(2)。我这里摘录如下：
Apriori 是一种广度优先算法，通过多次扫描数据库来获取支持度大于最小支持度的频繁项集。它的理论基础是频繁项集的两个单调性原则：频繁项集的任一子集一定是频繁 的；非频繁项集的任一超集一定是非频繁的。晦涩的理论我这里就不多写了，有兴趣的可以去看论文。我把里面的例子给翻译一下，图文并茂，简明易懂。 某数据库 DB 里有 4 条事务记录，取最小支持度（min support）为 0.5，则计算频繁项集的过程如下：
TID Items 100 A, C, D 200 B, C, E 300 A, B, C, E 400 B, E | TID | Items | 100 | A, C, D | 200 | B, C, E | 300 | A, B, C, E | 400 | B, E | 扫描DB | Itemset Support {A} 2 (0.5) {B} 3 (0.75) {C} 3 (0.75) {D} 1 (0.25) {E} 3 (0.75) | Itemset | Support | {A} | 2 (0.5) | {B} | 3 (0.75) | {C} | 3 (0.75) | {D} | 1 (0.25) | {E} | 3 (0.75) | 取满足 最小支持度 项集 | Itemset Support {A} 2 {B} 3 {C} 3 {E} 3 | Itemset | Support | {A} | 2 | {B} | 3 | {C} | 3 | {E} | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
TID | Items | |||||||||||||||||||||||||||||||||||
100 | A, C, D | |||||||||||||||||||||||||||||||||||
200 | B, C, E | |||||||||||||||||||||||||||||||||||
300 | A, B, C, E | |||||||||||||||||||||||||||||||||||
400 | B, E | |||||||||||||||||||||||||||||||||||
Itemset | Support | |||||||||||||||||||||||||||||||||||
{A} | 2 (0.5) | |||||||||||||||||||||||||||||||||||
{B} | 3 (0.75) | |||||||||||||||||||||||||||||||||||
{C} | 3 (0.75) | |||||||||||||||||||||||||||||||||||
{D} | 1 (0.25) | |||||||||||||||||||||||||||||||||||
{E} | 3 (0.75) | |||||||||||||||||||||||||||||||||||
Itemset | Support | |||||||||||||||||||||||||||||||||||
{A} | 2 | |||||||||||||||||||||||||||||||||||
{B} | 3 | |||||||||||||||||||||||||||||||||||
{C} | 3 | |||||||||||||||||||||||||||||||||||
{E} | 3 | |||||||||||||||||||||||||||||||||||
Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} | Itemset | {A, B} | {A, C} | {A, E} | {B, C} | {B, E} | {C, E} | 扫描DB | Itemset Support {A, B} 1 (0.25) {A, C} 2 (0.5) {A, E} 1 (0.25) {B, C} 2 (0.5) {B, E} 3 (0.75) {C, E} 2 (0.5) | Itemset | Support | {A, B} | 1 (0.25) | {A, C} | 2 (0.5) | {A, E} | 1 (0.25) | {B, C} | 2 (0.5) | {B, E} | 3 (0.75) | {C, E} | 2 (0.5) | 取满足 最小支持度 项集 | Itemset Support {A, C} 2 {B, C} 2 {B, E} 3 {C, E} 2 | Itemset | Support | {A, C} | 2 | {B, C} | 2 | {B, E} | 3 | {C, E} | 2 | |
Itemset | ||||||||||||||||||||||||||||||||||||
{A, B} | ||||||||||||||||||||||||||||||||||||
{A, C} | ||||||||||||||||||||||||||||||||||||
{A, E} | ||||||||||||||||||||||||||||||||||||
{B, C} | ||||||||||||||||||||||||||||||||||||
{B, E} | ||||||||||||||||||||||||||||||||||||
{C, E} | ||||||||||||||||||||||||||||||||||||
Itemset | Support | |||||||||||||||||||||||||||||||||||
{A, B} | 1 (0.25) | |||||||||||||||||||||||||||||||||||
{A, C} | 2 (0.5) | |||||||||||||||||||||||||||||||||||
{A, E} | 1 (0.25) | |||||||||||||||||||||||||||||||||||
{B, C} | 2 (0.5) | |||||||||||||||||||||||||||||||||||
{B, E} | 3 (0.75) | |||||||||||||||||||||||||||||||||||
{C, E} | 2 (0.5) | |||||||||||||||||||||||||||||||||||
Itemset | Support | |||||||||||||||||||||||||||||||||||
{A, C} | 2 | |||||||||||||||||||||||||||||||||||
{B, C} | 2 | |||||||||||||||||||||||||||||||||||
{B, E} | 3 | |||||||||||||||||||||||||||||||||||
{C, E} | 2 | |||||||||||||||||||||||||||||||||||
Itemset {A, B, C} {A, B, E} {A, C, E} {B, C, E} | Itemset | {A, B, C} | {A, B, E} | {A, C, E} | {B, C, E} | 扫描DB | Itemset Support {A, B, C} 1 (0.25) {A, B, E} 1 (0.25) {A, C, E} 1 (0.35) {B, C, E} 2 (0.5) | Itemset | Support | {A, B, C} | 1 (0.25) | {A, B, E} | 1 (0.25) | {A, C, E} | 1 (0.35) | {B, C, E} | 2 (0.5) | 取满足 最小支持度 项集 | Itemset Support {B, C, E} 2 (0.5) | Itemset | Support | {B, C, E} | 2 (0.5) | |||||||||||||
Itemset | ||||||||||||||||||||||||||||||||||||
{A, B, C} | ||||||||||||||||||||||||||||||||||||
{A, B, E} | ||||||||||||||||||||||||||||||||||||
{A, C, E} | ||||||||||||||||||||||||||||||||||||
{B, C, E} | ||||||||||||||||||||||||||||||||||||
Itemset | Support | |||||||||||||||||||||||||||||||||||
{A, B, C} | 1 (0.25) | |||||||||||||||||||||||||||||||||||
{A, B, E} | 1 (0.25) | |||||||||||||||||||||||||||||||||||
{A, C, E} | 1 (0.35) | |||||||||||||||||||||||||||||||||||
{B, C, E} | 2 (0.5) | |||||||||||||||||||||||||||||||||||
Itemset | Support | |||||||||||||||||||||||||||||||||||
{B, C, E} | 2 (0.5) |
如上可以看出，在海量数据的情况下，Apriori 算法的运算过程有 2 个问题：
- 需要多次扫描数据库，时间成本很高；
- 运算过程中需要产生大量的候选集，空间成本也非常高。
针对 Apriori 算法所做的改进也基本上是围绕着解决这两个问题进行的，如在扫描DB前首先进行以便事务合并和压缩，数据分区或抽样等。
Weka 里有 Apriori 算法的 Java 实现，非常值得一看。
推荐阅读：协同过滤(Collaborative Filtering)
