web文本挖掘-文檔資料

1、2022-3-612022-3-62WEB挖掘挖掘n萬維網(wǎng)是目前一個(gè)巨大的、分布廣泛的全球性信息服務(wù)中心，它涉及新聞、廣告、消費(fèi)信息、金融管理、教育、政府、電子商務(wù)和許多其它信息服務(wù)。WEB還包了豐富和動(dòng)態(tài)的超鏈接信息，以及WEB頁面的訪問和使用信息，這為數(shù)據(jù)挖掘提供了豐富的資源。nWEB對(duì)有效的資源和知識(shí)發(fā)現(xiàn)還是具有極大的挑戰(zhàn)性。2022-3-63The Web Has Many Other Rich Structures2022-3-64WEB對(duì)有效的資源和知識(shí)發(fā)現(xiàn)具有挑戰(zhàn)性對(duì)有效的資源和知識(shí)發(fā)現(xiàn)具有挑戰(zhàn)性n對(duì)有效的數(shù)據(jù)倉庫和數(shù)據(jù)挖掘而言，對(duì)有效的數(shù)據(jù)倉庫和數(shù)據(jù)挖掘而言，WEB似乎似乎太龐

2、大了。太龐大了。nWEB的數(shù)據(jù)量目前以百兆兆字節(jié)計(jì)算，而且仍然在迅速地增長。許多機(jī)構(gòu)和社團(tuán)都把各自大量的可訪問信息置于網(wǎng)上。這使得幾乎不可能去構(gòu)造一個(gè)數(shù)據(jù)倉庫來復(fù)制、存儲(chǔ)或集成WEB上的所有數(shù)據(jù)。2022-3-65WEB對(duì)有效的資源和知識(shí)發(fā)現(xiàn)具有挑戰(zhàn)性對(duì)有效的資源和知識(shí)發(fā)現(xiàn)具有挑戰(zhàn)性nWEB頁面的復(fù)雜性遠(yuǎn)比任何傳統(tǒng)的文本文檔復(fù)頁面的復(fù)雜性遠(yuǎn)比任何傳統(tǒng)的文本文檔復(fù)雜得多雜得多nWeb頁面缺乏同一的結(jié)構(gòu)，它包含了遠(yuǎn)比任何一組書籍或其它文本文檔多得多的風(fēng)格和內(nèi)容。Web可以看作一個(gè)巨大的數(shù)字圖書館；然而，這一圖書館中的大量文檔并不根據(jù)任何有關(guān)排列次序加以組織。他沒有分類索引，更沒有按標(biāo)題、作者、封面

3、頁等索引。對(duì)在這樣的圖書館中搜索希望得到的信息是極具挑戰(zhàn)性的。2022-3-66WEB對(duì)有效的資源和知識(shí)發(fā)現(xiàn)具有挑戰(zhàn)性對(duì)有效的資源和知識(shí)發(fā)現(xiàn)具有挑戰(zhàn)性nWeb是一個(gè)動(dòng)態(tài)性極強(qiáng)的信息源是一個(gè)動(dòng)態(tài)性極強(qiáng)的信息源。nWeb不僅以極快的速度增長，而且其信息還在不斷地發(fā)生著更新。新聞、股票市場、公司廣告和web服務(wù)中心都在不斷更新著各自的頁面。鏈接信息和訪問記錄也在頻繁地更新之中。nWeb面對(duì)的是一個(gè)廣泛的行行色色的用戶群體。面對(duì)的是一個(gè)廣泛的行行色色的用戶群體。n目前因特網(wǎng)上連接有約五千萬臺(tái)工作站，其用戶群仍在不斷地?cái)U(kuò)展中。各個(gè)用戶可以有不同的背景、興趣和使用目的。大部分用戶并不了解信息網(wǎng)絡(luò)結(jié)構(gòu)，不清

4、楚搜索的高昂代價(jià)，極容易在“黑暗”的網(wǎng)絡(luò)中迷失方向，也極容易在“跳躍式”訪問中翻亂不已和在等待一段信息中失去耐心。2022-3-67WEB對(duì)有效的資源和知識(shí)發(fā)現(xiàn)具有挑戰(zhàn)性對(duì)有效的資源和知識(shí)發(fā)現(xiàn)具有挑戰(zhàn)性nWeb上的信息只有很小的一部分是相關(guān)的或有用的。上的信息只有很小的一部分是相關(guān)的或有用的。n據(jù)說99%的web信息對(duì)99%的用戶是無用的。雖然這看起來不是很明顯，但一個(gè)人只是關(guān)心web上的很小很小一部分信息確是事實(shí)，web所包含的其余信息對(duì)用戶來說是不感興趣的，而且會(huì)淹沒所希望得到的搜索結(jié)果。2022-3-68 Finding Information On the Web兩種獲得兩種獲得web

