大数据数据挖掘学习 (大数据分析与数据挖掘方法)

第一章：简介

内容：

1. 寻找事物

2. 本书结构

3. 阅读完本书后你可以做些什么?

4. 为什么数据挖掘很重要?哪些内容可以为我所用?

5. 标题里的“Numerati的古老艺术”是什么意思?

序

如果你每天都能重复做这些简单的事，你就会获得某种特别的力量。在你获得之前，这是特别的，但获得之后，就没什么大不了的了。

——鈴木 俊隆

在阅读本书之前，你可能会认为像潘多拉、亚马逊那样的推荐系统、或是恐怖分子用的数据挖掘系统，一定会非常复杂，只有拥有博士学位的人才能够了解其中的算法。你也许会认为设计出这些系统的人都是研究火箭技术的。而我撰写本书的目的之一就是希望能够揭开这些系统的神秘面纱，展示它们所使用的基本原理。虽然的确会有像Google工程师或是在国家安全局工作的天才技术人员，数据挖掘却是建立在一些基本逻辑和方法之上的，非常易于理解。在阅读本书之前，你可能会认为数据挖掘是一种让人震惊的技术，但阅读之后你会发现，其实也没什么大不了的。

上图中的日本文字“初心”，表示要始终保持一颗“初学者的心”，也就是一种开放的心态，接受各种可能性。下面这个故事你可能在哪儿听过(很有可能是来自李小龙的“龙争虎斗”)：一位教授想要寻求指引，于是来到一位智者面前，希望能得到点化。这个教授不停地说着自己毕生学到了什么，发表了多少论文等等。这时，智者问他：“喝茶吗?”然后开始向教授的杯子里倒茶，一直倒，最后溢到了桌子上、地上。“你在干什么?”教授大叫道。智者说：“我在倒茶。你的思想就像这个茶杯，已经倒满了茶，容不下任何其他东西。你必须先放空你的思想，我们才能继续往下说。”

在我看来，优秀的程序员就像是空的茶杯，他不断地探索着新的技术(noSQL、node-js等等)。普通的程序员沉浸在那些固有的想法中：C++很棒，Java不好，PHP只能用来编写网页，MySQL是数据库的唯一选择。我希望你能够以开放的心态阅读本书，从而发现一些有价值的东西。正如铃木俊隆所说：

在初学者眼中，世界充满了可能;专家眼中，世界大都已经既定。

数据挖掘简介及如何使用本书

想象我们身处一个150年前的美国小镇。大家都互相认识。商店新进了一批布料，店员注意到几块印有特殊花纹的布料肯定会受到克兰西女士的喜爱，因为他知道这位女士喜欢同类型的布料，并暗自记下如果克兰西女士下次到访，要将这块布料推荐给她。温克勒周向酒吧老板威尔逊先生提到，他正考虑要将自己的雷明顿来福枪转售。威尔逊先生将这个消息告诉了巴德巴克莱，他正想购买一把高品质的来福枪。瓦尔克兹警官和他的下属们知道李派是个麻烦人物，因为他总是喝酒，脾气不好又身强力壮。100年前的小镇生活全靠人与人之间的关系。

人们知道你的喜好，健康和婚姻状况。无论好坏，这都是一种个性化的体验。世界各自的社区都存在这种高度个性化的生活状态。

让我们穿越100年，来到1960年代。个性化的交流会有所减少，但它依然存在。一位常客走进书店时，店员会招呼道“米切纳的新书到了”，因为他知道这位常客喜欢米切纳的书。或者他会推荐高华德的《The Conscience of a Conservative》，因为他知道这位常客是位坚定的保守派。再如，来到餐厅的常客会被服务员小姐问道“照旧吗”。

即使在今天，也存在很多个性化的服务。我去附近的梅西亚咖啡店时，服务员会问“您是要一杯加量的大杯拿铁吗”，因为她知道这是我每天早上都会喝的咖啡。当我带着贵宾犬去宠物店修剪毛发时，美容师不需要问我要剪成什么造型，因为他知道我喜欢标准的德国造型。

但时过境迁，如今的生活已和百年前的小镇不一样了。大型购物超市取代了邻家的小型商店或商贩，这使得人们的选择变得有限起来。福特曾说过：“顾客们可以让轿车喷上自己喜欢的颜色，不过前提是他喜欢的是黑色。”音像店只会采购有限的音像制品，书店采购的书也是有限的。想要吃冰激凌?你可以选择香草味、巧克力味，也许草莓味也有。想要买一台洗衣机?1950年的希尔士里只有两种机型：55美元的标准款和95美元的豪华款。

欢迎来到21世纪

到了21世纪，选择范围有限的问题已经不复存在了。想听音乐?iTunes里有1100万首曲目!截止到2011年10月，他们一共售出了160亿首歌曲。还想要有更多选择?可以去Spotify，那里有超过1500万首歌曲。

想买一本书?亚马逊有200万本可供选择。

想看视频?那选择就更多了：Netflix(10万个视频)、Hulu(5万)、Amazon Prime(10万)。

想买一台笔记本电脑?在亚马逊可以搜索到3811条结果。

搜索电饭煲则可以得到1000条结果。

相信在不久的将来会有更多的商品可供选择——上十亿的在线音乐，各种各样的视频节目，以及能够用3D打印机定制的产品。

寻找相关产品

现在的问题在于——如何寻找相关的产品。在那1100万首iTunes曲目中，肯定有一部分音乐是我特别喜爱的，我该如何找到它们?我想在Netflix上观看一段视频，应该看什么呢?我想用P2P*载下**一部电影，哪部比较好呢?而且问题会越来越严重——每分钟都有数以万记的媒体数据被发布到互联网上;共享群组里每分钟都会新增100个文件;YouTube上每分钟都会有24个小时时长的新视频被上传;每小时会有180本新书发布。每天都有新的东西可以购买，要想找到自己感兴趣的产品变得越来越难。

如果你是一位音乐人——比如马来西亚的季小薇——真正的威胁并不来自于你的专辑被他人非法*载下**，而是大众根本找不到你的专辑。

那要如何寻找商品呢?

很久以前，在那个小镇里，朋友 会帮助我们寻找商品——那块布料很适合我;那本新书我很喜欢;那台迷你留声机很棒。即便在今天，我们也非常看重朋友的推荐。

我们还会请 专家 帮助我们寻找商品。过去，消费者周刊能够对所有的洗衣机(20种)和电饭煲(10种)做出评测，并进行推荐;但如今，亚马逊上有上百种电饭煲，不是一个专家就能评测完全的。过去，影评家艾伯特几乎能够对所有的电影进行评判;但如今，每年都有两万五千部电影在世界各地上映。此外，我们还能通过各种途径获取到视频节目。艾伯特也好，其他影评家也罢，是不可能对所有的电影做出评价的。

此外，我们还会通过 商品本身 来寻找。比如，我有一台用了三十年的希尔士洗衣机，所以我会再去购买一台同品牌的洗衣机;我喜欢披头士的一张专辑，所以会认为他们的另一张专辑也很有吸引力。

这些寻找商品的方式可以沿用至今，但是我们需要用电算化的手段让这些方法能够适用于21世纪的商品数量。 本书将会探索这些方法，将人们的喜恶收集起来，分析他们的购买历史，发掘社会网络(朋友)的数据价值，从而帮助我们找到相关的商品。比方说，我喜欢Phoenix乐队，那系统会使用这个乐队的一些特点——重金属、朋克、和声——来推荐其他的乐队给我，如The Strokes乐队。

不仅仅是寻找商品

数据挖掘不仅仅是用来推荐商品，或是单单给商人增加销量的。看看下面的示例。

回到一百年前的那个小镇，镇长在竞选演讲上可以针对每个选民来给出承诺：玛莎，我知道你对教育事业非常在意，我会尽一切努力去招募另一名教师到我们小镇来;约翰，你的面包房经营得如何?我会在你的商店周围建造更多的停车场的。

我父亲是联合汽车工会的成员。在选举期间，工会的代表曾来到我家，游说我父亲要投票给谁：

赛尔，你好。你的家人和孩子都好吧?……现在让我来告诉你为什么要投票给赛德勒，让这位社会学家当选市长。

赛德勒是1968至1960年密尔沃基市的市长。

随着电视的普及，这类个性化的推广信息逐渐转变为广告形式，每个人得到的信息都是一样的，其中一个著名的示例是为支持约翰逊竞选的黛西广告(一个小女孩在雏菊花田里骑着单车，此时一枚*弹核**从天而降)。现在，随着得票率相差得越来越小，以及数据挖掘技术的应用推广，个性化的竞选广告又回来了。比如你对女权主义很在意，也许就会接听到一个关于这方面信息的语音电话。

那个小镇的警官非常清楚谁是制造麻烦的人。而如今，各类威胁是隐秘起来的，恐怖主义随处可能发生。2001年10月11日，政府通过了《美国爱国者法案》(USA Patriot Act，意为提供合适的工具来截获恐怖主义的相关信息，从而保护美国公民)。这项法案的条款之一是调查者能够通过各种渠道来获得信息，比如图书馆借阅记录、旅馆出入记录、信用卡信息、公路收费站记录等等。美国政府通过和某些私营企业合作，收集我们的各项信息。比如赛新公司持有几乎所有人的记录，我们的照片、住址、座驾、收入、消费习惯、朋友等。赛新拥有的超级计算机系统能够通过数据挖掘来预测人们的行为。他们的产品有一个响亮的名字：

矩阵

数据挖掘扩展了我们的能力

贝克在他的作品《数学奇才》中写道：

想象你正在一家咖啡馆，可能十分嘈杂。一位年轻的女士坐在你的右侧，正在操作笔记本电脑。你转过头去，看着她的屏幕。她正在上网。你开始观察。

几个小时过去了，她先是阅读了一篇在线论文，然后读了三篇关于中国的文章;她浏览了周五晚上会上映的电影，还看了一篇功夫熊猫的影评;她点击了一个广告，说是能帮助用户找到自己的老同学。你在那里看着她操作，并记录下来。每过一分钟，你对她的了解就多一分。好，现在想象一下你可以同时看着1500万人的电脑屏幕，记录他们的操作。

数据挖掘的重点在于找到数据中的模式。对于少量的数据，我们非常擅长在大脑中构建模型，搜寻模式。比如，今晚我想和妻子看一部电影，我很清楚她喜欢什么类型的电影。我知道她不喜欢含有*力暴**元素的电影(这就是她不喜欢第九区的原因)，她喜欢卡夫曼的电影。我可以利用这些信息来预测她会对什么电影感兴趣。

一位欧洲的朋友远道而来，我知道她是一位素食主义者，所以我能猜到她一定不会喜欢我们当地的烤肋排。人们非常善于利用已有信息来进行预测。数据挖掘则扩展了我们的能力，让我们能够处理海量的数据，比如我上文提到的1500万人的示例。数据挖掘能让潘多拉音乐站提供个性化的音乐列表;它能让Netflix将你最感兴趣的视频推荐给你。

海量数据挖掘不是星际争霸II才有的东西

20世纪末，百万单词的数据已经是很大的量了。我于1990年代毕业(没错，我已经很老了)，有一年我作为程序员在研究新约圣经，虽然只有20万字，但仍无法完整地放入主机内存，所以只能将计算结果不断地写入磁带中，而磁带的装卸是需要经过批准的。

这次的研究成果汇集成了一本书，名为《Analytical Greek New Testament》 ，由T.福利伯格和B.福利伯格编写。我是当时的三名程序员之一，在明尼苏达大学完成的研究。

如今，在TB级别的数据量上做挖掘已经很常见了。谷歌有超过5PB的页面数据(即5000TB)。2006年，谷歌向研究者社区开放了一万亿单词量的数据集。美国国家安全局有着上万亿的电话录音数据。Acxiom，这家做数据采集的公司(信用卡消费记录、电话通信记录、医疗记录、车辆登记等)，有着全美两亿成年人的信息，共计超过1PB的数据。

图为包含了1PB数据的服务器集装箱。

《无处可藏》的作者欧哈罗曾试图帮助我们理解1PB的数据是什么样的概念，说这些数据相当于5万公里的钦定版圣经的长度。我经常往返于新墨西哥州和弗吉尼亚州，两地相距两万公里，于是我便可以想象一路上看到的全是这些书籍，数据量可见之大。

