1、Web信息處理與應用復習筆記? 2017-1 熊家靖 PB14011026PART 1：Web Search一、 Introduction1、 web 搜索的挑戰：數據規模大、分布散、不穩定、質量差、無結構、異構、價值低2、信息檢索：給定查詢和信息庫，找到相關的文檔3、 IR 與 DB 的區別：DB 數據結構化、有明確語義，查詢結構化、匹配要精確、次序不重要IR 數據半結構化、無明確語義，查詢為任意內容、無需精確匹配、次序很重要4、 IR 的任務：基于用戶查詢的搜索、信息過濾、分類、問答5、 IR 的基礎性問題：相關性計算、檢索模型、評價、信息需求、檢索性能二、 Web Crawler1、網絡

2、爬蟲的概念：從一個種子站點集合開始，從web 中尋找并且下載網頁，獲取排序需要的相關信息，并且剔除低質量的網頁2、網絡爬蟲基本過程：種子裝入桶中、每次從桶中取出一個網頁、提取出網頁所有url 放入桶中、重復3、網絡爬蟲的主要需求：快、可擴展性、友好性、健壯、持續搜集、時新性4、網絡爬蟲的常用策略：用棧深度優先、用隊列廣度優先5、網絡爬蟲涉及的協議：HTTP/HTML、 DNS/URL、 Robots Exclusion（排斥協議）、 Sitemp（允許協議）6、 URL 規范化：協議 :/ 主機名 :端口 / 路徑 /: 參數 ?查詢 #Fragment7、分布式爬蟲的概念：如何有效地把N 個

3、網站的搜集任務分配到M 個機器上去使得分配比較均勻8、一致性Hash 的概念：將網頁和機器都映射到環路 Hash 空間，每個機器負責自身位置與后繼的網頁搜集三、 Text Processing1、文本處理的概念：將原始文檔轉換成詞項集以方便索引2、字符編碼的概念：ASCII：美國信息交換標準代碼Unicode： 統一碼，滿足跨語言、跨平臺的需求UTF-8 ：針對Unicode的可變長度字符編碼3、分詞中的概念：- 1 -分詞：將文檔的字符串序列變成詞序列語素：最小的語音語義結合體，是最小的語言單位詞：代表一定的意義，具有固定的語音形式，可以獨立運用的最小的語言單位交叉歧義：網球 /場 / 網

4、/球場 /組合歧義：我/ 個人 /三 /個 /人 /未登錄詞： 未包括在分詞詞表中但必須切分出來的詞，包括各類專名、術語、 縮略語等停用詞：在文檔中頻繁出現或與語料庫特性有關的詞4、中文分詞的挑戰：漢語是字的集合而不是詞的集合漢字存在著不同的組詞方式漢語虛詞眾多，大多數漢字在不同的詞語中可能為關鍵字，也可能為停用詞分詞歧義新詞的頻繁出現5、常用的分詞方法：機械分詞：正向最大匹配分詞FMM反向最大匹配分詞BMM / RMM雙向最大匹配分詞BM: FMM + RMM最少切分分詞：圖中最短路徑ASM( d, a, m ) d為匹配方向，a 為失敗后增/減串長， m 為最大 /小匹配理解分詞：分詞時進

5、行句法、語義分析，從而減少歧義統計分詞：一元文法模型即最大概率分詞二元文法模型每個詞的概率為前一個詞出現后的條件概率N 元文法模型每個詞的概率為前N 個詞出現后的條件概率6、詞根化和編輯距離的概念：詞根化：使用一系列后綴變換規則對單詞進行變換編輯距離：從s 轉換為 t 使用增加、刪除、替換三種操作的最小次數四、 Indexing1、布爾檢索的概念：利用 AND 、 OR 或者 NOT 操作符將詞項連接起來的查詢2、關聯矩陣的概念：行為詞項，列為文檔，詞項在文檔中出現為1 不出現為03、倒排索引的概念和結構：以詞項為索引，每個詞項維護一個鏈表，表示其出現過的文檔集（從小到大）可以加入擴展項：某詞

