大規模內容計算
王 斌 許洪波
摘要 網(wǎng)絡(luò )信息內容安全和智能內容管理是信息時(shí)代迫切而又長(cháng)期的重要需求。大規模內容計算是解決這些需求的一系列關(guān)鍵支撐技術(shù)的總稱(chēng)。本文主要介紹了大規模內容計算的相關(guān)背景、概念、技術(shù)、應用和發(fā)展前景。
關(guān)鍵詞：大規模內容計算 內容管理 信息處理 信息檢索 文本挖掘
1.1 1 引言
隨著(zhù)全球信息網(wǎng)絡(luò )的普及和信息化進(jìn)程的推進(jìn)，互聯(lián)網(wǎng)（Internet）信息數量巨大、良莠并存。一方面，從這些數據中高性能、高準確度地獲取所需內容早已成為服務(wù)社會(huì )、培育新興媒體的重要需求，于是，搜索引擎、信息Agent、垃圾郵件過(guò)濾等工具應運而生。不僅如此，上述需求逐漸成為不同政治、軍事力量甚至國家之間占領(lǐng)網(wǎng)上信息制高點(diǎn)和主動(dòng)權的舉足輕重的、迫切而又長(cháng)期的需求，信息安全特別是網(wǎng)絡(luò )信息內容安全受到各國政府的高度重視。美國、日本、法國等發(fā)達國家已把網(wǎng)絡(luò )信息內容安全列為國家重點(diǎn)發(fā)展規劃，投入了巨大的力量。近年來(lái)，我國也逐漸加大信息內容安全的投入力度。另一方面，如何有效地利用信息內容、對這些內容進(jìn)行智能化管理，也是信息社會(huì )提出的一項重要需求，科學(xué)院已經(jīng)把智能內容管理作為信息技術(shù)研究的重要方向進(jìn)行規劃，數字圖書(shū)館、電子政務(wù)、科技奧運等一系列重要任務(wù)都對智能內容管理提出了更高要求。
不論是網(wǎng)絡(luò )信息內容安全還是智能內容管理，都可以看成信息內容處理技術(shù)在網(wǎng)絡(luò )上的應用。比起傳統的信息處理來(lái)，網(wǎng)上的信息處理具有如下的特點(diǎn)：（一）所處理的信息內容規模極大，更新變化異常迅速；（二）信息來(lái)源、格式、載體和相互關(guān)聯(lián)多樣化，地理上、內容上的分布散亂無(wú)序；（三）同時(shí)訪(fǎng)問(wèn)的用戶(hù)數目巨大，用戶(hù)的信息需求多樣化。核心的問(wèn)題是要以Internet上的TB甚至PB級（1PB≈103TB≈1015字節）超大規模數據為基礎面向需求各異的用戶(hù)群實(shí)現高性能、高準確度的信息服務(wù)。
大規模內容計算是解決這個(gè)核心問(wèn)題的一系列關(guān)鍵技術(shù)的總稱(chēng)。具體地說(shuō)，大規模內容計算是在大規模的網(wǎng)絡(luò )信息環(huán)境下，研究與網(wǎng)絡(luò )信息內容的獲取、處理和服務(wù)相關(guān)的高性能計算模型、關(guān)鍵技術(shù)和關(guān)鍵算法的一門(mén)重要學(xué)科。所謂“大規?！?，主要是指它的處理對象數量規模巨大，基本在TB甚至PB的數量級。所謂“內容”，主要是指非結構化的或者半結構化的數據。包括文本數據和多媒體數據。所謂“計算”，當然是一種廣義的“處理”。單純以獲取、檢索、挖掘、過(guò)濾、分類(lèi)、聚類(lèi)、管理、跟蹤、理解、問(wèn)答等范疇來(lái)概括這個(gè)研究方向，都具有很大的局限性，只有用“計算”的概念才能從更高的高度覆蓋這個(gè)研究方向[1]。
大規模內容計算總體上包括如下步驟（參見(jiàn)圖1）：第一步是對大規模信息的獲取，即得到信息；第二步是對信息內容的分析、加工和處理；第三步是利用分析處理的信息提供服務(wù)。本文將主要以文本為處理對象，介紹大規模內容計算的相關(guān)技術(shù)和應用?；谖谋咎幚淼暮芏嗨枷胪瑯涌梢杂糜诙嗝襟w處理。另外，本文的對象是已經(jīng)數字化的文本內容。多媒體處理、書(shū)面或者手寫(xiě)信息的數字化過(guò)程等內容可參見(jiàn)相關(guān)文獻[2]。
本文的后續內容安排如下：第二節介紹信息獲取的相關(guān)技術(shù)；第三節到第四節主要介紹內容分析處理的相關(guān)技術(shù)；第五到第六節主要介紹大規模內容計算的兩個(gè)典型應用。最后是總結和展望。需要說(shuō)明的是，本文的典型應用（檢索和過(guò)濾）也常常被稱(chēng)為技術(shù)。它們和本文前面章節介紹的技術(shù)可以從單項和組合這個(gè)方面加以區分，本文所講的技術(shù)基本上是單項技術(shù)，即不太容易拆分或者一般不再拆分的基礎技術(shù)，而典型應用對應的技術(shù)都是多項單項技術(shù)的組合應用，在這個(gè)意義上，本文將組合后的技術(shù)稱(chēng)為應用。
圖1 大規模內容計算流程
1.2 2 信息獲取技術(shù)
信息獲取是指從網(wǎng)絡(luò )收集數據的過(guò)程。它是進(jìn)行后續信息處理、信息服務(wù)的基礎。如何快速、準確地獲取所需要的信息，是信息獲取研究的主要內容。在大規模內容計算中，信息獲取分為主動(dòng)獲取和被動(dòng)獲取。被動(dòng)獲取通常是將設備介入網(wǎng)絡(luò )的特定部位進(jìn)行獲取。而主動(dòng)獲取主要是指基于WEB（萬(wàn)維網(wǎng)-World Wide WEB）的信息采集（WEB Crawling, 簡(jiǎn)稱(chēng)WC），即根據WEB協(xié)議，直接從WEB上采集或下載信息。本文主要介紹WEB信息采集技術(shù)。
WEB信息采集技術(shù)可以分成[3]：基于整個(gè)WEB的信息采集（Scalable WC），增量式WEB信息采集（Incremental WC），基于主題的WEB信息采集（Focused WC），基于用戶(hù)個(gè)性化的WEB信息采集（Customized WC），基于A(yíng)gent的信息采集（Agent-based WC），遷移的信息采集（Relocatable WC）等等。實(shí)際系統往往是以上幾個(gè)采集技術(shù)的組合。
采集系統主要研究的是：如何高效穩定地以較小的代價(jià)獲取最相關(guān)的信息。為了提高采集速度，大規模的采集系統往往采用并行采集結構。如Google、百度、天網(wǎng)等搜索引擎后臺都采用了并行體系結構。這些體系結構的基本想法都是將采集的各個(gè)部分（控制、分析、執行、存儲）設計成并行流水結構，盡量減少采集系統的不合理等待、保證采集過(guò)程的通暢。
為了降低采集的空間代價(jià)，更新策略是研究的重點(diǎn)之一。最理想的是采集系統能夠自動(dòng)學(xué)到每個(gè)網(wǎng)站或站點(diǎn)的更新規律，從而能夠指導采集器的刷新策略，盡量做到?jīng)]有變化的網(wǎng)頁(yè)不采集，只采集那些更新的網(wǎng)頁(yè)?，F實(shí)的搜索引擎采集系統，都或多或少地采用了更新策略，避免重復性的采集。一種方法是通過(guò)統計不同類(lèi)型站點(diǎn)的更新周期來(lái)指導采集。而IBM設計完成的信息采集器WEBFountain則采用了一個(gè)優(yōu)化模型來(lái)控制采集策略。這個(gè)模型沒(méi)有對WEB頁(yè)面變化的統計行為做任何假設，而是采用了一種適應性的方法，根據先前采集周期里采集到的結果的實(shí)際變化率進(jìn)行調整。
基于主題的信息采集是主要針對相關(guān)主題的采集，目前是采集研究的熱點(diǎn)之一。只采集相關(guān)的信息也可以降低采集的代價(jià)?；谥黝}的采集的關(guān)鍵是采集結果和主題的相似度計算。一方面，可以通過(guò)采集結果與主題的內容相似度來(lái)計算該值；另一方面，可以通過(guò)相關(guān)鏈接信息（如錨文本anchor text、鏈接關(guān)系）來(lái)預測待采集結果的相似度，從而指導采集的方向。Aggarwal則提出了一種針對兩個(gè)假設的基于主題的WEB信息采集方法：一是Linkage Locality，即被相關(guān)于某一主題的頁(yè)面鏈接到的頁(yè)面趨向于擁有同一主題。 二是Sibling Locality，即對于某個(gè)鏈接到某主題的頁(yè)面，它所鏈接到的其它頁(yè)面也趨向于擁有這個(gè)主題。Menczer則評價(jià)了三種關(guān)于基于主題采集的策略 ：Best first Crawler（通過(guò)計算鏈接所在頁(yè)面與主題的相似度來(lái)得到采集優(yōu)先級）、PageRank（通過(guò)每25頁(yè)計算一遍PageRank值來(lái)得到采集優(yōu)先級，PageRank值計算方法參見(jiàn)第五節）以及InfoSpiders（通過(guò)鏈接周?chē)奈淖?，利用神?jīng)網(wǎng)絡(luò )和遺傳算法來(lái)得到采集優(yōu)先級）。
由于使用采集的用戶(hù)需求各異，一些采集系統的設計者把目光投向了基于用戶(hù)個(gè)性化的WEB信息采集（Customized WEB Crawling）?；趥€(gè)性化的信息采集的目標就是只采集用戶(hù)感興趣的信息。它與基于主題的采集的不同之處在于它針對某個(gè)用戶(hù)而不是某個(gè)主題。即使對同一主題，個(gè)性化的信息采集系統對不同用戶(hù)也可能返回不同結果。個(gè)性化信息采集主要是對用戶(hù)的行為（包括瀏覽習慣、興趣等）進(jìn)行跟蹤從而指導采集的進(jìn)行?？▋然仿〈髮W(xué)（CMU）研制的SPHINX是一個(gè)Java工具包組成的環(huán)境交互式信息采集器，它是一個(gè)典型的個(gè)性化信息采集系統。
另外，還有將智能Agent和采集技術(shù)相結合的信息采集技術(shù)以及將采集放在服務(wù)器端進(jìn)行的遷移式采集技術(shù)等等。限于篇幅，這里不再一一介紹。
1.3 3 內容分析技術(shù)
從網(wǎng)上獲取數據以后，要對這些數據進(jìn)行包括格式分析和轉換、編碼識別和轉換、內容意義分析等等相關(guān)的處理。本文只介紹基于自然語(yǔ)言文本的分析技術(shù)。當然，自然語(yǔ)言處理本身就是一個(gè)重要的研究方向，內容包羅萬(wàn)象?？梢哉f(shuō)，任何自然語(yǔ)言處理的技術(shù)都可以用于大規模內容計算?？紤]到篇幅關(guān)系，這里只對幾種最基礎、與大規模內容計算最相關(guān)的自然語(yǔ)言處理技術(shù)進(jìn)行介紹。
文本的內容分析主要包括詞法分析、句法分析、語(yǔ)義分析和語(yǔ)用分析等部分[4]。內容分析是實(shí)現網(wǎng)絡(luò )內容安全和內容管理的基礎算法。大規模內容計算的絕大多數應用都會(huì )用到內容分析技術(shù)，如垃圾郵件的內容特征分析、文本的自動(dòng)摘要、重要事件的發(fā)現和跟蹤等等。
1.3.1 3.1 詞法分析
詞法分析是對自然語(yǔ)言的形態(tài)進(jìn)行分析，判定詞的結構、類(lèi)別和性質(zhì)的過(guò)程。對于以英文為代表的形態(tài)豐富的語(yǔ)言來(lái)說(shuō)，英文的詞法分析的一個(gè)重要過(guò)程是形態(tài)分析，即將英文詞還原成詞干。而漢語(yǔ)形態(tài)變化很少，其主要的問(wèn)題在于書(shū)寫(xiě)時(shí)詞與詞之間沒(méi)有空格。所以通常中文詞法分析的第一步是分詞。分詞往往是后續進(jìn)一步處理的基礎。詞法分析的另一個(gè)主要任務(wù)是標注每個(gè)詞在上下文句子中的詞性。
3.1.1 英文形態(tài)分析
英語(yǔ)的詞常常由前綴、詞根、后綴等部分組成。具體到句子中，詞還有性、數、格以及時(shí)態(tài)引起的詞形變化。英文的形態(tài)分析的主要目標是將句子中的詞從詞形還原到詞甚至詞根。英文的形態(tài)分析常常也稱(chēng)為stemming，分析器稱(chēng)為stemmer。形態(tài)分析常常采用基于自動(dòng)機的規則方法，即將詞形變化的規律總結成規則，然后通過(guò)自動(dòng)機的方法對詞形進(jìn)行轉換。轉換的過(guò)程當中可使用或者不使用詞典。目前使用最廣泛的Stemmer是Martin Porter提出的Porter Stemmer。相對而言，英文形態(tài)分析比較簡(jiǎn)單。以使用最廣泛的Porter為例，它僅僅使用了一組規則，連詞典都沒(méi)有用上。但是，要做一個(gè)百分之百正確的形態(tài)分析工具也是非常困難的，需要用到詞性分析、句法分析甚至語(yǔ)義分析的信息。好在，很多應用對stemmer的要求不是很高，利用不同stemmer的應用結果也相差不大。有些應用（如TREC評測會(huì )議中的Home Page Finding任務(wù)）中詞形信息很重要，不需要stemmer進(jìn)行詞根還原。
3.1.2 中文分詞技術(shù)
目前的中文分詞方法[5]可以總結為兩大類(lèi)：基于機械匹配的分詞方法及基于概率統計的分詞方法。前者通過(guò)對已有詞典的機械匹配來(lái)得到分詞結果。后者不需要任何詞典就可以得到分詞結果，或者對粗切分結果進(jìn)行基于概率統計的后處理來(lái)得到最終的分詞結果。所謂機械匹配是指與已有詞典里的詞進(jìn)行一一匹配，匹配上的詞輸出到結果，匹配不上的詞常常以單字的形式輸出。中文分詞技術(shù)面臨的兩個(gè)最大問(wèn)題是切分歧義和未定義詞問(wèn)題。前者要解決在上下文環(huán)境下不同切分結果的選擇；后者要解決詞典中未收錄詞（如人名、地名、機構名等）的識別?？梢栽跈C械匹配的基礎上通過(guò)規則的方法來(lái)求解上述兩個(gè)問(wèn)題。然而規則方法很難窮盡真實(shí)文本的各種現象。目前比較主流的方法是通過(guò)對真實(shí)文本的概率統計來(lái)求解切分歧義和未定義詞問(wèn)題。包括北航、北師大、清華大學(xué)、北京大學(xué)、北工大、哈工大、東北大學(xué)、山西大學(xué)、中科院計算所等等在內的多家單位都進(jìn)行了中文分詞的研究，包括N元語(yǔ)言模型、隱馬爾可夫模型以及多種統計量等等都被引入到中文分詞，促進(jìn)了中文分詞結果準確率的提高。值得一提的是，一些研究（如微軟研究院）將中文分詞的一部分歧義問(wèn)題延到后續句法分析階段利用更加豐富的信息加以解決并進(jìn)行反饋，實(shí)現了基于這一新思路的分詞系統。
中文分詞的一個(gè)巨大非技術(shù)障礙乃是分詞規范和標準問(wèn)題。雖然中文分詞已經(jīng)有很多年的研究歷史，但是迄今為止國內仍沒(méi)有一個(gè)公開(kāi)的、受到廣泛認可的、可操作的分詞規范，也不存在一個(gè)通用的大規模評測語(yǔ)料。這使得眾多研究者的研究結果之間缺乏真正的可比性，從而制約了中文分詞技術(shù)的提高。能夠真正公開(kāi)為大眾所用的較好的分詞工具很少。目前，ACL（國際計算語(yǔ)言學(xué)協(xié)會(huì )）的SIGHAN分會(huì )已經(jīng)在這方面進(jìn)行了初步嘗試，并于2003年組織了國際第一次漢語(yǔ)分詞評測，吸引了國內外10多家研究單位參加，應該受到中文分詞研究者的廣泛注意。另外，值得一提的是，中科院計算所的ICTCLAS分詞系統[15]可供公開(kāi)測試和開(kāi)放源碼下載使用，目前已經(jīng)引起了較大反響，在分詞工具可用化方面做出了重要的探索。
3.1.3 詞性標注技術(shù)
詞性標注的根本性原因在于詞的兼類(lèi)現象，即一個(gè)詞可以有多個(gè)詞性，但在相關(guān)的上下文中，一個(gè)詞通常只能表現為一個(gè)詞性。詞性標注的目的就是多里挑一。
詞性標注也經(jīng)過(guò)了從規則方法到統計方法的過(guò)程。國外二十世紀60年代就開(kāi)始自動(dòng)詞性標注的研究。其中，1971年，美國B(niǎo)rown大學(xué)的TAGGIT系統利用3300條上下文框架規則和86個(gè)詞類(lèi)標記進(jìn)行自動(dòng)標注，正確率達到77%?；诟怕式y計的方法中，1983年Leech和Garside等人建立了CLAWS系統，通過(guò)共現概率矩陣的方法使得自動(dòng)標注的正確率達到96%~97%。1988年，DeRose對CLAWS系統進(jìn)行了改進(jìn)，降低了該系統的復雜性，使得自動(dòng)詞性標注的正確率達到了實(shí)用的水平?；谡Z(yǔ)言模型和隱馬模型的概率統計方法也取得了很好的結果。另外，也出現了很多將詞法分析整個(gè)過(guò)程一體化的工作，如英文的形態(tài)分析和詞性標注一體化、中文的分詞和詞性標注一體化等等。值得一提的工作還包括Eric Brown的基于錯誤驅動(dòng)的規則學(xué)習詞性標注方法。該方法可以通過(guò)初始標注語(yǔ)料，自動(dòng)學(xué)習到有序的多條標注規則來(lái)對未標注語(yǔ)料進(jìn)行標注。有人將該方法歸入規則方法，也有人將之納入統計方法，每種歸類(lèi)都有自己的道理。目前，該詞性標注方法可以達到97%的封閉測試正確率，是網(wǎng)上可以下載的實(shí)用詞法標注工具之一。對于中文詞性標注，國內清華大學(xué)、山西大學(xué)、北京大學(xué)、東北大學(xué)、中科院計算所等都做了大量有效的工作。見(jiàn)諸報道的中文詞性標注的最高正確率也在95%以上。
1.3.2 3.2 句法分析
句法分析是將線(xiàn)性的詞序列轉變成某種句法結構（最常見(jiàn)的是短語(yǔ)結構樹(shù)）的過(guò)程[6]。由于短語(yǔ)結構語(yǔ)法（特別是上下文無(wú)關(guān)語(yǔ)法）應用最為廣泛，因此以短語(yǔ)結構樹(shù)為目標的上下文無(wú)關(guān)語(yǔ)法（CFG）句法分析器研究得最為徹底。其他類(lèi)型的句法分析器可以由CFG句法分析器改造而成。句法分析的策略主要包括自頂向下、自底向上以及左角分析法。著(zhù)名的句法分析算法有：CYK、Early、Tomita、Chart等等。真正實(shí)現時(shí)，句法分析系統通常由短語(yǔ)規則和具體算法組成。短語(yǔ)規則指出了從詞到短語(yǔ)、從短語(yǔ)到句子結合的規律。句法分析的最大難點(diǎn)在于句法歧義。也就是說(shuō)，根據句法規則，一個(gè)短語(yǔ)或者句子往往有多棵句法樹(shù)，而這其中往往只有一棵是正確的。句法分析的主要目標是消除句法歧義。消除句法歧義可以通過(guò)在句法規則中不斷地引入上下文句法或者語(yǔ)義判定規則來(lái)進(jìn)行。但是這種方法引入的個(gè)性化規則一方面十分龐大，另一方面很難保證規則的一致性。另一種方法是在句法分析中引入概率，根據概率的大小來(lái)選擇句法樹(shù)的生成。在進(jìn)行句法分析的過(guò)程中，研究者發(fā)現對真實(shí)語(yǔ)料生成完全的句法分析樹(shù)似乎太理想化，從而萌生了部分分析[7]（partial parsing，也叫組塊分析或淺層分析，chunking parsing or shallow parsing）的思想，即不進(jìn)行完全的句法分析，而是產(chǎn)生部分語(yǔ)言單位組塊（如基本名詞短語(yǔ)、人名、地名、機構名等等）。這些組塊在大規模內容處理中可以得到很好的應用。從所發(fā)表論文公布的結果看，英文部分分析的測試結果（F值）可達93%以上。中文部分分析的測試結果也能達到這個(gè)值。不過(guò)，由于很多研究部分分析的定義、標準和語(yǔ)料并不統一，有些研究結果無(wú)法評價(jià)，結果之間也缺乏可比性。有實(shí)驗報告證明，查詢(xún)語(yǔ)句中名詞短語(yǔ)的識別可以改善系統檢索文檔的相關(guān)性，并可提高檢索系統的召回率和精確率。
目前，美國賓州大學(xué)已經(jīng)建立了用于句法分析的中英文句法結構庫（tree bank），可供研究者實(shí)驗和評價(jià)句法分析的成果。
1.3.3
3.3 語(yǔ)義分析
語(yǔ)義分析的主要目標有兩個(gè)：一是確定每個(gè)語(yǔ)言單位在文中的某種語(yǔ)義類(lèi)；二是確定這些語(yǔ)言單位之間的語(yǔ)義關(guān)系。前者的工作稱(chēng)為語(yǔ)義排歧（WSD, word sense disambiguation），即根據上下文從語(yǔ)言單位可能的多個(gè)語(yǔ)義中選擇最恰當的語(yǔ)義。后者也常常稱(chēng)為（狹義的）語(yǔ)義分析。
語(yǔ)義分析通常需要語(yǔ)義詞典的支持，目前著(zhù)名的英文語(yǔ)義詞典有：WordNet、FrameNet、MindNet等，中文語(yǔ)義詞典有：HowNet、同義詞詞林等等。
WSD的研究同樣有規則方法和統計方法。統計方法可以通過(guò)對上下文窗口的統計分析來(lái)確定詞匯的語(yǔ)義。在大規模內容計算中，WSD可以借鑒上下文的歷史查詢(xún)、以及對用戶(hù)的興趣跟蹤來(lái)對查詢(xún)詞的語(yǔ)義進(jìn)行排歧。
語(yǔ)義分析常常建立在某種語(yǔ)法或理論體系上。如語(yǔ)義語(yǔ)法、格語(yǔ)法、語(yǔ)義網(wǎng)絡(luò )、蒙格塔語(yǔ)法、范疇語(yǔ)法、概念依存理論等等。
1.4 4 聚類(lèi)、分類(lèi)技術(shù)
聚類(lèi)、分類(lèi)技術(shù)是模式識別的基本技術(shù)。目前在文本處理中，也是最常用的兩項技術(shù)。兩者都是將未知文本歸入某個(gè)類(lèi)別的過(guò)程。聚類(lèi)也稱(chēng)為無(wú)監督的分類(lèi)。它事先沒(méi)有類(lèi)別，而是根據樣本之間的某種相似程度自動(dòng)地聚集成某種類(lèi)別。而分類(lèi)過(guò)程事先都有給定的類(lèi)別及相關(guān)訓練樣本。分類(lèi)的過(guò)程包括分類(lèi)器的參數訓練以及對測試樣本的預測兩個(gè)部分。不論是聚類(lèi)還是分類(lèi)的結果往往都能降低大規模文本處理的復雜性。
信息聚類(lèi)和信息分類(lèi)都包括特征選擇、信息表示、相似度計算以及分組算法等主要組成部分。相對而言，由于信息分類(lèi)有訓練樣本，其特征選擇方法繁多且更為復雜。同樣，信息分類(lèi)中不涉及到訓練樣本的特征選擇方法都能用于信息聚類(lèi)。文本聚類(lèi)和文本分類(lèi)中的文本大都采用向量空間模型（參見(jiàn)第五節），相似度計算方面有各種距離計算方法，如夾角余弦、內積等等。
1.4.1 4.1 文本聚類(lèi)技術(shù)
聚類(lèi)技術(shù)通?？梢苑殖蓛深?lèi)：層次型（Hierarchical）聚類(lèi)和分割型（Partitional）聚類(lèi)。層次型聚類(lèi)生成一個(gè)樹(shù)型的聚類(lèi)譜系圖，根據需要可以在不同層次上選取類(lèi)別個(gè)數。分割型聚類(lèi)對原有數據集生成一個(gè)劃分。層次型聚類(lèi)方法包括基于最短距離、基于最長(cháng)距離、基于均值距離的方法。分割型聚類(lèi)又包括方差法（如k-means方法）和基于圖論的方法等等。
文本聚類(lèi)是聚類(lèi)方法在文本處理領(lǐng)域的應用。應用領(lǐng)域包括敏感話(huà)題的發(fā)現、敏感社區的發(fā)現、信息過(guò)濾中用戶(hù)（興趣）的自動(dòng)聚類(lèi)（用戶(hù)興趣可以采用文本表示）等等。
1.4.2 4.2 文本分類(lèi)技術(shù)
文本分類(lèi)的特征選擇有很多方法，如文檔頻率(Document Frequency, DF)、信息增益（Information Gain, IG）、互信息（Mutual Information, MI）、χ2統計量等等。CMU的Yang Yiming[8]對這些方法進(jìn)行了基于英文的分類(lèi)對比實(shí)驗，得出的結論是χ2統計量和IG方法最好。近年以來(lái)，也有一些基于中文分類(lèi)的特征選擇實(shí)驗，得到的實(shí)驗結論不盡相同。特征選擇的結果空間可能仍然維數很高，因此，研究人員提出對特征空間進(jìn)行降維。隱性語(yǔ)義索引（Latent Semantic Indexing, LSI） 和主成分分析（Principle Component Analysis, PCA）都是常用的特征降維方法。文本分類(lèi)算法有很多。如線(xiàn)性最小平方擬合、貝葉斯(Bayes)、k近鄰（k-Nearest Neighbor, kNN）、決策樹(shù)、支持向量機（Support Vector Machine, SVM）、基于神經(jīng)網(wǎng)絡(luò )的分類(lèi)等等?！ ang Yiming[9]對眾多的英文文本分類(lèi)方法進(jìn)行了比較，得出的結論是SVM、kNN以及線(xiàn)性最小平方擬合法較優(yōu)。目前，還沒(méi)有見(jiàn)到關(guān)于中文分類(lèi)算法性能比較的較權威的書(shū)面報道。
文本分類(lèi)技術(shù)應用十分廣泛，比如垃圾郵件的檢測、敏感話(huà)題的跟蹤、內容的分層次組織管理等等。
1.5 5 WEB檢索
所謂WEB檢索是指以檢索查詢(xún)方式從WEB中挑選出和用戶(hù)需求最相關(guān)的頁(yè)面。WEB檢索是大規模內容檢索中一個(gè)重要應用。之所以把它歸結成應用是因為它包括了各種基本技術(shù)的復雜組合。WEB檢索的對象是WEB，與傳統的IR處理對象并不相同，因此，WEB檢索中融合了傳統IR和一些現代的新技術(shù)。一方面，現代IR一直對傳統IR進(jìn)行補充和改進(jìn)，另一方面，也出現了和傳統IR不一樣的新技術(shù)。
本質(zhì)上，WEB檢索的關(guān)鍵就是將用戶(hù)的需求和網(wǎng)頁(yè)進(jìn)行匹配打分。根據打分依賴(lài)對象的不同，本節按照內容、結構、用戶(hù)行為三個(gè)方面來(lái)總結WEB檢索應用中的種種技術(shù)。
網(wǎng)絡(luò )內容安全和智能內容管理的很多問(wèn)題都可以歸結為對某個(gè)已知主題的查詢(xún)檢索問(wèn)題。如：查詢(xún)與伊拉克戰爭相關(guān)的文檔。
1.5.1 5.1 基于內容的檢索
基于內容的檢索就是根據頁(yè)面的內容（可以是標題、正文、錨文本-anchor text甚至是URL-Universal Resources Locator本身）來(lái)打分。這里面主要包括三種模型：布爾模型（Boolean Model）、向量空間模型（Vector Space Model，VSM）及概率模型（Probabilistic Model）。
布爾模型實(shí)際就是將用戶(hù)提交的查詢(xún)詞和每個(gè)頁(yè)面直接匹配。用戶(hù)提交的查詢(xún)是多個(gè)詞組成的布爾表達式。符合這個(gè)布爾表達式的頁(yè)面得1分，否則0分?；镜牟紶柲Ｐ鸵驗椴荒芴峁└毼⒌呐琶柺苤肛?。研究者們提出了各種各樣的方法，如根據命中關(guān)鍵詞的詞頻排序、將布爾模型進(jìn)行推廣以支持部分匹配等等。推廣的一個(gè)結果是Extended 布爾模型以至p-norm模型。推廣的另一個(gè)結果是向量空間模型。需要指出的是，現今的大部分搜索引擎仍然采用了布爾模型的主要思想。
康奈爾大學(xué)的Salton等人提出的向量空間模型將查詢(xún)和文本表示成標引項（標引項term是向量表示的基本單位，可以是字、詞、短語(yǔ)及其他語(yǔ)言單位）及其權重的向量。一個(gè)例子是：<信息,3,檢索,5,模型1>，然后通過(guò)向量之間的相似度比較來(lái)計算每個(gè)文本的相似程度。向量空間模型不僅可以用于檢索，而且廣泛用于包括文本分類(lèi)的諸多領(lǐng)域中。標引項權重的計算方法有很多種。最基本的是一種稱(chēng)為T(mén)FIDF（Term Frequency & Inverse Document Frequency）的方法，即同時(shí)考慮標引項在所在文本中的分布情況以及在全部文本集合中的分布情況。后續的研究還考慮文本的長(cháng)度因素，提出了多種改進(jìn)的權重計算公式。其中一種稱(chēng)為Pivoted Normalization的權重計算方法近些年來(lái)受到了廣泛關(guān)注。標引項的選擇也是向量空間模型在使用中遇到的問(wèn)題之一。有研究認為，中文檢索中的標引項選擇詞和二元字的組合較好。最典型的向量空間模型原型系統是康奈爾大學(xué)的SMART，它提供源代碼開(kāi)放下載，目前已經(jīng)被成千上萬(wàn)的研究者所用。
概率檢索模型是通過(guò)概率的方法將查詢(xún)和文本聯(lián)系起來(lái)。最經(jīng)典的概率檢索模型是英國倫敦城市大學(xué)的Robertson和劍橋大學(xué)的Sparck Jones提出的二元獨立概率模型（Binary Independence Retrieval, BIR）。它主要通過(guò)計算查詢(xún)詞中每個(gè)標引項和文本的相關(guān)概率來(lái)計算整個(gè)查詢(xún)和文本的概率。BIR模型的關(guān)鍵問(wèn)題是對其中各參數的估計，Robertson和Sparck Jones利用偽相關(guān)反饋技術(shù)來(lái)計算模型的參數，從而最終實(shí)現檢索。概率模型和向量空間模型在測試中表現出的性能不相上下，很難說(shuō)哪種模型就比另一種模型優(yōu)越。另外，概率檢索中的相似度計算公式也融入了不少向量空間模型的思想，比如文本長(cháng)度的引入。最著(zhù)名的概率檢索原型系統是倫敦城市大學(xué)的OKAPI。其他的概率檢索模型還包括基于神經(jīng)網(wǎng)絡(luò )的概率模型、基于語(yǔ)言學(xué)模型的檢索模型。后者90年代中期由麻省大學(xué)(UMass)提出，已經(jīng)引起了廣泛的關(guān)注。CMU實(shí)現的原型系統Lemur（同時(shí)實(shí)現了多種檢索模型）已經(jīng)支持基于語(yǔ)言學(xué)模型的檢索模型。
基于內容的檢索還有各種提高檢索精度的辦法，比如查詢(xún)擴展或重構（利用詞典或者統計信息對用戶(hù)初始查詢(xún)進(jìn)行修正）、相關(guān)性反饋（在初始檢索的結果上通過(guò)用戶(hù)交互或者自動(dòng)方式進(jìn)行反饋，構造更合適的查詢(xún)）、結果組合（多種檢索系統結果的融合）等等。它們的最終目的都是為了精確逼近查詢(xún)和文本在內容上的相似度。
基于內容的檢索的另外一個(gè)側重點(diǎn)是數據的存儲和組織，包括索引文件、壓縮方法、數據結構等等。篇幅所限，請有興趣的讀者參看相關(guān)文獻[10]。
1.5.2 5.2 基于結構的檢索
前面提到，WEB檢索的對象是WEB。而WEB最大的一個(gè)特征是互聯(lián)。另外，很多網(wǎng)頁(yè)都是半結構文本。充分利用結構信息是現代信息檢索，尤其是WEB檢索的一項重要內容。首先可以想到的是，可以利用頁(yè)面本身的半結構信息，比如標題、段落位置、字體信息等等來(lái)細化不同位置標引項的權重。這種思想已經(jīng)廣泛融入到基于內容的檢索中去，而且取得了很好的效果。除此之外，WEB中各頁(yè)面之間的鏈接關(guān)系是一項可以利用的重要信息?；谶@種信息的技術(shù)被稱(chēng)為鏈接分析技術(shù)。絕大部分鏈接分析算法都有共同的出發(fā)點(diǎn)：更多地被其他頁(yè)面鏈接的頁(yè)面是質(zhì)量更好的頁(yè)面，并且從更重要的頁(yè)面出發(fā)的鏈接有更大的權重。這個(gè)循環(huán)定義可以通過(guò)迭代算法巧妙打破。
最著(zhù)名的鏈接分析算法是Stanford大學(xué)提出并應用到Google搜索引擎中的PageRank算法以及IBM用于CLEVER搜索引擎的HITS算法[11]。
PageRank定義的是在WEB中頁(yè)面的訪(fǎng)問(wèn)概率。訪(fǎng)問(wèn)概率越大的頁(yè)面的PageRank值也越大。具體的計算公式是：
Pr(t)=(1-d)/T+d(Pr(t1)/C(t1)+ Pr(t2)/C(t2)+…+Pr(tn)/C(tn))
即，每個(gè)頁(yè)面的PageRank (Pr)是無(wú)意中直接瀏覽到的概率和從上一頁(yè)中繼續訪(fǎng)問(wèn)的概率總和。其中，T是節點(diǎn)（頁(yè)面）總數，C(t)是從頁(yè)面t指出的超鏈接總數，d稱(chēng)為阻尼因子（damping factor），一般取值為0.85。概率Pr(t)反映了節點(diǎn)t的重要程度。
HITS是IBM Almaden研究中心開(kāi)發(fā)的另一種鏈接分析算法。它認為每個(gè)WEB頁(yè)面都有被指向、作為權威（Authority）和指向其他頁(yè)面作為資源中心（Hub）的兩方面屬性，其取值分別用A(p)和H(p)表示。A(p)值為所有指向p的頁(yè)面q的中心權重H（q）之和，同樣，頁(yè)面p的中心權重H(p)值是所有p所指向的頁(yè)面q的權威權重A(q)之和，如下式：
A(p)=∑H(qi) （其中qi是所有鏈接到p的頁(yè)面）
H(p)=∑A(qi)（其中qi是所有頁(yè)面p所鏈接到的頁(yè)面）
鏈接分析方法常常和基于內容的檢索方法相結合。盡管很多基于較小的數據規模（數十G）網(wǎng)頁(yè)數據的實(shí)驗并不能證明鏈接分析算法能夠提高檢索的性能。但是，很多人都相信，鏈接分析方法能夠反映WEB社會(huì )的一些最自然的屬性，應該能夠在大規模真實(shí)環(huán)境下提高檢索結果。Google的使用成功也增強了大家的信心砝碼。
1.5.3 5.3 基于日志的檢索
WEB日志記錄了用戶(hù)訪(fǎng)問(wèn)WEB的歷史信息。根據該歷史信息可以挖掘出許多對提高檢索效果有用的信息，從而可以改進(jìn)檢索的結果。通過(guò)分析用戶(hù)的歷史請求，可以獲得用戶(hù)的興趣愛(ài)好，從而提供最符合用戶(hù)興趣的結果。通過(guò)分析用戶(hù)對結果的瀏覽記錄，也可以獲得用戶(hù)的興趣愛(ài)好和行為方式，從而指導檢索過(guò)程。其他用戶(hù)的訪(fǎng)問(wèn)和瀏覽信息（如訪(fǎng)問(wèn)頻度、用戶(hù)查詢(xún)聚類(lèi)、用戶(hù)瀏覽結果聚類(lèi)等等）同樣對提高單個(gè)特定用戶(hù)的檢索結果有幫助。利用日志信息提高檢索結果是當前商用搜索引擎的一個(gè)發(fā)展趨勢。
1.6 6 信息過(guò)濾
信息過(guò)濾是大規模內容處理的另一種典型應用。它是對陸續到達的信息進(jìn)行過(guò)濾操作，將符合用戶(hù)需求的信息保留，并根據用戶(hù)的操作不斷調整過(guò)濾策略。如果把信息檢索稱(chēng)為一種典型的“拉”（pull）的方式（用戶(hù)主動(dòng)，系統被動(dòng)服務(wù)）的話(huà)，那么信息過(guò)濾則可以稱(chēng)為
“推”（push）方式（用戶(hù)被動(dòng)，系統主動(dòng)服務(wù)）。信息過(guò)濾的典型應用場(chǎng)景包括：垃圾郵件的過(guò)濾、信息的個(gè)性化服務(wù)、智能內容分發(fā)和內容推薦等等。
信息過(guò)濾包括兩種：一種稱(chēng)為基于內容的信息過(guò)濾（Content-based Filtering）；另一種稱(chēng)為基于合作的信息過(guò)濾（Social Filtering，又叫協(xié)同過(guò)濾或社會(huì )過(guò)濾）。
在基于內容的過(guò)濾中，通常采用某種方式（如VSM）來(lái)表示用戶(hù)的興趣模型和信息資源模型。實(shí)現時(shí)，當歷史正例文本達到一定規模時(shí)，可以采用各種分類(lèi)技術(shù)。內容過(guò)濾最主要工作之一是對用戶(hù)興趣的不斷學(xué)習和反饋，以保證在任一時(shí)刻過(guò)濾的文本和當前用戶(hù)興趣相吻合。最常用的反饋算法是Rocchio算法。中科院計算所提出了一種在反饋信息很少的情況下盡可能提高過(guò)濾性能的自適應算法ICTFilter[12]。
基于合作的過(guò)濾算法從用戶(hù)相似度的角度出發(fā)。它的基本假設是經(jīng)常訪(fǎng)問(wèn)相似資源的用戶(hù)興趣相似，相似興趣的用戶(hù)又會(huì )訪(fǎng)問(wèn)相似的資源。因此，通過(guò)對相似興趣用戶(hù)的判定，來(lái)確定某個(gè)用戶(hù)對某一未知資源是否感興趣。合作過(guò)濾的關(guān)鍵在于建立用戶(hù)的相似度關(guān)系?？梢圆捎肞earson Correlation Coefficient （PCC）方法和Vector Similarity （VS），考慮上述方法中矩陣的稀疏性（即用戶(hù)—資源矩陣是稀疏矩陣）導致潛在相似興趣用戶(hù)的難以發(fā)現，有人提出了基于用戶(hù)分類(lèi)的方法和基于LSI的方法，取得了一定的效果。合作過(guò)濾常常和內容過(guò)濾方法配合使用。
1.7 7 總結及展望
上面介紹了大規模內容處理的相關(guān)背景、技術(shù)和應用，總之，大規模內容計算具有廣闊的應用前景，是Internet網(wǎng)絡(luò )內容安全和智能內容管理的關(guān)鍵支撐技術(shù)。這兩方面的迫切和長(cháng)期需求促進(jìn)了大規模內容計算的發(fā)展。
大規模內容計算技術(shù)的發(fā)展有以下幾個(gè)趨勢：
(1) 個(gè)性化趨勢。從與用戶(hù)的交互中挖掘出用戶(hù)的興趣從而更好地為不同用戶(hù)提供量身定體的服務(wù)是大規模內容計算的發(fā)展趨勢之一。
(2) 融合化趨勢。各種技術(shù)甚至學(xué)科的交融也是大規模內容計算的一個(gè)發(fā)展趨勢，包括 數據挖掘、機器學(xué)習、統計推斷、模式識別等等學(xué)科研究領(lǐng)域的技術(shù)廣泛地引入到大規模內容計算，從而推動(dòng)了大規模內容計算的發(fā)展。大規模內容計算的巨大規模同樣需要并行處理、海量存儲、高性能計算等等各方面的技術(shù)。而大規模傳統技術(shù)之間也有融合的趨勢，檢索和過(guò)濾、分類(lèi)和聚類(lèi)、各種檢索模型等等之間都逐漸相互借鑒和融合。
另外，與大規模內容計算技術(shù)的發(fā)展同樣相關(guān)還有一個(gè)語(yǔ)料庫建設、標準化和評測的趨勢。為了促進(jìn)相關(guān)技術(shù)的發(fā)展，必須要有大量的實(shí)驗語(yǔ)料庫、技術(shù)標準和評測評比。美國政府NIST和DARPAR組織的TREC[13]（Text REtrieval Conference）是評測會(huì )議中典型的代表，大大促進(jìn)了大規模內容計算技術(shù)的提高。大陸包括微軟亞洲研究院、復旦大學(xué)、中科院計算所、哈工大、清華大學(xué)、中科院自動(dòng)化所、軟件所都先后加入了TREC評測隊伍的行列并取得了不錯的成績(jì)。目前，國內也有部分組織機構（如北大天網(wǎng)網(wǎng)頁(yè)分類(lèi)評測、中科院計算所內容檢索評測等）開(kāi)展了評測相關(guān)的工作。這些工作已經(jīng)或者勢必促進(jìn)大規模內容計算技術(shù)的發(fā)展。
參考文獻
[1] 白碩，程學(xué)旗，郭莉，王斌，余智華，劉群，大規模內容計算，2003年，全國第七屆計算語(yǔ)言學(xué)聯(lián)合會(huì )議論文集，13~25，清華大學(xué)出版社。
[2] 高文，劉峰，黃鐵軍等著(zhù)，數字圖書(shū)館――原理與技術(shù)實(shí)現，2000年，清華大學(xué)出版社。
[3] 李盛韜，基于主題的WEB信息采集技術(shù)研究，2002年，中科院計算所碩士學(xué)位論文。
[4] 馮志偉，自然語(yǔ)言的計算機處理，1996年，上海外語(yǔ)教育出版社。
[5] 孫茂松，鄒嘉彥，漢語(yǔ)自動(dòng)分詞研究評述，當代語(yǔ)言學(xué)，2001年，第一期，22~32。
[6] 劉群，中科院研究生院《計算語(yǔ)言學(xué)》講義，2003年，
http://www.nlp.gov.cn.
[7] 李素建，漢語(yǔ)組塊計算的若干研究，2002年，中科院計算所博士學(xué)位論文。
[8] Yiming Yang and Jan O. Pederson, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning （ICML‘97）, 1997.
[9] Yiming Yang and Xin Lin, A re-examination of text categorization methods. Proceedings on the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval: 42-49.
[10] Baeza-Yates, R. and Ribeiro-Neto, B. 1999. Modern Information Retrieval. Addison Wesley Longman, Reading, MA.
[11] 劉悅，WWW上鏈接分析算法的若干研究，2004年，中科院計算所博士學(xué)位論文。
[12] 許洪波，大規模信息過(guò)濾技術(shù)研究及其在WEB問(wèn)答系統中的應用，2003年，中科院計算所博士學(xué)位論文。
[13] TREC 會(huì )議網(wǎng)站，
http://trec.nist.gov/[14] 大規模內容計算網(wǎng)站，
http://lcc.software.ict.ac.cn/[15] 中文資源開(kāi)放平臺網(wǎng)站，
http://www.nlp.gov.cn/作者： 王 斌 中國科學(xué)院計算技術(shù)研究所 博士 副研究員
許洪波 中國科學(xué)院計算技術(shù)研究所 博士 助理研究員
來(lái)源：中國科學(xué)院計算技術(shù)研究所
