第一講 搜索

IR（信息檢索是什么樣的學(xué)科）

實(shí)質(zhì)上是融合了文本及多媒體檢索、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和自然語言處理的綜合學(xué)科

(資料圖片僅供參考)

為什么要進(jìn)行信息檢索？信息過載

搜索

搜索的過程

從大規(guī)模非結(jié)構(gòu)化數(shù)據(jù)(通常是文本)的集合(通常保存在計(jì)算機(jī)上)中找出滿足用戶信息需求的資料(通常是文檔)的過程

信息檢索的本質(zhì)

確定文檔和查詢之間的相關(guān)度是IR的核心問題

IR作為一門學(xué)科，是研究信息的獲取(acquisition)、表示(representation)、存儲(chǔ)(storage)、組織(organization)和訪問(access)的一門學(xué)問

信息檢索本質(zhì)：給定一個(gè)查詢Q，從文檔集合C中，計(jì)算每篇文檔D與Q的相關(guān)度，并排序(Ranking)

什么是相關(guān)度

相關(guān)度是一個(gè)查詢和文檔相關(guān)的程度，形式上說，信息檢索中的相關(guān)度是一個(gè)**函數(shù)*f*，**輸入是查詢Q、文檔D和文檔集合C，返回的是一個(gè)實(shí)數(shù)值 R, R= f(Q,D,C)

相關(guān)度(relevance)不同于相似度(Similarity):

相關(guān)度通常只有相對(duì)意義

(1)相關(guān)取決于用戶的判斷，是一個(gè)主觀概念

(2)不同用戶做出的判斷很難保證一致

(3)即使是同一用戶在不同時(shí)期、不同環(huán)境下做出的判斷也不盡相同

定義“相關(guān)性”的兩個(gè)角度：(了解)

系統(tǒng)角度：系統(tǒng)輸出結(jié)果，用戶是信息的接受者。

用戶角度:觀察用戶對(duì)檢索結(jié)果的反應(yīng)，是系統(tǒng)輸出向用戶需求的投射

現(xiàn)代信息檢索研究中仍然主要采用系統(tǒng)角度定義的主題相關(guān)性概念，當(dāng)然也強(qiáng)調(diào)考慮用戶的認(rèn)知因素

信息檢索模型

描述信息檢索中的文檔、查詢和它們之間關(guān)系(匹配函數(shù))的數(shù)學(xué)模型

信息檢索主要技術(shù)

（1）文本分析（NLP）

（2）建立索引

（3）查詢，包括查詢分析（NLP），相關(guān)度計(jì)算(和信息檢索模型相關(guān))

（4）排序（實(shí)驗(yàn)室評(píng)價(jià)）

搜索引擎

工作原理

（1） 爬行和抓取

（2） 文本分析

（3）建立索引（可能會(huì)考的知識(shí)點(diǎn)：蜘蛛抓取的頁面文件分解、分析，并以巨大表格的形式存入數(shù)據(jù)庫，這個(gè)過程即是索引（index).搜索引擎的核心數(shù)據(jù)結(jié)構(gòu)為倒排文件（也稱倒排索引））

（4）搜索詞處理 （5）排序 （6）用戶反饋

搜索引擎評(píng)價(jià)

（1） 覆蓋面 （2）更新周期 （3）響應(yīng)速度 （4）排序結(jié)果是否滿足用戶的查詢要求

第二講 網(wǎng)絡(luò)爬蟲技術(shù)

爬蟲定義

一種自動(dòng)獲取網(wǎng)頁內(nèi)容的程序，從一個(gè)或若干初始網(wǎng)頁的**URL開始，獲取并解析它們，提取它們指向的URL，將提取的url放在隊(duì)列中，獲取隊(duì)列中的每個(gè)URL并重復(fù)此過程，直到滿足系統(tǒng)的一定停止條件**

通俗的講，也就是通過HTML源碼解析來獲得想要的內(nèi)容

爬蟲必須具有的功能

4.1 禮貌性: Web服務(wù)器有顯式或隱式的策略控制爬蟲的訪問

只爬允許爬的內(nèi)容、尊重 robots.txt

4.2 魯棒性: 能從采集器陷阱中跳出，能處理Web服務(wù)器的其他惡意行為

4.3 性能和效率:充分利用不同的系統(tǒng)資源，包括處理器、存儲(chǔ)器和網(wǎng)絡(luò)帶寬

優(yōu)先抓取“有用的網(wǎng)頁”

4.4 分布式: 可以在多臺(tái)機(jī)器上分布式運(yùn)行

?分布式帶來的問題

–哈希表判重

?解決方法：

–A、明確每臺(tái)下載服務(wù)器的分工，即一看到某個(gè)URL就知道交給哪臺(tái)服務(wù)器去執(zhí)行

–B、批量處理，減少通信的次數(shù)

可擴(kuò)展性: 添加更多機(jī)器后采集率應(yīng)該提高

4.5 新鮮度: 對(duì)原來抓取的網(wǎng)頁進(jìn)行更新

4.6功能可擴(kuò)展性：支持多方面的功能擴(kuò)展，例如處理新的數(shù)據(jù)格式、新的抓取協(xié)議等

爬取框架

3、搜索策略：深度優(yōu)先, 廣度優(yōu)先

實(shí)際應(yīng)用的網(wǎng)絡(luò)爬蟲不是對(duì)網(wǎng)頁次序的簡單BFS或者BFS，而是一個(gè)相對(duì)復(fù)雜的下載優(yōu)先級(jí)排序的方法，管理這個(gè)系統(tǒng)的叫做“調(diào)度系統(tǒng)”(Scheduler)，會(huì)有一個(gè)Priority Queue。BFS成分更加多一些。

4、URL 判重

建立一個(gè)散列，其中存放訪問過每一個(gè)網(wǎng)址

在其中存放網(wǎng)址經(jīng)過散列函數(shù)計(jì)算出的對(duì)應(yīng)的固定長度的散列值

在平均情況下**O(1)**的時(shí)間內(nèi)查找和更新占用O(n)空間的網(wǎng)址列表

利用哈希法，URL經(jīng)過哈希函數(shù)得到哈希碼，判斷是否已經(jīng)在散列中來判斷是否爬取過

爬蟲分類

?5.1基于整個(gè)Web的信息采集(Universal Web Crawling)

?傳統(tǒng)的采集方式

–作為門戶搜索引擎和大型的Web服務(wù)提供商的數(shù)據(jù)收集部分

–是指從一些種子URL擴(kuò)充到整個(gè)Web的信息采集

?5.2 增量式Web信息采集 (Incremental Web Crawling )

?5.3 基于主題的Web信息采集(Focused Web Crawling )

?5.4 基于用戶個(gè)性化的Web信息采集(Customized Web Crawling )

?基于元搜索的信息采集(Metasearch Web Crawling)

常見的開源爬蟲

Nutch Heritrix

?包括全文搜索和Web爬蟲。

–包括爬蟲crawler和查詢searcher。

?Crawler主要用于從網(wǎng)絡(luò)上抓取網(wǎng)頁并為這些網(wǎng)頁建立索引。

Pandas模塊

lxml模塊

?lxml是一個(gè)HTML/XML的解析庫

?主要功能是如何解析和提取HTML/XML數(shù)據(jù)

第三講 網(wǎng)頁分析技術(shù)

網(wǎng)頁解析方法

–一種是將文檔看作字符流;

?正則表達(dá)式

–一種是將文檔看作樹結(jié)構(gòu)。

?基于DOM

正則表達(dá)式

1、正則表達(dá)式的定義

正則表達(dá)式是對(duì)**字符串操作的一種邏輯公式，就是用事先定義好的一些特定字符、及這些特定字符的組合，組成一個(gè)“規(guī)則字符串”，這個(gè)“規(guī)則字符串”用來表達(dá)對(duì)字符串的一種過濾邏輯。**

2、基于正則表達(dá)式的信息提取的步驟

（1）在獲取數(shù)據(jù)前應(yīng)盡量去除無用部分（2）提取網(wǎng)頁內(nèi)的鏈接（3）提取網(wǎng)頁標(biāo)題（4）提取網(wǎng)頁內(nèi)的文本

3、正則表達(dá)式的工具有哪些

Java java.util.regex包 Python的 re模塊

4、正則表達(dá)式匹配特點(diǎn)是什么

（1）正則表達(dá)式匹配速度快，

（2）但表達(dá)能力較弱，只具有正規(guī)文法的表示能力。

（3）在對(duì)網(wǎng)頁內(nèi)容的信噪比要求不高的情況下可以使用基于正則表達(dá)式匹配的爬取程序

（4）受網(wǎng)頁噪音影響較大

DOM

5、什么叫做DOM

文檔對(duì)象模型（document object model，DOM）,DOM將一個(gè)XML文檔轉(zhuǎn)換成一個(gè)對(duì)象集合，然后可以任意處理該對(duì)象模型。

DOM將HTML視為樹狀結(jié)構(gòu)的元素，所有元素以及他們的文字和屬性可通過DOM樹來操作與訪問。

