读书笔记——智能Web算法

智能Web算法

这本书的知识量还是不小的,基本机器学习在Web中的应用面面具到了,不过书以java为主,所以我不一定都会尝试实验,但所有相关的应用都学习一遍还是有必要,相信机器学习是一种特殊的技术,基本上任何一个和数据有关的系统(而现在的系统基本上都可以和数据有关)都可以使用,所以认真学习一边还是有必要的。那就一个个来了。

书中很多代码写的都有一些不够好,用的我不喜欢的JAVA啊,或者在框架里直接用的裸代码(明明可以封装很好),包括有一些实现其实也不是那么合理……,但是可读性还是很高的,真的还是很清晰的了解到实现,并且能够想象到应用,所以最让我不爽的是代码,最让我爽的大概也是代码…。

搜索

只讨论文本搜索

其实最简单的搜索莫过于全文匹配,然后返回匹配结果。
但这有几个问题:

第一、数据从哪里来,爬虫,那爬虫如何识别重复页面;
第二个,当数据量变大如何存储大量数据;
第三个问题,每次全文匹配代价过大,速度肯定会随着数据量级线性上升(O(n)),这个在应用中基本上是不可忍受的;
第四个问题,当解决了前面的问题,就会遇到更人性化的问题,返回的结果很多很多,如何让用户最想翻阅的资料非常靠前或者就在第一个。

这本书的这一章,重点只放在了我提的第四个问题,如何让搜索的结果更智能,其他的问题等以后有相关的知识再写博客。

所以一般搜索分为几个部分:
爬取->解析->分析->索引->搜索

爬取,顾名思义就是爬取咯,爬取好要搜索的文档,包括.txt, .html, .pdf, .doc各种格式。感觉要防止重复,很可能两个链接到同一个页面,但URL参数稍有不同被保存下来多份。
解析,就是将不同格式的数据转化为统一格式数据,嗯哼,很熟悉的桥段,可以使用设计模式中的原型模式来生成统一的文本格式,在Lucene中就是生成统一的Document类。
分析,不仅仅用于搜索,这是有广泛应用价值一种语义理解器,应用在搜索中就是将不重要的词汇忽略掉(如”的“,”你“,”我“…等),只保留重要的核心的词汇。
索引,这里的索引和数据库里的索引应该是同一个物体,就是可以加快搜索的某种数据结构,但它只对分析器给出的”重要核心词汇“做索引。
搜索,将用户输入的关键字在索引中搜索,然后返回相关的供用户浏览。

但搜索不应该只是索引,因为只要是列表就一定会有顺序,如果让索引的算法来决定顺序,一些广告/垃圾网页精心制作适应算法的产物,让用户期望的网页不在最上面,这样用户体验就非常糟糕。

因此智能分析登上历史舞台,书中提到了两个:链接分析(客观重要性)和用户点击(主观用户个性),书中虽然细节涉猎不多,但是极大的扩展了我的想象力。

PageRank我还是不做介绍了吧,确实都被说烂了。

书中的公式p(k + 1) = p(k) * H是不符合线性代数的,应该是p(k + 1) = H * p(k),p(k)是列向量表示重要性,H的每一列代表一个网站的对外链接。
另外书中的用例直接用的二位数组,这个不能满足我的求知欲,我想深入稀疏矩阵的存储和计算。

我想在用户点击优化搜索这里多费一点笔墨,因为这里确实启发到我。当然也不是说PageRank没有启发到,只是因为很早就学过,当时大概是震惊的吧,但现在也不以为意了。

链接分析可以得到一个网页的客观上的重要性,但是没有考虑到每个用户的喜好,而点击分析就会考虑到用户的喜好。文中使用朴素贝叶斯,如果A用户上次点击了B网页,那么下次A用户再搜索同一个关键词的时候,B页面的比重会提高。

这就给了我很多想象,比如在搜索Linux相关的知识的时候,我可能希望点开的是我曾经点开过的页面,因为我可能回过头找曾经打开过的某个网页,这是书中提到的作用。或者我希望某些网站上的信息,比如我偏好点击知乎上的网页,在我搜索会自动将知乎的排名都提高一些;再或者我平时搜索Linux相关的知识的时候,我点英语页面点的更多,那我下次搜Linux相关页面的时候(如搜gentoo)的时候,英语页面的排名也可以提高一些,而搜索其他页面的时候,英文的比重依旧不变。

文中还提到了在美国搜索选举,在英国搜索选举应该是完全不同的页面……

感觉让用户体验变好是一件维度非常高,可以一直有极度创造力的事情。这一点上,这本书给我的启发真的是非常多的。

推荐系统

因为做了几年图像和机器学习,所以大部分知识都是很熟悉的,描述距离相似度的就略过了。

