第9 根據(jù)內(nèi)容檢索2

會計(jì)學(xué)1第9根據(jù)內(nèi)容檢索2實(shí)際上，LSI采用T維詞條空間中前k個(gè)主成分來近似原始的T維詞條空間，使用N×T的文檔-詞條來估計(jì)這個(gè)方向。主成分方法的直觀解釋是，由原始詞條的加權(quán)組合所構(gòu)成的單個(gè)向量可以非常好的近似由大得多的向量集合所起的效果。于是可以把原來的N×T大小的文檔-詞條矩陣簡化為N×k的矩陣(k<<T)，對于固定的查全率，和前面討論的向量空間方法相比，LSI可以提高查準(zhǔn)率。第1頁/共37頁對表9-2中的矩陣M計(jì)算奇異分解式(SVD)。第2頁/共37頁目標(biāo)是，找一個(gè)分解式M=USVT。式中U是一個(gè)10×6的矩陣，它的每一行是相對特定文檔的權(quán)向量，S是每個(gè)主成分方向特征值的6×6對角陣，6×6的矩陣VT的各列提供了數(shù)據(jù)的新共軛基，被稱為主成分方向。S矩陣的對角線元素是(協(xié)方差矩陣對應(yīng)…):λ1,…,λn={77.4,69.5,22.9,13.5,12.1,4.8}可見，前兩個(gè)主成分捕捉了數(shù)據(jù)中的主要變化，和直覺一致。當(dāng)使用兩個(gè)主成分時(shí)，那么二維表征所保留的變化比例0.925，信息丟失僅7.5%。第3頁/共37頁如果我們在新的二維主成分空間來表示文檔，那么每篇文檔的系數(shù)對應(yīng)于U矩陣的前兩列(兩個(gè)主成分對應(yīng)的特征向量，即新的文檔權(quán)值)：第4頁/共37頁這兩列可看作新的偽詞條，其作用相當(dāng)于原來6個(gè)詞條的線性組合。看一下前兩個(gè)主成分方向可以得到的信息(新共軛基)：V1=(0.74,0.49,0.27,0.28,0.18,0.19)V2=(-0.28,-0.24,-0.12,0.74,0.37,0.31)這兩個(gè)方向是原來6維詞條空間中數(shù)據(jù)最分散(具有最大方差)的方向。每方向更突出前兩個(gè)詞條(查詢,SQL)：實(shí)際上這是描述和數(shù)據(jù)庫有關(guān)文檔的方向。第5頁/共37頁第二方向突出了后三個(gè)詞條—回歸、似然和線性，這是描述和回歸有關(guān)文檔的方向。圖9-4以圖形方式說明了這一點(diǎn)(將上面數(shù)據(jù)用圖表示)。第6頁/共37頁當(dāng)把文檔投影到由前兩個(gè)主成分方向所決定的平面量，兩個(gè)不同組的文檔分布在兩個(gè)不同的方向上。注意文檔2幾乎落在文檔1上，使其有點(diǎn)模糊。文檔5和文檔10的詞條向量最大，因此離原最遠(yuǎn)。從圖可看出，文檔間的角度差異顯然是相似性的一個(gè)有用指標(biāo)，因?yàn)榛貧w和數(shù)據(jù)庫文檔在平面上是圍繞兩個(gè)不同的角度聚成簇的。主成分方法的應(yīng)用例子：考慮一個(gè)新的文檔D1，詞條“查詢”在該文檔第7頁/共37頁中出現(xiàn)50次，另一個(gè)文檔D2，包含詞條“SQL”50次，兩且兩篇文檔都不包含其他的詞條。如果直接使用關(guān)鍵字表示，這兩個(gè)文檔不會被認(rèn)為是相似的，因?yàn)樗鼈儧]有包含相同的詞條。然而，如果使用兩個(gè)主成分詞條來表示這兩篇文檔，并把它們投影到這個(gè)空間中，那么正如圖9-3所示，二者都被投影到“數(shù)據(jù)庫”方向，盡管它們都僅包含和數(shù)據(jù)庫有關(guān)的三個(gè)詞條中的一個(gè)。第8頁/共37頁從計(jì)算的角度來看，直接計(jì)算主成分向量(例如求解相關(guān)矩陣或協(xié)方差矩陣的特征值)通常要么是計(jì)算上不可行，要么是數(shù)值上不穩(wěn)定。實(shí)踐中，可以使用特別適合高維稀疏矩陣的SVD技術(shù)來估計(jì)PCA向量。第9頁/共37頁四、文檔和文本分類上面的討論可以看出使用詞條向量來表示文檔為文檔分類提供了一種自然框架。有了這一框架對于預(yù)先有標(biāo)簽的文檔我們可以使用有指導(dǎo)分類技術(shù)，對于沒有標(biāo)簽的文檔我們可以使用無指導(dǎo)學(xué)習(xí)(聚類)框架。典型詞條向量的維數(shù)都是非常高的，基于這一事實(shí)，高維空間中的準(zhǔn)確性和高效性通常是選擇分類器的首要標(biāo)準(zhǔn)。第10頁/共37頁對于文檔表示來說，像一階貝葉斯分類器這樣的分類模型或者是加權(quán)線性組合可工作得很好。在文檔分類這一領(lǐng)域還有很多有趣的問題可以探討，例如認(rèn)為每篇文檔屬于多個(gè)主題(類)而不是僅屬于某個(gè)類是有意義的。因此在分類時(shí)不再限于各個(gè)類是相互排斥的這一通用框架。一種簡單的方法是為每個(gè)類分別訓(xùn)練一個(gè)二值分類器，此方法僅當(dāng)類別總數(shù)較少時(shí)是可行的。第11頁/共37頁9.4對個(gè)人偏好建模一、相關(guān)性反饋文本檢索系統(tǒng)比其他數(shù)據(jù)挖掘算法更具有交互性。特別是，提出特定查詢Q的用戶可能愿意反復(fù)使用算法進(jìn)行一系列不同的檢索嘗試，并通過為返回的文檔標(biāo)記出相關(guān)與否來給算法提供用戶反饋。在這方面，Rocchio算法應(yīng)用的特別廣泛。算法的基本思想：第12頁/共37頁從根本上講相關(guān)性是以用戶為中心的，也就是，如果用戶可以(理論上)看到所有的文檔，那么原則上他可以把所有文檔分成兩個(gè)集合，相關(guān)的R和不相關(guān)的NR。如果給定了這兩個(gè)集合，那么可以證明最佳查詢(利用向量模型)為：其中D代表文檔的詞條向量表示，它的標(biāo)簽(用戶作出的)是已知的。第13頁/共37頁在實(shí)際應(yīng)用中，一般一個(gè)用戶不會把數(shù)據(jù)庫中所有文檔都標(biāo)上分類標(biāo)簽。相反，用戶是從一個(gè)特定查詢Qcurrent開始的，可以把這個(gè)查詢看作是相對Qoptimal次優(yōu)的。算法使用這個(gè)初始查詢返回文檔的一個(gè)較小子集，然后用戶把該子集的文檔標(biāo)記為相關(guān)R’和不相關(guān)NR’。Rocchio算法按下面的方式來提煉查詢：第14頁/共37頁該算法使查詢朝著相關(guān)文檔的均值向量靠近，并遠(yuǎn)離不相關(guān)文檔的均值向量。參數(shù)α、β和γ是正的常數(shù)(啟發(fā)式選取)，它們控制著新查詢對最近標(biāo)記文檔的敏感性(相對于當(dāng)前查詢向量Qcurrent)。不斷重復(fù)這個(gè)過程，把新的查詢Qnew與文檔集合進(jìn)行匹配，然后讓用戶再一次標(biāo)記文檔。原則上講，如果每一次迭代所作的標(biāo)簽是一致的，那么Qnew會逐步逼近Qoptimal。第15頁/共37頁實(shí)驗(yàn)證據(jù)表明，利用用戶反饋確實(shí)提高了查準(zhǔn)率-查全率性能。然而，在實(shí)際應(yīng)用時(shí)還有一些細(xì)節(jié)問題需要確定，比如顯示給讀者的文檔數(shù)量；使用的相關(guān)文檔和非相關(guān)文檔的相對數(shù)量；選取非相關(guān)文檔的方法等等。二、自動推薦系統(tǒng)第16頁/共37頁9.5圖像檢索隨著圖像和視頻數(shù)據(jù)集合在的不斷增加，人們對圖像檢索的興趣也日益濃厚。手工對圖像進(jìn)行注釋具有浪費(fèi)時(shí)間、主觀性強(qiáng)等缺點(diǎn)，而且可能因?yàn)樽⑨屨叩目捶ú煌鴣G失圖像的某些特征。一幅圖像可能要使用一千個(gè)詞來描述,但是到底使用哪一千個(gè)單詞卻不是簡單的問題.第17頁/共37頁因此，開發(fā)高效而又準(zhǔn)確的算法來根據(jù)內(nèi)容對圖像數(shù)據(jù)庫進(jìn)行查詢是很有必要的。比如，檢索系統(tǒng)允許用戶提交這樣的查詢“找出和這幅圖像最相近的K幅圖像”或者“找出和這組圖像屬性最匹配的K幅圖像”。一、圖像理解圖像數(shù)據(jù)查詢是非常困難的任務(wù)。從某種意義上來說尋找彼此相似的圖像等價(jià)于求解圖像理解問題，也就是從圖像數(shù)據(jù)中抽取語義信息。第18頁/共37頁在這方面人類非常出色，然而，關(guān)于模式識別和計(jì)算機(jī)視覺的幾十年研究已經(jīng)表明，要用計(jì)算機(jī)算法來“復(fù)制”人類在視覺理解和識別方面的能力是極端困難的。舉例來說，嬰兒可以很快學(xué)會要任何背景下辨別各種動物，比如各種大小、顏色、體型的狗，而這種完全無約束的識別問題超出了目前任何視覺算法的能力。因此，目前的大多數(shù)圖像檢索算法還僅依賴于相當(dāng)?shù)图壍目梢曁崾尽５?9頁/共37頁二、圖像表示為了便于檢索，可以把原始的像素?cái)?shù)據(jù)抽象為特征表示，通常是以類似色彩和紋理這樣的原語來表示圖像特征。類似于文本表達(dá)方式，仍然采用數(shù)據(jù)矩陣格式來表示圖像，每一行代表一幅特定的圖像；每一列代表一個(gè)圖像特征。這樣的特征表示通常比直接的象素測量值對縮放和平移變化更有效。第20頁/共37頁原始的像素?cái)?shù)據(jù)被簡化為標(biāo)準(zhǔn)的N×p數(shù)據(jù)矩陣，在這個(gè)矩陣中每一幅圖像被表示為特征空間中的一個(gè)p維向量。通過計(jì)算圖像局部化子區(qū)域的特征可以粗略的引入空間信息。例如，我們可以計(jì)算一幅1024×1024像素圖像的每個(gè)32×32子區(qū)域的顏色信息。這樣便可以在圖像查詢中使用粗略的空間約束，比如“尋找中央主要為紅色，四周為藍(lán)色的圖像”。第21頁/共37頁應(yīng)用于圖像的根據(jù)內(nèi)容檢索系統(tǒng)的一個(gè)著名商業(yè)實(shí)例是IBM開發(fā)的根據(jù)圖像內(nèi)容查詢(QBIC)系統(tǒng)。該系統(tǒng)允許用戶交互式的查詢圖像和視頻數(shù)據(jù)，查詢的依據(jù)可以是圖像實(shí)例、用戶輸入的草圖、顏色和紋理模式、對象屬性等等。允許對景物、對象以及視頻幀序列或者是這些的任意組合進(jìn)行查詢。第22頁/共37頁QBIC系統(tǒng)使用了多種特征以及多種和距離有關(guān)的尺度用于檢索：

