智能Web算法

《智能Web算法》涵盖了五类重要的智能算法：搜索、推荐、聚类、分类和分类器组合，并结合具体的案例讨论了它们在Web应用中的角色及要注意的问题。除了第1章的概要性介绍以及第7章对所有技术的整合应用外，第2～6章以代码示例的形式分别对这五类算法进行了介绍。

陈钢，计算机博士，华大科技副总裁，香港中文大学兼职助理教授。现主要从事生物数据存储，分析与可视化工作，兴趣包括机器学习，数据可视化，个人基因组等。阿稳，08年于中国科学技术大学研究生毕业后加入豆瓣算法组，从事数据与算法相关工作。五年的豆瓣工作生涯里经历了豆瓣早期几乎所有的数据与算法产品，如图书豆瓣猜、豆瓣FM。后加入阿里，参与过天猫商品推荐算法，及手机淘宝的产品与算法业务。2014年下半年创办移动外贸电商企业Akarat，继续在产品与算法结合的路上探索。

★你不需要为搭建一个智能网站而专门去修一个PhD学位，读这本书就可以了。
——Ajay Bhandari

★分析当前所知，解锁Web未来。
——Eric Swanson， AAA

前言
致谢
关于本书
1 什么是智能 Web
1.1 智能 Web 应用实例
1.2 智能应用的基本要素
1.3 什么应用会受益于智能
1.3.1 社交网络
1.3.2 Mashup
1.3.3 门户网站
1.3.4 维基
1.3.5 文件分享网站
1.3.6 网络游戏
1.4 如何构建智能应用
1.4.1 检查功能和数据
1.4.2 获取更多的数据
1.5 机器学习、数据挖掘及其他
1.6 智能应用中八个常见的误区
1.6.1 误区 1：数据是可靠的
1.6.2 误区 2：计算能马上完成
1.6.3 误区 3：不用考虑数据规模
1.6.4 误区 4：不考虑解决方案的可扩展性
1.6.5 误区 5：随处使用同样的方法
1.6.6 误区 6：总是能知道计算时间
1.6.7 误区 7：复杂的模型更好
1.6.8 误区 8：存在无偏见的模型
1.7 小结
1.8 参考资料

2 搜索
2.1 用 Lucene 实现搜索
2.1.1 理解 Lucene 代码
2.1.2 搜索的基本步骤
2.2 为什么搜索不仅仅是索引
2.3 用链接分析改进搜索结果
2.3.1 PageRank 简介
2.3.2 计算 PageRank 向量
2.3.3 alpha：网页间跳转的影响
2.3.4 理解幂方法
2.3.5 结合索引分值和 PageRank 分值
2.4 根据用户点击改进搜索结果
2.4.1 用户点击初探
2.4.2 朴素贝叶斯分类器的使用
2.4.3 整合 Lucene 索引、 PageRank 和用户点击
2.5 Word、 PDF 等无链接文档的排序
2.5.1 DocRank 算法简介
2.5.2 DocRank 的原理
2.6 大规模实现的有关问题
2.7 用户得到了想要的结果吗？精确度和查全率
2.8 总结
2.9 To Do
2.10 参考资料

3 推荐系统
3.1 一个在线音乐商店：基本概念
3.1.1 距离与相似度的概念
3.1.2 走近相似度的计算
3.1.3 什么才是最好的相似度计算公式
3.2 推荐引擎是怎么工作的
3.2.1 基于相似用户的推荐
3.2.2 基于相似条目的推荐
3.2.3 基于内容的推荐
3.3 推荐朋友、文章与新闻报道
3.3.1 MyDiggSpace.com 简介
3.3.2 发现朋友
3.3.3 DiggDelphi 的内部工作机制
3.4 像 Netflix.com 那样推荐电影
3.4.1 电影数据集的介绍及推荐器
3.4.2 数据标准化与相关系数
3.5 大规模的实现与评估
3.6 总结
3.7 To Do
3.8 参考资料

4 聚类：事物的分组
4.1 聚类的需求
4.1.1 网站中的用户组：案例研究
4.1.2 用 SQL order by 子句分组
4.1.3 用数组排序分组
4.2 聚类算法概述
4.2.1 基于分组结构的聚类算法分类
4.2.2 基于数据类型和结构的聚类算法分类
4.2.3 根据数据规模的聚类算法分类
4.3 基于链接的算法
4.3.1 树状图：基本的聚类数据结构
4.3.2 基于链接的算法概况
4.3.3 单链接算法
4.3.4 平均链接算法
4.3.5 最小生成树算法
4.4 k-means 算法
4.4.1 初识 k-means 算法
4.4.2 k-means 的内部原理
4.5 鲁棒的链接型聚类（ ROCK）
4.5.1 ROCK 简介
4.5.2 为什么 ROCK 这么强大
4.6 DBSCAN
4.6.1 基于密度的算法简介
4.6.2 DBSCAN 的原理
4.7 超大规模数据聚类
4.7.1 计算复杂性
4.7.2 高维度
4.8 总结
4.9 To Do
4.10 参考资料