推荐现在主流就两种方法,协同推荐和基于内容的推荐。应用最广泛的还是前者,因为后者需要对内容进行分析,如NLP,理解语音理解视频之类,目前技术水平有限,所以效果也一般,但将来某一天说不定可以直接基于内容给用户推荐了。

嗯…给自己看的笔记,能用人话说的绝对不画图;要画图的绝对只在笔记本上,搬上来太麻烦,懒。

协同推荐

基于用户推荐

举个例子,简单的说就是寻找和你喜好相同的用户,然后推荐他们喜欢的条目。

用音乐举例子,比如你点开私人FM,系统就会给你推荐一首歌,系统会建立一个方法衡量用户和用户之间的相似度,具体做法是用一个大大的向量代表一个用户对系统所有歌曲的评分(未听过的为空或这为0,随便什么,并不重要),用户对系统而言就是一个巨大的向量了,再用某种相似度的函数来衡量用户和用户之间的相似度,书中用的是两个用户对同一首歌曲的评分相同的数目除以两个用户共同评价过的总歌曲数,当然还有很多都可以。

建立起了用户和用户之间的相似度函数之后,再向用户推荐歌曲就是遍历所有歌曲,将其他用户对一首歌的评分乘以两个用户之间的相似度,累加起来,排序,取排名最高的,最近没听过的歌曲就是私人FM里在放的歌曲了。

基于条目推荐

依然用音乐作为例子,基于条目推荐就像音乐中的相似歌曲,听过一首非常抒情的音乐,想找类似曲风的歌曲来听,认为标记所有的歌曲之间的相似度…想想都觉得可怕,这里肯定要用到自动化,即机器学习。

具体怎么做呢,这样。

和基于用户类似,如果能做一个评分系统评价两首歌曲之间的相似度,想想是不是都简单了很多。那就从衡量两首歌曲来说,用所有用户对一首歌的评分作为向量,计算两个歌曲向量的相似度;书中是寻找所有对两首歌都做过评价的人,用对两首歌评分相同的用户数处以同时对两首歌评分的用户数。

建立起了歌曲之间的评分之后,相似歌曲推荐就是枚举所有歌曲,计算歌曲之间的相似度,推荐相似度最高的歌曲即可。当然歌曲可能评分不如豆瓣那样直接,我也只是举一个例子,完全可以换成豆瓣。具体听歌软件怎么去评价一个用户对歌曲的评分,可以通过用户切换啊,红心啊,丢进垃圾箱啊,单独拿出来听啊……通过这些操作赋予不同的分值嘛。而且用户之间的相似性还可以使用GPS啊,年龄啊,或者其他一些社交的数据来做,所以想象空间还是很大的。

基于内容的推荐

基于内容的推荐需要用户间的,条目间的或者用户与条目间内容的相似性,所以即使没有评分数据也可以很好的工作。

简单的说,就是要让机器能读懂文章,并且自动知道这些文章在说类似的东西,为什么说文章而不是歌曲呢,因为…让机器理解文章可能比理解歌曲要容易一些,毕竟直接用分析器(前一章提到过)就能提取重要词汇了。也许通过让两篇重要词汇相似的文章相似来建立其文章之间的评价体系(基于内容的比较),并且以此为基础建立推荐系统。

其实建立好条目(文章,歌曲…这些都算条目)和条目的相似度评价,就可以建立起推荐系统。那这个和协同推荐最大的区别就是协同推荐是基于历史用户对条目的喜好数据分析的到的相似度;而基于内容的推荐就是直接让机器理解条目的内容,比如我在阅读百度文库某篇文章,底下推荐某些其他的文献可能就是基于内容进行推荐的。

基于内容的推荐强不强主要在于分析器是否足够强大,对人类对条目的理解是否足够真实。

二合一——基于内容+协同推荐

其实两种推荐算法还是可以存在一些共同点,用户对条目的喜好总会存在,可以基于内容+协同推荐合作来推荐一些条目。

但自然也存在问题,如何协作,即:如何评价条目与条目之间的相似性?

直接让两种不同算法计算出来的分数加权相加?可以

一部分推荐来源于内容推荐,一部分来源于协同推荐?可以

讨论一下第二种,每种推荐算法推荐一部分条目,那如何对i条目排序?

这里需要做一些数据标准化,数据重新标度的工作。就是将两种不同的评分体系建立其一个对比机制,就像雅思和托福都是英语考试,他们之间的分数范围不同,计算不同,如果一个学校两种考试都接受的话,就需要一个将两种分数计算成一种统一的评价分数的算法。

嗯 ~ 推荐系统就说这么多了

分类

一般来说,采用的维数越多,分类的效果越好,但也有一个警戒线,处理大量属性时会遇到叫“维度灾难”的问题,这个大量是属性大于16个。“维度灾难”是随着维度的增加,属性空间会变得越来越同质化,无论用什么距离度量,任意两点的距离会变得大致相等。