相對整幅圖像進(jìn)行空間平均的三維顏色特征向量，采用歐氏距離尺度。

K-維顏色直方圖，直方圖的柱位可以使用像使用K-平均這樣的基于劃分聚類算法來選取。采用馬氏(Mahalanobis)距離尺度來表征顏色相關(guān)性。

衡量粒度/比例、方向性和對比度特征的三維紋理向量。采用加權(quán)的歐氏距離尺度來計(jì)算距離，權(quán)的缺省值為各個(gè)特征方差的倒數(shù)。第23頁/共37頁

20-維的對象形狀特征，比如區(qū)域、圓度、離心率、軸方向、各種矩等等。采用歐氏距離來計(jì)算相似性。三、圖像查詢和文本數(shù)據(jù)的情況相同，用于抽象表示圖像的方法決定了支持何種類型的查詢和檢索操作。特征表示提供了一種表示查詢的語言。有兩種形式來表示查詢。一種方法：通過樣例查詢，在這種樣例中，我們既可以為要尋找的目標(biāo)提供一個(gè)圖像樣例，也可以勾畫出感興趣圖像的形狀。第24頁/共37頁接下來便計(jì)算樣例圖像的特征向量，然后再把計(jì)算出的查詢特征向量和數(shù)據(jù)庫中預(yù)先計(jì)算出的特征向量進(jìn)行匹配。另一種方法：直接以特征表征表達(dá)查詢，比如“尋找這樣的圖像，50%的區(qū)域?yàn)榧t色，并且包含具有特定方向和粒度特征的紋理”。表示圖像和查詢的特征向量形式與用于文本檢索的向量空間表示非常相似。一個(gè)主要差異是圖像特征通常是一個(gè)實(shí)數(shù)，而詞條向量中的詞條分量通常是某種形式的加權(quán)計(jì)數(shù)，代表了這個(gè)詞條在文檔中出現(xiàn)的頻繁程度。第25頁/共37頁不過，這兩種問題都是根據(jù)內(nèi)容檢索的問題，這一共同特征決定了用于文本檢索的很多技術(shù)也適應(yīng)于圖像檢索應(yīng)用。第26頁/共37頁9.6時(shí)間序列和序列檢索在時(shí)間序列和序列數(shù)據(jù)集合中高效而又準(zhǔn)確的定位有意義模式的問題對于很多應(yīng)用都有重要意義，比如復(fù)雜系統(tǒng)的診斷和監(jiān)控、生物醫(yī)學(xué)數(shù)據(jù)分析以及對科研和商業(yè)時(shí)間序列的探索性數(shù)據(jù)分析。這樣例子包括：