6、開源HTML解析器（能夠列出一兩種即可）

（1）JAVA：HTMLParser,jsoup

（2）C/C++：htmlcxx

（3）Python：Beautiful Soup

bs解析器

–使用自帶的html.parser解析，

?速度慢但通用

?soup = BeautifulSoup(html, “html.parser”)

–Html5lib

?不規(guī)范的html文本轉(zhuǎn)為規(guī)范的文本再進(jìn)行解析

用瀏覽器的方式解析文檔

–lxml

?python的一個(gè)解析庫，

?支持HTML和XML的解析，

?支持XPath解析方式，

?而且解析效率非常高

?lxml只會(huì)局部遍歷

兩種方法比較

正則表達(dá)式匹配

（1）正則表達(dá)式匹配速度快，但表達(dá)能力較弱，只具有正規(guī)文法的表示能力。

（2）在對(duì)網(wǎng)頁內(nèi)容的信噪比要求不高的情況下可以使用基于正則表達(dá)式匹配的爬取程序

HTML DOM樹

（1）提取HTML DOM樹提取在解析HTML時(shí)速度較慢，但其表達(dá)能力相當(dāng)于上下文無關(guān)文法。

（2）在網(wǎng)頁自動(dòng)分類等需要進(jìn)行網(wǎng)頁去噪處理的情況時(shí)使用基HTMLDOM樹的爬取程序

Python爬蟲

?工作過程

–把URL地址中指定的網(wǎng)絡(luò)資源從網(wǎng)絡(luò)流中讀取出來，保存到本地

–過濾

Re

bs4

Scrapy shell

交互終端，不啟動(dòng)爬蟲的情況下調(diào)試代碼

直接用來測試XPath或者CSS表達(dá)式，不用import響應(yīng)模塊

查看運(yùn)行的結(jié)果方便分析網(wǎng)頁，測試表達(dá)式是否獲取到了數(shù)據(jù)

python爬蟲框架 Scrapy

?快速、高層次的屏幕抓取和web抓取框架，

?用于抓取web站點(diǎn)并從頁面中提取結(jié)構(gòu)化的數(shù)據(jù)。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-2rmF6m42-1608430839949)(C:\Users\yandalao\AppData\Roaming\Typora\typora-user-images\image-20201216162520302.png)]

?爬蟲文件novel_spider.py

–分析需要提取的數(shù)據(jù)

?在parse方法中做數(shù)據(jù)的提取

?使用Xpath，從頁面的HTML Source里面選取要要抽取的數(shù)據(jù)

Xpath

?XML路徑語言（XML Path Language），它是一種用來確定XML文檔中某部分位置的語言

?XPath基于XML的樹狀結(jié)構(gòu)，提供在數(shù)據(jù)結(jié)構(gòu)樹中找尋節(jié)點(diǎn)的能力。

?xpath為scrapy中的解析方式

?xpath函數(shù)返回的為列表

–列表中存放的數(shù)據(jù)為Selector類型數(shù)據(jù)。

–解析到的內(nèi)容被封裝在Selector對(duì)象中，需要調(diào)用extract()函數(shù)將解析的內(nèi)容從Selector中取出

Scrapy項(xiàng)目

?制作 Scrapy 爬蟲 一共需要四步：

–新建項(xiàng)目 ：新建一個(gè)新的爬蟲項(xiàng)目

–明確目標(biāo) （編寫items.py）：明確你想要抓取的目標(biāo)

?items.py: 需要提取的數(shù)據(jù)結(jié)構(gòu)定義文件

–Item 定義結(jié)構(gòu)化數(shù)據(jù)字段，用來保存爬取到的數(shù)據(jù)，

?修改novel_spider.py :分析需要提取的數(shù)據(jù)

–制作爬蟲 （spiders/xxspider.py）：制作爬蟲開始爬取網(wǎng)頁

–存儲(chǔ)內(nèi)容 （pipelines.py）：設(shè)計(jì)管道存儲(chǔ)爬取內(nèi)容

yield

?只要是數(shù)據(jù)持久化存儲(chǔ)，parse方法必須有返回值（也就是return后的內(nèi)容）

–return items

?yield將函數(shù)轉(zhuǎn)換成生成器。我們可以理解成一種特殊的return方法。

?yield返回的是一個(gè)生成器，也是可迭代對(duì)象，有利于減小服務(wù)器資源

?生成器相當(dāng)于一種方法而不是具體的信息，占用內(nèi)存小。

爬取多個(gè)網(wǎng)頁

?start_urls

?起始爬取列表，可以是多個(gè)url

start_urls = (‘http://example.com/page1’, ‘http://example.com/page2’,)

爬取多層網(wǎng)頁

?解析函數(shù)的末尾，通過Request方法對(duì)下一個(gè)頁面手動(dòng)發(fā)起請(qǐng)求

?**先提取二級(jí)頁面url，**再對(duì)二級(jí)頁面發(fā)送請(qǐng)求

比較

?request和bs4

–頁面級(jí)爬蟲，功能庫

–并行性考慮不足，性能較差

–重點(diǎn)在于頁面下載

?Scrapy

–網(wǎng)站級(jí)爬蟲，框架

–并行性好，性能較高

–重點(diǎn)在于爬蟲結(jié)構(gòu)

元搜索引擎

?元搜索引擎又稱多搜索引擎

?通過一個(gè)統(tǒng)一的用戶界面幫助用戶在多個(gè)搜索引擎中選擇和利用合適的（甚至是同時(shí)利用若干個(gè)）搜索引擎來實(shí)現(xiàn)檢索操作，是對(duì)分布于網(wǎng)絡(luò)的多種檢索工具的全局控制機(jī)制

第四講 爬蟲與網(wǎng)站的博弈

本章知道每個(gè)方面的思路和所用工具就可

Robot 協(xié)議

?網(wǎng)站通過Robots協(xié)議告訴搜索引擎哪些頁面可以抓取，哪些頁面不能抓取。

User-agent

?向訪問網(wǎng)站提供訪問者信息

?UA字符串在每次瀏覽器 HTTP 請(qǐng)求時(shí)發(fā)送到服務(wù)器！

–反爬蟲

IP屏蔽

–爬蟲：對(duì)策

?連接代理服務(wù)器

–寫了個(gè)IP代理池

?多個(gè)IP并行

? 增大爬取時(shí)間間隔

用戶登陸

?分析登陸過程的方法

?4.1發(fā)送post請(qǐng)求

?4.2分析post過程中隱藏的變量名

?4.3分析Cookie

–http 請(qǐng)求帶著Cookie

?它記錄了你的用戶ID，密碼、瀏覽過的網(wǎng)頁、停留的時(shí)間等信息，用于用戶身份的辨別

?流程

–**第一個(gè)網(wǎng)頁通過GET（****POST)參數(shù)提交參數(shù)

?參數(shù)序列化成字符串

?和基礎(chǔ)****url拼接

?Urllib.request.urlopen**()**

–后臺(tái)接受請(qǐng)求，生成cookie，發(fā)給用戶

–用戶帶著Cookie繼續(xù)訪問其他網(wǎng)頁

?4.4攜帶Cookie訪問已登陸網(wǎng)站

?保存cookie到文件

?從文件中讀取cookie并訪問

?利用cookie模擬登錄

模擬瀏覽器進(jìn)行交互

selenium

?反爬蟲： 用戶登陸

–輸入用戶名–輸入口令

–點(diǎn)擊登陸按鈕

?Selenium用程序模擬整個(gè)操作過程

–忽略post或者get方式差異–不需要知道參數(shù)名字

處理Cookie：

?selenium獲取登錄****cookies，

–selenium有一個(gè) get_cookies() 函數(shù)可以幫我們獲取當(dāng)前網(wǎng)頁的cookie值

?保存cookies到文件

?并添加cookies自動(dòng)登錄

AJAX 動(dòng)態(tài)加載

?通過在后臺(tái)與服務(wù)器進(jìn)行少量數(shù)據(jù)交換，AJAX 可以使網(wǎng)頁實(shí)現(xiàn)異步更新。

在不重新加載整個(gè)網(wǎng)頁的情況下，對(duì)網(wǎng)頁的某部分進(jìn)行更新

驗(yàn)證碼

?圖像識(shí)別

–6.1獲取圖片

?分析網(wǎng)頁下載圖片

?屏幕截圖

–6.2圖片處理Pillow與PIL模塊

–6.3獲取圖片中文字內(nèi)容ocr

-6.4 圖片滑動(dòng)驗(yàn)證碼

第五講 詞項(xiàng)詞典

如何建立詞項(xiàng)詞典？

一、文檔解析(Parsing a document)

~~二、詞條化 (Tokenization)~~這倆不考

三、詞項(xiàng)歸一化 (Normalization)

四、詞干還原 (Stemming)

五、詞形歸并 (Lemmatization)

六、去掉停用詞 (Stop Words)

詞項(xiàng)歸一化

