資訊檢索導論

　　資訊檢索（Information Retrieval, 簡寫IR）係指搜尋資訊的科學，如在檔案中搜尋資訊、搜尋文件本身、搜尋描述檔案中資料的資料，或是在資料庫中進行搜尋，無論是何種獨立資料庫或是普遍被使用之網路資料庫皆可稱之為資訊檢索，IR已成為一個種不斷發展並和其他領域、技術不斷融合的學科。

　　特別補充近年來受到廣泛關注的新內容，比如：基於語言建模的資訊檢索模型、基於機器學習的排序方法、檢索結果的Snippet生成、聚類標籤生成、XML檢索、搜索廣告、網頁作弊等等。此外，書中每章尾的「參考文獻及補充讀物」一節也給出了相關技術的最新進展。本書與傳統教材的另一個明顯不同之處，在於加入了文本分類/聚類技術的介紹，事實上這些技術已經成為當代資訊檢索不可分割的一部分。

　　同時，本書在深度上超過了大部分傳統教材。介紹資訊檢索技術的同時，亦深入介紹了其背後所依賴的原理。本書不僅資訊檢索領域的初階教科書，還能滿足對該領域進行深入研究的讀者。

本書特色

　　本書適合攻讀電腦專業的大學生或研究生、高年級資訊相關科系學生，及法律、醫學訊學、統計、語言學及其他工程學科背景的學生之教科書。本書主要的寫作原則可以提供一個學期的資訊檢索研究生課程，並儘量涵蓋資訊檢索的學科重點。

總校閱簡介

柯皓仁

　　國立交通大學資訊科學研究所博士，現為國立臺灣師範大學圖書資訊學研究所教授。研究領域及學術專長為數位與網路技術、數位典藏、資料探勘。 

譯者簡介

王斌

　　國家科學院計算技術研究所，副研究員。發表學術論文100餘篇。擔任CIKM、AIRS、CCIR、SEWM等國際國內會議的程式委員會委員，同時是ACM和IEEE會員及《中文資訊學報》編委。

序

第1章　布林檢索 1
1.1　一個資訊檢索的例子 2
1.2　構建倒排索引的初體驗 5
1.3　布林查詢的處理 8
1.4　對基本布林操作的擴展及有序檢索 11
1.5　參考文獻及補充讀物 13

第2章　詞項詞典及倒排記錄表 14
2.1　文檔分析及編碼轉換 14
2.1.1　字元序列的生成 14
2.1.2　文檔單位的選擇 16
2.2　詞項集合的確定 16
2.2.1　詞條化 16
2.2.2　去除停用詞 19
2.2.3　詞項歸一化 20
2.2.4　詞幹還原和詞形歸併 23
2.3　基於跳表的倒排記錄表快速合併演算法 26
2.4　含位置資訊的倒排記錄表及短語查詢 28
2.4.1　二元詞索引 28
2.4.2　位置資訊索引 29
2.4.3　混合索引機制 31
2.5　參考文獻及補充讀物 32

第3章　詞典及容錯式檢索 34
3.1　詞典搜索的資料結構 34
3.2　通配符查詢 36
3.2.1　一般的通配符查詢 37
3.2.2　支援通配符查詢的k-gram索引 38
3.3　拼寫校正 39
3.3.1　拼寫校正的實現 39
3.3.2　拼寫校正的方法 40
3.3.3　編輯距離 40
3.3.4　拼寫校正中的 k-gram索引 42
3.3.5　上下文敏感的拼寫校正 43
3.4　基於發音的校正技術 44
3.5　參考文獻及補充讀物 45

第4章　索引構建 46
4.1　硬體基礎 46
4.2　基於塊的排序索引方法 47
4.3　記憶體式單遍掃描索引構建方法 50
4.4　分散式索引構建方法 51
4.5　動態索引構建方法 54
4.6　其他索引類型 56
4.7　參考文獻及補充讀物 57

第5章　索引壓縮 59
5.1　資訊檢索中詞項的統計特性 59
5.1.1　Heaps定律：詞項數目的估計 61
5.1.2　Zipf定律：對詞項的分佈建模 62
5.2　詞典壓縮 63
5.2.1　將詞典看成單一字串的壓縮方法 63
5.2.2　按塊存儲 64
5.3　倒排記錄表的壓縮 66
5.3.1　可變位元組碼 67
5.3.2　γ編碼 68
5.4　參考文獻及補充讀物 74

