向量空間模型

向量空間模型(vectorspacemodel)向量空間模型概念簡單，把對文本內(nèi)容的處理簡化為向量空間中的向量運算，并且它以空間上的相似度表達語義的相似度，直觀易懂。當(dāng)文檔被表示為文檔空間的向量，就可以通過計算向量之間的相似性來度量文檔間的相似性。文本處理中最常用的相似性度量方式是余弦距離VSM基本概念：(1)文檔(Document):泛指一般的文本或者文本中的片斷(段落、句群或句子),一般指一篇文章，盡管文檔可以是多媒體對象，但是以下討論中我們只認(rèn)為是文本對象，本文對文本與文檔不加以區(qū)別"。(2)項(Term):文本的內(nèi)容特征常常用它所含有的基本語言單位(字、詞、詞組或短語等)來表示,這些基本的語言單位被統(tǒng)稱為文本的項，即文本可以用項集(TermList)表示為D(T1,T2,,,,Tn)其中「是項,1惑q”⑶項的權(quán)重(TermWeight):對于含有n個項的文本D(，工 項「.常常被賦予一定的權(quán)重.表示他們在112)文本D中的重要程度,即D=(I],?,)這時我們說項：的權(quán)重:⑴火皿為 ,mm(4)向量空間模型(VSM):給定一文本D二D(「.， /)由'.于...在文本中既可以重復(fù)出現(xiàn)又應(yīng)該有先后次序的關(guān)系，分析起來有一定困難。為了簡化分析，暫時不考慮「的順序,并要求［互異,這時可以把 「看作是一個 n維的坐標(biāo)，而/W???.. 就是n維坐標(biāo)所對應(yīng)的值，所以文檔1，2* ，D(W甲 就可以被看作一個n維的向量了。(5)相似度(Similarity)兩個文本D,和DZ之間的(內(nèi)容)相關(guān)程度(DegreeofRelevanee)常常用他們之間的相似度Sim(...」?：；)來度量,當(dāng)文本被表示為向量空間模型時，我們可以借助與向量之間的某種距離來表示文本間的相似度"常用向量之間的內(nèi)積進行計算：Simd：.*〕或者用夾角的余弦值表示：Sim』i，D2)=嚴(yán)叫叫1LZ注臨可以看出，對向量空間模型來說，有兩個基本問題：即特征項的選擇和項的權(quán)重計算。特征項選擇用來表示文檔內(nèi)容的項可以是各種類別，對漢語來說，有字、詞、短語，甚至是句子或句群等更高層次的單位。項也可以是相應(yīng)詞或短語的語義概念類。項的選擇必須由處理速度、精度、存儲空間等方面的具體要求來決定。特征項選取有幾個原則：一是應(yīng)當(dāng)選取包含語義信息較多，對文本的表示能力較強的語言單位作為特征項；二是文本在這些特征項上的分布應(yīng)當(dāng)有較為明顯的統(tǒng)計規(guī)律性，這樣將適用于信息檢索、文檔分類等應(yīng)用系統(tǒng)；三是特征選取過程應(yīng)該容易實現(xiàn)，其時間和空間復(fù)雜度都不太大。實際應(yīng)用中常常采用字、詞或短語作為特征項。由于詞匯是文本最基本的表示項,在文本中的出現(xiàn)頻度較高,呈現(xiàn)一定的統(tǒng)計規(guī)律,在考慮到處理大規(guī)模真實文本所面臨的困難,一般選擇詞匯或短語作為特征項,但是直接選用文本中的詞或詞組作為文本特征項也會存在以下問題:（1）文本中存在一些沒有實在意義但使用頻率很高的虛詞和功能詞,如中文中“的、”“把、”“了”,等常常把一些真正有分類作用的實詞淹沒掉了。解決這個問題的方法是把這些詞組織成一個禁用詞表,或者進行權(quán)重計算時,使它們的權(quán)重很低,通過取閥值將它們丟棄。采用禁用詞表時,詞表的選擇很關(guān)鍵,很難全面地包括所有的禁用詞,并且語言是不斷發(fā)展的,禁用詞表也是隨著訓(xùn)練文本集合的不同而不同,某個詞在這里不是禁用詞,到另外一類文本中可能就成了禁用詞。另一方面考慮到,最能代表一篇文章實際意義的詞,往往是那些實詞,如形容詞、動詞、名詞,而且同一個詞,當(dāng)處于不同詞性時,可能分別屬于和不屬于禁用詞表。例如：“他高興地走了”（副詞“地”應(yīng)是禁用詞）,“地很不平（”名詞“地”不應(yīng)作為禁用詞）"針對這個現(xiàn)象,提出了只提取形容詞、動詞和名詞作為特征項,并嘗試著取代禁用詞表方法.(2)采用詞語作為特征項時還會出現(xiàn)所謂的同義現(xiàn)象,同義現(xiàn)象是指:對于同一個事物不同的人會根據(jù)個人的需要、所處的環(huán)境、知識水平以及語言習(xí)慣有著不同的表達方式,因此所采用的詞匯也有很大的不同。所以經(jīng)常出現(xiàn)兩個文本所用的詞匯有所不同,但實際上兩者是相似的，這就是詞的同義現(xiàn)象造成的。例如電腦和計算機是同一個概念,應(yīng)該屬于同一個特征項,目前最常用的解決方案是采用概念詞典來解決這個問題。分詞確定了特征項單位以后,接下來要做的就是把文本分割成特征項的表示。我們知道,詞是最小的能夠獨立活動的有意義的語言成分。然而,漢語是以字為基本的書寫單位,文本中詞與詞之間沒有明確的分隔標(biāo)記,而是連續(xù)的漢字串,顯而易見,自動識別詞邊界,將漢字串分為正確的詞串的漢語分詞問題無疑是實現(xiàn)中文信息處理各項任務(wù)的基礎(chǔ)與關(guān)鍵。中文詞語分析一般包括3個過程:預(yù)處理過程的詞語粗切分、切分排歧與未登陸詞識別、詞性標(biāo)注。目前中文詞語分析采取的主要步驟是:先采取最大匹配、最短路徑、概率統(tǒng)計、全切分等方法 ,得到一個相對最好的粗分結(jié)果,然后進行排歧、未登陸詞識別,最后標(biāo)注詞性。在實際系統(tǒng)中,這三個過程可能相互交叉、反復(fù)融合,也可能不存在明顯的先后次序?？梢詫F(xiàn)在的分詞算法分為3大類:基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計的分詞方法。(1)基于字符串匹配的分詞方法這種方法又叫機械分詞法,它按照一定的策略將待分析的漢字串與機器字典中的詞條進行匹配,若在字典中可以找到某個字符串,則匹配成功(識別出一個詞)。按照掃描方向的不同可以分為正向匹配和逆向匹配；按照不同長度優(yōu)先匹配的情況,又可以分為最大(最長)匹配和最小(最短)匹配；按照是否與詞性標(biāo)注過程相結(jié)合,又可分為單純分詞法和分詞與標(biāo)注相結(jié)合的一體化方法。具體的方法主要有以下幾種：(a)最大匹配法(maximummatchingmethod,MM)在計算機中存放一個已知的詞表,這個詞表叫底表,從被切分的語料中,按給定的順序截取一個定長的字符串,通常為6-8個漢字,這個字符串的長度叫做最大詞長,把這個具有最大詞長的字符串與底表中的詞相匹配,如匹配成功,則可確定這個字符串為詞,然后指針向給定的方向移動與已經(jīng)識別出的詞長相應(yīng)個數(shù)的漢字 ,繼續(xù)進行匹配,否則,則把該字符串逐次減一,再與底表中的詞長進行匹配,直到成功為止。MM的原理簡單,易于在計算機上實現(xiàn),實現(xiàn)復(fù)雜度比較低。缺點是最大詞長難以確定,如果定得過長,則算法復(fù)雜度顯著提高,如果定得太短,則不能切分長度大于它的詞,導(dǎo)致切分正確率降低。(b)逆向最大匹配法(reversemaximummatchingmethod,RMM)這種方法的原理與MM相同，不同的是切詞的掃描方向，如果MM的方向是從左到右取字符串進行匹配,則RMM的切詞方向就是從右到左取字符串進行匹配。試驗證明RMM的切詞正確率較MM更高一些。但是,RMM要求配置逆序的切詞字典，這種詞典與人們的語言習(xí)慣不同。(c)逐詞遍歷匹配法這種方法把辭典中的詞按由長到短的順序,逐個與待切詞的語料進行匹配,直到把語料中所有的詞都切分出來為止。由于這種方法要把辭典中的每個詞都匹配一遍,需要花費很多時間,算法的時間復(fù)雜度相應(yīng)增加,效率不高。(d)雙向掃描法這種方法是分別用MM和RMM進行正向和逆向掃描完成初步的切分，并將用MM初步切分的結(jié)果與用RMM初步切分結(jié)果進行比較,如果兩種結(jié)果一致,則判定正確,否則定為疑點,此時或者結(jié)合上下文信息,或進行人工干預(yù),選取一種切分為正確結(jié)果,由于要進行雙向掃描,時間復(fù)雜度增加,而且為了使切分詞典能同時支持正向與逆向兩種順序的匹配和搜索,詞典的結(jié)構(gòu)比一般的切詞詞典復(fù)雜。最佳匹配法(optimummatchingmethod,0M)這是在切詞詞典中按詞出現(xiàn)頻率的大小排列詞條,高頻詞在前,低頻詞在后,從而縮短了查詢切詞詞典的時間，加快切詞的速度，使切詞達到最佳的效率。這種切詞方法對于分詞算法沒有什么改進,只是改變了分詞詞典的排列順序,它雖然降低了切詞的時間復(fù)雜度,卻沒有提高分詞的正確率。設(shè)立切分標(biāo)記法在書面語中,存在的切分標(biāo)記有兩種:一種是自然的切分標(biāo)志,如標(biāo)點符號,詞不能跨越標(biāo)點符號而存在,標(biāo)點符號則是詞的邊界之所在另一種是非自然的切分標(biāo)志,如只能在詞首出現(xiàn)的詞首字,只能在詞尾出現(xiàn)的詞尾字,沒有構(gòu)詞能力的單音節(jié)單純詞、多音節(jié)單純詞、擬聲詞等,詞顯然也不能跨越這些標(biāo)志而存在,它們也必然是詞的邊界。如果收集了大量的這種切分標(biāo)志,切詞時,先找到切分標(biāo)志,就可以把句子切分成一些較短的字段,然后再用MM或RMM進行進一步切分。使用這種方法切詞,要額外消耗時間,并掃描切分標(biāo)志,還要花費存儲空間來存儲非自然的切分標(biāo)志,使切詞算法的時間復(fù)雜度和空間復(fù)雜度都大大增加了,而切詞的正確率卻提高的有限,所以采用這種方法的自動切詞系統(tǒng)不多。有窮多級列舉法這種方法把現(xiàn)代漢語中的全部詞分為兩大類:一類是開放詞,如名詞、動詞、形容詞等,它們的成員幾乎是無窮的,另一類是閉鎖詞,如連詞、助詞、嘆詞等,它們的成員是可以一一枚舉的。切詞時,先切出詞的特殊標(biāo)志的字符串,如阿拉伯?dāng)?shù)字、拉丁字母等,再切出可枚舉的閉鎖詞,最后在逐級切出開放詞。這是完全立足于語言學(xué)的切詞方法,在計算機上實現(xiàn)起來還是很有困難。由于漢語很少單字成詞的特點,正向最小匹配和逆向最小匹配一般很少使用。一般說來,逆向匹配的切分精度略高于正向匹配,遇到的歧義現(xiàn)象也很少。統(tǒng)計結(jié)果表明,單純使用正向最大匹配的錯誤率為1/169,單純使用逆向最大匹配的錯誤率為1/245（這可能是因為漢語的中心語靠后的特點）。但這種精度還遠(yuǎn)遠(yuǎn)不能滿足實際的需要。由于分詞是一個智能決策過程,機械分詞方法無法解決分詞階段的兩大基本問題:歧義切分問題和未登陸詞識別問題。實際使用的分詞系統(tǒng),都是把機械分詞作為一種切分手段,還需通過利用各種其他的語言信息來進一步提高切分的正確率。對于機械分詞方法,可以建立一個通用模型,形式化地表示為ASM（d,a,m）即AutomaticSegmentationModel"其中:~:匹配方向,+1表示正向，一1表示逆向。a:每次匹配失敗后增加/減少字符串長度（字符數(shù)）,+1為增字，一1為減字。m:最大/最小匹配標(biāo)志,+1為最大匹配，一1為最小匹配。例如,ASM(+,-,+)就是正向減字最大匹配法(即MM),ASM(-,-,+)就是逆向減字最大匹配法(即RMM),等等。對于現(xiàn)代漢語來說,只有m=+1是實用的方法。(2)基于理解的分詞方法通常的分詞系統(tǒng),都力圖在分詞階段消除所有歧義切分現(xiàn)象,有些系統(tǒng)則在后續(xù)過程中來處理歧義切分問題,其分詞過程只是整個語言理解過程的一個小部分。其基本思想就是在分詞的同時進行句法、語義分析,利用句法信息和語義信息來處理歧義現(xiàn)象。它通常包括 3個部分:分詞子系統(tǒng)、句法語義子系統(tǒng)、總控部分。在總控部分的協(xié)調(diào)下,分詞子系統(tǒng)可以獲得有關(guān)詞、句子等的句法和語義信息來對分詞歧義進行判斷,即它模擬了人對句子的理解過程。這種分詞方法需要使用大量的語言知識和信息。由于漢語語言知識的籠統(tǒng)、復(fù)雜性,難以將各種語言信息組織成機器可直接讀取的形式,因此,目前基于理解的分詞系統(tǒng)還處于試驗階段,聯(lián)想回溯法就是其中的一種。聯(lián)想-回溯法(association-backtracking method,AB):要求建立知識庫-特征詞詞庫、實詞詞庫和規(guī)則庫。首先將待切分的漢字字符串序列分割為若干子串,子串可以是詞,也可以是由幾個詞組合成的詞群然后就利用實詞詞庫和規(guī)則庫將詞群細(xì)分為詞。切詞時,要利用一定的語法知識,建立聯(lián)想機制和回溯機制。聯(lián)想機制由聯(lián)想網(wǎng)絡(luò)和聯(lián)想推理構(gòu)成,聯(lián)想網(wǎng)絡(luò)描述每個虛詞的構(gòu)詞能力,聯(lián)想推理利用相應(yīng)的聯(lián)想網(wǎng)絡(luò)來判定所描述的虛詞究竟是單獨的詞還是作為其他詞中的構(gòu)成成分?；厮輽C制主要用于處理歧義句子的切分。聯(lián)想回溯算法雖然增加了算法的時間復(fù)雜度和空間復(fù)雜度 ,但是這種方法的切詞正確率得到了提高,是一種行之有效的方法。(3)基于統(tǒng)計的分詞方法從形式上看,詞是穩(wěn)定的字的組合,因此在上下文中,相鄰的詞同時出現(xiàn)的次數(shù)越多,就越有可能構(gòu)成一個詞"因此字與字相鄰共現(xiàn)的頻率或概率能夠較好地反映成詞的可信度?？梢詫φZ料中相鄰共現(xiàn)的各個字的組合的頻度進行統(tǒng)計,計算它們的互現(xiàn)信息。定義兩個字的互現(xiàn)信息為:M(X，Y)=log(P(X,Y)/P(X)*P(Y))其中P(X,Y)是漢字X,Y的相鄰共現(xiàn)頻率，P(X)、P(Y)分別是X、Y在語料中出現(xiàn)的概率。互現(xiàn)信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。當(dāng)緊密程度高于某一個闡值時,便可認(rèn)為此字組可能構(gòu)成一個詞。這種方法只需要對語料中字組頻度進行統(tǒng)計,不需要切分詞典,因而又稱為無詞典分詞法或統(tǒng)計取詞方法。但這種方法也有一定的局限性,會經(jīng)常抽出一些共現(xiàn)頻度高,但并不是詞的常用字組,例如“這一、”“之一”、“有的、”“我的、”“許多的”等,并且對常用詞的識別精度差,時空開銷大。實際應(yīng)用的統(tǒng)計分詞系統(tǒng)都要使用一部基本分詞詞典(常用詞詞典)進行串匹配分詞,同時使用統(tǒng)計方法識別一些新詞,即將串頻統(tǒng)計和串匹配結(jié)合起來,既發(fā)揮匹配分詞切分速度快、效率高的特點,又利用了無詞典分詞結(jié)合上下文識別生詞、自動消除歧義的優(yōu)點。常用的有基于詞頻統(tǒng)計的切詞法和基于期望的切詞法。(a)基于詞頻統(tǒng)計的切詞法這種方法利用詞頻統(tǒng)計的結(jié)果幫助在切詞過程中處理歧義切分字段.這種方法的缺點是:由于只考慮詞頻,出現(xiàn)頻率較低的詞總是被錯誤地切分.(b)基于期望的切詞法這種方法認(rèn)為一個詞的出現(xiàn),它后面緊隨的詞就有一種期望,據(jù)這種期望,在詞典中找到所有的詞從而完成切分.這種方法增加了切詞的空間復(fù)雜度,但在一定程度上提高了切詞的正確率。中文文本自動分詞技術(shù)一般以詞典作為分詞依據(jù),使用專門的分詞算法將文本中出現(xiàn)于詞典中的詞識別出來。通過這種方法獲得的文本特征只能是詞典中出現(xiàn)的詞匯,但是自然語言領(lǐng)域相關(guān)性和隨時間變化的特性,詞典中不可能包含文本中所有詞匯,因此,對不同類型文本進行分類時,就需要不斷修整和擴充詞典并改進分詞技術(shù),才能獲得良好的分類性能針對基于詞典分詞的分類系統(tǒng)存在的弊端 ,人們提出了一種基于n-gram信息的文本特征提取技術(shù),使文本自動分類系統(tǒng)擺脫了對復(fù)雜分詞處理程序?qū)嫶笤~庫的依賴,實現(xiàn)了中文文本自動分類的領(lǐng)域無關(guān)性和時間無關(guān)性。N-gram信息的概念是信息論創(chuàng)始人C.E.Shannon在研究信源編碼時提出來的,常被用來表示信源輸出的連續(xù)n個字符所組成的字符串。Shannon曾用它來研究英文文本中字符或字符串的統(tǒng)計特性,即信息嫡,隨后,n一gram信息被廣泛應(yīng)用于文本壓縮、字符識別與糾錯等領(lǐng)域,是一種直接面向代碼的技術(shù)。采用n-gram信息作為文本特征具有以下特點:第一:無需任何詞典支持;第二:對輸入文本所需的先驗知識少;第三:無需進行分詞處理;但是n-gram信息獲取技術(shù)的領(lǐng)域無關(guān)性和時間無關(guān)性的實現(xiàn)是有代價的.首先,n-gram信息的提取對系統(tǒng)資源的要求比較高 ,因為進行任何n-gram信息提取時,都會產(chǎn)生大量的數(shù)據(jù)冗余,占用很大的內(nèi)存空間。相比較于詞典的分詞技術(shù),其實現(xiàn)效率低,獲取n一gram信息將花費較長的時間。特征值抽取一篇文章在經(jīng)過了分詞處理之后,會產(chǎn)生很多詞條。如果一個文檔所有詞條都被作為其特征,將會使特征項異常龐大,而且這樣的特征項會使得每個特征項所含信息非常平滑,有用信息反而不會突出。因此我們需要進行特征項選取,把詞條中最能代表某類文本信息的詞條挑選出來，作為文本的特征項。實驗結(jié)果表明簡化特征項不但不會使分類結(jié)果準(zhǔn)確率降低，而且還會使結(jié)果更加準(zhǔn)確。特征項選擇一般使用統(tǒng)計方法,利用各種計算公式，計算詞代表的信息含量，確定一個閥值,將低于閥值的詞語過濾掉?；蛘叽_定一個特征項數(shù)目n,保留處于信息含量在前n位的詞條。特征抽取算法是文本自動分類中的一項關(guān)鍵技術(shù)和瓶頸技術(shù)，如何從原始文本特征集合中選擇最能表示文本主題內(nèi)容的特征子集，是文本特征抽取算法的研究目標(biāo)。目前，有多種特征抽取算法被用于文本自動分類的研究中，但這些算法都有其優(yōu)點和缺點，沒有公認(rèn)的最優(yōu)方法，需要針對具體系統(tǒng)進行對比來確定最優(yōu)方法。特征選擇可以從兩個方面提高系統(tǒng)性能一是分類速度，通過特征選擇,可以大大減少特征集合中的特征數(shù)，降低文本向量的維數(shù)，簡化計算,防止過度擬合，提高系統(tǒng)運行速度。二是準(zhǔn)確率，通過適當(dāng)?shù)奶卣鬟x擇，不但不會降低系統(tǒng)準(zhǔn)確性，反而會使系統(tǒng)精度提高。在文本處理中，一些常用特征提取評估函數(shù)有文檔頻數(shù)(documentfrequency)、信息增益(informationgain)、期望交叉熵(expectedcrossentropy)、互信息(mutualinformation)統(tǒng)計(CHI)、文本證據(jù)權(quán)(theweightofevideneefortext)等。(1)文檔頻數(shù)DF它是最簡單的評估函數(shù)，值為訓(xùn)練集合中該單詞發(fā)生的文本數(shù)。DF評估函數(shù)的理論假設(shè)稀有單詞可能不包含有用信息，也可能太少而不足以對分類產(chǎn)生影響,也可能是噪音,因此可以刪去。顯然它在計算量上比其他評估函數(shù)小很多,但是實踐運用中它的效果卻很好.DF的缺點是稀有單詞可能在某一類文本中并不稀有,也可能包含著重要的判斷信息,錯誤的舍棄,可能影響分類器的精度。因此,在實際運用中一般并不直接使用DF。(2)信息增益(informationGain)信息增益表示文檔中包含某一特征值時文檔類的平均信息量。它定義為某一特征在文檔中出現(xiàn)前后的信息熵之差。假定c為文檔類變量,C為文檔類的集合,d為文檔,f為特征(以下各節(jié)同此)。對于特征f,其信息增量記為IG⑴，計算公式如下：IG(f)=H(C)-H(C|f)特征項賦權(quán)為了兼顧查全率和查準(zhǔn)率，檢索系統(tǒng)在對特征項進行賦權(quán)時，應(yīng)同時包含提高查全率和查準(zhǔn)率的賦權(quán)因子。特征項賦權(quán)因子由頻率因子(TF)、文檔集因子(DF)和規(guī)格化因子三部分組成。(1)在文檔中頻繁出現(xiàn)的特征項具有較高的權(quán)重，因此檢索系統(tǒng)常使用頻率因子TF(TermFrequency)進行特征項賦權(quán)，使用高頻特征項進行查詢可以提高系統(tǒng)的查全率。(2)僅使用頻率因子并不能保證系統(tǒng)的查詢性能，提高查全率時會影響檢索系統(tǒng)的查準(zhǔn)率。因此需要引入一個與文檔集合有關(guān)的因子，加大文檔之間的區(qū)分度。如果特征項在集合中較少的文檔中出現(xiàn)，則相應(yīng)的文檔集因子IDF(InverseDocumentFrequency)較大。在文檔總數(shù)為N的集合中，如果包含某特征項的文檔數(shù)為n，則文檔集因子是id仁 n)°(3)當(dāng)文檔較長時，查詢式與文檔進行匹配的可能性更大，所以長文檔比短文檔更有可能被提取出來，因此引入規(guī)格化因子來消除文檔長度

對匹配結(jié)果的影響。假定兒代表特征項的權(quán)重，最后的規(guī)格化因子定義為：向量空間模型門限兒或文檔數(shù)伸文檔A或查詢Q的門限兒或文檔數(shù)伸文檔A或查詢Q的?S3Mr.向里表不，用戶查詢Q或相關(guān)反饋禁用詞表StophsU1根據(jù)與或M得到檢索結(jié)果，計算相似度測（%。）』并對5按相似度排序+TF-IDF權(quán)重特征項的權(quán)重計算是文本相似度計算中的一個非常重要的環(huán)節(jié)。一篇文本中的特征項數(shù)目眾多，要想得到比較準(zhǔn)確的對文本內(nèi)容的數(shù)學(xué)化表示，我們需要對能顯著體現(xiàn)文本內(nèi)容特征的特征項賦予高權(quán)重，而對不能可以體現(xiàn)文本內(nèi)容特征的特征項賦予低權(quán)重。從效率方面來說，特征項權(quán)重的計算是文本相似度計算中的主要工作， 它的效率也直接影響文本相似度計算的整體效率。經(jīng)典的TF-IDF權(quán)重是向