美国国会图书馆有大学20TB的文字，你可以将这些文字全部放入仅需几千美金的硬盘中。相对地，沃尔玛则有超过570TB的数据。这些数据不只是存放在那儿，而是不断有人对其进行挖掘，找到新的关联、新的模式。这就是海量数据挖掘!

本书中我们只会处理很小量的数据，这是好事，因为我们不希望自己的代码运行了一整周后发现其中有一个逻辑错误。我们会处理的最大数据量也在百兆以下，最小的数据集则只有几十行。

本书的结构

这本书按照边学边做的原则编写。与其被动地接受书中的内容，我建议读者使用书中提供的Python代码来进行实践。尝试各种算法，做一些修改，使用不同的数据集查看效果，从而真正地掌握这些知识和技术。

我会尝试在简单易懂的Python代码和其背后的算法逻辑之间找到平衡点。为了避免读者们为各种理论、数学公式、以及Python代码绞尽脑汁，我会增加图表和插画来做调剂。

谷歌研究院总监诺维格曾在他的Udacity课程《计算机程序设计》中写道：

我会向你展示和讨论我的解决方案。但需要注意的是，解决问题的方案不止一个。并不是说我的方案是 唯一的 或 最好的。我的方案不过是帮助你学习编程的一种风格和技术。如果你用另一种方式解决了问题，那会非常好。

所有的学习过程都是在你的头脑中发生的，而不是我的。所以你需要非常了解你的代码和我的代码之间的关系——你需要自己编写出答案，然后从我的代码中挑选出有用的部分来学习和借鉴。

我非常赞同这个观点

图文：用血和汗水来编程!

这本书并不是一本完整论述数据挖掘技术的教科书。市面上有一些这样的教科书，如由谭恩、 斯坦巴克、以及库马合著的《数据挖掘导论》，就很全面地讲解了数据挖掘的各种理论，及其背后的数学知识。而你正在阅读的这本书，只是帮助你快速了解数据挖掘的基础理论，并进行实践。读完本书后，你可以再找一本完整的教科书来填补空白。

这本书另一个比较实用的地方是它所提供的Python代码和数据集。我认为这可以帮助读者更快速地掌握数据挖掘的核心思想，而又不会陷得太深，事倍功半。

读完本书后你将能够做些什么事?

读完本书后，你将有能力使用Python或其它编程语言，为一个网站设计和实现一套推荐系统。例如，你在亚马逊上浏览一件商品，或者在潘多拉上聆听一首音乐，你可得到一组相关产品的列表(也就是“猜你喜欢”)。你会学到如何开发出这样一套系统。此外，这部分书提到的相关术语可以让你能够顺畅地与数据挖掘团队作沟通。

作为目标的一部分，本书还将为你揭开推荐系统的神秘面纱，包括那些恐怖分子识别系统及其他数据挖掘系统，至少你将知道这些系统是怎么运作的。

为什么这点很重要?

为什么你需要花时间来阅读本书呢?在本章的开始，我给出了很多示例来说明数据挖掘的重要性。那段文字可以转述如下：市场上有很多商品(电影、音乐、书籍、烹饪器具)，而且数量在不断增加，随之而来的问题便是如何在这么多商品中找到我们最感兴趣的——那么多电影我该看哪部?我接下来应该读哪本书?数据挖掘就是用来解决这类问题的。大多数网站都会提供查找商品的功能，除了上面提到的商品，你还会考虑该关注哪位好友;是否能够有一份报纸只刊登你感兴趣的文章?如果你是一名Web开发者，就非常需要了解数据挖掘方面的知识了。

好，现在你应该了解为什么要花时间来学习数据挖掘了，但为何要选择这本书呢?市面上有些书籍是非技术类的，描述了数据挖掘的大致情况。这些书可以快速翻阅，十分有趣，而且不贵，很适合深夜阅读(因为没有繁杂的技术细节)。这类书籍的最佳代表是贝克的《数学奇才》，我非常推荐这本书。在我往来弗吉尼亚和新墨西哥时就听的是这本书的语音版。另一个极端则是数据挖掘教学中使用的教科书。这些书籍涵盖面广，将数据挖掘的理论和实践讲解得非常透彻，所以我也推荐阅读这类书籍。至于这本书，则是用来填补这两者之间的空白的。本书的目标读者是那些喜欢编程的骇客们。

这本书应该在电脑前阅读，这样读者就可以立刻编写代码参与其中。

天呐，这是什么?这本书会包含一些数学公式，不过我会用一种简明的方式表述，相信普通的程序员都能了解，即便你已经忘记了大学中学习数学知识。

如果以上这些都不能说服你，那还有一点：这本书是免费的，你可以随意分享它。

标题中的“数学奇才的古老艺术”有什么含义?

2010年6月，我曾尝试给这本书起一个合适的标题。我喜欢有趣的标题，但很可惜我不太擅长起名字。近期，我发表了篇关于数据挖掘的论文，名为《扎入文字堆：阿拉伯文字的地域化分类》。我喜欢这个标题，不过我得承认这是我的太太帮我取的。我曾和马克肖恩合著了一篇论文，名为《情绪与模式：从理论到争辩》，这个标题也是我的搭档取的。总之，六月时我取的那些标题很难一眼看出这本书讲的是什么，所以我最后用了《面向程序员的数据挖掘指南》作为标题的一部分，因为这个标题和本书的内容非常契合——这本书是提供给正在从事编程工作的人员阅读的。也许你会疑惑子标题究竟是什么意思：

数学奇才(Numerati)是贝克自己创造的一个词语。如今，我们每个人无时无刻不在创造着新的数据，信用卡购物记录、推特、格瓦拉上的博客、Foursquare上的签到、手机通话记录、电子邮件、文字短信等。

当你一早醒来，“矩阵”就知道你会乘坐雾谷站7:10的地铁，并于7:32在西站下车;矩阵知道7:45分你会去第五大街的星巴克买上一杯大杯拿铁和一份蓝莓饼;8:05分，你用格瓦拉在上班地点签到;9:35分，你在亚马逊上购买了一套瘦身教程DVD和一副门上单杠;你在Golden Falafel吃的午餐。

贝克在书中这样写道：

只有那些数学家、计算机科学家、以及工程师们才能从这些庞大的数据集中获得有用的信息。这些数学奇才会从这些数据中了解到什么?首先，他们能够准确地定位到我们。比如你是纽约北部市郊的一个潜在的SUV客户，或是一个经常去教堂做礼拜的人，或是阿尔伯克基市的一名反堕胎的民主*党**人士;也许你是一个即将被调任到海得拉巴市的一名Java工程师，或是一个热爱爵士乐的人;你是射手座的，喜欢喝勤地酒，想在乡野间漫步，最后在斯德哥尔摩的篝火旁酣睡;更夸张的，也许你腰绑*弹炸**，正乘上一部公交车。无论你是谁，处在茫茫人海中，那些公司或政府机构都能掌握你的行踪。

你可能猜到了，起这个标题是因为我喜欢贝克的这段描述。

第二章：推荐系统入门

内容：

• 推荐系统工作原理

• 社会化协同过滤工作原理

• 如何找到相似物品

• 曼哈顿距离

• 欧几里得距离

• 闵可夫斯基距离

• 皮尔逊相关系数

• 余弦相似度

• 使用Python实现K最邻近算法

• 图书漂流站(BookCrossing)数据集

你喜欢的东西我也喜欢

我们将从推荐系统开始，开启数据挖掘之旅。推荐系统无处不在，如亚马逊网站的“看过这件商品的顾客还购买过”板块：

last.fm上对音乐和演唱会的推荐(相似歌手)：

在亚马逊的例子里，它用了两个元素来进行推荐：一是我浏览了里维斯翻译的《法华经》一书;二是其他浏览过该书的顾客还浏览过的译作。

本章我们讲述的推荐方法称为协同过滤。顾名思义，这个方法是利用他人的喜好来进行推荐，也就是说，是大家一起产生的推荐。他的工作原理是这样的：如果要推荐一本书给你，我会在网站上查找一个和你类似的用户，然后将他喜欢的书籍推荐给你——比如巴奇加卢比的《发条女孩》。

如何找到相似的用户?

所以首先要做的工作是找到相似的用户。这里用最简单的二维模型来描述。假设用户会在网站用五颗星来评价一本书——没有星表示书写得很糟，五颗星表示很好。因为我们用的是二维模型，所以仅对两本书进行评价：史蒂芬森的《雪崩》(纵轴)和拉尔森的《龙纹身的女孩》(横轴)。

首先，下表显示有三位用户对这两本书做了评价：

现在我想为神秘的X先生推荐一本书，他给《雪崩》打了四星，《龙纹身的女孩》两星。第一个任务是找出哪个用户和他最为相似。我们用距离来表示。

曼哈顿距离

最简单的距离计算方式是曼哈顿距离。在二维模型中，每个人都可以用(x, y)的点来表示，这里我用下标来表示不同的人，(x1, y1)表示艾米，(x2, y2)表示那位神秘的X先生，那么他们之间的曼哈顿距离就是：

也就是x之差的绝对值加上y之差的绝对值，这样他们的距离就是4。

完整的计算结果如下：

艾米的距离最近，在她的浏览历史中可以看到她曾给巴奇加卢比的《发条女孩》打过五星，于是我们就可以把这本书推荐给X先生。

欧几里得距离

曼哈顿距离的优点之一是计算速度快，对于Facebook这样需要计算百万用户之间的相似度时就非常有利。

勾股定理

也许你还隐约记得勾股定理。另一种计算距离的方式就是看两点之间的直线距离：

利用勾股定理，我们可以如下计算距离：

这条斜线就是欧几里得距离，公式是：

回顾一下，这里的x1表示用户1喜欢《龙纹身》的程度，x2是用户2喜欢这本书的程度;y1则是用户1喜欢《雪崩》的程度，y2是用户2喜欢这本书的程度。

艾米给《龙纹身》和《雪崩》都打了五颗星，神秘的X先生分别打了两星和四星，这样他们之间的欧几里得距离就是：

以下是全部用户的计算结果：

N维模型

刚才我们仅仅对两本书进行评价(二维模型)，下面让我们扩展一下，尝试更复杂的模型。假设我们现在要为一个在线音乐网站的用户推荐乐队。用户可以用1至5星来评价一个乐队，其中包含半星(如2.5星)。下表展示了8位用户对8支乐队的评价：

表中的短横表示这位用户没有给这支乐队打分。我们在计算两个用户的距离时，只采用他们都评价过的乐队，比如要计算Angelica和Bill的距离，我们只会用到5支乐队。这两个用户的曼哈顿距离为：

最后距离即是上方数据的加和：(1.5 + 1.5 + 3 + 2 + 1)。

计算欧几里得距离的方法也是类似的，我们也只取双方都评价过的乐队。

用公式来描述即：

掌握了吗? 那就试试计算其他几个用户之间的距离吧。

有个瑕疵

当我们计算Hailey和Veronica的距离时会发现一个问题：他们共同评价的乐队只有两支(Norah Jones和The Strokes)，而Hailey和Jordyn共同评价了五支乐队，这似乎会影响我们的计算结果，因为Hailey和Veronica之间是二维的，而Haily和Veronica之间是五维的。曼哈顿距离和欧几里得距离在数据完整的情况下效果最好。如何处理缺失数据，这在研究领域仍是一个活跃的话题。本书的后续内容会进行一些讨论，这里先不展开。现在，让我们开始构建一个推荐系统吧。

推广：闵可夫斯基距离

我们可以将曼哈顿距离和欧几里得距离归纳成一个公式，这个公式称为闵可夫斯基距离：

其中：

r = 1 该公式即曼哈顿距离

r = 2 该公式即欧几里得距离

r = ∞ 极大距离

当你在书中看到这些数学公式，你可以选择快速略过它，继续读下面的文字，过去我就是这样;你也可以停下来，好好分析一下这些公式，会发现其实它们并不难理解。比如上面的公式，当r = 1时，可以简化成如下形式：

仍用上文的音乐站点为例，x和y分别表示两个用户，d(x, y)表示他们之间的距离，n表示他们共同评价过的乐队数量，我们之前已经做过计算：

其中Difference一栏表示两者评分之差的绝对值，加起来等于9，也就是他们之间的距离。

