北郵郭軍2016web搜索第二章

Web搜索

郭軍

北京郵電大學(xué)

第2章文本檢索Web信息采集文本的保存與索引檢索模型網(wǎng)頁(yè)排序查詢重構(gòu)文本聚類文本分類特征選擇特征變換引言文本是最基本、同時(shí)也是最高級(jí)（抽象）的信息媒體文本檢索是Web搜索的起點(diǎn)也是重點(diǎn)文本檢索所涉及的問(wèn)題Web信息的采集與組織文本的表示用戶查詢方法相關(guān)文檔排序文本聚類文本分類Web信息采集Crawler/Spider:利用hyperlink自動(dòng)獲取網(wǎng)頁(yè)的URL利用HTTP進(jìn)行網(wǎng)絡(luò)編程自動(dòng)下載網(wǎng)頁(yè)Crawler的基本原理網(wǎng)頁(yè)采集過(guò)程是一個(gè)從WWW的某網(wǎng)頁(yè)出發(fā)不斷向前漫游的過(guò)程漫游的方向和路線是隨機(jī)的為了將隨機(jī)漫游變成有序的向外擴(kuò)展，必須對(duì)其進(jìn)行有效地控制Crawler的工作進(jìn)程Crawler的工作效率多線程Crawler分布式Crawler:通過(guò)分散在不同地點(diǎn)的服務(wù)器實(shí)現(xiàn)Crawler的難題前沿URL的選擇廣度優(yōu)先/深度優(yōu)先?優(yōu)質(zhì)網(wǎng)頁(yè)優(yōu)先？無(wú)效URL問(wèn)題同一網(wǎng)頁(yè)的多重訪問(wèn)問(wèn)題網(wǎng)頁(yè)的再訪問(wèn)周期問(wèn)題流行度高的網(wǎng)頁(yè)給予高頻訪問(wèn)基于鏈接分析判斷網(wǎng)頁(yè)的活躍度文本的預(yù)處理與保存預(yù)處理網(wǎng)頁(yè)去重:基于消息摘要/鏈接結(jié)構(gòu)網(wǎng)頁(yè)解析:HTML/XML文檔的解析，取出其中的元數(shù)據(jù)、超鏈接、標(biāo)題和文本內(nèi)容文本的保存文本通常以壓縮的形式保存網(wǎng)頁(yè)平均長(zhǎng)度為10KB，壓縮后為2-4KB通用文件系統(tǒng)的存儲(chǔ)塊尺寸為4-8KB網(wǎng)頁(yè)存儲(chǔ)通常采用專門開(kāi)發(fā)的文件系統(tǒng)大型商用搜索引擎需要在全球建立多個(gè)鏡像的文件系統(tǒng)骨干服務(wù)器文本的索引(1/2)建立索引就是制作標(biāo)記來(lái)指示內(nèi)容的位置Web搜索通常情況下是全文搜索，即對(duì)網(wǎng)頁(yè)中包含的所有詞匯都建立索引倒排文件(invertedfile)詞匯表(vocabulary):文本中所有不同詞匯的集合位置表(occurrences):詞匯在文本中出現(xiàn)的地址列表(postinglist)、字地址、詞地址、文檔地址Heaps定律:v~O(Na

)a≈0.5Gb級(jí)文本、Mb級(jí)詞匯查詢步驟:查詢?cè)~匯表位置表文檔或段落文本的索引(2/2)倒排索引的更新—批量更新主索引+新索引(stop-pressindex)新索引(d,t,s)三元組倒排(t,d,s)對(duì)一個(gè)用戶的查詢，主索引反饋文檔集D0，新索引返回文檔集D+和D-，返回給用戶D0∪D+\D-索引壓縮文檔的標(biāo)識(shí)符壓縮:delta編碼索引詞的選取詞標(biāo)識(shí)、去停詞(stopword)、詞干化(stemming)檢索模型文本檢索的本質(zhì)問(wèn)題:用戶需求文本集中最相關(guān)(最切題)的文檔需解決的3個(gè)基本問(wèn)題用戶如何提出需求簡(jiǎn)單、便捷，關(guān)鍵詞的方式相關(guān)文檔如何定義和計(jì)算語(yǔ)法層相關(guān)/語(yǔ)義層相關(guān)檢索結(jié)果如何反饋URL地址清單段落檢索QABoolean模型查詢:由關(guān)鍵詞及邏輯關(guān)系符構(gòu)成的Boolean表達(dá)式文檔:索引詞的集合查詢與文檔相關(guān)的定義:索引詞的集合是否滿足查詢Boolean表達(dá)式二元決策，無(wú)相關(guān)程度的度量人們常常不容易用Boolean表達(dá)式描述查詢用戶往往只是同時(shí)輸入多個(gè)關(guān)鍵詞，隱含地應(yīng)用“與”邏輯VSM用索引詞出現(xiàn)的絕對(duì)或相對(duì)頻度來(lái)表達(dá)文檔和查詢所有m個(gè)不同的索引詞構(gòu)成m維的特征向量文檔dj的特征向量dj=[w1j,w2j,…,wmj]查詢q的特征向量q=[w1q,w2q,…,wmq]計(jì)算q和dj之間相關(guān)性或相似性有多種方法