5、信息的方法信息的方法:nBrowsing: From a starting point, navigate through hyperlinks to find desired documents.nYahoos category hierarchy facilitates browsing.nSearching: Submit a query to a search engine to find desired documents.nMany well-known search engines on the Web: Google, MSN, Yahoo, AltaVista, Fast,

6、Lycos, , etc.nSearching is the second most popular activities on the Web behind email.2022-3-69 瀏覽和查找方式的比較瀏覽和查找方式的比較nCategory hierarchy is built mostly manually while search engine databases can be created automatically.nSearch engines can index much more documents than a category hierarchy.nBrowsin

7、g is more accurate and more focused (less junk will be encountered) than searching.2022-3-610WEB挖掘挖掘n盡管傳統(tǒng)的搜索引擎和新一代的搜索引擎Google等在一定程度上滿足了人們信息檢索的需要，但搜索引擎的查全率、查準(zhǔn)率都不盡如人意。于是，人們想到了數(shù)據(jù)挖掘技術(shù)，將傳統(tǒng)的數(shù)據(jù)挖掘同web結(jié)合起來進(jìn)行web挖掘，從web文檔和web活動(dòng)中抽取用戶感性趣的潛在的有用模式和隱藏信息，彌補(bǔ)了搜索引擎的不足。2022-3-611WEB挖掘及相關(guān)概念挖掘及相關(guān)概念nWeb挖掘時(shí)針對(duì)網(wǎng)絡(luò)信息資源進(jìn)行的，其中涉及一

8、些同傳統(tǒng)的數(shù)據(jù)挖掘不同的知識(shí)和概念。比如IP地址、網(wǎng)頁的HIML語言、WEB頁面的URL地址和WEB服務(wù)器的日志記錄等。2022-3-612WEB挖掘及相關(guān)概念挖掘及相關(guān)概念nWEB挖掘中用到的術(shù)語和概念nwww組織在1999年制定了一套規(guī)范的web范圍相關(guān)術(shù)語。nIP地址/域名。nURL統(tǒng)一資源定位器n超級(jí)鏈接hyperlinkn超文本標(biāo)記語言htmlnXml可擴(kuò)展標(biāo)記語言n代理服務(wù)器proxy servernWeb服務(wù)日志n搜索引擎n網(wǎng)絡(luò)蜘蛛2022-3-613搜索引擎搜索引擎為什么查詢很重要？為什么查詢很重要？n信息就在你的指尖nFundamental & pervasiven在

9、線廣告n查詢是一個(gè)在線廣告的分布渠道2022-3-614搜索引擎搜索引擎為什么查詢很重要？為什么查詢很重要？2022-3-615搜索引擎的發(fā)展搜索引擎的發(fā)展nWeb Search 1.0 Traditional Text RetrievalnWeb Search 2.0 Page-level Relevance RankingnWeb Search 3.0 Object-level Structured Search2022-3-616The Trend in Web Search1990Mid 199020042022-3-617Web Search 1.0: Traditional Tex

10、t RetrievalnRelevance ranking based on term distributionn Term frequency (TF) * Inverse document frequency (IDF)n Language modelsn 2022-3-618Web Search 1.0: Traditional Text Retrieval2022-3-619Web Page Has Richer Structure Than Plain Textn Different term types and formatsn Hyperlink structuren 2D vi

11、sual layout structure2022-3-620Web Search 1.0 Web Search 2.0nThe first major improvement in the history of Web searchn Link analysis PageRank & HITSn Relevance ranking = IR Score + PageRank2022-3-621Web Search 2.0 Web Search 3.02022-3-622Object Level Vertical Search (MSRA Libra) Object Level Ver