当r = 2时，我们得到欧几里得距离的计算公式：

提前预告一下：r值越大，单个维度的差值大小会对整体距离有更大的影响。

使用Python代码来表示数据(终于要开始编程了)

在Python中，我们可以用多种方式来描述上表中的数据，这里我选择Python的字典类型(或者称为关联数组、哈希表)。

注：本书的所有代码可以在这里找到。

我们可以用以下方式来获取某个用户的评分：

计算曼哈顿距离

我们可以做一下测试：

下面我们编写一个函数来找出距离最近的用户(其实该函数会返回一个用户列表，按距离排序)：

简单测试一下：

最后，我们结合以上内容来进行推荐。假设我想为Hailey做推荐，这里我找到了离他距离最近的用户Veronica。然后，我会找到出Veronica评价过但Hailey没有评价的乐队，并假设Hailey对这些陌生乐队的评价会和Veronica相近。比如，Hailey没有评价过Phoenix乐队，而Veronica对这个乐队打出了4分，所以我们认为Hailey也会喜欢这支乐队。下面的函数就实现了这一逻辑：

下面我们就可以用它来为Hailey做推荐了：

运行结果和我们的预期相符。我们看可以看到，和Hailey距离最近的用户是Veronica，Veronica对Phoenix乐队打了4分。我们再试试其他人：

我们可以猜想Chan会喜欢The Strokes乐队，而Sam不会太欣赏Deadmau5。

对于Angelica，我们得到了空的返回值，也就是说我们无法对其进行推荐。让我们看看是哪里有问题：

Angelica最相似的用户是Veronica，让我们回头看看数据：

我们可以看到，Veronica评价过的乐队，Angelica也都评价过了，所以我们没有推荐。

之后，我们会讨论如何解决这一问题。

作业：实现一个计算闵可夫斯基距离的函数，并在计算用户距离时使用它。

用户的问题

让我们仔细看看用户对乐队的评分，可以发现每个用户的打分标准非常不同：

1. Bill没有打出极端的分数，都在2至4分之间;

2. Jordyn似乎喜欢所有的乐队，打分都在4至5之间;

3. Hailey是一个有趣的人，他的分数不是1就是4。

那么，如何比较这些用户呢?比如Hailey的4分相当于Jordan的4分还是5分呢?我觉得更接近5分。这样一来就会影响到推荐系统的准确性了。

左：我非常喜欢Broken Bells乐队，所以我给他们打4分!

右：Broken Bells乐队还可以，我打4分。

皮尔逊相关系数

解决方法之一是使用皮尔逊相关系数。简单起见，我们先看下面的数据(和之前的数据不同)：

这种现象在数据挖掘领域称为“分数膨胀”。Clara最低给了4分——她所有的打分都在4至5分之间。我们将它绘制成图表：

一条直线——完全吻合!!!

直线即表示Clara和Robert的偏好完全一致。他们都认为Phoenix是最好的乐队，然后是Blues Traveler、Norah Jones。如果Clara和Robert的意见不一致，那么落在直线上的点就越少。

意见基本一致的情形

意见不太一致的情形

所以从图表上理解，意见相一致表现为一条直线。皮尔逊相关系数用于衡量两个变量之间的相关性(这里的两个变量指的是Clara和Robert)，它的值在-1至1之间，1表示完全吻合，-1表示完全相悖。从直观上理解，最开始的那条直线皮尔逊相关系数为1，第二张是0.91，第三张是0.81。因此我们利用这一点来找到相似的用户。

皮尔逊相关系数的计算公式是：

这里我说说自己的经历。我大学读的是现代音乐艺术，课程包括芭蕾、现代舞、服装设计等，没有任何数学课程。我高中读的是男子学校，学习了管道工程和汽车维修，只懂得很基础的数学知识。不知是因为我的学科背景，还是习惯于用直觉来思考，当我遇到这样的数学公式时会习惯性地跳过，继续读下面的文字。如果你和我一样，我强烈建议你与这种惰性抗争，试着去理解这些公式。它们虽然看起来很复杂，但还是能够被常人所理解的。

上面的公式除了看起来比较复杂，另一个问题是要获得计算结果必须对数据做多次遍历。好在我们有另外一个公式，能够计算皮尔逊相关系数的近似值：

这个公式虽然看起来更加复杂，而且其计算结果会不太稳定，有一定误差存在，但它最大的优点是，用代码实现的时候可以只遍历一次数据，我们会在下文看到。首先，我们将这个公式做一个分解，计算下面这个表达式的值：

对于Clara和Robert，我们可以得到：

很简单把?下面我们计算这个公式：

Clara的总评分是22.5， Robert是15，他们评价了5支乐队，因此：

所以，那个巨型公式的分子就是70 – 67.5 = 2.5。

下面我们来看分母：

首先：

我们已经计算过Clara的总评分是22.5，它的平方是506.25，除以乐队的数量5，得到101.25。综合得到：

对于Robert，我们用同样的方法计算：

最后得到：

因此，1表示Clara和Robert的偏好完全吻合。

先休息一下吧

计算皮尔逊相关系数的代码

测试一下：

最后一个公式：余弦相似度

这里我将奉上最后一个公式：余弦相似度。它在文本挖掘中应用得较多，在协同过滤中也会使用到。为了演示如何使用该公式，我们换一个示例。这里记录了每个用户*放播**歌曲的次数，我们用这些数据进行推荐：

简单扫一眼上面的数据(或者用之前讲过的距离计算公式)，我们可以发现Ann的偏好和Sally更为相似。

问题在哪儿?

我在iTunes上有大约4000首歌曲，下面是我最常听的音乐：

可以看到，Moonlight Sonata这首歌我*放播**了25次，但很有可能你一次都没有听过。事实上，上面列出的这些歌曲可能你一首都没听过。此外，iTunes上有1500万首音乐，而我只听过4000首。所以说单个用户的数据是 稀疏 的，因为非零值较总体要少得多。当我们用1500万首歌曲来比较两个用户时，很有可能他们之间没有任何交集，这样一来就无从计算他们之间的距离了。

类似的情况是在计算两篇文章的相似度时。比如说我们想找一本和《The Space Pioneers》相类似的书，方法之一是利用单词出现的频率，即统计每个单词在书中出现的次数占全书单词的比例，如“the”出现频率为6.13%，“Tom” 0.89%，“space” 0.25%。我们可以用这些数据来寻找一本相近的书。但是，这里同样有数据的稀疏性问题。《The Space Pioneers》中有6629个不同的单词，但英语语言中有超过100万个单词，这样一来非零值就很稀少了，也就不能计算两本书之间的距离。

余弦相似度的计算中会略过这些非零值。它的计算公式是：

其中，“·”号表示数量积。“||x||”表示向量x的模，计算公式是：

我们用上文中“偏好完全一致”的示例：

所以两个向量为：

它们的模是：

数量积的计算：

因此余弦相似度是：

余弦相似度的范围从1到-1，1表示完全匹配，-1表示完全相悖。所以0.935表示匹配度很高。

作业：尝试计算Angelica和Veronica的余弦相似度

应该使用哪种相似度?

我们整本书都会探索这个问题，以下是一些提示：

如果数据存在“分数膨胀”问题，就使用皮尔逊相关系数。

如果数据比较“密集”，变量之间基本都存在公有值，且这些距离数据是非常重要的，那就使用欧几里得或曼哈顿距离。

如果数据是稀疏的，则使用余弦相似度。

所以，如果数据是密集的，曼哈顿距离和欧几里得距离都是适用的。那么稀疏的数据可以使用吗?我们来看一个也和音乐有关的示例：假设有三个人，每人都给100首音乐评过分。

Jake(左)：乡村音乐的忠实听众。

Linda和Eric(右)：我们爱六十年代的摇滚乐!

Linda和Eric喜欢相同的音乐，他们的评分列表中有20首相同的的歌曲，且评分均值相差不到0.5!所以他们之间的曼哈顿距离为20 x 0.5 = 10，欧几里得距离则为：

Linda和Jake只共同评分了一首歌曲：Chris Cagle的 What a Beautiful Day 。Linda打了3分，Jake打了5分，所以他们之间的曼哈顿距离为2，欧几里得距离为：

所以不管是曼哈顿距离还是欧几里得距离，Jake都要比Eric离Linda近，这不符合实际情况。

嘿，我想到一个办法。人们给音乐打分是从1到5分，那些没有打分的音乐就统一给0分好了，这样就能解决数据稀疏的问题了!

想法不错，但是这样做也不行。为了解释这一问题，我们再引入两个人到例子里来：Cooper和Kelsey。他们和Jake都有着非常相似的音乐偏好，其中Jake在我们网站上评价了25首歌曲。

Cooper评价了26首歌曲，其中25首和Jake是一样的。他们对每首歌曲的评价差值只有0.25!

Kelsey在我们网站上评价了150首歌曲，其中25首和Jake相同。和Cooper一样，她和Jake之间的评价差值也只有0.25!

所以我们从直觉上看Cooper和Keylsey离Jake的距离应该相似。但是，当我们计算他们之间的曼哈顿距离和欧几里得距离时(代入0值)，会发现Cooper要比Keylsey离Jake近得多。

为什么呢?

我们来看下面的数据：

从4、5、6这三首歌来看，两人离Jake的距离是相同的，但计算出的曼哈顿距离却不这么显示：

问题就在于数据中的0值对结果的影响很大，所以用0代替空值的方法并不比原来的方程好。还有一种变通的方式是计算“平均值”——将两人共同评价过的歌曲分数除以歌曲数量。

总之，曼哈顿距离和欧几里得距离在数据完整的情况下会运作得非常好，如果数据比较稀疏，则要考虑使用余弦距离。

古怪的现象

假设我们要为Amy推荐乐队，她喜欢Phoenix、Passion Pit、以及Vampire Weekend。和她最相似的用户是Bob，他也喜欢这三支乐队。他的父亲为Walter Ostanek乐队演奏手风琴，所以受此影响，他给了这支乐队5星评价。按照我们现在的推荐逻辑，我们会将这支乐队推荐给Amy，但有可能她并不喜欢。

或者试想一下，Billy Bob Olivera教授喜欢阅读数据挖掘方面的书籍以及科幻小说，他最邻近的用户是我，因为我也喜欢这两种书。然而，我又是一个贵宾犬的爱好者，所以给《贵宾犬的隐秘生活》这本书打了很高的分。这样一来，现有的推荐方法会将这本书介绍给Olivera教授。

问题就在于我们只依靠最相似的 一个 用户来做推荐，如果这个用户有些特殊的偏好，就会直接反映在推荐内容里。解决方法之一是找寻多个相似的用户，这里就要用到K最邻近算法了。

K最邻近算法

在协同过滤中可以使用K最邻近算法来找出K个最相似的用户，以此作为推荐的基础。不同的应用有不同的K值，需要做一些实验来得出。以下给到读者一个基本的思路。

假设我要为Ann做推荐，并令K=3。使用皮尔逊相关系数得到的结果是：

这三个人都会对推荐结果有所贡献，问题在于我们如何确定他们的比重呢?我们直接用相关系数的比重来描述，Sally的比重是0.8/2=40%，Eric是0.7/2=35%，Amanda则是25%：

假设他们三人对Grey Wardens的评分以及加权后的结果如下：

最后计算得到的分数为：

Python推荐模块

我将本章学到的内容都汇集成了一个Python类，虽然代码有些长，我还是贴在了这里：

运行示例

首先构建一个推荐类，然后获取推荐结果：

现在让我们使用一个更为真实的数据集。Cai-Nicolas Zeigler从图书漂流站收集了超过100万条评价数据——278,858位用户为271,379本书打了分。这份数据(匿名)可以从这个地址获得，有SQL和CSV两种格式。由于特殊符号的关系，这些数据无法直接加载到Python里。我做了一些清洗，可以从这里*载下**。

CSV文件包含了三张表：

• 用户表，包括用户ID、位置、年龄等信息。其中用户的姓名已经隐去;

• 书籍表，包括ISBN号、标题、作者、出版日期、出版社等;

• 评分表，包括用户ID、书籍ISBN号、以及评分(0-10分)。

上文Python代码中的loadBookDB方法可以加载这些数据，用法如下：

注意 由于数据集比较大，大约需要几十秒的时间加载和查询。

项目实践

