北郵郭軍2016web搜索第二章

1、Web 搜索搜索郭軍郭軍北京郵電大學(xué) 第第2 2章章 文本檢索文本檢索nWeb信息采集信息采集n文本的保存與索引文本的保存與索引n檢索模型檢索模型n網(wǎng)頁排序網(wǎng)頁排序n查詢重構(gòu)查詢重構(gòu)n文本聚類文本聚類n文本分類文本分類n特征選擇特征選擇n特征變換特征變換引言引言n文本是最基本、同時也是最高級（抽象）的信息媒體n文本檢索是Web搜索的起點也是重點n文本檢索所涉及的問題uWeb信息的采集與組織u文本的表示u用戶查詢方法u相關(guān)文檔排序u文本聚類u文本分類Web信息采集信息采集nCrawler/Spider:u利用hyperlink自動獲取網(wǎng)頁的URLu利用HTTP 進行網(wǎng)絡(luò)編程自動下載網(wǎng)頁nCraw

2、ler的基本原理u網(wǎng)頁采集過程是一個從WWW的某網(wǎng)頁出發(fā)不斷向前漫游的過程u漫游的方向和路線是隨機的u為了將隨機漫游變成有序的向外擴展，必須對其進行有效地控制Crawler 的工作進程的工作進程Crawler的工作效率的工作效率n多線程Crawlern分布式Crawler: 通過分散在不同地點的服務(wù)器實現(xiàn)Crawler的難題的難題n前沿URL的選擇u廣度優(yōu)先/深度優(yōu)先?u優(yōu)質(zhì)網(wǎng)頁優(yōu)先？n無效URL問題n同一網(wǎng)頁的多重訪問問題n網(wǎng)頁的再訪問周期問題u流行度高的網(wǎng)頁給予高頻訪問u基于鏈接分析判斷網(wǎng)頁的活躍度文本的預(yù)處理與保存文本的預(yù)處理與保存n預(yù)處理u網(wǎng)頁去重: 基于消息摘要/鏈接結(jié)構(gòu)u網(wǎng)頁解析:

3、 HTML/XML文檔的解析，取出其中的元數(shù)據(jù)、超鏈接、標(biāo)題和文本內(nèi)容n文本的保存u文本通常以壓縮的形式保存u網(wǎng)頁平均長度為10KB，壓縮后為2-4KBu通用文件系統(tǒng)的存儲塊尺寸為4-8KBu網(wǎng)頁存儲通常采用專門開發(fā)的文件系統(tǒng)u大型商用搜索引擎需要在全球建立多個鏡像的文件系統(tǒng)骨干服務(wù)器文本的索引文本的索引(1/2)n建立索引就是制作標(biāo)記來指示內(nèi)容的位置nWeb搜索通常情況下是全文搜索，即對網(wǎng)頁中包含的所有詞匯都建立索引n倒排文件(inverted file)u詞匯表(vocabulary): 文本中所有不同詞匯的集合u位置表(occurrences):詞匯在文本中出現(xiàn)的地址列表(posting

4、 list)、字地址、詞地址、文檔地址uHeaps定律: vO(Na ) a 0.5 Gb級文本、Mb級詞匯n查詢步驟: 查詢詞匯表位置表文檔或段落文本的索引文本的索引(2/2)n倒排索引的更新批量更新u主索引+新索引(stop-press index)u新索引(d,t,s)三元組倒排(t,d,s)n對一個用戶的查詢，主索引反饋文檔集D0，新索引返回文檔集D+和D-，返回給用戶D0D+ D-n索引壓縮u文檔的標(biāo)識符壓縮: delta編碼n索引詞的選取u詞標(biāo)識、去停詞(stopword)、詞干化(stemming)檢索模型檢索模型n文本檢索的本質(zhì)問題: u用戶需求文本集中最相關(guān)(最切題)的文檔n