將文檔和查詢中的詞條“歸一化”成一致的形式（希望USA和U.S.A.之間也能形成匹配 ）

歸一化的結(jié)果： 在IR系統(tǒng)的詞項(xiàng)詞典中，形成多個(gè)近似詞項(xiàng)的一個(gè)等價(jià)類

策略：建立同義詞擴(kuò)展表

a) 為每個(gè)查詢維護(hù)一張包含多個(gè)詞的查詢擴(kuò)展詞表

b) 在建立索引建構(gòu)時(shí)就對(duì)詞進(jìn)行擴(kuò)展

詞干還原

a) 通常指去除單詞兩端詞綴的啟發(fā)式過程

b) 詞干還原能夠提高召回率，但是會(huì)降低準(zhǔn)確率

詞形歸并

a) 利用詞匯表和詞形分析來減少屈折變化的形式，將其轉(zhuǎn)變?yōu)榛拘问健?/p>

b) 詞形歸并可以減少詞項(xiàng)詞典中的詞項(xiàng)數(shù)量

詞干還原和詞形歸并的區(qū)別

a) 代表意義不同。

i. Stemming通常指很粗略的去除單詞兩端詞綴的啟發(fā)式過程。

ii. Lemmatization通常指利用詞匯表和詞形分析來去除屈折詞綴，從而返回詞的原形或詞典中的詞的過程。

b) 兩個(gè)過程的區(qū)別還在于：

i. 詞干還原在一般情況下會(huì)將多個(gè)派生相關(guān)詞合并在一起，

ii. 而詞形歸并通常只將同一詞元的不同屈折形式進(jìn)行合并。

c) 詞干還原和詞形歸并，都體現(xiàn)了不同語言之間的差異性

d)詞干還原過程可能僅返回 s，

e)而詞形歸并過程將返回see或者saw，

停用詞

a) 應(yīng)用太廣泛，區(qū)分度太低

b) 對(duì)這樣的詞搜索引擎無法保證能夠給出真正相關(guān)的搜索結(jié)果，難以幫助縮小搜索范圍，同時(shí)還會(huì)降低搜索的效率

消除停用詞的優(yōu)缺點(diǎn)

a) 優(yōu)點(diǎn)：

i. 停用詞消除可以減少term的個(gè)數(shù)

ii. 縮小搜索范圍，

iii. 提高搜索的效率

iv. 機(jī)器學(xué)習(xí)文本分類算法的文檔的預(yù)處理

b) 缺點(diǎn)：

i. 有時(shí)消除的停用詞對(duì)檢索是有意義的

如何確定停用詞

a) 查表法

b) 基于文檔頻率

第六講 中文分詞

分詞方法

a) 基于理解的分詞方法

NLP、語義分析、句法分析

b) 基于字符串匹配的分詞方法

查字典。

按照掃描方向：正向匹配和逆向匹配

按照掃描長度：最大匹配和最小匹配

a) 優(yōu)點(diǎn)：簡單，占用資源少，可自定義詞庫

i. 程序簡單易行，開發(fā)周期短；

ii. 僅需很少的語言資源（詞表），

iii. 不需要任何詞法、句法、語義資源。

iv. 可以自定義詞庫，增加新詞

b) 缺點(diǎn) ： 效果差

i. Out of Vocabulary

ii. 歧義消解能力差；

iii. 切分正確率不高，一般在95%左右。

c) 基于統(tǒng)計(jì)的分詞方法

用字與字相鄰出現(xiàn)的頻率來反應(yīng)成詞的可靠度，統(tǒng)計(jì)語料中相鄰出現(xiàn)的各個(gè)字的組合的頻度，當(dāng)組合頻度高于某一個(gè)臨界值時(shí)，我們便可認(rèn)為此字組可能構(gòu)成一個(gè)詞語。

基于統(tǒng)計(jì)的分詞方法的優(yōu)缺點(diǎn)：

a) 優(yōu)點(diǎn)：

i. 分詞準(zhǔn)確度高；

ii. 能夠平衡地看待詞表詞和未登錄詞的識(shí)別問題。

b) 缺點(diǎn)：

i. 局限性，會(huì)經(jīng)常抽出一些共現(xiàn)頻度高、但并不是詞的常用字組

ii. 對(duì)常用詞的識(shí)別精度差，時(shí)空開銷大

iii. 學(xué)習(xí)算法的復(fù)雜度往往較高，計(jì)算代價(jià)較大，依賴手工定義的特征工程

基于HMM的中文分詞方法

HMM作用

用來描述一個(gè)含有隱含未知參數(shù)的馬爾可夫過程。

隱含狀態(tài)之間存在轉(zhuǎn)換概率；隱含狀態(tài)和可見狀態(tài)之間存在發(fā)射概率

HMM模型是一個(gè)五元組:

StatusSet: 狀態(tài)值集合

ObservedSet: 觀察值集合

TransProbMatrix: 轉(zhuǎn)移概率矩陣 A

EmitProbMatrix: 發(fā)射概率矩陣 B

–在某一狀態(tài)下對(duì)應(yīng)到某字的概率–P(Observed[i]|Status[j])?基于觀察值只取決于當(dāng)前狀態(tài)值這一假設(shè)?其實(shí)也是一個(gè)條件概率

InitStatus: 初始狀態(tài)分布

–句子的第一個(gè)字屬于{B,E,M,S}這四種狀態(tài)的概率

?HMM三要素[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-ZlhDCqDG-1608430839951)(image\image-20201216190517905.png)]

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-BROKijaw-1608430839953)(image\image-20201216190525015.png)]

HMM模型可以用來解決三種問題

a) 模型參數(shù)學(xué)習(xí)問題

b) 預(yù)測問題

c) 評(píng)估觀察序列概率

HMM分詞

預(yù)測問題，也叫解碼問題

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-NGSEDXN9-1608430839955)(image\image-20201216190642734.png)]

Viterbi 算法

如何分詞：將句子中的詞看成有可能四個(gè)狀態(tài)BMES，最后求出最有可能的狀態(tài)序列（根據(jù)路徑）。就分詞成功

一種動(dòng)態(tài)規(guī)劃算法，它用于尋找最有可能產(chǎn)生 觀測事件 序列的維特比路徑——隱含狀態(tài)序列

?二維數(shù)組 weight[4] [7]

–4是狀態(tài)數(shù)(0:B,1:E,2:M,3:S)，

–7是輸入句子的字?jǐn)?shù)。

–P(Observed[i]|Status[j])

?比如 weight[0] [2] 代表 狀態(tài)B的條件下，出現(xiàn)‘市’這個(gè)字的可能性。

?二維數(shù)組 path[4] [15]

–path[0] [2] 代表 weight[0] [2]取到最大時(shí)，前一個(gè)字的狀態(tài)，

?比如 path[0] [2] = 1, 則代表 weight[0] [2]取到最大時(shí)，前一個(gè)字(也就是明)的狀態(tài)是E。

第七講 布爾模型與倒排索引

1、什么是信息檢索模型

信息檢索模型（IR model），依照用戶查詢，對(duì)文檔集合進(jìn)行相關(guān)排序的一組前提假設(shè)和算法。IR模型可形式地表示為一個(gè)四元組< D, Q, F, R(qi,dj) >

D是一個(gè)文檔集合，Q是一個(gè)查詢集合，R(qi,dj) 是一個(gè)排序函數(shù)，它給查詢qi和文檔 dj 之間的相關(guān)度賦予一個(gè)排序值，F(xiàn)是一個(gè)框架,用以構(gòu)建文檔,查詢以及它們之間關(guān)系的模型

2、基于內(nèi)容的信息檢索模型有哪些？

? 集合論模型：布爾模型、模糊集合模型、擴(kuò)展布爾模型

? 代數(shù)模型： 向量空間模型、廣義向量空間模型、潛在語義標(biāo)引模型、神經(jīng)網(wǎng)絡(luò)模型

? 概率模型： 經(jīng)典概率論模型、推理網(wǎng)絡(luò)模型、置信（信念）網(wǎng)絡(luò)模型

? 深度學(xué)習(xí)模型

3、布爾模型是什么

一種簡單的檢索模型，建立在經(jīng)典的集合論和布爾代數(shù)的基礎(chǔ)上

遵循兩條基本規(guī)則:

（1）每個(gè)索引詞在一篇文檔中只有兩種狀態(tài)：出現(xiàn)或不出現(xiàn)，對(duì)應(yīng)權(quán)值為 0或1。

（2）每篇文檔：索引詞（0或1）的集合

進(jìn)行查詢的時(shí)候，用布爾表達(dá)式進(jìn)行匹配，計(jì)算二值的相關(guān)度。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-Py4ldaW5-1608430839958)(image\image-20201217120733627.png)]

4、什么是bag of words 模型

在信息檢索中，Bag of words model假定

（1）對(duì)于一個(gè)文本，忽略其詞序和語法，句法，將其僅僅看做是一個(gè)詞集合，或者說是詞的一個(gè)組合，

