1、Web Data mining復習與總結一、 課程主要內容數據挖掘概述+WEB數據挖掘數據挖掘（ch1 概述）：又被稱為數據庫中的知識發現（）。是指從數據源（如DB、文本、圖片、萬維網等）探尋有用的模式或知識的過程。這些模式必須是有用的、有潛在價值的、并且是可以被理解的。數據挖掘是一門多學科交叉的學科，包括機器學習、統計、數據庫、人工智能、信息檢索和可視化。WEB數據挖掘（ch6-12）的目標是從web超鏈接、網頁內容和使用日志中探尋有用的信息。依據挖掘過程中使用的數據類別，web挖掘的任務劃分為三種主要的類型：web結構挖掘、web內容挖掘和web使用挖掘。web結構挖掘：從表征web結構的

2、超鏈接中尋找知識。Ch6-ch8：信息檢索與web搜索；鏈接分析；web爬取。web內容挖掘：從網頁內容中抽取有用的信息和知識。Ch9-ch11：結構化數據抽取：包裝器生成；信息集成；觀點挖掘。web使用挖掘：從記錄每位用戶點擊情況的使用日志中挖掘用戶的訪問模式。Ch12：web使用挖掘二、 各章主要知識點（一） （ch1）概述主要知識點1、 萬維網、超文本、超鏈接、超媒體的概念；2、 HTTP，HTML，URL， WEB，TCP/IP的含義；3、 Web數據的特點：P56；4、 數據挖掘的定義、數據挖掘任務、KDD過程、KDD的數據類型等；5、 Web數據挖掘的定義、分類、web數據挖掘過程

3、等。6、 關聯規則、列模式挖掘、分類與預測、聚類挖掘的基本概念及挖掘思想。WEB結構挖掘：包括信息檢索與WEB搜索、鏈接分析、WEB爬取（二） （ch6）信息檢索與web搜索1、 基本概念：（1）信息檢索IR：即幫助使用者從大號的數據集信息中發現需要的資料。了信息的采集、組織、存儲、檢索及分發。根據用戶的查詢信息得到相應的一組文檔，得到的結果根據其與用戶查詢信息的相關程序排序，最常用的用戶查詢信息是一組關鍵字（又稱詞）。其基本信息是單個文檔，大量的文檔形成文本數據庫。（2）web搜索：是信息檢索的一個重要分支。區別于信息檢索的特點是：效率是WEB搜索的一個最為重要的問題；網頁與傳統信息檢索系統

4、中使用的普通文檔不同：（1）具有超鏈接以及錨文本、（2）網頁是半結構化的、（3）網頁中的內容基本上是有組織的，并且在一些結構塊中出現；作弊技術是網絡上的一個重要的問題。（3）IR基本架構：用戶查詢（關鍵字查詢、布爾查詢、短語查詢、鄰近查詢、全文查詢、自然語言查詢等）+查詢操作（作簡單預處理如STOP WORDS刪除等發送到檢索引擎、或處理用戶反饋關聯性反饋）+索引器（為提高查詢效率對原始文檔用某種數據結構做索引，形成文檔索引返回文檔索引，如倒排索引）+檢索系統（為每個索引文檔計算與查詢的相關度分數）關鍵字查詢布爾查詢短語查詢鄰近查詢全文查詢自然語言查詢預處理關聯性反饋倒排索引計算文檔與查詢的相

5、關度分數布爾模型（布爾查詢：AND、OR、NOT）向量空間模型（TF表、TFIDF表、查詢、相關度排名）語言模型概率模型關聯性反饋（4）查全率（recall）、查準率（precision）、查準率查全率曲線（PR曲線）、排名查準率（rank precision）、F-score（5）網頁預處理：移除停用詞、詞干提取、數字、連字號、標點、字符大小寫的處理；辨別不同的字段；辨別錨文本；移除HTML標簽；辨別主要內容塊；（6）副本探測（對整個文本HashMD5算法；基于n元短語的副本探測技術）：即復制頁面，可減少索引大小，改善搜索效率； 鏡像：復制站點的技術。（7）倒排索引：是一張列表，包含了每一個

6、不同的詞和包含該詞的文檔列表。可加快檢索和查詢的速度。其本身構建速度也非常快。記錄格式：idj,fij,o1,o2,.o|fij|倒排索引的建立及壓縮：搜索引擎基于向量空間模型和詞匹配模型。爬取網頁！元搜索引擎和組合多種排序：略網絡作弊的概念及分類：l 內容作弊（詞組作弊）：標題、元標記、正文、錨文本、網址。如內容重復、或添加其他不相關的l 鏈接作弊（影響知名度分數）：鏈出鏈接作弊（指向中心頁面目錄克隆）或鏈入鏈接作弊（創建蜜罐、網絡目錄中添加鏈接、用戶生成內容是添加鏈接、交換鏈接、自發添加等）l 隱藏技術：內容隱藏（隱藏垃圾項）、掩飾技術（垃圾網絡服務器、重定向技術等）l 抵制作弊：分類處理

