數(shù)據(jù)挖掘以及搜索引擎經(jīng)典ppt

信息檢索和知識發(fā)現(xiàn)馬軍山東大學(xué)計算機學(xué)院majun@Tel:91528講課內(nèi)容目前的信息檢索與挖掘?qū)嵸|(zhì)上是融合了文本及多媒體檢索、數(shù)據(jù)挖掘、機器學(xué)習(xí)和自然語言處理的綜合學(xué)科，因此本課程的內(nèi)容包括：信息檢索的基本知識簡單的自然語言處理信息檢索與知識發(fā)現(xiàn)中的主要計算 聚類與分類基于內(nèi)容的圖像檢索技術(shù)信息檢索課程章節(jié)1簡介2理論模型（基本概念）3檢索評價4Web信息獲取算法5索引建立6基本運算算法7網(wǎng)頁排序8分類計算9聚類計算10層次聚類11XML文檔檢索12-15圖像檢索16圖像標(biāo)注/IR-book/IR簡介研究歷史基本概念目前和未來的研究內(nèi)容Web上的信息檢索WWW發(fā)展迅速，Web文本數(shù)據(jù)以T=1000G計。而多媒體數(shù)據(jù),如圖片,視頻，音頻信息正快速增加。Web可以看做巨型的、非結(jié)構(gòu)化的無所不在的數(shù)據(jù)庫,除了傳統(tǒng)的書面文檔，目前口語形式的文檔正在迅速增加（微博等）Web的發(fā)展要求有效的工具來管理、檢索、過濾信息：Datamining結(jié)論:信息獲取、組織和檢索將成為現(xiàn)代社會的不可缺少的基礎(chǔ)服務(wù)。Web的建立HowMuchInfo工程由Intel,Microsoft,HP,EMC等公司贊助，UCBerkeley大學(xué)完成2002年世界上共產(chǎn)生了5Exabyte的數(shù)據(jù)，其中92%的信息存儲于電子介質(zhì)相當(dāng)于人類歷史上所有說過的話語

所包含的信息量的總和大部分存儲于Web中，構(gòu)成了Web

中超過150Billion的網(wǎng)絡(luò)頁面WorldWideWeb是什么?

Theworldwideweb(web)isanetworkofinformationresources.Thewebreliesonthreemechanismstomaketheseresourcesreadilyavailabletothewidestpossibleaudience:1.Auniformnamingschemeforlocatingresourcesontheweb(e.g.,URLs).2.Protocols,foraccesstonamedresourcesovertheweb(e.g.,HTTP).3.Hypertext,foreasynavigationamongresources(e.g.,HTML).Web是一個有向圖<href…><href…><href…><href…><href…><href…><href…>網(wǎng)頁為節(jié)點網(wǎng)頁中的HyperLink為有向邊Crawl==圖遍歷,right?Web的發(fā)展帶來了什么？信息數(shù)量的急劇膨脹知識的獲取空前簡單與繁榮從Web中有效的獲取知識正在成為人們生活與工作的必須技能高科技企業(yè)員工1/3的時間用于查找資料由于無法找到有效信息而浪費的產(chǎn)值占企業(yè)收入1/5目前具有市場認(rèn)可的搜索引擎技術(shù)的國家有：美國、韓國、俄羅斯和中國搜索引擎市場的激烈競爭Google市值的變化舉世關(guān)注Baidu上市造就數(shù)以百計的百萬富翁MSN推出新版搜索，MSRA建立搜索研究中心Yahoo中國重組主要門戶網(wǎng)站Sohu,Sina,Netease,騰訊紛紛推出搜索引擎產(chǎn)品面向領(lǐng)域的搜索引擎目前最受北美IT畢業(yè)生青睞的公司GoogleApplefacebookMicrosoftYahoo!其中有3個公司的主要業(yè)務(wù)之一是信息檢索。而Apple過去和Google一起，研制iphone的手機檢索，但可能未來自己研發(fā)。微軟已經(jīng)認(rèn)為他們過去沒有重視搜索是犯了錯誤，目前正在飛速追趕。目前Google,微軟在美國正在建立巨型的數(shù)據(jù)處理中心，保存通過Internet,衛(wèi)星等收集的數(shù)據(jù)。上述3公司的搜索部門在面試時，一般會問關(guān)于現(xiàn)代檢索的核心算法，概念等。Google某數(shù)據(jù)中心微軟在芝加哥的數(shù)據(jù)中心國內(nèi)IT百度，搜狐，搜狗，一搜阿里巴巴騰訊中國大學(xué)生評出的2008最佳雇主中有半數(shù)和搜索有關(guān)。