（2）文本中每個(gè)詞的出現(xiàn)都是獨(dú)立的，不依賴于其他詞是否出現(xiàn)，在任意一個(gè)位置選擇一個(gè)詞匯都不受前面句子的影響而獨(dú)立選擇的。

5、搜索引擎的核心數(shù)據(jù)結(jié)構(gòu)為倒排文件（Inverted Files）（也叫倒排索引）

6、什么是倒排索引

有詞項(xiàng)和倒排記錄組成，**詞項(xiàng)詞典：**對(duì)于每一個(gè)詞項(xiàng)，存儲(chǔ)所有包含這個(gè)詞項(xiàng)的文檔的一個(gè)列表。**倒排記錄表：**一個(gè)文檔用一個(gè)序列號(hào)docID來表示。

?建立索引的步驟：

–詞條序列Token Sequence

?(修改過的詞條，文檔ID)對(duì) 序列

–排序

?先按照詞條排序，

?再按照docID排序

–構(gòu)建詞典和倒排表

?同一篇文檔中多次出現(xiàn)的詞被合并

?分割成詞典和倒排表

9、布爾檢索模型的特點(diǎn)是什么

優(yōu)點(diǎn)：（1）查詢簡單，因此容易理解（下面的具體說明理解即可）

? 布爾模型也許是IR系統(tǒng)中的最簡單的模型

? 是近30年來最主要的商業(yè)搜索工具

? 當(dāng)前使用的很多系統(tǒng)依然是使用的布爾模型

? 電子郵件，圖書館分類系統(tǒng)，mac osx的spotlight

（2）通過使用復(fù)雜的布爾表達(dá)式，可方便地控制查詢結(jié)果

? 同義關(guān)系 電腦 OR 計(jì)算機(jī)

? 詞組 數(shù)據(jù) AND 挖掘

缺點(diǎn) （1）準(zhǔn)確匹配，信息需求的能力表達(dá)不足。不能輸出部分匹配的情況

（2）無權(quán)重設(shè)計(jì) 無法排序，

（3）用戶必須會(huì)用布爾表達(dá)式提問，一般而言，檢出的文檔或者太多或者太少。

（4） 很難進(jìn)行自動(dòng)的相關(guān)反饋

第八講 向量空間模型

排序檢索

系統(tǒng)根據(jù)文檔與query的相關(guān)性排序返回文檔集合中的文檔；有布爾查詢和自由文本查詢兩種方式

Jaccard 系數(shù)

? 一種常用的衡量兩個(gè)集合A,B重疊度的方法

? Jaccard(A,B) = |A ∩ B| / |A ∪ B|（回答這個(gè)公式即可）

? Jaccard(A,A) = 1

? Jaccard(A,B) = 0 if A ∩ B = 0

? 集合A和B不需要具有同樣的規(guī)模

–沒有考慮

?文檔長短

?詞項(xiàng)頻率(詞項(xiàng)在文檔中出現(xiàn)的次數(shù))

?罕見詞比高頻詞的信息量更大，更加具有區(qū)分度

詞項(xiàng)頻率

詞項(xiàng)t在文檔d中出現(xiàn)的次數(shù)，記為tft,d）

一種替代原始tf的方法: 對(duì)數(shù)詞頻原始的詞頻tf以10為底取對(duì)數(shù)再加一

什么是idf：是逆文檔頻率，idft= log10(N/dft)，df是文檔頻率，指出現(xiàn)詞項(xiàng)的文檔數(shù)目

文檔頻率 (Document frequency，df)

? 文檔頻率:出現(xiàn)詞項(xiàng)的文檔數(shù)目

? dft文檔集合中包含t的文檔數(shù)目

– 與詞項(xiàng)t包含的信息量成反比

– dft<= N(N是文檔的總數(shù))

idf (inverse document frequency)逆文檔頻率

? idft= log10(N/dft)

– idft是反映詞項(xiàng)t的信息量的一個(gè)指標(biāo)

– 用log (N/dft) 代替N/dft來抑制idf的作用

tf-idf是什么

是信息檢索中最著名的權(quán)重計(jì)算方法，表示t對(duì)于文檔d的重要程度，詞項(xiàng)t的tf-idf 由它的tf和idf組合而成 wt,d=(1+log tft,d) × log10(N/dft)

（理解一下和重要程度是否符合：tf-idf值隨著詞項(xiàng)在單個(gè)文檔中出現(xiàn)次數(shù)(tf)增加而增大，tf-idf值隨著詞項(xiàng)在文檔集中數(shù)目(df)增加而減小）

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-s9lj0KLn-1608430839959)(image\image-20201217145033660.png)]

向量空間模型

是一個(gè)**|V|維實(shí)向量空間**（V是詞項(xiàng)集合，|V|表示詞項(xiàng)個(gè)數(shù)），空間的每一維都對(duì)應(yīng)一個(gè)詞項(xiàng)，每篇文檔表示成一個(gè)基于tf-idf權(quán)重的實(shí)值向量，向量的維度是詞項(xiàng)的個(gè)數(shù)，文檔是空間中的點(diǎn)或者向量，這就是向量空間模型

向量相似度計(jì)算

余玄相似度：（認(rèn)為cos(di,q) > cos(dj,q)，夾角更小，所以di比dj與q更相關(guān)）

R(d,q) = cos(d,q) = d·q/|d|×|q|

文檔長度歸一化

?一個(gè)文檔向量除以它的L2 范數(shù)（Xi的平方和取根號(hào)）就是給這個(gè)文檔進(jìn)行了長度歸一化

向量空間模型特點(diǎn)

優(yōu)點(diǎn):

（1）幫助改善了檢索結(jié)果。

（2）部分匹配的文檔也可以被檢索到。

（3）可以基于向量cosine 的值進(jìn)行排序，提供給用戶。

缺點(diǎn):

（1）這種方法假設(shè)標(biāo)記詞是相互獨(dú)立的，但實(shí)際可能不是這樣，如同義詞、近義詞等往往被認(rèn)為是不相關(guān)的詞

（2）維度非常高：特別是互聯(lián)網(wǎng)搜索引擎，空間可能達(dá)到千萬維或更高

（3）向量空間非常稀疏：對(duì)每個(gè)向量來說大部分都是0

第九講 檢索排序

精確top K檢索及其加速辦法

(一般)步驟：對(duì)每個(gè)文檔評(píng)分(余弦相似度)，按照評(píng)分高低排序，選出前K個(gè)結(jié)果

如何加速：

方法一：快速計(jì)算余弦

方法二：堆排序法N中選K（不對(duì)所有文檔的評(píng)分結(jié)果排序而直接選出Top K篇文檔）只是縮減了排序這一步驟

方法三：提前終止計(jì)算 （不需要計(jì)算所有Ｎ篇文檔的得分

非精確top K檢索

簡答題不用細(xì)答，看看了解

基本思想：找一個(gè)文檔集合A，K< |A|<< N，利用A中的top K結(jié)果代替整個(gè)文檔集的top K結(jié)果

下面的策略就是為了縮減文檔的數(shù)量

? 策略一：索引去除(Index elimination)

只考慮那些詞項(xiàng)的idf 值超過一定閾值的文檔

只考慮包含多個(gè)查詢?cè)~項(xiàng)

? 策略二：勝者表(Champion list) 每個(gè)詞項(xiàng)t對(duì)應(yīng)tf值高的表

? 策略三：靜態(tài)得分 不僅相關(guān)，還權(quán)威，根據(jù)相關(guān)和權(quán)威度加權(quán)，對(duì)doc進(jìn)行排序

? 策略四：影響度(Impact)排序 以詞項(xiàng)為單位，串行遍歷詞項(xiàng)的倒排索引表

? 策略五：簇剪枝方法—預(yù)處理

Pagerank算法

?隨機(jī)游走模型 是個(gè)一階馬爾可夫鏈

–用來描述不穩(wěn)定的移動(dòng)。

–移動(dòng)節(jié)點(diǎn)隨機(jī)選擇一個(gè)方向和速度來從當(dāng)前位置移動(dòng)到新的位置

PageRank的思路：在隨機(jī)游走過程中訪問越頻繁的網(wǎng)頁越重要

PageRank的一般定義

?PageRank一般定義的想法是在基本定義的基礎(chǔ)上導(dǎo)入平滑項(xiàng)

一個(gè)一定平穩(wěn)分布的馬爾可夫鏈：

M是轉(zhuǎn)移矩陣，–R 是n維向量，表示的就是有向圖的一般PageRank

R = d M R + 1 ? d n 1 R=d M R+\frac{1-d}{n} 1 R=dMR+n1?d1

?第一項(xiàng)表示（狀態(tài)分布是平穩(wěn)分布時(shí)）依照轉(zhuǎn)移矩陣M訪問各個(gè)結(jié)點(diǎn)的概率，

?第二項(xiàng)表示完全隨機(jī)訪問各個(gè)結(jié)點(diǎn)的概率