12、tical Search (MSRA Libra)2022-3-623Web Object Identification2022-3-624Object-level Link Analysis2022-3-6252022-3-626網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n網(wǎng)絡(luò)蜘蛛即Web Spider，是一個(gè)很形象的名字。把互聯(lián)網(wǎng)比喻成一個(gè)蜘蛛網(wǎng)，那么Spider就是在網(wǎng)上爬來爬去的蜘蛛。網(wǎng)絡(luò)蜘蛛是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁，從網(wǎng)站某一個(gè)頁面（通常是首頁）開始，讀取網(wǎng)頁的內(nèi)容，找到在網(wǎng)頁中的其它鏈接地址，然后通過這些鏈接地址尋找下一個(gè)網(wǎng)頁，這樣一直循環(huán)下去，直到把這個(gè)網(wǎng)站所有的網(wǎng)頁都抓取完為止。如果把整個(gè)互聯(lián)網(wǎng)當(dāng)

13、成一個(gè)網(wǎng)站，那么網(wǎng)絡(luò)蜘蛛就可以用這個(gè)原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁都抓取下來。 2022-3-627The previous Web: Search used to be “crawl and index”2022-3-628 網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛A Web crawler (also known as spider, robot) is a program for fetching web pages from the Web.Main idea:Place some initial URLs into a URL queue.Repeat the steps below until the queu

14、e is emptynTake the next URL from the queue and fetch the web page using HTTP.nExtract new URLs from the downloaded web page and add them to the queue.nA free Web crawler: /rcm/websphinx/ 2022-3-629網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n對(duì)于搜索引擎來說，要抓取互聯(lián)網(wǎng)上所有的網(wǎng)頁幾乎是不可能的，從目前公布的數(shù)據(jù)來看，容量最大的搜索引擎也不過是抓取了整個(gè)網(wǎng)頁數(shù)量的百分之四十左右。n這

15、其中的原因一方面是抓取技術(shù)的瓶頸，無法遍歷所有的網(wǎng)頁，有許多網(wǎng)頁無法從其它網(wǎng)頁的鏈接中找到；2022-3-630網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n另一個(gè)原因是存儲(chǔ)技術(shù)和處理技術(shù)的問題，如果按照每個(gè)頁面的平均大小為20K計(jì)算（包含圖片），100億網(wǎng)頁的容量是1002000G字節(jié)，即使能夠存儲(chǔ)，下載也存在問題（按照一臺(tái)機(jī)器每秒下載20K計(jì)算，需要340臺(tái)機(jī)器不停的下載一年時(shí)間，才能把所有網(wǎng)頁下載完畢）。n同時(shí)，由于數(shù)據(jù)量太大，在提供搜索時(shí)也會(huì)有效率方面的影響。因此，許多搜索引擎的網(wǎng)絡(luò)蜘蛛只是抓取那些重要的網(wǎng)頁，而在抓取的時(shí)候評(píng)價(jià)重要性主要的依據(jù)是某個(gè)網(wǎng)頁的鏈接深度。 2022-3-631網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n在抓取網(wǎng)

16、頁的時(shí)候，網(wǎng)絡(luò)蜘蛛一般有兩種策略：廣度優(yōu)先和深度優(yōu)先（如下圖所示）。廣度優(yōu)先是指網(wǎng)絡(luò)蜘蛛會(huì)先抓取起始網(wǎng)頁中鏈接的所有網(wǎng)頁，然后再選擇其中的一個(gè)鏈接網(wǎng)頁，繼續(xù)抓取在此網(wǎng)頁中鏈接的所有網(wǎng)頁。這是最常用的方式，因?yàn)檫@個(gè)方法可以讓網(wǎng)絡(luò)蜘蛛并行處理，提高其抓取速度。2022-3-632網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n深度優(yōu)先是指網(wǎng)絡(luò)蜘蛛會(huì)從起始頁開始，一個(gè)鏈接一個(gè)鏈接跟蹤下去，處理完這條線路之后再轉(zhuǎn)入下一個(gè)起始頁，繼續(xù)跟蹤鏈接。這個(gè)方法有個(gè)優(yōu)點(diǎn)是網(wǎng)絡(luò)蜘蛛在設(shè)計(jì)的時(shí)候比較容易。兩種策略的區(qū)別，下圖的說明會(huì)更加明確。 2022-3-633網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛2022-3-634網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n由于不可能抓取所有的網(wǎng)頁，有些