5、需解決的3個基本問題u用戶如何提出需求t簡單、便捷，關(guān)鍵詞的方式u相關(guān)文檔如何定義和計算t語法層相關(guān)/語義層相關(guān)u檢索結(jié)果如何反饋tURL地址清單段落檢索QABoolean模型模型n查詢: 由關(guān)鍵詞及邏輯關(guān)系符構(gòu)成的Boolean表達(dá)式n文檔: 索引詞的集合n查詢與文檔相關(guān)的定義: 索引詞的集合是否滿足查詢Boolean表達(dá)式n二元決策，無相關(guān)程度的度量n人們常常不容易用Boolean表達(dá)式描述查詢n用戶往往只是同時輸入多個關(guān)鍵詞，隱含地應(yīng)用“與”邏輯VSMn用索引詞出現(xiàn)的絕對或相對頻度來表達(dá)文檔和查詢n所有m個不同的索引詞構(gòu)成m維的特征向量n文檔dj的特征向量dj = w1j, w2j, ,

6、wmjn查詢q的特征向量q = w1q, w2q, ,wmqn計算q和dj之間相關(guān)性或相似性有多種方法 相關(guān)性計算相關(guān)性計算12211( ,)mijiqimmijiqiiwwcoswwjq dn余弦相似度12211() ()( ,)()()mijjiqqimmijjiqqiiwwwwrwwwwjq dn相關(guān)系數(shù)索引詞的權(quán)重索引詞的權(quán)重nTF: ijijjfreqfMaxFreqnIDF: logiiNidfnnTF-IDF:() logijijjifreqNwMaxFreqnn查詢詞的權(quán)重:0.5(0.5) logiqiqqifreqNwMaxFreqn概率模型概率模型(1/2)n給定一個用戶