相關(guān)性計(jì)算余弦相似度相關(guān)系數(shù)索引詞的權(quán)重TF:IDF:TF-IDF:查詢?cè)~的權(quán)重:概率模型(1/2)給定一個(gè)用戶查詢q和一個(gè)文檔dj

，概率模型通過(guò)估計(jì)dj與q的相關(guān)的概率來(lái)判斷二者的相關(guān)性假設(shè)在所有文檔中存在一個(gè)對(duì)應(yīng)q的理想集合R，即R中的文檔都是q的相關(guān)文檔，R之外的文檔都是q的不相關(guān)文檔概率模型計(jì)算幾率比:P(djrelevanttoq)/P(djnon-relevanttoq)在概率模型中，索引詞的權(quán)重變量都是二值的，即wij

∈{0,1}，wiq

∈{0,1}概率模型(2/2)取對(duì)數(shù)后簡(jiǎn)化dj與q的相似性sim(dj,q)被定義為兩個(gè)概率的初始化

返回文檔集合V后的改進(jìn)估計(jì)Bayesian推理網(wǎng)絡(luò)模型節(jié)點(diǎn)對(duì)應(yīng)文檔、檢索詞、概念、查詢等各類實(shí)體每個(gè)節(jié)點(diǎn)v都與一個(gè)隨機(jī)Boolean變量相聯(lián)系，給定父節(jié)點(diǎn)u1,…uk,P(v|u1,…uk)通常采用“或”邏輯，即只要有一個(gè)父節(jié)點(diǎn)的置信邏輯為“真”，則本節(jié)點(diǎn)就為“真”網(wǎng)頁(yè)排序基于文檔與查詢的相關(guān)性的排序基于網(wǎng)頁(yè)質(zhì)量的排序通過(guò)超鏈接分析來(lái)改進(jìn)排序結(jié)果是Web文本檢索與數(shù)據(jù)庫(kù)文本檢索的一個(gè)十分重要的區(qū)別指向一個(gè)網(wǎng)頁(yè)的超鏈接的數(shù)量代表著網(wǎng)頁(yè)的流行度和質(zhì)量?jī)蓚€(gè)網(wǎng)頁(yè)包含較多的相同的鏈接或被相同的網(wǎng)頁(yè)所指向常常意味著它們之間具有某種密切的關(guān)系PageRank模擬用戶在Web上可用Markov鏈建模的網(wǎng)頁(yè)瀏覽行為假設(shè)任意節(jié)點(diǎn)u對(duì)于節(jié)點(diǎn)v都有一條有向路徑，用戶以概率分布p0隨機(jī)地從一個(gè)節(jié)點(diǎn)出發(fā)，pi為i時(shí)刻到達(dá)各節(jié)點(diǎn)的概率令Web鄰接矩陣(圖)為E，如果節(jié)點(diǎn)u和v之間存在超鏈接，則E(u,v)=1，否則為0(Nu是節(jié)點(diǎn)u的出度)令則p將收斂于LT的主特征向量PageRank的完善假設(shè)用戶在Web圖的每個(gè)節(jié)點(diǎn)上將進(jìn)行兩種選擇以概率q隨機(jī)瀏覽Web上的任意一個(gè)網(wǎng)頁(yè)以概率1-q在所有的出鏈接中以均勻概率選擇一個(gè)，繼續(xù)前進(jìn)則PageRank的近似解當(dāng)N很大時(shí)，直接求解改進(jìn)PageRank方程組是困難的簡(jiǎn)單算法是先將p0的所有元素設(shè)為1/N，然后反復(fù)用因子(1-q)LT+q/N1N乘以pi，并將|pi|縮放至1。但此方法不能保證收斂。HITSHITS(HypertextInducedTopicSearch)與PageRank不同，是與查詢相關(guān)的網(wǎng)頁(yè)質(zhì)量評(píng)價(jià)算法收到查詢q后，系統(tǒng)返回一個(gè)網(wǎng)頁(yè)的集合RR中的任意節(jié)點(diǎn)(網(wǎng)頁(yè))指向的節(jié)點(diǎn)和指向R中任意節(jié)點(diǎn)的節(jié)點(diǎn)構(gòu)成集合X，R與X共同構(gòu)成一個(gè)基本集合V構(gòu)造圖G