6、在某文檔中的出現詞頻TF 、某詞出現過的文檔頻數DF4、倒排索引的構建：寫出每個文檔的詞項-> 文檔索引合并所有的索引，詞項和文檔號均從小到大排列5、倒排索引的存儲：詞項與鏈表存儲在同一個文件中/不同文件中6、詞匯表存儲結構：順序存儲、 Hash table、 B+- 樹、 Trie 樹7、 Zipf Law：任意一個詞項，其頻度和排名的乘積大致是一個常數- 2 -五、 Queries1、查詢表達的難點：一個查詢可以代表非常不同的信息需求一個查詢可能是其真正需求的一種非常差的表述2、查詢表達的優化：局部優化：對用戶查詢進行局部分析，如相關性反饋全局優化：進行全局分析來產生同/ 近義詞詞典

7、，如查詢擴展3、相關性反饋的概念和過程：用戶在查詢后標記相關/不相關文檔，然后迭代更新查詢以獲得更好的結果4、相關性反饋的分類及其各自的概念和特點：顯式反饋：定義：用戶顯式參加交互過程，即用戶反饋問題：開銷大、查詢長、用戶不愿意、反饋邏輯難理解隱式反饋：定義：系統跟蹤用戶的行為來推測返回文檔的相關性，從而反饋好處：省卻了用戶的顯式參與過程問題：對分析的要求高、準確度難保證、可能需要額外設備偽相關反饋： 定義：對于真實相關反饋的人工部分進行自動化好處：不用考慮用戶因素，處理簡單，平均效果也不錯問題：準確率難以保證，可能出現查詢漂移5、 Ricchio算法：新查詢向量= ·原查詢向量+

8、·平均相關向量·平均不相關向量計算過程中出現負值，全部設為0基本假設：用戶知道使用文檔集中的詞項來表達初始查詢；相關文檔出現的詞項類似6、查詢擴展的概念：相關性反饋中，用戶針對文檔提供附加信息，查詢擴展中，用戶對詞項提供附加信息7、查詢擴展的幾種方法：人工構建同 / 近義詞詞典、自動導出同 /近義詞詞典、基于查詢日志挖掘查詢等價類六、 Ranking1、 Ranking的難點：Web 網頁的質量參差不齊，大量的網頁組織性、結構性比較差大部分檢索用戶是沒有任何經驗的用戶的查詢需求存在著巨大差異2、信息檢索模型的概念：用來描述文檔和用戶查詢的標識形式以及它們之間相關性的框架形式

9、化表示為： D, Q, F, R(Di,q) 即 文檔表達 , 查詢表達 , 匹配框架 , 相關性度量函數3、信息檢索的實質問題：對于所有文檔，根據其與用戶查詢的相關程度從大到小排序4、信息檢索模型與搜索引擎排序算法的關系：好的信息檢索模型在相關性上產生和人類決策非常相關的結果基于好的檢索模型的排序算法能夠在排序結果頂部返回相關的文檔5、信息檢索的分類：基于集合論的模型：布爾模型基于代數論的模型：向量空間模型基于概率論的模型：概率模型、語言模型、推理網絡6、相關系數的概念和計算：- 3 -Jaccard ： A 與 B 的交中元素的個數/A 與 B 的并中元素的個數# 未考慮詞頻、文檔長度、罕

10、見詞信息量tf( t, d ) ： 詞項 t 在文檔d 中出現的次數# 相關度不會正比于詞項頻率w( t, d ):當 tf > 0 時， 1 + lg( tf ) ； 否則， 0df( t ):出現詞項 t 的文檔數目idf( t ):lg( N / df )其中 N 是文檔集中文檔的數目tf-idf:( 1 + lg tf )lg( N·/ df )# 隨著詞項頻率的增大而增大# 隨著詞項罕見度的增大而增大7、向量空間模型SMART ：D： 每個文檔是一個以詞項為維度的向量，每個維度的值為詞項的tf-idf 值Q： 每個查詢是一個以詞項為維度的向量，每個維度的值為詞項的tf