7、區別對待內容作弊、鏈接作弊、隱藏技術等；信任排名方法可用。2、主要知識點（1） IR系統的基本架構及原理l 用戶查詢的主要形式：關鍵字查詢、布爾查詢、短語查詢、鄰近查詢、全文查詢、自然語言查詢的含義l 查詢操作l 索引器l 檢索系統（2） 信息檢索模型主要有四種信息檢索模型：布爾模型、向量空間模型、語言模型、概率模型。熟悉布爾模型、向量空間模型的基本原理，了解統計語言模型、概率模型。布爾模型：文檔表示法、布爾查詢、文檔檢索。向量空間模型：文檔表示法（詞頻率表TF、詞逆向文檔頻率TFIDF等）、查詢、檢出文件以及相關度排名（向量夾角余弦相似度、Okapi相關度計算、旋轉標準化權值）（3） 信息檢

8、索模型的評估標準查全率（recall）查準率（precision）查準率查全率曲線（PR曲線）排名查準率（rank precision）F-score（4）文本和網頁的預處理內容l 停用詞移除l 詞干提取l 數字的預處理l 連字號的預處理l 標點符號的預處理l 字符大小寫的預處理*網頁預處理步驟：l 辨別不同的字段：標題、元數據、正文等l 辨別錨文本l 移除HTML標簽l 辨別主要內容塊（根據視覺線索分塊、樹匹配）l 副本探測（5）倒排索引及其壓縮l 倒排索引的概念：l 使用倒排索引搜索的算法步驟搜索詞匯表、結果合并、計算排名分數l 索引的建立方法：使用TRIE數據結構相比其他的結構更加有效。

9、l 索引的壓縮方法：常用的有兩種，即變位模式（一元編碼、Elias gamma編碼和delta編碼）和變字節模式（整數對應到自定義的二進制編碼）。l 索引壓縮的解碼：一元編碼的解碼、變字節編碼的解碼了解（6）隱式主義索引（略）（7）WEB搜索搜索引擎搜索引擎基于向量空間模型和詞匹配模型。爬取網頁！搜索引擎的工作步驟：分解（parsing）；索引（indexing）；搜索并排序（預處理、利用倒排索引查找含有全部查詢詞的頁面、對頁面排序并返回給用戶）。其中排序算法是核心。搜索引擎的排序算法：網頁質量和網頁知名度是排序的重要因素。可利用超鏈接（鏈入鏈接pagerank算法、鏈出鏈接） 的數量作為排序

10、網頁的指標之一；內容質量可利用（1）出現的形式，如標題、錨文本、網址、正文等；（2）計數：以不同形式出現的詞的計數；（3）位置：對于以不同出現形式出現的詞的位置記錄。基于內容的網頁評估分數（IR分數）與知名度分數的加權和以得到網頁的排名分數。另見第七章中的計算方法。搜索引擎的兩種查詢方式：單詞語查詢和多詞語查詢。網絡作弊技術：使用人為的手段，讓一些網頁高于其應有的排名。網頁作弊的主要形式：內容作弊、鏈接作弊、隱藏技術（內容隱藏、掩飾技術、重定向）、抵制作弊（信任排名等技術）。（三） （ch7）鏈接分析1、 基本概念(1)社會關系網：是一門研究社會中社會實體（組織中的人、或者叫參與者）以及他們之

11、間的活動與關系的學問。這種關系或活動可以用網絡或圖來表示。(2)社會網絡分析：分析研究社會關系網絡的結構特性，以及每個參與者的職責、位置、威望等屬性；找出各種類型的子圖。l 社會網絡分析方法：中心性和權威性。l 中心性（鏈出）的概念：鏈接（連接）、中心參與者。度中心性（有向圖、無向圖的度中心性）接近中心性（無向圖、有向圖的接近中心性）中介中心性（無向圖、有向圖的中介中心性）l 權威性（鏈入）的概念度權威鄰近權威等級權威(pagerank、hits算法)(3)同引分析的概念：用來度量不由自主文檔之間的相似性。引文耦合的概念： 將引用同一篇其他論文的兩篇論文聯系起來。兩篇論文引用的相同文章數目越多

12、，它們之間就越相似。Pagerank算法的基本思想Hits算法的基本思想社區發現的相關概念。2、 主要知識點(1)社會網絡分析：分析研究社會關系網絡的結構特性，以及每個參與者的職責、位置、威望等屬性；找出各種類型的子圖。(2)絡分析方法：中心性和權威性，這兩種指標對于網絡搜索以及鏈接分析都有非常密切的關系，是社會關系網中參與者的著名程度進行度量的標準。中心性（鏈出）的概念：鏈接（連接）、中心參與者。三種中心性度量：度中心性（有向圖、無向圖的度中心性）、接近中心性（無向圖、有向圖的接近中心性）、中介中心性（無向圖、有向圖的中介中心性）。權威性（鏈入）的概念：度權威、鄰近權威、分級權威(pager

13、ank、hits算法)。度權威：鄰近權威：等級權威：(3)同引分析的概念：用來度量不由自主文檔之間的相似性。引文耦合的概念： 將引用同一篇其他論文的兩篇論文聯系起來。兩篇論文引用的相同文章數目越多，它們之間就越相似。PAGERANK算法：1998年4月提出。了解基本思想及原理。PAGERANK算法的優缺點PAGERANKT可能改進timed pagerank算法的基本思想。HITS算法：1998年1月提出。了解其基本思想。(4)掌握同引分析與引文耦合與PAGERANK算法和HITS算法的關系。HITS算法的優點、缺點及可能的改進。了解社區發現的基本原理。（四） （ch8）WEB爬取1. 基本概