只有运行调试过书中的代码后才能真正掌握这些方法，以下是一些实践建议：

• 实现一个计算曼哈顿距离和欧几里得距离的方法;

• 本书的网站上有一个包含25部电影评价的数据集，实现一个推荐算法。

第三章：隐式评价和基于物品的过滤算法

本章会从用户的评价类型开始讨论，包括显式评价(赞一下、踩一脚、五星评价等等)和隐式评价(比如在亚马逊上购买了MP3，我们可以认为他喜欢这个产品)。

内容：

• 显式评价

• 隐式评价

• 哪种评价方式更准确?

• 基于用户的协同过滤

• 基于物品的协同过滤

• 修正的余弦相似度

• Slope One算法

• Slope One的Python实现

• MovieLens数据

第二章中我们学习了协同过滤和推荐系统的基本知识，其中讲述的算法是比较通用的，可以适用于多种数据集。用户使用5到10分的标尺来对不同的物品进行打分，通过计算得到相似的用户。但是，也有迹象表明用户通常不会有效地使用这种度量方式，而更倾向于给出极好或极差的评价，这种做法会使推荐结果变得不可用。这一章我们将继续探讨这个问题，尝试使用高效的方法给出更精确的推荐。

显式评价

用户的评价类型可以分为显式评价和隐式评价。显式评价指的是用户明确地给出对物品的评价，最常见的例子是Pandora和YouTube上的“喜欢”和“不喜欢”按钮：

以及亚马逊的星级系统：

隐式评价

所谓隐式评价，就是我们不让用户明确给出对物品的评价，而是通过观察他们的行为来获得偏好信息。示例之一是记录用户在纽约时报网上的点击记录。

经过几周的观察之后，我们就可以为用户刻画出一个合理的模型了——她不喜欢体育新闻，但关注科技新闻;如果用户连续看了两篇文章：《快速减肥方法》和《不反弹的减肥方式》，那她很可能正在减肥;如果她点击了iPhone的广告，就表明她或许对这款产品感兴趣。

试想一下，如果我们记录了用户在亚马逊上的操作记录，可以得出一些什么结论。你的首页上可能有这样的内容：

在这个示例中，亚马逊记录了用户的点击操作，因此它会知道浏览了Jupter Travel这本书的用户还浏览了Long Way Round这部DVD，其详细记录了演员伊万环球骑行的旅程。因此，亚马逊就用这些信息来做出“看过还看过”的推荐。

另一种隐式评价是用户的实际购买记录，亚马逊也会用这些记录来进行“买过还买过”、以及“看过此商品的用户还买过”的推荐。

可能你会觉得“买过还买过”应该会给出一些不合理的推荐结果，但事实上它运作得很好。

再来看看iTunes上如何记录用户的行为：

首先，我将一首歌添加到了iTunes，这至少表明我对这首歌是感兴趣的。然后是*放播**次数，上表中我听了Anchor这首歌52次，说明我很喜欢;而那些只听了一次的歌曲则是我不喜欢的。

头脑风暴

你觉得让用户对物品进行显式评价会更精确吗?还是说通过观察用户对物品的行为(是否购买或*放播**次数)才更为准确?

显式评价：我叫吉姆，是一个素食主义者。我爱喝葡萄酒，喜欢在森林中漫步，在篝火旁阅读Chekov的书，喜欢观看法国电影，周六会去艺术博物馆逛逛，我还喜欢舒曼的钢琴曲。

隐式评价：我们在吉姆的口袋里发现了12打美国蓝带啤酒的收银条，以及冰激淋、披萨和甜甜圈的收银条。还有一些租借DVD的回执，有复仇者联盟、生化危机、拳霸等。

显式评价的问题

问题1：人们很懒，不愿评价物品

首先，用户很可能不会对物品做出评价。相信各位读者已经在亚马逊上购买了很多商品，就拿我来说，仅过去一个月我就在那里购买了直升机模型、1TB硬盘、USB-SATA转接头、维他命药片、两本Kindle电子书、四本纸质书。一共十件商品，我评价了几件?零件!相信很多人和我是一样的——我们不评价商品，我们只管买。

我喜欢旅行和登山，所以购买了很多登山杖。亚马逊上一些价格实惠的登山杖很耐用。去年我到奥斯汀市参加音乐会，途中碰坏了膝盖，于是到REI专营店买了一根价格昂贵的登山杖。不过这根杖居然在我逛公园时用断了!这根昂贵的登山杖还没有买的10美元的来得结实。放假时，我打算给这件商品写一篇评价，告诫其他购买者。结果呢?我没有写，因为我太懒了。

问题2：人们会撒谎，或存有偏见

我们假设有人不像前面说得那么懒，确实去给物品做出评价了，但他有可能会撒谎。这种情况在前文中已经有提到了。用户可能会直接撒谎，给出不正确的评价;或是不置可否，抱有偏见。Ben和他的朋友们去看了一场泰国出的电影，Ben认为这部电影很糟糕，而其他人却觉得很好看，在餐厅里欢快地谈论着。于是，Ben在评价电影时很有可能会抬高它的分数，这样才能表现得合群。

问题3：人们不会更新他们的评论

假设我去亚马逊评价了商品——那个1TB的硬盘速度很快也很静音;直升机模型操作起来也很简便，不容易摔坏。所以这两件商品我都给出了5星的评价。但一个月后，那块硬盘坏了，我丢失了所有的电影和音乐;那台直升机模型也突然不再工作了，让我非常扫兴。但是，我不太会返回亚马逊网站对这两件商品的评价做出改动，这样人们依旧认为我是非常喜欢这两件商品的。

再举一个示例，玛丽很乐意在亚马逊上对商品做评价。她十年前给一些儿童类书籍打了很高的分数，近些年又对一些摇滚乐队的专辑给出了评价。从近年的评价看，她和另一位用户珍妮很相似。但是，如果我们把那些儿童书籍推荐给珍妮就显得不合适了。这个例子和上面的有些不同，但的确是个问题。

头脑风暴

你觉得隐式评价会有什么问题?提示：可以回忆一下你在亚马逊的购买记录。

上文中我给出了一个近期在亚马逊上的购物列表，其中有两样是我买来送给其他人的。为什么这会是一个问题?我再举一些其他的例子。我给我的孩子买了一个壶铃和一本关于健身的书籍;我给我的太太买了一个边境牧羊犬的毛绒玩具，因为我家那只14岁大的狗去世了。通过隐式评价来进行建模，会让你觉得我喜欢壶铃和毛绒玩具。亚马逊的购买记录无法区分这件商品是我买来自己用的还是送人的。贝克也曾给出了相似的例子：

对于计算机来说，能够将白色连衣裙和婴儿潮出生的女性关联起来是任务的第一步，然后再对这些用户建立模型。假设我的太太在商店里购买了几件商品：内衣、裤子、连衣裙、皮带等，这些商品都很符合婴儿潮的特点。离开时她想起要为自己16岁大的外甥女买一件生日礼物。由于我们上次看到她时她穿着一件黑色的T恤，上面写满了文字，并自称是一名哥特摇滚妞。于是，我的太太就去买了一根项圈准备送给她。

可以想象，如果我们要为这位用户构建模型，那这根项圈的存在就很有问题了。

再比如一对情侣使用的是同一个Netflix账号。男方喜欢各种*破爆**场面，女方则喜欢知性类型的电影。如果我们从浏览历史进行挖掘，则会发现一个人会喜欢两种截然不同的影片类型。

前面说到我买了一些书给别人，所以单从购买历史看，同一本书我会购买很多次。这样有两种可能：一是我的书不小心丢了，二是我得了老年痴呆，不记得自己曾读过这些书。而事实是我非常喜欢这些书，因此多买了几本作为礼物来送给别人。所以说，用户的购买记录还是非常值得深究的。

头脑风暴

我们可以收集到哪些隐式评价呢? 网页方面：页面点击、停留时间、重复访问次数、引用率、Hulu上观看视频的次数; 音乐*放播**器：*放播**的曲目、跳过的曲目、*放播**次数; 这些只是一小部分!

值得注意的是，我们在第二章中学习的算法对于显式评价和隐式评价都是适用的。

什么会阻碍你成功?

设想你有一个成熟的在线音乐网站，在构建推荐系统时会遇到什么问题呢?

假设你有一百万个用户，每次推荐需要计算一百万个距离数据。如果我们想在一秒钟里进行多次推荐，那计算量将是巨大的。除非增加服务器的数量，否则系统会变得越来越慢。说得专业一点，通过邻域进行计算的推荐系统，延迟会变得越来越严重。还好，这是有解决办法的。

基于用户的协同过滤

目前为止我们描述的都是基于用户的协同过滤算法。我们将一个用户和其他所有用户进行对比，找到相似的人。这种算法有两个弊端：

1. 扩展性 上文已经提到，随着用户数量的增加，其计算量也会增加。这种算法在只有几千个用户的情况下能够工作得很好，但达到一百万个用户时就会出现瓶颈。

2. 稀疏性 大多数推荐系统中，物品的数量要远大于用户的数量，因此用户仅仅对一小部分物品进行了评价，这就造成了数据的稀疏性。比如亚马逊有上百万本书，但用户只评论了很少一部分，于是就很难找到两个相似的用户了。

鉴于以上两个局限性，我们不妨考察一下基于物品的协同过滤算法。

基于物品的协同过滤

假设我们有一种算法可以计算出两件物品之间的相似度，比如Phoenix专辑和Manners很相似。如果一个用户给Phoenix打了很高的分数，我们就可以向他推荐Manners了。需要注意这两种算法的区别：基于用户的协同过滤是通过计算用户之间的距离找出最相似的用户，并将他评价过的物品推荐给目标用户;而基于物品的协同过滤则是找出最相似的物品，再结合用户的评价来给出推荐结果。

能否举个例子?

我们的音乐站点有m个用户和n个乐队，用户会对乐队做出评价，如下表所示：

我们要计算Phoenix和Passion Pit之间的相似度，可以使用蓝色方框中的数据，也就是同时对这两件商品都有过评价的用户。在基于用户的算法中，我们计算的是行与行之间的相似度，而在基于物品的算法中，我们计算的是列与列之间的。

基于用户的协同过滤又称为内存型协同过滤，因为我们需要将所有的评价数据都保存在内存中来进行推荐。

基于物品的协同过滤也称为基于模型的协同过滤，因为我们不需要保存所有的评价数据，而是通过构建一个物品相似度模型来做推荐。

修正的余弦相似度

我们使用余弦相似度来计算两个物品的距离。我们在第二章中提过“分数膨胀”现象，因此我们会从用户的评价中减去他所有评价的均值，这就是修正的余弦相似度。

左：我喜欢Phoenix乐队，因此给他们打了5分。我不喜欢Passion，所以给了3分。

右：Phoenix很棒，我给4分。Passion Pit太糟糕了，必须给0分!

U表示同时评价过物品i和j的用户集合

这个公式来自于一篇影响深远的论文《基于物品的协同过滤算法》，由Badrul Sarwar等人合著。

上式表示将用户u对物品i的评价值减去用户u对所有物品的评价均值，从而得到修正后的评分。s(i,j)表示物品i和j的相似度，分子表示将同时评价过物品i和j的用户的修正评分相乘并求和，分母则是对所有的物品的修正评分做一些汇总处理。

为了更好地演示修正的余弦相似度，我们举一个例子。下表是五个学生对五位歌手的评价：

首先，我们计算出每个用户的平均评分，这很简单：

下面，我们计算歌手之间的相似度，从Kacey Musgraves和Imagine Dragons开始。上图中我已经标出了同时评价过这两个歌手的用户，代入到公式中：

所以这两个歌手之间的修正余弦相似度为0.5260，我计算了其他一些歌手之间的相似度，其余的请读者们完成：

计算修正余弦相似度的Python代码

这个矩阵看起来不错，那下面该如何使用它来做预测呢?比如我想知道David有多喜欢Kacey Musgraves?

p(u,i)表示我们会来预测用户u对物品i的评分，所以p(David, Kacey Musgraves)就表示我们将预测David会给Kacey打多少分。

N是一个物品的集合，有如下特性：用户u对集合中的物品打过分;物品i和集合中的物品有相似度数据(即上文中的矩阵)。

Si,N表示物品i和N的相似度，Ru,N表示用户u对物品N的评分。