11、-idf 值F ： 非完全匹配R： 用文檔向量和查詢向量的相似度來估計相關性前提假設：檢索到的所有文檔相關性不等價、相關性多元、查詢關鍵字互相獨立8、余弦相似度：兩個向量夾角的余弦值，即：兩向量的點乘/ 各自模的積9、向量空間模型的操作過程：文檔和查詢表示成tf-idf 的權重向量計算兩向量余弦相似度將余弦相似度Top-K 的文檔返回給用戶10 、向量空間模型的缺點：用戶無法描述詞項之間的關系tf-idf 高的詞項可能會在檢索中影響過大詞項之間的獨立性假設與實際不符11 、概率模型：定義隨機變量R、Q、D，相關度R=0 或 1通過計算條件概率P( R = 1 | Q = q, D = d )來

12、度量文檔和查詢的相關度12 、 PageRank：PR(a) = ( 1d ) + dsigma(· PR(T) / C(T) )每個頁面的pagerank等于進入它的邊的pagerank的函數計算過程：每個網頁賦初值，然后迭代計算，直到變化小于一個閾值優點：給網頁提供重要性排序+ 可以離線完成+ 獨立于主題缺點：未區分鏈接種類+ 對新網頁不公平+ 不能單獨用于排序13 、 HITS ：入步驟：所有權威頁面的值等于鏈向它的中心頁面的值之和出步驟：所有中心頁面的值等于其鏈向的權威頁面的值之和計算過程：所有頁面初始為1 ，迭代使用入步驟和出步驟優點：能更好描述互聯網的組織特點+ 主題相關

13、+ 查詢無關+ 可以單獨用于排序缺點：需要在線計算時間代價大+ 容易受到“鏈接作弊”的影響七、 Evaluation1、信息檢索評價概述：評價受主觀、情景、認知、時間的影響，重點在于保持公平- 4 -2、信息檢索評價指標：效率：時間開銷、空間開銷、響應速度效果：準確率、召回率、是否靠前其他：覆蓋率、訪問量、數據更新速度3、效果評價指標：基于集合：正確率 P ：返回的相關文檔占返回的總文檔的比比例召回率 R：返回的相關文檔占相關總文檔的比例F 值：召回率 R 和正確率 P 的調和平均F值：召回率 R 和正確率 P 的加權調和平均其中 R 的權為 2 ， P 的權為 1基于序：PN ：值考慮返回的

14、前 N 個文檔時的正確率R-Precision ： 即 P 相關文檔總數未插值 AP ：P 相關文檔出現位置的平均插值 AP：在召回率 0,0.1,0.21.0 上十一點的正確率平均不存在某召回率點時， 取該點到下一個點之間最大正確率簡化 AP：在未插值 AP 中忽略未出現的相關文檔多個查詢：MAP ：所有查詢的 AP 的算術平均MRR ：第一個相關文檔返回的位置的倒數的算術平均其他：CGp ：位置 1 到位置 p 的檢索結果的相關度之和DCGp ：相關度要先除以 log2(i) 作為懲罰，其中 i 為出現的位置NDCGp ：DCG 的值除以理想化的 IDCG 的值，規范化為 0,1PART

15、2：Web Information Extraction一、 Named Entity Extraction1、信息抽取的概念：從語料中抽取指定的事件、事實等信息，形成結構化的數據能作為一種淺層的文本理解，是信息檢索的進一步深化2、信息抽取與信息檢索的關系：檢索是從文檔集合中找文檔子集，抽取是從文本中獲取用戶感興趣的事實信息檢索通常利用統計與關鍵詞等技術，抽取借助于自然語言處理技術檢索通常與領域無關，抽取通常與領域相關3、 MUC-7 定義的信息抽取任務：命名實體 NE：現實世界中具體或抽象的實體，還包括日期、時間、數量等模板元素 TE：實體屬性，通過槽描述命名實體的基本信息共指關系CR：命名