14、念（1）WEB爬蟲（蜘蛛或機器人）：能自動下載網頁的程序。（2）WEB爬蟲的分類：通用爬蟲、限定爬蟲、主題爬蟲。通用爬蟲限定爬蟲主題爬蟲（3）簡單爬蟲算法：種子URL、隊列、頁面獲取、網頁庫等模塊。l 寬度優先爬蟲l 帶偏好的爬蟲網頁獲取/網頁解析/刪除無用詞、詞干提取、鏈接提取和規范化/爬蟲陷井網頁庫爬蟲消耗的資源：網絡、中CPU和磁盤。(4)爬蟲的改進：實現并發性（并行爬蟲架構）。通用爬蟲：可擴展性、爬蟲覆蓋率、新鮮度和重要度。限定爬蟲：能爬取用戶感興趣的某一類網頁。熟悉概念。主題爬蟲：帶偏好爬取網頁的爬蟲。熟悉概念。了解通用爬蟲、限定爬蟲、主題爬蟲的聯系與區別。2、 主要知識點簡單爬蟲算

15、法及改進（并行爬蟲）。限定爬蟲算法的基本思想。主題爬蟲的基本原理。三種爬蟲算法的聯系與區別WEB內容挖掘：包括結構化信息抽取、信息集成、觀點挖掘。（五） (ch9)結構化數據抽取：包裝器生成1、基本概念（1）WEB信息抽取：從網頁中抽取目標信息，包括：從自然語言文本中抽取信息及從網頁的結構化數據中抽取信息。l 包裝器：抽取結構化數據的程序。l WEB結構化數據：從后臺數據庫獲取的數據記錄，它們按照一定的模板被展現在網頁上。l 數據記錄（2）信息抽取的主要方法：手工方法、包裝器歸納（監督學習方法）、自動抽取（無監督學習方法）。l 數據抽取：給定由HTML標記編碼的數據（網頁），抽取系統恢復數據模

16、型并從編碼后的數據記錄中抽取數據。即從HTML編碼的數據中恢復隱藏的模式。l 列表頁l 詳情頁l 數據模型：嵌套關系；基本類型、元組類型、集合類型、平坦元組類型、平坦集合類型；平坦關系；集合類型實例；元組類型實例等。l 數據實例的HTML編碼（3）包裝器歸納的概念及基本原理EC樹開始規則/結束規則地標通配符析取規則學習抽取規則：正規則、負規則地標提純拓樸提純 包裝器學習的重要問題之一：手工標注訓練樣例。費時費力。可能的包裝器歸納學習的改進：主動學習或協同測試的方法。l 主動學習：是一種幫助自動識別提供信息的未標注樣例的方法。包裝器學習中主動學習步驟：從U中隨機選取一個較小的未標注樣例子集L；手

17、工標注L中的樣例，并令UUL；基于標注樣例集L學習一個包裝器；將W應用于U以找到一個提供信息樣例的集合L；如果L，則終止，否則轉。 算法的關鍵是步。l 協同測試的方法可用來識別提供信息的樣例。了解其基本思想。l 包裝器維護：包裝器驗證問題、包裝器修復問題。學習目標數據項的特征模式，以監視抽取工作以及檢驗所抽取的數據項是否正確。再標注，再學習。l 基于實例的包裝器學習：不用學習抽取規則，而是通過將目標數據項的前綴和后綴標志字符串與對應的標注好的樣例進行比較，來從一個新的實例或網頁中識別目標數據項。如果一個未標注的樣例中，某個數據項不能被識別。則它將被交付標注，這是沒有附加機制的主動學習。（4）自

18、動包裝生成中的問題：手工標注不適合對大量站點的抽取；包裝器維護的開銷很大。l 包裝器自動生成中的模板：指代網頁設計者所采用的隱藏模板。l 包裝器自動生成中的模式：指代系統所發現的規則結構。l 包裝器的應用兩個抽取問題：基于一張列表頁的抽取；基于多張網頁的抽取。從一組編碼好的同種類型的實例中尋找編碼模板檢測HTML編碼字符串中重復出現的模式。l 信息抽取技術：字符串匹配和樹匹配。l DOM：文檔對象模型標簽樹。l 字符串的編輯距離：即萊文斯坦距離，定義為將串S1變成串S2所需要的點突變的最少次數。l 點突變是指下列操作之一改變一個字符；插入一個字符；刪除一個字符。l 掌握字符串的對齊算法。l 樹