分类器概述

纵观所有分类系统,可以划分为两大类——二分类和多分类。二分类就是回答是否的问题,如这个数据点是否属于X分类?如医疗诊断系统。多分类可以细分为是连续的还是离散的;多个类别是“平坦”(只是标签列表)还是有层次结构的。

还有一些技术分类就不如上面清晰,统计算法和结构算法都可用于分类。

统计又有三个主要分支,回归算法擅长做连续变量的预测;基于贝叶斯理论的算法以及贝叶斯网络。贝叶斯网络把贝叶斯理论和概率网络结构组合起来,用于描述分类问题中多个变量间的依赖关系。

结构算法也有三个分支:基于规则的算法,包括if-then和决策树;基于距离的算法;神经网络。

邮件的自动归类与垃圾邮件过滤

使用标题和正文中的关键字来确定邮件是否为垃圾邮件,当然还可以使用一些发送邮件的用户的黑白名单等作判断,但这里只用到标题和正文中的关键字。

朴素贝叶斯分类

书中将分类的结构定义为本体,由概念(Concept),实例(Instance)和属性(Attribute)组成。放在邮件分类系统中,概念就是是否为垃圾邮件(二分类)或者是邮件类别(多分类);实例就是一封封邮件;属性就是邮件的标题和正文中的那些关键字。将概念/分类用X表示,实例/邮件用Y表示。

朴素贝叶斯分类的基础就是贝叶斯公式的应用,p(x|y)=p(y|x)*p(x)/p(y)

那么最后看P(垃圾邮件|y)和P(非垃圾邮件|y)哪个概率大,结果即为哪一个。

其中p(x)很好算,就是垃圾邮件在所有邮件中占的比例和非垃圾邮件在所有邮件中占得比例,另外邮件本身的概率p(y)可以忽略,因为每个邮件的分母都是相同的,节省计算力。

还一个很重要的就是p(y|x)的计算:p(y|x)=p(a1a2..an|x)=p(a1|x)p(a2|x)…p(an|x),即转化为属性/关键字的计算。

书中还有一个将相似词语融合的函数,即如果两个词语的距离足够近,则表示为一个词语。这个距离是在语义方面的距离。

基于规则的分类

基于规则的分类系统由事实,规则引擎和规则构成,事实就是数据;规则是如果怎样就怎样的list;规则引擎是执行规则的程序。

因为这个方法和机器学习关系不大,从数据中学出规则(决策树)算是一个机器学习,但规则如何控制判断结果没有关系,所以就不展开说了。

不过书中提到一个有意思的设计模式,StatefulSession是为另一个类提供异步的方法。这个挺有意思的,本不支持异步的系统,使用这个类负责保存同步的状态,实现异步的接口。可以考虑添加到我的网络模块中去。仔细一想,本书也有不少设计模式的实现和介绍,只是这个设计惊艳到我才忽然感觉到。

神经网络做欺诈检测

书中没有涉及梯度下降和反向传播的细节,因此还是很好读的,大意就是用交易的金额,用户ID和交易的地址作为输入,是否为欺诈交易作为输出。自动训练出一个适应数据的模型。

结果是否可信

书最后提到了这个主题,用正确率来表示不是唯一的标准,举一个例子:

(以下数据都是我瞎掰的,理解意图即可)医院中检查癌症,正确率高的系统不一定可用。癌症在人群中的出现概率只有0.01%,那么我直接判断所有人都是没有癌症的。这个正确率

就高达99.99%,然而这个系统不能够使用。

对于二分类,确定结果是否可信要看四个参数,T判断为T的比例,T判断为F的比例,F判断为T的比例,F判断为F的比例。

这些参数有专业术语的,但我忘了,ahhh。

这一章大概就是这样,挺凌乱的,但关于分类还是介绍了不少。

分类器组合

我的毕业设计也是如此,单个算法总是只是用了片面的信息,需要组合所有信息就需要组合不同的算法。

本章设计了一个情景,将三种(神经网络,朴素贝叶斯和决策树)分类算法先单独使用,再组合使用,以查看效果。

提出了三种比较分类器效果的方法:McNemar检验;差额比例检验和Cochran Q检验与F检验。前面两个用于比较两个分类器,后面一个可以比较多个分类器。

再提出了两个组合分类器的方法:一个是bagging,将多个分类器用数据中的不同子集进行训练,检验时由所有的分类器投票决定结果;另一个是boosting,迭代提高的方法,与bagging训练不同,boosting每次迭代使用的数据都是上一次迭代中错判的部分,最后的结果依然是投票决定。

 

最后一章是奖算法综合应用在一个“虚拟业务”中,没什么新知识,就不做笔记了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注