第6章　文檔評分、詞項權重計算及向量空間模型 76
6.1　參數化索引及域索引 76
6.1.1　域加權評分 78
6.1.2　權重學習 79
6.1.3　最優權重g 的計算 80
6.2　詞項頻率及權重計算 81
6.2.1　逆文檔頻率 81
6.2.2　tf-idf 權重計算 82
6.3　向量空間模型 83
6.3.1　內積 83
6.3.2　查詢向量 86
6.3.3　向量相似度計算 87
6.4　其他tf-idf 權重計算方法 88
6.4.1　tf的亞線性尺度變換方法 88
6.4.2　基於最大值的tf歸一化 88
6.4.3　文檔權重和查詢權重機制 89
6.4.4　文檔長度的回轉歸一化 89
6.5　參考文獻及補充讀物 92

第7章　一個完整搜索系統中的評分計算 93
7.1　快速評分及排序 93
7.1.1　非精確返回前K篇文檔的方法 94
7.1.2　索引去除技術 94
7.1.3　勝者表 95
7.1.4　靜態得分和排序 95
7.1.5　影響度排序 96
7.1.6　簇剪枝方法 97
7.2　資訊檢索系統的組成 98
7.2.1　層次型索引 98
7.2.2　查詢詞項的鄰近性 98
7.2.3　查詢分析及文檔評分函數的設計 99
7.2.4　搜索系統的組成 100
7.3　向量空間模型對各種查詢操作的支持 101
7.3.1　布林查詢 101
7.3.2　通配符查詢 102
7.3.3　短語查詢 102
7.4　參考文獻及補充讀物 102

第8章　資訊檢索的評價 103
8.1　資訊檢索系統的評價 103
8.2　標準測試集 104
8.3　無序檢索結果集合的評價 105
8.4　有序檢索結果的評價方法 108
8.5　相關性判定 112
8.6　更廣的視角看評價：系統品質及用戶效用 115
8.6.1　系統相關問題 115
8.6.2　用戶效用 115
8.6.3　對已有系統的改進 116
8.7　結果片段 116
8.8　參考文獻及補充讀物 118

第9章　相關回饋及查詢擴展 120
9.1　相關回饋及偽相關回饋 120
9.1.1　Rocchio相關回饋演算法 122
9.1.2　基於概率的相關回饋方法 125
9.1.3　相關回饋的作用時機 125
9.1.4　Web上的相關回饋 126
9.1.5　相關回饋策略的評價 127
9.1.6　偽相關回饋 127
9.1.7　間接相關回饋 128
9.1.8　小結 128
9.2　查詢重構的全局方法 128
9.2.1　查詢重構的辭彙表工具 128
9.2.2　查詢擴展 129
9.2.3　同義詞詞典的自動構建 130
9.3　參考文獻及補充讀物 131

第10章　XML檢索 133
10.1　XML的基本概念 134
10.2　XML檢索中的挑戰性問題 137
10.3　基於向量空間模型的XML檢索 140
10.4　XML檢索的評價 144
10.5　XML檢索：以文本為中心與以資料為中心的對比 146
10.6　參考文獻及補充讀物 148

第11章　概率檢索模型 150
11.1　概率論基礎知識 150
11.2　概率排序原理 151
11.2.1　1/0風險的情況 151
11.2.2　基於檢索代價的概率排序原理 152
11.3　二值獨立模型 152
11.3.1　排序函數的推導 153
11.3.2　理論上的概率估計方法 155
11.3.3　實際中的概率估計方法 156
11.3.4　基於概率的相關回饋方法 157
11.4　概率模型的相關評論及擴展 158
11.4.1　概率模型的評論 158
11.4.2　詞項之間的樹型依賴 159
11.4.3　Okapi BM25: 一個非二值的模型 160
11.4.4　IR中的貝葉斯網路方法 161
11.5　參考文獻及補充讀物 162