Google（中國）貿(mào)易：阿里巴巴

兩大搜索：排第一Google和排第三的百度

三大游戲：盛大、巨人、完美時空

四大門戶：騰訊、網(wǎng)易、搜狐、新浪

市場的需求所有的網(wǎng)站都需要搜索引擎，但目前很多借用Google等，搜索效果不好，因為不專業(yè),Google的排序算法可能并不適合該網(wǎng)站的頁面鏈接分析。專業(yè)搜索引擎的需求無止境，未來多媒體，問題求解形式的檢索需求很大。從用戶數(shù)量上看，截至2008年12月31日，中國網(wǎng)民規(guī)模達(dá)到2.98億人，普及率達(dá)到22.6%，超過全球平均水平；網(wǎng)民規(guī)模較2007年增長8800萬人，年增長率為41.9%。無論是政府還是商家，都更重視網(wǎng)絡(luò)上的信息，討論的熱點及反應(yīng)出的問題。而這些計算必須基于對BBS,論壇、博客內(nèi)容的搜集和分析。信息檢索的重要性全球范圍數(shù)字化、信息化的基礎(chǔ)服務(wù)科學(xué)研究領(lǐng)域中的信息獲取電子商務(wù)中的產(chǎn)品檢索、評估日常生活中的信息和知識的獲取企業(yè)創(chuàng)新能力的提高DeepWep信息的獲取原因：紙面載體的信息都數(shù)字化了，更方便進行獲取。基于網(wǎng)絡(luò)的廣告根據(jù)2007年的統(tǒng)計，美國互聯(lián)網(wǎng)上廣告總收入為212億美元，而通過搜索引擎進行的廣告收入是總收入的41%。原因，通過搜索引擎，可以使廣告更有針對性，把廣告放到內(nèi)容相關(guān)的網(wǎng)頁上。而廣告則是在互聯(lián)網(wǎng)上進行經(jīng)濟活動驅(qū)動力和使搜索引擎，網(wǎng)站等盈利的重要手段。信息檢索目前的狀態(tài)目前基本認(rèn)為是出于開始階段未來的遠(yuǎn)景圖個性化專業(yè)化多媒體檢索智能化 檢索形式的創(chuàng)新，不是輸入關(guān)鍵詞，可能是目標(biāo)，得到的是解決方案。和以往IR研究的區(qū)別原來是圖書館學(xué)的專業(yè)方向，但目前的研究和以前的研究相差太大了。目前的研究者來自：數(shù)據(jù)庫，人工智能，計算機算法，人機交互，多媒體，移動通訊，模式識別，地理信息和衛(wèi)星圖像處理等都加入到這個領(lǐng)域。目前信息檢索的方式搜索web的三種方式：searchengine把一部分網(wǎng)絡(luò)文獻作為一個全文數(shù)據(jù)庫webdirectories按主題來對所選擇的Web文獻進行分類(browser)利用hyperlinkstructure.目前的信息檢索方式