7、查詢q和一個文檔dj ，概率模型通過估計dj與q的相關(guān)的概率來判斷二者的相關(guān)性n假設(shè)在所有文檔中存在一個對應(yīng)q的理想集合R，即R中的文檔都是q的相關(guān)文檔，R之外的文檔都是q的不相關(guān)文檔n概率模型計算幾率比:uP(dj relevant to q)/P(dj non-relevant to q)n在概率模型中，索引詞的權(quán)重變量都是二值的，即wij 0,1，wiq 0,1概率模型概率模型(2/2)n取對數(shù)后簡化ndj與q的相似性sim(dj, q)被定義為(R | ,)(|R, )(R)(, )(R | ,)(|R, )(R)jPqPqPsim dqPqPqPjjjjdddd1(1|R, )(1(

8、1|R, )(, )log(1(1|R, ) (1|R, )mijijjijiqiijijp wqp wqsim d qw wp wq p wqn兩個概率的初始化 (1| R, )0.5ijP wq(1|R, )iijnP wqNn返回文檔集合V后的改進估計|(1|R, )|iijVP wqV|(1|R, )|iiijnVP wqNVBayesian推理網(wǎng)絡(luò)模型推理網(wǎng)絡(luò)模型n節(jié)點對應(yīng)文檔、檢索詞、概念、查詢等各類實體n每個節(jié)點v都與一個隨機Boolean變量相聯(lián)系，給定父節(jié)點u1, uk, P(v|u1,uk) 通常采用“或”邏輯，即只要有一個父節(jié)點的置信邏輯為“真”，則本節(jié)點就為“真”r1d

9、1d2dn-1dnr2r3rm-1rmc1c2coq狗牛羊文檔層表示層概念層查詢貓寵物偶蹄動物網(wǎng)頁排序網(wǎng)頁排序n基于文檔與查詢的相關(guān)性的排序n基于網(wǎng)頁質(zhì)量的排序n通過超鏈接分析來改進排序結(jié)果是Web文本檢索與數(shù)據(jù)庫文本檢索的一個十分重要的區(qū)別u指向一個網(wǎng)頁的超鏈接的數(shù)量代表著網(wǎng)頁的流行度和質(zhì)量u兩個網(wǎng)頁包含較多的相同的鏈接或被相同的網(wǎng)頁所指向常常意味著它們之間具有某種密切的關(guān)系PageRankn模擬用戶在Web上可用Markov鏈建模的網(wǎng)頁瀏覽行為n假設(shè)任意節(jié)點u對于節(jié)點v都有一條有向路徑，用戶以概率分布p0隨機地從一個節(jié)點出發(fā)，pi為i時刻到達(dá)各節(jié)點的概率n令Web鄰接矩陣(圖)為E，如果節(jié)

10、點u和v之間存在超鏈接，則E(u,v) = 1，否則為0 (Nu是節(jié)點u的出度)( , )( , )/uu vu vNLE令1TiipL p則p將收斂于LT的主特征向量PageRank的完善的完善n假設(shè)用戶在Web圖的每個節(jié)點上將進行兩種選擇u以概率q隨機瀏覽Web上的任意一個網(wǎng)頁u以概率1-q在所有的出鏈接中以均勻概率選擇一個，繼續(xù)前進則11/1/(1)1/1/(1)/(1,.,1)TiiiTTiNNqqNNqq NpL ppL pPageRank的近似解的近似解n當(dāng)N很大時，直接求解改進PageRank方程組是困難的n簡單算法是先將p0的所有元素設(shè)為1/N，然后反復(fù)用因子(1-q)LT+q

11、/N 1N乘以pi，并將|pi|縮放至1。n但此方法不能保證收斂。HITSnHITS (Hypertext Induced Topic Search)n與PageRank不同，是與查詢相關(guān)的網(wǎng)頁質(zhì)量評價算法n收到查詢q后，系統(tǒng)返回一個網(wǎng)頁的集合RnR中的任意節(jié)點(網(wǎng)頁)指向的節(jié)點和指向R中任意節(jié)點的節(jié)點構(gòu)成集合X，R與X共同構(gòu)成一個基本集合Vn構(gòu)造圖G = (V , E)，E為節(jié)點間的有向鏈接n評價網(wǎng)頁的兩個測度: a(authority)和h(hub)( , )( )( )v ua uh vE( , )( )( )u vh ua vET= Eah= Ehan 賦初值a = h = 1 迭代，

12、n 收斂后，a等于ETE的主特征向量 h等于EET的主特征向量查詢重構(gòu)查詢重構(gòu)n用戶提出一個適當(dāng)?shù)牟樵冋埱笸遣蝗菀椎膎可將用戶的第一個查詢看作是初始的嘗試，通過對獲得的文檔的相關(guān)分析，對初始查詢進行重構(gòu)n查詢重構(gòu)的三類方法u基于用戶反饋信息的的方法u基于對初始反饋文檔的局部分析的方法u基于對全部文檔集合的全局分析的方法用戶相關(guān)反饋用戶相關(guān)反饋n先將檢索出的文檔清單提交給用戶，用戶查閱后，對相關(guān)的文檔進行標(biāo)記n設(shè)D+為用戶標(biāo)記的相關(guān)文檔的集合，D-為反饋文檔中非相關(guān)文檔的集合nRocchio公式+DD qqddn ，和都是可調(diào)參數(shù)，簡單的設(shè)置是令它們都為1 在D-不好確定時，常令 為0自動局

13、部分析自動局部分析n對于一個給定的查詢q，稱檢索出來的文檔集合Dl為局部文檔集合n自動局部分析從Dl中查找查詢詞的近鄰詞n近鄰的測度u關(guān)聯(lián)度u近鄰度u間接相關(guān)度 或jluvujvjdDsff1( , )iuvuvdDiuvnr t t|uviuvuvssss|uviuvuvnnnn11|( , )iuvuvdDuviuvnDr t tuvuvuuvvuvsssss局部語境分析局部語境分析LCAn基于由名詞詞組所構(gòu)成的“概念”進行查詢擴展n概念的定義通常基于詞典進行n步驟: u1) 將初始查詢檢索出的文檔分割成固定長度的段落，然后按與查詢的相關(guān)性對其排序，取出前n個u2) 計算各段落中每個概念c

14、與查詢q之間的相似度sim(c, q)u3) 將相似度最大的前m個概念加到初始查詢之中n關(guān)鍵是第二步，選擇一種合適的計算概念c和查詢q中包含的詞之間的相似度測度基于概念空間的全局分析基于概念空間的全局分析n尋找整個查詢的近鄰詞n用文本集的所有N個文檔構(gòu)成一個概念空間，每個文檔是空間中的一個維度n無論是檢索詞還是查詢，都被看作概念空間中的數(shù)據(jù)點，即概念，對于檢索詞ti(i = 1,m)，ti=(wi1,wiN)，其中21(0.50.5)log(/)max ()(0.50.5)log(/)max ()ijjjijijNillllilfm mfwfm mfn 而查詢 n 通過計算q與各檢索詞的相關(guān)性