第12章　基於語言建模的資訊檢索模型 163
12.1　語言模型 163
12.1.1　有窮自動機和語言模型 163
12.1.2　語言模型的種類 165
12.1.3　詞的多項式分佈 166
12.2　查詢似然模型 167
12.2.1　IR中的查詢似然模型 167
12.2.2　查詢生成概率的估計 167
12.2.3　Ponte和Croft進行的實驗 169
12.3　語言建模的方法與其他檢索方法的比較 171
12.4　擴展的LM方法 172
12.5　參考文獻及補充讀物 173

第13章　文本分類及樸素貝葉斯方法 175
13.1　文本分類問題 177
13.2　樸素貝葉斯文本分類 178
13.3　貝努利模型 182
13.4　NB的性質 183
13.5　特徵選擇 188
13.5.1　互信息 188
13.5.2　 統計量 191
13.5.3　基於頻率的特徵選擇方法 192
13.5.4　多類問題的特徵選擇方法 193
13.5.5　不同特徵選擇方法的比較 193
13.6　文本分類的評價 194
13.7　參考文獻及補充讀物 199

第14章　基於向量空間模型的文本分類 200
14.1　文檔表示及向量空間中的關聯度計算 201
14.2　Rocchio分類方法 202
14.3　k近鄰分類器 205
14.4　線性及非線性分類器 209
14.5　多類問題的分類 212
14.6　偏差—方差折中準則 214
14.7　參考文獻及補充讀物 219

第15章　支持向量機及文檔機器學習方法 221
15.1　二類線性可分條件下的支持向量機 221
15.2　支持向量機的擴展 226
15.2.1　軟間隔分類 226
15.2.2　多類情況下的支援向量機 228
15.2.3　非線性支援向量機 228
15.2.4　實驗結果 230
15.3　有關文本文檔分類的考慮 231
15.3.1　分類器類型的選擇 231
15.3.2　分類器效果的提高 233
15.4　ad hoc檢索中的機器學習方法 236
15.4.1　基於機器學習評分的簡單例子 236
15.4.2　基於機器學習的檢索結果排序 238
15.5　參考文獻及補充讀物 239

第16章　扁平聚類 241
16.1　資訊檢索中的聚類應用 242
16.2　問題描述 244
16.3　聚類演算法的評價 246
16.4　K-均值演算法 248
16.5　基於模型的聚類 254
16.6　參考文獻及補充讀物 258

第17章　層次聚類 260
17.1　凝聚式層次聚類 260
17.2　單連接及全連接聚類演算法 263
17.3　組平均凝聚式聚類 268
17.4　質心聚類 269
17.5　層次凝聚式聚類的最優性 270
17.6　分裂式聚類 272
17.7　簇標籤生成 273
17.8　實施中的注意事項 274
17.9　參考文獻及補充讀物 275

第18章　矩陣分解及隱性語義索引 277
18.1　線性代數基礎 277
18.2　詞項—文檔矩陣及SVD 280
18.3　低秩逼近 282
18.4　LSI 284
18.5　參考文獻及補充讀物 287

第19章　Web搜索基礎 289
19.1　背景和歷史 289
19.2　Web的特性 290
19.2.1　Web圖 291
19.2.2　作弊網頁 293
19.3　廣告經濟模型 294
19.4　搜索用戶體驗 296
19.5　索引規模及其估計 297
19.6　近似重複及shingling 300
19.7　參考文獻及補充讀物 303

第20章　Web採集及索引 304
20.1　概述 304
20.1.1　採集器必須提供的功能特點 304
20.1.2　採集器應該提供的功能特點 304
20.2　採集 305
20.2.1　採集器架構 305
20.2.2　DNS解析 308
20.2.3　待採集URL池 309
20.3　分散式索引 311
20.4　連接伺服器 312
20.5　參考文獻及補充讀物 314

第21章　鏈結分析 316
21.1　Web圖T 316
21.2　PageRankT 318
21.2.1　馬爾科夫鏈 318
21.2.2　PageRank的計算 320
21.2.3　T面向主題的PageRankT 322
21.3　Hub網頁及Authority網頁T 325
21.4　參考文獻及補充讀物T 329

參考文獻 331
索引 356