第一講 搜索

IR（信息檢索是什么樣的學科）

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

(資料圖片僅供參考)

為什么要進行信息檢索？信息過載

搜索

搜索的過程

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

信息檢索的本質(zhì)

確定文檔和查詢之間的相關度是IR的核心問題

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

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

什么是相關度

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

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

相關度通常只有相對意義

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

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

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

定義“相關性”的兩個角度：(了解)

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

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

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

信息檢索模型

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

信息檢索主要技術

（1）文本分析（NLP）

（2）建立索引

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

（4）排序（實驗室評價）

搜索引擎

工作原理

（1） 爬行和抓取

（2） 文本分析

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

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

搜索引擎評價

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

第二講 網(wǎng)絡爬蟲技術

爬蟲定義

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

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

爬蟲必須具有的功能

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

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

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

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

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

4.4 分布式: 可以在多臺機器上分布式運行

?分布式帶來的問題

–哈希表判重

?解決方法：

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

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

可擴展性: 添加更多機器后采集率應該提高

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

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

爬取框架

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

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

4、URL 判重

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

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

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

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

爬蟲分類

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

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

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

–是指從一些種子URL擴充到整個Web的信息采集

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

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

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

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

常見的開源爬蟲

Nutch Heritrix

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

–包括爬蟲crawler和查詢searcher。

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

Pandas模塊

lxml模塊

?lxml是一個HTML/XML的解析庫

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

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

網(wǎng)頁解析方法

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

?正則表達式

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

?基于DOM

正則表達式

1、正則表達式的定義

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

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

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

3、正則表達式的工具有哪些

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

4、正則表達式匹配特點是什么

（1）正則表達式匹配速度快，

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

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

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

DOM

5、什么叫做DOM

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

DOM將HTML視為樹狀結(jié)構的元素，所有元素以及他們的文字和屬性可通過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ī)范的文本再進行解析

用瀏覽器的方式解析文檔

–lxml

?python的一個解析庫，

?支持HTML和XML的解析，

?支持XPath解析方式，

?而且解析效率非常高

?lxml只會局部遍歷

兩種方法比較

正則表達式匹配

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

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

HTML DOM樹

（1）提取HTML DOM樹提取在解析HTML時速度較慢，但其表達能力相當于上下文無關文法。

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

Python爬蟲

?工作過程

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

–過濾

Re

bs4

Scrapy shell

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

直接用來測試XPath或者CSS表達式，不用import響應模塊

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

python爬蟲框架 Scrapy

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

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

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(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é)構，提供在數(shù)據(jù)結(jié)構樹中找尋節(jié)點的能力。

?xpath為scrapy中的解析方式

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

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

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

Scrapy項目

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

–新建項目 ：新建一個新的爬蟲項目

–明確目標 （編寫items.py）：明確你想要抓取的目標

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

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

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

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

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

yield

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

–return items

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

?yield返回的是一個生成器，也是可迭代對象，有利于減小服務器資源

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

爬取多個網(wǎng)頁

?start_urls

?起始爬取列表，可以是多個url

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

爬取多層網(wǎng)頁

?解析函數(shù)的末尾，通過Request方法對下一個頁面手動發(fā)起請求

?**先提取二級頁面url，**再對二級頁面發(fā)送請求

比較

?request和bs4

–頁面級爬蟲，功能庫

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

–重點在于頁面下載

?Scrapy

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

–并行性好，性能較高

–重點在于爬蟲結(jié)構

元搜索引擎

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

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

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

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

Robot 協(xié)議

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

User-agent

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

?UA字符串在每次瀏覽器 HTTP 請求時發(fā)送到服務器！

–反爬蟲

IP屏蔽

–爬蟲：對策

?連接代理服務器

–寫了個IP代理池

?多個IP并行

? 增大爬取時間間隔

用戶登陸

?分析登陸過程的方法

?4.1發(fā)送post請求

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

?4.3分析Cookie

–http 請求帶著Cookie

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

?流程

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

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

?和基礎****url拼接

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

–后臺接受請求，生成cookie，發(fā)給用戶

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

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