第一項(xiàng)表示：?在任意一個(gè)網(wǎng)頁上，瀏覽者或者以概率d決定按照超鏈接隨機(jī)跳轉(zhuǎn)，這時(shí)以等概率從連接出去的超鏈接跳轉(zhuǎn)到下一個(gè)網(wǎng)頁第二項(xiàng)表示：?或者以概率（1-d)決定完全隨機(jī)跳轉(zhuǎn)，這時(shí)以等概率1/n跳轉(zhuǎn)到任意一個(gè)網(wǎng)頁?第二個(gè)機(jī)制保證從沒有連接出去的超鏈接的網(wǎng)頁也可以跳轉(zhuǎn)出。這樣可以保證平穩(wěn)分布，即一般PageRank的存在，因而一般PageRank適用于任何結(jié)構(gòu)的網(wǎng)絡(luò)。

對(duì)于一個(gè)節(jié)點(diǎn)A

P R ( A ) = ( P R ( B ) L ( B ) + P R ( C ) L ( C ) + P R ( D ) L ( D ) + ? ? ? ) d + 1 ? d N P R(A)=\left(\frac{P R(B)}{L(B)}+\frac{P R(C)}{L(C)}+\frac{P R(D)}{L(D)}+\cdots \cdot \cdot\right) d+\frac{1-d}{N} PR(A)=(L(B)PR(B)+L(C)PR(C)+L(D)PR(D)+???)d+N1?d

其中，PR(A)表示頁面A的級(jí)別，頁面Ti鏈向頁面A，L(Ti) 是頁面Ti 鏈出的鏈接數(shù)量

迭代算法

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-CgRIEJHX-1608430839960)(image\image-20201217155401700.png)]

HITS算法

了解思想就行

? 在HITS算法中,對(duì)每個(gè)網(wǎng)頁都要計(jì)算兩個(gè)值**:權(quán)威值(authority)與中心值(hub)**

HITS和PageRank的區(qū)別

a.HITS算法將重要性分為兩個(gè)值權(quán)威值(authority)與中心值(hub)，PageRank只計(jì)算一個(gè)值

b.HITS和查詢有關(guān)系，PageRank算法和查詢無關(guān)

機(jī)器學(xué)習(xí)排序

步驟：

–人工標(biāo)注訓(xùn)練數(shù)據(jù)，給出文檔和查詢相關(guān)度

–文檔特征抽取、確定特征數(shù)量，文檔轉(zhuǎn)化為特征向量

–學(xué)習(xí)分類函數(shù)、

-在實(shí)際搜索系統(tǒng)中采用機(jī)器學(xué)習(xí)模型

它有以下3種方法：

（計(jì)算損失函數(shù)的方法，也是構(gòu)造訓(xùn)練集的方法）

單文檔方法

? PointWise Approach

? 損失函數(shù)評(píng)估單個(gè) doc 的預(yù)測得分和真實(shí)得分之間差異

文檔對(duì)方法

? PairWise Approach

? 是判斷任意兩個(gè)文檔組成的文檔對(duì)是否滿足順序關(guān)系

文檔列表方法

? ListWise Approach

? 搜索結(jié)果列表整體作為一個(gè)訓(xùn)練實(shí)例

第10講 信息檢索的評(píng)價(jià)

檢索評(píng)測基礎(chǔ)

、?信息檢索系統(tǒng)的目標(biāo)是較少消耗情況下盡快、全面返回準(zhǔn)確的結(jié)果。

測試集由一個(gè)文檔集、一組信息查詢實(shí)例、對(duì)應(yīng)于每個(gè)信息查詢實(shí)例的**一組相關(guān)文檔（由專家提供）**所組成

無序評(píng)測

查全率和查準(zhǔn)率

?無序檢索結(jié)果的評(píng)價(jià)

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-ri4IinkS-1608430839961)(image\image-20201217161456944.png)]

? 查準(zhǔn)率(Precision):返回的結(jié)果中真正相關(guān)結(jié)果的比率，也稱為查準(zhǔn)率， P∈ [0,1]

? 召回率(Recall): 返回的相關(guān)結(jié)果數(shù)占實(shí)際相關(guān)結(jié)果總數(shù)的比率，也稱為查全率，R∈ [0,1] P = R R R R + R N R = R R R R + N R P=\frac{R R}{R R+R N} \quad R=\frac{R R}{R R+N R} P=RR+RNRRR=RR+NRRR 關(guān)于召回率的計(jì)算：增加一個(gè)緩沖池： ?對(duì)多個(gè)檢索系統(tǒng)的Top N個(gè)結(jié)果組成的集合進(jìn)行人工標(biāo)注，標(biāo)注出的相關(guān)文檔集合作為整個(gè)相關(guān)文檔集合。查準(zhǔn)率不變，召回率增大

精確率，不用它

平均

–宏平均(Macro Average): 對(duì)每個(gè)查詢求出某個(gè)指標(biāo)，然后對(duì)這些指標(biāo)進(jìn)行算術(shù)平均

–微平均(Micro Average): 將所有查詢視為一個(gè)查詢，將各種情況的文檔總數(shù)求和，然后進(jìn)行指標(biāo)的計(jì)算

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-pBY2WnOS-1608430839962)(image\image-20201217162720957.png)]

F值(F-measure)

? F值(F-measure)：召回率R和查準(zhǔn)率P的加權(quán)調(diào)和平均值，

? F1 標(biāo)準(zhǔn)則綜合了精度和查全率，將兩者賦予同樣的重要性來考慮。F1的計(jì)算由下面的公式?jīng)Q定（調(diào)和平均數(shù)） F ( i , j ) = 2 × recall ? ( i , j ) ×  precision ( i , j ) recall ? ( i , j ) + precision ? ( i , j ) F(i, j)=\frac{2 \times \operatorname{recall}(i, j) \times \text { precision}(i, j)}{\operatorname{recall}(i, j)+\operatorname{precision}(i, j)} F(i,j)=recall(i,j)+precision(i,j)2×recall(i,j)× precision(i,j)

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-8TG2e0UG-1608430839963)(image\image-20201217162932501.png)]

調(diào)和平均值 F = 2 1 r + 1 p F=\frac{2}{\frac{1}{r}+\frac{1}{p}} F=r1+p12

排序評(píng)測

R-查準(zhǔn)率是什么

? 計(jì)算序列中第R個(gè)位置文獻(xiàn)的查準(zhǔn)率。在公式里指分母

? R是指與當(dāng)前查詢相關(guān)的文檔總數(shù).

? R=10, R-查準(zhǔn)率=4/10;

? R=3, R-查準(zhǔn)率=2/3

查準(zhǔn)率/查全率曲線

橫軸查全率，縱軸查準(zhǔn)率

曲線下的面積被稱為AP分?jǐn)?shù)（Average precision score）

去掉鋸齒，對(duì)一x取最大y

Mean Average Precision (MAP)是什么

? 平均查準(zhǔn)率均值

? MAP是多個(gè)查詢/排名的平均精度

? 在每個(gè)相關(guān)文檔位置上查準(zhǔn)率的平均值，被稱為平均查準(zhǔn)率Average Precision (AP)

也就是對(duì)每個(gè)查詢相關(guān)的R-查準(zhǔn)率（在R位置上的那個(gè)文檔是相關(guān)的）累計(jì)求和取均值

NDCG是什么

一種總體觀察檢索排序效果的方法，利用檢索序列加和（每個(gè)搜索結(jié)果都要有個(gè)評(píng)價(jià)分，越高越好）的思路來衡量。

第11講 概率檢索模型

不考推導(dǎo)，只看思想，只有填空

看不懂，這點(diǎn)分，不要也罷

Probability ranking principle PRP概率排名原則

令x代表集合中的文檔。令R代表文件w.r.t.的相關(guān)性。給定（固定）查詢，令R = 1表示相關(guān)，而R = 0不相關(guān)。

? 概率檢索模型作為一個(gè)分類問題，

? 對(duì)于某個(gè)文檔d來說，如果其屬于相關(guān)文檔子集的概率大于屬于不相關(guān)文檔子集的概率，我們就可以認(rèn)為這個(gè)文檔與用戶查詢q 是相關(guān)的。

? P(R=1|q,d)代表給定一個(gè)文檔D對(duì)應(yīng)的相關(guān)性概率， ? P(R=0| q,d)則代表該文檔的不相關(guān)概率

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-ZfmzRkaD-1608430839964)(image\image-20201216194643050.png)]

概率檢索策略

估計(jì)每個(gè)詞項(xiàng)對(duì)相關(guān)性的貢獻(xiàn)合并以查找文檔相關(guān)性概率通過概率降低順序?qū)ξ臋n進(jìn)行排序

BIM Binary Independence Model 二元獨(dú)立模型

Binary” =布爾值：文檔表示為詞項(xiàng)的二進(jìn)制關(guān)聯(lián)向量

Independence：term在文檔中獨(dú)立出現(xiàn)

詞包模型

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-lpCcQel0-1608430839965)(image\image-20201216195435537.png)]

