数据挖掘以及搜索引擎经典幻灯片.ppt

《数据挖掘以及搜索引擎经典幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据挖掘以及搜索引擎经典幻灯片.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据挖掘以及搜索引数据挖掘以及搜索引擎经典擎经典第1页，共34页，编辑于2022年，星期六OutlineBasic WWW TechnologiesWeb的基本概念Basic Crawling基本的爬取算法第2页，共34页，编辑于2022年，星期六URI：Uniform Resource Identifier-Uniform Resource IdentifiersURL:Uniform Resource LocatorsURN:Uniform Resource NamesEvery resource available on the Web has an address that may b

2、e encoded by a URL URIs typically consist of three pieces:The naming scheme of the mechanism used to access the resource.(HTTP,FTP)The name of the machine hosting the resourceThe name of the resource itself,given as a path第3页，共34页，编辑于2022年，星期六URL,URN与与URI的关系的关系URL,URN是是URI的子集的子集。URI是以某种统一的（标准化的）方式标识

3、资源的简单字符串。URI一般由三部分组成：1.访问资源的命名机制。2.存放资源的主机名。3.资源自身的名称，由路径表示。第4页，共34页，编辑于2022年，星期六URI Examplehttp:/www.w3.org/TR There is a document available via the HTTP protocolResiding on the machines hosting www.w3.orgAccessible via the path/TR第5页，共34页，编辑于2022年，星期六Hypertext Transfer Protocol(HTTP)A connection-o

4、riented protocol(TCP)used to carry WWW traffic between a browser and a serverOne of the transport layer protocol supported by Internet HTTP communication is established via a TCP connection and server port 80第6页，共34页，编辑于2022年，星期六On a Web server or Hypertext Transfer Protocol daemon,port 80 is the po

5、rt that the server listens to or expects to receive from a Web client,assuming that the default was taken when the server was configured or set up.A port can be specified in the range from 0-65536 on the NCSA server.However,the server administrator configures the server so that only one port number

6、can be recognized.By default,the port number for a Web server is 80.Experimental services may sometimes be run at port 8080 第7页，共34页，编辑于2022年，星期六GET Method in HTTP第8页，共34页，编辑于2022年，星期六HTML HyperlinkalumniA link is a connection from one Web resource to anotherIt has two ends,called anchors,and a dire