16、實體的等價關系模板關系TR：實體之間的各種關系，又稱為事實背景模板ST：實體發生的事件4、信息抽取的內容：實體、屬性、關系、事件關鍵在于“抽取實體，確定關系”5、命名實體識別NER的概念：識別文本中的人名、地名等專有名稱和有意義的時間、日期等數量短語并加以歸類6、命名實體識別NER的難點：命名實體類型多樣、新命名實體不斷出現、命名實體歧義、命名實體結構復雜- 5 -7、 MUC-7 中定義的NER內容：實體類：人名、地名、機構名時間類：日期、時間數值類：貨幣、百分比注意：人造物、重復指代的普通名詞、派生詞、以人命名的法律和獎項等不算！8、命名實體識別NER的性能評價指標：正確率 P：正確數/

17、總數( 正確數+ (1/2) 部分正確數) / 總數召回率 R：正確數/ 總正確數( 正確數+ (1/2) 部分正確數) / 總 (部分 )正確數F 值：P與 R 的調和平均9、命名實體識別NER的常用方法：基于詞典：詞典匹配；難以枚舉命名實體、構建詞典代價大、難以處理歧義基于規則：自行構造模板匹配；依賴性強、代價大、建設周期長、可移植性差基于統計：隱馬爾可夫HMM 、最大熵ME、支持向量機SVM、條件隨機場CRF混合方法：混合使用詞典、規則和統計二、 Relation Extraction1、關系抽取的概念：從文本中識別出兩個實體或多個實體之間存在的事實上的關系2、關系抽取的意義：提高搜索引

18、擎發現知識的能力廣泛應用于各種知識庫的構建支持知識推理和問答系統研究3、關系的表示方法：二元組、三元組、多元組4、關系抽取的常用方法：基于規則：針對特定領域的特定關系，設計針對性的抽取規則，代價大，難移植基于模式： 種子關系生成關系模式，基于關系模式抽取新的關系，再迭代生成新的模式和新的關系基于機器學習：特征向量、核函數5、 DIPRE系統：給定種子元組R在文檔中搜索元組R 的出現 O從出現 O 中提取模板P使用模板P 從文檔中獲取新的元組6、 Snowball 系統：只使用能匹配很多模板的元組只使用有多個元組支持的模板PART 3： Web Data Mining一、 Introductio

19、n1、網絡挖掘的概念：從 web 中挖掘有用的信息和有用的模式2、網絡挖掘的內容與應用：網絡內容挖掘：數據挖掘、數據分類、數據聚類網絡結構挖掘：社區分析、影響力分析- 6 -網絡用途挖掘：推薦系統二、 Data1、數據對象、屬性、維度、特征：數據對象是一個數據實例，其屬性、維度、 特征意思相同， 均為描述數據的一個域2、高維詛咒現象：數據分類的表現不會隨著維數的增加而一直上升，反而到了某個閾值后會下降因為隨著維數上升，每個類的數據變得稀疏，很多測量手段都逐漸失去意義3、數據預處理的基本方法：采樣：使用有代表性的樣本，使得樣本與總體在屬性上有相似的性質特征選擇：剔除冗余和無關特征降維：避免高維詛

20、咒、降低數據挖掘的代價、使數據更加清楚、消除噪聲三、 Classification1、監督學習和無監督學習：監督學習：使用訓練樣本訓練模型，再利用模型解析未知數據進行分類無監督學習：無訓練樣本，直接按照未知數據的相似程度建模聚類2、分類的基本原理：選定模型后，使用訓練數據訓練模型參數，之后用模型解析輸入數據得到分類3、數據的向量表示：用數據的頻數或者tf-idf 表示4、 KNN 算法：找到與待分類數據距離最近的K 個數據，然后將其分入頻數最高的類中KNN 無法免疫高維詛咒現象，但是在高維特征獨立數較小時，KNN 也適用5、 Logistic regression 算法：6、如何評價分類效果：

21、訓練誤差：訓練數據的過程中造成的錯誤測試誤差：測試的過程中造成的誤差accuracy 為測準率泛化誤差：使用模型在未知記錄上造成的分布相同的期望誤差四、 Clustering1、聚類的概念：聚類是一個把現實或抽象的對象和與它相似的對象組織到一起的過程2、聚類的基本原理：聚類內部相似性很高，聚類之間相似性很低3、層次式聚類算法流程：計算距離矩陣，默認所有數據點都是一個類每次找到距離最近的兩個類，將其合并，并更新距離矩陣，重復直到只有一個類4、類的距離定義：Single-link：使用兩個聚類之間最近的點作為聚類的距離Complete-link ：使用兩個聚類之間最遠的點作為聚類的距離Averag