为了让公式的计算效果更佳，对物品的评价分值最好介于-1和1之间。由于我们的评分系统是1至5星，所以需要使用一些运算将其转换到-1至1之间。

我们的音乐评分系统是5分制，MaxR表示评分系统中的最高分(这里是5)，MinR为最低分(这里是1)，Ru,N是用户u对物品N的评分，NRu,N则表示修正后的评分(即范围在-1和1之间)。

若已知NRu,N，求解Ru,N的公式为：

比如一位用户给Fall Out Boy打了2分，那修正后的评分为：

反过来则是：

有了这个基础后，下面就让我们看看如何求解上文中的p(David, Kacey Musgraves)。

首先我们要修正David对各个物品的评分：

然后结合物品相似度矩阵，代入公式：

所以，我们预测出David对Kacey Musgraves的评分是0.753，将其转换到5星评价体系中：

最终的预测结果是4.506分。

回顾

修正的余弦相似度是一种基于模型的协同过滤算法。我们前面提过，这种算法的优势之一是扩展性好，对于大数据量而言，运算速度快、占用内存少。

用户的评价标准是不同的，比如喜欢一个歌手时有些人会打4分，有些打5分;不喜欢时有人会打3分，有些则会只给1分。修正的余弦相似度计算时会将用户对物品的评分减去用户所有评分的均值，从而解决这个问题。

Slope One算法

还有一种比较流行的基于物品的协同过滤算法，名为Slope One，它最大的优势是简单，因此易于实现。Slope One算法是在一篇名为《Slope One：基于在线评分系统的协同过滤算法》的论文中提出的，由Lemire和Machlachlan合著。这篇论文非常值得一读。

我们用一个简单的例子来了解这个算法。假设Amy给PSY打了3分，Whitney Houston打了4分;Ben给PSY打了4分。我们要预测Ben会给Whitney Houston打几分。用表格来描述这个问题即：

我们可以用以下逻辑来预测Ben对Whitney Houston的评分：由于Amy给Whitney Houston打的分数要比PSY的高一分，所以我们预测Ben也会给高一分，即给到5分。

其实还有其他形式的Slope One算法，比如加权的Slope One。我们说过Slope One的优势之一是简单，下面说的加权的Slope One看起来会有一些复杂，但是只要耐心地看下去，事情就会变得很清晰了。

你可以将Slope One分为两个步骤：首先需要计算出两两物品之间的差值(可以在夜间批量计算)。在上文的例子中，这个步骤就是得出Whitney Houston要比PSY高一分。第二步则是进行预测，比如一个新用户Ben来到了我们网站，他从未听过Whitney Houston的歌曲，我们想要预测他是否喜欢这位歌手。通过利用他评价过的歌手以及我们计算好的歌手之间的评分差值，就可以进行预测了。

第一步：计算差值

我们先为上述例子增加一些数据：

计算物品之间差异的公式是：

其中，card(S)表示S中有多少个元素;X表示所有评分值的集合;card(Sj,i(X))则表示同时评价过物品j和i的用户数。我们来考察PSY和Taylor Swift之间的差值，card(Sj,i(X))的值是2——因为有两个用户(Amy和Ben)同时对PSY和Taylor Swift打过分。分子uj-ui表示用户对j的评分减去对i的评分，代入公式得：

所以PSY和Taylor Swift的差异是2，即用户们给Taylor Swift的评分比PSY要平均高出两分。那Taylor Swift和PSY的差异呢?

作业：计算其他物品之间的差值

头脑风暴

试想我们的音乐站点有100万个用户对20万个歌手做评价。如果有一个新进的用户对10个歌手做了评价，我们是否需要重新计算20万×20万的差异数据，或是有其他更简单的方法?

答案是你不需要计算整个数据集，这正是Slope One的美妙之处。对于两个物品，我们只需记录同时评价过这对物品的用户数就可以了。比如说Taylor Swift和PSY的差值是2，是根据9位用户的评价计算的。当有一个新用户对Taylor Swift打了5分，PSY打了1分时，更新后的差值为：

第二步：使用加权的Slope One算法进行预测

好，现在我们有了物品之间的差异值，下面就用它来进行预测。这里我们将使用加权的Slope One算法来进行预测，用PWS1来表示，公式为：

其中：

PWS1(u)j表示我们将预测用户u对物品i的评分。比如PWS1(Ben)Whitney Houston表示Ben对Whitney Houston的预测评分。下面就让我们来求解这个问题。

首先来看分子：

表示遍历Ben评价过的所有歌手，除了Whitney Houston以外(也就是-{j}的意思)。

整个分子的意思是：对于Ben评价过的所有歌手(Whitney Houston除外)，找出Whitney Houston和这些歌手之间的差值，并将差值加上Ben对这个歌手的评分。同时，我们要将这个结果乘以同时评价过两位歌手的用户数。

让我们分解开来看，先将Ben的评分情况和两两歌手之间的差异值展示如下：

1. Ben对Taylor Swift打了5分，也就是ui

2. Whitney Houston和Taylor Swift的差异是-1，即devj,i

3. devj,i + ui = 4

4. 共有两个用户(Amy和Daisy)同时对Taylor Swift和Whitney Houston做了评价，即cj,i = 2

5. 那么(devj,i + ui) cj,i = 4 × 2 = 8

6. Ben对PSY打了2分

7. Whitney Houston和PSY的差异是0.75

8. devj,i + ui = 2.75

9. 有两个用户同时评价了这两位歌手，因此(devj,i + ui) cj,i = 2.75 × 2 = 5.5

10. 分子：8 + 5.5 = 13.5

11. 分母：2 + 2 = 4

12. 预测评分：13.5 ÷ 4 = 3.375

使用Python实现Slope One算法

我们将沿用第二章中编写的Python类，重复的代码我不在这里赘述。输入的数据是这样的：

我们先来计算两两物品之间的差异，公式是：

计算后的输出结果应该如下表所示：

括号中的数值表示同时给这两个歌手评过分的用户数。

第一步

self.data是一个Python字典，它的values()方法可以获取所有键的值。比如上述代码在第一次迭代时，ratings变量的值为{“Taylor Swift”: 4, “PSY”: 3, “Whitney Houston”: 4}。

第二步

在这个类的初始化方法中，我们需要对self.frequencies和self.deviations进行赋值：

Python字典的setdefault()方法接受两个参数，它的作用是：如果字典中不包含指定的键，则将其设为默认值;若存在，则返回其对应的值。

第三步

还是用{“Taylor Swift”: 4, “PSY”: 3, “Whitney Houston”: 4}举例，在第一次遍历中，外层循环item = “Taylor Swift”，rating = 4;内层循环item2 = “PSY”，rating2 = 3，因此最后一行代码是对self.deviations[“Taylor Swift”][“PSY”]做+1的操作。

第四步

最后，我们便可计算出差异值：

完成了!仅仅用了18代码我们就实现了这个公式：

让我们测试一下：

结果和我们之前手工计算的一致：

感谢Bryan O’Sullivan，这里用Python实现的Slope One算法正是基于他的成果。

加权的Slope One算法：推荐逻辑的实现

MovieLens数据集

让我们在另一个数据集上尝试一下Slope One算法。MovieLens数据集是由明尼苏达州大学的GroupLens研究项目收集的，是用户对电影的评分。这个数据集可以在www.grouplens.org*载下**，有三种大小，这里我使用的是最小的那个，包含了943位用户对1682部电影的评价，约10万条记录。我们一起来测试一下：

作业

看看Slope One的推荐结果是否靠谱：对数据集中的10部电影进行评分，得到的推荐结果是否是你喜欢的电影呢?

实现修正的余弦相似度算法，比较一下两者的运算效率。

(较难)我的笔记本电脑有8G内存，在尝试用Slope One计算图书漂流站数据集时报内存溢出了。那个数据集中有27万本书，因此需要保存超过7300万条记录的Python字典。这个字典的数据是否很稀疏呢?修改算法，让它能够处理更多数据吧。

第四章：分类

在上几章中我们使用用户对物品的评价来进行推荐，这一章我们将使用物品本身的特征来进行推荐。这也是潘多拉音乐站所使用的方法。

内容：

• 潘多拉推荐系统简介

• 特征值选择的重要性

• 示例：音乐特征值和邻域算法

• 数据标准化

• 修正的标准分数

• Python代码：音乐，特征，以及简单的邻域算法实现

• 一个和体育相关的示例

• 特征值抽取方式一览

根据物品特征进行分类

前几章我们讨论了如何使用协同过滤来进行推荐，由于使用的是用户产生的各种数据，因此又称为社会化过滤算法。比如你购买了Phoenix专辑，我们网站上其他购买过这张专辑的用户还会去购买Vampire的专辑，因此会把它推荐给你;我在Netflix上观看了Doctor Who，网站会向我推荐Quantum Leap，用的是同样的原理。我们同时也讨论了协同过滤会遇到的种种问题，包括数据的稀疏性和算法的可扩展性。此外，协同过滤算法倾向于推荐那些已经很流行的物品。试想一个极端的例子：一个新乐队发布了专辑，这张专辑还没有被任何用户评价或购买过，那它将永远不会出现在推荐列表中。

这类推荐系统会让流行的物品更为流行，冷门的物品更无人问津。

– Daniel Fleder & Kartik Hosanagar 2009 《推荐系统对商品分类的影响》

这一章我们来看另一种推荐方法。以潘多拉音乐站举例，在这个站点上你可以设立各种音乐频道，只需为这个频道添加一个歌手，潘多拉就会*放播**和这个歌手风格相类似的歌曲。比如我添加了Phoenix乐队，潘多拉便会*放播**El Ten Eleven的歌曲。它并没有使用协同过滤，而是通过计算得到这两个歌手的音乐风格是相似的。其实在*放播**界面上可以看到推荐理由：

“根据你目前告知的信息，我们*放播**的这首歌曲有着相似的旋律，使用了声响和电音的组合，即兴的吉他伴奏。”在我的Hiromi音乐站上，潘多拉会*放播**E.S.T.的歌曲，因为“它有着古典爵士乐风，一段高水准的钢琴独奏，轻盈的打击乐，以及有趣的歌曲结构。”

潘多拉网站的推荐系统是基于一个名为音乐基因的项目。他们雇佣了专业的音乐家对歌曲进行分类(提取它们的“基因”)。这些音乐家会接受超过150小时的训练，之后便可用20到30分钟的时间来分析一首歌曲。这些乐曲特征是很专业的：

这些专家要甄别400多种特征，平均每个月会有15000首新歌曲，因此这是一项非常消耗人力的工程。

注意：潘多拉的音乐基因项目是商业机密，我不曾了解它的任何信息。下文讲述的是如何构造一个类似的系统。

特征值选取的重要性

假设潘多拉会用曲风和情绪作为歌曲特征，分值如下：

曲风：乡村1分，爵士2分，摇滚3分，圣歌4分，饶舌5分

情绪：悲伤的1分，欢快的2分，热情的3分，愤怒的4分，不确定的5分

比如James Blunt的那首You’re Beautiful是悲伤的摇滚乐，用图表来展示它的位置便是：

比如一个叫Tex的用户喜欢You’re Beautiful这首歌，我们想要为他推荐歌曲。

我们的歌曲库中有另外三首歌：

1.是悲伤的爵士乐;

2.是愤怒的圣歌;

3.是愤怒的摇滚乐。

你会推荐哪一首?

图中歌曲1看起来是最相近的。也许你已经看出了这种算法中的不足，因为不管用何种计算距离的公式，爵士乐和摇滚乐是相近的，悲伤的乐曲和快乐的乐曲是相近的等等。即使调整了分值的分配，也不能解决问题。这就是没有选取好特征值的例子。不过解决的方法也很简单，我们将每种歌曲类型拆分成单独的特征，并对此进行打分：

“乡村音乐”一栏的1分表示完全不是这个乐曲风格，5分则表示很相符。这样一来，评分值就显得有意义了。如果一首歌的“乡村音乐”特征是4分，另一首是5分，那我们可以认为它们是相似的歌曲。

其实这就是潘多拉所使用的特征抽取方法。每个特征都是1到5分的尺度，0.5分为一档。特征会被分到不同的大类中。通过这种方式，潘多拉将每首歌曲都抽象成一个包含400个数值元素的向量，并结合我们之前学过的距离计算公式进行推荐。