7、ctionStarts at the source anchor and points to the destination anchor,which may be any Web resource(e.g.,an image,a video clip,a sound bite,a program,an HTML document)第9页，共34页，编辑于2022年，星期六Anchor test(锚文本）锚文本）Anchor text is the hyperlinked words on a web page-the words you click on when you click a l

8、ink.Heres an example,reciprocal links,in which“reciprocal links”is the anchor text.锚文本主要是为访问者提供指向网页内容的说明。第10页，共34页，编辑于2022年，星期六OutlineBasic WWW TechnologiesWeb的基本概念Basic Crawling基本的爬取算法第11页，共34页，编辑于2022年，星期六WebWeb是一个有向图是一个有向图网页为节点网页中的HyperLink为有向边Crawl=图遍历,right?第12页，共34页，编辑于2022年，星期六Completeness Ob

9、servationsCompleteness is not guaranteed假设从一个page出发能到达web上的任何一个page.实际情况并不一定这样How to make it better:more seeds,more diverse seeds,port scanner maybe help第13页，共34页，编辑于2022年，星期六常用算法常用算法Depth First SearchWidth First Search第14页，共34页，编辑于2022年，星期六Depth-First Search1234567numbers=order inwhich nodes arevis

10、ited 8910第15页，共34页，编辑于2022年，星期六Depth-First SearchPROCEDURE SPIDER(G,SEEDS)Initialize COLLECTION/结果存结果存储储Initialize VISITED/已访问已访问URL列表列表For every ROOT in SEEDSInitialize STACK/待爬取待爬取URL栈栈 Let STACK:=push(ROOT,STACK)While STACK is not empty,Do URLcurr:=pop(STACK)Until URLcurr is not in VISITEDinsert-

11、hash(URLcurr,VISITED)PAGE:=look-up(URLcurr)/爬取页面爬取页面STORE(,COLLECTION)For every URLi in PAGE,/链接提取链接提取push(URLi,STACK)Return COLLECTION第16页，共34页，编辑于2022年，星期六Width-first Search12563710numbers=order inwhich nodes arevisited 489第17页，共34页，编辑于2022年，星期六Width-first SearchPROCEDURE SPIDER(G,SEEDS)Initialize

12、 COLLECTION/结果存储结果存储Initialize VISITED/已访问已访问URL列表列表For every ROOT in SEEDSInitialize QUEUE/待爬取待爬取URL队列队列 Let QUEUE:=EnQueue(ROOT,QUEUE)While QUEUE is not empty,Do URLcurr:=DeQueue(QUEUE)Until URLcurr is not in VISITEDinsert-hash(URLcurr,VISITED)PAGE:=look-up(URLcurr)/爬取页面爬取页面STORE(,COLLECTION)For e

13、very URLi in PAGE,/链接提取链接提取 EnQueue(URL,QUEUE)Return COLLECTION第18页，共34页，编辑于2022年，星期六面向领域的垂直检索面向领域的垂直检索采用类似A*算法，best-first，分支限界算法等的变形搜索算法，利用最大堆，选取目前最相似的网页的链接，继续进行爬去。第19页，共34页，编辑于2022年，星期六Best first AlgorithmInput:users query Q,and a list L of URLs,sim(Q,P),PL;Output:A page set S,where sim(Q,P);PS;S=

14、L;OPEN=L;while OPEN!=null do 1.Pick the best node B from OPEN./measured by sim 2.search pages pointed by page B 3.For each page p do:a.If it has not been recorded:compute sim(p,Q),add it to S and Open if sim(p,Q),and record its parent B.done 第20页，共34页，编辑于2022年，星期六Sim(Q,p)的计算因素的计算因素网站的重要性及和Q的相关性p 的父亲

15、节点f(p)对Q相关性的遗传性如将1/2 sim(f(p),Q)加到sim(p,Q)锚文本与Q的相关性网页文本内容与Q的相关性由p指向的网页中是否与Q在语义上相关第21页，共34页，编辑于2022年，星期六Crawler的任务和方法的任务和方法批量爬取在一个时间段尽量多的网页通用搜索引擎：涉及的网页内容尽量丰富，质量尽量高（例如不要集中在少数网站，不要那些没什么内容的网页）主题搜索引擎：尽量符合主题内容（例如某新闻主题，可能需要特别关注若干网站）增量爬取用尽量少的时间，尽量收集目前系统中没有（或者有但发生了更新）的网页，同时发现系统中已有的哪些网页现在实际上已经不存在网上了第22页，共34页，

16、编辑于2022年，星期六提高质量：提高质量：“全全”和和“好好”数量覆盖率搜索引擎索引的网页（一次收集）占目标区域中所有可能网页数量的百分比质量覆盖率搜索引擎索引的网页中“高质量”网页占目标区域中所有可能重要网页数量的百分比何谓“高质量网页”？PageRankHITS(Hyperlink-Induced Topic Search)第23页，共34页，编辑于2022年，星期六链接提取和规格化链接提取和规格化目标：得到网页中所含URL的标准型URL的处理和过滤避免多次抓取被不同url指向的相同网页IP地址和域名之间的多对多关系（见以前的讨论）大规模网站用于负载平衡的技术：内容镜像“virtual

17、hosting”和“Proxy pass”：不同的主机名映射到同一个IP地址，发布多个逻辑网站的需要（Apache支持）相对URL需要补齐基础URL第24页，共34页，编辑于2022年，星期六对对URLURL进行规格化进行规格化比如:http:/,http:/ exclusionRobot exclusion检查 在服务器文档根目录中的文件，robots.txt包含一个路径前缀表，crawlers不应该跟进去抓文档，例如#AltaVista SearchUser-agent:AltaVista Intranet V2.0 W3C WebreqDisallow:/Out-Of-Date#excl

18、ude some access-controlled areasUser-agent:*Disallow:/Team /不允许爬取的部分Disallow:/ProjectDisallow:/Systems限制只是对crawlers，一般浏览无妨“君子协定”（你的crawler可以不遵守）第27页，共34页，编辑于2022年，星期六消除已经访问过的消除已经访问过的URLURL检查某个URL是否已经被抓过了 在将一个新的URL放到工作池之前要很快，不要在这里形成性能瓶颈（检查将要访问磁盘）可以通过计算并对比（规格化后的）URL的MD5来实现利用访问的时空局部性两级hash函数（改善对空间局部性的利

19、用）主机名+端口号，散列到高位（例如高24位）路径散列到低位（例如后面的40位）用B-树管理符合条件（即未被访问过）的URLs放到crawler的任务中.第28页，共34页，编辑于2022年，星期六爬取器的陷阱爬取器的陷阱防止系统异常病态HTML文件例如，有的网页含有68 kB null字符误导爬取器的网站用CGI程序产生无限个网页用软目录创建的很深的路径 problem），例如由CGI表格查询产生的清除非文本类型的URLs（即它的MIME类型不是text/*）第30页，共34页，编辑于2022年，星期六避免在重复的网页上再提取链接避免在重复的网页上再提取链接减少爬取中的别名冗余网页（不仅本身

20、开销，还有其中的相对链接v）重复网页的检测：镜像网页和网站检测完全重复的网页（exact duplicates）对比不同URL对应网页的MD5摘要（访问一次磁盘）或者，将相对于网页u的链接v表示为(h(u);v)，其中h(u)是u的内容的散列。这样，两个别名的相同相对链接就有同样的表示，直接放到isUrlVisited中检查检测接近重复的网页（near-duplicates）即使是一个字符的改变也会完全改变MD5摘要例如，网页的转载常伴随有日期或者网站管理者名字的变化解决方案：Shingling（分段）第31页，共34页，编辑于2022年，星期六网页内容的存贮网页内容的存贮典型HTML网页可以

21、压缩到2-4 kB(using zlib)文件系统的block size通常是4-8 kB（对网页太大！），“一个block，一个文件”损失太大因此网页的存贮管理应该由专用存贮管理器来完成提供简单的访问方法（method），用来便于让crawler往里添加网页后边的程序（索引器等）从中获取文档第32页，共34页，编辑于2022年，星期六网页存贮网页存贮小规模系统能在一台机器的硬盘上放下用存贮管理器（例如，Berkeley DB）在一个文件内，管理基于磁盘的数据库如果后续访问操作是随机的，例如以URL为键，则可以将它配置成hash-table/B-tree。访问开销较大。如果后续访问可以是顺序的，例如索引器，则可以将它配置成一个顺序的网页记录。访问效率较高第33页，共34页，编辑于2022年，星期六网页存储网页存储大规模系统仓储分布在多个存储服务器上存储服务器通过高速局域网连到crawler按照URL散列网页到存储服务器第34页，共34页，编辑于2022年，星期六