web数据挖掘Web爬取PPT课件

1 Roadmap IntroductionCrawlingprocessImplementationissuesOnetaxonomyofcrawlers 2 Q Howdoesasearchengineknowthatallthesepagescontainthequeryterms A Becauseallofthosepageshavebeencrawled 3 Crawler basicidea startingpages seeds 4 Manynames CrawlerSpiderRobot orbot WebagentWanderer worm Andfamousinstances googlebot scooter slurp msnbot 5 Motivationforcrawlers Supportuniversalsearchengines Google Yahoo MSN WindowsLive Ask etc Vertical specialized searchengines e g news shopping papers recipes reviews etc Businessintelligence keeptrackofpotentialcompetitors partnersMonitorWebsitesofinterestEvil harvestemailsforspamming phishing Canyouthinkofsomeothers 6 Acrawlerwithinasearchengine Web Textindex PageRank Pagerepository googlebot Text linkanalysis Query hits Ranker 7 Crawlingprocess 8 Spiders Robots Bots Crawlers 从一个URL根集开始搜索 根据这些网页的链接寻找另外的网页 将遇到的所有新的网页建立索引 也允许直接索引用户提交的网页 9 Web有向图 网页为节点HTML链接引用为有向边 10 系统框图 Basiccrawlers ThisisasequentialcrawlerSeedscanbeanylistofstartingURLsOrderofpagevisitsisdeterminedbyfrontierdatastructureStopcriterioncanbeanything 12 Graphtraversal BFSorDFS BreadthFirstSearchImplementedwithQUEUE FIFO FindspagesalongshortestpathsIfwestartwith good pages thiskeepsusclose maybeothergoodstuff DepthFirstSearchImplementedwithSTACK LIFO Wanderaway lostincyberspace 13 单个采集线程个工作过程 将url解析成host和file 例如 url 14 单个采集线程个工作过程 续 在本地服务器缓冲区中组装http请求 用write 函数将组装好的http头发给网页服务器 调用read 函数读从网页服务器返回的网页数据当read 函数返回的字节数是0的时候 说明网页已经下载完毕 调用close 函数终止与网页服务器的连接 将网页保存到本地服务器 15 先广搜索算法 Thebasiccrawlingalgorithmisasfollows CreateanemptyURLqueueAdduser suppliedseedURLstothetailofthequeueUsingtheHTTPHEADrequest retrievetheHTTPheadersfortheresourceattheheadofthequeueIftheresourceisfound hasn tbeenvisitedpreviously andmeetsallcrawlingcriteria then RetrievetheresourceusinganHTTPGETrequestExtractURLsfromtheresource ForeachURL DecideiftheURLshouldbeaddedtotheURLqueue Ifso addtheURLtothetailoftheURLqueueStoretheheadersandresourceinthecollectionstoreRecordtheURLinthevisitedURLlistRepeatfromStep2untilthequeueisempty thenstop 16 AbasiccrawlerinPerl Queue aFIFOlist shiftandpush my frontier read seeds file while frontier 17 搜索策略 Breadth firstSearch 18 搜索策略 cont Depth firstSearch 19 Implementationissues 20 网页分布的若干特点 网页 内容 C 物理存在 P IP地址 A url L 存在有大量内容相同 但物理上不同的 url不同 IP地址不同的网页 镜像 拷贝同一篇 物理 网页可能被多个url指向例如 和www ir lab org一个url可能对应多个IP地址 从而多个物理的网页 尽管此时内容大都是相同 例如 一些大门户网站采用的负载分配技术 也是一个例子 21 1 DNS缓存 预取和解析 如果不采取措施 DNS地址解析会成为一个重要的瓶颈局域网中 DNS服务器通常较小 对付几百个工作站的常规操作没问题 但一个crawler产生的压力大很多同时从一个服务器抓许多网页也可以使DNS的cache能力发挥出来搜索引擎中可以设计一个专用的DNS模块 含有用于地址解析的DNSclient 和本模块的DNS缓存服务器打交道 缓存server预取client 22 DNSresolver 23 高效地址解析的定制client 一般系统 例如UNIX 提供的DNSclient没有考虑cralwer的需求 带来两个问题 以gethostbyname 为基础 它不能并发 不会考虑在多个DNSserver之间分配负载 因此一个customclient很必要 专门对付多个请求的并发处理容许一次发出多个解析请求协助在多个DNSserver之间做负载分配 例如根据掌握的URL进行适当调度 24 DNS缓存服务器 大缓存容量 跨DNS系统的刷新保持内容Internet的DNS系统会定期刷新 交换更新的域名和IP的信息 普通的DNScache一般应该尊重上级DNS服务器带来的域名 过期 的信息 但用于爬取网页的DNScache不一定如此 以减小开销 让缓存中有些过期的无所谓 但也要注意安排适时刷新 映射尽量放在内存 可以考虑用一台专门的服务器 25 预取client 为了减少等待查找涉及新主机的地址的时间 尽早将主机名投给DNS系统步骤分析刚得到的网页从HREF属性中提取主机名 不是完整的URL 向缓存服务器提交DNS解析请求结果放到DNScache中 后面可能有用 也可能用不上 通常用UDP实现非连接 基于包的通信协议 不保证包的投递用不着等待解析的完成 26 网页抓取 问题 网络连接及传输的开销局域网的延迟在1 10ms 带宽为10 1000Mbps Internet的延迟在100 500ms 带宽为0 010 2Mbps在一个网络往返时间RTT为200ms的广域网中 服务器处理时间SPT为100ms 那么TCP上的事务时间就大约500ms 2RTT SPT 网页的发送是分成一系列帧进行的 则发送1个网页的时间量级在 13KB 1500B 500ms 4s解决 多个并发的抓取 27 多个并发的抓取 管理多个并发的连接单个下载可能需要几秒钟同时对不同的HTTP服务器建立许多socket连接过多的硬件并行好处不大爬取的性能瓶颈主要在网络和硬盘两种基本方法用多线程 多进程用带事件处理的非阻塞sockets 28 Concurrency Acrawlerincursseveraldelays ResolvingthehostnameintheURLtoanIPaddressusingDNSConnectingasockettotheserverandsendingtherequestReceivingtherequestedpageinresponseSolution Overlaptheabovedelaysbyfetchingmanypagesconcurrently 29 Architectureofaconcurrentcrawler 30 2 链接提取和规格化 目标 得到网页中所含URL的标准型URL的处理和过滤避免多次抓取被不同URL指向的相同网页IP地址和域名之间的多对多关系大规模网站用于负载平衡的技术 内容镜像不同的主机名映射到同一个IP地址 发布多个逻辑网站的需要 Apache支持 相对URL需要补齐基础URL 31 节省资源 避免 同义 地址 域名与IP对应存在4种情况 一对一 一对多 多对一 多对多 一对一不会造成重复搜集后三种情况都有可能造成重复搜集可能是虚拟主机 多个域名共一个IP 内容不同www ir lab org 202 118 250 16可能是DNS轮转 202 112 8 2 202 112 8 3可能是一个站点有多个域名对应www ir lab org和等价 32 对URL进行规格化 用一个标准的字符串表示协议利用主机名查DNS会返回IP和一个主机名显式加上一个端口号 80也加上 规格化并清理好文档路径例如将 books papers sigmod1999 ps写成 papers sigmod1999 ps 33 3 爬取器的陷阱 防止系统异常病态HTML文件例如 有的网页含有68kBnull字符误导爬取器的网站用CGI程序产生无限个网页用软目录创建的很深的路径 34 爬取器的陷阱 解决方案 不存在完美的自动方案 积累历史数据很重要检查URL的长度保护模块 Guards 定期收集爬取中的统计数据发现太突出的网站 例如收集过程过多出现它 就将它放到保护模块中 以后就不考虑来自于它的URL 不爬取动态的内容 unsolvedproblem 例如由CGI表格查询产生的清除非文本类型的URLs 即它的MIME类型不是text 35 4 避免在重复网页上再提取链接 减少爬取中的别名冗余网页 不仅本身开销 还有其中的相对链接v 重复网页的检测 镜像网页和网站检测完全重复的网页 exactduplicates 对比不同URL对应网页的MD5摘要将相对于网页u的链接v表示为 h u v 其中h u 是u的内容的散列 这样 两个别名的相同相对链接就有同样的表示 直接放到isUrlVisited中检查检测接近重复的网页 near duplicates 即使是一个字符的改变也会完全改变MD5摘要例如 网页的转载常伴随有日期或者网站管理者名字的变化解决方案 网页去重 36 5 文本仓储 爬取器最后的任务将抓得的网页放到一个仓储 repository 中好处 将crawler和搜索引擎系统的其他功能分开 既有效率的好处 也有可靠性好处和网页相关的信息存成两个部分元数据网页内容 37 和网页相关信息的存贮 元数据 描述数据的数据 包括的域有content type last modifieddate content length HTTPstatuscode etc 本质上可以表达成关系但通常是由特别定制的软件来管理 以避免关系数据库的访问开销 以可能的可靠性损失为代价 我们这里不谈建立索引的问题 38 网页内容的存贮 典型HTML网页可以压缩到2 4kB usingzlib 文件系统的blocksize通常是4 8kB 对网页太大 一个block 一个文件 损失太大因此网页的存贮管理应该由专用存贮管理器来完成提供简单的访问方法 用来便于让crawler往里添加网页后边的程序 索引器等 从中获取文档 39 网页存贮 小规模系统能在一台机器的硬盘上放下用存贮管理器 例如 BerkeleyDB 在一个文件内 管理基于磁盘的数据库如果后续访问操作是随机的 例如以URL为键 则可以将它配置成hash table B tree 访问开销较大 如果后续访问可以是顺序的 例如索引器 则可以将它配置成一个顺序的网页记录 访问效率较高 40 网页存储 大规模系统仓储分布在多个存储服务器上存储服务器通过高速局域网连到crawler按照URL散列网页到存储服务器 41 还存在什么问题呢 网络资源的大小和动态性同时增长效率问题1billionpages permonth 385pages sec瓶颈DNSandtcpconnection transferoverheads improvenetworkbandwidthutilization没有足够的内存支持所有的数据结构真实世界是不完善的url htmlsyntaxerror servertrapsServercomplains legalissues 42 高性能的Crawler需要 ScalableParallel distributedFastBottleneck NetworkutilizationPoliteDoS robot txtRobustTraps errors crashrecoveryContinuousBatchorincremental 43 Web信息采集当前研究方向 基于整个Web的信息采集 UniversalWebCrawling 增量式Web信息采集 IncrementalWebCrawling 基于主题的Web信息采集 FocusedWebCrawling 基于用户个性化的Web信息采集 CustomizedWebCrawling 基于Agent的信息采集 AgentBasedWebCrawling 迁移的信息采集 RelocatableWebCrawling 基于元搜索的信息采集 MetasearchWebCrawling 实际的采集器往往是几种采集技术的结合 44 基于整个Web的信息采集 传统的采集方式作为门户搜索引擎和大型的Web服务提供商的数据收集部分是指从一些种子URL扩充到整个Web的信息采集优点采集数据广 采集速度快 适用于广泛主题的搜索缺点采集数据乱 数据利用率低 页面失效率高 采集周期长目前在实际应用中占较为主流的地位典型代表 GoogleCrawler 百度 45 Large scaleuniversalcrawlers Twomajorissues PerformanceNeedtoscaleuptobillionsofpagesPolicyNeedtotrade offcoverage freshness andbias e g toward important pages 46 Large scalecrawlers scalability NeedtominimizeoverheadofDNSlookupsNeedtooptimizeutilizationofnetworkbandwidthanddiskthroughput I Oisbottleneck UseasynchronoussocketsMulti processingormulti threadingdonotscaleuptobillionsofpagesNon blocking hundredsofnetworkconnectionsopensimultaneouslyPollingsockettomonitorcompletionofnetworktransfers 47 Universalcrawlers Policy CoverageNewpagesgetaddedallthetimeCanthecrawlerfindeverypage FreshnessPageschangeovertime getremoved etc Howfrequentlycanacrawlerrevisit Trade off Focusonmost important pages crawlerbias Importance issubjective Webcoveragebysearchenginecrawlers ThisassumesweknowthesizeoftheentiretheWeb Dowe Canyoudefine thesizeoftheWeb 49 Maintaininga fresh collection Universalcrawlersarenever done HighvarianceinrateandamountofpagechangesHTTPheadersarenotoriouslyunreliableLast modifiedExpiresSolutionEstimatetheprobabilitythatapreviouslyvisitedpagehaschangedinthemeanwhilePrioritizebythisprobabilityestimate 50 DoweneedtocrawltheentireWeb Ifwecovertoomuch itwillgetstaleThereisanabundanceofpagesintheWebForPageRank pageswithverylowprestigearelargelyuselessWhatisthegoal Generalsearchengines pageswithhighprestigeNewsportals pagesthatchangeoftenVerticalportals pagesonsometopicWhatareappropriateprioritymeasuresinthesecases Approximations 51 增量式Web信息采集 在页面刷新时 只需要采集新产生的或者已经发生变化的页面 而对于没有变化的页面不进行采集预测变化的策略 基于统计的方法 观察网站的平均变化周期基于数据建模的方法 通过网页中变化估计模型和参数优点极大地减小数据采集量进而极大地减小采集时空开销 缺点增加了一定的判别开销 典型代表 GoogleCrawler WebFountain 52 有统计资料表明 随机选择270个站点 132个 com站点 78个 edu站点 30个 net站点和30个 gov站点下载72000个页面 40 的 com每天变化 net和 org变化适中 edu和 gov变化最为缓慢需要为更新较快的页面提高刷新率 53 用户个性化Web信息采集 轻量级的信息采集不同的用户对一个搜索引擎提交同一个检索词 他们期望的返回结果是不同的通过用户兴趣制导或与用户交互等灵活手段来采集信息优点灵活 小巧 针对性强 缺点实用性和有效性还有待提高 典型代表 SPHINX 54 55 Preferentialcrawlers Assumewecanestimateforeachpageanimportancemeasure 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 56 Preferentialcrawlers Selectivebiastowardsomepages eg most relevant topical closesttoseeds mostpopular largestPageRank unknownservers highestrate amountofchange etc FocusedcrawlersSupervisedlearning classifierbasedonlabeledexamplesTopicalcrawlersBest firstsearchbasedonsimilarity topic parent AdaptivecrawlersReinforcementlearningEvolutionaryalgorithms artif