=(V,E)，E為節(jié)點(diǎn)間的有向鏈接評(píng)價(jià)網(wǎng)頁(yè)的兩個(gè)測(cè)度:a(authority)和h(hub)賦初值a=h=1

迭代，

收斂后，a等于ETE的主特征向量

h等于EET的主特征向量查詢重構(gòu)用戶提出一個(gè)適當(dāng)?shù)牟樵冋?qǐng)求往往是不容易的可將用戶的第一個(gè)查詢看作是初始的嘗試，通過(guò)對(duì)獲得的文檔的相關(guān)分析，對(duì)初始查詢進(jìn)行重構(gòu)查詢重構(gòu)的三類方法基于用戶反饋信息的的方法基于對(duì)初始反饋文檔的局部分析的方法基于對(duì)全部文檔集合的全局分析的方法用戶相關(guān)反饋先將檢索出的文檔清單提交給用戶，用戶查閱后，對(duì)相關(guān)的文檔進(jìn)行標(biāo)記設(shè)D+為用戶標(biāo)記的相關(guān)文檔的集合，D-為反饋文檔中非相關(guān)文檔的集合Rocchio公式α，β和γ都是可調(diào)參數(shù)，簡(jiǎn)單的設(shè)置是令它們都為1

在D-不好確定時(shí)，常令γ為0自動(dòng)局部分析對(duì)于一個(gè)給定的查詢q，稱檢索出來(lái)的文檔集合Dl為局部文檔集合自動(dòng)局部分析從Dl中查找查詢?cè)~的近鄰詞近鄰的測(cè)度關(guān)聯(lián)度近鄰度間接相關(guān)度

或局部語(yǔ)境分析LCA基于由名詞詞組所構(gòu)成的“概念”進(jìn)行查詢擴(kuò)展概念的定義通?；谠~典進(jìn)行步驟:1)將初始查詢檢索出的文檔分割成固定長(zhǎng)度的段落，然后按與查詢的相關(guān)性對(duì)其排序，取出前n個(gè)2)計(jì)算各段落中每個(gè)概念c與查詢q之間的相似度sim(c,q)3)將相似度最大的前m個(gè)概念加到初始查詢之中關(guān)鍵是第二步，選擇一種合適的計(jì)算概念c和查詢q中包含的詞之間的相似度測(cè)度基于概念空間的全局分析尋找整個(gè)查詢的近鄰詞用文本集的所有N個(gè)文檔構(gòu)成一個(gè)概念空間，每個(gè)文檔是空間中的一個(gè)維度無(wú)論是檢索詞還是查詢，都被看作概念空間中的數(shù)據(jù)點(diǎn)，即概念，對(duì)于檢索詞ti(i=1,…,m)，ti=(wi1,…,wiN)，其中而查詢

