web数据挖掘-10Web爬取

Web爬取RoadmapIntroductionCrawlingprocessImplementationissuesOnetaxonomyofcrawlersQ:Howdoesasearchengineknowthatallthesepagescontainthequeryterms?A:BecauseallofthosepageshavebeencrawledCrawler:

basic

ideastartingpages(seeds)ManynamesCrawlerSpiderRobot(orbot)WebagentWanderer,worm,…Andfamousinstances:googlebot,scooter,slurp,msnbot,…MotivationforcrawlersSupportuniversalsearchengines(Google,Yahoo,MSN/WindowsLive,Ask,etc.)Vertical(specialized)searchengines,e.g.news,shopping,papers,recipes,reviews,etc.Businessintelligence:keeptrackofpotentialcompetitors,partnersMonitorWebsitesofinterestEvil:harvestemailsforspamming,phishing……Canyouthinkofsomeothers?…AcrawlerwithinasearchengineWebTextindexPageRankPagerepositorygooglebotText&linkanalysisQueryhitsRankerCrawlingprocessSpiders(Robots/Bots/Crawlers)从一个URL根集开始搜索.根据这些网页的链接寻找另外的网页.将遇到的所有新的网页建立索引.也允许直接索引用户提交的网页.Web有向图<href…><href…><href…><href…><href…><href…><href…>网页为节点HTML链接引用为有向边系统框图BasiccrawlersThisisasequentialcrawlerSeedscanbeanylistofstartingURLsOrderofpagevisitsisdeterminedbyfrontierdatastructureStopcriterioncanbeanythingGraphtraversal