15、進行查詢擴展iiqtqwiqt基于同義詞辭典的全局分析基于同義詞辭典的全局分析n辭典包含若干同義詞類n每個類由通過文檔聚類算法獲得的若干檢索詞構(gòu)成u采用全鏈接(complete link)的聚類算法，即類對之間的相似度被定義為所有文檔對的相似度的最小值uBottom-up的層次聚類u通過設(shè)置以下參數(shù)進行同義詞類選擇tTsim:最小類內(nèi)相似度閾值tTnod:類內(nèi)最大文檔數(shù)閾值tTidf:倒文檔頻度閾值文本聚類文本聚類n在文本檢索中的作用非常廣泛和重要n聚類一直是模式識別、機器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域中的一個重點課題n無監(jiān)督學(xué)習(xí)(Unsupervised learning)n目的是找到數(shù)據(jù)集合中潛在(

16、latent)的聚合結(jié)構(gòu)n兩大類聚類算法u區(qū)分法(discriminative method)u生成法(generative method)區(qū)分式聚類的基本思想?yún)^(qū)分式聚類的基本思想n給定一個(文檔)集合D = di|i=1,Nu其中di = (di1,diM)為元素di的VSMn定義sim(di, dj)為di和dj之間的相似度n聚類問題可以定義為:u將集合D劃分為k個子集D1,Dk，使類內(nèi)的相似度總和S達(dá)到最大1sim(,)ikiDS uvuvd ,ddd區(qū)分式聚類的方式區(qū)分式聚類的方式n區(qū)分性聚類也稱為分割聚類，核心操作是將集合中的元素排他式地劃歸到某個類中nbottom-up方式u初始將

17、每個文檔作為一類，然后對最相似的類進行合并，直至類別數(shù)目或類內(nèi)相似度達(dá)到設(shè)定值ntop-down方式u先將所有文檔放在一類，然后以增大類內(nèi)相似度為目標(biāo)，對類進行分裂操作，直至類別數(shù)目或類內(nèi)相似度達(dá)到設(shè)定的閾值Bottom-up方式例方式例Top-down方式例方式例層次匯合聚類層次匯合聚類HAC算法算法n1) 令每個文檔d在一個單獨的組中，形成N個組dn2) 令 G 為這N個組的集合n3) while |G| 1 don4)選擇 u, vG，標(biāo)準(zhǔn)為合并它們將帶來最大的利益測度n5)將 u 和 v 從 G 中移除n6)令 w = uvn7)將 w 插入 Gn8) end while隨著合并次數(shù)的

18、增加，被合并類之間的相似度sim(u,v)會越來越低第4步的常用測度，S(w)的類內(nèi)相似度，w = uv2,| |1( )sim(,)ijd dwwS wCijd dk-means聚類聚類n給定數(shù)據(jù)集合x1, xN, 每個數(shù)據(jù)是一個d維向量n目標(biāo)是把這個數(shù)據(jù)集合劃分為K個類(cluster)n預(yù)設(shè)K個類的質(zhì)心k (k = 1, K)n通過使下式最小化，迭代新質(zhì)心k和類別歸屬rnkk-means聚類算法聚類算法n1)初始化k個組的質(zhì)心向量n2) while 還可以繼續(xù)改進 don3) for 每個元素(文檔) d don4)找出質(zhì)心向量與d最相似的組cn5)將d調(diào)整到組c之中n6) end fo

19、rn7) for 每個組 c don8) 重新計算質(zhì)心向量n9) end forn10) end while要點:u預(yù)先確定類別數(shù)為ku質(zhì)心與元素都用向量表示k-means聚類示意聚類示意k-means聚類應(yīng)用聚類應(yīng)用軟軟k-means聚類聚類n硬k均值聚類: 元素d要么屬于組c，要么不屬于組c，在計算質(zhì)心時，組內(nèi)所有元素都具有相同的權(quán)重n軟k均值聚類:允許一個元素部分地分別屬于不同的組，但在計算組的質(zhì)心時各個元素的貢獻(xiàn)不同u計算質(zhì)心的公式2211/ |()1/ |Niccicijcjddd基于親和性消息的聚類基于親和性消息的聚類n在k均值聚類中，如果選用樣本數(shù)據(jù)為類中心，則稱為k中心法，稱被