通過(guò)計(jì)算q與各檢索詞的相關(guān)性進(jìn)行查詢擴(kuò)展基于同義詞辭典的全局分析辭典包含若干同義詞類每個(gè)類由通過(guò)文檔聚類算法獲得的若干檢索詞構(gòu)成采用全鏈接(completelink)的聚類算法，即類對(duì)之間的相似度被定義為所有文檔對(duì)的相似度的最小值Bottom-up的層次聚類通過(guò)設(shè)置以下參數(shù)進(jìn)行同義詞類選擇Tsim:最小類內(nèi)相似度閾值Tnod:類內(nèi)最大文檔數(shù)閾值Tidf:倒文檔頻度閾值文本聚類在文本檢索中的作用非常廣泛和重要聚類一直是模式識(shí)別、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域中的一個(gè)重點(diǎn)課題無(wú)監(jiān)督學(xué)習(xí)(Unsupervisedlearning)目的是找到數(shù)據(jù)集合中潛在(latent)的聚合結(jié)構(gòu)兩大類聚類算法區(qū)分法(discriminativemethod)生成法(generativemethod)區(qū)分式聚類的基本思想給定一個(gè)(文檔)集合D={di|i=1,…,N}其中di=(di1,…,diM)為元素di的VSM定義sim(di,dj)為di和dj之間的相似度聚類問(wèn)題可以定義為:將集合D劃分為k個(gè)子集D1,…Dk，使類內(nèi)的相似度總和S達(dá)到最大區(qū)分式聚類的方式區(qū)分性聚類也稱為分割聚類，核心操作是將集合中的元素排他式地劃歸到某個(gè)類中bottom-up方式初始將每個(gè)文檔作為一類，然后對(duì)最相似的類進(jìn)行合并，直至類別數(shù)目或類內(nèi)相似度達(dá)到設(shè)定值top-down方式先將所有文檔放在一類，然后以增大類內(nèi)相似度為目標(biāo)，對(duì)類進(jìn)行分裂操作，直至類別數(shù)目或類內(nèi)相似度達(dá)到設(shè)定的閾值Bottom-up方式例Top-down方式例層次匯合聚類HAC算法1)令每個(gè)文檔d在一個(gè)單獨(dú)的組中，形成N個(gè)組pipowwx2)令G為這N個(gè)組的集合3)while|G|>1do4)選擇u,v∈G，標(biāo)準(zhǔn)為合并它們將帶來(lái)最大的利益測(cè)度5)將u和v從G中移除6)令w=u∪v7)將w插入G8)endwhile隨著合并次數(shù)的增加，被合并類之間的相似度sim(u,v)會(huì)越來(lái)越低第4步的常用測(cè)度，S(w)的類內(nèi)相似度，w=u∪vk-means聚類給定數(shù)據(jù)集合{x1,…xN},每個(gè)數(shù)據(jù)是一個(gè)d維向量目標(biāo)是把這個(gè)數(shù)據(jù)集合劃分為K個(gè)類(cluster)預(yù)設(shè)K個(gè)類的質(zhì)心μk(k=1,…,K)通過(guò)使下式最小化，迭代新質(zhì)心μk和類別歸屬rnkk-means聚類算法1)初始化k個(gè)組的質(zhì)心向量2)while

還可以繼續(xù)改進(jìn)do3)

for

每個(gè)元素(文檔)d

do4)找出質(zhì)心向量與d最相似的組c5)將d調(diào)整到組c之中6)

endfor7)

for

每個(gè)組c

do8)重新計(jì)算質(zhì)心向量9)