5 分类：把事物放到它该在的地方
5.1 对分类的需求
5.2 分类器的概述
5.2.1 结构分类算法
5.2.2 统计分类算法
5.2.3 分类器的生命周期
5.3 邮件的自动归类与垃圾邮件过滤
5.3.1 朴素贝叶斯分类
5.3.2 基于规则的分类
5.4 用神经网络做欺诈检测
5.4.1 交易数据中关于欺诈检测的一个用例
5.4.2 神经网络概览
5.4.3 一个可用的神经网络欺诈检测器
5.4.4 神经网络欺诈检测器剖析
5.4.5 创建通用神经网络的基类
5.5 你的结果可信吗
5.6 大数据集的分类
5.7 总结
5.8 To Do
5.9 参考资料

6 分类器组合
6.1 信贷价值：分类器组合案例研究
6.1.1 数据的简要说明
6.1.2 为真实问题生成人工数据
6.2 用单分类器做信用评估
6.2.1 朴素贝叶斯的基准线
6.2.2 决策树基准线
6.2.3 神经网络的基准线
6.3 在同一个数据集中比较多个分类器
6.3.1 McNemar 检验
6.3.2 差额比例检验
6.3.3 Cochran Q 检验与 F 检验
6.4 bagging： bootstrap 聚合（ bootstrap aggregating）
6.4.1 bagging 实例
6.4.2 bagging 分类器底层细节
6.4.3 分类器集成
6.5 boosting：一种迭代提高的方法
6.5.1 boosting 分类器实例
6.5.2 boosting 分类器底层细节
6.6 总结
6.7 To Do
6.8 参考资料

7 智能技术大汇集：一个智能新闻门户
7.1 功能概览
7.2 获取并清洗内容
7.2.1 各就各位——预备——开抓！
7.2.2 搜索预备知识回顾
7.2.3 一个抓取并处理好的新闻数据集
7.3 搜索新闻
7.4 分配新闻类别
7.4.1 顺序问题
7.4.2 使用 NewsProcessor 类进行分类
7.4.3 分类器
7.4.4 分类策略：超越底层的分类
7.5 用 NewsProcessor 类创建新闻分组
7.5.1 聚类全部文章
7.5.2 在一个新闻类别中聚类文章
7.6 基于用户评分的动态内容展示
7.7 总结
7.8 To Do
7.9 参考资料

附录 A Bean Shell 简介
附录 B 网络采集
附录 C 数学知识回顾
附录 D 自然语言处理
附录 E 神经网络
索引

《智能Web算法》：
4.修改G矩阵：悬孤节点。对于悬孤节点在矩阵中对应的行，我们给其中每个元素的赋值是1／n。因为没有关于用户浏览习惯的额外信息，或是假设有足够的用户能覆盖所有的浏览习惯，这种赋值是合理的。如果有其他不同的，但同样合理的假设，整个系统会怎么工作？
假设用户遇到了悬孤节点，可以很自然地假设用户的下一个目标是搜索引擎，或是跟悬孤节点类似的网页，而不会是跟悬孤节点的内容完全无关的网站。基于这种假设，我们可以对悬孤节点的值进行调整：给搜索引擎和有相似内容的网页赋较高的值，而给其他网页赋较低的值。这会给PageRank值带来什么影响？给查询结果带来什么影响？精确度／查全率图会有什么变化？
5.修改G矩阵：跳转。在我们原来的实现中，跳转的贡献是以平均的方法分配的——所有网页的跳转概率都是（1-alpha）／n，其中，n是网页的数量。但还有很多其他的方法可以用来解决这个问题。如果选择合适，就能反映出各网页的特点；如果从用户的角度选择，就可以像用户点击一样让我们照顾到各个用户的喜好。后者正是跳转贡献也被称为个性化向量（personalizationvector）的原因。
尝试修改它，赋给某些网页较高的权重。有效果吗？这些网页的PageRank值是不是比较高？这样的实现有什么问题吗？假设我们给每个用户分配一个个性化的向量，从计算量来说这意味着什么？值得吗？可行吗？Haveliwala、Jeh、Widom，以及Richardson和Domingos的论文与此相关，给你提供了更多有关这个重要话题的信息和观点。
6.合并不同的分数。在2.4.3节中，为了能得到查询结果的最终排序，我们演示了一种结合三种不同分数的方法，但这种方法并不是唯一的。你可以根据自己的需求调整这三种分数间的关系。这里有一个想法：给三种分数引入权重的概念，然后尝试给每种分数赋予不同的权重。
如果考虑一个给定的网页或文件网络，权重系数的变化会给结果带来什么影响？尝试三组不同的权重组合，画出20个不同查询的精确度／查全率图，例如权重组合可以是（0.6，0.2，0.2）、（0.2，0.6，0.2）、（0.2，0.2，0.6）。得到了什么结果？图中的点跟等权重为（1，1，1）得到的点有什么异同？可否提出其他的公式来合理地衡量不同类型的分数的权重？
……