?保存cookie到文件

?從文件中讀取cookie并訪問

?利用cookie模擬登錄

模擬瀏覽器進行交互

selenium

?反爬蟲： 用戶登陸

–輸入用戶名–輸入口令

–點擊登陸按鈕

?Selenium用程序模擬整個操作過程

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

處理Cookie：

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

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

?保存cookies到文件

?并添加cookies自動登錄

AJAX 動態(tài)加載

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

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

驗證碼

?圖像識別

–6.1獲取圖片

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

?屏幕截圖

–6.2圖片處理Pillow與PIL模塊

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

-6.4 圖片滑動驗證碼

第五講 詞項詞典

如何建立詞項詞典？

一、文檔解析(Parsing a document)

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

三、詞項歸一化 (Normalization)

四、詞干還原 (Stemming)

五、詞形歸并 (Lemmatization)

六、去掉停用詞 (Stop Words)

詞項歸一化

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

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

策略：建立同義詞擴展表

a) 為每個查詢維護一張包含多個詞的查詢擴展詞表

b) 在建立索引建構時就對詞進行擴展

詞干還原

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

b) 詞干還原能夠提高召回率，但是會降低準確率

詞形歸并

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

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

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

a) 代表意義不同。

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

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

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

i. 詞干還原在一般情況下會將多個派生相關詞合并在一起，

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

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

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

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

停用詞

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

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

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

a) 優(yōu)點：

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

ii. 縮小搜索范圍，

iii. 提高搜索的效率

iv. 機器學習文本分類算法的文檔的預處理

b) 缺點：

i. 有時消除的停用詞對檢索是有意義的

如何確定停用詞

a) 查表法

b) 基于文檔頻率

第六講 中文分詞

分詞方法

a) 基于理解的分詞方法

NLP、語義分析、句法分析

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

查字典。

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

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

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

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

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

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

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

b) 缺點 ： 效果差

i. Out of Vocabulary

ii. 歧義消解能力差；

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

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

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

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

a) 優(yōu)點：

i. 分詞準確度高；

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

b) 缺點：

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

ii. 對常用詞的識別精度差，時空開銷大

iii. 學習算法的復雜度往往較高，計算代價較大，依賴手工定義的特征工程

基于HMM的中文分詞方法

HMM作用

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

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

HMM模型是一個五元組:

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

ObservedSet: 觀察值集合

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

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

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

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

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

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

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

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

a) 模型參數(shù)學習問題

b) 預測問題

c) 評估觀察序列概率

HMM分詞

預測問題，也叫解碼問題

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

Viterbi 算法

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

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

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

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

–7是輸入句子的字數(shù)。

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

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

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

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

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

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

1、什么是信息檢索模型

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

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

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

? 集合論模型：布爾模型、模糊集合模型、擴展布爾模型

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

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

? 深度學習模型

3、布爾模型是什么

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

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

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

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

進行查詢的時候，用布爾表達式進行匹配，計算二值的相關度。

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

4、什么是bag of words 模型

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

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

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

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

6、什么是倒排索引

有詞項和倒排記錄組成，**詞項詞典：**對于每一個詞項，存儲所有包含這個詞項的文檔的一個列表。**倒排記錄表：**一個文檔用一個序列號docID來表示。

?建立索引的步驟：

–詞條序列Token Sequence

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

–排序

?先按照詞條排序，

?再按照docID排序

–構建詞典和倒排表

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

?分割成詞典和倒排表

9、布爾檢索模型的特點是什么

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

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

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

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

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

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

? 同義關系 電腦 OR 計算機

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

缺點 （1）準確匹配，信息需求的能力表達不足。不能輸出部分匹配的情況

（2）無權重設計 無法排序，

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

（4） 很難進行自動的相關反饋

第八講 向量空間模型

排序檢索

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

Jaccard 系數(shù)

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

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

? Jaccard(A,A) = 1

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

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

–沒有考慮

?文檔長短

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

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

詞項頻率

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

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

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

文檔頻率 (Document frequency，df)

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

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

– 與詞項t包含的信息量成反比

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