endfor10)endwhile要點(diǎn):預(yù)先確定類別數(shù)為k質(zhì)心與元素都用向量表示k-means聚類示意k-means聚類應(yīng)用軟k-means聚類硬k均值聚類:元素d要么屬于組c，要么不屬于組c，在計(jì)算質(zhì)心時(shí)，組內(nèi)所有元素都具有相同的權(quán)重軟k均值聚類:允許一個(gè)元素部分地分別屬于不同的組，但在計(jì)算組的質(zhì)心時(shí)各個(gè)元素的貢獻(xiàn)不同計(jì)算質(zhì)心的公式基于親和性消息的聚類在k均值聚類中，如果選用樣本數(shù)據(jù)為類中心，則稱為k中心法，稱被選為中心的數(shù)據(jù)為范例(exemplar)，但初始范例選取困難基于消息傳播的聚類方法[Frey07]將所有樣本看作潛在范例，數(shù)據(jù)點(diǎn)通過(guò)已知的相似度被連成網(wǎng)絡(luò)，相鄰節(jié)點(diǎn)通過(guò)反復(fù)地傳遞和修改兩個(gè)消息—responsibility和availability使范例涌現(xiàn)出來(lái)迭代更新a(i,k)和r(i,k)算法基于親和性消息的聚類算法1)輸入數(shù)據(jù)點(diǎn)間的相似度s(i,k)，表示k作為i的范例的適當(dāng)度2)為每個(gè)數(shù)據(jù)點(diǎn)輸入偏愛(ài)度s(k,k)，該值越大k越可能為范例3)將所有可用性消息a(i,k)置為0，

a(i,k)是由k發(fā)給i的一個(gè)累積的“證據(jù)”，來(lái)證明k適合于作為i的范例4)更新依靠性消息r(i,k)，這是由i發(fā)給候選范例k的(通過(guò)與其他候選范例比較的)一個(gè)累積的“證據(jù)”，證明k適于作為i的范例5)按如下規(guī)則分別更新可用性消息a(i,k)和a(k,k)6)對(duì)每個(gè)元素i計(jì)算

，如不滿足終止條件，轉(zhuǎn)4)繼續(xù)迭代生成式聚類每個(gè)文檔類別被看作對(duì)應(yīng)一個(gè)主題的文檔集合將文檔的產(chǎn)生看作隨機(jī)過(guò)程，每個(gè)主題類別有一個(gè)關(guān)于文檔的概率分布模型一個(gè)文檔應(yīng)該歸屬哪個(gè)類，決定于哪個(gè)類別的模型產(chǎn)生該文檔的概率最大關(guān)鍵是各個(gè)類別概率模型的估計(jì)二值概率模型文檔是二值元素的向量，每個(gè)元素對(duì)應(yīng)詞表W中的一個(gè)詞t假設(shè)詞的出現(xiàn)是相互獨(dú)立的事件，且只考慮詞是否出現(xiàn)而不管出現(xiàn)的次數(shù)，則可得在概率參數(shù)集合Φ條件下文檔d生成的二值概率模型由于詞表中的詞數(shù)遠(yuǎn)遠(yuǎn)多于文檔中的詞數(shù)，且的平均值低于0.5，使得該模型有利于短文本的生成，同時(shí)降低了實(shí)際出現(xiàn)可能性大的文檔的產(chǎn)生概率多值概率模型考慮詞在文檔中的出現(xiàn)次數(shù)假設(shè)文檔的總長(zhǎng)度L符合一個(gè)概率分布P(l)文檔的產(chǎn)生過(guò)程是一個(gè)擲|W|個(gè)面的骰子的過(guò)程，每個(gè)面對(duì)應(yīng)詞表中的一個(gè)詞產(chǎn)生長(zhǎng)度為ld的文檔的過(guò)程就等于投擲骰子ld次假設(shè)第t面出現(xiàn)了n(d,t)次，則文檔的生成概率概率模型的參數(shù)估計(jì)假設(shè)要處理的文檔集合共對(duì)應(yīng)m個(gè)話題，產(chǎn)生第i類話題的概率為αi，第i類話題中詞t的產(chǎn)生概率為θi,t將m類話題文檔的所有參數(shù)表示為:獲得多類模型的關(guān)鍵步驟是通過(guò)訓(xùn)練數(shù)據(jù)將模型中的參數(shù)估計(jì)出來(lái)，著名的EM算法可用來(lái)完成這個(gè)參數(shù)估計(jì)基于MLE準(zhǔn)則的參數(shù)估計(jì)為了簡(jiǎn)化描述，假設(shè)每個(gè)類別只有一個(gè)參數(shù)μi，即用x表示文檔，則其生成概率設(shè)有n個(gè)iid樣本構(gòu)成訓(xùn)練集合X={x1,…,xn}，則可根據(jù)MLE準(zhǔn)則通過(guò)對(duì)以下函數(shù)最大化來(lái)估計(jì)參數(shù)ΘEM算法(E步)EM算法的思想：初始值E步/M步迭代尋優(yōu)算法在不知各個(gè)樣本的類別Y={y1,…,yn}的情況下求解先對(duì)Θ給出初始“猜想”值Θ'，令全數(shù)據(jù)似然度Q為X、Y和Θ'條件下logL的期望值

