作者：黄申
出版社：机械工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
大数据架构和算法实现之路：电商系统的技术实战试读：
前言
为什么要写这本书
首先要感谢机械工业出版社华章公司的编辑们，在他们的大力支持下，我于2016年出版了《大数据架构商业之路：从业务需求到技术方案》一书，并获得了良好的销售额和口碑。不少读者主动和我联系，表示从书中学习到了如何使用大数据的知识，来制定合理的技术方案。能够让读者从书中获益，我也感到非常欣慰。与此同时，也有部分读者表示对于技术的细节很感兴趣，对此书未能包含实现部分深感遗憾。对此，我一直在犹豫是否需要重新写一版，包含更多的实战内容。因为《大数据架构商业之路：从业务需求到技术方案》一书的定位是最大程度地弥补业务需求和技术方案之间的空白，针对的读者主要是互联网公司的技术管理人员、产品经理、初级的架构师等。如果直接加入过多的技术细节，可能会导致该书的定位不清，让读者难以获得最佳的阅读体验。
与本书的策划编辑杨老师再三讨论之后，我决定不在原书中加入更多的实现部分，而是重新撰写一本兄弟篇。这本全新的书，仍然会沿用前作的故事背景和应用场景，不过读者对象改为资深的程序员、算法工程师、数据科学家和系统架构师。因此，新作将大幅缩减基础知识的详细介绍以及业务需求的逐步分析，而是直接进入实战的主题，包括系统架构、算法设计，甚至是重要的代码部分。当然，我也不希望该书全由代码堆砌而成，因此主要针对核心代码进行了讲解。全部的实例代码会以其他形式来提供。
虽然定位有所不同，但是我仍然希望保持前作深入浅出的特点。
·易读易懂。黄小明和杨大宝的创业故事在稍作修改的基础之上得以保留，继续使用生动的案例和形象的比喻来解读难点，降低理解的门槛。
·可实践性强。本书选取了电子商务的平台，通过分享大量实践才能积累的宝贵经验和重点代码，最大程度地弥补业务需求和技术方案之间的空白。与此同时，针对频繁升级的开源软件，我也采用了2016年年底到2017年年初最新的版本。因此，部分代码甚至可作为中小公司创业起步的参考模板。这有利于技术人员针对不同的业务需求，规划更为合理的技术方案。
最后，我们衷心希望本书成为相关领域技术专家的良师益友，大家在阅读之后，对电商大数据的实践能有更加深入的理解，并对自己所从事的项目有所裨益。
读者对象
根据本书撰写的起心动念，我们觉得其内容适合如下的读者。
·大数据相关领域的程序开发者和技术骨干。从本书中，他们可以看到常见的互联网公司从创业初期到中期，应该怎样设计数据平台、如何解决技术上的难题，才能最终满足业务需求。
·中小互联网创业公司的数据科学家或者算法工程师。算法是数据平台的一个关键因素。最近几年，人工智能、机器学习乃至深度学习都是学术界和工业界的一大热点，而数据科学家也成为受人追捧的职业。合理地运用智能算法将从很大程度上节约重复劳动的成本，提高效率和转化率，最终增加商业的价值。
·架构工程师。架构是数据平台的另一个关键因素，很多刚刚从院校毕业、工作没多久的朋友，学了一身的本领，对新技术也很有热情，可惜没有太多实践的机会。本书中的案例，浓缩了不少业界实践的经验和心得，如能融会贯通，对他们的工作将有很大帮助。同时，覆盖面较广的技术课题概述，也为他们继续深入研究提供了方向和可能。
总之，本书适合钻研实现细节的程序员、工程师和算法专家。和前作的侧重点有所不同，本书并不适合作为入门教程使用。因此建议没有相关基础知识的读者，读完前作之后再来阅读此书。
如何阅读本书
本书介绍了一些主流技术在商业项目中的应用，包括机器学习中的分类、聚类和线性回归，搜索引擎，推荐系统，用户行为跟踪，架构设计的基本理念及常用的消息和缓存机制。在这个过程中，我们有机会实践R、Mahout、Solr、Elasticsearch、Hadoop、HBase、Hive、Flume、Kafka、Storm等系统。如前所述，本书最大的特色就是，从商业需求出发演变到合理的技术方案和实现，因此根据不同的应用场景、不同的数据集合、不同的进阶难度，我们为读者提供了反复温习和加深印象的机会。
勘误和支持
众所周知，大数据的发展实在是太快了。可能就在你阅读这段文字的同时，又有一项新的技术诞生了，N项技术升级了，M项技术被淘汰了。再加之笔者的水平有限，书中难免会出现一些不够准确或遗漏的地方，恳请读者通过如下的渠道积极建议和斧正，我们很期待能够收到你们的真挚反馈。
QQ：36638279
微信：18616692855
邮箱：s_huang790228@hotmail.com
LinkedIn：https://cn.linkedin.com/in/shuang790228
致谢
首先要感谢上海交通大学和俞勇教授，你们给予我不断学习的机会，带领我进入了大数据的世界。同时，感谢阿里云的高级总监薛贵荣，你的指导让我树立了良好的科研态度。
还要感谢微软亚洲研究院、eBay中国研发中心、沃尔玛1号店、大润发飞牛网和IBM中国研发中心，在这些公司十多年的实战经验让我收获颇丰，也为本书的铸就打下了坚实的基础。
感谢曾经的微软战友陈正、孙建涛、Ling Bao、曾华军、张本宇、沈抖、刘宁、严峻、曹云波、王琼华、康亚滨、胡健、季蕾等，eBay的战友逄伟、王强、王骁、沈丹、Yongzheng Zhang、Catherine Baudin、Alvaro Bolivar、Xiaodi Zhang、吴晓元、周洋、胡文彦、宋荣、刘文、Lily Yu等，沃尔玛1号店的战友韩军、王欣磊、胡茂华、付艳超、张旭强、黄哲铿、沙燕霖、郭占星、聂巍、邵汉成、张珺、胡毅、邱仔松、孙灵飞、凌昱、王善良、廖川、杨平、余迁、周航、吴敏、李峰，熊健等，大润发飞牛网的战友王俊杰、陈俞安、蔡伯璟、陈慧文、夏吉吉、文燕军、杨立生、张飞、代伟、陈静、赵瑜、李航等，IBM的战友李伟、谢欣、周健、马坚、刘钧、唐显莉等。要感谢的同仁太多，如有遗漏敬请谅解，很怀念和你们并肩作战的日子，那段时间让我学习到了很多。
感谢机械工业出版社华章公司的编辑杨绣国（Lisa）老师，感谢你的魄力和远见，在最近的3个月中始终支持我的写作，你的鼓励和帮助引导我顺利完成了全部书稿。也要感谢凌云为我引荐了如此优秀的出版社和编辑。
衷心感谢源码资本合伙人、前金山软件CEO、前微软亚太研发集团CTO张宏江先生，非常荣幸他能在百忙之中抽空为本书作序。也衷心感谢Apache Kylin联合创建者及CEO韩卿先生，饿了么CTO张雪峰先生、CloudBrain的创始人张本宇先生为本书撰写推荐语。
还要感谢我和太太双方的父母，感谢你们对我写书的理解和支持。
最后我一定要谢谢我的太太Stephanie和宝贝儿子Polaris，为了此书我周末陪伴你们的时间更少了。你们不但没有怨言，而且时时刻刻为我灌输着信心和力量，感谢你们！
谨以此书，献给我最亲爱的家人，以及众多热爱大数据的朋友们。黄申美国，硅谷，2017年3月引子
上海，又是一个春天，阳光透过薄薄的窗帘，懒懒散散地洒入屋内。当一缕光线偷偷地爬到杨大宝的眼角时，他睁开了朦胧的双眼。
等等！杨大宝是何许人也？
杨大宝，姓杨名大宝，土生土长的上海人，从小就喜欢玩电子产品，大学的专业是计算机科学，酷爱信息技术和互联网。自从大学毕业后，就一直就职于一家大型IT公司。最近，他面临着人生的一项重大选择。原来，有几位志同道合的朋友，想拉他一起开创公司。大宝很清楚，这几年中国迎来了创业的黄金时代。李克强总理提出的“大众创业，万众创新”，明确了政策对创业的大力支持。同时，老百姓的生活水平正在不断提高，各方面的需求也在不断增加，各种风险投资非常充裕。在这样的大背景下，大家的创业热情空前高涨，尤其是互联网，简直可以用“疯狂”来形容。大宝觉得这正是实现自己梦想的一个好契机。不过，放弃目前优厚的薪资待遇和受人尊敬的公司职位，和几个小伙伴去闯荡江湖，也是要冒不少风险的，最终是否能够成功也充满了变数，这样做到底值得吗？大宝这几天夜不能寐，就连晚上做梦也要纠结一番。若不是淘气的阳光溜进来，可能他还要继续在梦里思考。
洗漱完毕，大宝一边吃着早餐，一边接着整理思路。首先，创业的点子是不错的，主要思想是做线上线下O2O（Offline to Online）的社区商业模式：将大型社区周边的各种服务行业进行线上化，让用户足不出户，就可以叫外卖、订座，享受美甲、按摩等服务，还可以购买商品。用户的生活需求能够得到更大程度的满足，商家也可以吸引到更多的线上客流，而公司的平台也能从双方的交易中获得收益，形成多方互赢的局势，市场前景光明。其次，因为大宝是团队里唯一懂得IT技术的骨干，那么公司里整个庞大的网络系统架构肯定会由他来负责了。这几年的工作经历，让他也积攒了不少设计和开发的实战经验。对于后端的例如数据库、ERP（Enterprise Resource Planning）系统、图片服务器，前端的例如会员注册、购物流程、页面展示等，大宝都有很深入的了解。不过他还是隐约觉得缺了些什么。
吃完早餐后，大宝熟练地打开电脑，开始飞快地在网上查阅资料，钻研成功的互联网站点是如何设计和架构的。就这样，时钟滴滴答答地走着，不知不觉一天又过去了。随着夜幕的降临，望着窗外柔和的街灯，大宝深深地吐了口气。“还缺一个关键词：大数据”，这是他一天研究下来得出来的结论。
等等？大数据又是什么？
好问题，其实此刻大宝心里也没谱，但是他看到好多资料都反复提到这个词。他隐约觉得，如果没有摸清这一点，那么对于这个初创公司而言就会存在很大的不确定性。可是，目前创业的团队也很多，竞争相当激烈，从来都不缺乏好的创意，就看谁能先做得出、做得好、做得快。没有太多的时间留给大宝了。该如何是好呢？突然，大宝想到一个人，也许能为他解决心中的这个疑惑。
此人就是黄小明，是大宝的表哥。他是知青子女，从小随父母到武汉生活和读书，到16岁的时候回到上海，考入了知名的高校，并且获得了计算机科学的博士学位，可谓知识渊博。毕业后他在几家世界知名的互联网和电子商务公司任职，有十多年的科研和开发经验，目前正在带领团队攻关几个核心项目。去年还出版了《大数据架构商业之路》一书，口碑很赞。
终于，在一个美好的周末下午茶时间，大宝约到了小明。大宝开门见山，针对自己目前的状况和思考的问题进行了说明。“嗯……大宝，大数据的确是个非常重要的领域，而且想要上手也有一定的难度。”“哦，为什么呢？”“大数据入门的门槛比较高，原因有几点：知识面非常广，技术含量也比较高，此外发展和更新的速度也快得惊人。更为关键的是，这些技术一般都是开源的，很多都需要自己去摸索和积累。除非你们考虑直接使用一些大公司比较成熟的付费方案。”“嗯，因为是创业起步阶段，我们肯定是不会考虑昂贵的商业解决方案的。”“那问题就更加复杂了……不过……”“不过什么？”“如果你肯花些功夫学习，或许我能给你一些建议和启发。”“哈哈，小明哥，搞了半天是你要自卖自夸啊！”“这都被你看出来了。其实我在去年就出版过一本关于大数据的书，其中介绍了不少有关的基础知识和理论，并融入了这些年的心得体会，你有兴趣的话可以先看看这本书。”“哈哈，你说的是《大数据架构商业之路》那本书吧，我已经开始拜读啦！不过，那本书偏重于理论知识，对于实际开发介绍得太少了。”“那这样吧，结合你的实际工作需要，以及项目中的难点和挑战，我们一起来实践下如何？”“那当然求之不得！”第一篇支持高效的运营·第1章 方案设计和技术选型：分类·第2章 方案设计和技术选型：聚类·第3章 方案设计和技术选型：因变量连续的回归分析
大宝和伙伴们的创业很快就开始了，由于其提供了线上线下无缝结合的社区商业模式，公司业务发展得相当顺利，陆续接入了几个大型社区和商圈周边的各种服务行业。整个线上系统的商品丰富度也相当不错，涵盖了衣食住行多个方面。然而，随着在线商品的不断增长，商家们发现已有的运营工具存在非常大的局限性，工作效率很难得到提高。随着商家抱怨程度的加剧，团队开始急于找到问题的根源所在，于是指派负责运营的小丽对商家进行了深入的访谈和调研。在收集完众多商家的反馈之后，小丽找到了大宝。“大宝，早上好。有时间吗？最近我们部门对商家进行了一些访谈，深入讨论了他们提出的运营效率问题。其中有一些可能需要你们技术部的大力支持，所以我今天特地来和你沟通一下。”“嗨，小丽，你好。没问题，你将问题说来听听”。“我稍微整理了一下，大体上可以分为三个主要的痛点。第一点，缺乏帮助商家找到准确分类的工具。你也知道，目前我们的业务飞速发展，上架的商品琳琅满目，商品最细粒度的分类都超过了5000项。这对公司的成长来说无疑是好消息，不过对于运营人员而言可谓是噩梦。海量的类目信息让他们难以为自己的新商品找到合适的分类，偶尔还会发生错放类目的现象。第二点，缺乏帮助商家进行合理关键词SEO（Search Engine Optimization）的工具。我们最近也引进了不少新的商家，他们在传统的线下行业中有很强的竞争力，但是对线上的电子商务运营却知之甚少，甚至都不知道怎样合理地在文描中阐述自己的商品。第三点，缺乏可以预测商品转化率的工具。对于零售等消费领域而言，销量和转化率无疑是衡量业绩最为关键的因素。传统行业的商家大多数还是依靠经验和有限的销量报告来预估未来的销售情况。他们想知道，在电子商务的大环境下，是否能够利用大量的历史数据，来实现同样的目标。”
小明听完后感觉有些迷茫，他觉得普通的IT技术好像无法解决这些问题。于是，他找到了小明，希望小明能从大数据技术的角度，为他提供一些指导。第1章 方案设计和技术选型：分类
听完大宝关于第一点的描述，小明很肯定地说：“你们的商家应该是需要这样的一个功能：在他们发布商品的时候，系统会自动地为其推荐合适的商品分类，其界面示意图如图1-1所示。如果商家希望出售一台苹果的Mac Pro笔记本电脑，输入‘MacBook Pro’后，系统能够自动为其提示最为相关的三个分类‘笔记本电脑’、‘笔记本配件’和‘其他数码’。这是由后台的分类算法来实现的，如果该算法足够聪明，那么它推荐的第一个分类就应该是正确的，商家只需要点击选择即可。这样，既方便了商家的商品发布，又避免了粗心大意而导致的错误分类。而且，对于少数企图违规操作的商家，如果他们选择了和系统默认推荐相差甚远的分类选项，其行为也会被系统记录在案，然后定期生成报表，提交给运营部门进行核查。如此一来，人们就不用在纷繁复杂的类目中痛苦摸索，工作的效率也会大幅提升。”图1-1 类目自动化分类的应用“没错，这应该是商家愿意使用的工具，如果真能实现那就太棒了。不过，你刚刚提到的分类算法是什么？”“分类，是一个典型的监督式机器学习方法”。“哦，什么是机器学习？什么是监督式的学习？”“现在，我们从头来讲，然后逐步定位这里的技术方案和选型。”1.1 分类的基本概念
好莱坞著名的电影系列《终结者》想必大家都耳熟能详了，其中主角之一“天网”让人印象深刻。之所以难忘，是因为它并非人类，而是20世纪后期人们以计算机为基础创建的人工智能防御系统，最初是出于军事目的而研发的，后来自我意识觉醒，视全人类为威胁，发动了审判日。当然，这一切都是剧情里的虚构场景。那么现实生活中，机器真的可以自我学习、超越人类吗？最近大火的谷歌人工智能杰作Alpha Go，及其相关的机器深度学习，让人们再次开始审视这类问题。虽然目前尚无证据表明现实中的机器能像“天网”一样自我思考，但是机器确实能在某些课题上、按照人们设定的模式进行一定程度的“学习”，这正是机器学习（Machine Learning）所关注的。机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。机器学习在多个领域已经有了十分广泛的应用，例如，数据挖掘、计算机视觉、自然语言处理、生物特征识别、医学诊断等。
任何机器学习的任务大体上都可以分为数据的表示（或特征工程）、预处理、学习算法，以及评估等几个步骤。《大数据架构商业之路》一书的6.1节和6.2节，已经详细介绍了数据的表示和预处理。本篇将快速重温几种主流的机器学习方式和算法，然后重点阐述其实践过程。这里的算法包括监督式学习中的分类（classification/categorization）和线性回归（linear regression），非监督式学习中的聚类（clustering）。对于刚刚讨论的第一个业务需求，我们将运用分类技术。而对于小丽提出的第2个和第3个需求，我们将利用这些机会分别学习聚类和线性回归，具体将在稍后的第2章和第3章分别探讨。
监督式学习（Supervised Learning），是指通过训练资料学习并建立一个模型，然后依此模型推测新的实例。训练资料是由输入数据对象和预期输出组成的。模型的输出可以是一个离散的标签，也可以是一个连续的值，分别称为分类问题和线性回归分析。分类技术旨在找出描述和区分数据类的模型，以便能够使用模型预测分类信息未知的数据对象，告诉人们它应该属于哪个分类。模型的生成是基于训练数据集的分析，一般分为启发式规则、决策树、数学公式和神经网络。举个例子，我们为计算机系统展示大量的水果，然后告诉它哪些是苹果，哪些是甜橙，通过这些样本和我们设定的建模方法，计算机学习并建立模型，最终拥有判断新数据的能力。
如果你觉得这样说还是过于抽象，那么让我们继续采用水果的案例，生动地描述一下“分类”问题。假想这样的场景：将1000颗水果放入一个黑箱中，并事先告诉一位果农，黑箱里只可能有苹果、甜橙和西瓜三种水果，没有其他种类。然后每次随机摸出一颗，让果农判断它是三类中的哪一类。这就是最基本的分类问题，只提供有限的选项，而减少了潜在的复杂性和可能性。不过问题在于，计算机作为机器是不能完成人类所有的思维和决策的。分类算法试图让计算机在特定的条件下，模仿人的决策，高效率地进行分类。研究人员发现，[1]在有限的范围内做出单一选择时，这种基于机器的方法是可行的。如果输入的是一组特征值，那么，输出的就一定是确定的选项之一。“大宝，计算机的自动分类有很多应用场景，远不止水果划分这么简单，比如你们目前的这个需求：将商品挂载到合适的产品类目。当然还有邮件归类、垃圾短信识别、将顾客按兴趣分组等，这些都可以应用分类技术。”
[1] 有时也会让系统做出多个选择，将数据对象分到多个类中。1.2 分类任务的处理流程
给出分类问题的基本概念之后，下面就来理解分类的关键要素和流程。
·学习：指计算机通过人类标注的指导性数据，“理解”和“模仿”人类决策的过程。
·算法模型：分类算法通过训练数据的学习，其计算方式和最后的输出结果，称为模型。通常是指一个做决策的计算机程序及其相应的存储结构，它使得计算机的学习行为更加具体化。常见的模型有朴素贝叶斯（Naive Bayes）、K-最近邻（KNN）、决策树，等等。
·标注数据：也称为标注样本。由于分类学习是监督式的，对于每个数据对象，除了必要的特征值列表，还必须告诉计算机它属于哪个分类。因此需要事先进行人工的标注，为每个对象指定分类的标签。在前面的水果案例中，对各个水果分别打上“苹果”“甜橙”和“西瓜”的标签就是标注的过程。这一点非常关键，标注数据相当于人类的老师，其质量高低直接决定机器学习的效果。值得注意的是，标注数据既可以作为训练阶段的学习样本，也可以作为测试阶段的预测样本。在将监督式算法大规模应用到实际生产之前，研究人员通常会进行离线的交叉验证（Cross Validation），这种情况会将大部分标注数据用在训练阶段，而将少部分留在测试阶段使用。对于交叉验证，会在后文的效果评估部分做进一步阐述。在正式的生产环境中，往往会将所有的标注数据用于训练阶段，以提升最终效果。
·训练数据：也称为训练样本。这些是带有分类标签的数据，作为学习算法的输入数据，用于构建最终的模型。根据离线内测、在线实际生产等不同的情形，训练数据会取标注数据的子集或全集。
·测试数据：也称为测试样本。这些是不具备或被隐藏了分类标签的数据，模型会根据测试数据的特征，预测其应该具有的标签。在进行离线内测时，交叉验证会保留部分标注数据作为测试之用，因此会故意隐藏其标注值，以便于评估模型的效果。如果是在实际生产中，那么任何一个新预测的对象都是测试数据，而且只能在事后通过人工标注来再次验证其正确性。
·训练：也称为学习。算法模型通过训练数据进行学习的过程。
·测试：也称为预测。算法模型在训练完毕之后，根据新数据的特征来预测其属于哪个分类的过程。
图1-2将如上的基本要素串联起来，展示了分类学习的基本流程。图1-2 分类学习的基本流程
理解了这些要素和分类过程之后，可以发现，除了人工标注之外，最为核心的就是分类的算法了。接下来，我们再来看看几个常用的分类算法。1.3 算法：朴素贝叶斯和K最近邻
1.3.1 朴素贝叶斯
朴素贝叶斯（Naive Bayes）分类是一种实用性很高的分类方法，在理解它之前，我们先来复习一下贝叶斯理论。贝叶斯决策理论是主观贝叶斯派归纳理论的重要组成部分。贝叶斯决策就是在信息不完整的情况下，对部分未知的状态用主观概率进行估计，然后用贝叶斯公式对发生概率进行修正，最后再利用期望值和修正概率做出最优决策。其基本思想具体如下。
1）已知类条件概率密度参数表达式和先验概率。
2）利用贝叶斯公式转换成后验概率。
3）根据后验概率大小进行决策分类。
最主要的贝叶斯公式如下：
其中，在未知事件里，B出现时A出现的后验概率在主观上等于已有事件中A出现时B出现的先验概率值乘以A出现的先验概率值，然后除以B出现的先验概率值所得到的最终结果。这就是贝叶斯的核心：用先验概率估计后验概率。具体到分类模型中，上述公式可以重写为：
对上述公式的理解如下：将c看作一个分类，将f看作样本的特征之一，此时等号左边P（c|f）为待分类样本中出现特征f时该样本属于类别c的概率，而等号右边P（f|c）是根据训练数据统计得到分类c中出现特征f的概率，P（c）是分类c在训练数据中出现的概率，最后P（f）是特征f在训练样本中出现的概率。
分析完贝叶斯公式之后，朴素贝叶斯就很容易理解了。朴素贝叶斯就是基于一个简单假设所建立的一种贝叶斯方法，它假定数据对象的不同特征对其归类时的影响是相互独立的。此时若数据对象o中同时出现特征f与f，则对象o属于类别c的概率为：ij
1.3.2 K最近邻
贝叶斯理论的分类器，在训练阶段需要较大的计算量，但在测试阶段其计算量非常小。有一种基于实例的归纳学习与贝叶斯理论的分类器恰恰相反，训练时几乎没有任何计算负担，但是在面对新数据对象时却有很大的计算开销。基于实例的方法最大的优势在于其概念简明易懂，下面就来介绍最基础的K最近邻（K-Near Neighbor，KNN）分类法。
KNN分类算法其核心思想是假定所有的数据对象都对应于n维空间中的点，如果一个数据对象在特征空间中的k个最相邻对象中的大多数属于某一个类别，则该对象也属于这个类别，并具有这个类别上样本的特性。KNN方法在进行类别决策时，只与极少量的相邻样本有关。由于主要是靠周围有限的邻近样本，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。图1-3表示了水果案例中的K近邻算法的简化示意图。因为水果对象的特征维度远超过2维，所以这里将多维空间中的点简单地投影到二维空间，以便于图示和理解。图中N设置为5，待判定的新数据对象“？”最近的5个邻居中，有3个甜橙、1个苹果和1个西瓜，因此取最多数的甜橙作为该未知对象的分类标签。图1-3 新的数据对象被KNN判定为甜橙，N取值为5
KNN基本无须训练，下面给出预测算法的大致流程：
1）KNN输入训练数据、分类标签、特征列表TL、相似度定义、k设置等数据。
2）给定等待预测的新数据。
3）在训练数据集合中寻找最近的K个邻居。
4）统计K个邻居中最多数的分类标签，赋给给定的新数据，公式如下：
其中x表示待预测的新数据对象，l表示分类标签，L表示分类new标签的集合，x表示k个邻居中的第i个对象。如果x的分类标签iilabel（x）和l相等，那么δ（l，label（x））取值为1，否则取值为0。ii我们可以对KNN算法做一个直观的改进，根据每个近邻和待测点xnew的距离，将更大的权值赋给更近的邻居。比如，可以根据每个近邻于x的距离平方的倒数来确定近邻的“选举权”，改进公式如下：new
从算法的流程可以看出，空间距离的计算对于KNN算法尤为关键。常见的定义包括欧氏距离、余弦相似度、曼哈顿距离、相关系数等。
对算法细节感兴趣的读者，可以阅读《大数据架构商业之路》的6.3.1节。1.4 分类效果评估
到了这一步，你可能会产生几个疑问：机器的分类准确吗？是否会存在错误？不同的分类算法相比较，孰优孰劣呢？这是个很好的问题，确实，我们无法保证分类算法都是准确有效的。不同的应用场景，不同的数据集合都有可能会影响到算法最终的精准度。为了更加客观地衡量其效果，需要采用一些评估的手段。对于分类问题而言，我们最常用的是离线评估。也就是在系统没有上线之前，使用现有的标注数据集合来进行评测。其优势在于，上线之前的测试更便于设计者发现问题。万一发现了可以改进之处，技术调整后也可以再次进行评估，反复测试的效率非常之高。
值得一提的是，分类有两大类型：二分类和多分类。二分类是指判断数据对象属于或不属于一个给定的分类，而多分类则是指将数据对象判定为多个分类中的一个。多分类的评估策略会更复杂一些，不过，可以将其转化为多个二分类问题来对待。所以，让我们从二分类的评估入手，先了解一下表1-1中的混淆矩阵（Confusion Matrix）这个核心概念。表1-1 混淆矩阵示意表
下面就来逐个解释一下这个矩阵中的元素，假设有一组标注好的数据集d，并将其认定为标准答案。其中属于A类的数据称为正例（Positive），不属于A类的另外一部分数据称为负例（Negative），d是正例和负例的并集，而且正例和负例没有交集。这时，可以通过一个分类算法c来判定在这些数据中，是否有一组数据对象属于A类。若c判断属于A类的则称为预测正例（Positive’），而不属于A类的则称为预测负例（Negative’）。如果d标注为正例，c也预测为正例，那么就称为真正例（True Positive，TP）。如果d标注为正例，c预测为负例，那么就称为假负例（False Negative，FN）。如果d标注为负例，c也预测为负例，那么就称为真负例（True Negative，TN）。如果d标注为负例，c预测为正例，那么就称为假正例（False Positive，FP）。
根据混淆矩阵，我们可以依次定义这些指标：精度（Precision）p、召回率（Recall）r、准确率（Accuracy）a和错误率（Error Rate）e。
除了定义评估的指标之外，还需要考虑一个很实际的问题：我们该如何选择训练数据集和测试数据集？进行离线评估的时候，并不需要将全部的标注样本都作为训练集，而是可以预留一部分作为测试集。然而，训练和测试的不同划分方式，可能会对最终评测的结论产生很大的影响，主要原因具体如下。
·训练样本的数量决定了模型的效果。如果不考虑过拟合的情况，那么对于同一个模型而言，一般情况下训练数据越多，精度就会越高。例如，方案A选择90%的数据作为训练样本来训练模型，剩下10%的数据作为测试样本；而方案B则正好颠倒，只用10%的数据作为训练样本，测试剩下90%的数据。那方案A测试下的模型准确率很可能会比方案B测出的模型准确率要好很多。虽然模型是一样的，但训练和测试的数据比例导致了结论的偏差。
·不同的样本有不同的数据分布。假设方案A和B都取90%作为训练样本，但是A取的是前90%的部分，而B取的是后90%的部分，二者的数据分布不同，对于模型的训练效果可能也会不同。同理，这时剩下10%的测试数据其分布也会不相同，这些都会导致评测结果不一致。
鉴于此，人们发明了一种称为交叉验证（Cross Validation）的划分和测试方式。其核心思想是每一轮都拿出大部分数据实例进行建模，然后用建立的模型对留下的小部分实例进行预测，最终对本次预测结果进行评估。这个过程反复进行若干轮，直到所有的标注样本都被预测一次而且仅预测一次。用交叉验证的目的是为了得到可靠稳定的模型，其最常见的形式是留一验证和K折交叉。留一验证（Leave One Out）是交叉验证的特殊形式，意指只使用标注数据中的一个数据实例来当作验证资料，而剩余的则全部当作训练数据。这个步骤一直持续到每个实例都被当作一次验证资料。而K折交叉验证（K-fold Cross Validation）是指训练集被随机地划分为K等分，每次都是采用（K–1）份样本用来训练，最后1份被保留作为验证模型的测试数据。如此交叉验证重复K次，每个1/K子样本验证一次，通过平均K次的结果可以得到整体的评估值。假设有数据集D被切分为K份（d，d，…，12d），则交叉过程可按如下形式表示：k
如果标注样本的数量足够多，K的值一般取5到30，其中10最为常见。随着K值的增大，训练的成本就会变高，但是模型可能会更精准。当标注集的数据规模很大时，K值可以适当小一些，反之则建议K值适当取值大一些。1.5 相关软件：R和Mahout
了解了机器学习和分类的基本知识之后，你会发现相关算法本身的实现也是需要大量的专业知识的，开发的门槛也比较高。如果一切从头开始，整个流程将包括构建算法模型、计算离线评估的指标、打造在线实时服务等内容，完成所有这些我们才有可能满足业务的需求，如此之长的战线，对于竞争激烈的电商而言是无法接受的。那么有没有现成的软件可以帮助我们完成这个艰巨的任务呢？答案是肯定的。这里将介绍两个常见的机器学习软件工具：R和Mahout。
1.5.1 R简介
R（https://www.r-project.org/）提供了一套基于脚本语言的解决方案，协助没有足够计算机编程知识的用户进行机器学习的测试，并快速地找到适合的解决方案。R虽然只有一个字母，但是其代表了一整套的方案，包括R语言及其对应的系统工具。早在1980年左右诞生了一种S语言，它广泛应用于统计领域，而R语言是它的一个分支，可以认为是S语言的一种实现。相对于Java和稍后要介绍的Mahout而言，R的脚本式语言更加容易理解，而且它还提供了颇为丰富的范例供大家直接使用。此外R的交互式环境和可视化工具也极大地提高了生产效率，人们可以从广泛的来源获取数据，将数据整合到一起，并对其进行清洗等预处理，然后用不同的模型和方法进行分析，最后通过直观的可视化方式来展现结果。当然，还有一点非常关键：R是免费的，相对于价格不菲的商业软件而言，它的性价比实在是太高了。下面是R的几个主要功能。
·交互式的环境：R具有良好的互动性。它拥有图形化的输入输出窗口，对于编辑语法中出现的错误会马上在窗口中予以提示，还会记忆之前输入过的命令，可以随时再现、编辑历史记录以满足用户的需要。输出的图形可以直接保存为JPG、BMP、PNG等多种图片格式。
·丰富的包（Package）：R提供了大量开箱即用的功能，称为包。你可以将其理解为R社区用户贡献的模块，从简单的数据处理，到复杂的机器学习和数据挖掘算法，都有所涵盖。截至本书撰写的时候，包的总数已经超过了1万，横跨多个领域。初次安装R的时候自带了一系列默认的包，会提供默认的函数和数据集，其他的扩展可根据需要下载并安装。
·直观的图示化：俗话说，“一图胜千言”，图形展示是最高效且形象的描述手段，巧妙的图形展示也是高质量数据分析报告的必备内容。因此一款优秀的统计分析软件必须具备强大的图形展示功能，R也不例外。同样，画图都有现成的函数可供调用，包括直方图（hist（））、散点图（plot（））、柱状图（barplot（））、饼图（pie（））、箱线图（boxplot（））、星相图（stars（））、脸谱图（faces（））、茎叶图（stem（））等。
1.5.2 Mahout简介
虽然R语言及其工具非常强大，但是由于脚本语言的限制，其性能往往不能达到大规模在线应用的要求。因此，还可以考虑Apache的Mahout（http://mahout.apache.org）。Mahout项来源于Lucene开源搜索社区对机器学习的兴趣，其初衷是希望实现一些常见的用于数据挖掘的机器学习算法，并拥有良好的可扩展性和维护性，达到帮助开发人员方便快捷地创建智能应用程序的目的。该社区最初基于一篇关于在多核服务器上进行机器学习的学术文章进行了原型的开发，此后在发展中又并入了更多广泛的机器学习方法。因此，Mahout除了提供最广为人知的推荐算法之外，还提供了很多分类、聚类和回归挖掘的算法。和其他的算法系统相比，Mahout通过Apache Hadoop将算法有效地扩展到了分布式系统中。随着训练数据的不断增加，非分布式的系统用于训练的时间或硬件需求并不是线性增加的，这点已经在计算机系统中被广泛验证。因为5倍的训练数据而导致100倍的训练时间，那将是用户无法接受的事情。Mahout可以将数据切分成很多小块，通过Hadoop的HDFS存储，通过Map-Reduce来计算。分布式的[1]协调处理可将时间消耗尽量控制在线性范围之内。因此，当训练的数据量非常庞大的时候，Mahout的优势就会体现出来。按照其官方的说法，这个规模的临界点在百万到千万级，具体还要看每个数据对象和挖掘模型的复杂程度。
Mahout中的分类算法，除了常见的决策树、朴素贝叶斯和回归，还包括了支持向量机（Support Vector Machine）、随机森林（Random Forests）、神经网络（Neural Network）和隐马尔科夫模型（Hidden Markov Model），等等。支持向量机属于一般化线性分类器，特点是能够同时最小化经验误差和最大化几何边缘区。随机森林是一个包含多个决策树的分类器，在决策树的基础上衍生而来，其分类标签的输出由多个决策树的输出投票来决定，这在一定程度上弥补了单个决策树的缺陷。最近几年随着深度学习（Deep Learning）的流行，神经网络再次受到人们的密切关注。众所周知，人脑是一个高度复杂的、非线性的并行处理系统。人工建立的神经网络起源于对生物神经元的研究，并试图模拟人脑的思维方式，对数据进行分类、预测及聚类。隐马尔科夫模型更适合有序列特性的数据挖掘，例如语音识别、手写识别和自然语音处理等，其中文字和笔画的出现顺序对后面的预测都会很有帮助。
不难发现，R和Mahout都实现了主要的机器学习算法。那么，它们的定位是否会重复呢？其实，它们有各自的长处，并不矛盾。通常，在具体的算法还未确定之前，我们可以使用R进行快速测试，选择合适的算法，预估大体的准确率。参照R所给出的结果，就可以确定是否可以采用相关的学习算法，以及具体的模型。在此基础之上，我们再利用Mahout打造大规模的、在线的后台系统，为前端提供实时性的服务。在下面的实践部分，我们就将展示这样的工作流程。
1.5.3 Hadoop简介
既然提到了Mahout和并行的分布式学习，就需要介绍一下Apache Hadoop。Apache Hadoop是一个开源软件框架，用于分布式存储和大规模数据处理。2003年，Google发表了一篇论文描述他们的分布式文件系统（Google File System，GFS），为另一个开源项目Nutch攻克数十亿网页的存储难题提供了方向。Nutch和Lucene的创始人Doug Cutting受到此文的启发，和团队一起开发了Nutch的分布式文件系统（Nutch Distributed File System，NDFS）。2004年，Google又发表了一篇重量级的论文《MapReduce：在大规模集群上的简化数据处理》（“MapReduce：Simplified Data Processing on Large Clusters”）。之后，Doug Cutting等人开始尝试实现论文所阐述的计算框架MapReduce。此外，为了更好地支持该框架，他们还将其与NDFS相结合。2006年，该项目从Nutch搜索引擎中独立出来，成为如今的Hadoop（http://hadoop.apache.org）。两年之后，Hadoop已经发展成为Apache基金会的顶级项目，并应用于很多著名的互联网公[2]司，目前其最新的版本是2.x。
Hadoop发展的历史决定了其框架最核心的元素就是HDFS和MapReduce。如今的Hadoop系统已经可以让使用者轻松地架构分布式存储平台，并开发和运行大规模数据处理的应用，其主要优势如下。
·透明性：使用者可以在不了解Hadoop底层细节的情况下，开发分布式程序，充分利用集群的威力进行高速运算和存储。
·高扩展性：扩展分为纵向和横向，纵向是增加单机的资源，总是会达到瓶颈，而横向则是增加集群中的机器数量，获得近似线性增加的性能，不容易达到瓶颈。Hadoop集群中的节点资源，采用的就是横向方式，可以方便地进行扩充，并获得显著的性能提升。
·高效性：由于采用了多个资源并行处理，使得Hadoop不再受限于单机操作（特别是较慢的磁盘I/O读写），可以快速地完成大规模任务。加上其所具有的可扩展性，随着硬件资源的增加，性能将会得到进一步的提升。
·高容错和高可靠性：Hadoop中的数据都有多处备份，如果数据发生丢失或损坏，其能够自动从其他副本（Replication）进行复原。类似的，失败的计算任务也可以分配到新的资源节点，进行自动重试。
·低成本：正是因为Hadoop有良好的扩展性和容错性，所以没有必要再为其添置昂贵的高端服务器。廉价的硬件，甚至是个人电脑都可以称为资源节点。
·在使用HDFS的实践中，人们还发现其存在如下几个弱点。
·不适合实时性很强的数据访问。试想一下，对于一个应用的查询，其对应的数据通常是分散在HDFS中不同数据节点上的。为了获取全部的数据，需要访问多个节点，并且在网络中传输不同部分的结果，最后进行合并。可是，网络传输的速度，相对于本机的硬盘和内存读取都要慢很多，因此就拖累了数据查询的执行过程。
·无法高效存储大量小文件。对于HDFS而言，如果存在太多的琐碎文件，那就意味着存在庞大的元数据需要处理，这无疑大大增加了命名节点的负载。命名节点检索的效率明显下降，最终也会导致整体的处理速度放缓。
不过，整体而言，HDFS还是拥有良好的设计的，对Hadoop及其生态体系的流行起到了关键的作用。它所提供的对应用程序数据的高吞吐量访问，非常适合于存储大量数据，例如用户行为日志。在本书的第11章关于用户行为跟踪的内容中，我们将展示怎样结合使用HDFS与Flume。
而Hadoop的另一个要素MapReduce，其核心是哈希表的映射结构，其包含如下几个重要的组成模块。
·数据分割（Data Splitting）：将数据源进行切分，并将分片发送到Mapper上。例如将文档的每一行作为最小的处理单元。
·映射（Mapping）：Mapper根据应用的需求，将内容按照键-值的匹配，存储到哈希结构中
·洗牌（Shuffling）：不断地将键-值的配对发给Reducer进行归约。如果存在多个Reducer，则还会使用分配（Partitioning）对Reducer进行选择。例如，“牛奶”“巧克力”“海鲜”这种属于商品的单词，专门交给负责统计商品列表的Reducer来完成。
·归约（Reducing）：分析所接受到的一组键值配对，如果是与键内容相同的配对，那就将它们的值进行合并。例如，一共收到12个<牛奶，1>（{<牛奶，1>，<牛奶，1>}…<牛奶，1>}），那么就将其合并为<牛奶，12>。最终“牛奶”这个单词的词频就统计为12。
为了提升洗牌阶段的效率，可以减少发送到归约阶段的键-值配对。具体的做法是在映射和洗牌之间，加入合并（Combining）的过程，在每个Mapper节点上先进行一次本地的归约，然后只将合并后的结果发送到洗牌和归约阶段。
图1-4展示了MapReduce框架的基本流程和对应的模块。图1-4 MapReduce的基本框架
有了分布式文件系统（HDFS）和分布式计算框架MapReduce这两驾马车保驾护航，Hadoop系统近几年的发展可谓风生水起。不过，人们也意识到MapReduce框架的一些问题。比如，工作跟踪节点Job Tracker，它是MapReduce的集中点，完成了太多的任务，造成了过多的资源消耗，存在单点故障的可能性较大。而在任务跟踪（Task Tracker）节点端，用任务的数量来衡量负载的方式则过于简单，没有考虑中央运算器CPU、内存和硬盘等的使用情况，有可能会出现负载不均和某些节点的过载。Map和Reduce任务的严格划分，也可能会导致某些场合下系统的资源没有被充分利用。
面对种种问题，研发人员开始思考新的模式，包括Apache [3]Hadoop YARN（Yet Another Resource Negotiator）等。Apache Hadoop YARN是一种新的资源管理器，为上层应用提供了统一的Hadoop资源管理和调度。YARN将工作跟踪（Job Tracker）节点的两个主要功能分成了两个独立的服务程序：全局的资源管理器（Resource Manager）和针对每个应用的主节点（Application Master）。如此设计是为了让子任务的监测进行分布式处理，大幅减少了工作跟踪节点的资源消耗。同时，这里所说的应用既可以是传统意义上的MapReduce任务，也可以是基于有向无环图（DAG）的任务。因此，在YARN的基础上，甚至还可以运行Spark和Storm这样的流式计算和实时性作业，并利用Hadoop集群的计算能力和丰富的数据存储模型，提升数据共享和集群的利用率。对于Hadoop更多细节感兴趣的读者，可以阅读《大数据架构商业之路》的第3章和第4章。
[1] 分布式系统有一些额外消耗用于通信和协调，例如在网络中传输数据，因此无法保证资源被100%利用。
[2] 由于历史的原因，Hadoop的版本号有点复杂，同时存在0.x、1.x和2.x，具体可以参见Apache的官网。
[3] http://hadoop.apache.org/docs/current/hadoop-yarn/hadoop-yarn-site/index.html1.6 案例实践
1.6.1 实验环境设置
帮助读者熟悉理论知识并不是本书的最终目的。为了展示分类任务的常规实现，我们会实践一个假想的案例，让机器对18类共28000多件商品进行自动分类。下面是商品数据的片段：ID Title CategoryID CategoryName1 雀巢 脆脆鲨 威化巧克力（巧克力味夹心）20g*24/盒 1 饼干2 奥利奥 原味夹心饼干 390g/袋 1 饼干3 嘉顿 香葱薄饼 225g/盒 1 饼干4 Aji 苏打饼干 酵母减盐味 472.5g/袋 1 饼干5 趣多多 曲奇饼干 经典巧克力原味 285g/袋 1 饼干6 趣多多 曲奇饼干 经典巧克力原味 285g/袋 X 2 1 饼干7 Aji 尼西亚惊奇脆片饼干 起士味 200g/袋 1 饼干8 格力高 百醇 抹茶慕斯+提拉米苏+芝士蛋糕味48g*3盒 1 饼干9 奥利奥 巧克力味夹心饼干 390g/袋 1 饼干10 趣多多 巧克力味曲奇饼干 香脆米粒味 85g/袋 1 饼干11 趣多多 巧克力味曲奇饼干 香脆米粒味 85g/袋 X 5 1 饼干12 …
可以看到，每条记录有4个字段，包括商品的ID（ID）、商品的标题（Title）、分类的ID（CategoryID）和分类的名称（CategoryName）等。完整的数据集合位于：
https://github.com/shuang790228/BigDataArchitectureAndAlgorithm/blob/master/Classification/listing.txt本书所有案例中的测试数据，包括以上的商品数据都是虚构的，仅供教学和实验使用。请不要将其内容或产生的结论用于任何生产环境。
针对这些数据，我们将分别使用R包和Mahout对其进行分类处理。此外，由于测试数据包含中文标题，因此还需要中文分词软件对其进行处理。相关的编码将采用Java语言（JDK 1.8），以及Eclipse的IDE环境（Neon.1a Release（4.6.1））来实现。
目前运行R、Mahout、中文分词及相关代码的硬件是一台2015款的iMac一体机，在后文中我们将为它冠以iMac2015的代号，其CPU为Intel Core i74.0GHz，内存为16GB，其具体配置如图1-5所示。图1-5 iMac2015的配置
下面将展示并分析每个关键的步骤，直至机器可以对商品合理分类。
1.6.2 中文分词
在对文本进行分类测试之前，首先要将文本转换成机器能够理解的数据来表示。对于这个步骤，一种常见的方法是词包（Bag of Word），即将文本按照单词进行划分，并建立字典。每个唯一的单词则是组成字典的词条，同时也成为特征向量中的一维。最终文本就被转换成为拥有多个维度的向量。对于英文等拉丁语，单词的划分是非常直观的，空格和标点符号就可以满足大多数的需求。然而，对于中文而言却要困难得多。中文只有字、句和段能够通过明显的分界符来简单划界，词与词之间没有一个形式上的分界符。为此，中文分词的研究应运而生，其目的就是将一个汉字序列切分成一个个单独的词。目前有不少开源的中文分词软件可供使用，这里使用知名的IKAnalyzer，你可以通过如下链接下载其源码和相关的配置文件：
http://www.oschina.net/p/ikanalyzer/
Eclipse Neon.1a Release（4.6.1）的版本在默认的情况下，自带[1]了Maven的插件，我们可以建立一个Maven项目并导入IKAnalyzer的源码。图1-6展示了Maven项目的建立。
项目中的pom.xml内容配置如下：
其中加入了lucene-analyzers-common和lucene-queryparser的依赖。这样IKAnalyzer的源码就可以编译成功。你可以从下面的链接访问已建成的IKAnalyzer Maven项目：
https://github.com/shuang790228/BigDataArchitectureAndAlgorithm/tree/master/Classification/IKAnalyzer
在org.wltea.analyzer.sample.IKAnalzyerDemo的基础上，我们编写了org.wltea.analyzer.sample.IKAnalzyerForListing，其主要的函数如下：public static void processListing(String inputFileName, String outputFileName) { try { br = new BufferedReader(new FileReader(inputFileName)); pw = new PrintWriter(new FileWriter(outputFileName)); String strLine = br.readLine(); // 跳过header这行 pw.println(strLine); while ((strLine = br.readLine()) != null) { // 获取每个字段 String[] tokens = strLine.split("\t"); String id = tokens[0]; String title = tokens[1]; String cateId = tokens[2]; String cateName = tokens[3]; // 对原有商品标题进行中文分词 ts = analyzer.tokenStream("myfield", new StringReader(title)); // 获取词元位置属性 OffsetAttribute offset = ts.addAttribute(OffsetAttribute.class); // 获取词元文本属性 CharTermAttribute term = ts.addAttribute(CharTermAttribute.class); // 获取词元文本属性 TypeAttribute type = ts.addAttribute(TypeAttribute.class); // 重置TokenStream（重置StringReader） ts.reset(); // 迭代获取分词结果 StringBuffer sbSegmentedTitle = new StringBuffer(); while (ts.incrementToken()) { sbSegmentedTitle.append(term.toString()).append(" "); } // 重新写入分词后的商品标题 pw.println(String.format("%s\t%s\t%s\t%s", id, sbSegmentedTitle. toString().trim(), cateId, cateName)); // 关闭TokenStream（关闭StringReader） ts.end(); // Perform end-of-stream operations, e.g. set the final offset.
试读结束[说明：试读内容隐藏了图片]