Given:使用用文字(關(guān)鍵詞)表示的檢索意愿Find:搜索引擎返回一系列相關(guān)文檔IR系統(tǒng)的構(gòu)成-爬蟲,中間處理和檢索服務(wù)IRSystemQueryStringDocumentcorpusRankedDocuments1.Doc12.Doc23.Doc3..WebsearchbasicsTheWebAdindexesWebspiderIndexerIndexesSearchUser利用搜索引擎為工具的數(shù)據(jù)挖掘互聯(lián)網(wǎng)的尺寸互聯(lián)網(wǎng)的鏈接特征分析互聯(lián)網(wǎng)的動態(tài)變化特征語義萬維網(wǎng)互聯(lián)網(wǎng)上的社區(qū)發(fā)現(xiàn)進入2000后對IR的研究2000’s基于網(wǎng)頁鏈接分析技術(shù)的Google網(wǎng)頁的排序技術(shù)PageRank網(wǎng)頁的分析技術(shù)基于塊的分解，內(nèi)容提取和理解面向領(lǐng)域的垂直檢索系統(tǒng)和查詢內(nèi)容有關(guān)、和領(lǐng)域知識有關(guān)和機器學(xué)習(xí)、人工智能的發(fā)展有關(guān)如何計算仍是一個未能很好解決的問題IR的新研究課題1自動文本摘要或主題的提取WhizbangFetchBurningGlass問題回答系統(tǒng)TRECQ/AtrackAnswer.google會話體文本的處理微博，博客

IR的新研究課題2多Multimedia（多媒體的檢索技術(shù)）ImageVideoAudioandmusicCross-LanguageIR（跨語言的檢索技術(shù)）DARPATidesAltavista（自然語言轉(zhuǎn)換，網(wǎng)站或具體網(wǎng)頁）DocumentSummarization內(nèi)容摘要技術(shù)基于圖象的標(biāo)注技術(shù)

人工和基于機器學(xué)習(xí)不足之處一副畫勝過千言萬語，如何用簡短的文字描述自然，風(fēng)景？不可能文字也不能很好地表達(dá)感知的相似關(guān)系感知是人主觀的東西，因人而異，而文字描述只能是唯一的。但目前如何自動地進行對圖像的標(biāo)注，仍是國際上研究的熱點課題。是為圖像建立語義特征的主要手段。圖像的自動標(biāo)注,使得對圖像的檢索可以借助關(guān)鍵詞進行檢索問題用戶比較難于表達(dá)自己的檢索需求（相對于關(guān)鍵詞檢索）能否把文本檢索技術(shù)和圖像檢索技術(shù)結(jié)合起來進行檢索？對很多主題，利用Googleimage檢索出的圖像數(shù)量遠(yuǎn)遠(yuǎn)高于對應(yīng)的網(wǎng)頁數(shù)量，如何排序？理想的狀態(tài)輸入關(guān)鍵詞輸入圖像（草圖）搜索引擎找到那些網(wǎng)頁，它們即含有關(guān)鍵詞同時包含和輸入圖像非常接近的圖像。如何做？目前的現(xiàn)狀如何解決圖像的語義理解對圖像進行標(biāo)記，利用機器學(xué)習(xí)的方法，基于已經(jīng)標(biāo)注圖像來解決新圖像的標(biāo)注。能否利用領(lǐng)域知識解決特殊對象的檢索交通標(biāo)記，企業(yè)的logo,特殊場景的發(fā)現(xiàn)等

IR的新研究課題3：

垂直檢索技術(shù)目前通用的搜索引擎對Internet網(wǎng)頁的覆蓋率小于50%。未來計算機的存儲和運算能力都不可能100%的覆蓋，需要面向具體領(lǐng)域的專用搜索引擎如就業(yè)，股票，賓館飯店，地圖，天氣，商品查找，任務(wù)，風(fēng)景，。。。垂直檢索也是未來利用移動通訊設(shè)備檢索的支撐技術(shù)微軟的科技論文垂直檢索系統(tǒng)IR的新研究課題4

