（計算機軟件與理論專業(yè)論文）支持向量機在文本分類中的應(yīng)用.pdf

東北大學(xué)碩士學(xué)位論文 摘要 支持向量機在文本分類中的應(yīng)用 摘要 文本分類是信息處理領(lǐng)域的一項基礎(chǔ)性技術(shù) 隨著語料庫語言學(xué)的興起 機器學(xué)習(xí) 方法也被引入到文本分類的任務(wù)中來 支持向量機是當前流行的模式識別方法 在許多 應(yīng)用領(lǐng)域都有很好的應(yīng)用 先前的一些相關(guān)工作表明支持向量機尤其適合應(yīng)用于文本分 類任務(wù) 支持向量機的兩大特性 核方法和泛化錯誤界的控制保證該模型要比其它分類 模型有更優(yōu)的效果 本文主要考察應(yīng)用支持向量機于文本分類的過程中所遇到的幾個問題 主要集中在 多類別支持向量機的構(gòu)建以及高維向量文本表示的降維問題 針對第一個問題 本文中 主要研究以多個二類分類器組合實現(xiàn)多類分類器的方法 本文在中英文兩個數(shù)據(jù)集上進 行的實驗比較了當前流行的四種實現(xiàn)方法 包括o n e a g a i n s t r e s t p a i r w i s em a x w i n d d a g 以及s i g m o i d 方法 結(jié)果表明 o n e a g a i n s t r e s t 從效率與效果兩方面考量都適用 于多類別支持向量機的實現(xiàn) 為解決降維問題 本文首先將降維方法分成特征選取和特 征抽取兩大類別 其中本文考察的特征選取方法包括文檔頻度 信息增益 開方擬合檢 驗 特征抽取方法包括潛在語義索引以及主成份分析方法 同樣 在中英文兩個不同的 數(shù)據(jù)集中的比較實驗 證明特征選取方法在與支持向量機組合時 沒有達到與其它分類 器組合時的效果 與此形成對比的是 特征抽取方法在把空間降到非常低維后 仍然保 證分類的性能 甚至能夠明顯地改善了實驗的效果 在本文實驗中 潛在語義索弓l 和主 成分分析方法都獲得了近似的性能 為了說明支持向量機在文本分類任務(wù)中的優(yōu)越性 本文單獨列出一章對支持向量機 和其它分類模型進行比較實驗 考察的分類器包括樸素貝葉斯 最大熵 k 最近鄰居 以及核心向量法 實驗表明 即使支持向量機在未做任何降維處理的情況下 其性能就 已優(yōu)于傳統(tǒng)的分類模型 通過本文的工作 可以得出如下結(jié)論 支持向量機是性能優(yōu)越的分類模型 而且由 于模型本身以及文本分類問題自身的一些性質(zhì) 保證在這個任務(wù)中應(yīng)用支持向量桃時 可以獲得良好的性能 為了快速而簡單地構(gòu)造多類支持向量機 從效率與效果方面考慮 都可以選擇o n e a g a i n s t r e s t 方法 在某些實時性應(yīng)用中 當需要對高維向量進行降維處 理時 建議優(yōu)先選擇特征抽取的方法 本文所考察的兩個抽取方法可以獲得近似的結(jié)果 i i 東北大學(xué)碩士學(xué)位論文 摘要 關(guān)鍵詞 文本分類 支持向量機 多類別支持向量機 特征選取 特征抽取 i i i 東北大學(xué)碩士學(xué)住論文 s u p p o r tv e c t o rm a c h i n e sf o rt e x t c a t e g o r i z a t i o n a b s t r a c t t e x tc a t e g o r i z a t i o ni saf o u n d a t i o n a lt e c h n i q u ef o ri n f o r m a t i o np r o c e s s i n g m a n y m a c h i n el e a r n i n gm e t h o d sh a v eb e e ni n t r o d u c e da n dd e e p l ys t u d i e df o rt h i sp o p u l a rt a s k s u p p o r tv e c t o rm a c h i n e sa g oas t a t e o f t h e a r tp a t t e r nc l a s s i f i c a t i o nm o d e l w h i c hh a sr e a d i l y v e r i f i e da p p r o p r i a t et ot e x tc a t e g o r i z a t i o n s v m so w ei t ss u c c e s st ot h ei n c o r p o r a t i o no f k e r n e lm e t h o d sa n de x c e l l e n tg e n e r a l i z a t i o ne f l o rw h i c ha s s u r e so v e r f i t t i n gp r o t e c t i o n i n t h i st h e s i s w ee x a m i n et h ea p p l i c a t i o no fs v m st ot h et a s ko ft e x tc a t e g o r i z a t i o n m a i n l yf o c u s i n go nt w op r o b l e m s c o n s t r u c t i o no fm u l t i c l a s ss v m sa n dd i m e n s i o nr e d u c t i o n f o rv e c t o r sw h i c hr e p r e s e n tt e x t sw i t hh i r g hd i m e n s i o n t os o l v et h ef i r s tp r o b l e m w ee x a m i n e f o u rm e t h o d s w h i e hr e d u c et h ec o n s t r u c t i o no fam u l t i c l a s sc l a s s i f i e ri n t ot h ep r o b l e mo f c o m b i n a t i o nw i t hm u l t ib i n a r yc l a s s i f i e r s i n c l u d i n go n e a g a i n s t r e s t d d a g p a i r w i s e m a x w i na n ds i g m o i d e x p e r i m e n t a lr e s u l t ss h o wt h a to n e a g a i n s t r e s tm e t h o do u t p e r f o r m s o t h e rt h r e eo n e s r e g a r d i n ge f f i c i e n c ya n de f f e c t i v e n e s s f o rt h es e c o n dp r o b l e m w eg r o u p e d d i m e n s i o nr e d u c t i o nm e t h o d si n t ot w od i s t i n c tk i n d s f e a t u r es e l e c t i o na n df e a t u r e e x t r a c t i o n w ee x a m i n et h r e es e l e c t i o nm e t h o d s i n c l u d i n gi n f o r m a t i o ng a i n z 2s t a t i s t i c a l d o c u m e n t sf r e q u e n c y a n dt w oe x t r a c t i o nm e t h o d si n c l u d i n gl a t e n ts e m a n t i c i n d e x i n g p r i n c i p a lc o m p o n e n ta n a l y s i s e x p e r i m e n t a lr e s u l t sv e i l f yt h ee f f e c t i v e n e s so ff e a t u r e e x t r a c t i o nf o rt h ed i m e n s i o nr e d u c t i o no fs v m s b u t o nt h ec o n t r a r y f e a t u r es e l e c t i o nd i d n o tp e r f o r mw e l la si td o e sw h e nc o m b i n e dw i t ho t h e rt r a d i t i o n a lc l a s s i f i e r s s u c ha sn a i v e b a y e s m o r e o v e r t ov e r i f yt h ea d v a n t a g eo fs v m so v e ro t h e rc l a s s i f i e r s w ee x a m i n et h e c o m p a r eo fs v m sa n ds o m ep o p u l a rc l a s s i f i e r s i n c l u d i n gr o c c h i o kn e a r e s tn e i g h b o r s n a i v eb a y e s a n dm a x i m u me n t r o p y i na c c o r d a n c ew i t ht h e o r e t i c a la n a l y s i s s v m sp e r f o r m b e s ta m o n ga l lt h ec l a s s i f i e r sw ee x a m i n e d s v m sw a sc l a i m e dt ob ea p p r o p r i a t et ot h et a s ko ft e x tc a t e g o r i z a t i o n b o mb e c a u s eo f k e r n e lm e t h o d sa n dt h ea b i l i t yo fo v e r f i t t i n gp r o t e c t i o n t h ec o m p a r a t i v ee x p e r i m e n t ss h o w i v 東北大學(xué)碩士學(xué)位論文 i ti st h es t a t e o f t h e a r tc l a s s i f i e ra n dw h e nc o m b i n e dw i t hf e a t u r ee x t r a c t i o nm e t h o d sf l s i a n dp c a h e r e t h ep e r f o r m a n c ea c h i e v e dc o u l db eb e t t e r k e yw o r d s t e x t c a t e g o r i z a t i o n s u p p o r t v e c t o rm a c h i n e s m u l t i c l a s ss u p p o r t v e c t o r m a c h i n e s f e a t u r es e l e c t i o n f e a t u r ee x t r a c t i o n v 獨創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是在導(dǎo)師的指導(dǎo)下完成的 論文中取得的研究成果除加 以標注和致謝的地方外 不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果 也不包括本人為 獲得其他學(xué)位而使用過的材料 與我一同工作的同志對本研究所做的任何貢獻均已在論 文中作了明確的說明并表示誠摯的謝意 學(xué)位論文作者簽名 糶瓣 簽字日期 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者和指導(dǎo)教師完全了解東北大學(xué)有關(guān)保留 使用學(xué)位論文的規(guī)定 即 學(xué)校有權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和磁盤 允許論文被查閱和借 閱 本人同意東北大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索 交 流 如作者和導(dǎo)師同意網(wǎng)上交流 請在下方簽名 否則視為不同意 學(xué)位論文作者簽名 導(dǎo)師簽名 簽字日期 簽字日期 東北大學(xué)碩士學(xué)位論文 第一章前言 第一章前言 1 1 研究背景 隨著9 0 年代初期開始 因特網(wǎng)的發(fā)展 人們面臨著的數(shù)據(jù)呈爆炸式增長 隨著因 特網(wǎng)的必展 網(wǎng)路上出現(xiàn)了越來越多的電子圖書館和在線數(shù)據(jù)庫可供人們自由的訪問和 獲取 在這種情況下 如何有效地組織數(shù)據(jù)以及對所需的數(shù)據(jù)進行查找 已經(jīng)成為一個 越來越熱門的研究領(lǐng)域 越來越多的信息處理技術(shù)被應(yīng)用來解決這個目前急需解決的問 題 已經(jīng)被應(yīng)用的技術(shù)包括信息檢索 i n f o n n a t i o n mr e t r i e v a l i r 信息抽取 i n f o r m a t i o n e x t r a c t i o n i e 文本摘要 t e x ts u m m a r i z a t i o n t s 以及文本分類 t e x t c a t e g o r i z a t i o n t c 等等 其中 文本分類任務(wù)是本篇論文所要討論的內(nèi)容 分類問 n n 以做如下定義 給定一個預(yù)先定義好的類別集合抄 y y 為待分類的每個樣 例x 賦予這個集合中的一個或多個類別 特別地文本分類 也叫做t e x t c l a s s i f i c a t i o n 或 者主題檢測t o p i cs p o t t i n g 可以如下定義 給定從某個確定但未知的分布中隨機抽樣 得到的訓(xùn)練數(shù)據(jù)集 兒 d c 其中d 是文本所屬的領(lǐng)域 領(lǐng)域決定數(shù)據(jù)的分布 c 是類別的集合 文本分類的任務(wù)就是要給依次得到的文本賦予一個或多個類別 到目 前為止 文本分類作為一項基礎(chǔ)性研究 應(yīng)用廣泛 已經(jīng)被應(yīng)用到基于受控詞典的自動 文摘 a u t o m a t i cd o c u m e n ti n d e x i n g 文本過濾 d o c u m e n tf i l t e r i n g 詞義消歧 w o r d s e n s ed i s a m b i g u a t i o n w s d 和文檔組織 d o c u m e n to r g a n i z a t i o n 等等 1 用來構(gòu)建分類器的方法有很多 根據(jù)實現(xiàn)的理論基礎(chǔ) 主要可以分為兩個大類 一 是基于知識工程的方法 二是基于統(tǒng)計和機器學(xué)習(xí)的方法 知識工程的系統(tǒng)在研究的早 期處于支配地位 直到8 0 年代末 人們在應(yīng)用這種方法的過程中發(fā)現(xiàn)了知識工程方法 的不足 才逐漸被統(tǒng)計和機器學(xué)習(xí)的方法所取代 知識工程方法主要的不足在于利用這 種方法構(gòu)建一個系統(tǒng)需要屬于待分類的領(lǐng)域的專家的大量參與 利用領(lǐng)域?qū)＜业膶I(yè)知 識 采用人工的方式書寫大量的分類規(guī)則 然后對這些規(guī)則進行組合 形成最終的分類 系統(tǒng) 如此構(gòu)建的構(gòu)建的基于人工知識的規(guī)則系統(tǒng)雖然可以在有限的領(lǐng)域內(nèi)獲得很好的 性能 但其致命的弱點在于它們是領(lǐng)域相關(guān)的系統(tǒng) 利用了大量人工構(gòu)建的分類器沒有 辦法從一個領(lǐng)域簡便地移植到另一個領(lǐng)域 同時 因為規(guī)則沖突的原因以及人力資本的 角度考慮 利用領(lǐng)域?qū)＜襾順?gòu)建多領(lǐng)域的分類器又是不實際的 這些缺陷嚴重限制了規(guī) 1 東北大學(xué)碩士學(xué)位論文第一章前言 則系統(tǒng)的應(yīng)用與發(fā)展 由h a y e s 構(gòu)建的c o n s t r u e 是規(guī)則系統(tǒng)的一個典型代表 2 為了克服知識工程方法的諸多不足 使文本分類真正做到可用 從9 0 年代早期開 始 統(tǒng)計和機器學(xué)習(xí) m a c h i n el e a r n i n g m l 的方法越來越普遍地被應(yīng)用到文本分類 這個任務(wù)中來 剛好克服知識工程方法的不足 基于學(xué)習(xí)的分類器可以做到與領(lǐng)域的無 關(guān) 只要在訓(xùn)練過程中給定訓(xùn)練所需數(shù)據(jù) 分類器就可以做到自動地學(xué)習(xí) 由一個領(lǐng)域 轉(zhuǎn)移到另一個領(lǐng)域時 分類器不需要重新構(gòu)建 人力只需要集中在針對新領(lǐng)域的數(shù)據(jù)構(gòu) 建上面來 從這個角度講 機器學(xué)習(xí)方法也常常被稱為是基于語料庫和統(tǒng)計的方法 從 語言學(xué)角度講 一個文本語料庫是一個巨大的并且常常是帶有結(jié)構(gòu)的文本 如今 通常 是以電子的形式存儲以及處理 構(gòu)建一個基于學(xué)習(xí)的分類器的過程可以分為三個步驟 1 首先需要構(gòu)建一個足夠大的用于分類器訓(xùn)練的語料庫 要求帶有必需的標注信息 2 從給定的語料庫中學(xué)習(xí)分類器的參數(shù) 3 當給出一個新的樣例時 用學(xué)習(xí)得到的分類 器進行分類 如今 一般情況下 如果沒有特殊地說明 我們講 文本分類系統(tǒng) 指是的基于機 器學(xué)習(xí)方法的自動文本分類系統(tǒng) 在本論文的剩余章節(jié)中 如無特殊說明 我們將依此 慣例 1 2 研究現(xiàn)狀 自從統(tǒng)計和機器學(xué)習(xí)的方法被用來解決文本分類任務(wù)以后 越來越多的研究人員和 研究機構(gòu)對文本分類的各個方面進行了非常深入的研究 i 3 4 在中文處理領(lǐng)域中 同樣是如此 1 2 1 特征表示 特征表示是文本分類任務(wù)中非常重要的一項 語料庫中的任何數(shù)據(jù)都必須先表示為 分類器可以處理的格式 目前常用來表示特征的單元包括 基于詞的特征 1 3 基于短語的特征 5 6 基于詞簇的特征 7 8 1 1 9 1 0 中文文本分類中的n 元文法作為特征f 1 1 在文本分類任務(wù)中 向量空間模型 v e c t o rs p a c em o d e l v s m 1 2 是n 前最流行的表 示方法 這種方法最開始被用于信息檢索中用來表示查詢 q u e r y g l i s 2 2 檔 向量空間模型 2 東北大學(xué)碩士學(xué)位論文 第一章前言 已經(jīng)被證明同樣可以用在文本分類中用于分類文本的表示 用這種表示方法 每個文檔 d 都可以表示為由一個一個 對 p a i r 幕示成的向量 d 她 w l l f w 2 l f 其中 f w i d l i i n 是對應(yīng)第i 個特征的 對 t 表示特征的編號 w u 表示特征 的權(quán)重 n 是整個特征集合的大小 也就是特征的個數(shù) 一旦文本用向量空間模型表示 成這種格式 所有可以對向量進行的操作都可以應(yīng)用到文本上來 例如聯(lián)合 刪除 比 較等操作 但是另一方面 用向量空間模型得到的向量表示往往具有非常高的維數(shù) 通常來講 特征越多 我們對文本的表示就更準確 但從另一個方面講 得到的向量維數(shù)也就越高 這樣的高維特征對某些分類器來說會因為巨大的計算復(fù)雜度而導(dǎo)致 維數(shù)災(zāi)難 的問題 例如 在以詞做為特征的時候 在去除停用詞以后 得到的不同詞的個數(shù)可能有幾萬 十幾萬維 甚至達到上百萬 這對一些分類器來講 是難以處理的高維特征空間 因此 在應(yīng)用分類器處理數(shù)據(jù)之前通常需要降維 d i m e n s i o nr e d u c t i o n 處理 而且 降維還 有另外一個好處 可以部分解決過度擬合 o v e r f i t t i n g 的問題 降維處理的目標就是 要在降低特征空間維數(shù)的同時 要避免分類的性能發(fā)生明顯的降低 根據(jù)方法的理論基 礎(chǔ)進行分類 降維方法可以分為特征選取 f e a t u r es e l e c t i o n f s 和特征抽取 f e a t u r e e x t r a c t i o n f e 兩大類 3 1 1 3 特征選取方法根據(jù)某種對特征 好 或者 壞 的衡量 從原有特征集合中選擇合適的子集 特征選取方法包括文檔頻度 d o c u m e n tf r e q u e n c y d f 互信息 m u t u a li n f o r m a t i o n m i 信息增益 i n f o r m a t i o ng a i n i g 特征頻度 t e r m f r e q u e n c y t f 特征熵 f e a t u r ee n t r o p y t e 特征強度 t e r ms t r e n g t h t s 等等 3 特征抽取與特征選取有本質(zhì)的區(qū)別 它不是從特征集合中抽取一個子集 而是尋求從原 始空間向某個低維空間的映射 在降維的同時盡可能的保留原有的信息 特征抽取方法 包括兩大部分 1 從原始特征中抽取新特征 2 用新的特征表示文本 特征抽取方法 包括潛在語義索引 l a t e n ts e m a n t i ci n d e x i n g l s i 1 4 主成分分析 p r i n c i p a lc o m p o n e n t a n a l y s i s p c a 等等 1 1 2 分類器 分類器是文本分類系統(tǒng)中的核心成分 到目前為止 許多機器學(xué)習(xí)的方法已經(jīng)被應(yīng) 用到文本分類任務(wù)中來 這其中包括核心向量法 r o c c h i o k 最近鄰居法 kn e a r e s t n e i g h b o r s k n n 最大熵模型 m a x i m u me n t r o p y m e 樸素貝葉斯 n a i v eb a y e s n b 3 東北是學(xué)碩士學(xué)位論文第一童前言 已經(jīng)被證明同樣可以用在文本分類中用于分類文本的表示 用這種表示方 杰 每個文檔 d 都可以表示為由一個一個 對 p a i o 表示成的向量 d r w 1 0 w 2 l n 其中 o h l i sn 是對應(yīng)第i 個特征的 對 t 表示特征的編號 o 表示特征 的權(quán)重 n 是整個特征集合的大小 也就是特征的個數(shù) 一旦文本用向量空間模型表示 成這種格式 所有可以對向量進行的操作都可以應(yīng)用到文本上來 例如聯(lián)合 刪除 比 較等操作 但是另一方面 用向量空間模型得到的向量表示往往具有非常高的維數(shù) 通常來講 特征越多 我們對文本的表示就更準確 但從另一個方面講 得到的向量維數(shù)也就越高 這樣的高維特征對某些分類器來說會因為巨大的計算復(fù)雜度而導(dǎo)致 維數(shù)災(zāi)難 的問題 例如 在以詞做為特征的時候 在去除停用詞以后 得到的不同詞的個數(shù)可能有幾萬 十幾萬維 甚至達到上百萬 這對 些分類器來講 是難以處理的高維特征空間 網(wǎng)此 在應(yīng)用分類器處理數(shù)據(jù)之前通常需要降維 d i m e n s i o nr e d u c t i o n 處理 而且 降維還 有另外一個好處 可以部分解決過度擬合 o v e r f i t t i n g 的問題 降維處理的目標就是 要在降低特征空間維數(shù)的同時 要避免分類的性能發(fā)生明顯的降低 根據(jù)方法的理論基 礎(chǔ)進行分類 降維方法可以分為特征選取 f e a t u r es e l e c t i o n f s 和特征抽取 f e a t u r e e x t r a c t i o n f e 兩大類 3 1 3 特征選取方法根據(jù)某種對特征 好 或者 壞 的衡量 從原有特征集合中選擇合適的于集 特征選取方法包括文檔頻度 d o c u m e n tf r e q u e n c y d f 互信息 m m u a l i n f o r m a t i o n m i 信息增益 i n f o r m a t i o n g a i n i g 特征頻度 t e r m f r e q u e n c y t f 特征熵 f e a t u r e e n t r o p y t e 特征強度 t e r ms t r e n g t h t s 等等 3 特征抽敬與特征選取有本質(zhì)的區(qū)別 它不是從特征集合甲抽取一個子集 而是尋求從原 始空同向某個低維空間的映射 在降繼的同時盡可能的保留甄有的信息 特征抽耿方法 包括兩大部分 1 從原始特征中抽取新特征 2 用新的特征表示文本 特征抽馭方法 包括潛在語義索引 l a t ts e m a n t i ci n d e x i n g l s d f l a 主成分分析 州n c i p a ic o m p o n e n t a v a l y s i sp c a 等等 1 1 2 分類器 分類器是文本分類系統(tǒng)中的核心成分 到目前為止 許多機器學(xué)習(xí)的方法已經(jīng)被應(yīng) 用到文本分類任務(wù)中來 這其中包括核心向量法 r o c c h i o k 最近鄰居法 kn e a r e s t n e i g h b o r sk n n 最大熵模型 m a x i m u m e n l m p y m e 樸素貝葉斯 n f f v e b a y e s n b n e i g t l b o r sk n n 最大熵模型 m a x i m u m e n t m p y m e 樸素貝葉斯 n a f v e b a y e s n b 3 東北大學(xué)碩士學(xué)位論文第一章前言 支持向量機 s u p p o r tv e c t o r m a c h i n e s v m 等 1 在下面的章節(jié)中 我們將詳細地介 紹這些分類器 在文本分類任務(wù)中 這些分類模型都已經(jīng)被深入地研究和廣泛地應(yīng)用 其中 支持向量機作為一個有監(jiān)督的學(xué)習(xí)方法 在文本分類任務(wù)中更是取得了顯著的成 功 支持向量機是本文討論的重點 為了描述的方便 我們將上述除了支持向量機以外 的模型統(tǒng)稱為傳統(tǒng)模型 支持向量機最早是由v a p n i k 和他的同事提出 其理論基礎(chǔ)是基于結(jié)構(gòu)風(fēng)險最小化 s t r u c t u r e dr i s km i n i m i z a t i o n s r m 1 5 結(jié)構(gòu)風(fēng)險最小化是統(tǒng)計學(xué)習(xí)理論 s t a t i s t i c a l l e a r n i n gt h e o r y s t 1 6 中一項重要的推導(dǎo)原則 同時 支持向量機的成功在很大程度 上還歸因于模型應(yīng)用核方法的能力 核方法的應(yīng)用可以使分類器通過一種隱式的非線性 映射 在高維 甚至可能是無限維 的特征空間中進行分類 與原始空間相對應(yīng) 映射 得到的高維空間我們把它叫做 特征空間 f e a t u r es p a c e 實際上 在泛函理論中 特征空間叫做再生核希爾伯特空間 r e p r o d u c i n gk e r n e lh i l b e r ts p a c e 支持向量機的 基本思想就是在特征空間中 尋找 個分割超平面將兩類數(shù)據(jù)線性分類 同時尋求最大 化數(shù)據(jù)點到超平面的最小距離 與支持向量機相關(guān)的研究內(nèi)容包括多類別支持向量機的 構(gòu)建 核函數(shù)的選擇 支持向量機的特征選擇 以及泛化錯誤界等理論研究 等等 支持向量機在模式識別 p a t t e r nr e c o g n i t i o n p r 領(lǐng)域具有廣泛的應(yīng)用 例如數(shù)字 識別 d i g i tr e c o g n i t i o n 人臉識別 f a c er e c o g n i t i o n o c r 等 最近 支持向量 機更是被用來解決文本分類的任務(wù) 在下一章中 我們將詳細介紹如何用支持向量機構(gòu) 建分類器從而解決分類問題 i 2 3 文本分類公開評測 在2 0 0 3 年3 月 北京大學(xué) p e m n gu n i v e r s i t y 組織了 中文網(wǎng)頁的自動分類競賽 這次競賽吸引了中國大陸十支隊伍參加 組織方提供了統(tǒng)一的訓(xùn)練和測試數(shù)據(jù) 整個數(shù) 據(jù)集包括1 3 9 7 3 個中文網(wǎng)頁 其中的1 1 0 5 9 個用于訓(xùn)練 其余的2 9 1 4 個網(wǎng)頁用于測 試用 所有的網(wǎng)頁由人工按1 1 個類別進行了標注 在公開評測的時候 主辦方現(xiàn)場下 載4 4 個頁面用于最后系統(tǒng)的評測 在2 0 0 3 年和2 0 0 4 年 中國科學(xué)院計算所 h l s t i t u t eo f c o m p u t i n gt e c h n o l o g y c h i n e s e a c a d e m yo fs c i e n c e 連續(xù)兩年舉辦8 6 3 自動文本分類評測 這兩次評測 分別有五家 和九家不同的單位參加 舉辦方提供的數(shù)據(jù)集包括3 6 0 0 個文本 由人工根據(jù)中國圖書 分類法 c h i n e s el i b r a r yc a t e g o r i z a t i o n 1 7 分為3 6 類 不包括類別t i i 技術(shù)類 一4 末北大學(xué)碩士學(xué)位論文 第一章前言 類別z 綜合圖書類 在2 0 0 3 年 除訓(xùn)練語料外 提供額外的3 6 0 0 個文本作為測試 語料用 面2 0 0 4 年的訓(xùn)練語料則以2 0 0 3 年的測試語料來充當 1 3 本文貢獻 支持向量機的理論及其應(yīng)用是一個非常廣泛的研究領(lǐng)域 希望在一篇論文中涉及到 所有的研究問題是不現(xiàn)實的 在本論文中 我們著眼于為文本分類任務(wù)提供一種解決方 法 因此我們把考察的重點放在在構(gòu)建基于支持向量機的分類器的過程中所遇到的兩個 關(guān)鍵性的問題 1 支持向量機是 種二類分類器 而現(xiàn)實生活中 文本分類任務(wù)都是 多類分類問題 因此如何高效地構(gòu)建一個多類別的支持向量機就是我們必須考慮的第一 個關(guān)鍵問題 2 在某些實時性要求比較高的應(yīng)用環(huán)境下 文本表示的高維性質(zhì)也不是 一個可以忽略的問題 因此降維方法的研究是本文的另 個研究重點 下面將詳細解釋 支持向量機從理論上分析 只為尋找某個分類超平面可以將兩類數(shù)據(jù)以最大的邊界分類 開 本質(zhì)上講 支持向量機是一個二類分類模型 但是 我們大家都知道 在現(xiàn)實生活 中的大多數(shù)分類問題都是多類分類問題 其中文本分類任務(wù)也是如此 因此 在應(yīng)用支 持向量機解決一個分類問題時 所出現(xiàn)的第一個問題就是如何構(gòu)建多類別支持向量機 目前有兩種常用的多類別分類器構(gòu)建方法 一種是把多類別分類問題分解為多個二類分 類問題 然后再通過對這多個二類分類器的分類結(jié)果進行組合 得到最終的分類結(jié)果 另一種方法稱之為基于核的多類別支持向量機i r a 基于核的多類別支持向量機是對支 持向量機模型的一種泛化 它為每個類別構(gòu)建專屬于該類別的權(quán)向量和核函數(shù) 基于核 的支持向量機 具有較深的理論基礎(chǔ) 對初學(xué)者來說比較難以掌握 構(gòu)建基于核的多類 別分類器更是不容易實現(xiàn) 出于簡單程度和構(gòu)建的效率方面考慮 在本論文中 我們將 著重介紹前一種實現(xiàn)方法 對現(xiàn)在常用的多種具體的實現(xiàn)方法進行深入的比較研究 本 文的第二個貢獻來自于文本分類任務(wù)的本身性質(zhì) 如上文所提 文本通常以向量形式表 示 向量空間模型 這通常會導(dǎo)致非常高維的向量空問 這樣的高維空間對于傳統(tǒng)的 分類模型 例如樸素貝葉斯模型 即使不是不可能操作 起碼也是非常困難的一件事 對于這些個模型 在應(yīng)用分類器對數(shù)據(jù)進行操作之前 降維都是不可避免的一個階段 降維除了簡化計算復(fù)雜度之外 還有另外的作用 這就是說 通過適度的降維 我們可 以去除部分噪音 相應(yīng)的 分類性能也能得到改善 對于支持向量機而言 因為支持向 量機的解具有稀疏性 支持向量機的計算復(fù)雜度主要地取決于樣例的個數(shù) 而不是特征 的維數(shù) 特征維數(shù)同樣具有影響 但不是主要的因素 但對于某些實時性要求比較高 5 東北大學(xué)碩士學(xué)位論文 第一章前言 的應(yīng)用 因為采用降維技術(shù)而得到的時間節(jié)省也是非?？捎^的 因此 我們同樣考察了 降維方法與支持向量機組合效果 如上文所述 降維方法主要分為特征選取和特征抽取 兩大類 通過實現(xiàn) 我們將證明 特征選取不適用于支持向量機模型 雖然在與其它分 類器聯(lián)合應(yīng)用時 特征選取方法往往達到理想的效果 另一方面 我們發(fā)現(xiàn)特征抽取方 法可以在顯著降維的同時 保持支持向量機的分類性能不發(fā)生明顯的降低 甚至有時候 還可以改善分類的性能 因此 當特征降維是文本向量預(yù)處理中一項不可避免的階段時 我們可以把更多注意力放在特征抽取的方法上 1 4 相關(guān)工作 研究人員已經(jīng)在如何將支持向量機應(yīng)用于文本分類這個問題上進行了深入的研究 在 1 9 j o a c h i m s 深入地討論了支持向量機適用于文本分類任務(wù)的理論基礎(chǔ) 根據(jù) j o a c h i m s 的觀點 正是文本本身的性質(zhì)決定了支持向量機對文本分類任務(wù)的適用性 如 上所述 一個文本被表示成向量以后 其維數(shù)總是非常地高 可以與詞匯表的大小基本 相同 大多數(shù)傳統(tǒng)的分類模型因為計算復(fù)雜度等原因?qū)θ绱烁呔S的向量空間無法進行處 理 與此相反的是 支持向量機的解具有稀疏性 可以在高維空間 通過核函數(shù)的隱式 映射 甚至是無限維 中構(gòu)建分類器 某此分類器 例如 樸素貝葉斯 必須做的獨立 性假設(shè)對支持向量機來講是沒有必要的 因此 支持向量機可以充分利用特征之間的相 互信息 而這種相互信息往往是被樸素貝葉斯模型所不得不忽略的 而且 支持向量機 還有另外的優(yōu)勢 模型本身具有防止過度擬合的機制 因為支持向量機泛化錯誤的上界 并不由特征向量的維數(shù)所決定 這也是支持向量機可以利用核方法做隱式地空間映射 在更高維空間中表示文本 更好分類的原因 不幸地是 j o a c h i m s 僅僅強調(diào)了支持向量 機的魯棒性 而沒有闡述向量空間的維數(shù)對分類效果的影響 在本論文后面的章節(jié)中 我們將看到 向量的維數(shù)或多或少地影響著模型的計算復(fù)雜度 在本論文后面的章節(jié)中 第二章將對支持向量機模型本身以及必要的理論基礎(chǔ)進行 介紹 這是我們進一步介紹我們工作的必要的基礎(chǔ)知識 支持向量機是一個相對來講比 較復(fù)雜的模型 尤其是當它與統(tǒng)計學(xué)習(xí)理論聯(lián)合在一起考慮時候 更加復(fù)雜 因此 本 章將把主要地討論放在模型本身 在第三章中 我們將討論如何通過對多個二類分類器 的組合來實現(xiàn)多類別支持向量機模型 這是一種簡單而高效率的實現(xiàn)方法 基于核的多 類別支持向量機是另一種實現(xiàn)方法 但本文將不予討論 為了驗證支持向量機相對于其 它模型的優(yōu)越性 我們將在第四章將支持向量機與四個傳統(tǒng)分類模型進行比較 這四個 6 東北大學(xué)碩士學(xué)位論文第一章前言 分類模型包括核心向量法 樸素貝葉斯模型 最大熵和k 最近鄰居 這都是目前在文本 分類任務(wù)中最常用的模型 在第五章中 我們將討論第二項主要工作 降維的研究 考 察特征選取和特征抽取方法 究竟哪種方法適用于支持向量機的降維 最后一章是我們 的結(jié)論以及對未來工作的展望 7 一 東北大學(xué)碩士學(xué)位論文第二章支持向量機模型 第二章支持向量機模型 支持向量機模型最初由c o r t e s 和v a p n i k 首先提出 1 5 最初始的時候 為了與人工 神經(jīng)元網(wǎng)絡(luò) n e u r a ln e t w o r k 相對照 該模型被命名為支持向量網(wǎng) s u p p o r tv e c t o r n e t w o r k 支持向量機模型是基于結(jié)構(gòu)風(fēng)險最小化歸納原則的學(xué)習(xí)算法 結(jié)構(gòu)風(fēng)險最小 化可以表示如下 喇觀荊 掣f 罌 仁 上式右側(cè)的第一項 我們把它叫做經(jīng)驗風(fēng)險項 第二項是泛化錯誤的上界 從這個 式子可以看出 結(jié)構(gòu)風(fēng)險最小化 以及在此基礎(chǔ)上的支持向量機模型試圖尋找訓(xùn)練錯誤 經(jīng)驗風(fēng)險 和泛化錯誤之間的一種均衡 支持向量機的目標就是要尋找一種高效的學(xué)習(xí)算法 可以在高維空間中尋找分類超 平面 以達到分類的良好性能 而且 支持向量機的成功也很大因素上歸因于其理論基 礎(chǔ)一統(tǒng)計學(xué)習(xí)理論 這個理論基礎(chǔ)可以使支持向量機避免過度擬臺的問題 支持向量機模型可以分解成三個主要的模塊 分別是 線性分類器 核函數(shù) 和實 際應(yīng)用過程中所必需的實用優(yōu)化算法 在后面的各節(jié)中 我們將依次對這三個模型進行 詳細地介紹 在此之前 我們將介紹一個邊界 m a r g i n 的概念 通常來講 邊界可以 分為兩類 函數(shù)邊界 f m l c t i o n a lm a r g i n 和幾何邊界 g e o m e t r i cm a r g i n 函數(shù)邊界 特指函數(shù)的輸出值 與之相對應(yīng)的是 幾何邊界定義為在對權(quán)向量做了歸一化之后的函 數(shù)邊界 從直觀角度分析 被分類的兩類數(shù)據(jù)如果離分類面距離越遠 則得到的分類模 型的魯棒性要更強 因為同一個函數(shù)的函數(shù)邊界的數(shù)值會隨著權(quán)值的調(diào)整而發(fā)生改變 因此函數(shù)邊界不適用于支持向量機模型 在該模型中 采用幾何邊界作為邊界的衡量方 法 根據(jù)統(tǒng)計學(xué)習(xí)理論 支持向量機模型的泛化錯誤上界與幾何邊界的大小成反l l 6 1 本文將不作具體討論 因此我們把函數(shù)邊界的值固定為1 函數(shù)邊界為l 的超平面 有時也被稱為規(guī)范超平面 在此條件下去優(yōu)化幾何邊界值 這個最優(yōu)化過程 可以等 價地表示為最小化權(quán)向量的長度的過程 2 1 最大邊界分類器 最大邊界分類器是最簡單的支持向量機模型 也是第一個提出的分類器模型 這個 一8 東北大學(xué)碩士學(xué)位論文 第二章支持向量機模型 分類器模型是一種理想化的模型 只適用于兩類數(shù)據(jù)線性可分的情況 給定某個確定但 是未知的分布 經(jīng)過獨立同分布地抽樣過程抽樣得到的數(shù)據(jù)集 戤 m l x 虬l(fā) 0 兒 這個數(shù)據(jù)集被認為是線性可分的 如果存在權(quán)向量w 和標 量b 使下面的不等式成立 w 6 1 i fy f 1 矽 x i b 一1 i fy 一1 這個線性可分的定義可以簡化為m 一 6 1 為了計算幾何邊界 必須使函數(shù)邊 界的值為1 這就意味著臨界點必須滿足 幾何邊界 就是滿足上述條件的分類器所對應(yīng)的函數(shù)邊界 三 南一 一镢盯 贏 一 一 注意到這里的x 指的是正訓(xùn)練數(shù)據(jù)中的臨界點 z 一指的是負訓(xùn)練數(shù)據(jù)中的臨界點 如 9 一 東北大學(xué)碩士學(xué)位論文 第二章支持向量機模型 圖2 i 最大分界支持向量機 f i g u r e 2 im a x i m a lm a r g i ns u p p o nv e c t o rm a c h i n e s 利用上面的定義 支持向量機的問題就可以轉(zhuǎn)化為一個數(shù)學(xué)上的最優(yōu)化問題 m i n i m i z e 彬 s u b j e c t t o y f 礦 x 6 1 i 1 1 上述等式被稱為優(yōu)化問題的原始式子 為了得到原始式的對偶形式 我們首先要得到原 始的拉格朗日 l a g r a n g i a n 式 如下所示 工 彬 6 a 丟 一圭q 陟 x 6 一1 為了求解對偶式 我們首先得對w 和b 進行求導(dǎo) 并且根據(jù)最優(yōu)化理論中最優(yōu)解的必 要條件 將得到的求導(dǎo)式固定為0 然后將式子回代到原函數(shù)中 如此則得到最優(yōu)化問 題的對偶表示形式 m a x i m i z e 矽 a a 一百1 乙i 扣 y i 乃a i a 勺 s u b j e c tt o 二y f a j o 2 2 a o i 1 因此 支持向量機的訓(xùn)練過程就可以看作是解一個優(yōu)化問題的對偶式子的二次規(guī)劃過 程 注意到分類超平面只由不為0 的拉格郎日乘子所對應(yīng)的訓(xùn)練樣例確定 對應(yīng)的拉格 1 0 一 苧型望堂皇堂苧墮圭 莖三主叁量魚重i 墮型 郎目乘子不為0 的訓(xùn)練樣例 我們把它叫做支持向量 這也是支持向量機 g 字的由來 在圖2 1 中 支持向量用灰色的方格子表示 從理論角度看 任何可以解二次規(guī)劃問題 的解法都可以用來訓(xùn)練支持向量機 但因為在實際應(yīng)用 所要處理的數(shù)據(jù)量一般比較龐 大 導(dǎo)致大多數(shù)的優(yōu)化方法在實際應(yīng)用中并不可行 在2 4 節(jié)中 我們將介紹一種名為 序貫最小優(yōu)化 s e q u e n t i a lm i n i m i z a t i o no p t i m i z a t i o n s m o 的優(yōu)化算法 這也是在實際 應(yīng)用構(gòu)建支持向量機時通常采用的訓(xùn)練算法 正如我們已知的 最大邊界支持向量機只能用來處理兩類數(shù)據(jù)線性可分的理想情 況 但從所周知 在現(xiàn)實生活中 因為噪音或是表示樣例的特征選擇等等問題 要處理 的兩類數(shù)據(jù)往往具有交叉和重疊 在這種情況下 最大邊界支持向量機并不適用 會導(dǎo) 致極差的效果 但從另一方面來看 最大邊界支持向量機給我們提供了 個很好的出發(fā) 點 它揭示了這些學(xué)習(xí)算法的所有核心特性 成為了進一步構(gòu)建復(fù)雜 實用模型的基礎(chǔ) 性模塊 下面我們將介紹一種實用的支持向量機模型 也就是所謂的 r 軟邊界分類器 s o f tm a r g i nc l a s s i f i e r 2 2 軟邊界分類器 正如我們在前一節(jié)中已經(jīng)討論的 最大邊界支持向量機在實際的存在噪音數(shù)據(jù)的應(yīng) 用環(huán)境中并不實用 但它能做為進一步研究和構(gòu)建復(fù)雜實用系統(tǒng)的基礎(chǔ) 一個實用的支 持向量機模型必須對可能遇到的嗓音數(shù)據(jù)具有魯棒性 容忍噪音數(shù)據(jù)的存在 反應(yīng)到優(yōu) 化問題上來 就是要使限制條件具有 定的彈性 n c k 軟邊界分類囂在最大分界分類 器的基礎(chǔ)上引入了松馳因子的概念 s u b j e c t t o 兒 矽 x i 6 1 一f i f 1 一 f 告i2u z 1 這里的島這里松馳因子 通過它的調(diào)整 松馳優(yōu)化問題的約束 從而使模型對噪間數(shù)據(jù) 具有較強的容忍 邊界的松馳向量指的是將所有松馳因子集合到一起所形成的向量 一 共有兩種軟邊界模型的存在 其中第 個是基于松馳向量的2 范式 m i n i 啊吃 c 等 s u b j e c t t o y i x 6 1 一虧 i l 繭 o i i 1 1 東北大學(xué)碩士學(xué)位論文 第二章支持向量機模型 第二個模型基于松馳向量的1 范式 m i n i m i s 吒 w 礦 c 0 s u b j e c t t o y i z 6 1 一專 i 1 裊 o i 1 在這兩種情況下 目標函數(shù)都叫做軟邊界 常量c o 用于控制訓(xùn)練錯誤最小化和最大 化邊界之間的平衡 在本論文中 我們將只討論l 一范式的情況 因為這種情況得到的模 型更適合于解決模式識別領(lǐng)域的問題 當然也包括文本分類任務(wù)的問題 1 一范式優(yōu)化問 題所對應(yīng)的拉格朗日式子可以表示如下 形 6 a y 委 c 步 i z 7 一圭a i v 6 一1 鼻 一圭n 岳 扛 f 1 同樣的 通過對 眚和b 的求導(dǎo) 并將求導(dǎo)式右側(cè)固定為0 代回原式以后 可咀得到 原始優(yōu)化問題的對偶形式 上 6 掌 y 圭o i z y y i o i o i 葺 勺 i 1 i j l s u b j e c tt o y f a o a 0 i 1 f 2 3 上面得到的1 范式最優(yōu)化式子 對應(yīng)的支持向量機模型隱式地考慮o 1 損失函數(shù)的情況 這種損失函數(shù)在分類正確時 損失值為0 否則損失為l 這神損失函數(shù)適用于分類問 題 但對一些自然語言處理任務(wù) 例如自然語言句法解析中 一棵與正確結(jié)果只有細微 差別的解析樹 它的損失函數(shù)就與另一棵與正確結(jié)果明顯不同的解析樹區(qū)別開來 如果 用的都是o 1 損失 顯然無法有效地區(qū)分這兩種錯誤的解析結(jié)果 這個問題 我們可以 根據(jù)損失的大小對松馳變量的進行調(diào)節(jié) 這樣就可以將o 1 損失的情況泛化到可以使用 任何損失函數(shù)的情況 具體來講 可以有兩種做法 第一 對違背約束條件的式子乘上 損失函數(shù)以作為懲罰 第二 對松馳變量乘上損失值大小的倒數(shù)來調(diào)節(jié)松馳變量值的大 小 得到的式子可以表示如下 1 2 東北大學(xué)碩士學(xué)位論文 第二章支持向量機模型 m i n l h w t2 魯豁 v i v j 剛y t 哪y 小豳 2 3 核方法 從模型角度來看 線性學(xué)習(xí)算法存在著表示能力不足的問題 通常來講 現(xiàn)實生活 中的復(fù)雜應(yīng)用要求表示能力比線性函數(shù)更強的假設(shè)空間 從