17、網(wǎng)絡(luò)蜘蛛對(duì)一些不太重要的網(wǎng)站，設(shè)置了訪問的層數(shù)。例如，在上圖中，A為起始網(wǎng)頁，屬于0層，B、C、D、E、F屬于第1層，G、H屬于第2層，I屬于第3層。n如果網(wǎng)絡(luò)蜘蛛設(shè)置的訪問層數(shù)為2的話，網(wǎng)頁I是不會(huì)被訪問到的。這也讓有些網(wǎng)站上一部分網(wǎng)頁能夠在搜索引擎上搜索到，另外一部分不能被搜索到。 對(duì)于網(wǎng)站設(shè)計(jì)者來說，扁平化的網(wǎng)站結(jié)構(gòu)設(shè)計(jì)有助于搜索引擎抓取其更多的網(wǎng)頁。 2022-3-635網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n網(wǎng)絡(luò)蜘蛛在訪問網(wǎng)站網(wǎng)頁的時(shí)候，經(jīng)常會(huì)遇到加密數(shù)據(jù)和網(wǎng)頁權(quán)限的問題，有些網(wǎng)頁是需要會(huì)員權(quán)限才能訪問。n網(wǎng)站的所有者可以通過協(xié)議讓網(wǎng)絡(luò)蜘蛛不去抓取，但對(duì)于一些出售報(bào)告的網(wǎng)站，他們希望搜索引擎能搜索到他們的

18、報(bào)告，但又不能完全免費(fèi)的讓搜索者查看，這樣就需要給網(wǎng)絡(luò)蜘蛛提供相應(yīng)的用戶名和密碼。n網(wǎng)絡(luò)蜘蛛可以通過所給的權(quán)限對(duì)這些網(wǎng)頁進(jìn)行網(wǎng)頁抓取，從而提供搜索。而當(dāng)搜索者點(diǎn)擊查看該網(wǎng)頁的時(shí)候，同樣需要搜索者提供相應(yīng)的權(quán)限驗(yàn)證。 2022-3-636網(wǎng)站與網(wǎng)絡(luò)蜘蛛 n網(wǎng)絡(luò)蜘蛛需要抓取網(wǎng)頁，不同于一般的訪問，如果控制不好，則會(huì)引起網(wǎng)站服務(wù)器負(fù)擔(dān)過重。今年4月，淘寶網(wǎng)（ http:/ ）就因?yàn)檠呕⑺阉饕娴木W(wǎng)絡(luò)蜘蛛抓取其數(shù)據(jù)引起淘寶網(wǎng)服務(wù)器的不穩(wěn)定。n網(wǎng)站是否就無法和網(wǎng)絡(luò)蜘蛛交流呢？其實(shí)不然，有多種方法可以讓網(wǎng)站和網(wǎng)絡(luò)蜘蛛進(jìn)行交流。一方面讓網(wǎng)站管理員了解網(wǎng)絡(luò)蜘蛛都來自哪兒，做了些什么，另一方面也告訴網(wǎng)絡(luò)蜘蛛哪些

19、網(wǎng)頁不應(yīng)該抓取，哪些網(wǎng)頁應(yīng)該更新。 2022-3-637網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n每個(gè)網(wǎng)絡(luò)蜘蛛都有自己的名字，在抓取網(wǎng)頁的時(shí)候，都會(huì)向網(wǎng)站標(biāo)明自己的身份。網(wǎng)絡(luò)蜘蛛在抓取網(wǎng)頁的時(shí)候會(huì)發(fā)送一個(gè)請(qǐng)求，這個(gè)請(qǐng)求中就有一個(gè)字段為Useragent，用于標(biāo)識(shí)此網(wǎng)絡(luò)蜘蛛的身份。n例如:nGoogle網(wǎng)絡(luò)蜘蛛的標(biāo)識(shí)為GoogleBot，nBaidu網(wǎng)絡(luò)蜘蛛的標(biāo)識(shí)為BaiDuSpider，nYahoo網(wǎng)絡(luò)蜘蛛的標(biāo)識(shí)為Inktomi Slurp。n如果在網(wǎng)站上有訪問日志記錄，網(wǎng)站管理員就能知道，哪些搜索引擎的網(wǎng)絡(luò)蜘蛛過來過，什么時(shí)候過來的，以及讀了多少數(shù)據(jù)等等。如果網(wǎng)站管理員發(fā)現(xiàn)某個(gè)蜘蛛有問題，就通過其標(biāo)識(shí)來和其所有者聯(lián)