推導(dǎo)可得由于Q是Θ的對(duì)數(shù)似然度在Y的分布上獲得的期望，因此這一步被稱為E步EM算法(M步)怎樣才能在Θ'的基礎(chǔ)上獲得一個(gè)更好的Θ值呢，一種合理的方法是通過(guò)最大化Q來(lái)實(shí)現(xiàn)，這一步被稱為M步Θ中包含α和μ兩類參數(shù)，先以α為例介紹M步的更新算法因?yàn)橛屑s束條件通過(guò)標(biāo)準(zhǔn)的Lagrange優(yōu)化，可得方程組

求解可得EM算法(M步)假設(shè)各類別的概率分布服從均值為μk的Poisson分布

Pr(x|μ)=e-μμx/x!求解可得文本分類分類是最基本最重要的智能活動(dòng)之一模式識(shí)別系統(tǒng)的主要任務(wù)就是構(gòu)造性能優(yōu)良的分類器分類是靠有監(jiān)督的學(xué)習(xí)實(shí)現(xiàn)的，即通過(guò)有類別標(biāo)注的樣本對(duì)分類器進(jìn)行訓(xùn)練在Web搜索中的應(yīng)用網(wǎng)頁(yè)及文檔分類Spam檢測(cè)情感分類在線廣告

