搜索
第五章经典的机器学习案例机器学习是一门成熟的学科，它所能解决的问题涵盖多种行业。本章介绍了四种经典的机器学习算法，它们所关心的重点在于机器学习是如何将统计学和数据挖掘连接起来的。通过学习本章，读者可以见识到机器学习的特殊魅力，并明白机器学习与其他学科的异同。使读者可以熟练地应用机器学习算法来解决实际问题是本章的目标。5.1机器学习综述在正式开始了解机器学习之前，我们首先要搞清楚这样一个问题：世界上是不是所有的问题都可以使用一行一行清楚无误的代码解决？举个例子，倘若我们想让一个机器人完成出门去超市买菜并回家这一任务，我们能不能在程序里详详细细地把机器人所有可能遇到的情况以及对策都写下来，好让机器人一条一条按着执行？答案是“很难”。机器人在路上可能遭遇塑料袋儿、石头、跑动的儿童等障碍物，在超市可能遇到菜卖完了、菜篮挪动了位置等问题，把这些问题全部罗列出来是不太可能的，因此我们就难以使用硬性的、固定的程序来命令机器人完成这件事，我们需要的是一种灵活的、可以变化的程序。就像你去买菜时不用你妈告诉你路上看见有人打架要躲开，你就知道要躲开一样（即便你以前从来没有遇见过这种情况），我们希望机器人也可以根据经验学习到正确的做法，而不是必须依赖程序员一条一条地输入“IF……THEN……”。美国人塞缪尔设计的下棋程序是另一个的经典机器学习算法。塞缪尔设计了一个可以依靠经验积累概率知识的下棋程序，一开始这个程序毫无章法，但四年以后，它就能够打败塞缪尔了，又过了三年，它战胜了美国的围棋冠军。这个下棋程序进步的方式和人类学习下棋的过程非常类似，如何让机器像人类一样学习，正是机器学习关心的事情。不难想象，机器学习是一门多领域交叉的学科，它主要依赖统计学、概率论、逼近论等数学学科，同时也依赖算法复杂度、编译原理等计算机学科。通俗的说，机器学习首先将统计学得到的统计理论拿来进一步研究，然后改造成适合编译成程序的机器学习算法，最终才会应用到实际中。但机器学习和统计学仍有不同的地方，这种差异主要在于统计学关心理论是否完美，而机器学习关心实际效果是否良好。同时，机器学习侧重于归纳和总结，而不是演绎。机器学习将统计学的研究理论改造成能够移植在机器上的算法，数据挖掘将机器学习的成果直接拿来使用。从这一意义上来说，机器学习是统计学和数据挖掘之间的桥梁。机器学习也是人工智能的核心，机器学习算法普遍应用于人工智能的各个领域。此外，机器学习和模式识别具有并列的关系，它们一个注重模仿人类的学习方式，一个注重模仿人类认识世界的方式。因此机器学习、数据挖掘、人工智能和模式识别等本来就属于一个不可分的整体，离开其他学科的支持，任何学科都难以独立生存下去。本章介绍了语义搜索、顺序分析、文本分析和协同过滤这四种经典的机器学习算法，它们不仅理论完善，同时也具有广泛的应用。通过本章的学习，读者将看到机器学习在各行各业中的神奇作用以及广阔前景，并学会如何使用机器学习算法来解决实际问题。5.2语义搜索——沃尔玛搜索引擎提升15%销售额语义搜索是21世纪最被看好的IT技术之一，如今各大厂商都在积极投资语义搜索相关的基础设施。未来的互联网务必是语义搜索的天下。本小节介绍了语义搜索和寻常搜索不同的地方，以及它所能完成的事情。并使用沃尔玛开发的北极星语义搜索系统为例，剖析了语义搜索的技术原理和各项特性。5.2.1注重用户体验的沃尔玛公司我们在第二章和第四章中已经看到大数据分析是如何在零售业起作用的，实际上，在大数据的冲击下，零售业正面临巨大的挑战。众所周知，如今的零售业利润十分微薄，同时电商又瓜分走了一大块市场，传统的百货公司正面临巨大的压力。创建于1962年的沃尔玛超市是全球最大的连锁超市。它在27个国家拥有超过一万个门店，员工总数220万余人，每周接待2亿人次的顾客。这样一个雄踞全球零售业榜首的庞然大物，也有自己难以言明的烦恼。2015年初，分析师预言阿里巴巴将很快取代沃尔玛，成为全球最大的零售企业。来自中国的威胁固然不可轻视，但美国公司亚马逊网站则让沃尔玛产生更大的危机感。电商网站能够给消费者提供价格低廉、种类丰富的产品，沃尔玛企业所创办的沃尔玛网站固然也有不错的收益，但随着线上零售占据越来越多的零售市场份额，沃尔玛在沃尔玛网站上投入了越来越多的精力。沃尔玛一直秉承“帮顾客省每一分钱”的宗旨，并在进货渠道、分销方式以及营销费用、行政开支等各方面节省资金。物美价廉一直是沃尔玛的一大优势，但不幸的是，亚马逊平台在这一方面并不逊色于沃尔玛。因此，为了反超亚马逊平台，沃尔玛势必要在用户体验方面做出突破。零售业的用户体验法则大多都是关于货品摆放规则的，将牛奶和面包摆在一起，将口香糖摆到收银台附近等都是经典的货物摆放规则，合理的摆放方式能够替顾客节省搜寻货物的时间，提高顾客的用户体验。这种规则同样适用于电子商务网站，如果在顾客搜索产品时，能迅速将顾客想要的商品展示出来，用户体验想必会大大提高。沃尔玛希望通过改善搜索引擎提高15%的销售额，这意味着搜索引擎必须有质的飞跃才能达成这一高远的目标。沃尔玛采用的北极星搜索引擎主要模仿了Kosmix的语义搜索技术和语义分析技术，前者从用户在社交平台上发出的推特、和其他用户之间的互动行为中挖掘出用户的购物倾向，后者则度量产品之间的相关度和相似度，包括产品、人物、事件之间的关联。以上两种技术使北极星搜索引擎能够为顾客提供更精准地产品链接，此外北极星在确定产品排名时还引入了顾客的搜索记录。这种解析关键词和挖掘同义词的搜索方法可以给顾客提供更合理的产品，从而提高用户体验。5.2.2语义搜索引擎的底层技术和原理搜索引擎是每个人都十分熟悉的一项服务，具体来说，首先用户在搜索栏中输入搜索关键词，如“春季碎花外套”，其次搜索引擎将关键词切割为“春季”、“碎花”和“外套”，再次搜索引擎从所有的网页中抓出网页标题包含这三个关键词网页，并按照一定的规则排列展示给用户。以上是传统搜索引擎的工作模式，这种工作模式合情合理，但仍具有疏漏。比如在上文的例子中它只会推荐标题是“春季碎花外套”的网页，而不会推荐标题是“春季小花外套”的网页，并且认为标题是“春季碎花上衣”的网页和标题是“春季碎花短裤”的网页同样不重要。我们不能一条一条地告诉搜索引擎“碎花”等同于“小花”、“上衣”比“外套”更重要等网页排序规则，这是因为首先这些规则非常多，其次这些规则总是在变化。好在语义搜索引擎能够通过学习，智能化的分辨关键词之间的细微不同，并捕捉到用户搜索关键词的真正含义。从根本上解决以上问题。图5.1语义搜索引擎体系结构图5.1是一个语义搜索引擎的体系结构，它分成七层，越往下越接近底层技术，越往上越接近具体的搜索规则和网页。Unicode和URI所代表的字符集层以及XML+NS+xmlschema所代表的根标记语言层是搜索引擎的基础设施，RDF层则提供词汇嵌入的框架，这一层将多种词汇集中起来描述Web资源。这三层都属于搜索引擎的基本构架，它们支撑着搜索引擎的正常运转。从Ontologyvocabulary层向上就是语义搜索引擎的核心内容了。Ontologyvocabulary的意思是本体词汇表，这一层用于支持知识库的搭建。本体是一种术语的集合，它把现实世界的物体用一组一组的术语描述出来。例如，上衣这一本体可以由{季节性、长度、薄厚、风格、颜色}等概念构成，而季节性这一概念又成为一个单独的本体，由{春、夏、秋、冬}构成，长度由{短、中、长}构成……将这些本体合起来，就得到了本体词汇表。本体词汇表可以由半监督的形式形成，即根据以往累积的用户搜索记录提取得到高频率出现的词汇，并人工汇总本体词汇表。不同语义搜索引擎的本体词汇表很可能不同，如沃尔玛百货搜索引擎中就不会收录关于“数据分析”等科技类的本体词汇。有了本体词汇表，知识库就能够将某一确定的关键词转化为一组概念的集合，并搜索到相关联的网页。图5.2网页文档和网页数据的对应关系当用户在搜索栏输入关键词后，语义搜索引擎将找出与关键词相似度高的词语和相关度高的词语，相似度高指的是两组词语具有互相代替的关系，比如“碎花”可以用“小花”代替；相关度高指的是两组词语总是伴随出现，比如“数据分析”和“数据挖掘”总是同时出现。语义搜索引擎将网页中的相似词和相关词找出来，并根据这些词语的多寡按照一定规则排序。图5.2展示了搜索引擎怎样从网页文档中提取出有效数据来。图中每个纸张图形都代表一个真实的网页文档，网页文档中包含的相关词和相似词则用图形中的蓝色圆点表示。网页文档中圆点越多，该文档的重要性就越高。向搜索引擎中引入相似度和相关度的概念将改变原有网页的排列顺序，有些网页未必包含了所有的用户搜索关键词，但只需包含大量相似关键词和相关关键词，即可获得较好的排名。图5.1中的Logic、Proof、Trust层用于规则的推理和验证。它们通过逻辑推理对关键词、关键词之间的关系以及搜索结果排列顺序的合理性进行验证。这种验证技术主要基于Proof交换和数字签名技术，它一方面将钓鱼网站和伪装成优质网站的劣质网站剔除，另一方面预防不合理的网页排序结果，从而确保了良好的用户体验。5.2.3语义搜索技术小结本小节介绍了语义搜索技术的七层结构，以及本体词汇层中本体的概念和知识库的工作原理。在语义搜索技术的七层结构中，本体词汇层是最重要的一层，它使搜索引擎能够像人类一样真正“理解”不同关键词之间的联系和区别，并根据用户真正的意图排列相关网页。语义搜索技术是多种技术的综合体现，本小节仅介绍了本体论和相关度、相似度等几个概念，此外，语义搜索引擎的好坏还依赖于分词技术的好坏。在分词技术中，粒度是最重要的概念，它指的是关键词划分的粗细程度。比如，“碎花外套”分成“碎花”和“外套”时，粒度就较大；分成“碎”、“花”和“外套”是，粒度就较小。粒度较小的分割方法使得搜索引擎反馈的网页更准确；粒度较大的分割方法则使搜索引擎反馈的速度更快。为了提高语义搜索引擎的准确度，工程师还会向引擎中引入用户的以往浏览数据，比如当用户搜索“苹果价格”时，搜索引擎难以判断用户想搜的是水果的价格还是手机的价格，此时如果发现用户的以往搜索记录和浏览记录中电子产品相关的词组高频出现，则可断定用户想问的是手机的价格。不难理解，语义搜索引擎实际上应用的是一种概率知识，苹果和橘子在同一篇文章中出现的概率高于苹果和面包，因此苹果和橘子相关度高于苹果和面包。这种通过概率学习的方法与人类通过经验学习生活知识的方法十分类似，但它仍然不能像人类一样理解更深层的知识，即苹果和橘子都是水果，而面包则是一种谷物加工食品。作为一种新兴的高度智能化技术，语义搜索技术拥有难以想象的广阔前景。当我们搜索某一城市的名称时，它能够同时给出车票信息、天气信息、旅游热点信息、酒店信息等，程序不可能理解什么叫“旅游”，但它知道搜索了这一城市的人大部分都关注了这些信息，因此它也将这些信息推荐给你。这种人性化的智能机制能够应用于购物网站、医疗系统、图书馆系统等各种程序中，这会使人类的搜索行为更加有效。如今已有十几种成熟的语义搜索引擎上市，除去本小节提到的北极星系统外，较著名的还有Kngine、Hakia、DuckDuckGo等搜索系统。但语义搜索引擎仍是一种处于起步阶段的技术，它的阻碍主要体现在两方面：首先，数据网络的支持并不完善，不同网页采取的不同信息标准造成了数据分享方面的困难，网页的源码中也需要标注标签，以便搜索引擎快速抓取每个网页的主要内容；其次，语义分析的智能化程度仍然不够高，如今的算法程序仅能从表层理解世界，这意味着一个算法要比人类用掉更多的信息和计算空间才能像人类一样聪明。尽管存在重重的难关，但语义搜索技术一旦被广泛应用，其产生的效益是不可估量的，因此语义搜索的概念一经问世，即成为多个领域关注的热点。在语义搜索技术引擎的XML、RDF和Ontology这三项关键技术中，XML和RDF技术的实现依赖于计算机工程师，而Ontology技术则主要使用了概率的知识来提取文本文档中的知识，因此语义搜索引擎的成熟正需要数据分析师和网络工程师的通力协作，无论缺少这两种人才中的哪一