(BFSorDFS?)BreadthFirstSearchImplementedwithQUEUE(FIFO)FindspagesalongshortestpathsIfwestartwith“good”pages,thiskeepsusclose;maybeothergoodstuff…DepthFirstSearchImplementedwithSTACK(LIFO)Wanderaway(“lostincyberspace”)单个采集线程个工作过程将url解析成host和file。例如：url：host:file:/asp/customercenter/center_home.asp根据host〔〕做DNS解析创立一个socket，用于网络通信把创立的socket编号和DNS解析得到的网络地址作为参数传递给connect()函数，进行本地效劳器和远程网页效劳器的连接操作单个采集线程个工作过程〔续〕在本地效劳器缓冲区中组装请求。用write()函数将组装好的头发给网页效劳器。调用read()函数读从网页效劳器返回的网页数据当read()函数返回的字节数是0的时候，说明网页已经下载完毕。调用close()函数终止与网页效劳器的连接。将网页保存到本地效劳器先广搜索算法Thebasiccrawlingalgorithmisasfollows:CreateanemptyURLqueueAdduser-suppliedseedURLstothetailofthequeueUsingtheHTTPHEADrequest,retrievetheHTTPheadersfortheresourceattheheadofthequeueIftheresourceisfound,hasn’tbeenvisitedpreviously,andmeetsallcrawlingcriteria,then:RetrievetheresourceusinganHTTPGETrequestExtractURLsfromtheresource.ForeachURL:DecideiftheURLshouldbeaddedtotheURLqueue.Ifso,addtheURLtothetailoftheURLqueueStoretheheadersandresourceinthecollectionstoreRecordtheURLinthevisitedURLlistRepeatfromStep2untilthequeueisempty,thenstop.AbasiccrawlerinPerlQueue:aFIFOlist(shiftandpush)my@frontier=read_seeds($file);while(@frontier&&$tot<$max){my$next_link=shift@frontier;my$page=fetch($next_link);add_to_index($page);my@links=extract_links($page,$next_link);push@frontier,process(@links);}搜索策略Breadth-firstSearch搜索策略(cont)Depth-firstSearchImplementationissues网页分布的假设干特点网页：内容〔C〕，物理存在〔P〕，IP地址〔A〕，url〔L〕存在有大量内容相同，但物理上不同的，url不同，IP地址不同的网页镜像，拷贝同一篇〔物理〕网页可能被多个url指向例如，和一个url可能对应多个IP地址，从而多个物理的网页〔尽管此时内容大都是相同〕例如，一些大门户网站采用的负载分配技术〔也是一个例子〕1.DNS缓存，预取和解析如果不采取措施，DNS地址解析会成为一个重要的瓶颈局域网中，DNS效劳器通常较小，对付几百个工作站的常规操作没问题，但一个crawler产生的压力大很多同时从一个效劳器抓许多网页也可以使DNS的cache能力发挥出来搜索引擎中可以设计一个专用的DNS模块，含有用于地址解析的DNSclient〔和本模块的DNS缓存效劳器打交道〕缓存server预取clientDNSresolver高效地址解析的定制client一般系统〔例如UNIX〕提供的DNSclient没有考虑cralwer的需求，带来两个问题：以gethostbyname()为根底，它不能并发；不会考虑在多个DNSserver之间分配负载。因此一个customclient很必要。专门对付多个请求的并发处理容许一次发出多个解析请求协助在多个DNSserver之间做负载分配〔例如根据掌握的URL进行适当调度〕DNS缓存效劳器大缓存容量，跨DNS系统的刷新保持内容Internet的DNS系统会定期刷新，交换更新的域名和IP的信息。普通的DNScache一般应该尊重上级DNS效劳器带来的域名“过期”的信息，但用于爬取网页的DNScache不一定如此，以减小开销〔让缓存中有些过期的无所谓，但也要注意安排适时刷新〕映射尽量放在内存，可以考虑用一台专门的效劳器预取client为了减少等待查找涉及新主机的地址的时间：尽早将主机名投给DNS系统步骤分析刚得到的网页从HREF属性中提取主机名〔不是完整的URL〕向缓存效劳器提交DNS解析请求结果放到DNScache中〔后面可能有用，也可能用不上〕通常用UDP实现非连接，基于包的通信协议，不保证包的投递用不着等待解析的完成网页抓取问题:网络连接及传输的开销局域网的延迟在1-10ms，带宽为10-1000Mbps,Internet的延迟在100-500ms，带宽为0.010-2Mbps在一个网络往返时间RTT为200ms的广域网中，效劳器处理时间SPT为100ms，那么TCP上的事务时间就大约500ms〔2RTT+SPT〕网页的发送是分成一系列帧进行的，那么发送1个网页的时间量级在(13KB/1500B)*500ms≈4s解决:多个并发的抓取多个并发的抓取管理多个并发的连接单个下载可能需要几秒钟同时对不同的HTTP效劳器建立许多socket连接过多的硬件并行好处不大爬取的性能瓶颈主要在网络和硬盘两种根本方法用多线程/多进程用带事件处理的非阻塞socketsConcurrencyAcrawlerincursseveraldelays:ResolvingthehostnameintheURLtoanIPaddressusingDNSConnectingasockettotheserverandsendingtherequestReceivingtherequestedpageinresponseSolution:OverlaptheabovedelaysbyfetchingmanypagesconcurrentlyArchitectureofaconcurrentcrawler2.链接提取和规格化目标：得到网页中所含URL的标准型URL的处理和过滤防止屡次抓取被不同URL指向的相同网页IP地址和域名之间的多对多关系大规模网站用于负载平衡的技术：内容镜像不同的主机名映射到同一个IP地址，发布多个逻辑网站的需要〔Apache支持〕相对URL需要补齐根底URL节省资源：防止“同义”地址域名与IP对应存在4种情况：一对一，一对多，多对一，多对多。一对一不会造成重复搜集后三种情况都有可能造成重复搜集可能是虚拟主机，多个域名共一个IP,内容不同可能是DNS轮转，可能是一个站点有多个域名对应和等价对URL进行规格化用一个标准的字符串表示协议利用主机名查DNS会返回IP和一个主机名显式加上一个端口号〔80也加上〕规格化并清理好文档路径例如将/books/../papers/sigmod1999.ps写成/papers/sigmod1999.ps3.爬取器的陷阱防止系统异常病态HTML文件例如，有的网页含有68kBnull字符误导爬取器的网站用CGI程序产生无限个网页用软目录创立的很深的路径HTTP效劳器中的路径重映射特征爬取器的陷阱：解决方案不存在完美的自动方案，积累历史数据很重要检查URL的长度保护模块〔Guards〕定期收集爬取中的统计数据发现太突出的网站〔例如收集过程过多出现它〕，就将它放到保护模块中，以后就不考虑来自于它的URL。不爬取动态的内容〔unsolvedproblem〕，例如由CGI表格查询产生的去除非文本类型的URLs〔即它的MIME类型不是text/****〕4.防止在重复网页上再提取链接减少爬取中的别名冗余网页〔不仅本身开销，还有其中的相对链接v〕重复网页的检测：镜像网页和网站检测完全重复的网页〔exactduplicates〕比照不同URL对应网页的MD5摘要将相对于网页u的链接v表示为(h(u);v)，其中h(u)是u的内容的散列。这样，两个别名的相同相对链接就有同样的表示，直接放到isUrlVisited中检查检测接近重复的网页〔near-duplicates〕即使是一个字符的改变也会完全改变MD5摘要例如，网页的转载常伴随有日期或者网站管理者名字的变化解决方案：网页去重5.文本仓储爬取器最后的任务将抓得的网页放到一个仓储〔repository〕中好处：将crawler和搜索引擎系统的其他功能分开，既有效率的好处，也有可靠性好处和网页相关的信息存成两个局部元数据网页内容和网页相关信息的存贮元数据(描述数据的数据)包括的域有content-type,last-modifieddate,content-length,HTTPstatuscode,etc.本质上可以表达成关系但通常是由特别定制的软件来管理，以防止关系数据库的访问开销〔以可能的可靠性损失为代价〕〔我们这里不谈建立索引的问题〕网页内容的存贮典型HTML网页可以压缩到2-4kB(usingzlib)文件系统的blocksize通常是4-8kB〔对网页太大！〕，“一个block，一个文件”损失太大因此网页的存贮管理应该由专用存贮管理器来完成提供简单的访问方法，用来便于让crawler往里添加网页后边的程序〔索引器等〕从中获取文档网页存贮小规模系统能在一台机器的硬盘上放下用存贮管理器〔例如，BerkeleyDB〕在一个文件内，管理基于磁盘的数据库如果后续访问操作是随机的，例如以URL为键，那么可以将它配置成hash-table/B-tree。访问开销较大。如果后续访问可以是顺序的，例如索引器，那么可以将它配置成一个顺序的网页记录。访问效率较高网页存储大规模系统仓储分布在多个存储效劳器上存储效劳器通过高速局域网连到crawler按照URL散列网页到存储效劳器还存在什么问题呢？网络资源的大小和动态性同时增长效率问题1billionpages/permonth385pages/sec瓶颈DNSandtcpconnection/transferoverheads->improvenetworkbandwidthutilization没有足够的内存支持所有的数据结构真实世界是不完善的url/htmlsyntaxerror,servertrapsServercomplains,legalissues高性能的Crawler需要…ScalableParallel,distributedFastBottleneck?NetworkutilizationPoliteDoS,robot.txtRobustTraps,errors,crashrecoveryContinuousBatchorincrementalWeb信息采集当前研究方向基于整个Web的信息采集(UniversalWebCrawling)增量式Web信息采集(IncrementalWebCrawling)基于主题的Web信息采集(FocusedWebCrawling)基于用户个性化的Web信息采集(CustomizedWebCrawling)基于Agent的信息采集(AgentBasedWebCrawling)迁移的信息采集(RelocatableWebCrawling)基于元搜索的信息采集(MetasearchWebCrawling)

实际的采集器往往是几种采集技术的结合基于整个Web的信息采集传统的采集方式作为门户搜索引擎和大型的Web效劳提供商的数据收集局部是指从一些种子URL扩充到整个Web的信息采集优点采集数据广，采集速度快，适用于广泛主题的搜索缺点采集数据乱，数据利用率低，页面失效率高，采集周期长目前在实际应用中占较为主流的地位典型代表：GoogleCrawler,百度Large-scaleuniversalcrawlersTwomajorissues:PerformanceNeedtoscaleuptobillionsofpagesPolicyNeedtotrade-offcoverage,freshness,andbias(e.g.toward“important”pages)Large-scalecrawlers:scalabilityNeedtominimizeoverheadofDNSlookupsNeedtooptimizeutilizationofnetworkbandwidthanddiskthroughput(I/Oisbottleneck)UseasynchronoussocketsMulti-processingormulti-threadingdonotscaleuptobillionsofpagesNon-blocking:hundredsofnetworkconnectionsopensimultaneouslyPollingsockettomonitorcompletionofnetworktransfersUniversalcrawlers:PolicyCoverageNewpagesgetaddedallthetimeCanthecrawlerfindeverypage?FreshnessPageschangeovertime,getremoved,etc.Howfrequentlycanacrawlerrevisit?Trade-off!Focusonmost“important”pages(crawlerbias)?“Importance”issubjectiveWebcoveragebysearchenginecrawlersThisassumesweknowthesizeoftheentiretheWeb.Dowe?Canyoudefine“thesizeoftheWeb”?Maintaininga“fresh”collectionUniversalcrawlersarenever“done”HighvarianceinrateandamountofpagechangesHTTPheadersarenotoriouslyunreliableLast-modifiedExpiresSolutionEstimatetheprobabilitythatapreviouslyvisitedpagehaschangedinthemeanwhilePrioritizebythisprobabilityestimateDoweneedtocrawltheentireWeb?Ifwecovertoomuch,itwillgetstaleThereisanabundanceofpagesintheWebForPageRank,pageswithverylowprestigearelargelyuselessWhatisthegoal?Generalsearchengines:pageswithhighprestigeNewsportals:pagesthatchangeoftenVerticalportals:pagesonsometopicWhatareappropriateprioritymeasuresinthesecases?Approximations?增量式Web信息采集在页面刷新时，只需要采集新产生的或者已经发生变化的页面，而对于没有变化的页面不进行采集预测变化的策略：基于统计的方法：观察网站的平均变化周期基于数据建模的方法：通过网页中变化估计模型和参数优点极大地减小数据采集量进而极大地减小采集时空开销。缺点增加了一定的判别开销。典型代表：GoogleCrawler,WebFountain。有统计资料说明随机选择270个站点，132个站点，78个.edu站点，30个.net站点和30个.gov站点下载72000个页面，40%的每天变化，.net和.org变化适中，.edu和.gov变化最为缓慢需要为更新较快的页面提高刷新率用户个性化Web信息采集轻量级的信息采集不同的用户对一个搜索引擎提交同一个检索词，他们期望的返回结果是不同的通过用户兴趣制导或与用户交互等灵活手段来采集信息优点灵活、小巧、针对性强。缺点实用性和有效性还有待提高。典型代表：SPHINXPreferentialcrawlersAssumewecanestimateforeachpageanimportancemeasure,I(p)WanttovisitpagesinorderofdecreasingI(p)MaintainthefrontierasapriorityqueuesortedbyI(p)Possiblefiguresofmerit:Precision~

|p:crawled(p)&I(p)>threshold|/|p:crawled(p)|Recall~

|p:crawled(p)&I(p)>threshold|/|p:I(p)>threshold|PreferentialcrawlersSelectivebiastowardsomepages,eg.most“relevant”/topical,closesttoseeds,mostpopular/largestPageRank,unknownservers,highestrate/amountofchange,etc…FocusedcrawlersSupervisedlearning:classifierbasedonlabeled

examplesTopicalcrawlersBest-firstsearchbasedonsimilarity(topic,parent)AdaptivecrawlersReinforcementlearningEvolutionaryalgorithms/artificiallifePreferentialcrawlingalgorithms:ExamplesBreadth-FirstExhaustivelyvisitalllinksinorderencounteredBest-N-FirstPriorityqueuesortedbysimilarity,exploretopNatatimeVariants:DOMcontext,hubscoresPageRankPriorityqueuesortedbykeywords,PageRankSharkSearchPriorityqueuesortedbycombinationofsimilarity,anchor