20、選為中心的數(shù)據(jù)為范例(exemplar)，但初始范例選取困難n基于消息傳播的聚類方法Frey 07將所有樣本看作潛在范例，數(shù)據(jù)點通過已知的相似度被連成網(wǎng)絡(luò)，相鄰節(jié)點通過反復(fù)地傳遞和修改兩個消息responsibility和availability使范例涌現(xiàn)出來n迭代更新a(i,k)和r(i, k)算法基于親和性消息的聚類算法基于親和性消息的聚類算法n1) 輸入數(shù)據(jù)點間的相似度s(i,k)，表示k作為i的范例的適當(dāng)度n2) 為每個數(shù)據(jù)點輸入偏愛度s(k,k)，該值越大k越可能為范例n3) 將所有可用性消息a(i,k)置為0， a(i,k)是由k發(fā)給i的一個累積的“證據(jù)”， 來證明k適合于作為i的

21、范例n4)更新依靠性消息r(i,k)，這是由i發(fā)給候選范例k的(通過與其他候選范例比較的)一個累積的“證據(jù)”，證明k適于作為i的范例( , )( , )max ( ,)( ,)kkr i ks i ka i ks i kn5) 按如下規(guī)則分別更新可用性消息a(i,k)和a(k,k) , ( , )min0, ( , )max0, ( , )ii ka i kr k kr i k( , )max0, ( , )ika k kr i kn6) 對每個元素i計算 ，如不滿足終止條件，轉(zhuǎn)4)繼續(xù)迭代argmax ( ,)( ,)kkr i ka i k生成式聚類生成式聚類n每個文檔類別被看作對應(yīng)一個主

22、題的文檔集合n將文檔的產(chǎn)生看作隨機過程，每個主題類別有一個關(guān)于文檔的概率分布模型n一個文檔應(yīng)該歸屬哪個類，決定于哪個類別的模型產(chǎn)生該文檔的概率最大n關(guān)鍵是各個類別概率模型的估計二值概率模型二值概率模型n文檔是二值元素的向量，每個元素對應(yīng)詞表W中的一個詞tn假設(shè)詞的出現(xiàn)是相互獨立的事件，且只考慮詞是否出現(xiàn)而不管出現(xiàn)的次數(shù)，則可得在概率參數(shù)集合條件下文檔d生成的二值概率模型,P(|)(1)ttt dt W t dd n由于詞表中的詞數(shù)遠(yuǎn)遠(yuǎn)多于文檔中的詞數(shù)，且 的平均值低于0.5，使得該模型有利于短文本的生成，同時降低了實際出現(xiàn)可能性大的文檔的產(chǎn)生概率t多值概率模型多值概率模型n考慮詞在文檔中的出現(xiàn)

23、次數(shù)n假設(shè)文檔的總長度L符合一個概率分布P(l)n文檔的產(chǎn)生過程是一個擲|W|個面的骰子的過程，每個面對應(yīng)詞表中的一個詞n產(chǎn)生長度為ld的文檔的過程就等于投擲骰子ld次n假設(shè)第t面出現(xiàn)了n(d,t)次，則文檔的生成概率( , )P( , ( , )|)P(|)P( ( , )|,)P(|) ( , )ddddn d tdtt dln d tLln d tllLln d t 12! ( , )( , )! ( , )!.ddlln d tn d tn d t概率模型的參數(shù)估計概率模型的參數(shù)估計n假設(shè)要處理的文檔集合共對應(yīng)m個話題，產(chǎn)生第i類話題的概率為i ，第i類話題中詞t的產(chǎn)生概率為i,tn將