20、系。 2022-3-638網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛2022-3-639網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n網(wǎng)絡(luò)蜘蛛進(jìn)入一個(gè)網(wǎng)站，一般會(huì)訪問一個(gè)特殊的文本文件Robots.txt，這個(gè)文件一般放在網(wǎng)站服務(wù)器的根目錄下，如： http:/ 。n網(wǎng)站管理員可以通過robots.txt來定義哪些目錄網(wǎng)絡(luò)蜘蛛不能訪問，或者哪些目錄對(duì)于某些特定的網(wǎng)絡(luò)蜘蛛不能訪問。2022-3-640網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n例如有些網(wǎng)站的可執(zhí)行文件目錄和臨時(shí)文件目錄不希望被搜索引擎搜索到，那么網(wǎng)站管理員就可以把這些目錄定義為拒絕訪問目錄。n當(dāng)然，Robots.txt只是一個(gè)協(xié)議，如果網(wǎng)絡(luò)蜘蛛的設(shè)計(jì)者不遵循這個(gè)協(xié)議，網(wǎng)站管理員也無法阻止網(wǎng)絡(luò)蜘蛛對(duì)于某些頁面

21、的訪問，但一般的網(wǎng)絡(luò)蜘蛛都會(huì)遵循這些協(xié)議，而且網(wǎng)站管理員還可以通過其它方式來拒絕網(wǎng)絡(luò)蜘蛛對(duì)某些網(wǎng)頁的抓取。 2022-3-641網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛n現(xiàn)在一般的網(wǎng)站都希望搜索引擎能更全面的抓取自己網(wǎng)站的網(wǎng)頁，因?yàn)檫@樣可以讓更多的訪問者能通過搜索引擎找到此網(wǎng)站。n為了讓本網(wǎng)站的網(wǎng)頁更全面被抓取到，網(wǎng)站管理員可以建立一個(gè)網(wǎng)站地圖，即Site Map。n許多網(wǎng)絡(luò)蜘蛛會(huì)把sitemap.htm文件作為一個(gè)網(wǎng)站網(wǎng)頁爬取的入口，網(wǎng)站管理員可以把網(wǎng)站內(nèi)部所有網(wǎng)頁的鏈接放在這個(gè)文件里面，那么網(wǎng)絡(luò)蜘蛛可以很方便的把整個(gè)網(wǎng)站抓取下來，避免遺漏某些網(wǎng)頁，也會(huì)減小對(duì)網(wǎng)站服務(wù)器的負(fù)擔(dān)。 2022-3-642更新周期更新周期

22、 n由于網(wǎng)站的內(nèi)容經(jīng)常在變化，因此網(wǎng)絡(luò)蜘蛛也需不斷的更新其抓取網(wǎng)頁的內(nèi)容，這就需要網(wǎng)絡(luò)蜘蛛按照一定的周期去掃描網(wǎng)站，查看哪些頁面是需要更新的頁面，哪些頁面是新增頁面，哪些頁面是已經(jīng)過期的死鏈接。 2022-3-643更新周期更新周期 n搜索引擎的更新周期對(duì)搜索引擎搜索的查全率有很大影響。n如果更新周期太長，則總會(huì)有一部分新生成的網(wǎng)頁搜索不到；n周期過短，技術(shù)實(shí)現(xiàn)會(huì)有一定難度，而且會(huì)對(duì)帶寬、服務(wù)器的資源都有浪費(fèi)。n搜索引擎的網(wǎng)絡(luò)蜘蛛并不是所有的網(wǎng)站都采用同一個(gè)周期進(jìn)行更新，對(duì)于一些重要的更新量大的網(wǎng)站，更新的周期短，如有些新聞網(wǎng)站，幾個(gè)小時(shí)就更新一次；相反對(duì)于一些不重要的網(wǎng)站，更新的周期就長，可

23、能一兩個(gè)月才更新一次。2022-3-644更新周期更新周期 n一般來說，網(wǎng)絡(luò)蜘蛛在更新網(wǎng)站內(nèi)容的時(shí)候，不用把網(wǎng)站網(wǎng)頁重新抓取一遍，對(duì)于大部分的網(wǎng)頁，只需要判斷網(wǎng)頁的屬性（主要是日期），把得到的屬性和上次抓取的屬性相比較，如果一樣則不用更新。 2022-3-645 網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛一些具體的問題一些具體的問題:What initial URLs to use? Choice depends on type of search engines to be built.nFor general-purpose search engines, use URLs that are likely to r

24、each a large portion of the Web such as the Yahoo home page.1.For local search engines covering one or several organizations, use URLs of the home pages of these organizations. In addition, use appropriate domain constraint.2022-3-646 網(wǎng)絡(luò)蜘蛛網(wǎng)絡(luò)蜘蛛Several research issues about Web crawlers:nFocused-crawl