BM25

BM25是信息索引領(lǐng)域用來計(jì)算query與文檔相似度得分的經(jīng)典算法

不同于TF-IDF，BM25的公式主要由三個(gè)部分組成： ? query中每個(gè)單詞t與文檔d之間的相關(guān)性? 單詞t與query之間的相似性? 每個(gè)單詞的權(quán)重

目標(biāo)：對(duì)術(shù)語頻率和文檔長度敏感，同時(shí)不添加太多參數(shù)

文件生成模型

使用多項(xiàng)式分布從詞典中獨(dú)立繪制單詞

詞項(xiàng)頻率（tf）的分布遵循二項(xiàng)式分布-由泊**松（Poisson）**近似

泊松模型

假設(shè)文檔中的詞頻（tfi）遵循泊松分布

?“固定間隔”表示文檔長度固定…認(rèn)為大小恒定的文檔摘要?…稍后將修復(fù)

第12講 隱語義空間

奇異值分解需要了解，但是不考了

?用前r大的奇異值來近似描述矩陣

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-WX65Uzzn-1608430839966)(C:\Users\yandalao\AppData\Roaming\Typora\typora-user-images\image-20201220095654805.png)]

PCA主成分分析（回憶計(jì)算機(jī)視覺）

隱語義分析 LSA

什么是LSA

–使用統(tǒng)計(jì)計(jì)算的方法對(duì)大量的文本集進(jìn)行分析，–從而提取出詞與詞之間潛在的語義結(jié)構(gòu)，并用這種潛在的語義結(jié)構(gòu)，來表示詞和文本，達(dá)到消除詞之間的相關(guān)性和簡化文本向量實(shí)現(xiàn)降維的目的

把高維的向量空間模型（VSM）表示中的文檔映射到低維的潛在語義空間中

基本步驟

（1）建立詞頻矩陣

（2）計(jì)算矩陣的奇異值分解

（3）對(duì)于每一個(gè)文檔d，用排除了SVD中消除后的詞的新的向量替換原有的向量

（4）用轉(zhuǎn)換后的矩陣進(jìn)行文檔索引和相似度計(jì)算

LSA優(yōu)點(diǎn)

（1）文檔和單詞都映射到同一個(gè)語義空間，所以可以計(jì)算文檔和文檔的相似度，詞項(xiàng)和詞項(xiàng)的相似度，詞項(xiàng)和文檔的相似度

（2）語義空間的維度明顯明顯少于源單詞-文章矩陣

?最關(guān)鍵的性質(zhì)：每個(gè)奇異值對(duì)應(yīng)的是每個(gè)“語義”維度的權(quán)重

?將不太重要的權(quán)重置為0，可以保留重要的信息，去掉一些信息“枝節(jié)”。。枝節(jié)信息可能會(huì)使本來應(yīng)該相似的對(duì)象不相似

LSA缺點(diǎn)

a) 無法解決多義詞的問題

b) 特征向量的方向沒有對(duì)應(yīng)的物理解釋

c) SVD的計(jì)算復(fù)雜度很高，而且當(dāng)有新的文檔來到時(shí)，若要更新模型需重新訓(xùn)練

d) 維數(shù)的選擇是ad-hoc的

e) LSA具有詞袋模型的缺點(diǎn)，即在一篇文章，或者一個(gè)句子中忽略詞語的先后順序

f) LSA的概率模型假設(shè)文檔和詞的分布是服從聯(lián)合正態(tài)分布的，但從觀測數(shù)據(jù)來看是服從泊松分布的

概率潛在語義分析 pLSA

什么是pLSA

a) PLSA是以統(tǒng)計(jì)學(xué)的角度來看待LSA，是基于雙模式和共現(xiàn)的數(shù)據(jù)分析方法延伸的經(jīng)典的統(tǒng)計(jì)學(xué)方法

生成模型

?在概率統(tǒng)計(jì)理論中，

–生成模型是指能夠隨機(jī)生成觀測數(shù)據(jù)的模型，尤其是在給定某些隱含參數(shù)的條件下。它給觀測值和標(biāo)注數(shù)據(jù)序列指定一個(gè)聯(lián)合概率分布

什么是主題模型？

一篇文檔(Document) 可以由多個(gè)主題(Topic) 混合而成每個(gè)Topic 都是詞匯上的概率分布每個(gè)詞都是由一個(gè)固定的 Topic 生成的

“文檔-詞項(xiàng)”的生成模型的訓(xùn)練？

a) 按照概率選擇一篇文檔d

b) 選定文檔后，從主題分布中按照概率選擇一個(gè)隱含的主題類別p(z|d)

c) 選定后，從詞分布中按照概率p(w|z)選擇一個(gè)詞

PLSA生成文檔的過程?

a) pLSA中生成文檔的整個(gè)過程便是選定文檔生成主題，確定主題生成詞。

b) 自動(dòng)地發(fā)現(xiàn)文檔集中的主題（分布）

i. 根據(jù)大量已知的文檔-詞項(xiàng)信息p(w|d) ，

ii. 訓(xùn)練出文檔-主題p(z|d)和主題-詞項(xiàng)p(w|z)

EM算法

PLSA有哪些應(yīng)用？

根據(jù)p(z|d)來的

a) 文本聚類

b) 文本分類

PLSA的優(yōu)勢？

a) 定義了概率模型，而且每個(gè)變量以及相應(yīng)的概率分布和條件概率分布都有明確的物理解釋

b) 相比于LSA隱含了高斯分布假設(shè)，pLSA隱含的Multi-nomial分布假設(shè)更符合文本特性

c) pLSA的優(yōu)化目標(biāo)是是KL-divergence最小，而不是依賴于最小均方誤差等準(zhǔn)則

d) 可以利用各種model selection和complexity control準(zhǔn)則來確定topic

pLSA不足

?隨著document和term 個(gè)數(shù)的增加，pLSA模型也線性增加，變得越來越龐大；

?PLSA可以生成其所在數(shù)據(jù)集的的文檔的模型，但卻不能生成新文檔的模型。

?EM算法需要反復(fù)的迭代，需要很大計(jì)算量；

?概率模型不夠完備

–不是完整的貝葉斯模型

–文檔-主題p(z|d)和主題-詞項(xiàng)p(w|z)是直接根據(jù)數(shù)據(jù)估計(jì)出來的，沒有進(jìn)一步引入先驗(yàn)

這兩點(diǎn)在LDA模型做了優(yōu)化

LDA模型

什么是LDA模型？

a) 一個(gè)隱含狄利克雷分布的主題模型

和pLSA主題模型有什么區(qū)別

增加了狄利克雷的先驗(yàn)知識(shí)，所有的參數(shù)都不是設(shè)定的，而是進(jìn)行了全貝葉斯化，更符合實(shí)際的情況

GENSIM

Gensim是一個(gè)用于從文檔中自動(dòng)提取語義主題的Python庫

?第一步、準(zhǔn)備訓(xùn)練語料

?第二步、預(yù)處理

–分詞（tokenize the documents）、去除停用詞和在語料中只出現(xiàn)一次的詞

?第三步、文本向量化

第13講 詞嵌入

重點(diǎn)：統(tǒng)計(jì)語言，表征學(xué)習(xí)

統(tǒng)計(jì)語言模型

什么是語言模型和統(tǒng)計(jì)語言模型？

a) 語言模型根據(jù)語言客觀事實(shí)而進(jìn)行的語言抽象數(shù)學(xué)建模

b) 統(tǒng)計(jì)語言模型為上下文相關(guān)的特性建立數(shù)學(xué)模型

語言模型的公式

–S ：一連串特定順序排列的詞ω1，ω2，…，ωn

a) S 的概率 P(S)等于每一個(gè)詞出現(xiàn)的概率相乘

b) P(S) =*P*(ω1)?*P*(ω2|ω1)?*P*(ω3|ω1,ω2)???*P*(ωn|ω1，ω2，…，ωn-1)

什么是n-gram語言模型？

N-1階馬爾可夫假設(shè):

假定文本中的每個(gè)詞ωi和前面的N-1個(gè)詞有關(guān)，而與更前面的詞無關(guān)

對(duì)應(yīng)的語言模型稱為N元模型(N-Gram Model)

統(tǒng)計(jì)語言模型、n-gram語言模型有什么應(yīng)用

? 文本生成、機(jī)器翻譯

? 拼寫糾錯(cuò)

? 語音識(shí)別

? 音字轉(zhuǎn)換

? 分詞

n-gram語言模型的缺點(diǎn)

a) 簡單有效

b) 只考慮了詞的位置關(guān)系，

c) 沒有考慮詞之間的相似度，詞語法和詞語義，

d) 還存在數(shù)據(jù)稀疏的問題

文檔重復(fù)檢測

判斷重復(fù)的思路：

–為每一個(gè)web文檔通過hash的方式生成一個(gè)指紋（fingerprint）。

–將高維的特征向量映射成一個(gè)f-bit的指紋(fingerprint)，

