（計算機應(yīng)用技術(shù)專業(yè)論文）二階段文本分類器及分類在推薦系統(tǒng)中的應(yīng)用.pdf

摘要 文本分類在文本挖掘和信息檢索系統(tǒng)中發(fā)揮著重要的作用。這種技術(shù)可以改 善檢索性能、提供導航瀏覽機制、發(fā)現(xiàn)相似文本等。因此，文本分類已成為一 種處理和研究文本的重要技術(shù)。 目前，基于統(tǒng)計和機器學習的文本分類算法已經(jīng)比較成熟，但可以考慮通過 某種方式引入其他方法來改進分類效果，比如下面所提的統(tǒng)計方法。分類算法除 了在文本挖掘和信息檢索系統(tǒng)中發(fā)揮著重要的作用外，還可以考慮在電子商務(wù)個 性化推薦系統(tǒng)中的應(yīng)用。針對上述二方面，本人做了以下工作i 第一：提出了基于k m e a n s 的二階段多類s v m 分類方法。該方法分為二個 階段，第一階段采用k m e a n s 聚類，在聚類結(jié)束以后，抽樣調(diào)查每個小類的分類 精準度，完全分對的類可以不必進行第二步的分類，從而降低了已經(jīng)聚類正確的 實例再次分類的風險：第二階段采用l i b s v m 來進行分類。本文在理論論證后， 使用中英文語料，通過實驗證實該方法切實可行，相較于直接使用l i b s v m 進 行分類，分類準確度分別提高了9 3 5 和1 5 。 第二：用戶個性化推薦是電子商務(wù)領(lǐng)域中的研究熱點與核心技術(shù)，近年來得 到了廣泛的關(guān)注和快速的發(fā)展，本文將分類技術(shù)引入推薦系統(tǒng)。文中提出了基于 分類的用戶多興趣個性化推薦方法。該方法分為二個模塊，第一模塊是長期興趣 模塊( l i m ) ，針對用戶多興趣的特征，通過分類來提高推薦準確度；第二是短 期興趣模塊( s i m ) ，針對用戶短期興趣的專注性，引入w e b 日志上下文分析的 方法。最后，本文分別對l i m 和s i m 進行了實驗證實，證實該方法切實可行， 相較于傳統(tǒng)方法，推薦準確度及用戶滿意度都得到了較好提升。 關(guān)鍵詞：文本分類，k 。m e a n s ，二階段多類s v m 分類方法，用戶個性化推薦 v a b s t r a c t t e x tc l a s s i f i c a t i o np l a y sa ni m p o r t a n tr o l ei nt e x tm i n i n ga n di n f o r m a t i o n r e t r i e v a ls y s t e m s i tc a l li m p r o v et h er e s u l to fq u e r i e s ；p r o v i d ei n t u i t i v en a v i g a t i o na n d b r o w s i n gm e c h a n i s m s ；a n df i n ds i m i l a rt e x t s t h e r e f o r e ，t h et e x tc l a s s i f i c a t i o nh a s b e c o m ea ni m p o r t a n tt e c h n o l o g yt or e s e a r c ha n dt r e a tt h et e x t a tp r e s e n t ，b a s e do nt h es t a t i s t i c sa n dm a c h i n el e a r n i n gt e x tc a t e g o r i z a t i o n a l g o r i t h mh a sm o r em a t u r e ，b u tc a nc o n s i d e rw a yi n t oo t h e rw a y st oi m p r o v e c l a s s i f i c a t i o ne f f e c t , f o re x a m p l es t a t i s t i c sm e t h o db e l o w e x c e p ti nt h et e x t c l a s s i f i c a t i o na l g o r i t h ma n di n f o r m a t i o nr e t r i e v a ls y s t e mp l a y sa ni m p o r t a n tr o l e ， c l a s s i f i c a t i o na l s ot a i lp l a yar o l ei np e r s o n a lr e c o m m e n d e rs y s t e m b a s e do nt h e a b o v ei s s u e s ，id ot h ef o l l o w i n gw o r k ： 1 i nt h i sp a p e r , t w os t a g e sm u l t i - l a b e ls v mc l a s s i f i e rb a s e do nk - m e a n sh a s b e e np r o p o s e d t h i sm e t h o dd i v i d e si n t ot w os t a g e s ，t h ef i r s ts t a g eu s e st h ek - m e a n s c l u s t e r , e n h a n c e st h ec l u s t e ra c c u r a c yt h r o u g ht h es a m p l i n gp r e c i s i o n ；，i nt h ee n d ，t h e c l u s t e rs a m p l i n gs u r v e yo fe a c hs m a l lc l a s s i f i c a t i o na c c u r a c yo fc l a s si fi ti sf u l l r i g h t ， t h es e c o n ds t e pi s n tb ec l a s s i f i e d ，t h e r e b yh a sb e e nr e d u c e do n c ea g a i na ne x a m p l e o ft h ec o r r e c tc l u s t e r i n go fr i s kc l a s s i f i c a t i o n ；t h es e c o n ds t a g eu s e sl i b s v mt oc a i t y o nt h e c l a s s i f i c a t i o n t h i sa r t i c l ea f t e rt h e o r yp r o o f , u s e st h ee n g l i s ha n dc h i n e s e l a n g u a g et e s ts e t s ，t h r o u g he x p e r i m e n tc o n f i r m e dt h a tt h i sm e t h o dw a sp r a c t i c a la n d f e a s i b l e ，c o m p a r e dt o t h ed i r e c tu s eo fl i b s v mc l a s s i f y , t h ec l a s s i f i e da c c u r a c y i n c r e a s e d9 3 5 a n d1 5 ，r e s p e c t i v e l y 2 p e r s o n a l i z e dr e c o m m e n d e rs y s t e ma r eh o ts p o t sa n dc o r et e c h n o l o g yi nt h e f i e l do fe = c o m m e r c e i nr e c e n ty e a r s ，i th a sb e e nw i d e s p r e a dc o n c e ma n dr a p i d d e v e l o p m e n t i nt h i sp a p e r , w ep r o p o s e ab a s e do nt h ec l a s s i f i c a t i o no fu s e r s m u l t i - i n t e r e s ti np e r s o n a l i z e dr e c o m m e n d e rs y s t e m t h em e t h o di sd i v i d e di n t ot w o m o d u l e s ，t h ef i r s tm o d u l ei st h el o n g - t e r mi n t e r e s tm o d u l e ( l i m ) ，f o rt h e u s e r s m u l t i - i n t e r e s tc h a r a c t e r i s t i c s ，t h r o u g ht h ec l a s s i f i c a t i o nt oi m p r o v et h ea c c u r a c y r e c o m m e n d ；t h es h o r t t e r mi n t e r e s tm o d u l ei st h es e c o n dm o d u l e ( s i m ) ，f o ru s e r s i n t e r e s t e di ns h o r t - t e r mf o c u s ，j o i n e dt h ec o n t e x to ft h ew e bl o ga n a l y s i s f i n a l l y , t h i sa r t i c l ec a r r yo u tt h ee x p e r i m e n tc o n f i r m e dt h el i m & s i mc l a s s i f i c a t i o ne f f e c t f e a s i b l e c o m p a r e dt o t r a d i t i o n a lm e t h o d s ，r e c o m m e n d e ra c c u r a c ya n dc u s t o m e r v l s a t i s f yh a v e b e e nu p g r a d e d k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；k r e c a l l sc l u s t e r i n ga l g o r i t h m ；t w os t a g e sm u l t i l a b e l s v mc l a s s i f i e r ；p e r s o n a l i z e dr e c o m m e n d e r v i l 獨創(chuàng)性聲明 本人聲明所呈交的論文是我個人在導師指導下進行的研究工 作及取得的研究成果。盡我所知，除了文中特別加以標注和致謝 的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫的研究成果，也 不包含為獲得江西財經(jīng)大學或其他教育機構(gòu)的學位或證書所使用 過的材料。與我一同工作的同志對本研究所做的任何貢獻均已在 論文中作了明確的說明并表示了謝意。 張蟬吼丑里方 關(guān)于論文使用授權(quán)的說明 本人完全了解江西財經(jīng)大學有關(guān)保留、使用學位論文的規(guī)定， 即：學校有權(quán)保留送交論文的復印件，允許論文被查閱和借閱； 學校可以公布論文的全部或部分內(nèi)容，可以采用影印、縮印或其 他復制手段保存論文。 ( 保密的論文在解密后遵守此規(guī)定) 蘭徭 日期：2 2 ：墮2 口 1 緒論 l 緒論 1 1 課題的背景及意義 隨著i n t e m e t 的迅猛發(fā)展，w e b ，電子郵件，聊天室和數(shù)字圖書館等電子文 本成幾何級數(shù)迅猛增長，當前我們正處于一個信息爆炸的時代。假定信息雜亂無 序，信息量又如此巨大，我們將很難找到自己所需的信息。一方面，互聯(lián)網(wǎng)上面 蘊涵的信息是海量的，人們可以隨意獲取，但是面對規(guī)模巨大的信息汪洋，人們 又無法有效地利用這些資源，這增加了人們對于快速、自動文本分類的迫切需求： 另一方面激增的信息資源又為基于機器學習的文本分類方法準備了充分的實驗 數(shù)據(jù)。通過文本自動分類系統(tǒng)把文本數(shù)據(jù)進行歸類，可以幫助人們更好地發(fā)現(xiàn)、 過濾和分析文本信息資源。 文本分類是基于文本內(nèi)容將待定文本劃分到一個或多個預先定義的類中的 方法，最初的文本分類是依靠專家手工進行的，它對領(lǐng)域知識要求較高且花費巨 大，不能滿足大規(guī)模文檔處理的要求。2 0 世紀9 0 年代逐漸成熟的基于機器學 習的文本分類方法，更注重分類器的模型自動挖掘和生成及動態(tài)優(yōu)化能力，在分 類效果和靈活性上都比之前基于知識工程和專家系統(tǒng)的文本分類模式有所突破， 成為相關(guān)領(lǐng)域研究和應(yīng)用的經(jīng)典范例。典型的自動文本分類方法包括決策樹和規(guī) 則學習算法、回歸方法、k n n 方法、樸素貝葉斯方法、神經(jīng)網(wǎng)絡(luò)、支持向量機 篁f l 】 寸。 文本自動分類的目的就是對文本集進行有序組織，把相似與相關(guān)的文本組織 在一起。它作為知識的組織工具，為信息檢索提供了更高效的搜索策略和更準確 地查詢結(jié)果，使得檢索的查全率和準確率都得到了提高。傳統(tǒng)的人工分類的做法 存在許多弊端，如耗費大量人力、物力以及精力，且分類結(jié)果一致性不高。因而， 構(gòu)造一個有效的文本分類系統(tǒng)是十分必要且必需的。文本分類作為信息過濾、信 息檢索、搜索引擎、文本數(shù)據(jù)庫、數(shù)字化圖書館等領(lǐng)域的技術(shù)基礎(chǔ)，有著廣泛的 應(yīng)用前景。 1 2 國內(nèi)外研究現(xiàn)狀 1 2 1 國外現(xiàn)狀 國外自動分類研究始于1 9 5 0 年末，h p l u h n 在這一領(lǐng)域進行了開創(chuàng)性的研 二階段文本分類器及分類在推薦系統(tǒng)中的應(yīng)用 究，他將詞頻統(tǒng)計的思想引入文本分類中。接著，1 9 6 0 年m a r o n 在j o u r n a lo f a s m 上發(fā)表了有關(guān)自動分類的第一篇論文“o nr e l e v a n c ep r o b a b i l i t i ci n d e x i n ga n d i n f o r m a r i o nr e t r i r a l ”。其后許多學者在這一領(lǐng)域進行了卓有成效的研究。國外文 本數(shù)據(jù)分類研究大體上可以分為三個階段： 第一階段是從2 0 世紀6 0 年代直到2 0 世紀8 0 年代前，m a r o n 和k u h n 提出了概率 標引模型，并應(yīng)用于信息檢索領(lǐng)域【2 ，3 】；1 9 6 2 年r o s e n b l a t t 設(shè)計了感知機，通過具 有閾值的神經(jīng)元處理二類分類問題【4 】；s a l o n 于1 9 7 5 年提出了向量空間模型用于 對文本進行描述1 5 1 。這一階段主要是集中在對分類理論的研究。 第二階段是2 0 世紀8 0 年代到9 0 年代。這期間最有效的文本分類系統(tǒng)一直 是由專家人工構(gòu)建的基于知識工程技術(shù)的分類系統(tǒng)。典型的系統(tǒng)為c o n s t r u e 系 統(tǒng)。 第三階段是9 0 年代以后，基于機器學習和統(tǒng)計學習的分類技術(shù)開始取代基 于知識工程的方法成為文本分類的主流技術(shù)，這種分類方法不再需要專家的介 入，節(jié)約了大量的人力資源，同時加快了分類系統(tǒng)的建立速度，至此，文本自動 分類技術(shù)才開始蓬勃發(fā)展，形成了眾多的分類模型和分類算法。 國外當前流行的文本分類方法包括r o c c h i o 法及其變異方法、k 近鄰法 ( 1 心n ) 、決策樹、樸素貝葉斯、貝葉斯網(wǎng)絡(luò)、支持向量機( s v m ) 等方法。近幾 年，國外的研究主要集中在以下幾方面：一方面是針對已有分類方法進行改良， 如使用詞典【1o 】或w i k i t l l l 擴展特征值選取，一方面是針對半監(jiān)督文本分類方法的 研究【1 扣1 3 1 。 國外很多研究人員對英文文本分類領(lǐng)域的各個問題都有相當深入的研究，對 幾種流行的方法進行了大量的對比研究。s e b a s t i a n if 與y a n gy i m i n g 1 ，1 4 1 分別在 一些標準英文文本分類數(shù)據(jù)集上對一些流行的方法進行了理論分析和對比研究。 結(jié)果表明這些算法各有優(yōu)缺，沒有占絕對優(yōu)勢的算法，總的來講，支持向量機、 k 近鄰和神經(jīng)網(wǎng)絡(luò)具有比較高的分類準確率，但是它們的分類時間比較長，而貝 葉斯方法分類精度稍差但具有較快的分類速度。找到一種分類精度高分類速度快 的文本分類算法是文本自動分類領(lǐng)域的研究方向之一。 1 2 2 國內(nèi)現(xiàn)狀 國內(nèi)對文本分類的研究起步較晚，開始于2 0 世紀8 0 年代初期。大體上經(jīng)歷 2 1 緒論 了可行性探討、輔助分類、自動分類系統(tǒng)三個發(fā)展階段。早期對中文文本的分類 研究較少，采用的技術(shù)也主要是把英文文本分類的技術(shù)應(yīng)用到中文文本分類當 中。自上世紀9 0 年代后期才開始著重于對中文文本分類的研究，結(jié)合中文文本 的特點，形成中文文本數(shù)據(jù)分類研究體系。 1 9 8 1 年候漢清先生首先對自動分類在文獻中的應(yīng)用作了探討，從計算機管 理分類、計算機分類檢索、計算機自動分類、機編分類等四個方面介紹了國外的 發(fā)展概況【1 5 1 。這是理論方面，隨后在1 9 8 6 年，上海交大電腦應(yīng)用技術(shù)研究所的 朱蘭娟、王永成等開發(fā)的中文科技文獻( 計算機類) 實驗性分類系統(tǒng)。該系統(tǒng)檢索 并累計特征詞在類主題表中的類歸屬度，采用b a y e s 分類準則，對每一篇文獻計 算相應(yīng)的條件概率，當該文獻屬于某一類的條件概率超過一定閩值的時候，就把 它劃分為該類，但是由于該系統(tǒng)缺乏全文、沒有摘要、類目必須事先確定，分類 結(jié)構(gòu)粗糙，不適合專用文獻【1 6 】。1 9 9 8 年，東北大學的計算機系的張月杰、姚天 順研制的新聞?wù)Z料漢語文本自動分類模型，通過計算預定義類別和文本特征項之 間相關(guān)性來進行自動分類的。該分類方法的特征向量規(guī)范化，采用多重加權(quán)處理 方法【17 1 。 在評測方面，已經(jīng)有了比較標準的語料庫，如復旦大學自然語言處理小組提 供的文本分類語料庫和人民日報標注語料庫，一些搜索引擎公司也提供相應(yīng)的語 料的下載，如s o h u 等；在分詞方面，主要的代表是中科院計算所中文詞語一 體化分析系統(tǒng)i c t c l a s ，其次有國家語委文字所應(yīng)用句法分析技術(shù)的漢語自動 分詞系統(tǒng)、清華大學的s e g t a g 系統(tǒng)和哈爾濱工業(yè)大學詞法分析系統(tǒng)等。這些 都為中文文本分類技術(shù)的深入研究提供了一個良好的環(huán)境?，F(xiàn)有中文文本分類的 方法是支持向量機、最近鄰分類、b o o s t i n g 、基于序列的文本分類等。 以計算機學報、軟件學報、中文信息學報近期發(fā)表的文章為參考，可以大致 了解國內(nèi)這二年的研究狀況。針對基于支持度一置信度架構(gòu)的關(guān)聯(lián)分類方法僅僅 是選擇頻繁文字構(gòu)建分類規(guī)則，忽略了文字的分類有效性，陳志雄等人提出了基 于信息增益的關(guān)聯(lián)分類算法【1 8 】。孫景廣等人提出了一種使用知網(wǎng)作為語義資源選 取分類特征，并使用最大熵模型進行分類的方法，該方法用于問答系統(tǒng)中的問題 分類【1 9 1 。針對半監(jiān)督的文本分類，鄭海清等人提出一種基于緊密度衡量的半監(jiān)督 的文本分類算法，其主要思路是先提取出一些可信的負例，然后再根據(jù)緊密度衡 二階段文本分類器及分類在推薦系統(tǒng)中的應(yīng)用 量對提取出的負例集合進行擴展，進而得到包含正負例的訓練集合，從而提高分 類器的性能【2 0 1 。最近鄰分類器是假定局部的類條件概率不變，而這個假定在高維 特征空間中無效，王煜等人針對這種情況提出了一種改進k n n 算法1 2 。由于 l 心n 分類方法存在著計算量大和訓練文檔分布不均所造成的分類準確率下降等 問題，王修君等人提出基于最小化學習誤差的增量思想，將學習型矢量量化( l v q ) 和生長型神經(jīng)氣( g n g ) 結(jié)合起來提出一種新的增量學習型矢量量化方法【2 2 1 。 文本分類的研究主要圍繞算法方面進行，如特征提取、權(quán)重計算、分類模型 的算法的分析與改進，而劉華則從特征項的粒度選擇和獲取方面進行研究，認為 關(guān)鍵短語作為特征項有助于文本分類】。王小冷等人提出基于n 一伊鋤模型的 貝葉斯分類方法，該方法利用了所有相鄰漢字之間的依賴關(guān)系，提高了抗噪音能 力【2 4 1 。孫宏綱等人將h o w n e t 語義詞典引入到v s m 特征向量生成的過程中，通 過在語義層面擴展特征向量的維數(shù)，即合理地增加特征向量的維數(shù)，使擴展后的 特征向量不僅較好的符合原始文檔的語義要求，又能滿足v s m 分類模型的要 求，進而改善復雜語料的分類結(jié)剁2 5 1 。 數(shù)據(jù)流具有數(shù)據(jù)持續(xù)到達、到達速度快、數(shù)據(jù)規(guī)模巨大等特點，王濤等人針 對這種情況提出一種基于線索化排序- - x 樹的增量模糊決策樹分類算法【2 6 】。傳統(tǒng) 的文本分類方法，即非增量學習算法，根據(jù)當前所獲得的所有訓練樣本計算得到 文本分類模型，存在二方面問題，一是訓練樣本很難一次性獲得，二是內(nèi)存限制。 羅長升等人提出基于推拉策略的文本分類增量學習方法1 2 7 1 。隨著深度網(wǎng)的重要日 益顯著，d e e pw 曲數(shù)據(jù)庫資源信息進行分類或聚類逐漸成為研究熱點1 2 s l 。分類 器對某些類別的判別能力不強，我們稱這些類別為混淆類?；煜惖拇嬖谠斐闪?文本分類性能的下降，朱靖波等人提出一種混淆類的判別技術(shù)，并采用兩個階段 的分類來提高分類性能【2 9 1 。l d a ( l a t e n td i r i c h l e ta l l o c a t i o n ) 模型是近年來提出 的一種能夠提取文本隱含主題的非監(jiān)督學習模型，針對l d a 模型用于分類時強 制分配隱含主題的缺陷，李文波等人提出提出了一種附加類別標簽的l d a 模型 p o i o 總的來講，國內(nèi)在分類方面取得很大進展，但相對國外的研究還存一定差距， 需要我們進一步的研究。 1 3 本文的工作和論文組織 4 1 緒論 基于機器學習文本分類技術(shù)由文本的表示( r e p r e s e n t a t i o n ) 、分類方法及效果 ( e f f e c t i v e n e s s ) 評估三個部分組成。本文主要研究分類方法。聚類可以看成是無“標 簽 的分類過程，與分類有著密切關(guān)系。本文針對二者的關(guān)系，提出先聚類再分 類的二階段分類方法。其基本思想是：第一階段先對文本進行聚類，并對聚類結(jié) 果進行樣本抽樣，對抽樣結(jié)果不理想的類進行第二階段分類。本文的主要工作有： ( 1 ) 采用k m e a n s 與s v m 結(jié)合，即：在第一階段的聚類中采用k - m e a n s 算法， 第二階段分類采用s v m 算法。第一階段的k m e a n s 算法采用j a 、，a 實現(xiàn)，第二 階段的s v m 采用l i b s v m 軟件。方案采用中、英文語料。 ( 2 ) 作為中文文本分類技術(shù)的應(yīng)用之一，根據(jù)當前電子商務(wù)推薦系統(tǒng)的不 足，提出基于分類的用戶多興趣個性化推薦方法。該方法分為二個模塊，第一模 塊是長期興趣模塊( l i m ) ，針對用戶多興趣的特征，通過分類來提高推薦準確 度；第二是短期興趣模塊( s i m ) ，針對用戶短期興趣的專注性，引入w e b 日志 上下文分析的方法。文中分別對l i m 和s i m 進行了實驗證實，證實該方法切實 可行，相較于傳統(tǒng)方法，推薦準確度及用戶滿意度都得到了較好提升。 本文的組織結(jié)構(gòu)： 第一章：分析了分類技術(shù)發(fā)展的國內(nèi)外現(xiàn)狀，提出本文的工作及組織結(jié)構(gòu)； 第二章：介紹中文文本分類基礎(chǔ)理論和系統(tǒng)架構(gòu)； 第三章：提出二階段分類器的設(shè)計構(gòu)想，并通過實驗對分類器進行了實驗； 第四章：在電子商務(wù)領(lǐng)域中，分類技術(shù)有著廣泛的應(yīng)用，本文根據(jù)現(xiàn)有推薦 系統(tǒng)的不足，提出基于分類的用戶多興趣個性化推薦方法； 第五章：對本文的工作進行總結(jié)，并提出下一步的工作打算。 二階段文本分類器及分類在推薦系統(tǒng)中的應(yīng)用 2 中文文本分類技術(shù)概述 文本自動分類的研究包括很多學科領(lǐng)域，包括自然語言處理，圖書館科學中 的分類學，數(shù)學領(lǐng)域的統(tǒng)計學等知識，以及計算機領(lǐng)域的模式識別、人工神經(jīng)網(wǎng) 絡(luò)等研究課題。本章將分別介紹文本分類的基本概念和文本自動分類系統(tǒng)的基礎(chǔ) 理論及相關(guān)技術(shù)，并對其典型的系統(tǒng)結(jié)構(gòu)進行了分析研究【3 1 1 。 2 1 文本分類定義 文本分類是指按照預先定義的分類體系，根據(jù)文本的內(nèi)容自動地將文本集合 的每個文本歸入某個類別，這是分類過程，它需經(jīng)過二個過程：輸入與輸出，系 統(tǒng)的輸入是需要進行分類處理的大量文本，而輸出是與文本關(guān)聯(lián)的類別。簡單地 說，文本分類就是對文檔標以合適的文本類標簽。 從數(shù)學的角度來看，文本分類也可以看成是一個映射過程，它將未標明類別 的文本映射到現(xiàn)有類別中，這種映射可以是一一映射，也可以是一對多映射，因 為通常一篇文本可以與多個類別相關(guān)聯(lián)。文本分類的映射規(guī)則是：系統(tǒng)根據(jù)已知 類別中若干樣本的數(shù)據(jù)信息得出各類別的特征，然后總結(jié)出分類的規(guī)律性，建立 類別判別公式和判別規(guī)則，下次當遇到新文本時，根據(jù)總結(jié)出的類別判別規(guī)則確 定文本所屬的類別，從而得到正確的分類判別。 在理論研究方面，對單類別分類的研究要多于對多類別分類的研究。主要原 因是由于單類別分類算法與多類別分類算法存在很多相通之處，二者之間的轉(zhuǎn)化 必須滿足這樣一個假設(shè)條件，即各個類之間是獨立的，沒有相互依存關(guān)系或其它 影響，當然在實際應(yīng)用中，絕大多數(shù)情況是可以滿足此假設(shè)條件的。因此，在文 本分類的研究中，大部分實驗都是基于單類別分類問題的探討，不過，本文的研 究是基于多類別。 2 2 自動分詞 漢語自動分詞是對漢語文本進行自動分析的第一個步驟。大家可以這樣設(shè)想 漢語自動分詞過程的困難：如果把某個英語文本中的所有空格符都去掉，然后讓 計算機自動恢復文本中原有的空格符，這就是詞的識別過程，此過程的主要問題 是對大量歧義現(xiàn)象的處理；而中文文本是不存在空格的，所以相對于英文文本首 先必須解決分詞的問題。 6 2 中文文本分類技術(shù)概述 分詞體現(xiàn)了漢語與英語的顯著的不同。英語文本是小字符集上的已充分分隔 開的詞串，而漢語文本是大字符集上的連續(xù)字串。這里把字串分隔成詞串，就是自 動分詞系統(tǒng)需要做的工作。由于“在中文信息處理中，凡是涉及句法，語義等研 究項目都要以詞為基本單位“，所以中文分詞技術(shù)屬于自然語言處理技術(shù)范疇， 對于一句話，人可以通過自己的知識來明白哪些是詞，哪些不是詞，但如何讓計 算機也能理解? 其處理過程就是分詞算法，現(xiàn)有的分詞算法包括三大類：基于字 符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計的分詞方法。 2 2 1 自動分詞方法 ( 1 ) 基于字符串匹配的分詞方法【3 2 】 這類方法又稱機械分詞方法，它是按照一定的規(guī)則將待分析的漢字串與機器 詞典中的詞條進行配，若在詞典中找到這個字符串，則匹配成功( 識別出一個詞) ， 如沒有找到則為不成功。機械分詞的方法又可以按不同的方式區(qū)分為不同種類： 一是按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配二種方 法；二是按照不同長度優(yōu)先匹配的情況，可以分為最大( 最長) 匹配和最小( 最 短) 匹配方法：三是按照是否與詞性標注過程相結(jié)合，又可以分為單純分詞方法 和分詞與標注相結(jié)合的一體化方法。常用的幾種機械分詞方法如下：正向最大匹 配法( 由左到右的方向) 、逆向最大匹配法( 由右到左的方向) 和最少切分( 使 每一句中切出的詞數(shù)最小) 。 ( 2 ) 基于理解的分詞方法 這種分詞方法是在語義上進行分詞，涉及到自然語言處理的知識，它通過讓 計算機模擬人對句子的理解，達到識別詞的效果，其基本思想就是在分詞的同時， 進行句法、語義分析，利用語義信息來處理歧義現(xiàn)象。這種分詞方法通常包括三 個部分：分詞子系統(tǒng)、句法語義子系統(tǒng)、總控部分。在總控部分的協(xié)調(diào)下，分詞 子系統(tǒng)可以獲得有關(guān)詞、句子等的句法和語義信息來對分詞歧義進行判斷，這模 擬了人對句子的理解過程，它需要使用大量的語言知識和信息。但由于漢語語言 知識的復雜性，難以將各種語言信息組織成機器可直接讀取與理解的形式，因此 目前基于理解的分詞系統(tǒng)還處在試驗階段。 ( 3 ) 基于統(tǒng)計的分詞方法 從形式上看，詞是穩(wěn)定的字的組合，所以在上下文中相鄰的字同時出現(xiàn)的次 二階段文本分類器及分類在推薦系統(tǒng)中的應(yīng)用 數(shù)越多，就越有可能構(gòu)成一個詞。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好的 反映成詞的可信度，所以我們可以對語料中相鄰共現(xiàn)的各個字的組合的頻度進行 統(tǒng)計，計算它們的互現(xiàn)信息。這里，定義兩個字的互現(xiàn)信息，用于計算兩個漢字 x 、y 的相鄰共現(xiàn)概率。注意，這里的互現(xiàn)信息體現(xiàn)了漢字之間結(jié)合大系的緊密 程度，當緊密程度高于某一個閾值時，便可認為此字組可能構(gòu)成了一個詞，反之 則不應(yīng)該把它分成一個詞。這種分詞方法只需對語料中的字組頻度進行預先統(tǒng) 計，并不需要切分詞典，因而又叫做無詞典分詞法也稱統(tǒng)計取詞方法。但這種方 法也有一定的局限性，會經(jīng)常抽出一些并不是詞的常用字組，例如f 這一j 、我 的j 、之一j 、f 許多的j 、有的j 等，并且對常用詞的識別精度不高，時空開銷 很大。實際應(yīng)用的統(tǒng)計分詞系統(tǒng)都是與機械分詞系統(tǒng)結(jié)合在一起使用，首先使用 一部基本的分詞詞典( 常用詞詞典) 進行串匹配分詞，同時使用統(tǒng)計方法識別一 些新的詞，即將串頻統(tǒng)計和串匹配結(jié)合起來，既發(fā)揮匹配分詞切分速度快、效率 高的特點，又利用了無詞典分詞結(jié)合上下文識別生詞、自動消除歧義的優(yōu)點。 2 2 2 分詞中的難題 成熟的分詞算法有了，是否就能容易的解決中文分詞的所有問題呢? 事實遠 非如此。中文不象英文，它是一種十分復雜的語言，讓計算機理解中文語言更為 困難。在中文分詞過程中，有幾個難題一直沒有完全突破。 ( 1 ) 歧義識別 典型的歧義有交集型歧義( 約占全部歧義的8 5 以上) 和組合型歧義。這種 歧義的消除只有向分詞系統(tǒng)提供進一步的語法、語義知識才有可能作出正確的決 策。排除歧義常常使用的方法是添加其它信息，如詞頻、詞長、詞間關(guān)系等信息， 比如“真正在 這個組合中，“真作為單字詞的頻率大大低于”在”作為單字詞的 頻率，所以應(yīng)切成”真正在”。有時切分歧義發(fā)生在- d , 段文字中，但我們?yōu)榱伺懦?歧義則需要看較長的一段文字，比如”學生會”既可能是一個名詞，指一種學生組織， 也可能是”學生會”，其中”會”為”可能”或”能夠”的意思，具體取哪一種，還需要結(jié) 合上下文的信息，如在“學生會主席 中只能是前者，在”學生會去”中只能是后者， 在“學生會組織義演活動 中歧義仍然排除不了，則需要看更多的語境信息。 ( 2 ) 新詞識別 新詞就是那些在字典中都沒有收錄過，但又確實能稱為詞的那些詞。典型的 8 2 中文文本分類技術(shù)概述 是人名，大家可以很容易理解句子f 王軍虎去廣州了j 中，王軍虎j 是個詞， 因為它代表一個人的名字，但計算機如何去識別就困難了。因為如果把王軍虎j 做為一個詞收錄到字典中去，中國有那么多名字，且時時刻刻都有新增的人名， 收錄這些人名本身就是一項巨大的工程，同時也會大大增加詞典的容量，降低分 詞的速度。即使這項工作可以完成，還是會存在其它問題，例如：在句子f 王軍 虎頭虎腦的j 中，f 王軍虎j 就不能算詞。新詞中除了人名以外，還有地名、機 構(gòu)名、商標名、產(chǎn)品名、省略語、簡稱等都是很難處理的問題，而且這些又正好 是人們經(jīng)常使用的詞。因此，分詞系統(tǒng)中的新詞識別十分重要，所以新詞識別準 確率已經(jīng)成為評價一個分詞系統(tǒng)好壞的重要標志。 ( 3 ) 分詞與理解的先后 計算機無法像人在閱讀漢語文章時那樣邊理解邊分詞，而只能是先分詞后理 解，因為計算機理解文本的前提是識別出詞、獲得詞的各項信息。這就是邏輯上 的兩難：分詞要以理解為前提，而理解又是以分詞為前提。由于計算機只能在對 輸入文本尚無理解的條件下進行分詞，則任何分詞系統(tǒng)都不可能企求百分之百的 切分正確率。 2 3 文本表示 ( 1 ) 向量空間模型 文本是一個由眾多字符構(gòu)成的字符串，無法被學習算法自己用于訓練或分 類，所以要將機器學習技術(shù)運用于文本分類問題，首先需要將作為訓練和分類的 文檔轉(zhuǎn)化為電腦易于處理的向量形式。即運用各種文本形式化表示方法，最常用 的如向量空間模型對文檔進行文本形式化表示。 文本形式化首先要解決的問題是特征粒度的選擇，即是選擇字、詞、句或其 他來分類。剛開始的選擇是用字，后來發(fā)現(xiàn)用二元同現(xiàn)字串的分類方法的準確率 要比用字的方法高，所以現(xiàn)在又使用詞，隨著漢語自動分詞技術(shù)的日益成熟，基 于詞的漢語文本自動分類已經(jīng)成為了我們的一個研究熱點。實踐表明基于詞的分 類方法優(yōu)于基于字和基于二元同現(xiàn)串的分類方法。特征粒度確定了以后，通常文 本表示方法有：向量空間模型( v e c t o rs p a c em o d e l ) ，布爾模型( b o o l e a nm o d e l ) ， 概率模型( p r o b a b i l i s t i cm o d e l ) ，聚類模型( c l u s t e rm o d e l ) 和基于知識模型 ( k n o w l e d g e b a s e dm o d e l ) 等。 9 二階段文本分類器及分類在推薦系統(tǒng)中的應(yīng)用 g s a l t o n 提出的向量空間模型【3 3 】( v s m ) 有較好的計算性和可操作性，相對 應(yīng)用也較廣泛且效果較好的一種模型，向量空間模型成功應(yīng)用于信息檢索領(lǐng)域， 隨后推廣到文本分類領(lǐng)域。向量空間模型有一個基本假設(shè)是，一份文檔所屬的類 別僅與某些特定的詞或詞組在該文檔中出現(xiàn)的頻數(shù)有關(guān)，但是與這些單河或詞組 在該文檔中出現(xiàn)的位置或順序無關(guān)。我們?nèi)绻麑?gòu)成文本的各種語義單位( 如單 詞、詞組) 統(tǒng)稱為“詞項 ，把詞項在文本中出現(xiàn)的頻數(shù)稱為“詞頻 ，文檔中蘊 涵的各個詞項的詞頻信息就足以用來對其進行正確的分類。在向量空間模型中文 本被形式化為n 維空間中的向量： d = ( 2 1 ) 上式為第i 個特征的權(quán)重。如果特征項選擇為詞語，那么就刻畫出了詞語在 表示文本內(nèi)容時所起到的重要程度。 ( 2 ) 權(quán)值計算公式 目前，賦權(quán)重最普遍的方法是運用統(tǒng)計的方法，即用文本的統(tǒng)計信息，主要 是詞頻信息，來計算特征項的權(quán)重。最初的特征項權(quán)重計算方法是o 、1 賦值法， 即布爾權(quán)重( b o o l e a nw e i g h t i n g ) 。如果特征項未出現(xiàn)，則其權(quán)重為零；如果特征 項出現(xiàn)次數(shù)大于零，則其權(quán)重為l 。布爾權(quán)重無法體現(xiàn)特征項在文本中的作用程 度，故逐漸被更精確的詞頻代替。 詞頻通常分為絕對詞頻和相對詞頻。絕對詞頻，就是使用特征項在文本中出 現(xiàn)的頻率表示文本；相對詞頻為歸一化的詞頻，計算方法主要運用t f i d f 公式。 其中t f 是特征項在文本中的絕對頻率，而i d f 表示特征項在文本中的文本內(nèi)頻 數(shù)。t f 越大，此特征項在文檔集中出現(xiàn)的范圍越廣，說明它的重要程度越高； i d f 越大，此特征項在文檔中的分布越集中，說明它在區(qū)分該文檔內(nèi)容屬性方面 的能力越強。 目前存在多種t f i d f 公式，下式是一種使用比較普遍的t f i d f 公式： 緲( f ，西：絲壘絲絲絲型墜一( 2 - 2 ) 蔚【( ，d ) l o g ( n n , + o 0 1 ) 】2 其中，w ( t ，孑) 為詞t 在孑的權(quán)重，f ( t ，西) 為詞t 在萬的詞頻，n 為訓練文本 的總數(shù)，為訓練文本集中出現(xiàn)t 的文本數(shù)，分母為歸一化因子。 ( 3 ) 相似度計算公式 1 0 2 中文文本分類技術(shù)概述 文檔表示成向量后，文檔之間的語義相似度就可以通過空間中的這兩個向量 間的幾何關(guān)系來進行度量，主要是采用有相似函數(shù)與距離函數(shù)兩類函數(shù)。 相似度通?？梢圆捎萌N函數(shù)來計算，即內(nèi)積、夾角余弦與相關(guān)系數(shù)。 內(nèi)積函數(shù)是一種簡單且常用的相似度計算函數(shù)，在基于支持向量的分類算法 中被廣泛使用。計算公式如下： 溉= z z ( 2 - 3 ) j 夾角余弦函數(shù)是采用空間中的兩個向量的夾角的余弦值來度量文檔之間的 語義相似度。兩個向量在空間中的夾角越小，余弦值就越大，表明其語義相似度 越高，文檔越相似，反之如果夾角大，則文檔相似度低。余弦函數(shù)是文本領(lǐng)域中 應(yīng)用最廣泛的相似度計算函數(shù)。它的計算公式如下： 置r s i m , = ，：蘭：；：一 ( 2 - 4 ) ，yx ：r 2 y ，j 相關(guān)系數(shù)是對向量做標準差標準化后的余弦函數(shù)。它表示兩個向量的線性相 關(guān)的程度。 2 4 特征提取 在中文文本分類中，文本集經(jīng)過分詞后變成詞集，然后去掉停用詞得到特征 集。但是，特征集一般仍然是個高維的特征空間，對于分類算法來說維數(shù)太大。 因此，面臨尋求一種有效的特征抽取方法，用于降低特征空間的維數(shù)，提高分類 的效率和精度。特征提取算法是文本分類中的關(guān)鍵技術(shù)和瓶頸技術(shù)，如何找到最 小的特征子集來表達文本主題內(nèi)容，是文本特征抽取算法的研究所在。 常見的特征選擇f 3 4 】，【3 5 】有：信息增益( i g ) 、文檔頻率( d f ) 、z 統(tǒng)計- 量( c h i ) 、 互信息( m i ) 等。這些降維算法各有優(yōu)缺點，需要根據(jù)具體系統(tǒng)應(yīng)用來確定最優(yōu)方 法。但其基本思想都是對每一個特征即詞條，計算它的某種統(tǒng)計的度量值，然后 設(shè)定一個閾值t ，把度量值小于閾值t 的那些特征過濾掉，剩下的即認為是有效 特征。下面簡單介紹一下常用的各種特征選擇方法。 ( 1 ) 特征詞的文檔頻率( d f ) 文本中某個特征的文檔頻率( d o c u m e n tf r e q u e n c y ，簡記為d r ) 是指在文檔集 中含有該特征的文檔數(shù)目。之所以采用d f 作為特征選擇，是基于如下基本假設(shè)： d f 值低于某個閡值的詞條是低頻詞，它們不含或含有較少的類別信息，不應(yīng)將 二階段文本分類器及分類在推薦系統(tǒng)中的應(yīng)用 其作為特征詞來區(qū)分類別，將這樣的詞條從原始特征空間中除去，既可以降低特 征空間的維數(shù)，又能提高分類的精度。文檔頻率是最簡單的特征抽取技術(shù)，由于 其相對于訓練語料規(guī)模具有線性的計算復雜度，所以計算速度快，能夠很容易被 用于大規(guī)模語料統(tǒng)計。相反，在信息檢索研究中通常卻認為d f 值低的詞條相對 于d f 值高的詞條具有較多的信息量，不應(yīng)該將它們完全移除。不同的應(yīng)用將對 d f 值的認識不同，應(yīng)考慮具體情況來使用該方法。 ( 2 ) 信息增益方法( i g ) 信息增益( i n f o r m a t i o ng a i n ，簡記為i g ) 在機器學習領(lǐng)域被廣泛使用。對于詞 條t 和文檔類別c ，用i g 考察文檔類別c 中出現(xiàn)和不出現(xiàn)詞條t 的文檔頻數(shù)來衡 量詞條t 對于文檔類別c 的信息增益。我們采用如下的定義式： g a i n = 一i u l p ( c , ) 1 0 9 p ( c j ) + 戶( ，) ：尸( q o g 尸( q 協(xié)尸( ) ：e ( c , i t ) 1 0 9 尸( q l - ) ( 2 5 ) 其中p ( q ) 表示c 類文檔在語料中出現(xiàn)的概率，p ( t ) 表示語料中包含詞條t 的 文檔的概率，p ( qlf ) 表示文檔包含詞條t 時屬于c 類的條件概率，尸( f ) 表示語料 中不包含詞條t 的文檔的概率，尸( qi ，) 表示文檔不包含詞條t 時屬于c 的條件概 率，m 表示類別數(shù)。 ( 3 ) 互信息方法( m i ) 互信息( m u t u a li n f o r m a t i o n ，簡記為m i ) 在統(tǒng)計語言模型中得到廣泛應(yīng)用，其 中m i 值越大表明共現(xiàn)程度越大。我們先假定用a 表示包含詞條t 且屬于類別c 的文檔頻數(shù)，b 為包含t 但是不屬于c 的文檔頻數(shù)，c 表示屬于c 但是不包含t 的的文檔頻數(shù)，n 表示語料中文檔總數(shù)，則t 和c 的互信息可以由下式計算： m 一禮g 篇札g 醬叫昭 ( 4 ) x2 統(tǒng)計量( c h i ) 彳n ( 彳+ c ) ( 彳+ b ) ( 2 6 ) z 2 統(tǒng)計方法度量詞條t 和文檔類別c 之間的相關(guān)程度，并有一個基本假設(shè)t 和c 之間符合具有一階自由度的z 2 分布。詞條t 對于某類的z 2 統(tǒng)計值越高，表 明它與該類之間的相關(guān)性越大，攜帶的類別信息越多，越應(yīng)該選擇為特征詞。令 1 2 2 中文文本分類技術(shù)概述 n ，a ，b ，c 的含義同上式2 - 6 中描述的相同，這里再假定d 是既不屬于c 也不包含 t 的文檔頻數(shù)。若a d 三g 毒? c b o口 圖2 1 一條具有較小分類間隔的決策線( 實線) ，分類間隔定義為兩條平行虛線之間的距離 oo o o 己= o 圖2 - 2 具有最大分類間隔的決策線，虛線上的數(shù)據(jù)點為支持向量 圖2 1 和圖2 2 中的實線顯示了兩個可能的決策平面，每個面都可以正確分 割兩組數(shù)據(jù)。與實線平行的虛線表示決策平面平移后得到的平面，這種平移不會 造成數(shù)據(jù)的分割錯誤。平行線間的距離稱為分類間隔。s v m 就是要在訓練集中 找到具有最大分類間隔的決策平面。 可以通過在s v m 中引入軟分類間隔或者將原來的數(shù)據(jù)空間映射到更高維空 間( 該空間中的新特征包含原空間中特征的交互作用，該新空間中線性可分) 的方 法將解決線性可分情況推廣到解決線性不可分的情況。如果用內(nèi)積k ( x ，薯) 代替 最優(yōu)分類面中的點積，就相當于把原特征空間變換到了某一新的特征空間。采用 不同的內(nèi)積函數(shù)將導致不同的支持向量機算法，目前得到研究的內(nèi)積函數(shù)形式主 要有三類，它們都與己有的方法有對應(yīng)關(guān)系：分別為多項式形式的內(nèi)積函數(shù)、核 函數(shù)型內(nèi)積、s 形函數(shù)( 雙曲正切函數(shù)s i g t m o i d ) 內(nèi)積。 支持向量機的優(yōu)點在于： ( 1 ) 它是專門針對有限樣本情況的分類方法，其目標是得到現(xiàn)有信息下的最 優(yōu)解而不僅僅是樣本數(shù)趨于無窮大時的最優(yōu)值，該算法最終將轉(zhuǎn)化成為一個二次 型最優(yōu)問題，理論上得到的將是全局最優(yōu)點，避免了局部極值問題。 ( 2 ) 該方法將實際問題通過非線性變換轉(zhuǎn)換到高維的特征空間，在高維特征 二階段文本分類器及分類在推薦系統(tǒng)中的應(yīng)用 空間中構(gòu)造線性判別函數(shù)來實現(xiàn)原空間中的非線性判別函數(shù)，特殊性質(zhì)能保證具 有良好的推廣能力，計算的復雜度不再取決于空間維數(shù)，而是取決于樣本數(shù)，尤 其是樣本中的支持向量數(shù)，這些特點就可能有效地用于解決高維問題。 ( 3 ) 該方法對稀疏數(shù)據(jù)不敏感，更好的捕捉了