一个简单的示例

我们先来构建一个数据集，我选取了以下这些特征(可能比较随意)，使用5分制来评分(0.5分一档)：

• 使用钢琴的程度(Piano)：1分表示没有使用钢琴，5分表示整首歌曲由钢琴曲贯穿;

• 使用美声的程度(Vocals)：标准同上

• 节奏(Driving beat)：整首歌曲是否有强烈的节奏感

• 蓝调(Blues infl.)

• 电音吉他(Dirty elec. Guitar)

• 幕后和声(Backup vocals)

• 饶舌(Rap infl.)

使用以上标准对一些歌曲进行评分：

然后我们便可以使用距离计算公式了，比如要计算Dr. Dog的Fate歌曲和Phoenix的Lisztomania之间的曼哈顿距离：

相加得到两首歌曲的曼哈顿距离为9。

使用Python实现推荐逻辑

回忆一下，我们在协同过滤中使用的用户评价数据是这样的：

我们将上文中的歌曲特征数据也用类似的格式储存起来：

假设我有一个朋友喜欢Black Keys Magic Potion，我便可根据曼哈顿距离来进行推荐：

这里我推荐的是Heartless Bastard的Out as Sea，还是很合乎逻辑的。当然，由于我们的数据集比较小，特征和歌曲都不够丰富，因此有些推荐结果并不太好。

如何显示“推荐理由”?

潘多拉在推荐歌曲时会显示推荐理由，我们也可以做到这一点。比如在上面的例子中，我们可以将Magic Potion和Out at Sea的音乐特征做一个比较，找出高度相符的点：

可以看到，两首歌曲最相似的地方是钢琴、和声、以及饶舌，这些特征的差异都是0。但是，这些特征的评分都很低，我们不能告诉用户“因为这首歌曲没有钢琴伴奏，所以我们推荐给你”。因此，我们需要使用那些相似的且评分较高的特征。

我们推荐歌曲是因为它有着强烈的节奏感，美声片段，以及电音吉他的演奏。

评分标准的问题

假如我想增加一种音乐特征——每分钟的鼓点数(bpm)，用来判断这是一首快歌还是慢歌。以下是扩充后的数据集：

没有bpm时，Magic Potion和Out at Sea距离最近，和Smells Like Teen Spirit距离最远。但引入bpm后，我们的结果就乱套了，因为bpm基本上就决定了两首歌的距离。现在Bad Plus和The Black Keys距离最近就是因为bpm数据相近。

再举个有趣的例子。在婚恋网站上，我通过用户的年龄和收入来进行匹配：

这样一来，年龄的最大差异是28，而薪资的最大差异则是72,000。因为差距悬殊，薪水的高低基本决定了匹配程度。如果单单目测，我们会将David推荐给Yun，因为他们年龄相近，工资也差不多。但如果使用距离计算公式，那么53岁的Brian就会被匹配给Yun，这就不太妙了。

事实上，评分标准不一是所有推荐系统的大敌!

标准化

不用担心，我们可以使用标准化。

要让数据变得可用我们可以对其进行标准化，最常用的方法是将所有数据都转化为0到1之间的值。

拿上面的薪酬数据举例，最大值115,000和最小值43,000相差72,000，要让所有值落到0到1之间，可以将每个值减去最小值，并除以范围(72,000)。所以，Yun标准化之后的薪水是：

对一些数据集，这种简单的方法效果是不错的。

如果你学过统计学，会知道还有其他的标准化方法。比如说标准分(z-score)——分值偏离均值的程度：

标准差的计算公式是：

card(x)表示集合x中的元素个数。

如果你对统计学有兴趣，可以读一读《漫话统计学》。

我们用上文中*友网交**站的数据举例。所有人薪水的总和是577,000，一共有8人，所以均值为72,125。代入标准差的计算公式：

那Yun的标准分则是：

练习题：计算Allie、Daniela、Rita的标准分

标准分带来的问题

标准分的问题在于它会受异常值的影响。比如说一家公司有100名员工，普通员工每小时赚10美元，而CEO一年能赚600万，那全公司的平均时薪为：

结果是每小时38美元，看起来很美好，但其实并不真实。鉴于这个原因，标准分的计算公式会稍作变化。

修正的标准分

计算方法：将标准分公式中的均值改为中位数，将标准差改为绝对偏差。以下是绝对偏差的计算公式：

中位数指的是将所有数据进行排序，取中间的那个值。如果数据量是偶数，则取中间两个数值的均值。

下面就让我们试试吧。首先将所有人按薪水排序，找到中位数，然后计算绝对偏差：

最后，我们便可以计算得出Yun的修正标准分：

是否需要标准化?

当物品的特征数值尺度不一时，就有必要进行标准化。比如上文中音乐特征里大部分是1到5分，鼓点数却是60到180;*友网交**站中薪水和年龄这两个尺度也有很大差别。

再比如我想在新墨西哥圣达菲买一处宅子，下表是一些选择：

可以看到，价格的范围是最广的，在计算距离时会起到决定性作用;同样，有两间卧室和有二十间卧室，在距离的影响下作用也会很小。

需要进行标准化的情形：

1. 我们需要通过物品特性来计算距离;

2. 不同特性之间的尺度相差很大。

但对于那种“赞一下”、“踩一脚”的评分数据，就没有必要做标准化了：

在潘多拉的例子中，如果所有的音乐特征都是在1到5分之间浮动的，是否还需要标准化呢?虽然即使做了也不会影响计算结果，但是任何运算都是有性能消耗的，这时我们可以通过比较两种方式的性能和效果来做进一步选择。在下文中，我们会看到标准化反而会降低结果正确性的示例。

回到潘多拉

在潘多拉网站的示例中，我们用一个特征向量来表示一首歌曲，用以计算歌曲的相似度。潘多拉网站同样允许用户对歌曲“赞”和“踩”，那我们要如何利用这些数据呢?

假设我们的歌曲有两个特征，重金属吉他(Dirty Guitar)和强烈的节奏感(Driving Beat)，两种特征都在1到5分之间。一位用户对5首歌曲做了“赞”的操作(图中的L)，另外五首则“踩”了一下(图中的D)：

图中多了一个问号所表示的歌曲，你觉得用户会喜欢它还是不喜欢呢?想必你也猜到了，因为这个问号离用户喜欢的歌曲距离较近。这一章接下来的篇幅都会用来讲述这种计算方法。最明显的方式是找到问号歌曲最邻近的歌曲，因为它们之间相似度比较高，再根据用户是否喜欢这些邻近歌曲来判断他对问号歌曲的喜好。

使用Python实现最邻近分类算法

我们仍使用上文中的歌曲示例，用7个特征来标识10首歌曲：

使用Python代码来表示这些数据：

这样做虽然可行，但却比较繁琐，piano、vocals这样的键名需要重复很多次。我们可以将其简化为向量，即Python中的数组类型：

接下来我还需要将用户“赞”和“踩”的数据也用Python代码表示出来。由于用户并不会对所有的歌曲都做这些操作，所以我用嵌套的字典来表示：

这里使用L和D两个字母来表示喜欢和不喜欢，当然你也可以用其他方式，比如0和1等。

对于新的向量格式，我们需要对曼哈顿距离函数和邻近物品函数做一些调整：

最后，我需要建立一个分类函数，用来预测用户对一个新物品的喜好，如：

这个函数会先计算出与这个物品距离最近的物品，然后找到用户对这个最近物品的评价，以此作为新物品的预测值。下面是一个最简单的分类函数：

让我们试用一下：

我们认为她会喜欢这首歌曲!为什么呢?

可以看到，距离I Breathe In最近的歌曲是Alejandro，并且Angelica是喜欢这首歌曲的，所以我们预测她也会喜欢I Breathe In。

其实我们做的是一个分类器，将歌曲分为了用户喜欢和不喜欢两个类别。

号外，号外!我们编写了一个分类器!

分类器是指通过物品特征来判断它应该属于哪个组或类别的程序!

分类器程序会基于一组已经做过分类的物品进行学习，从而判断新物品的所属类别。在上面的例子中，我们知道Angelica喜欢和不喜欢的歌曲，然后据此判断她是否会喜欢Chris Cagle的歌。

在Angelica评价过的歌曲中找到距离Chris Cagle最近的歌曲，即Laydy Gaga的Alejandro;

由于Angelica是喜欢Alejandro这首歌的，所以我们预测她也会喜欢Chris Cagle的Breathe In, Breathe Out。

分类器的应用范围很广，以下是一些示例：

推特情感分类

很多人在对推特中的文字消息进行情感分类(积极的、消极的)，可以有很多用途，如Axe发布了一款新的腋下除臭剂，通过推文就能知道用户是否满意。这里用到的物品特征是文字信息。

人脸识别

现在有些手机应用可以识别出照片里你的朋友们，这项技术也可用于监控录像中的人脸识别。不同的识别技术细节可能不同，但都会用到诸如五官的大小和相对距离等信息。

政治拉票

通过将目标选民分为“爱凑热闹”、“很有主见”、“家庭为重”等类型，来进行有针对性的拉票活动。

市场细分

这和上个例子有点像，与其花费巨额广告费向不可能购买维加斯公寓的人进行宣传，不如从人群中识别出潜在客户，缩小宣传范围。最好能再对目标群体进行细分，进一步定制广告内容。

个人健康助理

如今人们越来越关注自身，我们可以购买到像Nike健身手环这样的产品，而Intel等公司也在研制一种智能家居，可以在你行走时称出你的重量，记录你的行动轨迹，并给出健康提示。有些专家还预言未来我们会穿戴各种便携式设备，收集我们的生活信息，并加以分类。

其他

1. 识别恐怖分子

2. 来信分类(重要的、一般的、垃圾邮件)

3. 预测医疗费用

4. 识别金融诈骗

她是从事什么运动的?

让我们来为之后的几章做一个预热，先看一个较为简单的例子——根据女运动员的身高和体重来判断她们是从事什么运动项目的。下表是原始数据：

这里列出的是2008和2012奥运会上排名靠前的二十位女运动员。篮球运动员参加了WNBA;田径运动员则完成了2012年奥运会的马拉松赛。虽然数据量很小，但我们仍可以对其应用一些数据挖掘算法。

你可以看到上表中列出了运动员的年龄，光凭这一信息就能进行一些预测了。比如，以下运动员会是哪个项目的呢?

答案

Candace Parker是篮球运动员，McKayla Maroney是美国女子体操队的一员，Olivera Jevtic是塞尔维亚的一名长跑运动员，Lisa Jane Weightman则是澳大利亚的长跑运动员。

看，我们刚刚就进行了一次分类——通过运动员的年龄特征来识别她们参与的体育项目。

头脑风暴

假设我想通过运动员的身高和体重来预测她所从事的运动，数据集只有两人：Nakia Sanford是篮球运动员，身高6尺4寸(76英寸，1.93米)，体重200磅(90公斤);Sarah Beale是橄榄球运动员，身高5尺10寸(70英寸，1.78米)，体重190磅(86公斤)。我想知道Catherine Spencer是从事哪项运动的，她的身高是5尺10寸，重200磅，如何预测呢?

如果你认为她是橄榄球运动员，那么你猜对了。但是，如果用曼哈顿距离来进行计算，Catherine和Nakia的距离是6，和Sarah的距离是10，那应该预测她是篮球运动员才对。我们之前是否学过一个方法，能让距离计算更为准确呢?

没错，就是修正的标准分!

测试数据

下表是我们需要进行预测的运动员列表，一起来做分类器吧!

Python编码

这次我们不将数据直接写在Python代码中，而是放到两个文本文件里：athletesTrainingSet.txt和athletesTestSet.txt。我会使用第一个文件中的数据来训练分类器，然后使用测试文件里的数据来进行评价。

文件格式大致如下：

文件中的每一行是一条完整的记录，字段使用制表符分隔。我要使用运动员的身高体重数据来预测她所从事的运动项目，也就是用第三、四列的数据来预测第二列的数据。运动员的姓名不会使用到，我们既不能通过运动员的姓名得知她参与的项目，也不会通过身高体重来预测运动员的姓名。

你好，你有五英尺高，150磅重，莫非你的名字是Clara Coleman?

