web數(shù)據(jù)挖掘-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根集開始搜索.根據(jù)這些網(wǎng)頁的鏈接尋找另外的網(wǎng)頁.將遇到的所有新的網(wǎng)頁建立索引.也允許直接索引用戶提交的網(wǎng)頁.Web有向圖<href…><href…><href…><href…><href…><href…><href…>網(wǎng)頁為節(jié)點(diǎn)HTML鏈接引用為有向邊系統(tǒng)框圖BasiccrawlersThisisasequentialcrawlerSeedscanbeanylistofstartingURLsOrderofpagevisitsisdeterminedbyfrontierdatastructureStopcriterioncanbeanythingGraphtraversal

(BFSorDFS?)BreadthFirstSearchImplementedwithQUEUE(FIFO)FindspagesalongshortestpathsIfwestartwith“good”pages,thiskeepsusclose;maybeothergoodstuff…DepthFirstSearchImplementedwithSTACK(LIFO)Wanderaway(“l(fā)ostincyberspace”)單個采集線程個工作過程將url解析成host和file。例如：url：host:file:/asp/customercenter/center_home.asp根據(jù)host〔〕做DNS解析創(chuàng)立一個socket，用于網(wǎng)絡(luò)通信把創(chuàng)立的socket編號和DNS解析得到的網(wǎng)絡(luò)地址作為參數(shù)傳遞給connect()函數(shù)，進(jìn)行本地效勞器和遠(yuǎn)程網(wǎng)頁效勞器的連接操作單個采集線程個工作過程〔續(xù)〕在本地效勞器緩沖區(qū)中組裝請求。用write()函數(shù)將組裝好的頭發(fā)給網(wǎng)頁效勞器。調(diào)用read()函數(shù)讀從網(wǎng)頁效勞器返回的網(wǎng)頁數(shù)據(jù)當(dāng)read()函數(shù)返回的字節(jié)數(shù)是0的時候，說明網(wǎng)頁已經(jīng)下載完畢。調(diào)用close()函數(shù)終止與網(wǎng)頁效勞器的連接。將網(wǎng)頁保存到本地效勞器先廣搜索算法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網(wǎng)頁分布的假設(shè)干特點(diǎn)網(wǎng)頁：內(nèi)容〔C〕，物理存在〔P〕，IP地址〔A〕，url〔L〕存在有大量內(nèi)容相同，但物理上不同的，url不同，IP地址不同的網(wǎng)頁鏡像，拷貝同一篇〔物理〕網(wǎng)頁可能被多個url指向例如，和一個url可能對應(yīng)多個IP地址，從而多個物理的網(wǎng)頁〔盡管此時內(nèi)容大都是相同〕例如，一些大門戶網(wǎng)站采用的負(fù)載分配技術(shù)〔也是一個例子〕1.DNS緩存，預(yù)取和解析如果不采取措施，DNS地址解析會成為一個重要的瓶頸局域網(wǎng)中，DNS效勞器通常較小，對付幾百個工作站的常規(guī)操作沒問題，但一個crawler產(chǎn)生的壓力大很多同時從一個效勞器抓許多網(wǎng)頁也可以使DNS的cache能力發(fā)揮出來搜索引擎中可以設(shè)計一個專用的DNS模塊，含有用于地址解析的DNSclient〔和本模塊的DNS緩存效勞器打交道〕緩存server預(yù)取clientDNSresolver高效地址解析的定制client一般系統(tǒng)〔例如UNIX〕提供的DNSclient沒有考慮cralwer的需求，帶來兩個問題：以gethostbyname()為根底，它不能并發(fā)；不會考慮在多個DNSserver之間分配負(fù)載。因此一個customclient很必要。專門對付多個請求的并發(fā)處理容許一次發(fā)出多個解析請求協(xié)助在多個DNSserver之間做負(fù)載分配〔例如根據(jù)掌握的URL進(jìn)行適當(dāng)調(diào)度〕DNS緩存效勞器大緩存容量，跨DNS系統(tǒng)的刷新保持內(nèi)容Internet的DNS系統(tǒng)會定期刷新，交換更新的域名和IP的信息。普通的DNScache一般應(yīng)該尊重上級DNS效勞器帶來的域名“過期”的信息，但用于爬取網(wǎng)頁的DNScache不一定如此，以減小開銷〔讓緩存中有些過期的無所謂，但也要注意安排適時刷新〕映射盡量放在內(nèi)存，可以考慮用一臺專門的效勞器預(yù)取client為了減少等待查找涉及新主機(jī)的地址的時間：盡早將主機(jī)名投給DNS系統(tǒng)步驟分析剛得到的網(wǎng)頁從HREF屬性中提取主機(jī)名〔不是完整的URL〕向緩存效勞器提交DNS解析請求結(jié)果放到DNScache中〔后面可能有用，也可能用不上〕通常用UDP實現(xiàn)非連接，基于包的通信協(xié)議，不保證包的投遞用不著等待解析的完成網(wǎng)頁抓取問題:網(wǎng)絡(luò)連接及傳輸?shù)拈_銷局域網(wǎng)的延遲在1-10ms，帶寬為10-1000Mbps,Internet的延遲在100-500ms，帶寬為0.010-2Mbps在一個網(wǎng)絡(luò)往返時間RTT為200ms的廣域網(wǎng)中，效勞器處理時間SPT為100ms，那么TCP上的事務(wù)時間就大約500ms〔2RTT+SPT〕網(wǎng)頁的發(fā)送是分成一系列幀進(jìn)行的，那么發(fā)送1個網(wǎng)頁的時間量級在(13KB/1500B)*500ms≈4s解決:多個并發(fā)的抓取多個并發(fā)的抓取管理多個并發(fā)的連接單個下載可能需要幾秒鐘同時對不同的HTTP效勞器建立許多socket連接過多的硬件并行好處不大爬取的性能瓶頸主要在網(wǎng)絡(luò)和硬盤兩種根本方法用多線程/多進(jìn)程用帶事件處理的非阻塞socketsConcurrencyAcrawlerincursseveraldelays:ResolvingthehostnameintheURLtoanIPaddressusingDNSConnectingasockettotheserverandsendingtherequestReceivingtherequestedpageinresponseSolution:OverlaptheabovedelaysbyfetchingmanypagesconcurrentlyArchitectureofaconcurrentcrawler2.鏈接提取和規(guī)格化目標(biāo)：得到網(wǎng)頁中所含URL的標(biāo)準(zhǔn)型URL的處理和過濾防止屢次抓取被不同URL指向的相同網(wǎng)頁IP地址和域名之間的多對多關(guān)系大規(guī)模網(wǎng)站用于負(fù)載平衡的技術(shù)：內(nèi)容鏡像不同的主機(jī)名映射到同一個IP地址，發(fā)布多個邏輯網(wǎng)站的需要〔Apache支持〕相對URL需要補(bǔ)齊根底URL節(jié)省資源：防止“同義”地址域名與IP對應(yīng)存在4種情況：一對一，一對多，多對一，多對多。一對一不會造成重復(fù)搜集后三種情況都有可能造成重復(fù)搜集可能是虛擬主機(jī)，多個域名共一個IP,內(nèi)容不同可能是DNS輪轉(zhuǎn)，可能是一個站點(diǎn)有多個域名對應(yīng)和等價對URL進(jìn)行規(guī)格化用一個標(biāo)準(zhǔn)的字符串表示協(xié)議利用主機(jī)名查DNS會返回IP和一個主機(jī)名顯式加上一個端口號〔80也加上〕規(guī)格化并清理好文檔路徑例如將/books/../papers/sigmod1999.ps寫成/papers/sigmod1999.ps3.爬取器的陷阱防止系統(tǒng)異常病態(tài)HTML文件例如，有的網(wǎng)頁含有68kBnull字符誤導(dǎo)爬取器的網(wǎng)站用CGI程序產(chǎn)生無限個網(wǎng)頁用軟目錄創(chuàng)立的很深的路徑HTTP效勞器中的路徑重映射特征爬取器的陷阱：解決方案不存在完美的自動方案，積累歷史數(shù)據(jù)很重要檢查URL的長度保護(hù)模塊〔Guards〕定期收集爬取中的統(tǒng)計數(shù)據(jù)發(fā)現(xiàn)太突出的網(wǎng)站〔例如收集過程過多出現(xiàn)它〕，就將它放到保護(hù)模塊中，以后就不考慮來自于它的URL。不爬取動態(tài)的內(nèi)容〔unsolvedproblem〕，例如由CGI表格查詢產(chǎn)生的去除非文本類型的URLs〔即它的MIME類型不是text/****〕4.防止在重復(fù)網(wǎng)頁上再提取鏈接減少爬取中的別名冗余網(wǎng)頁〔不僅本身開銷，還有其中的相對鏈接v〕重復(fù)網(wǎng)頁的檢測：鏡像網(wǎng)頁和網(wǎng)站檢測完全重復(fù)的網(wǎng)頁〔exactduplicates〕比照不同URL對應(yīng)網(wǎng)頁的MD5摘要將相對于網(wǎng)頁u的鏈接v表示為(h(u);v)，其中h(u)是u的內(nèi)容的散列。這樣，兩個別名的相同相對鏈接就有同樣的表示，直接放到isUrlVisited中檢查檢測接近重復(fù)的網(wǎng)頁〔near-duplicates〕即使是一個字符的改變也會完全改變MD5摘要例如，網(wǎng)頁的轉(zhuǎn)載常伴隨有日期或者網(wǎng)站管理者名字的變化解決方案：網(wǎng)頁去重5.文本倉儲爬取器最后的任務(wù)將抓得的網(wǎng)頁放到一個倉儲〔repository〕中好處：將crawler和搜索引擎系統(tǒng)的其他功能分開，既有效率的好處，也有可靠性好處和網(wǎng)頁相關(guān)的信息存成兩個局部元數(shù)據(jù)網(wǎng)頁內(nèi)容和網(wǎng)頁相關(guān)信息的存貯元數(shù)據(jù)(描述數(shù)據(jù)的數(shù)據(jù))包括的域有content-type,last-modifieddate,content-length,HTTPstatuscode,etc.本質(zhì)上可以表達(dá)成關(guān)系但通常是由特別定制的軟件來管理，以防止關(guān)系數(shù)據(jù)庫的訪問開銷〔以可能的可靠性損失為代價〕〔我們這里不談建立索引的問題〕網(wǎng)頁內(nèi)容的存貯典型HTML網(wǎng)頁可以壓縮到2-4kB(usingzlib)文件系統(tǒng)的blocksize通常是4-8kB〔對網(wǎng)頁太大！〕，“一個block，一個文件”損失太大因此網(wǎng)頁的存貯管理應(yīng)該由專用存貯管理器來完成提供簡單的訪問方法，用來便于讓crawler往里添加網(wǎng)頁后邊的程序〔索引器等〕從中獲取文檔網(wǎng)頁存貯小規(guī)模系統(tǒng)能在一臺機(jī)器的硬盤上放下用存貯管理器〔例如，BerkeleyDB〕在一個文件內(nèi)，管理基于磁盤的數(shù)據(jù)庫如果后續(xù)訪問操作是隨機(jī)的，例如以URL為鍵，那么可以將它配置成hash-table/B-tree。訪問開銷較大。如果后續(xù)訪問可以是順序的，例如索引器，那么可以將它配置成一個順序的網(wǎng)頁記錄。訪問效率較高網(wǎng)頁存儲大規(guī)模系統(tǒng)倉儲分布在多個存儲效勞器上存儲效勞器通過高速局域網(wǎng)連到crawler按照URL散列網(wǎng)頁到存儲效勞器還存在什么問題呢？網(wǎng)絡(luò)資源的大小和動態(tài)性同時增長效率問題1billionpages/permonth385pages/sec瓶頸DNSandtcpconnection/transferoverheads->improvenetworkbandwidthutilization沒有足夠的內(nèi)存支持所有的數(shù)據(jù)結(jié)構(gòu)真實世界是不完善的url/htmlsyntaxerror,servertrapsServercomplains,legalissues高性能的Crawler需要…ScalableParallel,distributedFastBottleneck?NetworkutilizationPoliteDoS,robot.txtRobustTraps,errors,crashrecoveryContinuousBatchorincrementalWeb信息采集當(dāng)前研究方向基于整個Web的信息采集(UniversalWebCrawling)增量式Web信息采集(IncrementalWebCrawling)基于主題的Web信息采集(FocusedWebCrawling)基于用戶個性化的Web信息采集(CustomizedWebCrawling)基于Agent的信息采集(AgentBasedWebCrawling)遷移的信息采集(RelocatableWebCrawling)基于元搜索的信息采集(MetasearchWebCrawling)

實際的采集器往往是幾種采集技術(shù)的結(jié)合基于整個Web的信息采集傳統(tǒng)的采集方式作為門戶搜索引擎和大型的Web效勞提供商的數(shù)據(jù)收集局部是指從一些種子URL擴(kuò)充到整個Web的信息采集優(yōu)點(diǎn)采集數(shù)據(jù)廣，采集速度快，適用于廣泛主題的搜索缺點(diǎn)采集數(shù)據(jù)亂，數(shù)據(jù)利用率低，頁面失效率高，采集周期長目前在實際應(yīng)用中占較為主流的地位典型代表：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信息采集在頁面刷新時，只需要采集新產(chǎn)生的或者已經(jīng)發(fā)生變化的頁面，而對于沒有變化的頁面不進(jìn)行采集預(yù)測變化的策略：基于統(tǒng)計的方法：觀察網(wǎng)站的平均變化周期基于數(shù)據(jù)建模的方法：通過網(wǎng)頁中變化估計模型和參數(shù)優(yōu)點(diǎn)極大地減小數(shù)據(jù)采集量進(jìn)而極大地減小采集時空開銷。缺點(diǎn)增加了一定的判別開銷。典型代表：GoogleCrawler,WebFountain。有統(tǒng)計資料說明隨機(jī)選擇270個站點(diǎn)，132個站點(diǎn)，78個.edu站點(diǎn)，30個.net站點(diǎn)和30個.gov站點(diǎn)下載72000個頁面，40%的每天變化，.net和.org變化適中，.edu和.gov變化最為緩慢需要為更新較快的頁面提高刷新率用戶個性化Web信息采集輕量級的信息采集不同的用戶對一個搜索引擎提交同一個檢索詞，他們期望的返回結(jié)果是不同的通過用戶興趣制導(dǎo)或與用戶交互等靈活手段來采集信息優(yōu)點(diǎn)靈活、小巧、針對性強(qiáng)。缺點(diǎn)實用性和有效性還有待提高。典型代表：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