22、e-link ：使用所有跨聚類的結點對的平均距離Centroid ：使用聚類重心之間的距離5、 K-means 算法流程：隨機產生k 個聚類中心點每個數據點歸類到與它最近的那個中心所代表的類- 7 -每個類重新計算中心點，返回第二步算法迭代到所有數據點的類歸屬不再改變6、 K-means 算法優化目標：每個數據點到它所屬的類中心距離的平方和最小7、 K-means 收斂性分析：均方差函數單調遞減而有界8、聚類算法的評價標準：凝聚度：計算各聚類的均方差的和分離度：不同聚類的重心要盡可能相互遠離專家評判五、社區分析：1、圖的表示、組成部分以及相關性質：點、邊（有向、無向）2、社區的概念：一組結點集

23、，集合內的點之間有很多聯系，而集合內的點與集合外的點聯系很少3、社區發現與聚類：基于結構相似性通過使用層次式聚類或分割式聚類4、結構相似度計算：結構差異測度dij ：取兩點關聯向量的差，向量中兩點所在的位置清零，取模Jaccard相似度：兩點公共鄰居數/ 兩點無重總鄰居數余弦相似度：兩點關聯向量的余弦5、 GN 算法：一對結點之間的最短路徑為路上的邊貢獻一個流若最短路徑有多條，則均分每次切除一條流量最大的邊，然后重新計算流量，迭代進行，直到無邊6、矩陣及性質：鄰接矩陣：相鄰為1，不相鄰為0度數矩陣：對角線放每個結點的度數，其余地方為0拉普拉斯矩陣：度數矩陣減去鄰接矩陣，是半正定的7、 Cut

24、的性質：Cut( A, B )表示 A 與 B 之間的邊數1?1?Cut( A, B ) = 4 ?( ?-?) ?= 4 ? ?；當 u A， y(u) = 1，當 u B， y(u) = -111RatioCut ( A,B) = cut(A, B)( |?| + |?|)NCut( A,B) =cut(A, B)(11)vol(A)表示 A 中結點度數之和+?(?)?(?)? ( ?-? )?RatioCut ( A,B) = ? ?st. ?= 0? -0.5-0.5?()?(?-? ) ? 0.5NCutA,B=?st. ? ?= 0?8、 modularity的概念：一種測量網絡劃

25、分為社區的好壞程度的指標?，期望邊數為? ? ?兩結點間的實際邊數為，每個社區內的邊數差為?2?- 2?- 8 -每個社區內邊數差相加后除以總度數2m，即為 Q( G, S 屬)于 -1, 1六、影響力分析：1、度量結點中心性的標準：Degree centrality ：結點的度，可以除以n-1 標準化Closeness centrality：結點到其他結點的平均測地距離的倒數Betweenness centrality ：該結點通過的流量，可除以(n-1)(n-2)/2 標準化Eigenvector centrality ： Ax = x，其中 x 是所有結點的Eigenvector cen

26、trality2、關系強度：刪除后會造成結點對不連通的邊叫橋刪除后造成的結點對的距離增量越大，該關系越不牢固鄰居 overlap 函數：兩結點公共鄰居數/ ( 兩結點無重總鄰居數2 )s3、影響力傳播模型：線性閾值模型LTM：關聯到某結點的激發邊的總激發值大于閾值，則該結點被激發層級傳播模型ICM：激發結點按照邊權概率激發周圍的結點區別： LTM 是基于接收者的，ICM 是基于發送者的LTM 依賴于所有鄰居結點，ICM 影響到所有鄰居結點LTM 狀態只依賴于閾值，ICM 的狀態存在隨機性但是他們都具有子模性質！4、最大影響結點集：f(S)是結點集S 最終能夠影響的結點集的大小最優化問題： max