k-NN分類器利用k個(gè)與未知樣本最接近的已知樣本的類別來(lái)投票決定未知樣本的類別兩個(gè)步驟:尋找未知樣本的k個(gè)最近鄰(測(cè)度問(wèn)題)利用k近鄰的類別對(duì)未知樣本的類別進(jìn)行投票預(yù)測(cè)只需對(duì)訓(xùn)練樣本進(jìn)行標(biāo)注，不需要進(jìn)行其他訓(xùn)練參數(shù)k的選擇是最大問(wèn)題計(jì)算和存儲(chǔ)開(kāi)銷通常很大Bayes分類器基于Bayes規(guī)則的分類器，理論與應(yīng)用均非常重要假設(shè)每個(gè)文檔只屬于一個(gè)類別，并按如下條件建模每個(gè)類c都有一個(gè)先驗(yàn)概率P(c)對(duì)于每個(gè)類c，存在似然度函數(shù)P(d|c)則，生成類c中的文檔d的概率等于P(d|c)P(c)，而給定文檔d,類c的(后驗(yàn))概率樸素Bayes模型假設(shè)樣本的各維特征之間是相互獨(dú)立的應(yīng)用在文本分類中，假設(shè)詞匯之間相互獨(dú)立以二值文檔概率模型為例為簡(jiǎn)化計(jì)算，將上式改寫(xiě)為上式的第二個(gè)乘積與d無(wú)關(guān)可以預(yù)先計(jì)算利用樸素Bayes模型需進(jìn)行參數(shù)平滑，以防零概率事件Bayes網(wǎng)絡(luò)P(d|c)不再是所有詞的概率乘積，而成為條件概率的乘積X表示節(jié)點(diǎn)，x表示其取值最大熵原理最大熵原理：當(dāng)需要對(duì)事物進(jìn)行預(yù)測(cè)時(shí)，所做的預(yù)測(cè)應(yīng)當(dāng)滿足全部已知的條件，而對(duì)未知的情況不要做任何主觀假設(shè)(以保證概率分布的信息熵最大)假設(shè)有訓(xùn)練數(shù)據(jù){(di,ci),i=1,…,n}P(c|d)的最大熵模型通過(guò)一些反映已知條件的特征函數(shù)來(lái)建立。作為最基本的特征函數(shù)，每個(gè)特征fj的期望為假設(shè)訓(xùn)練數(shù)據(jù)無(wú)重復(fù)文檔且每個(gè)文檔只有一個(gè)標(biāo)簽，可獲得如下約束：最大熵分類器在滿足已知約束條件下利用最大熵原理求解P(c|d)利用Lagrange乘子法，為對(duì)應(yīng)每個(gè)特征的約束設(shè)一個(gè)Lagrange乘子λi，所有乘子構(gòu)成集合Λ，構(gòu)造函數(shù)通過(guò)最大化G，可獲得：區(qū)分式分類器區(qū)分式分類器不去探究概率分布P(c|d)，而是直接將文檔特征向量映射為類別標(biāo)簽例如，一種構(gòu)造區(qū)分式二元分類器的方法是：在特征空間中找到一個(gè)向量α，使得文檔d的類別標(biāo)簽等于sgn(α·di+b)線性最小二乘回歸是獲得上述分類器參數(shù)α和b的有效方法它利用訓(xùn)練數(shù)據(jù){(di,ci),i=1,…,n}，通過(guò)最小化類標(biāo)簽預(yù)測(cè)的均方誤差求解參數(shù)，即最小化誤差SVM基本思想是最大化分類面兩側(cè)的樣本距超平面的最小距離建立在統(tǒng)計(jì)學(xué)習(xí)的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則基礎(chǔ)上文檔向量空間中線性判別函數(shù)的一般形式為g(d)=α·d+b分類面方程為α·d+b=0將判別函數(shù)歸一化，即使離分類面最近的樣本的|g(d)|=1，則分類間隔等于2/‖α‖SVM的優(yōu)化目標(biāo)使間隔最大等價(jià)于使‖α‖最小而要求H對(duì)所有樣本正確分類，應(yīng)使引入正的松弛因子ξi允許錯(cuò)分樣本的存在，則從而，尋找最優(yōu)分類面問(wèn)題可表示為如下二次優(yōu)化問(wèn)題SVM的求解利用Lagrange優(yōu)化方法，可將上式的優(yōu)化問(wèn)題轉(zhuǎn)化為如下對(duì)偶問(wèn)題上式的解中，只有少數(shù)λi不為零，它們所對(duì)應(yīng)的樣本就是支持向量，分類閾值b*可利用最優(yōu)分類面方程通過(guò)兩類中任意一對(duì)支持向量求得最終，文檔d的最優(yōu)分類函數(shù)為非線性SVM對(duì)于非線性可分的情況，可以用一個(gè)非線性映射Φ將樣本映射到高維特征空間中，使之在高維空間中線性可分文本在高維空間的內(nèi)積為Φ(di)·Φ(dj)問(wèn)題是能否找到函數(shù)K，使得K(di,dj)=Φ(di)·Φ(dj)，K被稱為核函數(shù)有了核函數(shù)，非線性SVM的求解就變成最優(yōu)分類函數(shù)變?yōu)槌Ｓ煤撕瘮?shù)多項(xiàng)式核函數(shù)徑向基函數(shù)Sigmoid函數(shù)特征選擇文本聚類和文本分類都以詞作為基本特征來(lái)描述文檔高維文檔特征不僅帶來(lái)高額的運(yùn)算開(kāi)銷，而且會(huì)產(chǎn)生由訓(xùn)練樣本不足所導(dǎo)致的模型不可靠或失效的問(wèn)題特征降維非常重要，特征選擇是方法之一兩類特征選擇算法包含算法:從空集開(kāi)始選擇越來(lái)越多好的特征，直到適當(dāng)為止排除算法:從初始特征集開(kāi)始逐步排除差的特征，直到適當(dāng)為止包含算法算法1)對(duì)每個(gè)詞，計(jì)算其類區(qū)分性測(cè)度2)按區(qū)分性測(cè)度對(duì)詞進(jìn)行降序排序3)保留最好的n個(gè)詞作為特征用于表達(dá)文檔各個(gè)詞的類區(qū)分性一般是獨(dú)立計(jì)算的，因此這類算法具有貪心(greedy)的特點(diǎn)區(qū)分性測(cè)度是關(guān)鍵常用測(cè)度包括χ2、互信息、Fisher鑒別指數(shù)等χ2測(cè)度以二類問(wèn)題為例，設(shè)k00,k01分別為不包含/包含詞t的類0中文檔數(shù)k10