24、m類話題文檔的所有參數(shù)表示為:1,( ;,;, )mi tmi t n獲得多類模型的關(guān)鍵步驟是通過訓(xùn)練數(shù)據(jù)將模型中的參數(shù)估計出來，著名的EM算法可用來完成這個參數(shù)估計基于基于MLE準(zhǔn)則的參數(shù)估計準(zhǔn)則的參數(shù)估計n為了簡化描述，假設(shè)每個類別只有一個參數(shù)i，即11( ;,;,)mmm n用x表示文檔，則其生成概率1P( |)P( |)mjjjxx n設(shè)有n個iid樣本構(gòu)成訓(xùn)練集合X = x1,xn，則可根據(jù)MLE準(zhǔn)則通過對以下函數(shù)最大化來估計參數(shù)1P(|)P(|)(|)niiXxLX 11log (|)log(P(|)nmjijijLXxEM算法算法(E步步)nEM算法的思想：初始值E步/M步迭代尋

25、優(yōu)n算法在不知各個樣本的類別Y = y1,yn的情況下求解n先對給出初始“猜想”值 ，令全數(shù)據(jù)似然度Q為X、Y和條件下logL的期望值( ,)(log (|, )|,)P(|,)logP(,|)YYQELX YXY XX Y 11( ,)P( |,)log(P(|)mnililliQl xx n 推導(dǎo)可得n 由于Q是的對數(shù)似然度在Y的分布上獲得的期望，因此這一步被稱為E步EM算法算法(M步步)n怎樣才能在的基礎(chǔ)上獲得一個更好的值呢，一種合理的方法是通過最大化Q來實現(xiàn)，這一步被稱為M步n中包含和兩類參數(shù)，先以為例介紹M步的更新算法n因為有約束條件1ii11log.P( |,)0mnlillilk

26、l x n 通過標(biāo)準(zhǔn)的Lagrange優(yōu)化，可得方程組 n 求解可得11P( |,)nkiik xnEM算法算法(M步步)n 假設(shè)各類別的概率分布服從均值為k的Poisson分布 Pr( x | ) = e- x / x!11Pr( |,)(log)0mnilillikl xx n 求解可得11Pr( |,)Pr( |,)niiikniixk xk x文本分類文本分類n分類是最基本最重要的智能活動之一n模式識別系統(tǒng)的主要任務(wù)就是構(gòu)造性能優(yōu)良的分類器n分類是靠有監(jiān)督的學(xué)習(xí)實現(xiàn)的，即通過有類別標(biāo)注的樣本對分類器進行訓(xùn)練n在Web搜索中的應(yīng)用u網(wǎng)頁及文檔分類uSpam檢測u情感分類u在線廣告 k-N

27、N分類器分類器n利用k個與未知樣本最接近的已知樣本的類別來投票決定未知樣本的類別n兩個步驟:u尋找未知樣本的k個最近鄰(測度問題)u利用k近鄰的類別對未知樣本的類別進行投票預(yù)測n只需對訓(xùn)練樣本進行標(biāo)注，不需要進行其他訓(xùn)練n參數(shù)k的選擇是最大問題n計算和存儲開銷通常很大Bayes分類器分類器n基于Bayes規(guī)則的分類器，理論與應(yīng)用均非常重要n假設(shè)每個文檔只屬于一個類別，并按如下條件建模u每個類c都有一個先驗概率P(c)u對于每個類c，存在似然度函數(shù)P(d|c)n則，生成類c中的文檔d的概率等于P(d|c) P(c)，而給定文檔d, 類c的(后驗)概率P( | )P( )P( |)P( | )P(

28、 )rd ccc dd rr樸素樸素Bayes模型模型n假設(shè)樣本的各維特征之間是相互獨立的n應(yīng)用在文本分類中，假設(shè)詞匯之間相互獨立n以二值文檔概率模型為例,P(|)(1)c tc ttdt W tddcn為簡化計算，將上式改寫為,P( | )(1)1c tc tt dt Wc td cn上式的第二個乘積與d無關(guān)可以預(yù)先計算n利用樸素Bayes模型需進行參數(shù)平滑，以防零概率事件Bayes網(wǎng)絡(luò)網(wǎng)絡(luò)thechtmlxmlPr(c = mp3) = .Pr(c = sports) = .thechtmlxml.Pr(xml = 1 | c = mp3) = .Pr(xml = 1 | c = spor

29、ts) = .Pr(xml = 1 | html = 1, c = mp3) = .Pr(xml = 1 | html = 1, c = sports) = .Pr(xml = 1 | html = 0, c = mp3) = .Pr(xml = 1 | html = 0, c = sports) = .(a)(b)xXx)(|Pr()Pr(paxP(d|c)不再是所有詞的概率乘積，而成為條件概率的乘積X表示節(jié)點，x表示其取值最大熵原理最大熵原理n最大熵原理：當(dāng)需要對事物進行預(yù)測時，所做的預(yù)測應(yīng)當(dāng)滿足全部已知的條件，而對未知的情況不要做任何主觀假設(shè)(以保證概率分布的信息熵最大)n假設(shè)有訓(xùn)練數(shù)據(jù)

30、(di, ci), i = 1, nnP(c|d)的最大熵模型通過一些反映已知條件的特征函數(shù)來建立。作為最基本的特征函數(shù)，每個特征fj的期望為,()P( , )( , )P( )P( |)( , )jjjd cdcE fd c fd cdc d fd cn假設(shè)訓(xùn)練數(shù)據(jù)無重復(fù)文檔且每個文檔只有一個標(biāo)簽，可獲得如下約束：( ,)P( |)( , )jiiijiiicf d cc d f d c最大熵分類器最大熵分類器n在滿足已知約束條件下利用最大熵原理求解P(c|d)n利用Lagrange乘子法，為對應(yīng)每個特征的約束設(shè)一個Lagrange乘子i，所有乘子構(gòu)成集合，構(gòu)造函數(shù),(P(|),)P() P

31、(|) log P(|)(,)P(|)(,)d cjjiiijijii cGcddcdcdfdccdfdc n通過最大化G，可獲得：1P( |)exp( , )( )jjjc dfd cZ d區(qū)分式分類器區(qū)分式分類器n區(qū)分式分類器不去探究概率分布P(c|d) ，而是直接將文檔特征向量映射為類別標(biāo)簽n例如，一種構(gòu)造區(qū)分式二元分類器的方法是：在特征空間中找到一個向量，使得文檔d的類別標(biāo)簽等于sgn (di + b)n線性最小二乘回歸是獲得上述分類器參數(shù)和b的有效方法n它利用訓(xùn)練數(shù)據(jù)(di, ci), i = 1, n，通過最小化類標(biāo)簽預(yù)測的均方誤差求解參數(shù)，即最小化誤差2() diiibcSVMn

32、基本思想是最大化分類面兩側(cè)的樣本距超平面的最小距離n建立在統(tǒng)計學(xué)習(xí)的結(jié)構(gòu)風(fēng)險最小化原則基礎(chǔ)上n文檔向量空間中線性判別函數(shù)的一般形式為g(d) = d + bn分類面方程為d + b = 0n將判別函數(shù)歸一化，即使離分類面最近的樣本的|g(d)|=1 ，則分類間隔等于2/SVM的優(yōu)化目標(biāo)的優(yōu)化目標(biāo)n使間隔最大等價于使最小n而要求H對所有樣本正確分類，應(yīng)使()11,., d iicbin n引入正的松弛因子i允許錯分樣本的存在，則()11,., d iiicb -in n從而，尋找最優(yōu)分類面問題可表示為如下二次優(yōu)化問題12()11,., d iiiiiMinimizeCsubject tocb -

33、in SVM的求解的求解n利用Lagrange優(yōu)化方法，可將上式的優(yōu)化問題轉(zhuǎn)化為如下對偶問題niandctosubjectccMinimizeiiiijijijijiii,.,1 C0 0 )(21 ,ddn上式的解中，只有少數(shù)i不為零，它們所對應(yīng)的樣本就是支持向量，分類閾值b*可利用最優(yōu)分類面方程通過兩類中任意一對支持向量求得n最終，文檔d的最優(yōu)分類函數(shù)為*( )sgn()d diiiSVf dcb非線性非線性SVMn對于非線性可分的情況，可以用一個非線性映射將樣本映射到高維特征空間中，使之在高維空間中線性可分n文本在高維空間的內(nèi)積為(di) (dj)n問題是能否找到函數(shù)K，使得K(di ,

34、dj) =(di) (dj)，K被稱為核函數(shù)n有了核函數(shù)，非線性SVM的求解就變成,1 (,)2 0 0C 1,.,iijijijii jiiiiMinimizecc Ksubject tocandin d dn最優(yōu)分類函數(shù)變?yōu)?( )sgn()iiSVfc Kbidd ,d常用核函數(shù)常用核函數(shù)n多項式核函數(shù)n徑向基函數(shù)nSigmoid函數(shù)( ,)(1)qjjKd dd d22()( ,)expjjKddd d( ,)tanh( ()jjKvcd dd d特征選擇特征選擇n文本聚類和文本分類都以詞作為基本特征來描述文檔n高維文檔特征不僅帶來高額的運算開銷，而且會產(chǎn)生由訓(xùn)練樣本不足所導(dǎo)致的模型不

35、可靠或失效的問題n特征降維非常重要，特征選擇是方法之一n兩類特征選擇算法u包含算法: 從空集開始選擇越來越多好的特征，直到適當(dāng)為止u排除算法: 從初始特征集開始逐步排除差的特征，直到適當(dāng)為止包含算法包含算法n算法u1) 對每個詞，計算其類區(qū)分性測度u2) 按區(qū)分性測度對詞進行降序排序u3) 保留最好的n個詞作為特征用于表達(dá)文檔n各個詞的類區(qū)分性一般是獨立計算的，因此這類算法具有貪心(greedy)的特點n區(qū)分性測度是關(guān)鍵n常用測度包括2、互信息、Fisher鑒別指數(shù)等2 測度測度n以二類問題為例，設(shè)uk00, k01分別為不包含/包含詞t的類0中文檔數(shù)uk10 , k11分別為不包含/包含詞t