当然，名字也有它的用处，我们可以用它来解释分类器的预测结果：“我们认为Amelia Pond是一名体操运动员，因为她的身高体重和另一名体操运动员Gabby Douglas很接近。”

为了让我们的Python代码更具一般性，并不只适用于这一种数据集，我会为每一列数据增加一个列名，如：

所有被标记为comment的列都会被分类器忽略;标记为class的列表示物品所属分类;不定个数的num列则表示物品的特征。

头脑风暴

我们在Python中应该如何表示这些数据呢?以下是一些可能性：

这种方式使用了运动员的姓名作为键，而我们说过分类器程序根本不会使用到姓名，所以不合理。

这种方式看起来不错，它直接反映了文件的格式。由于我们需要遍历文件的数据，所以使用列表类型(list)是合理的。

这是我最认同的表示方式，因为它将不同类型的数据区别开来了，依次是分类、特征、备注。这里备注可能有多个，所以也用了一个列表来表示。以下是读取数据文件并转换成上述格式的函数：

动手实践

在计算修正的标准分之前，我们需要编写获取中位数和计算绝对偏差的函数，尝试实现这两个函数：

关于断言

通常我们会将一个大的算法拆分成几个小的组件，并为每个组件编写一些单元测试，从而确保它能正常工作。很多时候，我们会先写单元测试，再写正式的代码。在我提供的模板代码中已经编写了一些单元测试，摘录如下：

你需要完成的geMedian函数的模板是：

这个模板函数返回的是0，你需要编写代码来返回列表的中位数。比如单元测试中我传入了以下列表：

assert(断言)表示函数的返回值应该是65。如果所有的单元测试都能通过，则报告以下信息：

否则，则抛出以下异常：

断言在单元测试中是很常用的。

将大型代码拆分成一个个小的部分，并为每个部分编写单元测试，这一点是很重要的。如果没有单元测试，你将无法知道自己是否正确完成了所有任务，以及未来的某个修改是否会导致你的程序不可用。— Peter Norvig

答案

可以看到，getMedian函数对列表进行了排序，由于数据量并不大，所以这种方式是可以接受的。如果要对代码进行优化，我们可以使用选择算法。

现在，我们已经将数据从athletesTrainingSet.txt读取出来，并保存为以下形式：

我们需要对向量中的数据进行标准化，变成以下结果：

在init方法中，添加标准化过程：

在for循环中逐列进行标准化，即第一次会标准化身高，第二次标准化体重。

动手实践 *载下**normalizeColumnTemplate.py文件，编写normalizeColumn方法。

答案

可以看到，我将计算得到的中位数和绝对偏差保存在了medianAndDeviation变量中，因为我们会用它来标准化需要预测的向量。比如，我要预测Kelly Miller的运动项目，她身高5尺10寸(70英寸)，重140磅，即原始向量为[70, 140]，需要先进行标准化。

我们计算得到的meanAndDeviation为：

它表示向量中第一元素的中位数为65.5，绝对偏差为5.95;第二个元素的中位数为107.0，绝对偏差33.65。

现在我们就利用这组数据将[70, 140]进行标准化。第一个元素的标准分数是：

第二个元素为：

以下是实现它的Python代码：

最后，我们要编写分类函数，用来预测运动员的项目：

在我们的实现中，classify函数只是nearestNeighbor的一层包装：

动手实践 实现nearestNeighbor函数。

答案

好了，我们用200多行代码实现了近邻分类器!

在完整的示例代码中，我提供了一个test函数，它可以对分类器程序的准确性做一个评价。比如用它来评价上面实现的分类器：

可以看到，这个分类器的准确率是80%。它对篮球运动员的预测很准确，但在预测田径和体操运动员时出现了4个失误。

鸢尾花数据集

我们可以用鸢尾花数据集做测试，这个数据集在数据挖掘领域是比较有名的。它是20世纪30年代Ronald Fisher对三种鸢尾花的50个样本做的测量数据(萼片和花瓣)。

Ronald Fisher是一名伟大的科学家。他对统计学做出了革命性的改进，Richard Dawkins称他为“继达尔文后最伟大生物学家。”

鸢尾花数据集可以在这里找到，你可以测试你的算法，并问自己一些问题：标准化让结果更正确了吗?训练集中的数据量越多越好吗?用欧几里得距离来算会怎样?

记住 所有的学习过程都是在你自己的脑中进行的，你付出的努力越多，学到的也就越多。

鸢尾花数据集的格式如下，我们要预测的是Species这一列：

训练集中有120条数据，测试集中有30条，两者没有交集。

测试结果如何呢?

这又一次证明我们的分类算法是简单有效的。有趣的是，如果不对数据进行标准化，它的准确率将达到100%。这个现象我们会在后续的章节中讨论。

每加仑燃油可以跑多少公里?

最后，我们再来测试另一个广泛使用的数据集，卡内基梅隆大学统计的汽车燃油消耗和公里数数据。它在1983年的美国统计联合会展中使用过，大致格式如下：

这个数据集做过一些修改。我们要预测的是加仑燃油公里数(mpg)，使用的数据包括汽缸数、排气量、马力、重量、加速度等。

数据集中有342条记录，50条测试记录，运行结果如下：

如果不进行标准化，准确率将只有32%。

我们应该如何提高预测的准确率呢?改进分类算法?增加训练集?还是增加特征的数量?我们将在下一章揭晓!

番外篇：关于标准化

这一章我们讲解了标准化的重要性，即当不同特征的评分尺度不一致时，为了得到更准确的距离结果，就需要将这些特征进行标准化，使他们在同一个尺度内波动。

虽然大多数数据挖掘工程师对标准化的理解是一致的，但也有一些人要将这种做法区分为“正规化”和“标准化”两种。其中，“正规化”表示将值的范围缩小到0和1之间;“标准化”则是将特征值转换为均值为0的一组数，其中每个数表示偏离均值的程度(即标准偏差或绝对偏差)。我们使用的修正的标准分就是属于后者。

回忆一下，我们上文中有讲解过如何将特征值缩小到0到1之间：找出最大最小值，并做如下计算：

我们来比较一下使用不同的标准化方法得到的准确度：

看来还是使用修正的标准分结果会好些。

用不同的数据集来测试我们的算法是不是很有趣?这些数据集是从UCI机器学习仓库中获得的。去*载下**一些新的数据集，调整一下格式，测试我们学过的算法吧!

第五章：进一步探索分类

效果评估算法和kNN

让我们回到上一章中运动项目的例子。

在那个例子中，我们编写了一个分类器程序，通过运动员的身高和体重来判断她参与的运动项目——体操、田径、篮球等。

上图中的Marissa Coleman，身高6尺1寸，重160磅，我们的分类器可以正确的进行预测：

对于身高4尺9寸，90磅重的人：

当我们构建完一个分类器后，应该问以下问题：

1. 分类器的准确度如何?

2. 结果理想吗?

3. 如何与其它分类器做比较?

训练集和测试集

上一章我们一共引入了三个数据集，分别是女运动员、鸢尾花、加仑公里数。我们将这些数据集分为了两个部分，第一部分用来构造分类器，因此称为训练集;另一部分用来评估分类器的结果，因此称为测试集。训练集和测试集在数据挖掘中很常用。

数据挖掘工程师不会用同一个数据集去训练和测试程序。

因为如果使用训练集去测试分类器，得到的结果肯定是百分之百准确的。换种说法，在评价一个数据挖掘算法的效果时，如果用来测试的数据集是训练集本身的一个子集，那结果会极大程度趋向于好，所以这种做法不可取。

将数据集拆分成一大一小两个部分的做法就产生了，前者用来训练，后者用来测试。不过，这种做法似乎也有问题：如果分割的时候不凑巧，就会引发异常。比如，若测试集中的篮球运动员恰巧都很矮，她们就会被归为马拉松运动员;如果又矮又轻，则会被归为体操运动员。使用这样的测试*会集**造成评分结果非常低。相反的情况也有可能出现，使评分结果趋于100%准确。无论哪种情况发生，都不是一种真实的评价。

解决方法之一是将数据集按不同的方式拆分，测试多次，取结果的平均值。比如，我们将数据集拆为均等的两份：

我们可以先用第一部分做训练集，第二部分做测试集，然后再反过来，取两次测试的平均结果。我们还可以将数据集分成三份，用两个部分来做训练集，一个部分来做测试集，迭代三次：

1. 使用Part 1和Part 2训练，使用Part 3测试;

2. 使用Part 1和Part 3训练，使用Part 2测试;

3. 使用Part 2和Part 3训练，使用Part 1测试;

最后取三次测试的平均结果。

在数据挖掘中，通常的做法是将数据集拆分成十份，并按上述方式进行迭代测试。因此这种方式也称为——

十折交叉验证

将数据集随机分割成十个等份，每次用9份数据做训练集，1份数据做测试集，如此迭代10次。

我们来看一个示例：假设我有一个分类器能判断某个人是否是篮球运动员。我的数据集包含500个运动员和500个普通人。

第一步：将数据分成10份

每个桶中会放50个篮球运动员，50个普通人，一共100人。

第二步：重复以下步骤10次

每次迭代我们保留一个桶，比如第一次迭代保留木桶1，第二次保留木桶2。

我们使用剩余的9个桶来训练分类器，比如第一次迭代使用木桶2至10来训练。

我们用刚才保留的一个桶来进行测试，并记录结果，比如：35个篮球运动员分类正确，29个普通人分类正确。

第三步：合并结果

我们可以用一张表格来展示结果：

500个篮球运动员中有372个人判断正确，500个普通人中有280个人判断正确，所以我们可以认为1000人中有652个人判断正确，准确率就是65.2%。通过十折交叉验证得到的评价结果肯定会比二折或者三折来得准确，毕竟我们使用了90%的数据进行训练，而非二折验证中的50%。

好，既然十折交叉验证效果那么好，我们为何不做一个N折交叉验证?N即数据集中的数据量。

如果我们有1000个数据，我们就用999个数据来训练分类器，再用它去判定剩下的一个数据。这样得到的验证效果应该是最好的。

留一法

在数据挖掘领域，N折交叉验证又称为留一法。上面已经提到了留一法的优点之一：我们用几乎所有的数据进行训练，然后用一个数据进行测试。留一法的另一个优点是：确定性。

什么是确定性?

试想Lucy花了一整周的时间编写了一个分类器。周五的时候她请两位同事(Emily和Li)来对这个分类器进行测试，并给了他们相同的数据集。这两位同事都使用十折交叉验证，结果是：

Emily：这个分类器的准确率是73.69%，很不错!

Li：它的准确率只有71.27%。

为什么她们的结果不一样?是某个人计算发生错误了吗?其实不是。在十折交叉验证中，我们需要将数据随机等分成十份，因此Emily和Li的分法很有可能是不一样的。这样一来，她们的训练集和测试集也都不相同了，得到的结果自然不同。即使是同一个人进行检验，如果两次使用了不同的分法，得到的结果也会有差异。因此，十折交叉验证是一种不确定的验证。相反，留一法得到的结果总是相同的，这是它的一个优点。

留一法的缺点

最大的缺点是计算时间很长。假设我们有一个包含1000条记录的数据集，使用十折交叉验证需要运行10分钟，而使用留一法则需要16个小时。如果我们的数据集更大，达到百万级，那检验的时间就更长了。

我两年后再给你检验结果!

留一法的另一个缺点是分层问题。

分层问题

让我们回到运动员分类的例子——判断女运动员参与的项目是篮球、体操、还是田径。在训练分类器的时候，我们会试图让训练集包含全部三种类别。如果我们完全随机分配，训练集中有可能会不包含篮球运动员，在测试的时候就会影响结果。比如说，我们来构建一个包含100个运动员的数据集：从女子NBA网站上获取33名篮球运动员的信息，到Wikipedia上获取33个参加过2012奥运会体操项目的运动员，以及34名田径运动员的信息。这个数据集看起来是这样的：

现在我们来做十折交叉验证。我们按顺序将这些运动员放到10个桶中，所以前三个桶放的都是篮球运动员，第四个桶有篮球运动员也有体操运动员，以此类推。这样一来，没有一个桶能真正代表这个数据集的全貌。最好的方法是将不同类别的运动员按比例分发到各个桶中，这样每个桶都会包含三分之一篮球运动员、三分之一体操运动员、以及三分之一田径运动员。这种做法叫做分层。而在留一法中，所有的测试集都只包含一个数据。所以说，留一法对小数据集是合适的，但大多数情况下我们会选择十折交叉验证。