,k11分別為不包含/包含詞t的類1中文檔數(shù)n=k00+k01+k10+k11P(C=0)=(k00+k01)/n…定義χ2越大，類與詞之間的相關(guān)性也越大互信息通過(guò)互信息計(jì)算文檔類與詞之間的相關(guān)性互信息通過(guò)P(x,y)對(duì)P(x)P(y)的偏離程度對(duì)隨機(jī)變量之間的依賴程度進(jìn)行測(cè)量如果隨機(jī)變量X和Y相互獨(dú)立，則對(duì)于所有的取值x和yP(x,y)/P(x)P(y)=1因此，定義互信息為Fisher鑒別以二類學(xué)習(xí)問(wèn)題為例，令X和Y分別表示一類向量的集合。向量的元素可以是令向量長(zhǎng)度歸一的實(shí)數(shù)Fisher鑒別在尋找一種映射α*，它使得X和Y兩個(gè)數(shù)據(jù)集被映射到二者質(zhì)心間的距離相對(duì)集合內(nèi)數(shù)據(jù)的展開(kāi)幅度達(dá)到最大的方向上，即令S=(SX+SY)/2，當(dāng)S-1存在時(shí)，α=S-1(μX-μY)是一個(gè)解

Fisher鑒別指數(shù)Fisher鑒別是一種變換，具有破壞特征稀疏性的特點(diǎn)將每個(gè)詞t都看作為一個(gè)候選的方向，即令

αt=(0,…,1,…,0)T，即1只在詞t的位置出現(xiàn)，定義t的Fisher鑒別指數(shù)為由于αt的特殊形式，上式可簡(jiǎn)化為

對(duì)于多類問(wèn)題

排除算法排除算法從全部詞特征集T開(kāi)始逐步對(duì)“無(wú)用”特征進(jìn)行排除，直至獲得一個(gè)滿意的特征子集F排除算法的核心思想是盡量保持P(C

|T)與P(C|F)的相似性，因?yàn)榉诸惻c聚類可以基于類(C)的后驗(yàn)概率分布來(lái)設(shè)計(jì)算法P(C

|T)與P(C|F)的相似性可用KL距離來(lái)度量排除算法如果P(P=p|Q=q，R=r)=P(P=p|R=r)，則稱P在R條件下獨(dú)立于Q排除算法的核心是尋找類與特征之間的條件獨(dú)立關(guān)系排除算法復(fù)雜度高，優(yōu)點(diǎn)是考慮了特征之間的相關(guān)性特征維數(shù)確認(rèn)Validation:取多少維特征最佳普通確認(rèn)訓(xùn)練數(shù)據(jù)被分為兩部分，分別用于特征排序和測(cè)試交叉確認(rèn):留一法(Leave-One-Out)訓(xùn)練數(shù)據(jù)較少時(shí)使用每次留出一個(gè)樣本用于測(cè)試特征變換通過(guò)數(shù)學(xué)變換對(duì)原始特征進(jìn)行不同的線性或非線性組合，從新產(chǎn)生的組合中挑選好特征本質(zhì)是不同域或空間之間的映射目的是找到能用更低維度“緊湊”地表達(dá)文檔數(shù)據(jù)的空間，同時(shí)，在新空間中，文檔之間仍然保持在原空間的親疏關(guān)系只要能起到特征降維和保持文檔之間原有距離的效果的各種數(shù)學(xué)變換都可應(yīng)用于文檔特征變換Fourier、Wavelet、PCA、LDA、流形分析在文本聚類和分類中，SOM和LSI具有典型意義SOM(Self-OrganizingMap)輸入數(shù)據(jù)并聯(lián)地饋入到一維或二維排列的神經(jīng)元陣列，將多維連續(xù)數(shù)據(jù)空間映射到一維或二維離散數(shù)據(jù)空間神經(jīng)元間的拓?fù)渚嚯x代表使其興奮