通過比較兩篇文章的f-bit指紋的Hamming Distance來確定文章是否重復(fù)或者高度近似

shingl算法

?核心思想是將文件相似性問題轉(zhuǎn)換為集合的相似性問題

–給定正整數(shù)k及文檔d的一個(gè)詞項(xiàng)序列，可以定義文檔d的k-shingle為d中所有k個(gè)連續(xù)詞項(xiàng)構(gòu)成的序列。

–a rose is a rose is a rose → 4-Grams

a_rose_is_a

rose_is_a_rose

is a rose is

a_rose_is_a …

直觀上看，如果兩個(gè)文檔的shingle集合幾乎一樣，那么它們就滿足近似重復(fù)

局部敏感哈希 LSH

局部敏感哈希可以用來降維

MinHash的用處

a) 可以用來快速估算兩個(gè)集合的相似度。

b) 用于在搜索引擎中檢測重復(fù)網(wǎng)頁。

c) 它也可以應(yīng)用于大規(guī)模聚類問題

SimHash的步驟

a) 分詞、hash、加權(quán)、合并、降維

w指的是每個(gè)term的權(quán)重

加權(quán)：遇到1則hash值和權(quán)值正相乘，遇到0則hash值和權(quán)值負(fù)相乘 例如W(CSDN) = 100101 4 = 4 -4 -4 4 -4 4

降維：對(duì)于n-bit簽名的累加結(jié)果，如果大于0則置1，否則置0

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-IfucazqJ-1608430839967)(image\image-20201216220909219.png)]

相似度判斷：每篇文檔得到SimHash簽名值后，接著計(jì)算兩個(gè)簽名的海明距離即可

表征學(xué)習(xí)和詞嵌入

?表征學(xué)習(xí)：

–在機(jī)器學(xué)習(xí)中，表征學(xué)習(xí)是學(xué)習(xí)一個(gè)特征的技術(shù)的集合

–將原始數(shù)據(jù)轉(zhuǎn)換成為能夠被機(jī)器學(xué)習(xí)來有效開發(fā)的一種形式。

?向量

?嵌入（embedding）

–是一種可用于將離散變量表示成連續(xù)向量的方法。

神經(jīng)網(wǎng)絡(luò)語言模型

NNLM

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-7JBzTbHC-1608430839968)(image\image-20201217085938669.png)]

知道這個(gè)圖各部分意思，下面的word2vec就是改進(jìn)了一下上面

word2vec

?對(duì)原始的NNLM模型做如下改造：

–移除前向反饋神經(jīng)網(wǎng)絡(luò)中非線性的hidden layer（ tanh 隱藏層），直接將中間層的embedding layer與輸出層的softmax layer連接；–忽略上下文環(huán)境的序列信息：輸入的所有詞向量均匯總到同一個(gè)embedding layer；–將future words納入上下文環(huán)境

?連續(xù)詞袋模型 CBOW

根據(jù)某個(gè)詞前面的C個(gè)詞或者前后C個(gè)連續(xù)的詞，來計(jì)算某個(gè)詞出現(xiàn)的概率

步驟，PPT非常清晰了

V是詞項(xiàng)數(shù)量，N是中間向量那個(gè)O的維度

具體步驟：

模型輸入：上下文的one hot表示方式

–1xV的向量

–V 詞匯表大小

輸入分別跟同一個(gè)VxN的大小的系數(shù)矩陣W1相乘得到C個(gè)1xN的隱藏層hidden layer，

然后C個(gè)取平均所以只算一個(gè)隱藏層

?隱藏層跟另一個(gè)NxV大小的系數(shù)矩陣W2相乘得到1xV的輸出層，

–這個(gè)輸出層每個(gè)元素代表的就是詞庫里每個(gè)詞的事后概率。

?輸出層需要跟ground truth也就是“coffee”的one hot形式做比較計(jì)算loss

?通過大量的數(shù)據(jù)迭代，使用梯度下降更新W和W’，來最小化loss函數(shù)，

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-Yf0THKo1-1608430839969)(image\image-20201217090553751.png)]

?Skip-Gram Model

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-8BKqtI1Y-1608430839970)(file:///D:\360MoveData\Users\yandalao\Documents\Tencent Files\2922610627\Image\C2C\AB502D3E6C82F00132C9127A669EA5E0.jpg)]

Skip-Gram Model相反，是根據(jù)某個(gè)詞，然后分別計(jì)算它前后出現(xiàn)某幾個(gè)詞的各個(gè)概率

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-dR2lyz5a-1608430839970)(image\image-20201217091825010.png)]

Skip-gram–名稱源于該模型在訓(xùn)練時(shí)會(huì)對(duì)上下文環(huán)境里的word進(jìn)行采樣

?基于成對(duì)的單詞來對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，

–訓(xùn)練樣本是 ( input word, output word ) 這樣的單詞對(duì)，

–input word和output word都是one-hot編碼的向量。

–最終模型的輸出是一個(gè)概率分布。

?輸出層使用了sotfmax。

?模型的本質(zhì):

計(jì)算輸入word和輸出word的余弦相似度，并進(jìn)行softmax歸一化（想象一下softmax圖像，所有的值都被分配到[0,1]之間的數(shù)）

?直接對(duì)詞典里的 V 個(gè)詞計(jì)算相似度并歸一化，顯然是一件極其耗時(shí)的impossible mission。為了加快速度優(yōu)化：

負(fù)采樣：–層次Softmax（Hierarchical Softmax）

word2vec應(yīng)用

列出所有相似詞語列表和程序猿相似詞語，比如攻城獅，比如猝死

?詞匯的語義的類比皇帝-皇后=男-女

?尋找對(duì)應(yīng)關(guān)系：男人——男孩 女人——女孩

第14講 圖片檢索

圖像檢索

跨媒體檢索Cross-MediaRetrieval

–不同媒體映射到同一低維度空間

?基于文本的[圖像檢索技術(shù)]TBIR

–查詢?cè)~：文本

–搜索引擎

?爬蟲 圖片

?索引 圖片對(duì)應(yīng)的文字，錨文本，URL

?基于圖像周圍文本的檢索

?基于鏈接錨文本的檢索

?基于內(nèi)容的圖像檢索CBIR

–用戶輸入一張圖片，以查找具有相同或相似內(nèi)容的其他圖片。

CBIR 的關(guān)鍵技術(shù):圖像特征提取和特征匹配

圖像特征

?圖像的特征主要包括低層特征(Primitive Features)和語義特征(Semantic Features）

–低層視覺

?與圖像的具體類型或內(nèi)容無關(guān)，

–顏色、形狀、紋理等

?某些先驗(yàn)知識(shí)（或假設(shè)）

–人的面部特征

–指紋特征

圖片的特征有顏色特征、形狀特征、紋理特征

顏色特征

底層、直觀，魯棒性強(qiáng)

顏色特征的表示有幾種

? 1、顏色直方圖(Color Histogram)直方圖，就是CV教的那個(gè)，但是是對(duì)顏色來的，不是灰度

沒有體現(xiàn)空間信息，平移尺度旋轉(zhuǎn)不變性

? **2、顏色相關(guān)圖(Color Correlogram)**不考

? 3、顏色矩(Color Moment)

–在顏色直方圖的基礎(chǔ)上計(jì)算出每個(gè)顏色的矩估計(jì)

? 4、顏色一致性矢量(Color Coherence Vectors, CCV)

紋理特征

一般說紋理就是指在圖像中反復(fù)出現(xiàn)的局部模式和它們的排列規(guī)則

基于統(tǒng)計(jì)特征的紋理特征提取

1.灰度差分統(tǒng)計(jì)法

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-DJPGNRYU-1608430839972)(image\image-20201217105234873.png)]

2.基于灰度共現(xiàn)矩陣的紋理特征 –常用統(tǒng)計(jì)量：對(duì)比度、相關(guān)度、方差、熵等

3.Tamura紋理特征

?Tamura紋理特征中所有紋理特征都在視覺上有意義。

–對(duì)比度(contrast)、粗糙度(coarseness)、方向性(directionality)對(duì)于圖像檢索尤為重要。

–線像度(1ine likeness)、規(guī)整度(regularity)和粗略度(roughness)。

基于信號(hào)處理方法描述紋理特征

–利用某種線性變換、濾波器或者濾波器組將紋理轉(zhuǎn)換到變換域，

–然后應(yīng)用某種能量準(zhǔn)則提取紋理特征。

形狀特征

有一定的語義信息

?基于輪廓的形狀描述符

鏈碼–差分結(jié)果第一位是原鏈碼最后一位和第一位相減的結(jié)果。–例如，對(duì)于4向鏈碼10030321的一階差分的結(jié)果為03031333

基于網(wǎng)格的方法

傅里葉描述子

–物體輪廓線表示成一個(gè)一維的輪廓線函數(shù)

–傅立葉級(jí)數(shù)中的一系列系數(shù)z(k)是直接與邊界曲線的形狀有關(guān)的，稱為傅立葉描述子．