混淆矩阵

目前我们衡量分类器准确率的方式是使用以下公式：正确分类的记录数÷记录总数。有时我们会需要一个更为详细的评价结果，这时就会用到一个称为混淆矩阵的可视化表格。表格的行表示测试用例实际所属的类别，列则表示分类器的判断结果。

混淆矩阵可以帮助我们快速识别出分类器到底在哪些类别上发生了混淆，因此得名。让我们看看运动员的示例，这个数据集中有300人，使用十折交叉验证，其混淆矩阵如下：

可以看到，100个体操运动员中有83人分类正确，17人被错误地分到了马拉松一列;92个篮球运动员分类正确，8人被分到了马拉松;85个马拉松运动员分类正确，9人被分到了体操，16人被分到了篮球。

混淆矩阵的对角线(绿色字体)表示分类正确的人数，因此求得的准确率是：

从混淆矩阵中可以看出分类器的主要问题。在这个示例中，我们的分类器可以很好地区分体操运动员和篮球运动员，而马拉松运动员则比较容易和其他两个类别发生混淆。

怎样，是不是觉得混淆矩阵其实并不混淆呢?

代码示例

让我们使用加仑公里数这个数据集，格式如下：

我会通过汽车的以下属性来判断它的加仑公里数：汽缸数、排气量、马力、重量、加速度。我将392条数据都存放在mpgData.txt文件中，并用下面这段Python代码将这些数据按层次等分成十份：

执行这个程序后会生成10个文件：mpgData01、mpgData02等。

编程实践

你能否修改上一章的近邻算法程序，让test函数能够执行十折交叉验证?输出的结果应该是这样的：

解决方案

我们需要进行以下几步：

1. 修改初始化方法，只读取九个桶中的数据作为训练集;

2. 增加一个方法，从第十个桶中读取测试集;

3. 执行十折交叉验证。

下面我们分步来看：

初始化方法__init__

__init__方法的签名会修改成以下形式：

每个桶的文件名是mpgData-01、mpgData-02这样的形式，所以bucketPrefix就是“mpgData”。testBucketNumber是测试集所用的桶，如果是3，则分类器会使用1、2、4-9的桶进行训练。dataFormat用来指定数据集的格式，如：

意味着第一列是所属分类，后五列是特征值，最后一列是备注信息。

以下是初始化方法的示例代码：

testBucket方法

下面的方法会使用一个桶的数据进行测试：

比如说bucketPrefix是mpgData，bucketNumber是3，那么程序会从mpgData-03中读取内容，作为测试集。这个方法会返回如下形式的结果：

这个字段的键表示真实类别。如第一行的35表示该行数据的真实类别是35加仑公里。这个键又对应一个字典，这个字典表示的是分类器所判断的类别，如：

其中的3表示有3条记录真实类别是15加仑公里，但被分类到了20加仑公里;4表示分类正确的记录数;1表示被分到10加仑公里的记录数。

执行十折交叉验证

最后我们需要编写一段程序来执行十折交叉验证，也就是说要用不同的训练集和测试集来构建10个分类器。

执行结果如下：

可以在这里*载下**代码和数据集。

Kappa指标

本章的开头我们对分类器的效果提了几个问题，并在此之后使用十折交叉验证和混淆矩阵来对分类器进行评估。上一节中我们对加仑公里数分类器的评价结果是53.316%的正确率，那这个结果是好是坏呢?我们就需要使用一个新的指标：Kappa指标。

Kappa指标可以用来评价分类器的效果比随机分类要好多少。我们仍用运动员的例子来说明，以下是它的混淆矩阵：

我增加了“合计”一列，因此在计算正确率时，我们只需将对角线相加(35 + 88 + 28 = 151)除以合计(200)就可以了，结果是0.755。

现在，我们建造另一个混淆矩阵，用来表示随机分类的结果。首先，我们将上表中的数据抹去一部分，只留下合计：

从最后一行可以看到，我们之前构造的分类器将50%的运动员分类到篮球运动员中(200中的100人)，20%分到了体操，剩余30%分到了马拉松。即：

• 体操 20%

• 篮球 50%

• 田径 30%

我们会用这个百分比来构造随机分类器的混淆矩阵。比如，真实的体操运动员一共有60人，随机分类器会将其中的20%(12人)分类为体操，50%(30人)分类为篮球，30%(18人)分类为马拉松，填入表格：

继续用这种方法填充空白。100个真实的篮球运动员，20%(20人)分到体操，50%(50人)分到篮球，30%(30人)分到马拉松。

从而得到随机分类器的准确率是：

Kappa指标可以用来衡量我们之前构造的分类器和随机分类器的差异，公式为：

P(c)表示分类器的准确率，P(r)表示随机分类器的准确率。将之前的结果代入公式：

0.61要如何解释呢?可以参考下列经验结果：

来源：Landis, JR, Koch, GG. 1977 分类效果评估 生物测量学

动手实践

假设我们开发了一个效果不太好的分类器，用来判断600名大学生所读专业，使用的数据是他们对10部电影的评价。这些大学生的专业类别有计算机科学(cs)、教育学(ed)、英语(eng)、心理学(psych)。以下是该分类器的混淆矩阵，尝试计算出它的Kappa指标并予以解释。

准确率 = 0.697

解答

首先，计算列合计和百分比：

然后根据百分比来填充随机分类器的混淆矩阵：

准确率 = (8 + 24 + 51 + 92) / 600 = (175 / 600) = 0.292

最后，计算Kappa指标：

这说明分类器的效果还是要好过预期的。

优化近邻算法

有一种分类器叫“机械记忆分类器(Rote Classifer)”，它会将数据集完整地保存下来，并用来判断某条记录是否存在于数据集中。所以，如果我们只对数据集中的数据进行分类，准确率将是100%。而在现实应用中，这种分类器并不可用，因为我们需要判定某条新的记录属于哪个分类。你可以认为我们上一章中构建的分类器是机械记忆分类器的一种扩展，只是我们不要求新的记录完全对应到数据集中的某一条记录，只要距离最近就可以了。PangNing Tan等人在其机器学习的教科书中写过这样一段话：如果一只动物走起来像鸭子、叫起来像鸭子、而且看起来也像鸭子，那它很有可能就是一只鸭子。

近邻算法的问题之一是异常数据。还是拿运动员分类举例，不过只看体操和马拉松。假设有一个比较矮也比较轻的人，她是马拉松运动员，这样就会形成以下这张图，横轴是体重，纵轴是身高，其中m表示马拉松，g表示体操：

可以看到这名特别的马拉松运动员处于体操运动员的群组中。假设我们要对一名新的运动员进行分类，用图中的x表示，可以看到离她最近的运动员是那名特别的马拉松运动员，这样一来这名新的运动员就会被归到马拉松，但实际上她更有可能是一名体操运动员。

kNN算法

优化方法之一是考察这条新记录周围距离最近的k条记录，而不是只看一条，因此这种方法称为k近邻算法(kNN)。每个近邻都有投票权，程序会将新记录判定为得票数最多的分类。比如说，我们使用三个近邻(k = 3)，其中两条记录属于体操，一条记录属于马拉松，那我们会判定x为体操。

因此，我们在判定一条记录的具体分类时可以用这种投票的方法。如果两个分类的票数相等，就随机选取一个。但对于需要预测具体数值的情形，比如一个人对Funky Meters乐队的评分，我们可以计算k个近邻的距离加权平均值。举个例子，我们需要预测Ben对Funky Meters的喜好程度，他的三个近邻分别是Sally、Tara、和Jade。下表是这三个人离Ben的距离，以及他们对Funky Meters的评分：

可以看到，Sally离Ben最近，她给Funky Meters的评分是4。在计算平均值的时候，我希望距离越近的用户影响越大，因此可以对距离取倒数，从而得到下表：

下面，我们把所有的距离倒数除以距离倒数的和(0.2 + 0.1 + 0.067 = 0.367)，从而得到评分的权重：

我们可以注意到两件事情：权重之和是1;原始数据中，Sally的距离是Tara的二分之一，这点在权重中体现出来了。最后，我们求得平均值，也即预测Ben对Funky Meters的评分：

动手实践

我们想要预测Sofia对爵士钢琴手Hiromi的评分，以下是她三个近邻的距离和评分：

解答

第一步，计算距离的倒数：

第二步，计算权重(距离倒数之和为0.475)：

第三步，预测评分：

新的数据集，新的挑战!

是时候使用新的数据集了——比马印第安人糖尿病数据集，由美国国家糖尿病、消化和肾脏疾病研究所提供。

令人惊讶的是，超过30%的比马人患有糖尿病，而全美的糖尿病患者比例是8.3%，中国只有4.2%。

数据集中的一条记录代表一名21岁以上的比马女性，她们分类两类：五年内查出患有糖尿病，以及没有得病。共选取了8个特征：

• 怀孕次数;

• 口服葡萄糖耐量实验两小时后的血浆葡萄糖浓度;

• 舒张压(mm Hg);

• 三头肌皮褶厚度(mm);

• 血清胰岛素(mu U/ml);

• 身体质量指数(BMI)：体重(公斤)除以身高(米)的平方;

• 糖尿病家谱;

• 年龄(岁)。

以下是示例数据，最后一列的0表示没有糖尿病，1表示患有糖尿病：

比如说，第一条记录表示一名生过两次小孩的女性，她的血糖浓度是99，舒张压是52，等等。

实践[1]

本书提供了两份数据集：pimaSmall.zip和pima.zip。前者包含100条记录，后者包含393条记录，都已经等分成了10个文件(10个桶)。我用前面实现的近邻算法计算了pimaSmall数据集，得到的结果如下：

提示：代码中的heapq.nsmallest(n, list)会返回n个最小的项。heapq是Python内置的优先队列类库。

你的任务是实现kNN算法。首先在类的init函数中添加参数k：

knn函数的签名应该是：

它会使用到self.k(记得在init函数中保存这个值)，它的返回值是0或1。此外，在进行十折交叉验证(tenFold函数)时也要传入k参数。

解答

init函数的修改很简单：

knn函数的实现是：

对tenFold函数的改动如下：

你可以从网站上*载下**这些代码，不过我的代码并不一定是最优的，仅供参考。

实践[2]

在分类效果上，究竟是数据量的多少比较重要(即使用pimaSmall和pima数据集的效果)，还是更好的算法比较重要(k=1和k=3)?

解答

以下是比较结果：

看来增加数据量要比使用更好的算法带来的效果好。

实践[3]

72.519%的准确率看起来不错，但还是用Kappa指数来检验一下吧：

解答

计算合计和比例：

随机分类器的混淆矩阵：

随机分类器的正确率：

Kappa指标：

效果一般

更多数据，更好的算法，还有抛锚的巴士

几年前我去参加一个墨西哥城的研讨会，比较特别的是会议的第二天是坐观光巴士旅游，观看黑脉金斑蝶等。这辆巴士比较破旧，中途抛锚了好几次，所以我们一群有着博士学位的人就站在路边一边谈笑，一边等着司机修理巴士。而事实证明这段经历是这次会议最大的收获。其间，我有幸与Eric Brill做了交流，他在词性分类方面有着很高的成就，他的算法比前人要优秀很多，从而使他成为自然语言处理界的名人。我和他谈论了分类器的效果问题，他说实验证明增加数据所带来的效果要比改进算法来得大。事实上，如果仍沿用老的词性分类算法，而仅仅增加训练集的数据量，效果很有可能比他现有的算法更好。当然，他不可能通过收集更多的数据来获得一个博士学位，但如果如果你的算法能够取得哪怕一点点改进，也足够了。

当然，这并不是说你就不需要挑选出更好的算法了，我们之前也看到了好的算法所带来的效果也是惊人的。但是如果你只是想解决一个问题，而非发表一篇论文，那增加数据量会更经济一些。

所以，在认同数据量多寡的重要影响后，我们仍将继续学习各种算法。

人们使用kNN算法来做以下事情：

• 在亚马逊上推荐商品

• 评估用户的信用

• 通过图像分析来分类路虎车型

• 人像识别

• 分析照片中人物的性别

• 推荐网页

• 推荐旅游套餐

via：36大数据 感谢 作者：Ron Zacharski