idf (inverse document frequency)逆文檔頻率

? idft= log10(N/dft)

– idft是反映詞項t的信息量的一個指標

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

tf-idf是什么

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

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

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

向量空間模型

是一個**|V|維實向量空間**（V是詞項集合，|V|表示詞項個數(shù)），空間的每一維都對應一個詞項，每篇文檔表示成一個基于tf-idf權重的實值向量，向量的維度是詞項的個數(shù)，文檔是空間中的點或者向量，這就是向量空間模型

向量相似度計算

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

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

文檔長度歸一化

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

向量空間模型特點

優(yōu)點:

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

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

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

缺點:

（1）這種方法假設標記詞是相互獨立的，但實際可能不是這樣，如同義詞、近義詞等往往被認為是不相關的詞

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

（3）向量空間非常稀疏：對每個向量來說大部分都是0

第九講 檢索排序

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

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

如何加速：

方法一：快速計算余弦

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

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

非精確top K檢索

簡答題不用細答，看看了解

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

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

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

只考慮那些詞項的idf 值超過一定閾值的文檔

只考慮包含多個查詢詞項

? 策略二：勝者表(Champion list) 每個詞項t對應tf值高的表

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

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

? 策略五：簇剪枝方法—預處理

Pagerank算法

?隨機游走模型 是個一階馬爾可夫鏈

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

–移動節(jié)點隨機選擇一個方向和速度來從當前位置移動到新的位置

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

PageRank的一般定義

?PageRank一般定義的想法是在基本定義的基礎上導入平滑項

一個一定平穩(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

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

?第二項表示完全隨機訪問各個結(jié)點的概率

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

對于一個節(jié)點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的級別，頁面Ti鏈向頁面A，L(Ti) 是頁面Ti 鏈出的鏈接數(shù)量

迭代算法

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

HITS算法

了解思想就行

? 在HITS算法中,對每個網(wǎng)頁都要計算兩個值**:權威值(authority)與中心值(hub)**

HITS和PageRank的區(qū)別

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

b.HITS和查詢有關系，PageRank算法和查詢無關

機器學習排序

步驟：

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

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

–學習分類函數(shù)、

-在實際搜索系統(tǒng)中采用機器學習模型

它有以下3種方法：

（計算損失函數(shù)的方法，也是構造訓練集的方法）

單文檔方法

? PointWise Approach

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

文檔對方法

? PairWise Approach

? 是判斷任意兩個文檔組成的文檔對是否滿足順序關系

文檔列表方法

? ListWise Approach

? 搜索結(jié)果列表整體作為一個訓練實例

第10講 信息檢索的評價

檢索評測基礎

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

測試集由一個文檔集、一組信息查詢實例、對應于每個信息查詢實例的**一組相關文檔（由專家提供）**所組成

無序評測

查全率和查準率

?無序檢索結(jié)果的評價

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

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

? 召回率(Recall): 返回的相關結(jié)果數(shù)占實際相關結(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 關于召回率的計算：增加一個緩沖池： ?對多個檢索系統(tǒng)的Top N個結(jié)果組成的集合進行人工標注，標注出的相關文檔集合作為整個相關文檔集合。查準率不變，召回率增大

精確率，不用它

平均

–宏平均(Macro Average): 對每個查詢求出某個指標，然后對這些指標進行算術平均

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

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

F值(F-measure)

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

? F1 標準則綜合了精度和查全率，將兩者賦予同樣的重要性來考慮。F1的計算由下面的公式?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)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(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

排序評測

R-查準率是什么

? 計算序列中第R個位置文獻的查準率。在公式里指分母

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

? R=10, R-查準率=4/10;

? R=3, R-查準率=2/3

查準率/查全率曲線

橫軸查全率，縱軸查準率

曲線下的面積被稱為AP分數(shù)（Average precision score）

去掉鋸齒，對一x取最大y

Mean Average Precision (MAP)是什么

? 平均查準率均值

? MAP是多個查詢/排名的平均精度

? 在每個相關文檔位置上查準率的平均值，被稱為平均查準率Average Precision (AP)

也就是對每個查詢相關的R-查準率（在R位置上的那個文檔是相關的）累計求和取均值

NDCG是什么

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

第11講 概率檢索模型

不考推導，只看思想，只有填空

看不懂，這點分，不要也罷

Probability ranking principle PRP概率排名原則

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

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

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

? P(R=1|q,d)代表給定一個文檔D對應的相關性概率， ? P(R=0| q,d)則代表該文檔的不相關概率

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

概率檢索策略

估計每個詞項對相關性的貢獻合并以查找文檔相關性概率通過概率降低順序?qū)ξ臋n進行排序

BIM Binary Independence Model 二元獨立模型

Binary” =布爾值：文檔表示為詞項的二進制關聯(lián)向量

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

詞包模型

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

BM25

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

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

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

文件生成模型

使用多項式分布從詞典中獨立繪制單詞

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

泊松模型

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

?“固定間隔”表示文檔長度固定…認為大小恒定的文檔摘要?…稍后將修復

第12講 隱語義空間

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

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

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

PCA主成分分析（回憶計算機視覺）

隱語義分析 LSA

什么是LSA

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

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

基本步驟

（1）建立詞頻矩陣

（2）計算矩陣的奇異值分解

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

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

LSA優(yōu)點

（1）文檔和單詞都映射到同一個語義空間，所以可以計算文檔和文檔的相似度，詞項和詞項的相似度，詞項和文檔的相似度

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

?最關鍵的性質(zhì)：每個奇異值對應的是每個“語義”維度的權重

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

LSA缺點

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

b) 特征向量的方向沒有對應的物理解釋