?基于物體輪廓坐標(biāo)序列的傅立葉描述子具有最佳的形狀識(shí)別性能．

感知哈希算法

?全局特征降維

（1）對(duì)每張圖片生成一個(gè)**“指紋”（fingerprint）字符串，也就是圖片的特征**

（2）然后比較不同圖片的指紋，結(jié)果越接近，就說明圖片越相似（用海明距離來計(jì)算）

（之前計(jì)算文檔相似度的局部敏感哈希也是用hash法，比較哈希碼的相似度來判斷文檔相似程度，都是用海明距離）

那么怎么將圖片變?yōu)楣４a呢？

（1）均值Hash算法

縮小尺寸，收縮色彩度（比如300-64），計(jì)算所有像素的灰度平均值，閾值二值化，二值化結(jié)果為哈希值

（2）pHash算法

（3）顏色分布法–紅綠藍(lán)分別有4個(gè)區(qū)（顏色分段）

–總共可以構(gòu)成64種組 4^3。

?任何一種顏色必然屬于這64種組合中的一種——特征為64維向量，計(jì)算余弦相相似度

(4)?內(nèi)容特征法

(圖片二值化)–原圖轉(zhuǎn)成一張較小的灰度圖片，確定一個(gè)閾值，將灰度圖片轉(zhuǎn)成黑白圖片

–兩張圖片很相似，它們的黑白輪廓應(yīng)該是相近的

?基于區(qū)域的形狀描述符

大津法Otsu’s method

a) 證明了 "類內(nèi)差異最小"與"類間差異最大"是同一件事

b) 計(jì)算方法：

i. 灰度值小于閾值的像素為 n1 個(gè)，

ii. 大于等于閾值的像素為 n2 個(gè)

iii. w1 和 w2 表示這兩種像素各自的比重

iv. w1 = n1 / n

v. 類內(nèi)差異 = w1(σ1的平方) + w2(σ2的平方)

vi. 類間差異 = w1w2(μ1-μ2)^2

圖像局部特征

LBP特征

局部二值模式 Local Binary Patterns，結(jié)合了紋理圖像結(jié)構(gòu)和像素統(tǒng)計(jì)關(guān)系的紋理特征描述方法

LBP怎么構(gòu)造

? LBP算子定義為在3*3的窗口內(nèi)，

? 以窗口中心像素為閾值，將相鄰的8個(gè)像素的灰度值與其進(jìn)行比較，若周圍像素值大于中心像素值，則該像素 點(diǎn)的位置被標(biāo)記為1，否則為0。

? 3*3鄰域內(nèi)的8個(gè)點(diǎn)經(jīng)比較可產(chǎn)生8位二進(jìn)制數(shù)（通常轉(zhuǎn)換為十進(jìn)制數(shù)即LBP碼，共256種），即得到該窗口中心像 素點(diǎn)的LBP值，并用這個(gè)值來反映該區(qū)域的紋理信息。

LBP的應(yīng)用中，如紋理分類、人臉分析等，采用LBP特征譜的統(tǒng)計(jì)直方圖作為特征向量用于分類識(shí)別。可將一幅圖片化為多個(gè)子區(qū)域，分別求每個(gè)子區(qū)域的統(tǒng)計(jì)直方圖。

HOG特征

關(guān)鍵詞：cell，梯度直方圖，行人檢測

HOG是什么？

a) 方向梯度直方圖，Histogram of Oriented Gradient, HOG

b) 一種在計(jì)算機(jī)視覺和圖像處理中用來進(jìn)行物體檢測的特征描述子

c) 通過計(jì)算和統(tǒng)計(jì)圖像局部區(qū)域的梯度方向直方圖來構(gòu)成特征

Hog特征結(jié)合 SVM分類器已經(jīng)被廣泛應(yīng)用于圖像識(shí)別中，尤其在行人檢測中獲得了極大的成功

HOG特征如何提取？

a) 灰度化

b) 采用Gamma校正法對(duì)輸入圖像進(jìn)行顏色空間的標(biāo)準(zhǔn)化（歸一化）

c) 計(jì)算圖像每個(gè)像素的梯度

d) 將圖像劃分成小cells

e) 統(tǒng)計(jì)每個(gè)cell的梯度直方圖

梯度直方圖，橫軸是梯度方向，y軸是在該梯度方向的梯度值的和

f) 將每幾個(gè)cell組成一個(gè)block

g) 將圖像image內(nèi)的所有block的HOG特征descriptor串聯(lián)起來就可以得到該image的HOG特征descriptor了

HOG算法的優(yōu)缺點(diǎn)？

a) 優(yōu)點(diǎn)

i. 由于HOG是在圖像的局部方格單元上操作，所以它對(duì)圖像幾何的和光學(xué)的形變都能保持很好的不 變性，這兩種形變只會(huì)出現(xiàn)在更大的空間領(lǐng)域上。

ii. 其次，在粗的空域抽樣、精細(xì)的方向抽樣以及較強(qiáng)的局部光學(xué)歸一化等條件下，只要行人大體上能夠保持直立的姿 勢，可以容許行人有一些細(xì)微的肢體動(dòng)作，這些細(xì)微的動(dòng)作可以被忽略而不影響檢測效果。

iii. 因此HOG特征是特別適合于做圖像中的人體檢測的

SIFT

SIFT特征是什么

尺度不變特征轉(zhuǎn)換，Scale-invariant feature transform或SIFT，在空間尺度中尋找極值點(diǎn)，并提取出其位置、尺度、旋轉(zhuǎn)不變量。

SIFT特征和HOG特征好處

SIFT特征不只具有尺度不變性，即使改變旋轉(zhuǎn)角度，圖像亮度或拍攝視角，仍然能夠得到好的檢測效果，Hog沒有旋轉(zhuǎn)和尺度不變性

SIFT有哪幾個(gè)步驟

– 步驟一：建立尺度空間

? 即建立高斯差分(DoG)金字塔

– 步驟二：在尺度空間中檢測極值點(diǎn)，并進(jìn)行精確定位和篩選

– 步驟三：特征點(diǎn)方向賦值，

? 完成此步驟后，每個(gè)特征點(diǎn)有三個(gè)信息：位置、尺度、方向

– 步驟四：計(jì)算特征描述子

SIFT特征的匹配是暴力匹配

圖像檢索算法

圖像檢索算法

a) 圖像檢索領(lǐng)域：將局部特征表示成全局特征的編碼

b) 通常繼承了局部特征的部分不變性，如對(duì)平移、旋轉(zhuǎn)、縮放、光照和遮擋等與語義相關(guān)不大的因素保持不變

三種經(jīng)典的編碼

a) [BoW](http://yongyuan.name/blog/Bag of visual words model: recognizing object categories)

b) VLAD局部聚合向量

c) FV

BOF

圖像視為文檔，局部特征經(jīng)過聚類后看作一個(gè)視覺詞匯（也就是詞）

BOF算法先求出特征點(diǎn)，再聚類生成類心，得到視覺詞匯，生成直方圖（橫軸視覺詞匯，縱軸頻數(shù)），再根據(jù)TF-IDF調(diào)整權(quán)重

查詢時(shí)，求夾角余弦

BOF算法流程

– 1.用surf算法生成圖像庫中每幅圖的特征點(diǎn)及描述符。

? surf算法是關(guān)鍵點(diǎn)計(jì)算和描述算法，作用和SIFT相似。

– 2.再用k-means算法對(duì)圖像庫中的特征點(diǎn)進(jìn)行訓(xùn)練，生成類心。

– 3.生成每幅圖像的BOF，

? 判斷圖像的每個(gè)特征點(diǎn)與哪個(gè)類心最近，最近則放入該類心，最后將生成一列頻數(shù)表，即初步的無權(quán)BOF（直方圖向量）。

– 4.通過tf-idf對(duì)頻數(shù)表加上權(quán)重，生成最終的bof。

? 因?yàn)槊總€(gè)類心對(duì)圖像的影響不同。比如超市里條形碼中的第一位總是6，它對(duì)辨別產(chǎn)品毫無作用，因此權(quán)重要減小。

? TF/IDF

– 5.對(duì)查詢圖像也進(jìn)行3.4步操作，生成該圖的直方圖向量BOF。

– 6.將查詢圖像的Bof向量與圖像庫中每幅圖的Bof向量計(jì)算相似度

? 求夾角余弦。

Fisher vector

FV考慮了特征點(diǎn)到每個(gè)聚類中心的距離，也就是用所有聚類中心的線性組合去表示該特征點(diǎn)

–FV描述局部特征和GMM中心之間的平均一階和二階差異

VLAD特征

?可以認(rèn)為VLAD是FV的簡化版本

?如同BOF先建立出含有k個(gè)visual word的codebook，只考慮離特征點(diǎn)最近的聚類中心

-采用的是計(jì)算出local descriptor和每個(gè)visual word(ci)在每個(gè)分量上的差距，將每個(gè)分量的差距形成一個(gè)新的向量來代表圖片