在如今生活的世界里，我们被淹没在大量的选择之中，因为我们生活中方方面面的事情几乎都具有不止一个的可选项。我们日常需要做出的决定，包括从汽车到家庭影院，从寻找自己的另一半到选择律师或者会计，从书籍、报纸到wiki和博客，从电影到音乐，如此等等。此外，我们每天都得忍受持续地被信息轰炸（有时还是垃圾信息）的事情。在这样“恶劣”的环境下，要是谁能给你推荐一个合适的选择，该是多么有用啊！何况，如果这个推荐还比较切合你的偏好，这种能力更是弥足珍贵。
总有那么一些公司在孜孜不倦地影响你的选择，对于怎样给你一个好的结果这件事情上，广告公司无疑显得特别用心。这些公司存在的理由就是要说服你是真的喜欢X商品或者Y服务的。但如果你对这些东西没有丝毫的兴趣，那么不单是你感觉到被骚扰，他们的努力也只不过是在浪费时间而已。传统广告的“广播”方式（比如广告牌、电视广告、电台广告）都存在着这样的问题，因为这种“广播”只是希望通过持续不断地重复相同的信息来改变你的爱好。而另一种更友好、更有效的方式是：定位你的偏爱，然后诱导你去选择符合你个人的愿望与需要的产品。这就是单纯的网络世界与基于网络的智能广告商业之间的区别所在。Google之所以闻名遐迩，也许是因为它在搜索领域方面的能力，但Google之所以富有，却是因为它们的广告系统。
在本章，我们会告诉你关于构建一个推荐引擎的所有知识，你会学习到协同过滤（collaborative filtering）与基于内容（content-based）的推荐引擎，同时还会学习到怎样优化并扩展经典的算法，以使它们能应用到更多的实际应用领域。我们会以一个在线音乐商店中的推荐问题作为引子，然后把我们的解决方案推广到其他的应用环境中。这个在线的音乐商店只是一个简单的例子，但它足够具体、详细，有助于我们理解在构建一个推荐引擎过程中所涉及的所有的基本概念。
后面我们会通过展示一些更复杂的例子来让学习更加有趣。在谨遵商业宣传的重要原则的前提下，例子的内容涵盖在线电影租赁、网络书店和普通网上商店中至关重要的各种推荐引擎。
3.1一个在线音乐商店：基本概念
假设你有一个专门提供音乐下载销售的在线商店，典型的场景是：注册用户登录到你的在线商店后，可以试听某些歌曲，如果用户喜欢某首歌曲，可以把这首歌曲放到购物车，如此循环，在完成全部的选购之后，下单购买购物车里的所有歌曲。通常来说，当用户在完成购买过程后，或者是当用户刚刚来到这个假想的应用时，我们很希望能给他们推荐更多的歌曲。因为我们拥有数以百万计的可供选择的歌曲，不计其数的歌手，数十种音乐的风格——经典、宗教、流行、重金属、乡村，以及很多其他可以进一步细分的风格，能把它们推销出去当然是一桩更好的买卖。但是，人们通常对那些他们不喜欢的音乐极为敏感，就我个人而言，如果你展示给我的都是与说唱乐（rap）相关的歌曲，那还不如雷死我，而对于另一些人来说，他们会对经典音乐表现出极不感兴趣，如此等等，不一而足。
以上例子的寓意在于，当你给一个用户展示音乐时，你希望这些内容推荐能够命中用户的偏好，同时避开用户不喜欢的内容。这个看起来有点困难？不要害怕，推荐引擎做的正是这样的事情，它会帮助你把正确的内容传递到你的用户面前。
一个推荐引擎会仔细审查一个用户以前所做出的选择，然后识别出他对某个自己还没接触过的条目的喜好程度。也就是说，它可以识别出你的用户喜欢什么类型的音乐，进而判定他会购买什么样的音乐，判定的方法是在音乐类型特征上比较他偏好的歌曲与其他歌曲的“相似度”。进而发挥一下想象力——也许我们还可以依据用户对音乐喜好的差异，帮助用户在网站上建立一个关于音乐喜好的社会网络。所以，显而易见，推荐引擎的核心功能在于计算任意两个用户或两个条目之间的相似程度，这种相似度即可用于后续的推荐。
3.1.1距离与相似度的概念
现在让我们从一些数据开始理解推荐引擎的这些概念的细节，最基本的概念是：条目、用户与评分。在推荐引擎的范畴里，相似度是一个用于比较两个条目相近程度的度量，大致上与我们习惯的用于表征两个城市相近程度的地理距离是一回事。在度量两个城市之间的距离时，我们会倾向于使用它们的经纬度坐标，而在条目或用户这个虚拟空间里，我们则使用“评分”作为这个空间的坐标来度量任意两个节点的距离。下面具体介绍这些概念，我们会从一个名为MusicUsers的评分数据库里选取三名用户，然后计算他们对数据库里所有歌曲（条目）的可能评分。
在互联网里，评分通常介于1到5分之间（含1和5分），对于选定的一些歌曲，我们令前两名用户（Frank与Constantine）给它们打4或5分（喜欢这些歌曲），同时令第三名用户（Catherine）给它们的评分为1～3分。很显然，我们会期待前两名用户彼此是相似的，并同时与第三名用户不相似。