c) SVD的計算復雜度很高，而且當有新的文檔來到時，若要更新模型需重新訓練

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

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

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

概率潛在語義分析 pLSA

什么是pLSA

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

生成模型

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

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

什么是主題模型？

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

“文檔-詞項”的生成模型的訓練？

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

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

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

PLSA生成文檔的過程?

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

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

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

ii. 訓練出文檔-主題p(z|d)和主題-詞項p(w|z)

EM算法

PLSA有哪些應用？

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

a) 文本聚類

b) 文本分類

PLSA的優(yōu)勢？

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

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

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

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

pLSA不足

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

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

?EM算法需要反復的迭代，需要很大計算量；

?概率模型不夠完備

–不是完整的貝葉斯模型

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

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

LDA模型

什么是LDA模型？

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

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

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

GENSIM

Gensim是一個用于從文檔中自動提取語義主題的Python庫

?第一步、準備訓練語料

?第二步、預處理

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

?第三步、文本向量化

第13講 詞嵌入

重點：統(tǒng)計語言，表征學習

統(tǒng)計語言模型

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

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

b) 統(tǒng)計語言模型為上下文相關的特性建立數(shù)學模型

語言模型的公式

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

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

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

什么是n-gram語言模型？

N-1階馬爾可夫假設:

假定文本中的每個詞ωi和前面的N-1個詞有關，而與更前面的詞無關

對應的語言模型稱為N元模型(N-Gram Model)

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

? 文本生成、機器翻譯

? 拼寫糾錯

? 語音識別

? 音字轉(zhuǎn)換

? 分詞

n-gram語言模型的缺點

a) 簡單有效

b) 只考慮了詞的位置關系，

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

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

文檔重復檢測

判斷重復的思路：

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

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

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

shingl算法

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

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

–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 …

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

局部敏感哈希 LSH

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

MinHash的用處

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

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

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

SimHash的步驟

a) 分詞、hash、加權、合并、降維

w指的是每個term的權重

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

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

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

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

表征學習和詞嵌入

?表征學習：

–在機器學習中，表征學習是學習一個特征的技術的集合

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

?向量

?嵌入（embedding）

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

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

NNLM

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

知道這個圖各部分意思，下面的word2vec就是改進了一下上面

word2vec

?對原始的NNLM模型做如下改造：

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

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

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

步驟，PPT非常清晰了

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

具體步驟：

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

–1xV的向量

–V 詞匯表大小

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