基于移動設(shè)備的信息檢索Google已經(jīng)決定進軍手機的檢索，而NEC,微軟已經(jīng)開始了對手機檢索系統(tǒng)的研究。解決的科學(xué)與技術(shù)問題，如何在小屏幕上顯示用戶的檢索結(jié)果，如何在小鍵盤上輸入不方面的情況下進行文本檢索？能否通過語音檢索？能否通過圖片進行檢索？因為手機更方便語音和圖像。用戶量的需求調(diào)查微軟的msn手機檢索系統(tǒng)

IR的新研究課題5：

對DEEPWeb的信息檢索DeepWeb是可以通過Internet訪問的數(shù)據(jù)庫，它們所承載的信息量是目前Internent的500倍！難點：如何發(fā)現(xiàn)DeepWeb？如何知道該數(shù)據(jù)庫所屬的領(lǐng)域和類別？目前研究的主要課題如何對DeepWeb網(wǎng)頁的爬?。看怪彼阉饕?，元搜索引擎？如何知道DeepWeb的內(nèi)容？如何對DeepWeb數(shù)據(jù)庫進行聚類和分類？

IR的新研究課題6：Web的數(shù)據(jù)和知識挖掘（如何利用虛擬世界研究現(xiàn)實世界）網(wǎng)上人氣榜的排名網(wǎng)上對產(chǎn)品，任務(wù)、事件的評論網(wǎng)上所反映的最關(guān)心的熱點和焦點是什么？網(wǎng)上對事物，人物，事件的正面和反面評價的比例是什么？作弊(spam)網(wǎng)頁、重復(fù)網(wǎng)頁及水軍網(wǎng)頁的發(fā)現(xiàn)Spam網(wǎng)站和網(wǎng)頁的作弊手法在網(wǎng)頁中加入大量的常用關(guān)鍵詞以提高被匹配的可能性在網(wǎng)頁中加入大量的鏈接，自己鏈向自己的鏈接，使得PageRank的值較大，當(dāng)被檢索到時，排名靠前如何對Web中的頁面（網(wǎng)站）給出可信計算（credibility）?IR新研究課題7：基于對象的搜索

問題—回答對用戶的需求返回的不是網(wǎng)頁的URL,而是關(guān)于該問題的較全面的資料。信息服務(wù)公司，根據(jù)客戶的需求建立描述，每天對Web上的信息檢索、摘要和分類，把信息主動地送給用戶。這是一個新興的盈利模式和企事業(yè)需要的服務(wù)，如電力集團，報業(yè)、新聞記者等。研究問題8：如何利用Web上的資源進行知識發(fā)現(xiàn)Wiki百科利用維基百科對文檔和圖像的類別識別GoogleEarth利用圖像中的坐標(biāo)，通過Googleearth中相同位置的圖像，對圖像進行補充說明Web上的大型數(shù)據(jù)源，如圖片庫Flickr利用Flickr上的圖像的標(biāo)注，對新圖像進行標(biāo)注。研究9：基于互聯(lián)網(wǎng)信息對人類活動進行研究-輿情分析，事件發(fā)現(xiàn)等通過對網(wǎng)絡(luò)上的信息收集，了解公眾對某種社會現(xiàn)象或社會問題的具有一定影響力和傾向性的共同意見。網(wǎng)絡(luò)環(huán)境下輿情信息的主要來源有：新聞評論、BBS、聊天室、博客、聚合新聞(RSS)利用facebook,myspace等發(fā)現(xiàn)人類自身活動等。結(jié)論信息檢索是一項飛速發(fā)展的科學(xué)技術(shù)信息檢索是一項和人們生活密切相關(guān)的技術(shù)，是計算機科學(xué)研究領(lǐng)域中為數(shù)不多的理論和應(yīng)用密切相關(guān)的研究領(lǐng)域。即理論研究可直接導(dǎo)致應(yīng)用系統(tǒng)的產(chǎn)生。信息檢索是包括了搜索算法，網(wǎng)絡(luò)技術(shù)，機器學(xué)習(xí)，