19、匹配中的樹編輯距離：是將樹A變換為樹B所需要的最小操作集對應的代價。l 樹編輯距離的操作包括：節點刪除；節點插入和節點替換。每個操作都被指定了一個代價。l 解樹編輯距離問題應時尋找兩棵樹間的最小代價映射。l 樹代價映射的定義l 簡單樹匹配STM：不允許節點替換和層次交叉，STM的目標是找到兩棵樹間的最大匹配。l 最大匹配：設A、B是兩棵樹，而iA和jB是A和B中的兩節點，兩棵樹間的一個匹配定義為一個映射M，使得對每一個節點對（i,j）M,( i,j都不是根節點)，都有（parent(i）,parent(j) M。一個最大匹配就是一個擁有最多節點對的匹配。了解STM算法多重對齊：產生一個對所有字

20、符串或樹的全局對齊任務稱為多重對齊。 兩種多重對齊算法：中星方法和部分樹對齊。中星方法部分樹對齊方法：構建DOM樹標簽樹。標簽樹的構建方法：標簽方法或用標簽和視覺提示的方法。利用標簽構建DOM樹：HTML編碼清理；樹的構建。用標簽和視覺提示構建DOM樹：通過調用瀏覽器的渲染引擎找到每一個HTML元素長廊形的四個邊界；依據開始標簽序列進行包含檢驗以構建標簽樹。包含檢驗：是指檢驗一個長方形是否被另一個長方形包含。基于列表頁的抽取：平坦數據記錄的抽取假設網頁的DOM樹已經構建，給定一個含有多個列表，且每個列表含有多個數據記錄的列表頁，將執行下列任務：（1）識別每個列表（也稱為數據區域），即挖掘所有數

21、據區域（挖掘廣義節點序列；比較廣義節點；）；MDR算法（2）將每個列表或數據區域內的數據記錄分段，以及；識別數據記錄、（3）對齊數據記錄中的數據項以為每一個數據區域產生一個數據表和一個正則表達式。數據項對齊與抽取；沖突消解；利用視覺信息等；基于列表頁的抽取嵌套數據記錄（NET算法：后序遍歷）：了解2 主要知識點信息抽取的主要方法：手工方法、包裝器歸納（監督學習方法）、自動抽取（無監督學習方法）。（1）數據抽取：給定由HTML標記編碼的數據（網頁），抽取系統恢復數據模型并從編碼后的數據記錄中抽取數據。即從HTML編碼的數據中恢復隱藏的模式。列表頁/詳情頁數據模型：嵌套關系；基本類型、元組類型、集

22、合類型、平坦元組類型、平坦集合類型；平坦關系；集合類型實例；元組類型實例等。數據實例的HTML編碼（2）包裝器歸納的概念及基本原理l EC樹l 開始規則/結束規則l 地標l 通配符l 析取規則l 學習抽取規則：正規則、負規則l 地標提純l 拓樸提純 包裝器學習的重要問題之一：手工標注訓練樣例。費時費力。可能的包裝器歸納學習的改進：主動學習或協同測試的方法。了解主動學習：是一種幫助自動識別提供信息的未標注樣例的方法。包裝器學習中主動學習的算法步驟：（1）從U中隨機選取一個較小的未標注樣例子集L；（2）手工標注L中的樣例，并令UUL；（3）基于標注樣例集L學習一個包裝器；（4）將W應用于U以找到一

23、個提供信息樣例的集合L；（5）如果L，則終止，否則轉（2）。 算法的關鍵是（4）步。協同測試的方法可用來識別提供信息的樣例。了解其基本思想。包裝器維護：包裝器驗證問題、包裝器修復問題。學習目標數據項的特征模式，以監視抽取工作以及檢驗所抽取的數據項是否正確。再標注，再學習。基于實例的包裝器學習：不用學習抽取規則，而是通過將目標數據項的前綴和后綴標志字符串與對應的標注好的樣例進行比較，來從一個新的實例或網頁中識別目標數據項。如果一個未標注的樣例中，某個數據項不能被識別。則它將被交付標注，這是沒有附加機制的主動學習。（3）自動包裝生成中的問題：手工標注不適合對大量站點的抽取；包裝器維護的開銷很大。包

24、裝器自動生成中的模板：指代網頁設計者所采用的隱藏模板。包裝器自動生成中的模式：指代系統所發現的規則結構。包裝器的應用兩個抽取問題：基于一張列表頁的抽取；基于多張網頁的抽取。從一組編碼好的同種類型的實例中尋找編碼模板檢測HTML編碼字符串中重復出現的模式。（4）信息抽取技術：字符串匹配和樹匹配及相關算法。DOM：文檔對象模型標簽樹。字符串的編輯距離：即萊文斯坦距離，定義為將串S1變成串S2所需要的點突變的最少次數。點突變是指下列操作之一改變一個字符；插入一個字符；刪除一個字符。掌握字符串的對齊算法。樹匹配中的樹編輯距離：是將樹A變換為樹B所需要的最小操作集對應的代價。樹編輯距離的操作包括：節點刪

25、除；節點插入和節點替換。每個操作都被指定了一個代價。解樹編輯距離問題應時尋找兩棵樹間的最小代價映射。樹代價映射的定義簡單樹匹配STM：不允許節點替換和層次交叉，STM的目標是找到兩棵樹間的最大匹配。最大匹配：設A、B是兩棵樹，而iA和jB是A和B中的兩節點，兩棵樹間的一個匹配定義為一個映射M，使得對每一個節點對（i,j）M,( i,j都不是根節點)，都有（parent(i）,parent(j) M。一個最大匹配就是一個擁有最多節點對的匹配。了解STM算法多重對齊：產生一個對所有字符串或樹的全局對齊任務稱為多重對齊。 兩種多重對齊算法：中星方法和部分樹對齊。中星方法掌握運用部分樹對齊方法：掌握應

26、用構建DOM樹標簽樹。標簽樹的構建方法：標簽方法或用標簽和視覺提示的方法。利用標簽構建DOM樹：HTML編碼清理；樹的構建。用標簽和視覺提示構建DOM樹：通過調用瀏覽器的渲染引擎找到每一個HTML元素長廊形的四個邊界；依據開始標簽序列進行包含檢驗以構建標簽樹。包含檢驗：是指檢驗一個長方形是否被另一個長方形包含。基于列表頁的抽取：平坦數據記錄的抽取平坦數據記錄抽取流程或算法步驟：假設網頁的DOM樹已經構建，給定一個含有多個列表，且每個列表含有多個數據記錄的列表頁，將執行下列任務（應盡量細化內核）：（1）識別每個列表（也稱為數據區域），即挖掘所有數據區域（挖掘廣義節點序列；比較廣義節點；）；MDR

27、算法， （2）將每個列表或數據區域內的數據記錄分段，以及；識別數據記錄、（3）對齊數據記錄中的數據項以為每一個數據區域產生一個數據表和一個正則表達式。數據項對齊與抽取；沖突消解；利用視覺信息等；基于列表頁的抽取嵌套數據記錄（NET算法：后序遍歷）：了解（六） (ch10)信息集成1、基本概念（1）信息集成：最初的研究是針對關系數據庫和數據倉庫。（2）WEB全局搜索界面：是用來產生查詢字從而到WEB數據庫（深層WEB）中獲取相關信息的。全局搜索界面允許用戶輸入相關的信息，系統根據用戶提供的信息自動填寫所有的源搜索界面從而從各個站點獲取所。各站點返回的數據需要經過集成，展示給用戶。（3）樣式表匹配

28、：是指對于兩個或更多個數據庫的樣式表建立映射，把具有相同意義的屬性（或元素）映射到一起。目的是把多個樣式表整合為一張全局的統一的樣式表。（4）樣式表的匹配方法：半自動化的匹配（有難度，基于啟發式的領域知識）或自動匹配（難度很大，產生候選匹配由用戶確認）。l 基于輸入信息，樣式表匹配的不同類型：樣式表層次的匹配、領域和實例層次的匹配；樣式表、領域、實例整合的匹配。l 樣式表匹配的預處理：分詞、擴展、移除無用詞和詞干提取、詞的標準化等。l 匹配類型：1：1；1：m；m：1；m：nl 樣式表層次的匹配中，主要有兩種信息：樣式表中屬性的名稱、描述等的自然語言詞匯（基于語言學的算法名稱匹配、上位關系、基

29、于描述的匹配等）；樣式表中的限制（數據類型和數值范圍、唯一性、關系類型的的限制等）。l 基于領域和實例層次的匹配：在WEB數據庫中，數據實例易于獲得；有些應用中，屬性的領域信息也是可獲得的。l 屬性的領域分為：簡單領域和復雜領域。l 簡單領域是指該領域中的實例值都是簡單的，也就是非合成的。l 數據類型：如果樣式表對于屬性的類型沒有說明，則需要通過屬性的實例值來判斷元素的數據類型。l 識別數據類型的方法：半自動方法（即正則表達式匹配的方法）和自動化方法（使用機器學習的方法）。l 匹配算法：DI 1DI6 簡單領域匹配算法l DI 1使用數據類型作為限制信息，建立對應表來描述一系列預定義好的數據類

30、型之間的兼容度。l DI 2對于數字類型的數據，數值范圍、平均值和言狀都可以被用來計算他們之間的數據類型的相似度。l DI 3對于不確定的數據類型，可以抽取和比較兩個元素的實例值，以決定其屬性是否匹配。l DI 4對于字母和數字混雜的數據類型，字符串的長度和字母/非字母的比例都是非常有用的信息。l DI 5對于文本數據，可以用夾角余弦計算屬性之間的相似度。l DI 6把樣式表元素的名稱添加到實例值中進行比較。l 復合的領域和屬性：一個K元的復合領域是一個有序的K元組，其中第i個部分是第i個子領域的值，記作di。每個di都是一個簡單領域。如果一個屬性所有的領域是復合的，則稱該屬性是復合的屬性。l

31、 一個復合領域通常可以通過它的實例值來反映。往往含有各種形式的分隔符，或其他的特殊單詞。進行復合領域的匹配時，為了保證分隔的正確性，需要大量的實例值。l 算法DI 7一個簡單領域與一個復合領域的相似度是通過比較簡單領域和復合領域的各個子領域來實現的。兩個復合領域的相似度也是通過比較他們各自所包含的簡單子領域的相似性來決定的。l 不同相似度的聯合：可通過多種策略實現取最大值的策略；加權和；加權平均；機器學習的方法。l 1：m匹配對于part-of 類型的匹配；對于is-a類型的匹配l 樣式表匹配的結果的處理：最熱門N個候選；取最大相似度；閾值篩選等。（5）WEB全局搜索界面：把多個搜索界面集成為

32、一個以提供給用戶一個全局的搜索因人而異，無需用戶逐個手動搜索各個數據源，只需在全局搜索界面上輸入所需的信息即可。l WEB全局搜索界面與普通的信息集成的區別：在WEB搜索界面中縮寫記號使用非常有限；詞匯有限；WEB中有大量的相似數據庫（網頁）；附加的結構。l WEB全局搜索界面集成的方法：基于聚類的算法；基于互關系的方法；基于實例的方法。l WEB全局搜索界面構建步驟：l 一個良好的全局搜索界面應該滿足的條件：結構上的正確性；詞匯的正確性和實例的正確性。2、主要知識點（1）信息集成：從單一網站上抽取信息往往是不夠的，需要從大量的站點中提取數據，然后對提取出的數據進行集成以便提供增值服務。對不同

33、的數據而言集成意味著匹配出表示同類信息的列，或者匹配出語義相同但是表達方式不同的值，并可能存放在后臺數據庫中。（2）信息集成的基本方法：樣式表匹配抽取樣式表樣式表預處理樣式表層次的匹配（基于語言學的算法、或基于樣式表中限制的算法）、基于領域和實例層次的匹配（簡單領域匹配方法半自動的方法或自動的方法；復合領域匹配的方法）、樣式表/領域/實例整合的匹配； 大量樣式表的匹配（借助聚類算法、互關系或模式發現算法）樣式表匹配的結果處理（最熱門的N個候選；最大相似度；閾值篩選等）用戶交互（匹配系統搭建；匹配的后期工作）。（3）WEB搜索界面的集成：全局搜索界面的構建全局搜索界面樣式表：全局搜索界面構建：基

34、于聚類的算法、基于互關系的方法、基于實例的方法。基于聚類的算法：了解實現思想基于互關系的方法：了解實現思想基于實例的方法：了解實現思想（七） (ch11)觀點挖掘1、基本概念l 背景：從網頁中抽取的結構化數據通常在網頁設計時是來自于一個后臺的數據庫，并遵循一定的模板格式顯示在網頁中。此外，網頁中還存在大量的非結構化的文本信息，包括了所有類型的各種有價值的信息，分析這些信息是非常重要的。l 觀點挖掘的背景：企業需要了解用戶對其產品或服務的評價；新用戶需要知道現有用戶對某產品或服務的評價；了解評價可為廣告放置提供參考等。l 現實性與可能性：網絡用戶有多種發表觀點的方法：商業網站、產品或服務評價、博

35、客、論壇等。本章內容：評估文本、觀點搜索、觀點欺詐。（1）評估文本的三個挖掘任務：意見分類、基于特征的觀點挖掘和摘要、比較性句子和比較關系挖掘。（2）觀點挖掘：可以使用戶搜索關于任何對象的觀點。（3）觀點欺詐：欺詐性觀點是指有些人為推銷自身產品或服務。或者損害競爭對手聲譽而發表的那些不切實際的或者懷有惡意的觀點。l 意見分類：正面評論、負面評論和中立評論。意見分類主要用于快速判定大眾對一個對象的普遍觀點。該任務和傳統的基于主題的文本分類相似。但有不同。意見分類中主題相關的詞匯并不重要，表征正面或負面觀點的詞匯更加重要。意見分類的研究層次：主要是文檔層次；其次還有句子層次的。意見分類的具體方法：

36、基于意見短語的分類；采用文本分類方法進行意見分類；基于評分函數進行分類。l 基于意見短語的分類：基于各個評估文本中正面和負面的意見詞和短語。算法步驟：基于調整性標注的自然語言處理技術S1. 抽取包含有形容詞和副詞的短語，采用賓州樹庫詞性標注集（表11.1）+基于特征的觀點摘要（表11.2）；S2. 采用點對互信息估計所抽取的短語的語義傾向（一個短語的語義傾向SO基于它和正面參考詞“excellent”與負面詞“poor”的關聯程度進行計算）；S3. 給定一個評審。算法計算評審中所有短語的平均SO。如果平均SO是正的，則為正面證人否則為負面評價。l 采用文本分類方法進行意見分類：將該問題作為基于

37、主題的文本分類問題，可采用naïve Bayesian, VM, N等方法。l 基于評分函數進行分類：采用通用評分函數，算法步驟為：S1. 在訓練集中采用評分公式為每個詞賦值，介于11之間；S2.算法將新文檔的所有詞的評分求和，并給出分類的判斷。基于特征的觀點挖掘和摘要：一個關于特定對象的正面評估文本并不能說明作者對于該對象的任一方面都有正面的評價。在一個特定產品的評審中，評審人通常會同時給出一個產品的正面或負面評價，挖掘往往作用于句子層面。l 定位和抽取評審者所評論產品的特征產品特征l 判定對于特定特征的評價是正面的、負面的還是中立的。對象：一個對象O是指一個實體,它可以是一個產品

38、、人物、事件、組織或者主題。它關聯到一個序對O：（T，A），其中T是一個層次化或者結構化的部件（或者組件）、子部件等。A是一個關于屬性的集合，每個部件都擁有它自己的子部件或屬性集合。O：數碼相機部件：lens,battery,view-finder.Battery: life, size, weight. 顯式特征和隱式特征：如果一個特征f出現在一個評估文本r中，則稱它是r的一個顯式特征。如果f沒有在r中出現，則稱其為r的一個隱式特征。如 the battery life of this camera is too short. This camera is too large.某一特征的觀點

39、段：一個關于對象r的特征f的觀點段是r中一組表達了關于f的正面或者負面觀點的連續句子。如：the battery quality is good, but the battery life is short.大多數的研究集中在句子上。每個段落由一個單獨的句子組成。顯式觀點和隱式觀點：一個關于特征f的顯式觀點是一個直接表達了正面或負面觀點的主觀句子。一個關于特征f的隱式觀點是一個蘊含了正面或負面觀點的客觀句子。如：this picture quality of this camera is amazing. The earphone broke in two days.觀點持有對象：關于某一特定

40、觀點的持有對象是指擁有這一觀點的人或組織。一個對象和該對象之上的觀點集合的簡要模型：一個對象可以被表示為一個關于特征的有限集合Ff1,f2,fn，每一個F中的特征fi都可以表示為一個同義詞或者同義短語Wi的集合。即對于n個特征，有一個對應的同義詞集合WW1，W2，Wn。由于每個F中的特征fi都有一個名字（標記為fi），可得到fiWi。每個作者或觀點持有對象j對一個特征的子集SjÍF進行評論。對于每個觀點持有對象進行評論了的特征fkSj，可以從Wk中選擇一個詞或者短語來描述該特征，并對其表達正面或負面的觀點。給定一個評測文本集合D作為輸入，則可有如下三個問題：P1：F和W都是未知的，在

41、觀點挖掘中需要挖掘的任務T1、T2和T3.T1：從每個評估dD中定位與抽取被評估對象的特征。T2：確定對于該特征的觀點是正面的、負面的或中立的。T3：由于不同的人可能采用不同的詞或短語來描述同樣的特征。需將各個特征的同義詞進行歸并。P2：F已知而W未知。與P1類似有三個任務，但處理更簡單。其中T1與T2同前；但T3可將已發現的特征與給定特征集合F進行匹配而求解。P3：W已知（可以推出F也是已知的）。僅需要進行任務T2，即在抽取所有包含相應特征的句子后，確定一個已知特征上的觀點是正面的，負面的還是中立的。基于特征的摘要：形成針對某一對象的各種觀點的基于特征的摘要。對象特征提取：主要用在在線產品的

42、評審上。有三種類型的評審格式，不同的評審格式需要不同的技術進行特征提取。格式1：區分正面、負面以及細節的評審。評審者被要求獨立地描述正面和負面觀點；此外，還要給出細節評審。格式2：區分正面和負面的評審。評審者被要求獨立地描述正面和負面觀點；但不需要給出獨立的細節評審。格式3：自由格式。評審者可以自由地給出評價。不必區分正面或負面觀點。格式1中特征抽取算法：S1：用于LSR挖掘的訓練數據準備；S2：標記順序規則挖掘；找到包含特征的規則，詞性標注和詞形成語言模式； S3：特征抽取，考慮三種情形：l 如果一個句子片段匹配多個規則的處理l 對于沒有規則適用的句子片段，如果存在，被詞性標注工具標出來的名

43、詞和名詞短語被抽取為特征；l 對于只有一個詞的句子片段，單一詞匯被對待為特征。隱式特征匹配同義詞分組特征粒度格式2和格式3的特征抽取算法：了解S1：找到所有的調頻名詞和名詞短語；名詞和名詞短語可能通過詞性標注工具勷S2：通過利用意見詞找到不頻繁出現的特征。意見詞（又稱觀點詞）通常表達正面或負面評價的形容詞和副詞。觀點傾向分類：意見詞和短語是那些表達了正面或負面意見（觀點）的詞，通常是形容詞和副詞，也可是動詞或名詞。已構建了意見詞的集合l 人工找到一個正面或負面詞匯、成語的種子集合，為形容詞、動詞、名詞和副詞、成語等都準備一個單獨的種子集合。l 在WORDNET中迭代地查找它們的同義詞和反義詞，

44、以此擴展種子集合直到收斂。l 人工檢查結果，并去除不正確的詞匯。l 識別句子的意見詞和短語，是正面的則賦值 +1，負面的賦值 為1，所有的賦值相加，為正則結論是正面的，否則結論為負面的。比較性句子和比較關系挖掘直接表達某一對象的正面或負面觀點只是評估的一種形式，將一個對象和其他同等對象進行比較是另一種形式。比較也是更能讓人信服的一種方式。分為主觀比較和客觀比較。如the picture quality of camera x is great. 典型句子主觀比較：the picture quality of camera x is better than that of camera y.客觀

45、比較：camera Xis 20 grams heavier than camera y.比較性句子和判定比較關系是很難的。很多包含比較級（最高級）的句子并不是比較格式；而不包含這類詞的句子卻是比較性句子。比較性句子：是一個表達了多個對象之間的相似或者不同關系的句子，比較性句子中的比較關系通常由一個形容詞或副詞的比較級或最高級來表達。幾種重要的比較類型：等級比較和非等級比較，其中等級比較可進一步分為形容詞和副詞比較。等級比較包括：不相等的等級比較、相等等級的比較、最高級的比較。非等級比較比較了兩個或者多個對象的特征，但并不對他們進行分級。可分為三種類型：對象A和對象B在某些特征上相似或者不同；

46、對象A有特征f1，而對象B有特征f2；對象A擁有特征f，但是對象B沒有。比較性句子的三種類型：非平等等級比較；平等比較；最高級比較。比較關系的抽取：l 序列數據產生：用于挖掘的順序數據庫創建；在數據中手工標記每個句子的標號詞.l LSR的生成挖掘規則系統被用來生成標號順序規則。l 關系項抽取，如使用規則來匹配句子，并用具有最高置信度的規則來抽取關系項。觀點搜索包括：1. 搜索某一特定對象或對象特征上的觀點。2. 搜索某一個人或組織對某一特定對象或對象特征的看法。觀點欺詐指人們故意誤導讀者和自動觀點挖掘系統的行為（比如撰寫欺詐性的評審）。觀點欺詐的目的：推銷某些目標對象；損害某些其他目標對象的聲

47、譽等。觀點欺詐的行為：為了推銷目標對象撰寫一些不切實際的正面評審炒作欺詐；為了詆毀某些目標對象的聲譽，撰寫一些不公平或者惡毒的反而評審誹謗欺詐。欺詐和欺詐者的種類：人工欺詐和自動欺詐；個人欺詐和群組欺詐。隱藏技巧：欺詐者為了避免被檢測出來所采取的預防措施。欺詐檢測：面向評論的欺詐檢測；面向評論者的欺詐檢測；面向服務器的欺詐檢測。面向評論的欺詐檢測：比較內容相似性；檢測評分和內容例外；比較多個網站的平均打分；檢測評分例外。面向評論者的欺詐檢測：觀察早期用戶；檢測早期修正動作；比較同一評論者對于不同品牌產品的評論打分；比較評論時間。面向服務器的欺詐檢測。2、主要知識點（1）意見分類l 基于意見短語

48、的分類算法：基于各個評估文本中正面和負面的意見詞和短語。算法步驟：基于調整性標注的自然語言處理技術S1. 抽取包含有形容詞和副詞的短語，采用賓州樹庫詞性標注集（表11.1）+基于特征的觀點摘要（表11.2）；S2. 采用點對互信息估計所抽取的短語的語義傾向（一個短語的語義傾向SO基于它和正面參考詞“excellent”與負面詞“poor”的關聯程度進行計算）；S3. 給定一個評審。算法計算評審中所有短語的平均SO。如果平均SO是正的，則為正面證人否則為負面評價。l 采用文本分類方法進行意見分類：將該問題作為基于主題的文本分類問題，可采用naïve Bayesian, VM, N等方法

49、。l 基于評分函數進行分類：采用通用評分函數，算法步驟為：S1. 在訓練集中采用評分公式為每個詞賦值，介于11之間；S2.算法將新文檔的所有詞的評分求和，并給出分類的判斷。（2） 基于特征的觀點挖掘和摘要：一個關于特定對象的正面評估文本并不能說明作者對于該對象的任一方面都有正面的評價。在一個特定產品的評審中，評審人通常會同時給出一個產品的正面或負面評價，挖掘往往作用于句子層面。l 定位和抽取評審者所評論產品的特征產品特征l 判定對于特定特征的評價是正面的、負面的還是中立的。對象：一個對象O是指一個實體,它可以是一個產品、人物、事件、組織或者主題。它關聯到一個序對O：（T，A），其中T是一個層次

50、化或者結構化的部件（或者組件）、子部件等。A是一個關于屬性的集合，每個部件都擁有它自己的子部件或屬性集合。O：數碼相機部件：lens,battery,view-finder.Battery: life, size, weight. 顯式特征和隱式特征：如果一個特征f出現在一個評估文本r中，則稱它是r的一個顯式特征。如果f沒有在r中出現，則稱其為r的一個隱式特征。如 the battery life of this camera is too short. This camera is too large.某一特征的觀點段：一個關于對象r的特征f的觀點段是r中一組表達了關于f的正面或者負面觀點的

51、連續句子。如：the battery quality is good, but the battery life is short.大多數的研究集中在句子上。每個段落由一個單獨的句子組成。顯式觀點和隱式觀點：一個關于特征f的顯式觀點是一個直接表達了正面或負面觀點的主觀句子。一個關于特征f的隱式觀點是一個蘊含了正面或負面觀點的客觀句子。如：this picture quality of this camera is amazing. The earphone broke in two days.觀點持有對象：關于某一特定觀點的持有對象是指擁有這一觀點的人或組織。一個對象和該對象之上的觀點集合的簡要模型：一個對象可以被表示為一個關于特征的有限集合Ff1,f2,fn，每一個F中的特征fi都可以表示為一個同義詞或者同義短語Wi的集合。即對于n個特征，有一個對應的同義詞集合WW1，W2，Wn。由于每個F中的特征fi都有一個名字（標記為fi），可得到fiWi。每個作者或觀點持有對象j對一個特征的子集SjÍF進行評論。對于每個觀點持有對象進行評論了