25、ing: Fetch web pages in a specified subject area such as movies and sports for creating domain-specific search engines.nEfficient re-crawling: Re-fetch web pages to keep web page index up-to-date.nDeep-crawling: Crawl documents in the deep Web.2022-3-647Deep webnStatic Web vs. Dynamic WebnCriterion:

26、 Frequency of changenVisible Web vs. Invisible WebnCriterion: can be “seen” by crawlersnSurface Web vs. Deep WebnCriterion: protocol & database support2022-3-648The previous Web: Search used to be “crawl and index”2022-3-649The current Web: Search must eventually resort to integration2022-3-650鏈

27、接分析鏈接分析n在過去幾年之內(nèi)，Google成為了全世界被使用的最多的搜索引擎。與其它搜索引擎比較，除高性能和易用以外，一個(gè)決定性的因素是它的優(yōu)秀的搜索結(jié)果。搜索結(jié)果的這質(zhì)量極大地來源于PageRank一個(gè)精密的排序網(wǎng)頁文件等級(jí)的方式。 2022-3-651鏈接分析鏈接分析n從萬維網(wǎng)的早期，搜索引擎開發(fā)不同的方法排序網(wǎng)頁。實(shí)際上，任一個(gè)搜索引擎對(duì)網(wǎng)頁的排序，是根據(jù)搜索的詞組短語在頁面中的出現(xiàn)次數(shù)，并用頁面長度和html標(biāo)簽的重要性提示等進(jìn)行權(quán)重修訂。2022-3-652鏈接分析鏈接分析n為了得到更好的搜索結(jié)果，連接人氣值的概念開始被開發(fā)了。根據(jù)這個(gè)概念，一個(gè)網(wǎng)頁文件的入鏈數(shù)量通常表示此文件的重

28、要程度。因此，一般地，如果從其他網(wǎng)頁鏈接到一個(gè)網(wǎng)頁的數(shù)量越多，那么這個(gè)網(wǎng)頁就越重要。鏈接人氣值的概念通?？梢员苊饽切┲槐粍?chuàng)造出來欺騙搜索引擎并且沒有任何實(shí)際意義的網(wǎng)頁得到好的等級(jí)。2022-3-653鏈接分析鏈接分析n如此, 在PageRank概念中，文件的等級(jí)由與它連接那些文件的等級(jí)決定的。它們的等級(jí)再由與他們連接文件的等級(jí)決定。因此, 文件的PageRank由其他文件的PageRank總遞歸之和確定。因?yàn)?，即使是在邊緣的少量鏈接，任一個(gè)文件的等級(jí)都會(huì)影響些其他文件的等級(jí)，概言之，PageRank的等級(jí)是由整個(gè)網(wǎng)的連接結(jié)構(gòu)決定的。雖然這種方法似乎是非常寬泛和復(fù)雜的, Page和Brin已經(jīng)能

29、夠通過一個(gè)微不足道的運(yùn)算法則將它投入實(shí)踐了。 2022-3-654鏈接分析鏈接分析Vector spread activation (Yuwono 97)nThe final ranking score of a page p is the sum of its regular similarity and a portion of the similarity of each page that points to p.nRationale: If a page is pointed to by many relevant pages, then the page is also likel

30、y to be relevant.Let sim(q, di) be the regular similarity between q and di; rs(q, di) be the ranking score of di with respect to q; link(j, i) = 1 if dj points to di, = 0 otherwise. rs(q, di) = sim(q, di) + link(j, i) sim(q, dj) = 0.2 is a constant parameter.2022-3-655 鏈接分析鏈接分析-PAGERANKPageRank cita

31、tion ranking (Page, Brin, et al. The PageRank Citation Ranking: Bring Order to the Web. Technical report, Stanford U. 98).nWeb can be viewed as a huge directed graph G(V, E), where V is the set of web pages (vertices) and E is the set of hyperlinks (directed edges).nEach page may have a number of ou

32、tgoing edges (forward links) and a number of incoming links (backlinks).nEach backlink of a page represents a citation to the page.nPageRank is a measure of global web page importance based on the backlinks of web pages.2022-3-656 鏈接分析鏈接分析-PAGERANKPageRank is based on the following basic ideas:nIf a

33、 page is linked to by many pages, then the page is likely to be important.nIf a page is linked to by important pages, then the page is likely to be important even though there arent too many pages linking to it.nThe importance of a page is divided evenly and propagated to the pages pointed to by it.

