圖書簡介
前言
譯者
2009年3月譯者序序言
過去幾十年里，Web的迅速發展使其成為世界上規模最大的公共數據源。Web數據挖掘的目標是從Web超連結、網頁內容和使用日誌中探尋有用的信息。依據在挖掘過程中使用的數據類別，Web挖掘的任務可以被劃分為三種主要類型：Web結構挖掘、Web內容挖掘和Web使用挖掘。Web結構挖掘從表征Web結構的超連結中尋找知識。Web內容挖掘從網頁內容中抽取有用的信息和知識。而Web使用挖掘則從記錄每位用戶點擊情況的使用日誌中挖掘用戶的訪問模式。
因此，本書自然的分為兩大部分。第一部分，包括第2~5章，介紹數據挖掘的基礎。第二部分，包括第6~12章，介紹Web相關的挖掘任務。
有兩大指導性原則貫穿本書始末。其一，本書的基礎內容適合本科生閱讀，但也包括足夠多的深度資料，以滿足打算在Web數據挖掘和相關領域研讀博士學位的研究生。書中對讀者的預備知識幾乎沒有作任何要求，任何對算法和機率知識稍有理解的人都應當能夠順利地讀完本書。其二，本書從實踐的角度來審視Web挖掘的技術。這一點非常重要，因為大多數Web挖掘任務都在現實世界中有所套用。在過去的幾年中，我有幸直接或間接地與許多研究人員和工程人員一起工作，他們來自於多個搜尋引擎、電子商務公司，甚至是對在業務中利用Web信息感興趣的傳統公司。在這個過程中，我獲得了許多現實世界問題的實踐經歷和第一手知識。我儘量將其中非機密的信息和知識通過本書傳遞給讀者，因此本書能在理論和實踐中有所平衡。我希望本書不僅能夠成為學生的教科書，也能成為Web挖掘研究人員和實踐人員獲取知識、信息，甚至是創新想法的一個有效渠道。
序言序言致 謝
在撰寫本書的過程中，許多研究人員都給予我無私的幫助；沒有他們的幫助，這本書也許永遠無法成為現實。我最深切的感謝要給予Filippo Menczer和Bamshad Mobasher，他們熱情地撰寫了本書中重要的兩個章節，他們也是相關領域的專家。Filippo負責Web爬取這一章，Bamshad負責Web使用挖掘這一章。我還要感謝Wee Sun Lee（李偉上），他幫助完成第5章半監督學習的很大一部分。
Jian Pei（裴健）幫助撰寫了第2章中PrefixSpan算法，並且檢查了MS-PS算法。Eduard Dragut幫助撰寫了第10章的最後一節，並且多次閱讀並修改這一整章。Yuanlin Zhang對第9章提出很多意見。我對他們所有人都有所虧欠。
還有許多研究人員以各種方式提供了幫助。Yang Dai（戴陽）和Rudy Setiono在支持向量機（SVM）上提供幫助。Chris Ding（丁宏強）對連結分析提供了幫助。Clement Yu（余德）和ChengXiang Zhai（翟成祥）閱讀了第6章。Amy Langville閱讀了第7章。Kevin C.-C. Chang（張振川）、Ji-Rong Wen（文繼榮）和Clement Yu（余德）幫助了第10章的許多方面。Justin Zobel幫助理清了索引壓縮的許多議題。Ion Muslea幫助理清了包裹簡介的一些議題。Divy Agrawal、Yunbo Cao（曹雲波）、Edward Fox、Hang Li（李航）、Xiaoli Li（李曉黎）、Zhaohui Tan、Dell Zhang（張德）和Zijian Zheng幫助檢查了各個章節。在此對他們表示感謝！
和許多研究人員的討論也幫助本書的成形。這些人包括Amir Ashkenazi、Imran Aziz、 Roberto Bayardo、Wendell Baker、Ling Bao、Jeffrey Benkler、AnHai Doan、Byron Dom、Michael Gamon、Robert Grossman、Jiawei Han（韓家煒）、Wynne Hsu、Ronny Kohavi、David D. Lewis、Ian McAllister、Wei-Ying Ma（馬維英）、Marco Maggini、Llew Mason、Kamel Nigan、Julian Qian、Yan Qu、 Thomas M. Tirpak、Andrew Tomkins、Alexander Tuzhilin、Weimin Xiao、 Gu Xu（徐谷）、Philip S. Yu和 Mohammed Zaki.
我的學生們（不論已畢業或是在讀）檢查了許多算法的正確性並且作出了許多修正。他們包括Gao Cong（從高）、Minqing Hu、Nitin Jindal、Xin Li、Yiming Ma、Yanhong Zhai 和Kaidi Zhao。本書中一些章節是我在伊利諾伊斯大學芝加哥分校的研究生課程講義。我要感謝這些課程的學生幫我實現了一部分算法。他們提出的問題在某些情況下也幫助我修正算法。在這裡我不可能完全列出他們的名字，但我要特別感謝John Castano、Xiaowen Ding、Murthy Ganapathibhotla、Cynthia Kersey、Hari Prasad Divyakotti、Ravikanth Turlapati、Srikanth Tadikonda、Makio Tamura、Haisheng Wang和Chad Williams，他們指出講義中文本、舉例或算法的錯誤。來自德保羅大學的Michael Bombyk 也指出了不少筆誤。
與Springer出版社的員工一起工作是一段令人愉快的經歷。感謝編輯Ralf Gerstner在2005年初徵詢我對撰寫一本有關Web挖掘的書籍是否感興趣。從那以後，我們一直保持著愉快的合作經歷。我還要感謝校對Mike Nugent提高了本書內容的表達質量，以及製作編輯Michael Reinfarth引導我順利完成了本書的出版過程。還有兩位匿名評審也給出不少有見解的評論。伊利諾伊斯大學芝加哥分校計算機科學系對本項目提供了計算資源和工作環境的支持。
最後，我要感謝我的父母和兄弟姐妹，他們給予我一貫的支持和鼓勵。我將最深刻的感激給予我自己的家庭成員：Yue、Shelley和Kate。他們也在許多方面給予支持和幫助。儘管Shelley和Kate還年幼，但他們閱讀了本書的絕大部分，並且找出了不少筆誤。我的妻子將家裡一切事情打理得秩序井然，使我可以將充分的時間和精力用在這本書上。謹以此書獻給他們！
Bing Liu（劉兵）
目錄
第一部分 數據挖掘基礎
第1章 概述3
1.1 什麼是全球資訊網3
1.2 全球資訊網和網際網路的歷史簡述4
1.3 Web數據挖掘5
1.3.1 什麼是數據挖掘6
1.3.2 什麼是Web數據挖掘7
1.4 各章概要8
1.5 如何閱讀本書10
文獻評註10
第2章 關聯規則和序列模式12
2.1 關聯規則的基本概念12
2.2 Apriori算法14
2.2.1 頻繁項目集生成14
2.2.2 關聯規則生成17
2.3 關聯規則挖掘的數據格式19
2.4 多最小支持度的關聯規則挖掘20
2.4.1 擴展模型21
2.4.2 挖掘算法22
2.4.3 規則生成26
2.5 分類關聯規則挖掘27
2.5.1 問題描述27
2.5.2 挖掘算法28
2.5.3 多最小支持度分類關聯規則挖掘31
2.6 序列模式的基本概念31
2.7 基於GSP挖掘序列模式32
2.7.1 GSP算法33
2.7.2 多最小支持度挖掘34
2.8 基於PrefixSpan算法的序列模式挖掘37
2.8.1 PrefixSpan算法38
2.8.2 多最小支持度挖掘39
2.9 從序列模式中產生規則41
2.9.1 序列規則41
2.9.2 標籤序列規則41
2.9.3 分類序列規則42
文獻評註42
目錄目錄第3章 監督學習45
3.1 基本概念45
3.2 決策樹推理48
3.2.1 學習算法49
3.2.2 混雜度函式50
3.2.3 處理連續屬性53
3.2.4 其他一些問題54
3.3 評估分類器56
3.3.1 評估方法56
3.3.2查準率、查全率、F-score和平衡點(Breakeven Point)57
3.4 規則推理59
3.4.1 序列化覆蓋59
3.4.2 規則學習： Learn-One-Rule函式61
3.4.3 討論63
3.5 基於關聯規則的分類63
3.5.1 使用類關聯規則進行分類64
3.5.2 使用類關聯規則作為分類屬性66
3.5.3 使用古典的關聯規則分類66
3.6 樸素貝葉斯分類67
3.7 樸素貝葉斯文本分類70
3.7.1 機率框架70
3.7.2 樸素貝葉斯模型71
3.7.3 討論73
3.8 支持向量機73
3.8.1 線性支持向量機： 可分的情況74
3.8.2 線性支持向量機: 數據不可分的情況78
3.8.3 非線性支持向量機： 核方法80
3.9 k-近鄰學習82
3.10 分類器的集成83
3.10.1 Bagging83
3.10.2 Boosting84
文獻評註84
第4章 無監督學習87
4.1 基本概念87
4.2 k-均值聚類89
4.2.1 k-均值算法89
4.2.2 k-均值算法的硬碟版本91
4.2.3 優勢和劣勢92
4.3 聚類的表示95
4.3.1 聚類的一般表示方法95
4.3.2 任意形狀的聚類95
4.4 層次聚類96
4.4.1 單連結方法97
4.4.2 全連結方法98
4.4.3 平均連結方法98
4.4.4 優勢和劣勢98
4.5 距離函式99
4.5.1 數值的屬性(Numeric Attributes)99
4.5.2 布爾屬性和符號屬性(Binary and Nominal Attributes)99
4.5.3 文本文檔101
4.6 數據標準化101
4.7 混合屬性的處理103
4.8 採用哪種聚類算法104
4.9 聚類的評估104
4.10 發現數據區域和數據空洞106
文獻評註108
第5章 部分監督學習110
5.1 從已標註數據和無標註數據中學習110
5.1.1 使用樸素貝葉斯分類器的EM算法111
5.1.2 Co-Training114
5.1.3 自學習115
5.1.4 直推式支持向量機116
5.1.5 基於圖的方法117
5.1.6 討論119
5.2 從正例和無標註數據中學習119
5.2.1 PU學習的套用120
5.2.2 理論基礎121
5.2.3 建立分類器： 兩步方法122
5.2.4 建立分類器： 直接方法127
5.2.5 討論128
附錄： 樸素貝葉斯EM算法的推導129
文獻評註131第二部分 Web挖掘
第6章 信息檢索與Web搜尋135
6.1 信息檢索中的基本概念136
6.2 信息檢索模型138
6.2.1 布爾模型138
6.2.2 向量空間模型139
6.2.3 統計語言模型141
6.3 關聯性反饋142
6.4 評估標準143
6.5 文本和網頁的預處理147
6.5.1 停用詞移除147
6.5.2 詞幹提取147
6.5.3 其他文本預處理步驟148
6.5.4 網頁預處理步驟148
6.5.5 副本探測149
6.6 倒排索引及其壓縮150
6.6.1 倒排索引150
6.6.2 使用倒排索引搜尋151
6.6.3 索引的建立152
6.6.4 索引的壓縮153
6.7 隱式語義索引157
6.7.1 奇異值分解158
6.7.2 查詢和檢索159
6.7.3 實例160
6.7.4 討論163
6.8 Web搜尋163
6.9 元搜尋引擎和組合多種排序165
6.9.1 使用相似度分數的合併166
6.9.2 使用排名位置的合併166
6.10 網路作弊168
6.10.1 內容作弊169
6.10.2 連結作弊169
6.10.3 隱藏技術170
6.10.4 抵製作弊171
文獻評註172
第7章 連結分析174
7.1 社會關係網分析175
7.1.1 中心性175
7.1.2 權威177
7.2 同引分析和引文耦合178
7.2.1 同引分析178
7.2.2 引文耦合179
7.3 PageRank179
7.3.1 PageRank算法180
7.3.2 PageRank算法的優點和缺點185
7.3.3 Timed PageRank185
7.4 HITS186
7.4.1 HITS算法187
7.4.2 尋找其他的特徵向量189
7.4.3 同引分析和引文耦合的關係189
7.4.4 HITS算法的優點和缺點189
7.5 社區發現191
7.5.1 問題定義191
7.5.2 二分核心社區192
7.5.3 最大流社區193
7.5.4 基於中介性的電子郵件社區195
7.5.5 命名實體的重疊社區196
文獻評註197
第8章 Web爬取199
8.1 一個簡單爬蟲算法199
8.1.1 寬度優先爬蟲201
8.1.2 帶偏好的爬蟲201
8.2 實現議題202
8.2.1 網頁獲取202
8.2.2 網頁解析202
8.2.3 刪除無用詞並提取詞幹204
8.2.4 連結提取和規範化204
8.2.5 爬蟲陷阱206
8.2.6 網頁庫206
8.2.7 並發性207
8.3 通用爬蟲208
8.3.1 可擴展性208
8.3.2 覆蓋度、新鮮度和重要度209
8.4 限定爬蟲210
8.5 主題爬蟲212
8.5.1 主題本地性和線索213
8.5.2 最優優先變種217
8.5.3 自適應219
8.6 評價標準223
8.7 爬蟲道德和衝突226
8.8 最新進展228
文獻評註230
第9章 結構化數據抽取：包裝器生成231
9.1 預備知識231
9.1.1 兩種富含數據的網頁232
9.1.2 數據模型233
9.1.3 數據實例的HTML標記編碼235
9.2 包裝器歸納236
9.2.1 從一張網頁抽取237
9.2.2 學習抽取規則238
9.2.3 識別提供信息的樣例242
9.2.4 包裝器維護242
9.3 基於實例的包裝器學習243
9.4 自動包裝器生成中的一些問題245
9.4.1 兩個抽取問題246
9.4.2 作為正則表達式的模式246
9.5 字元串匹配和樹匹配247
9.5.1 字元串編輯距離247
9.5.2 樹匹配249
9.6 多重對齊252
9.6.1 中星方法252
9.6.2 部分樹對齊253
9.7 構建DOM樹257
9.8 基於列表頁的抽取： 平坦數據記錄258
9.8.1 有關數據記錄的兩個觀察結果258
9.8.2 挖掘數據區域259
9.8.3 從數據區域中識別數據記錄263
9.8.4 數據項對齊與抽取263
9.8.5 利用視覺信息264
9.8.6 一些其他技術264
9.9 基於列表頁的抽取： 嵌套數據記錄265
9.10 基於多張網頁的抽取269
9.10.1 採用前幾節中的技術270
9.10.2 RoadRunner算法270
9.11 一些其他問題271
9.11.1 從其他網頁中抽取271
9.11.2 析取還是可選272
9.11.3 一個集合類型還是一個元組類型273
9.11.4 標註與整合273
9.11.5 領域相關的抽取273
9.12 討論274
文獻評註274
第10章 信息集成276
10.1 什麼是樣式表匹配277
10.2 樣式表匹配的預處理工作278
10.3 樣式表層次的匹配279
10.3.1 基於語言學的算法279
10.3.2 基於樣式表中限制的算法280
10.4 基於領域和實例層次的匹配280
10.5 不同相似度的聯合282
10.6 1:?m?匹配283
10.7 其他問題284
10.7.1 重用以前的匹配結果284
10.7.2 大量樣式表的匹配285
10.7.3 樣式表匹配的結果285
10.7.4 用戶互動285
10.8 Web搜尋界面的集成285
10.8.1 基於聚類的算法287
10.8.2 基於互關係的方法289
10.8.3 基於實例的方法290
10.9 構建一個全局的搜尋界面292
10.9.1 結構上的正確性和合併算法293
10.9.2 辭彙的正確性294
10.9.3 實例的正確性295
文獻評註295
第11章 觀點挖掘296
11.1 意見分類297
11.1.1 基於意見短語的分類297
11.1.2 採用文本分類方法進行意見分類299
11.1.3 基於評分函式進行分類299
11.2 基於特徵的觀點挖掘和摘要300
11.2.1 問題定義301
11.2.2 對象特徵抽取305
11.2.3 格式1中正面和負面評價部分的特徵抽取306
11.2.4 符合格式2和3的評審上的特徵抽取308
11.2.5 觀點傾向分類309
11.3 比較性句子和比較關係挖掘310
11.3.1 問題定義311
11.3.2 等級比較性語句的識別312
11.3.3 比較關係的抽取314
11.4 觀點搜尋315
11.5 觀點欺詐316
11.5.1 觀點欺詐的目標和行為317
11.5.2 欺詐和欺詐者的種類317
11.5.3 隱藏技巧318
11.5.4 欺詐檢測318
文獻評註320
第12章 Web使用挖掘322
12.1 數據收集和預處理323
12.1.1 數據的來源和類型323
12.1.2 Web使用記錄數據預處理的關鍵元素326
12.2 Web使用記錄挖掘的數據建模331
12.3 Web用法模式的發現和分析334
12.3.1 會話和訪問者分析334
12.3.2 聚類分析和訪問者分割334
12.3.3 關聯及相關度分析337
12.3.4 序列和導航模式分析340
12.3.5 基於Web用戶事務的分類和預測342
12.4 討論和展望343
文獻評註344
參考文獻345