找出這樣的顧客：他們相對時(shí)間的消費(fèi)模式和給定的消費(fèi)特征相似；

在復(fù)雜的實(shí)時(shí)監(jiān)控和故障診斷系統(tǒng)中，搜索出與當(dāng)前異常傳感器信號相似的以前實(shí)例；

在蛋白質(zhì)序列中進(jìn)行有噪聲子串的匹配。第27頁/共37頁和二維圖像數(shù)據(jù)相比，可以把序列數(shù)據(jù)看作是一維的。時(shí)間序列數(shù)據(jù)是相對時(shí)間測量出來的一系列觀察結(jié)果，因此可以用時(shí)間變量t來索引觀察值。序列數(shù)據(jù)的概念比時(shí)間序列數(shù)據(jù)的概念更廣，因?yàn)樾蛄袛?shù)據(jù)不一定是時(shí)間的函數(shù)。例如，在計(jì)算生物學(xué)中，蛋白質(zhì)是以其在蛋白質(zhì)序列中的順序位置來索引的。第28頁/共37頁一、時(shí)間序列數(shù)據(jù)的全局模型傳統(tǒng)的時(shí)間序列建模技術(shù)(比如統(tǒng)計(jì)方法)主要是建立在全局線性模型基礎(chǔ)上的，典型的例子是Box-Jenkins自回歸模型族，該方法把當(dāng)前值y(t)模擬成過去值y(t-k)的加權(quán)線性組合，再加上一個(gè)額外的噪聲項(xiàng)：式中αi是加權(quán)系數(shù)，e(t)是時(shí)間t的噪聲(通常被假定為均值為零的高斯函數(shù))。第29頁/共37頁Box-Jenkins方法的一個(gè)重要貢獻(xiàn)是，如果在時(shí)間序列中存在可識別的系統(tǒng)性非平穩(wěn)分量(比如某種趨勢)，那么很多情況下可以把這個(gè)不平穩(wěn)分量刪除使這個(gè)時(shí)間序列變成平穩(wěn)的形式。例如，像國內(nèi)生產(chǎn)總值和道瓊斯指數(shù)這樣的經(jīng)濟(jì)指標(biāo)中包含著固有的上升趨勢(總體而言)，通常要在建模前將這種趨勢刪除。對于非平穩(wěn)性比較復(fù)雜的情況，另一種有用方法是假定這個(gè)信號是相對時(shí)間局部平穩(wěn)的。第30頁/共37頁非線性的全局模型對上面公式進(jìn)行了推廣，比如可以允許y(t)非線性地依賴過去值：其中g(shù)(.)是非線性的。從數(shù)據(jù)挖掘的角度來看，如果我們假定這樣的全局模型充分地描述了潛在的時(shí)間序列，那么我們就可以使用模型參數(shù)(比如上面的各個(gè)權(quán))作為表示數(shù)據(jù)的基礎(chǔ)，而不使用原始數(shù)據(jù)本身。第31頁/共37頁通過把時(shí)間序列表示為參數(shù)向量，把序列問題轉(zhuǎn)化為本章前面所介紹的文本和圖像的方法，便可以在參數(shù)向量空間中定義相似性尺度、在這個(gè)空間中定義根據(jù)內(nèi)容檢索的查詢。二、時(shí)間序列的結(jié)構(gòu)和形狀考慮一個(gè)實(shí)數(shù)值時(shí)間序列的子序列Q=[q(t),…q(t+m)]，和一個(gè)長得多的歸檔時(shí)間序列X=[x(t),…,x(T)]，前者稱為查詢序列。第32頁/共37頁我們的目標(biāo)是在X中找到和Q最相似的一個(gè)子序列?，F(xiàn)實(shí)情況下，X可能是由許多單個(gè)的時(shí)間序列組成的，但是為了簡單，我們假定它們已經(jīng)被合成一條長的序列。并且假定X和Q都是使用相同采用時(shí)間間隔測量的。上一節(jié)所講的一般方法僅描述一個(gè)時(shí)間序列的全局特征，根本沒有提供對局部形狀的描述，比如峰值等。通常