34、10552022-3-657 鏈接分析鏈接分析-PAGERANKPageRank DefinitionLet u be a web page, Fu be the set of pages u points to, Bu be the set of pages that point to u, Nu = |Fu| be the number of pages in Fu.The rank (importance) of a page u can be defined by: R(u) = ( R(v) / Nv ) v Bu2022-3-658 鏈接分析鏈接分析-PAGERANKPageRan

35、k is defined recursively and can be computed iteratively.nInitiate all page ranks to be 1/N, N is the number of vertices in the Web graph.nIn i-th iteration, the rank of a page is computed using the ranks of its parent pages in (i-1)th iteration. Repeat until all ranks converge.Let Ri(u) be the rank

36、 of page u in ith iteration and R0(u) be the initial rank of u. Ri(u) = ( Ri-1(v) / Nv ) v Bu2022-3-659鏈接分析鏈接分析-PAGERANKn r I 1=0* r i-1 1 + 1/2* r i-1 2 + 0* r i-1 3 + 0* r i-1 4 n r I 2=0* r i-1 1 + 1/2* r i-1 2 + 0* r i-1 3 + 0* r i-1 4 0 0 1RI=ri1ri2ri3ri4ri-1 1ri-1 2ri-1 3ri-1 4=2022-3-660 鏈接分析

37、鏈接分析-PAGERANKMatrix representation Let M be an N N matrix and muv be the entry at the u-th row and v-th column. muv = 1/Nv if page v has a link to page u muv = 0 if there is no link from v to u Let Ri be the N 1 rank vector for i-th iteration and R0 be the initial rank vector. Then Ri = M Ri-12022-3

38、-661 鏈接分析鏈接分析-PAGERANKExample: Consider the following partial Web graph: Ri = M = Ri+1 =ABCD0 0 1 ABCDA B C Dri1ri2ri3ri4ri-1 1ri-1 2ri-1 3ri-1 42022-3-662 鏈接分析鏈接分析-PAGERANKIf the ranks converge, i.e., there is a rank vector R such that R = M R, R is the eigenvector of matrix M with eigenvalue being

39、 1.Convergence is guaranteed only ifnM is aperiodic (the Web graph is not a big cycle). This is practically guaranteed for Web.nM is irreducible (the Web graph is strongly connected). This is usually not true.2022-3-663 鏈接分析鏈接分析-PAGERANKRank sink: A page or a group of pages is a rank sink if they ca

40、n receive rank propagation from its parents but cannot propagate rank to other pages.Rank sink causes the loss of total ranks.Example:ABCD(C, D) is a rank sink2022-3-664 鏈接分析鏈接分析-PAGERANKA solution to the non-irreducibility and rank sink problem.nConceptually add a link from each page v to every pag

41、e (include self).nIf v has no forward links originally, make all entries in the corresponding column in M be 1/N.nIf v has forward links originally, replace 1/Nv in the corresponding column by c 1/Nv and then add (1-c) 1/N to all entries, 0 c 0 = 0, otherwise where 0 w 1.nBoth sim(q, d) and R(d) nee

42、d to be normalized to between 0, 1.2022-3-670鏈接分析鏈接分析-PAGERANKnPageRank算法實(shí)質(zhì)上是一種通過離線對(duì)整個(gè)互聯(lián)網(wǎng)結(jié)構(gòu)圖進(jìn)行冪迭代的方法.nPageRank所計(jì)算出的價(jià)值度的值實(shí)際上就是互聯(lián)網(wǎng)結(jié)構(gòu)圖經(jīng)過修改后的相鄰矩陣的特征值.對(duì)這些值的計(jì)算有非常有效的方法(事實(shí)上,僅需要若干次的迭代計(jì)算即可以得到),因此能夠很好地應(yīng)用到整個(gè)互聯(lián)網(wǎng)規(guī)模的實(shí)踐中.n這種方法的另一個(gè)主要優(yōu)點(diǎn)是所有的處理過程都是離線進(jìn)行的,因此不會(huì)為在線的查詢過程付出額外的代價(jià).2022-3-671鏈接分析鏈接分析-PAGERANKn但是,PageRank算法也同樣存

43、在一個(gè)顯著的問題,即價(jià)值度的計(jì)算是不是針對(duì)查詢的.n對(duì)于某個(gè)特定主題的查詢,在返回結(jié)果中一些與主題無關(guān)的“強(qiáng)壯”網(wǎng)頁將會(huì)排在較前的位置.n比如,PageRank會(huì)把網(wǎng)頁網(wǎng)頁排在 鏈接分析鏈接分析-PAGERANKnPageRank defines the global importance of web pages but the importance is domain/topic independent.nWe often need to find important/authoritative pages which are relevant to a given query.nWhat