36、的類1中文檔數(shù)un = k00 + k01+ k10+ k11uP(C=0) = (k00+k01) / n n定義n2越大，類與詞之間的相關(guān)性也越大)()()()(00100111000110112011000112kkkkkkkkkkkkn22,()()()()pqtp qtknP Cp P OqnP Cp P Oq互信息互信息n通過互信息計算文檔類與詞之間的相關(guān)性n互信息通過P(x,y)對P(x)P(y)的偏離程度對隨機變量之間的依賴程度進行測量n如果隨機變量X和Y相互獨立，則對于所有的取值x和y P(x,y)/P(x)P(y)=1n因此，定義互信息為P( , )( , )P( , )l

37、ogP( )P( )MIxyx yX Yx yxyFisher鑒別鑒別n以二類學(xué)習(xí)問題為例，令X和Y分別表示一類向量的集合。向量的元素可以是令向量長度歸一的實數(shù)nFisher鑒別在尋找一種映射*，它使得X和Y兩個數(shù)據(jù)集被映射到二者質(zhì)心間的距離相對集合內(nèi)數(shù)據(jù)的展開幅度達(dá)到最大的方向上，即)()(maxarg)(maxarg2*YXTYXTSSJn令S = (SX+SY)/2，當(dāng)S-1存在時， = S-1 (X-Y) 是一個解 Fisher鑒別指數(shù)鑒別指數(shù)nFisher鑒別是一種變換，具有破壞特征稀疏性的特點n將每個詞t都看作為一個候選的方向，即令t = (0,1,0)T，即1只在詞t的位置出現(xiàn)，

38、定義t的Fisher鑒別指數(shù)為tTtYXTttSJt2)()()(FIn由于t的特殊形式，上式可簡化為XYtYttXttYtXyYxXt2,2,2,)(|)| /1 ()(|)| /1 ()()(FIn對于多類問題cDdtctdcccctctcxDt2,2, 12,2, 1)(|)| /1 ()()(FI排除算法排除算法n排除算法從全部詞特征集T開始逐步對“無用”特征進行排除，直至獲得一個滿意的特征子集Fn排除算法的核心思想是盡量保持P(C |T)與P(C|F)的相似性，因為分類與聚類可以基于類(C)的后驗概率分布來設(shè)計算法nP(C |T)與P(C|F)的相似性可用KL距離來度量cTcFcFcTCFCKL)|Pr()|Pr(log)|Pr()|Pr(|)|(Pr(排除算法排除算法n如果P(P=p|Q=q，R=r) = P(P=p|R=r)，則稱P在R條件下獨立于Qn排除算法的核心是尋找類與特征之間的條件獨立關(guān)系n排除算法復(fù)雜度高，優(yōu)點是考慮了特征之間的相關(guān)性特征維數(shù)確認(rèn)特征維數(shù)確認(rèn)nValidation: 取多少維特征最佳n普通確認(rèn)u訓(xùn)練數(shù)據(jù)被分為兩部分，分別用于特征排序和測試n交叉確認(rèn): 留一法(Lea