然后C個取平均所以只算一個隱藏層

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

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

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

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

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

?Skip-Gram Model

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

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

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

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

?基于成對的單詞來對神經(jīng)網(wǎng)絡進行訓練，

–訓練樣本是 ( input word, output word ) 這樣的單詞對，

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

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

?輸出層使用了sotfmax。

?模型的本質(zhì):

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

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

負采樣：–層次Softmax（Hierarchical Softmax）

word2vec應用

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

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

?尋找對應關系：男人——男孩 女人——女孩

第14講 圖片檢索

圖像檢索

跨媒體檢索Cross-MediaRetrieval

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

?基于文本的[圖像檢索技術]TBIR

–查詢詞：文本

–搜索引擎

?爬蟲 圖片

?索引 圖片對應的文字，錨文本，URL

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

?基于鏈接錨文本的檢索

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

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

CBIR 的關鍵技術:圖像特征提取和特征匹配

圖像特征

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

–低層視覺

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

–顏色、形狀、紋理等

?某些先驗知識（或假設）

–人的面部特征

–指紋特征

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

顏色特征

底層、直觀，魯棒性強

顏色特征的表示有幾種

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

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

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

? 3、顏色矩(Color Moment)

–在顏色直方圖的基礎上計算出每個顏色的矩估計

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

紋理特征

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

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

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

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

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

3.Tamura紋理特征

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

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

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

基于信號處理方法描述紋理特征

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

–然后應用某種能量準則提取紋理特征。

形狀特征

有一定的語義信息

?基于輪廓的形狀描述符

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

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

傅里葉描述子

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

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

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

感知哈希算法

?全局特征降維

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

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

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

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

（1）均值Hash算法

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

（2）pHash算法

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

–總共可以構成64種組 4^3。

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

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

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

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

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

大津法Otsu’s method

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

b) 計算方法：

i. 灰度值小于閾值的像素為 n1 個，

ii. 大于等于閾值的像素為 n2 個

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é)構和像素統(tǒng)計關系的紋理特征描述方法

LBP怎么構造

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

? 以窗口中心像素為閾值，將相鄰的8個像素的灰度值與其進行比較，若周圍像素值大于中心像素值，則該像素 點的位置被標記為1，否則為0。

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

LBP的應用中，如紋理分類、人臉分析等，采用LBP特征譜的統(tǒng)計直方圖作為特征向量用于分類識別?？蓪⒁环鶊D片化為多個子區(qū)域，分別求每個子區(qū)域的統(tǒng)計直方圖。

HOG特征

關鍵詞：cell，梯度直方圖，行人檢測

HOG是什么？

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

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

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

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

HOG特征如何提??？

a) 灰度化

b) 采用Gamma校正法對輸入圖像進行顏色空間的標準化（歸一化）

c) 計算圖像每個像素的梯度

d) 將圖像劃分成小cells

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

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

f) 將每幾個cell組成一個block

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

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

a) 優(yōu)點

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

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

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

SIFT

SIFT特征是什么

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

SIFT特征和HOG特征好處

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

SIFT有哪幾個步驟

– 步驟一：建立尺度空間

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

– 步驟二：在尺度空間中檢測極值點，并進行精確定位和篩選

– 步驟三：特征點方向賦值，

? 完成此步驟后，每個特征點有三個信息：位置、尺度、方向

– 步驟四：計算特征描述子

SIFT特征的匹配是暴力匹配

圖像檢索算法

圖像檢索算法

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

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

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

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

b) VLAD局部聚合向量

c) FV

BOF

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

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

查詢時，求夾角余弦

BOF算法流程

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

? surf算法是關鍵點計算和描述算法，作用和SIFT相似。

– 2.再用k-means算法對圖像庫中的特征點進行訓練，生成類心。

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

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

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

? 因為每個類心對圖像的影響不同。比如超市里條形碼中的第一位總是6，它對辨別產(chǎn)品毫無作用，因此權重要減小。

? TF/IDF

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

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

? 求夾角余弦。

Fisher vector

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

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

VLAD特征

?可以認為VLAD是FV的簡化版本

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

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