44、 are important web browser pages?nWhich pages are important game pages?nKleinberg (Kleinberg 98) proposed to use authority and hub scores to measure the importance of a web page with respect to a given query.2022-3-673 鏈接分析鏈接分析-HITSThe basic idea:nA page is a good authoritative page with respect to

45、a given query if it is referenced (i.e., pointed to) by many (good hub) pages that are related to the query.nA page is a good hub page with respect to a given query if it points to many good authoritative pages with respect to the query.nGood authoritative pages (authorities) and good hub pages (hub

46、s) reinforce each other.2022-3-674 鏈接分析鏈接分析-HITSnAuthorities and hubs related to the same query tend to form a bipartite subgraph of the web graph.nA web page can be a good authority and a good hub.hubsauthorities2022-3-675 鏈接分析鏈接分析-HITSMain steps of the algorithm for finding good authorities and hu

47、bs related to a query q.1.Submit q to a regular similarity-based search engine. Let S be the set of top n pages returned by the search engine. (S is called the root set and n is often in the low hundreds).2022-3-676 鏈接分析鏈接分析-HITSMain steps of the algorithm for finding good authorities and hubs relat

48、ed to a query q.Expand S into a large set T (base set):Add pages that are pointed to by any page in S.2.Add pages that point to any page in S. If a page has too many parent pages, only the first k parent pages will be used for some k.2022-3-677 鏈接分析鏈接分析-HITS3. Find the subgraph SG of the web graph t

49、hat is induced by T.ST2022-3-678 鏈接分析鏈接分析-HITSCompute the authority score and hub score of each web page in T based on the subgraph SG(V, E). Given a page p, let a(p) be the authority score of p h(p) be the hub score of p (p, q) be a directed edge in E from p to q. Two basic operations:nOperation I:

50、 Update each a(p) as the sum of all the hub scores of web pages that point to p.nOperation O: Update each h(p) as the sum of all the authority scores of web pages pointed to by p.2022-3-679 鏈接分析鏈接分析-HITSOperation I: for each page p: a(p) = h(q) q: (q, p) EOperation O: for each page p: h(p) = a(q) q:

51、 (p, q) Eq1q2q3pq3q2q1p2022-3-680 鏈接分析鏈接分析-HITSMatrix representation of operations I and O.Let A be the adjacency matrix of SG: entry (p, q) is 1 if p has a link to q, else the entry is 0.Let AT be the transpose of A.Let hi be the vector of hub scores after i iterations.Let ai be the vector of autho

52、rity scores after i iterations. Operation I: ai = AT hi-1 Operation O: hi = A ai2022-3-681 鏈接分析鏈接分析-HITS After each iteration of applying Operations I and O, normalize all authority and hub scores. Repeat until the scores for each page converge (the convergence is guaranteed).5. Sort pages in descen

53、ding authority scores.6. Display the top authority pages.Vqqapapa2)()()(Vqqhphph2)()()(2022-3-682 鏈接分析鏈接分析-HITSAlgorithm (summary) submit q to a search engine to obtain the root set S; expand S into the base set T; obtain the induced subgraph SG(V, E) using T; initialize a(p) = h(p) = 1 for all p in

54、 V; for each p in V until the scores converge apply Operation I; apply Operation O; normalize a(p) and h(p); return pages with top authority scores;2022-3-683 鏈接分析鏈接分析-HITSExample: Initialize all scores to 1.1st Iteration: I operation: a(q1) = 1, a(q2) = a(q3) = 0, a(p1) = 3, a(p2) = 2 O operation:

55、h(q1) = 5, h(q2) = 3, h(q3) = 5, h(p1) = 1, h(p2) = 0 Normalization: a(q1) = 0.267, a(q2) = a(q3) = 0, a(p1) = 0.802, a(p2) = 0.535, h(q1) = 0.645, h(q2) = 0.387, h(q3) = 0.645, h(p1) = 0.129, h(p2) = 0q1q2q3p1p22022-3-684 鏈接分析鏈接分析-HITSAfter 2 Iterations: a(q1) = 0.061, a(q2) = a(q3) = 0, a(p1) = 0.791, a(p2) = 0.609, h(q1) = 0.656, h(q2) = 0.371, h(q3) = 0.656, h(p1) = 0.029, h(p2) = 0After 5 Iter